Metoda iterației

Metoda iterației sau metoda iterației simple este o metodă numerică de rezolvare a unui sistem de ecuații algebrice liniare . Esența metodei este de a găsi valoarea aproximativă a următoarei aproximări, care este mai precisă.

Metoda face posibilă obținerea valorilor rădăcinilor sistemului cu o precizie dată sub forma unei limite a unei secvențe a unor vectori (ca urmare a unui proces iterativ). Natura convergenței și însuși faptul convergenței metodei depind de alegerea aproximării inițiale a rădăcinii.

Descrierea metodei

Fie dat un SLAE de forma: , unde $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}}

Se presupune că . Exprimăm prin prima ecuație, prin a doua etc. [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.

Lăsa

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

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

pentru si lasa $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}}

Apoi sistemul original este transformat în forma . $x=\beta +\alpha x$

Pentru aproximarea zero, luăm coloana membrilor liberi:

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

Apoi

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

- prima abordare,

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

- a doua aproximare etc.

Formula generală pentru procesul iterativ are forma

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

Soluția sistemului original este considerată . $x^{*}=\lim _{k\to \infty }x^{(k))$

Condiții de convergență a procesului

Condiție necesară și suficientă pentru convergență: , unde este raza spectrală [2] . $\rho (\alpha)<1$ $\rho (\alpha)$ $\alfa$

Condiție suficientă pentru convergență: [2] . $\Vert \alpha \Vert <1$

În special, atunci când se alege o normă subordonată vectorului, condiția de convergență ia forma (unde ). $\|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$

Atunci când se alege o normă , condiția ia forma (unde ), care se numește condiția de dominanță diagonală a matricei originale . $\|x\|_{1}=\sum _{i=1}^{n}|x_{i}|$ $\sum _{i=1 \atop i\neq j}^{n}\vert \alpha _{ij}\vert <1$ $j=1,2,\dots ,n$ $A$

Estimarea erorii

Fie vectorul soluție exactă. Apoi putem obține următoarele estimări de eroare pentru soluția aproximativă la pasul al-lea al algoritmului [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.

Note

↑ Berezin, Jidkov, 1959 , p. 57.
↑ 1 2 Lebedeva, Pakulina, 2021 , p. 132.
↑ Lebedeva, Pakulina, 2021 , p. 133.

Literatură

Berezin, I. S. , Zhidkov N. P. Metode de calcul. -M .:Fizmatlit, 1959. - T. II. (Rusă)
Lebedeva, A. V. , Pakulina, A. N. Practicum privind metodele de calcul. Partea 1 . - Sankt Petersburg. : Universitatea de Stat din Sankt Petersburg, 2021. - 156 p. (Rusă)

Metode de rezolvare a SLAE
Metode directe	Metoda matricei metoda Gauss Metoda Gauss-Iordan Metoda Cramer descompunerea LU Descompunerea Cholesky Metoda de măturare
Metode iterative	metoda Jacobi Metoda Gauss-Seidel Metoda iterației Metoda de relaxare Metoda gradientului conjugat Metoda gradientului biconjugat Metoda gradientului biconjugat stabilizat
General	matrice inversă Metode de proiecție pentru rezolvarea SLAE Precondiționare