Feje metode

Den aktuelle version af siden er endnu ikke blevet gennemgået af erfarne bidragydere og kan afvige væsentligt fra den version , der blev gennemgået den 23. november 2021; verifikation kræver 1 redigering .

Sweep-metoden ( eng. tridiagonal matrix-algoritme ) eller Thomas - algoritmen ( eng. Thomas-algoritme ) bruges til at løse systemer af lineære ligninger af formen , hvor er en tridiagonal matrix . Det er en variant af metoden til sekventiel eliminering af ukendte [1] . Sweep-metoden blev foreslået af I. M. Gelfand og O. V. Lokutsievskii (i 1952 [2] ; udgivet i 1960 [3] og 1962 [4] ), såvel som uafhængigt af andre forfattere [5] . $Ax=F$ $EN$

Beskrivelse af metoden

Ligningssystemet svarer til relationen $Ax=F$

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

Sweep-metoden er baseret på antagelsen om, at de nødvendige ubekendte er relateret af den rekursive relation:

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

hvor

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

Ved at bruge denne relation udtrykker vi og gennem og erstatter i ligning (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

hvor F i er højre side af den i -te ligning. Dette forhold vil holde uanset løsningen, hvis du har brug for det

{\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 {cases}}

Dette indebærer:

{\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} }

Fra den første ligning får vi:

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

Efter at have fundet sweep-koefficienterne og ved hjælp af ligning (2) får vi systemets løsning. hvori, $\alfa$ $\beta$

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}}}

En anden måde at forklare essensen af sweep-metoden, tættere på terminologien for finite difference-metoder og forklare oprindelsen af dens navn, er følgende: vi transformerer ligning (1) til dens ækvivalente ligning

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

med en overdiagonal (overdiagonal) matrix

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

Beregningerne udføres i to trin. I det første trin beregnes komponenterne i matrixen og vektoren , startende fra til $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}.

På anden fase beregnes for løsningen: $i=n, n-1, \prikker, 1$

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

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

Dette beregningsskema forklarer også det engelske udtryk for denne metode[ afklar ] "shuttle" .

For at formlerne for sweep-metoden kan anvendes, er den diagonale dominansegenskab for matrix A tilstrækkelig .

Eksempel på brug

Tridiagonale matricer, som den simple sweep-metode bruges til, opstår ofte, når man løser differentialligninger for to uafhængige variable ved den endelige differensmetode . Overvej for eksempel løsningen af en lineær endimensionel varmeligning :

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

hvor er en positiv konstant (tallet er den termiske diffusivitet ) og er en funktion af varmekilder [6] . Den ønskede funktion indstiller temperaturen på punktet med koordinaten på tidspunktet . $-en$ $a^2$ $f(x,t)$ $u=u(x,t)$ $x$ $t$

Lad os diskretisere denne ligning på et ensartet gitter med et rumligt trin og et tidstrin . I dette tilfælde erstattes de kontinuerlige funktioner og af deres diskrete modstykker og , og de rumlige og tidsmæssige afledte erstattes af endelige forskelle: $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}}\til {\frac {u(x_{ i+1},t)-2u(x_{i},t)+u(x_{i-1},t)}{h^{2}}}.$

Værdierne af mængder på laget vil blive betragtet som kendte (opnået som et resultat af diskretisering af de indledende betingelser eller løsningen af ligningen i det foregående tidstrin). Lad os yderligere overveje en tilnærmelse implicit i tid, hvor værdierne af varmekilder og varmestrømme er taget fra det næste tidslag . Det tilsvarende system af lineære algebraiske ligninger for ukendte værdier har formen ${\displaystyle 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}.$

Ved at overføre de kendte mængder til højre side, gange med og gruppere koefficienterne, bringer vi SLAE til den endelige form $\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}.$

Formen af matrixen af koefficienter for endepunkterne af differensgitteret bestemmes af grænsebetingelserne og vises separat. Tilstedeværelsen af diagonal dominans i matrixen af koefficienter garanterer stabiliteten af sweep-metoden, når denne SLAE løses.

Generalisering af sweep-metoden

A. A. Abramov i 1963 foreslog den såkaldte periodiske sweep-metode, som gør det muligt at løse SLAE med en matrix, hvor alle hjørneelementer , , , ikke er nul . For at løse SLAE beregnes de fremadgående sweep-koefficienter ved det første trin: $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}}}.$

Dernæst udføres et tilbagesweep (fra højre mod venstre) for at opnå koefficienterne

$\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}.$

Dernæst beregnes den ønskede værdi af vektoren ved hjælp af formlerne ${\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}).$

Noter

↑ "Sweep-metoden ... er en variant af metoden til sekventiel eliminering af ukendte" (Samarsky, Gulin, s. 45).
↑ "Sweep, som en stabil metode til at løse grænseværdiproblemer med et stort antal parametre, blev introduceret og undersøgt af I. M. Gelfand og O. V. Lokutsievskii i 1952" (Fedorenko, s. 500).
↑ Berezin, Zhidkov, s. 387, 506 (med henvisning til et upubliceret manuskript af Gelfand og Lokutsievskii).
↑ Tillæg til bogen om Godunov og Ryabenky.
↑ "Sweep blev" opdaget af I. M. Gelfand og O. V. Lokutsievskii i 1952 netop som en anvendelse af algoritmen beskrevet i algebraskolens lærebog. Deres fordel er etableringen af stabilitet og brugen af algoritmen til at løse komplekse problemer. Omtrent samtidig, i forbindelse med lignende arbejde, blev sweep foreslået af andre forfattere” (Fedorenko, s. 501).
↑ Tikhonov A.N., Samarsky A.A. Matematisk fysiks ligninger. - ch. III, § 1. - Enhver udgave.

Metoder til løsning af SLAE
Direkte metoder	Matrix metode Gauss metode Gauss-Jordan metode Cramer metode LU nedbrydning Kolesky nedbrydning Feje metode
Iterative metoder	Jacobi metode Gauss-Seidel metode Iterationsmetode Afslapningsmetode Konjugeret gradientmetode Bikonjugeret gradientmetode Stabiliseret bikonjugat gradientmetode
Generel	omvendt matrix Projektionsmetoder til løsning af SLAE Forkonditionering

Feje metode

Beskrivelse af metoden

Eksempel på brug

Generalisering af sweep-metoden

Links

Noter