Metoda Jacobi

Versiunea actuală a paginii nu a fost încă examinată de colaboratori experimentați și poate diferi semnificativ de versiunea revizuită pe 22 aprilie 2022; verificările necesită 2 modificări .

Metoda Jacobi este o variație a metodei iterației simple pentru rezolvarea unui sistem de ecuații algebrice liniare . Numit după Carl Gustav Jacobi .

Enunțul problemei

Să luăm un sistem de ecuații liniare:

$A\vec{x}=\vec{b}$ , Unde $A=\left( \begin{array}{ccc} a_{11} & \ldots & a_{1n} \\ \vdots & \ddots & \vdots \\ a_{n1} & \ldots & a_{nn} \ end{array} \right),\quad \vec{b}=\left( \begin{array}{c} b_1 \\ \vdots \\ b_n \end{array} \right)$

Sau $\left\{{\begin{array}{rcl}a_{{11}}x_{1}+\ldots +a_{{1n}}x_{n}&=&b_{{1}}\\\ldots ~ ~~~~~~~~~~~~~~~~~~\\a_{{n1}}x_{1}+\ldots +a_{{nn}}x_{n}&=&b_{ { n}}\end{matrice}}\dreapta.$

Descrierea metodei

Pentru a construi o procedură iterativă a metodei Jacobi, este necesar să se efectueze o transformare preliminară a sistemului de ecuații în forma iterativă . Se poate face conform uneia dintre următoarele reguli: $A\vec{x}=\vec{b}$ ${\vec {x}}=B{\vec {x}}+{\vec {g}}$

$B=ED^{{-1}}A=D^{{-1}}(DA),\quad {\vec {g}}=D^{{-1}}{\vec {b}}) ;$

$B=-D^{{-1}}(L+U)=-D^{{-1}}(AD),\quad {\vec {g}}=D^{{-1}}{\ vec{b}}$

$D_{{ii}}^{{-1}}=1/D_{{ii}},D_{{ii}}\neq 0,\,i=1,2,...,n\quad ;$

unde, în notația acceptată, înseamnă o matrice a cărei diagonală principală conține elementele corespunzătoare ale matricei și toate celelalte zerouri; în timp ce matricele și conțin părți triunghiulare superioare și inferioare , pe diagonala principală a cărora este zero, matricea de identitate . $D$ $A$ $U$ $L$ $A$ $E$

Atunci procedura pentru găsirea unei soluții este:

{\vec {x}}^{{(k+1)}}=B{\vec {x}}^{{(k)))+{\vec {g}},

Sau ca o formulă element cu element:

x_{i}^{{(k+1)}}={\frac {1}{a_{{ii}}}}\left(b_{i}-\sum _{{j\neq i}}a_ {{ij}}x_{j}^{{(k)}}\dreapta),\quad i=1,2,\ldots ,n.

unde este contorul de iterații. $k$

Spre deosebire de metoda Gauss-Seidel, nu putem înlocui cu în timpul procedurii iterative, deoarece aceste valori vor fi necesare pentru restul calculelor. Aceasta este cea mai semnificativă diferență dintre metoda Jacobi și metoda Gauss-Seidel pentru rezolvarea SLAE . Astfel, la fiecare iterație, vor trebui stocați ambii vectori de aproximare: cel vechi și cel nou. $x_{i}^{(k))$ $x_{i}^{{(k+1)}}$

Condiție de convergență

Să prezentăm o condiție suficientă pentru convergența metodei.

Teorema .
Lasă. Apoi, pentru orice alegere de aproximare inițială:

\|B\|<1

\vec{x}^{(0)}

metoda converge;
rata de convergenţă a metodei este egală cu rata de convergenţă a unei progresii geometrice cu numitorul ; $q=\|B\|$
estimarea corectă a erorii: . $\|{\vec {x}}^{(k)}-{\vec {x}}\|<q^{k}\,\|{\vec {x}}^{(0) }-{\vec {x}}\|$

Stare de oprire

Condiția pentru încheierea procesului iterativ atunci când este atinsă acuratețea are forma: $\varepsilon$

\parallel x^{(k+1)}-x^{(k)}\parallel \leq {\frac {1-q}{q}}\varepsilon .

Pentru o matrice suficient de bine condiționată (pentru ), este valabil pentru $B$ $\parallel B\parallel =q<1/2$

\parallel x^{(k+1)}-x^{(k)}\parallel \leq \varepsilon .

Acest criteriu nu necesită calculul normei matriceale și este adesea folosit în practică. În acest caz, condiția exactă pentru încheierea procesului iterativ are forma

\parallel Ax^{(k)}-b\parallel \le \varepsilon

și necesită o multiplicare suplimentară a vectorului matrice la fiecare iterație, ceea ce dublează aproximativ complexitatea de calcul a algoritmului.

Algoritm

Mai jos este algoritmul de implementare în C++

#include <math.h> const dublu eps = 0,001 ; ///< precizia dorită ......................... /// N - dimensiunea matricei; A[N][N] - matrice de coeficienți, F[N] - coloană de termeni liberi, /// X[N] - aproximare inițială, răspunsul se scrie tot în X[N]; void Jacobi ( int N , dublu ** A , dublu * F , dublu * X ) { dublu * TempX = dublu nou [ N ]; dubla norma ; // normă, definită ca cea mai mare diferență între componentele coloanei x ale iterațiilor învecinate. face { pentru ( int i = 0 ; i < N ; i ++ ) { TempX [ i ] = F [ i ]; pentru ( int g = 0 ; g < N ; g ++ ) { dacă ( i != g ) TempX [ i ] -= A [ i ][ g ] * X [ g ]; } TempX [ i ] /= A [ i ][ i ]; } norm = fabs ( X [ 0 ] - TempX [ 0 ]); pentru ( int h = 0 ; h < N ; h ++ ) { dacă ( fabs ( X [ h ] - TempX [ h ]) > normă ) norm = fabs ( X [ h ] - TempX [ h ]); X [ h ] = TempX [ h ]; } } în timp ce ( norm > eps ); șterge [] TempX ; }

Mai jos este algoritmul de implementare în Python

din collections.abc import Sequence , MutableSequence def Jacobi ( A : Sequence [ Sequence [ float ]], b : Sequence [ float ], eps : float = 0.001 , x_init : MutableSequence [ float ] | None = None ) -> list [ float ]: """ Metoda Jacobi pentru A*x = b(*) :param A: Matrice (*) în stânga :param b: vector cunoscut (*) în dreapta :param x_init: aproximare inițială :return: valoarea aproximativă x (*) """ def sum ( a : Sequence [ float ], x : Sequence [ float ], j : int ) -> float : S : float = 0 pentru i , ( m , y ) în enumerate ( zip ( a , x )): dacă i != j : S += m * y returnează S def norm ( x : Sequence [ float ], y : Sequence [ float ]) -> float : return max (( abs ( x0 - y0 ) pentru x0 , y0 in zip ( x , y ))) dacă x_init este None : y = [ a / A [ i ][ i ] for i , a in enumerate ( b )] else : y = x . copie () x : listă [ float ] = [ - ( suma ( a , y , i ) - b [ i ]) / A [ i ][ i ] pentru i , a în enumerare ( A )] în timp ce norm ( y , x ) > eps : for i , elem în enumerate ( x ): y [ i ] = elem for i , a in enumerate ( A ): x [ i ] = - ( sum ( a , y , i ) ) - b [ i ]) / A [ i ][ i ] returnează x

Vezi și

Metoda Gauss-Seidel

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 de iterație 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