Gauss-Seidelova metoda řešení soustavy lineárních rovnic
Gauss-Seidelova metoda (Seidelova metoda, Libmanův proces, metoda postupné substituce) je klasickou iterační metodou pro řešení soustavy lineárních rovnic .
Pojmenováno po Seidelovi a Gaussovi .
Prohlášení o problému
Vezměte systém:
, kde![A\vec{x}=\vec{b}](https://wikimedia.org/api/rest_v1/media/math/render/svg/bec3e6a204d6c406e92e474ff08701af60a3c9fd)
Nebo
A ukážeme si, jak to lze řešit pomocí Gauss-Seidelovy metody.
Metoda
Abychom objasnili podstatu metody, přepíšeme problém do formuláře
Zde jsme v té rovnici převedli na pravou stranu všechny členy obsahující , pro . Tento záznam může být reprezentován jako
![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)
kde v akceptované notaci znamená matici, jejíž hlavní diagonála obsahuje odpovídající prvky matice a všechny ostatní nuly; zatímco matice a obsahují horní a dolní trojúhelníkové části , na jejichž hlavní diagonále jsou nuly.
![\mathrm{D}](https://wikimedia.org/api/rest_v1/media/math/render/svg/3c894024162d89aa8502758b2151cb579806ea9a)
![A](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)
![A](https://wikimedia.org/api/rest_v1/media/math/render/svg/7daff47fa58cdfd29dc333def748ff5fa4c923e3)
Iterační proces v Gauss-Seidelově metodě je postaven podle vzorce
po zvolení vhodné počáteční aproximace .
![\vec{x}^{(0)}](https://wikimedia.org/api/rest_v1/media/math/render/svg/bba4c3386310019219b3b52120130b66633e601a)
Na Gauss-Seidelovu metodu lze pohlížet jako na modifikaci Jacobiho metody . Hlavní myšlenkou úpravy je, že nové hodnoty jsou zde použity ihned po jejich přijetí, zatímco v Jacobiho metodě se nepoužívají až do další iterace:
![\vec{x}^{(i)}](https://wikimedia.org/api/rest_v1/media/math/render/svg/765f38cb24670dd968199b58affb922c1ef78254)
kde
I -tá složka -té aproximace se tedy vypočítá podle vzorce
![(k+1)](https://wikimedia.org/api/rest_v1/media/math/render/svg/3f9f13644a6be482d7ddb19a6e0c706564773085)
Například, když :
![n=3](https://wikimedia.org/api/rest_v1/media/math/render/svg/1c5a5a42ced00df920fad4ab2d4acdb960a4105b)
![x_{1}^{{(k+1)}}=\součet _{{j=1}}^{{1-1}}c_{{1j}}x_{{j}}^{{(k) +1)}}+\součet _{{j=1}}^{{3}}c_{{1j}}x_{{j}}^{{(k)}}+d_{1}](https://wikimedia.org/api/rest_v1/media/math/render/svg/3bcf1485ab0ee27838a2a372d5af5de69e534c02)
, to je
![x_{2}^{{(k+1)}}=\sum _{{j=1}}^{{2-1}}c_{{2j}}x_{{j}}^{{(k) +1)}}+\součet _{{j=2}}^{{3}}c_{{2j}}x_{{j}}^{{(k)}}+d_{2}](https://wikimedia.org/api/rest_v1/media/math/render/svg/05c574da64857c2a8073eac0005bbcafae3d25bf)
, to je
![x_{3}^{{(k+1)}}=\sum _{{j=1}}^{{3-1}}c_{{3j}}x_{{j}}^{{(k) +1)}}+\součet _{{j=3}}^{{3}}c_{{3j}}x_{{j}}^{{(k)}}+d_{3}](https://wikimedia.org/api/rest_v1/media/math/render/svg/0e8802609130f0e42d2bb2dd0a6b5de27f2202f1)
, to je
Podmínka konvergence
Uveďme postačující podmínku pro konvergenci metody.
|
Věta . Nechť, kdeje matice inverzní k. Pak pro jakoukoli volbu počáteční aproximace:
![{\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} +\ mathrm {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) - metoda Gauss-Seidel konverguje;
- rychlost konvergence metody je rovna rychlosti konvergence geometrické progrese se jmenovatelem ;
![{\displaystyle q=\|\mathrm {A} _{2}\|}](https://wikimedia.org/api/rest_v1/media/math/render/svg/57ecfa2b1a7f1711e936b85d41fc913ffc272902)
- správný odhad chyby: .
![{\displaystyle \|{\vec {x}}^{(k)}-{\vec {x}}\|=q^{k}\,\|{\vec {x}}^{(0) }-{\vec {x}}\|}](https://wikimedia.org/api/rest_v1/media/math/render/svg/aa64613b1f422a660563385258a9c2a1a5f7f0b2)
|
|
Podmínka ukončení
Podmínka pro ukončení Seidelova iteračního procesu při dosažení přesnosti ve zjednodušené podobě má podobu:
![\varepsilon](https://wikimedia.org/api/rest_v1/media/math/render/svg/a30c89172e5b88edbd45d3e2772c7f5e562e5173)
Přesnější podmínka pro ukončení iteračního procesu má tvar
a vyžaduje více výpočtů. Dobré pro řídké matrice .
Příklad implementace v C++
#include <iostream>
#include <cmath>
pomocí jmenného prostoru std ;
// Koncová podmínka
bool converge ( double xk [ 10 ], double xkp [ 10 ], int n , double eps )
{
dvojitá norma = 0 ;
for ( int i = 0 ; i < n ; i ++ )
norma += ( xk [ i ] - xkp [ i ]) * ( xk [ i ] - xkp [ i ]);
return ( sqrt ( norm ) < eps );
}
double okr ( double x , double eps )
{
int i = 0 ;
double neweps = eps ;
zatímco ( novinky < 1 )
{
i ++ ;
neweps *= 10 ;
}
int okr = pow ( double ( 10 ), i );
x = int ( x * okr + 0,5 ) / double ( okr );
návrat x ;
}
boolova úhlopříčka ( double a [ 10 ][ 10 ], int n )
{
int i , j , k = 1 ;
dvojnásobný součet ;
for ( i = 0 ; i < n ; i ++ ) {
součet = 0 ;
for ( j = 0 ; j < n ; j ++ ) součet += abs ( a [ i ][ j ]);
součet -= abs ( a [ i ][ i ]);
if ( součet > a [ i ][ i ])
{
k = 0 _
cout << a [ i ][ i ] << " < " << soucet << endl ;
}
jiný
{
cout << a [ i ][ i ] << " > " << soucet << endl ;
}
}
návrat ( k == 1 );
}
int main ()
{
setlocale ( LC_ALL , "" );
double eps , a [ 10 ][ 10 ], b [ 10 ], x [ 10 ], p [ 10 ];
int n , i , j , m = 0 ;
metoda int _
cout << "Zadejte velikost čtvercové matice: " ;
cin >> n ;
cout << "Zadejte přesnost výpočtu: " ;
cin >> eps ;
cout << "Vyplňte matici A: " << endl << endl ;
pro ( i = 0 ; i < n ; i ++ )
pro ( j = 0 ; j < n ; j ++ )
{
cout << "A[" << i << "][" << j << "] = " ;
cin >> a [ i ][ j ];
}
cout << endl << endl ;
cout << "Vaše matice A je: " << endl << endl ;
pro ( i = 0 ; i < n ; i ++ )
{
pro ( j = 0 ; j < n ; j ++ )
cout << a [ i ][ j ] << " " ;
cout << endl ;
}
cout << endl ;
cout << "Vyplňte sloupec volných členů: " << endl << endl ;
pro ( i = 0 ; i < n ; i ++ )
{
cout << "B[" << i + 1 << "] = " ;
cin >> b [ i ];
}
cout << endl << endl ;
/*
Postup metody, kde:
a[n][n] - Matice koeficientů
x[n], p[n] - Aktuální a předchozí řešení
b[n] - Sloupec pravých částí
Všechna výše uvedená pole jsou skutečná a
musí být definováno v hlavním programu,
také do pole x[n] byste měli vložit počáteční
aproximace sloupce řešení (např. všechny nuly)
*/
for ( int i = 0 ; i < n ; i ++ )
x [ i ] = 1 ;
cout << "Diagonální dominance: " << endl ;
if ( úhlopříčka ( a , n )) {
dělat
{
for ( int i = 0 ; i < n ; i ++ )
p [ i ] = x [ i ];
for ( int i = 0 ; i < n ; i ++ )
{
double 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 ++ ;
} while ( ! konvergovat ( x , p , n , eps ));
cout << "Rozhodnutí systému:" << endl << endl ;
for ( i = 0 ; i < n ; i ++ ) cout << "x" << i << " = " << okr ( x [ i ], eps ) << "" << endl ;
cout << "Iterace: " << m << endl ;
}
jinak {
cout << "Bez diagonální dominance" << endl ;
}
systém ( "pauza" );
návrat 0 ;
}
Příklad implementace v Pythonu
import numpy jako np
def seidel ( A , b , eps ):
n = len ( A )
x = np . nuly ( n ) # nulový vektor
converge = False
, zatímco nekonverguje : x_new = np . kopie ( x ) pro i v rozsahu ( n ): s1 = součet ( A [ i ][ j ] * x_new [ j ] pro j v rozsahu ( i )) s2 = součet ( A [ i ][ j ] * x [ j ] pro j v rozsahu ( i + 1 , n )) x_new [ i ] = ( b [ i ] - s1 - s2 ) / A [ i ][ i ]
konvergovat = np . sqrt ( součet (( x_new [ i ] - x [ i ]) ** 2 pro i v rozsahu ( n ))) <= eps
x = x_new
vrátit x
Viz také
Poznámky
Odkazy
Metody řešení SLAE |
---|
Přímé metody |
|
---|
Iterační metody |
|
---|
Všeobecné |
|
---|