Jacobin menetelmä

Kokeneet kirjoittajat eivät ole vielä tarkistaneet sivun nykyistä versiota, ja se voi poiketa merkittävästi 22. huhtikuuta 2022 tarkistetusta versiosta . tarkastukset vaativat 2 muokkausta .

Jacobi - menetelmä on muunnelma yksinkertaisesta iteraatiomenetelmästä lineaaristen algebrallisten yhtälöiden ratkaisemiseksi . Nimetty Carl Gustav Jacobin mukaan .

Ongelman selvitys

Otetaan lineaarinen yhtälöjärjestelmä:

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

Tai $\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.$

Menetelmän kuvaus

Jacobin menetelmän iteratiivisen proseduurin rakentamiseksi on tarpeen suorittaa alustava yhtälöjärjestelmän muunnos iteratiiviseen muotoon . Se voidaan tehdä jollakin seuraavista säännöistä: $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 ;$

missä hyväksytyssä merkinnässä tarkoittaa matriisia, jonka päädiagonaali sisältää vastaavat matriisin elementit ja kaikki muut nollat; kun taas matriisit ja sisältävät ylemmän ja alemman kolmion muotoisen osan , jonka päädiagonaalissa nollia, on identiteettimatriisi . $D$ $A$ $U$ $L$ $A$ $E$

Sitten menettely ratkaisun löytämiseksi on:

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

Tai elementtikohtaisena kaavana:

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

missä on iteraatiolaskuri. $k$

Toisin kuin Gauss-Seidel-menetelmässä, emme voi korvata arvolla iteratiivisen prosessin aikana, koska näitä arvoja tarvitaan lopuissa laskelmissa. Tämä on merkittävin ero Jacobi-menetelmän ja Gauss-Seidel-menetelmän välillä SLAE :n ratkaisemiseksi . Siten jokaisessa iteraatiossa molemmat approksimaatiovektorit on tallennettava: vanha ja uusi. ${\displaystyle x_{i}^{(k)))$ $x_{i}^{{(k+1)}}$

Konvergenssiehto

Esitetään riittävä ehto menetelmän konvergenssille.

Lause .
Anna. Sitten mistä tahansa alkuperäisen likiarvon valinnasta:

\|B\|<1

\vec{x}^{(0)}

menetelmä konvergoi;
menetelmän konvergenssinopeus on yhtä suuri kuin geometrisen progression lähentymisnopeus nimittäjän kanssa ; $q=\|B\|$
oikea virhearvio: . $\|{\vec {x}}^{(k)}-{\vec {x}}\|<q^{k}\,\|{\vec {x}}^{(0) }-{\vec {x}}\|$

Pysäytysehto

Iteratiivisen prosessin päättymisen ehto, kun tarkkuus saavutetaan , on muotoa: $\varepsilon$

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

Riittävän hyvin käsitellylle matriisille (kohdalle ), se pätee for $B$ $\parallel B\parallel =q<1/2$

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

Tämä kriteeri ei vaadi matriisinormin laskemista ja sitä käytetään usein käytännössä. Tässä tapauksessa iteratiivisen prosessin päättymisen tarkalla ehdolla on muoto

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

ja vaatii ylimääräistä matriisi-vektori kertolaskua jokaisessa iteraatiossa, mikä noin kaksinkertaistaa algoritmin laskennallisen monimutkaisuuden.

Algoritmi

Alla on toteutusalgoritmi C++:ssa

#include <math.h> const double eps = 0,001 ; ///< haluttu tarkkuus .......................... /// N - matriisin ulottuvuus; A[N][N] - kertoimien matriisi, F[N] - vapaiden termien sarake, /// X[N] - alkuperäinen approksimaatio, vastaus kirjoitetaan myös X[N]; tyhjä Jacobi ( int N , double ** A , double * F , double * X ) { double * TempX = uusi tupla [ N ]; kaksinkertainen normi ; // normi, joka määritellään suurimmaksi eroksi viereisten iteraatioiden x-sarakekomponenttien välillä. do { for ( int i = 0 ; i < N ; i ++ ) { TempX [ i ] = F [ i ]; for ( int g = 0 ; g < N ; g ++ ) { jos ( 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 ); poista [] TempX ; }

Seuraavassa on toteutusalgoritmi Pythonissa

from collections.abc Import Sequence , MutableSequence def Jacobi ( A : Sequence [ Sequence [ float ]], b : Sequence [ float ], eps : float = 0.001 , x_init : MutableSequence [ float ] | None = Ei mitään ) -> list [ float ]: """ Jacobi-menetelmä kohteelle A*x = b(*) :param A: Matriisi (*) vasemmalla :param b: tunnettu vektori (*) oikealla :param x_init: alkuperäinen approksimaatio :return: likimääräinen x-arvo (*) """ def summa ( a : Sequence [ float ], x : Sequence [ float ], j : int ) -> float : S : float = 0 for i , ( m , y ) in enumerate ( zip ( a , x )): jos i != j : S += m * y palauttaa S def norm ( x : sekvenssi [ float ], y : sekvenssi [ float ]) -> float : paluu max (( abs ( x0 - y0 ) x0 , y0 zip -muodossa ( x , y ) )) jos x_init on Ei mitään : y = [ a / A [ i ] [ i ] i : lle , a luettelossa ( b )] else : y = x . kopioi () x : lista [ float ] = [ - ( summa ( a , y , i ) - b [ i ]) / A [ i ][ i ] for i , a in enumerate ( A )] kun taas normi ( y , x ) > eps : i : lle elem in enumerate ( x ): y [ i ] = elem i : lle , a luettelossa ( A ): x [ i ] = - ( summa ( a , y , i ) ) - b [ i ]) / A [ i ][ i ] palauttaa x

Katso myös

Gauss-Seidelin menetelmä

Menetelmät SLAE :n ratkaisemiseksi
Suorat menetelmät	Matriisimenetelmä Gaussin menetelmä Gauss-Jordan menetelmä Cramer menetelmä LU:n hajoaminen Cholesky-hajoaminen Lakaisumenetelmä
Iteratiiviset menetelmät	Jacobin menetelmä Gauss-Seidelin menetelmä Iterointimenetelmä Rentoutumismenetelmä Konjugaattigradienttimenetelmä Bikonjugaattigradienttimenetelmä Stabiloitu bikonjugaattigradienttimenetelmä
Kenraali	käänteinen matriisi Projektiomenetelmät SLAE:n ratkaisemiseen Esikäsittely