Iterationsmetode

Iterationsmetoden eller den simple iterationsmetode er en numerisk metode til at løse et system af lineære algebraiske ligninger . Essensen af metoden er at finde den omtrentlige værdi af den næste tilnærmelse, som er mere nøjagtig.

Metoden gør det muligt at opnå værdierne af systemets rødder med en given nøjagtighed i form af en grænse for en sekvens af nogle vektorer (som et resultat af en iterativ proces). Arten af konvergensen og selve kendsgerningen af metodens konvergens afhænger af valget af den indledende tilnærmelse af roden.

Beskrivelse af metoden

Lad en SLAE af formen gives: , hvor $Ax=B$

A={\begin{bmatrix}a_{11}&\cdots &a_{1n}\\\vdots &\ddots &\vdots \\a_{n1}&\cdots &a_{nn}\end{bmatrix} },\ x={\begin{bmatrix}x_{1}\\\vdots \\x_{n}\end{bmatrix)),\ B={\begin{bmatrix}b_{1}\\\vdots \ \b_{n}\end{bmatrix}}

Det antages at . Vi udtrykker gennem den første ligning, gennem den anden osv. [1] : $a_{ii}\neq 0,\ i={\overline {1,n))$ $x_{1}$ $x_{2}$

\left\{{\begin{array}{c}x_{1}={\dfrac {b_{1}}{a_{11}}}-{\dfrac {a_{12}}{a_{ 11}}}x_{2}-\cdots -{\dfrac {a_{1n}}{a_{11}}}x_{n}\\\vdots \\x_{n}={\dfrac {b_{n }}{a_{nn}}}-{\dfrac {a_{n1}}{a_{nn}}}x_{1}-{\dfrac {a_{n2}}{a_{nn}}}x_{2 }-\cdots -{\dfrac {a_{n,n-1}}{a_{nn}}}x_{n-1}\end{array}}\right.

Lade

\alpha _{ij}=\left\lbrace {\begin{array}{cc}-{\dfrac {a_{ij}}{a_{ii}}},&i\neq j,\\0, &i=j,\end{array}}\right.

\beta _{i}={\frac {b_{i}}{a_{ii}}},

for og lad $i,j={\overline {1,n))$

\alpha ={\begin{bmatrix}\alpha _{11}&\cdots &\alpha _{1n}\\\vdots &\ddots &\vdots \\\alpha _{n1}&\cdots & \alpha _{nn}\end{bmatrix}},\ \beta ={\begin{bmatrix}\beta _{1}\\\vdots \\\beta _{n}\end{bmatrix}}

Derefter transformeres det oprindelige system til formen . $x=\beta +\alpha x$

For nul-tilnærmelsen tager vi kolonnen med gratis medlemmer:

{\begin{bmatrix}x_{1}^{(0)}\\\vdots \\x_{n}^{(0)}\end{bmatrix}}={\begin{bmatrix}\beta _{1}\\\vdots \\\beta _{n}\end{bmatrix}}

Derefter

{\begin{bmatrix}x_{1}^{(1)}\\\vdots \\x_{n}^{(1)}\end{bmatrix))={\begin{bmatrix}\beta _{1}\\\vdots \\\beta _{n}\end{bmatrix}}+{\begin{bmatrix}\alpha _{11}&\cdots &\alpha _{1n}\\\vdots & \ddots &\vdots \\\alpha _{n1}&\cdots &\alpha _{nn}\end{bmatrix}}{\begin{bmatrix}x_{1}^{(0)}\\\vdots \ \x_{n}^{(0)}\end{bmatrix}}

- første tilgang,

{\begin{bmatrix}x_{1}^{(2)}\\\vdots \\x_{n}^{(2)}\end{bmatrix))={\begin{bmatrix}\beta _{1}\\\vdots \\\beta _{n}\end{bmatrix}}+{\begin{bmatrix}\alpha _{11}&\cdots &\alpha _{1n}\\\vdots & \ddots &\vdots \\\alpha _{n1}&\cdots &\alpha _{nn}\end{bmatrix}}{\begin{bmatrix}x_{1}^{(1)}\\\vdots \ \x_{n}^{(1)}\end{bmatrix}}

- anden tilnærmelse osv.

Den generelle formel for den iterative proces har formen

x^{(k)}=\beta +\alpha x^{(k-1)},\ k=1,2,\dots

Løsningen af det oprindelige system anses for at være . ${\displaystyle x^{*}=\lim _{k\to \infty }x^{(k)))$

Proceskonvergensbetingelser

Nødvendig og tilstrækkelig betingelse for konvergens: , hvor er den spektrale radius [2] . $\rho (\alpha )<1$ $\rho (\alpha )$ $\alfa$

Tilstrækkelig betingelse for konvergens: [2] . $\Vert \alpha \Vert <1$

Især når man vælger en norm, der er underordnet vektoren, antager konvergensbetingelsen formen (hvor ). $\|x\|_{\infty }=\max \limits _{1\leq i\leq n}|x_{i}|$ $\max _{j=1}^{n}\vert \alpha _{ij}\vert <1$ $i=1,2,\dots ,n$

Når man vælger en norm , antager betingelsen formen (hvor ), som kaldes betingelsen for diagonal dominans af den oprindelige matrix . $\|x\|_{1}=\sum _{i=1}^{n}|x_{i}|$ $\sum _{i=1 \atop i\neq j}^{n}\vert \alpha _{ij}\vert <1$ $j=1,2,\prikker ,n$ $EN$

Fejlvurdering

Lad være den nøjagtige løsning vektor. Derefter kan vi opnå følgende fejlestimater for den omtrentlige løsning i algoritmens trin [3] : $x$ $x^{{(k)}}$ $k$

a priori:

\Vert xx^{(k)}\Vert \leq ||\alpha ||^{k}||x^{(0)}||+{\frac {\Vert \alpha \Vert ^{ k}}{1-\Vert \alpha \Vert }}\Vert \beta \Vert .

a posteriori:

\Vert xx^{(k)}\Vert \leq {\frac {\Vert \alpha \Vert }{1-\Vert \alpha \Vert }}\Vert x^{(k)}-x^ {(k-1)}\Vert .

Noter

↑ Berezin, Zhidkov, 1959 , s. 57.
↑ 1 2 Lebedeva, Pakulina, 2021 , s. 132.
↑ Lebedeva, Pakulina, 2021 , s. 133.

Litteratur

Berezin, I. S. , Zhidkov N. P. Beregningsmetoder. -M .:Fizmatlit, 1959. - T. II. (Russisk)
Lebedeva, A. V. , Pakulina, A. N. Practicum on computational methods. Del 1 . - Sankt Petersborg. : St. Petersburg State University, 2021. - 156 s. (Russisk)

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