Gauss-Seidel metode til løsning af et system af lineære ligninger
Gauss-Seidel-metoden (Seidel-metoden, Libman-processen, successiv substitutionsmetode) er en klassisk iterativ metode til løsning af et system af lineære ligninger .
Opkaldt efter Seidel og Gauss .
Udtalelse af problemet
Tag systemet:
, hvor![A\vec{x}=\vec{b}](https://wikimedia.org/api/rest_v1/media/math/render/svg/bec3e6a204d6c406e92e474ff08701af60a3c9fd)
Eller
Og vi vil vise, hvordan det kan løses ved hjælp af Gauss-Seidel-metoden.
Metode
For at tydeliggøre essensen af metoden omskriver vi problemet i formularen
Her, i den th ligning, har vi overført til højre side alle led, der indeholder , for . Denne post kan repræsenteres som
![j](https://wikimedia.org/api/rest_v1/media/math/render/svg/2f461e54f5c093e92a55547b9764291390f0b5d0)
![x_{i}](https://wikimedia.org/api/rest_v1/media/math/render/svg/e87000dd6142b81d041896a30fe58f0c3acb2158)
![i>j](https://wikimedia.org/api/rest_v1/media/math/render/svg/2886c2c870767297c5efcf319aa2bf68a31cb4b6)
hvor, i den accepterede notation, betyder en matrix, hvis hoveddiagonal indeholder de tilsvarende elementer i matrixen og alle andre nuller; mens matricerne og indeholder øvre og nedre trekantede dele , på hvis hoveddiagonal er nuller.
![\mathrm{D}](https://wikimedia.org/api/rest_v1/media/math/render/svg/3c894024162d89aa8502758b2151cb579806ea9a)
![EN](https://wikimedia.org/api/rest_v1/media/math/render/svg/7daff47fa58cdfd29dc333def748ff5fa4c923e3)
![\mathrm{U}](https://wikimedia.org/api/rest_v1/media/math/render/svg/b2ad0ddf5dc86cfc99e6ffdb37f3f0329f0982b0)
![\mathrm{L}](https://wikimedia.org/api/rest_v1/media/math/render/svg/e7693963f7eb3050c4c00a3417c955a5e3630cab)
![EN](https://wikimedia.org/api/rest_v1/media/math/render/svg/7daff47fa58cdfd29dc333def748ff5fa4c923e3)
Den iterative proces i Gauss-Seidel metoden er bygget efter formlen
efter at have valgt den passende indledende tilnærmelse .
![\vec{x}^{(0)}](https://wikimedia.org/api/rest_v1/media/math/render/svg/bba4c3386310019219b3b52120130b66633e601a)
Gauss-Seidel-metoden kan ses som en modifikation af Jacobi-metoden . Hovedideen med modifikationen er, at nye værdier bruges her, så snart de er modtaget, mens de i Jacobi-metoden ikke bruges før næste iteration:
![\vec{x}^{(i)}](https://wikimedia.org/api/rest_v1/media/math/render/svg/765f38cb24670dd968199b58affb922c1ef78254)
hvor
Således beregnes
den i -te komponent af den -te tilnærmelse af formlen![(k+1)](https://wikimedia.org/api/rest_v1/media/math/render/svg/3f9f13644a6be482d7ddb19a6e0c706564773085)
For eksempel, når :
![n=3](https://wikimedia.org/api/rest_v1/media/math/render/svg/1c5a5a42ced00df920fad4ab2d4acdb960a4105b)
![x_{1}^{{(k+1)}}=\sum _{{j=1}}^{{1-1}}c_{{1j}}x_{{j}}^{{(k +1)}}+\sum _{{j=1}}^{{3}}c_{{1j}}x_{{j}}^{{(k)}}+d_{1}](https://wikimedia.org/api/rest_v1/media/math/render/svg/3bcf1485ab0ee27838a2a372d5af5de69e534c02)
, det er
![x_{2}^{{(k+1)}}=\sum _{{j=1}}^{{2-1}}c_{{2j}}x_{{j}}^{{(k +1)}}+\sum _{{j=2}}^{{3}}c_{{2j}}x_{{j}}^{{(k)}}+d_{2}](https://wikimedia.org/api/rest_v1/media/math/render/svg/05c574da64857c2a8073eac0005bbcafae3d25bf)
, det er
![x_{3}^{{(k+1)}}=\sum _{{j=1}}^{{3-1}}c_{{3j}}x_{{j}}^{{(k +1)}}+\sum _{{j=3}}^{{3}}c_{{3j}}x_{{j}}^{{(k)}}+d_{3}](https://wikimedia.org/api/rest_v1/media/math/render/svg/0e8802609130f0e42d2bb2dd0a6b5de27f2202f1)
, det er
Konvergensbetingelse
Lad os præsentere en tilstrækkelig betingelse for metodens konvergens.
|
Sætning . Lad, hvorer matrixen invers til. Så for ethvert valg af indledende tilnærmelse:
![{\displaystyle \|\mathrm {A} _{2}\|<1}](https://wikimedia.org/api/rest_v1/media/math/render/svg/e792f87b8f83b22528ccc68a6d7c83f7ddd04b11) ![{\displaystyle \mathrm {A} _{2}=-(\mathrm {L} +\mathrm {D} )^{-1}\,\mathrm {U} ,\quad (\mathrm {L} +\ matematik {D} )^{-1}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/61def150299d8fbd0141ee01f61f58762a303e2f) ![{\displaystyle (\mathrm {L} +\mathrm {D} )}](https://wikimedia.org/api/rest_v1/media/math/render/svg/aa23e25ffdeeb384f6860bb05e4e0714344c7ddd) ![\vec{x}^{(0)}](https://wikimedia.org/api/rest_v1/media/math/render/svg/bba4c3386310019219b3b52120130b66633e601a) - Gauss-Seidel-metoden konvergerer;
- metodens konvergenshastighed er lig med konvergenshastigheden for en geometrisk progression med nævneren ;
![{\displaystyle q=\|\mathrm {A} _{2}\|}](https://wikimedia.org/api/rest_v1/media/math/render/svg/57ecfa2b1a7f1711e936b85d41fc913ffc272902)
- korrekt fejlvurdering :.
![{\displaystyle \|{\vec {x}}^{(k)}-{\vec {x}}\|=q^{k}\,\|{\vec {x}}^{(0) }-{\vec {x}}\|}](https://wikimedia.org/api/rest_v1/media/math/render/svg/aa64613b1f422a660563385258a9c2a1a5f7f0b2)
|
|
Opsigelsesbetingelse
Betingelsen for afslutning af Seidel iterative proces, når nøjagtighed er opnået i en forenklet form, har formen:
![\varepsilon](https://wikimedia.org/api/rest_v1/media/math/render/svg/a30c89172e5b88edbd45d3e2772c7f5e562e5173)
En mere præcis betingelse for afslutningen af den iterative proces har formen
og kræver mere beregning. God til sparsomme matricer .
Implementeringseksempel i C++
#include <iostream>
#include <cmath>
bruger navneområde std ;
// Sluttilstand
bool konvergere ( dobbelt xk [ 10 ], dobbelt xkp [ 10 ], int n , dobbelt eps )
{
dobbelt norm = 0 ;
for ( int i = 0 ; i < n ; i ++ )
norm += ( xk [ i ] - xkp [ i ]) * ( xk [ i ] - xkp [ i ]);
return ( sqrt ( norm ) < eps ;
}
dobbelt okr ( dobbelt x , dobbelt eps )
{
int i = 0 ;
dobbelt neweps = eps ;
mens ( neweps < 1 )
{
i ++ ;
neweps *= 10 ;
}
int okr = pow ( dobbelt ( 10 ), i );
x = int ( x * okr + 0,5 ) / dobbelt ( okr );
returnere x ;
}
bool diagonal ( dobbelt a [ 10 ][ 10 ], int n )
{
int i , j , k = 1 ;
dobbelt sum ;
for ( i = 0 ; i < n ; i ++ ) {
sum = 0 ;
for ( j = 0 ; j < n ; j ++ ) sum += abs ( a [ i ][ j ]);
sum -= abs ( a [ i ][ i ]);
if ( sum > a [ i ][ i ])
{
k = 0 _
cout << a [ i ][ i ] << " < " << sum << endl ;
}
andet
{
cout << a [ i ][ i ] << " > " << sum << endl ;
}
}
return ( k == 1 );
}
int main ()
{
setlocale ( LC_ALL , "" );
dobbelt eps , a [ 10 ][ 10 ], b [ 10 ], x [ 10 ], p [ 10 ];
int n , i , j , m = 0 ;
int metode _
cout << "Indtast størrelsen af den kvadratiske matrix: " ;
cin >> n ;
cout << "Indtast beregningspræcisionen: " ;
cin >> eps ;
cout << "Fyld matrix A: " << endl << endl ;
for ( i = 0 ; i < n ; i ++ )
for ( j = 0 ; j < n ; j ++ )
{
cout << "A[" << i << "][" << j << "] = " ;
cin >> a [ i ][ j ];
}
cout << endl << endl ;
cout << "Din matrix A er: " << endl << endl ;
for ( i = 0 ; i < n ; i ++ )
{
for ( j = 0 ; j < n ; j ++ )
cout << a [ i ][ j ] << " " ;
cout << endl ;
}
cout << endl ;
cout << "Udfyld kolonnen for gratis medlemmer: " << endl << endl ;
for ( i = 0 ; i < n ; i ++ )
{
cout << "B[" << i + 1 << "] = " ;
cin >> b [ i ];
}
cout << endl << endl ;
/*
Metodefremskridt, hvor:
a[n][n] - Matrix af koefficienter
x[n], p[n] - Nuværende og tidligere løsninger
b[n] - Kolonne af højre dele
Alle ovenstående arrays er ægte og
skal defineres i hovedprogrammet,
også i arrayet x[n] skal du sætte initialen
løsningskolonnetilnærmelse (f.eks. alle nuller)
*/
for ( int i = 0 ; i < n ; i ++ )
x [ i ] = 1 ;
cout << "Diagonal dominans: " << endl ;
if ( diagonal ( a , n )) {
gør
{
for ( int i = 0 ; i < n ; i ++ )
p [ i ] = x [ i ];
for ( int i = 0 ; i < n ; i ++ )
{
dobbelt var = 0 ;
for ( int j = 0 ; j < n ; j ++ )
if ( j != i ) var += ( a [ i ][ j ] * x [ j ]);
x [ i ] = ( b [ i ] -var ) / a [ i ][ i ] ;
}
m ++ ;
} mens ( ! konvergerer ( x , p , n , eps ));
cout << "Systembeslutning:" << endl << endl ;
for ( i = 0 ; i < n ; i ++ ) cout << "x" << i << " = " << okr ( x [ i ], eps ) << "" << endl ;
cout << "Iterations: " << m << endl ;
}
andet {
cout << "Ingen diagonal dominans" << endl ;
}
system ( "pause" );
returnere 0 ;
}
Implementeringseksempel i Python
import numpy som np
def seidel ( A , b , eps ):
n = len ( A )
x = np . nuller ( n ) # nul vektor
converge = Falsk
, mens den ikke konvergerer :
x_new = np . kopi ( x )
for i i område ( n ):
s1 = sum ( A [ i ][ j ] * x_ny [ j ] for j i område ( i ))
s2 = sum ( A [ i ][ j ] * x [ j ] for j i området ( i + 1 , n ))
x_new [ i ] = ( b [ i ] - s1 - s2 ) / A [ i ][ i ]
konvergere = np . sqrt ( sum (( x_new [ i ] - x [ i ]) ** 2 for i i området ( n ))) <= eps
x = x_new
returnere x
Se også
Noter
Links
Metoder til løsning af SLAE |
---|
Direkte metoder |
|
---|
Iterative metoder |
|
---|
Generel |
|
---|