Lakaisumenetelmä

Kokeneet kirjoittajat eivät ole vielä tarkistaneet sivun nykyistä versiota, ja se voi poiketa merkittävästi 23.11.2021 tarkistetusta versiosta . vahvistus vaatii 1 muokkauksen .

Pyyhkäisymenetelmää ( esim . tridiagonaalinen matriisialgoritmi ) tai Thomas - algoritmia ( eng. Thomas-algoritmi ) käytetään lineaariyhtälöjärjestelmien ratkaisemiseen muotoa , jossa on tridiagonaalinen matriisi . Se on muunnelma tuntemattomien peräkkäisen eliminoinnin menetelmästä [1] . Pyyhkäisymenetelmää ehdottivat I. M. Gelfand ja O. V. Lokutsievskii (vuonna 1952 [2] ; julkaistiin 1960 [3] ja 1962 [4] ) sekä itsenäisesti muut kirjoittajat [5] . $Ax=F$ $A$

Menetelmän kuvaus

Yhtälöjärjestelmä vastaa relaatiota $Ax=F$

A_{i}x_{i-1}+B_{i}x_{i}+C_{i}x_{i+1}=F_{i}.\qquad \qquad (1)

Pyyhkäisymenetelmä perustuu oletukseen, että vaaditut tuntemattomat liittyvät toisiinsa rekursiivisen suhteen:

x_{i}=\alpha _{i+1}x_{i+1}+\beta _{i+1},

missä

i=n-1,n-2,\dots ,1.\qquad \qquad (2)

Käyttämällä tätä suhdetta ilmaisemme ja kautta ja korvaamme yhtälön (1): $x_{{i-1}}$ $x_{i}$ $x_{{i+1}}$

\left(A_{i}\alpha _{i}\alpha _{i+1}+B_{i}\alpha _{i+1}+C_{i}\right)x_{i+1 }+A_{i}\alpha _{i}\beta _{i+1}+A_{i}\beta _{i}+B_{i}\beta _{i+1}-F_{i}= 0

jossa F i on i : nnen yhtälön oikea puoli. Tämä suhde säilyy ratkaisusta riippumatta, jos tarvitset

{\begin{cases}A_{i}\alpha _{i}\alpha _{i+1}+B_{i}\alpha _{i+1}+C_{i}=0\\A_ {i}\alpha _{i}\beta _{i+1}+A_{i}\beta _{i}+B_{i}\beta _{i+1}-F_{i}=0\end {tapaukset}}

Tämä tarkoittaa:

{\begin{cases}\alpha _{i+1}={\dfrac {-C_{i}}{A_{i}\alpha _{i}+B_{i}}}\\\beta _{i+1}={\dfrac {F_{i}-A_{i}\beta _{i}}{A_{i}\alpha _{i}+B_{i}}}\end{cases} }

Ensimmäisestä yhtälöstä saamme:

{\begin{cases}\alpha _{2}=-C_{1}/B_{1}\\\beta _{2}=F_{1}/B_{1}\end{cases))

Kun pyyhkäisykertoimet ja , saadaan yhtälön (2) avulla järjestelmän ratkaisu. Jossa, $\alpha$ $\beeta$

x_{i}={\alpha _{i+1}x_{i+1}+\beta _{i+1)),

i=n-1\ldots 1

x_{n}={\frac {F_{n}-A_{n}\beta _{n}}{B_{n}+A_{n}\alpha _{n}}}

Toinen tapa selittää pyyhkäisymenetelmän olemusta, lähempänä äärellisten erojen menetelmien terminologiaa ja selittää sen nimen alkuperää, on seuraava: muunnamme yhtälön (1) vastaavaksi yhtälöksi

A'x=F'\qquad \qquad (1')

ylidiagonaalisen (overdiagonaalisen) matriisin kanssa

A'={\begin{pmatrix}B_{1}'&C_{1}&0&0&\pisteet &0&0\\0&B_{2}'&C_{2}&0&\pisteet &0&0\\0&0&B_{3}'&C_{3 }&\pisteet &0&0\\\pisteet &\pisteet &\pisteet &\pisteet &\pisteet &\pisteet &\pisteet \\\pisteet &\pisteet &\pisteet &\pisteet &\pisteet &\pisteet &\pisteet \ \\pisteet &\pisteet &\pisteet &\pisteet &0&B'_{n-1}&C_{n-1}\\0&0&0&0&\pisteet &0&B_{n}'\end{pmatrix}}

Laskelmat suoritetaan kahdessa vaiheessa. Ensimmäisessä vaiheessa lasketaan matriisin ja vektorin komponentit alkaen - $B_{i}'$ $F'$ $i=2$ $i=n:$

B'_{1}=B_{1};

B'_{i}=B_{i}-{\frac {A_{i}}{B'_{i-1}}}C_{i-1},

F'_{1}=F_{1};

F'_{i}=F_{i}-{\frac {A_{i}}{B'_{i-1}}}F'_{i-1}.

Toisessa vaiheessa ratkaisu lasketaan: $i = n, n-1, \pisteet, 1$

x_{n}={\frac {F'_{n}}{B'_{n}}};

x_{i}={\frac {F'_{i}-C_{i}x_{i+1}}{B'_{i}}}.

Tämä laskentakaavio selittää myös tämän menetelmän englanninkielisen termin[ selventää ] "sukkula" .

Jotta pyyhkäisymenetelmän kaavat olisivat sovellettavissa, matriisin A diagonaalinen dominanssin ominaisuus riittää .

Käyttöesimerkki

Tridiagonaalisia matriiseja, joissa käytetään yksinkertaista pyyhkäisymenetelmää, syntyy usein ratkaistaessa kahden riippumattoman muuttujan differentiaaliyhtälöitä äärellisen eron menetelmällä . Tarkastellaan esimerkiksi lineaarisen yksiulotteisen lämpöyhtälön ratkaisua :

${\frac {\partial u}{\partial t}}-a^{2}{\frac {\partial ^{2}u}{\partial x^{2}}}=f(x, t),$

missä on positiivinen vakio (luku on lämpödiffuusivuus ) ja on lämmönlähteiden funktio [6] . Haluttu toiminto asettaa lämpötilan pisteessä, jonka koordinaatit ovat ajanhetkellä . $a$ $a^2$ $f(x,t)$ ${\näyttötyyli u=u(x,t)}$ $x$ $t$

Diskretisoidaan tämä yhtälö yhtenäisellä ruudukolla, jossa on tila- ja aikaaskel . Tässä tapauksessa jatkuvat funktiot ja korvataan niiden erillisillä vastineilla ja , ja tila- ja ajalliset derivaatat korvataan äärellisillä eroilla: $h$ $\tau$ $u(x, t)$ $f(x,t)$ $u_{i}^{j}=u(x_{i},t_{j})$ $f_{i}^{j}=f(x_{i},t_{j})$

$\left.{\frac {\partial u}{\partial t))\right|_{t=t_{j))\to {\frac {u(x,t_{j+1})- u(x,t_{j})}{\tau )),$

$\left.{\frac {\partial ^{2}u}{\partial x^{2}}}\right|_{x=x_{i}}\to {\frac {u(x_{ i+1},t)-2u(x_{i},t)+u(x_{i-1},t)}{h^{2}}}.$

Kerroksella olevien suureiden arvot katsotaan tunnetuiksi (saatu alkuolosuhteiden diskretoinnin tuloksena tai yhtälön ratkaisun seurauksena edellisessä aikavaiheessa). Tarkastellaan edelleen implisiittistä ajassa olevaa approksimaatiota, jossa lämmönlähteiden ja lämpövirtojen arvot otetaan seuraavasta aikakerroksesta . Vastaavalla lineaaristen algebrallisten yhtälöiden järjestelmällä tuntemattomille arvoille on muoto ${\näyttötyyli t^{j))$ $t^{j+1}$ $u_{i}^{j+1}$

${\frac {u_{i}^{j+1}-u_{i}^{j}}{\tau }}-a^{2}{\frac {u_{i+1}^{ j+1}-2u_{i}^{j+1}+u_{i-1}^{j+1}}{h^{2}}}=f_{i}^{j+1}.$

Siirtämällä tunnetut suureet oikealle, kertomalla ja ryhmittelemällä kertoimet, saamme SLAE:n lopulliseen muotoon $\tau$

${\frac {-a^{2}\tau }{h^{2}}}u_{i-1}^{j+1}+\left(1+2{\frac {a^{ 2}\tau }{h^{2}}}\right)u_{i}^{j+1}+{\frac {-a^{2}\tau }{h^{2}}}u_{ i+1}^{j+1}=u_{i}^{j}+\tau f_{i}^{j+1}.$

Erotusruudukon päätepisteiden kertoimien matriisin muoto määräytyy reunaehtojen mukaan ja se näytetään erikseen. Diagonaalisen dominanssin esiintyminen kertoimien matriisissa takaa pyyhkäisymenetelmän vakauden tätä SLAE:tä ratkaistaessa.

Sweep-menetelmän yleistäminen

A. A. Abramov ehdotti vuonna 1963 niin sanottua periodista pyyhkäisymenetelmää, joka mahdollistaa SLAE:n ratkaisemisen matriisilla, jossa kaikki kulmaelementit , , , ovat nollasta poikkeavia . SLAE:n ratkaisemiseksi eteenpäinpyyhkäisykertoimet lasketaan ensimmäisessä vaiheessa: $A_{11}$ $A_{1N}$ ${\displaystyle A_{N1))$ $A_{NN}$

$\alpha _{1}=c_{0}/b_{0},\;\beta _{1}=-\varphi _{0}/b_{0},\;\gamma _{1} =a_{0}/b_{0};$

$\alpha _{k+1}={\dfrac {c_{k}}{b_{k}-\alpha _{k}a_{k}}},\;\beta _{k+1} ={\dfrac {a_{k}\beta _{k}-f_{k}}{b_{k}-\alpha _{k}a_{k}}},\;\gamma _{k+1} ={\dfrac {a_{k}\gamma _{k}}{b_{k}-\alpha _{k}a_{k}}}.$

Seuraavaksi suoritetaan takaisinpyyhkäisy (oikealta vasemmalle) kertoimien saamiseksi

$\mu _{N}=-{\dfrac {c_{N}}{a_{N}(\alpha _{N}+\gamma _{N})-b_{N}}},\; \nu _{N}={\dfrac {f_{N}-a_{N}\beta _{N}}{a_{N}(\alpha _{N}+\gamma _{N})-b_{ N}}};$

$\mu _{n-1}=\alpha _{n}\mu _{n}+\gamma _{n}\mu _{N},\;\nu _{n-1}=\ beta _{n}+\alpha _{n}\nu _{n}+\gamma _{n}\nu _{N}.$

Seuraavaksi vektorin haluttu arvo lasketaan kaavoilla ${\vec {y}}$

$y_{0}={\dfrac {\nu _{0}}{1-\mu _{0}}};$

$y_{n-1}=\alpha _{n}(\mu _{n}y_{0}+\nu _{n})+\beta _{n}+\gamma _{n}( \mu _{N}y_{0}+\nu _{N}).$

Linkit

Esimerkki ratkaisusta
P. Ahuja. 1.1 Tridiagonaalinen matriisialgoritmi (TDMA) // Johdatus kemiantekniikan numeerisiin menetelmiin. — PHI Learning Pvt. Ltd., 2010. - ISBN 9788120340183 . (Englanti)
A. A. Abramov, V. B. Andreev. Pyyhkäisymenetelmän soveltamisesta differentiaali- ja differentiaaliyhtälöiden jaksollisten ratkaisujen löytämiseen // Zh. Vychisl. matematiikka. ja matto. fysiikka - 1963. - T. 3:2 . - S. 377-381 .
Thomasin algoritmi
Fedorenko R.P. Johdatus laskennalliseen fysiikkaan / Toim. A.I. Lobanov. - Dolgoprudny: Intellect Publishing House, 2008. - 504 s. - ISBN 978-5-91559-011-2 .
Berezin I.S. , Zhidkov N.P. Laskentamenetelmät. - M .: Fizmatlit, 1960. - T. 2. - 620 s.
Samarsky A.A. , Gulin A.V. Numeeriset menetelmät. - M .: Nauka, 1989. - 432 s. — ISBN 5-02-013996-3 .
Godunov S.K. , Ryabenky V.S. Johdatus erotuskaavioiden teoriaan. - M .: Fizmatgiz, 1962.

Muistiinpanot

↑ "Sweep-menetelmä... on muunnelma tuntemattomien peräkkäisen eliminoinnin menetelmästä" (Samarsky, Gulin, s. 45).
↑ "I. M. Gelfand ja O. V. Lokutsievskii esittelivät ja tutkivat pyyhkäisyn vakaana menetelmänä raja-arvoongelmien ratkaisemiseksi suurella määrällä parametreja" (Fedorenko, s. 500).
↑ Berezin, Zhidkov, s. 387, 506 (viittaen Gelfandin ja Lokutsievskin julkaisemattomaan käsikirjoitukseen).
↑ Liite Godunovin ja Ryabenkyn kirjaan.
↑ I. M. Gelfand ja O. V. Lokutsievskii löysivät pyyhkäisyn vuonna 1952 juuri koulun algebran oppikirjassa esitetyn algoritmin sovelluksena. Heidän ansionsa on vakauden luominen ja algoritmin käyttö monimutkaisten ongelmien ratkaisemisessa. Suunnilleen samaan aikaan, samanlaisen työn yhteydessä, muut kirjoittajat ehdottivat pyyhkäisyä” (Fedorenko, s. 501).
↑ Tikhonov A.N., Samarsky A.A. Matemaattisen fysiikan yhtälöt. - ch. III, § 1. - Mikä tahansa painos.

Menetelmät SLAE :n ratkaisemiseksi
Suorat menetelmät	Matriisimenetelmä Gaussin menetelmä Gauss-Jordan menetelmä Cramer menetelmä LU:n hajoaminen Cholesky-hajoaminen Lakaisumenetelmä
Iteratiiviset menetelmät	Jacobin menetelmä Gauss-Seidelin menetelmä Iterointimenetelmä Rentoutumismenetelmä Konjugaattigradienttimenetelmä Bikonjugaattigradienttimenetelmä Stabiloitu bikonjugaattigradienttimenetelmä
Kenraali	käänteinen matriisi Projektiomenetelmät SLAE:n ratkaisemiseen Esikäsittely