Jacobi metod

Den aktuella versionen av sidan har ännu inte granskats av erfarna bidragsgivare och kan skilja sig väsentligt från versionen som granskades den 22 april 2022; kontroller kräver 2 redigeringar .

Jacobi - metoden är en variant av den enkla iterationsmetoden för att lösa ett system av linjära algebraiska ekvationer . Uppkallad efter Carl Gustav Jacobi .

Förklaring av problemet

Låt oss ta ett system med linjära ekvationer:

$A\vec{x}=\vec{b}$ , var $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)$

Eller $\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{array}}\right.$

Beskrivning av metoden

För att konstruera en iterativ procedur av Jacobi-metoden är det nödvändigt att utföra en preliminär transformation av ekvationssystemet till den iterativa formen . Det kan göras enligt en av följande regler: $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 ;$

där, i den accepterade notationen, betyder en matris vars huvuddiagonal innehåller motsvarande element i matrisen och alla andra nollor; medan matriser och innehåller övre och nedre triangulära delar , på huvuddiagonalen av vilka nollor, är identitetsmatrisen . $D$ $A$ $U$ $L$ $A$ $E$

Då är proceduren för att hitta en lösning:

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

Eller som en element-för-element-formel:

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

var är iterationsräknaren. $k$

Till skillnad från Gauss-Seidel-metoden kan vi inte ersätta med under den iterativa proceduren, eftersom dessa värden kommer att behövas för resten av beräkningarna. Detta är den mest signifikanta skillnaden mellan Jacobi-metoden och Gauss-Seidel-metoden för att lösa SLAE . Sålunda, vid varje iteration, måste båda approximationsvektorerna lagras: den gamla och den nya. ${\displaystyle x_{i}^{(k)))$ $x_{i}^{{(k+1)}}$

Konvergensvillkor

Låt oss presentera ett tillräckligt villkor för metodens konvergens.

Teorem .
Låt. Sedan för valet av initial uppskattning:

\|B\|<1

\vec{x}^{(0)}

metoden konvergerar;
metodens konvergenshastighet är lika med konvergenshastigheten för en geometrisk progression med nämnaren ; $q=\|B\|$
korrekt feluppskattning: . $\|{\vec {x}}^{(k)}-{\vec {x}}\|<q^{k}\,\|{\vec {x}}^{(0) }-{\vec {x}}\|$

Stoppvillkor

Villkoret för slutet av den iterativa processen när noggrannhet uppnås har formen: $\varepsilon$

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

För en tillräckligt välkonditionerad matris (för ) håller det för $B$ $\parallel B\parallel =q<1/2$

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

Detta kriterium kräver inte beräkning av matrisnormen och används ofta i praktiken. I det här fallet har det exakta villkoret för att avsluta den iterativa processen formen

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

och kräver ytterligare matris-vektormultiplikation vid varje iteration, vilket ungefär fördubblar beräkningskomplexiteten hos algoritmen.

Algoritm

Nedan är implementeringsalgoritmen i C++

#inkludera <math.h> const dubbel eps = 0,001 ; ///< önskad precision ........................ /// N - matrisdimension; A[N][N] - matris av koefficienter, F[N] - kolumn med fria termer, /// X[N] - initial approximation, svaret skrivs också i X[N]; void Jacobi ( int N , dubbel ** A , dubbel * F , dubbel * X ) { dubbel * TempX = ny dubbel [ N ]; dubbel norm ; // norm, definierad som den största skillnaden mellan x-kolumnskomponenterna i angränsande iterationer. gör { for ( int i = 0 ; i < N ; i ++ ) { TempX [ i ] = F [ i ]; för ( int g = 0 ; g < N ; g ++ ) { om ( i != g ) TempX [ i ] -= A [ i ][ g ] * X [ g ]; } TempX [ i ] /= A [ i ][ i ]; } norm = fabs ( X [ 0 ] - TempX [ 0 ]); för ( int h = 0 ; h < N ; h ++ ) { if ( fabs ( X [ h ] - TempX [ h ] ) > norm ) norm = fabs ( X [ h ] - TempX [ h ]); X [ h ] = TempX [ h ]; } } while ( norm > eps ); ta bort [] TempX ; }

Följande är implementeringsalgoritmen i Python

från collections.abc import Sequence , MutableSequence def Jacobi ( A : Sequence [ Sequence [ float ]], b : Sequence [ float ], eps : float = 0,001 , x_init : MutableSequence [ float ] | Ingen = Ingen ) -> list [ float ]: """ Jacobi-metod för A*x = b(*) :param A: Matrix (*) till vänster :param b: känd vektor (*) till höger :param x_init: initial approximation :return: ungefärligt x värde (*) """ def summa ( a : Sekvens [ float ], x : Sekvens [ float ], j : int ) -> float : S : float = 0 för i , ( m , y ) i räkna upp ( zip ( a , x )): om i != j : S += m * y returnerar S def norm ( x : Sekvens [ float ], y : Sekvens [ float ]) -> float : return max (( abs ( x0 - y0 ) för x0 , y0 i zip ( x , y ))) om x_init är Inget : y = [ a / A [ i ][ i ] för i , a i uppräkning ( b ) ] annars : y = x . kopiera () x : lista [ float ] = [ - ( summa ( a , y , i ) - b [ i ]) / A [ i ][ i ] för i , a i uppräkning ( A )] medan norm ( y , x ) > eps : för i , elem i räkna upp ( x ): y [ i ] = elem för i , a i räkna upp ( A ): x [ i ] = - ( summa ( a , y , i ) ) - b [ i ]) / A [ i ][ i ] returnerar x

Se även

Gauss-Seidel-metoden

Metoder för att lösa SLAE
Direkta metoder	Matrismetod Gauss metod Gauss-Jordan-metoden Cramer metod LU-nedbrytning Cholesky nedbrytning Sopa metod
Iterativa metoder	Jacobi metod Gauss-Seidel-metoden Iterationsmetod Avslappningsmetod Konjugerad gradientmetod Bikonjugerad gradientmetod Stabiliserad bikonjugatgradientmetod
Allmän	invers matris Projektionsmetoder för att lösa SLAE Förkonditionering