Jacobi 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 22. april 2022; checks kræver 2 redigeringer .

Jacobi-metoden er en variation af den simple iterationsmetode til løsning af et system af lineære algebraiske ligninger . Opkaldt efter Carl Gustav Jacobi .

Udtalelse af problemet

Lad os tage et system af lineære ligninger:

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

Beskrivelse af metoden

For at konstruere en iterativ procedure af Jacobi-metoden er det nødvendigt at udføre en foreløbig transformation af ligningssystemet til den iterative form . Det kan gøres i henhold til en af følgende 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 ;$

hvor, i den accepterede notation, betyder en matrix, hvis hoveddiagonal indeholder de tilsvarende elementer i matrixen og alle andre nuller; mens matricer og indeholder øvre og nedre trekantede dele , på hoveddiagonalen af hvilke nuller, er identitetsmatrixen . $D$ $EN$ $U$ $L$ $EN$ $E$

Så er proceduren for at finde en løsning:

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

Eller som en element-for-element-formel:

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

hvor er iterationstælleren. $k$

I modsætning til Gauss-Seidel-metoden kan vi ikke erstatte med under den iterative procedure, da disse værdier vil være nødvendige for resten af beregningerne. Dette er den mest signifikante forskel mellem Jacobi-metoden og Gauss-Seidel-metoden til at løse SLAE . Ved hver iteration skal begge tilnærmelsesvektorer således lagres: den gamle og den nye. ${\displaystyle x_{i}^{(k)))$ $x_{i}^{{(k+1)}}$

Konvergensbetingelse

Lad os præsentere en tilstrækkelig betingelse for metodens konvergens.

Sætning .
Lad. Så for ethvert valg af indledende tilnærmelse:

\|B\|<1

\vec{x}^{(0)}

metoden konvergerer;
metodens konvergenshastighed er lig med konvergenshastigheden for en geometrisk progression med nævneren ; $q=\|B\|$
korrekt fejlvurdering :. $\|{\vec {x}}^{(k)}-{\vec {x}}\|<q^{k}\,\|{\vec {x}}^{(0) }-{\vec {x}}\|$

Stop betingelse

Betingelsen for afslutningen af den iterative proces, når nøjagtigheden er opnået, har formen: $\varepsilon$

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

For en tilstrækkeligt velkonditioneret matrix (for ), holder det for $B$ $\parallel B\parallel =q<1/2$

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

Dette kriterium kræver ikke beregning af matrixnormen og bruges ofte i praksis. I dette tilfælde har den nøjagtige betingelse for afslutningen af den iterative proces formen

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

og kræver yderligere matrix-vektor multiplikation ved hver iteration, hvilket omtrent fordobler beregningskompleksiteten af algoritmen.

Algoritme

Nedenfor er implementeringsalgoritmen i C++

#include <math.h> const dobbelt eps = 0,001 ; ///< ønsket præcision ................................ /// N - matrixdimension; A[N][N] - matrix af koefficienter, F[N] - kolonne med frie led, /// X[N] - indledende tilnærmelse, svaret skrives også i X[N]; void Jacobi ( int N , double ** A , double * F , double * X ) { double * TempX = ny dobbelt [ N ]; dobbelt norm ; // norm, defineret som den største forskel mellem x-kolonne komponenterne i tilstødende iterationer. gør { for ( int i = 0 ; i < N ; i ++ ) { TempX [ i ] = F [ i ]; for ( int g = 0 ; g < N ; g ++ ) { hvis ( i != g ) TempX [ i ] -= A [ i ][ g ] * X [ g ]; } TempX [ i ] /= A [ i ][ i ]; } norm = fabs ( X [ 0 ] - TempX [ 0 ]); for ( 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 ); slet [] TempX ; }

Følgende er implementeringsalgoritmen i Python

fra collections.abc importer Sequence , MutableSequence def Jacobi ( A : Sequence [ Sequence [ float ]], b : Sequence [ float ], eps : float = 0,001 , x_init : MutableSequence [ float ] | Ingen = Ingen ) -> list [ float ]: """ Jacobi-metode for A*x = b(*) :param A: Matrix (*) til venstre :param b: kendt vektor (*) til højre :param x_init: indledende tilnærmelse :return: omtrentlig x værdi (*) """ def sum ( a : Sekvens [ float ], x : Sekvens [ float ], j : int ) -> float : S : float = 0 for i , ( m , y ) i enumerate ( zip ( a , x )): hvis i != j : S += m * y returnerer S def norm ( x : Sekvens [ float ], y : Sekvens [ float ]) -> float : return max (( abs ( x0 - y0 ) for x0 , y0 i zip ( x , y ))) hvis x_init er Ingen : y = [ a / A [ i ][ i ] for i , a i opregn ( b ) ] ellers : y = x . kopi () x : liste [ float ] = [ - ( sum ( a , y , i ) - b [ i ]) / A [ i ][ i ] for i , a i opregn ( A )] mens norm ( y , x ) > eps : for i , elem i enumerate ( x ): y [ i ] = elem for i , a i enumerate ( A ): x [ i ] = - ( sum ( a , y , i ) ) - b [ i ]) / A [ i ][ i ] returner x

Se også

Gauss-Seidel metode

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