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
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
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.
Iterační proces v Gauss-Seidelově metodě je postaven podle vzorce
po zvolení vhodné počáteční aproximace .
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:
kde
I -tá složka -té aproximace se tedy vypočítá podle vzorce
Například, když :
, to je
, to je
, 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:
- metoda Gauss-Seidel konverguje;
- rychlost konvergence metody je rovna rychlosti konvergence geometrické progrese se jmenovatelem ;
- správný odhad chyby: .
|
|
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:
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é |
|
---|