Gauss-Seidelin menetelmä lineaarisen yhtälöjärjestelmän ratkaisemiseksi

Gauss-Seidelin menetelmä (Seidel-menetelmä, Libman-prosessi, peräkkäinen substituutiomenetelmä) on klassinen iteratiivinen menetelmä lineaarisen yhtälöjärjestelmän ratkaisemiseksi .

Nimetty Seidelin ja Gaussin mukaan .

Ongelman selvitys

Ota järjestelmä: , missä $A\vec{x}=\vec{b}$ $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} \\ & &\\ a_{n1}x_1 + \ldots + a_{nn }x_n & = & b_{n} \end{array} \right.$

Ja näytämme kuinka se voidaan ratkaista Gauss-Seidel-menetelmällä.

Menetelmä

Selvittääksemme menetelmän ydintä, kirjoitamme ongelman uudelleen muotoon

\left\{ \begin{array}{lcr} a_{11}x_1 & = &-a_{12}x_2 - a_{13}x_3 -\ldots - a_{1n}x_n + b_1\\ a_{21}x_1 + a_{22}x_2 & = & -a_{23}x_3 - \ldots - a_{2n}x_n + b_2\\ \ldots & &\\ a_{(n-1)1}x_1 + a_{(n- 1)2}x_2 +\lpisteet+ a_{(n-1)(n-1)}x_{n-1} & = & -a_{(n-1)n}x_n + b_{n-1}\\ a_{n1}x_1 + a_{n2}x_2 +\ldots+ a_{n(n-1)}x_{n-1}+ a_{nn}x_n & = & b_n \end{array} \right.

Tässä yhtälössä olemme siirtäneet oikealle puolelle kaikki termit, jotka sisältävät , for . Tämä merkintä voidaan esittää muodossa $j$ $x_{i}$ $i>j$

(\mathrm{L} + \mathrm{D} )\vec{x} = -\mathrm{U} \, \vec{x} + \vec{b},

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 osat , joiden päälävistäjä on nollia. $\mathrm{D}$ $A$ $\mathrm{U}$ $\mathrm{L}$ $A$

Gauss-Seidel-menetelmän iteratiivinen prosessi rakennetaan kaavan mukaan

(\mathrm {L} +\mathrm {D} ){\vec {x}}^{(k+1)}=-\mathrm {U} {\vec {x}}^{(k) }+{\vec {b)],\quad k=0,1,2,\ldots

kun olet valinnut oikean alkuperäisen likiarvon . $\vec{x}^{(0)}$

Gauss-Seidelin menetelmää voidaan pitää Jacobin menetelmän muunnelmana . Muokkauksen pääideana on, että uusia arvoja käytetään täällä heti, kun ne on vastaanotettu, kun taas Jacobi-menetelmässä niitä ei käytetä ennen seuraavaa iteraatiota: $\vec{x}^{(i)}$

\left\{\begin{array}{ccccccccccc} {x_{1}}^{(k+1)} &=& c_{12}{x_2^{(k))) &+& c_{13}x_3 ^{(k)}&+& {\ldots}&+& c_{1n}{x_n}^{(k)} &+& d_1 \\ {x_{2}}^{(k+1)} & =& c_{21}{x_1^{(k+1)}} &+& c_{23}x_3^{(k)}&+& {\ldots}&+& c_{2n}{x_n}^{ (k)} &+& d_2 \\ \lpisteet & & & & & & & & & & & \\ {x_{n}}^{(k+1)} &=& c_{n1}{x_1^{( k+1)}} &+& c_{n2}{x_2^{(k+1)}}&+& {\ldots}&+& c_{n(n-1)}{x_{n-1} }^{(k+1)} &+& d_n \end{array}\right.,

missä

c_{ij}={\begin{cases}-{\frac {a_{ij}}{a_{ii}}},&j\neq i,\\0,&j=i.\end{cases} }\quad d_{i}={\frac {b_{i}}{a_{ii}}},\quad i=1,\ldots ,n.

Siten - :nnen approksimoinnin i -komponentti lasketaan kaavalla $(k+1)$

x_{i}^{(k+1)}=\summa _{j=1}^{i-1}c_{ij}x_{j}^{(k+1)}+\summa _ {j=i}^{n}c_{ij}x_{j}^{(k)}+d_{i},\quad i=1,\ldots ,n.

Esimerkiksi kun : $n = 3$

x_{1}^{{(k+1)}}=\summa _{{j=1}}^{{1-1}}c_{{1j}}x_{{j}}^{{(k +1)}}+\summa _{{j=1}}^{{3}}c_{{1j}}x_{{j}}^{{(k)}}+d_{1}

, tuo on

x_{1}^{(k+1)}=c_{11}x_{1}^{(k)}+c_{12}x_{2}^{(k)}+c_{13} x_{3}^{(k)}+d_{1},

x_{2}^{{(k+1)}}=\summa _{{j=1}}^{{2-1}}c_{{2j}}x_{{j}}^{{(k +1)}}+\summa _{{j=2}}^{{3}}c_{{2j}}x_{{j}}^{{(k)}}+d_{2}

, tuo on

x_{2}^{(k+1)}=c_{21}x_{1}^{(k+1)}+c_{22}x_{2}^{(k)}+c_{ 23}x_{3}^{(k)}+d_{2},

x_{3}^{{(k+1)}}=\summa _{{j=1}}^{{3-1}}c_{{3j}}x_{{j}}^{{(k +1)}}+\summa _{{j=3}}^{{3}}c_{{3j}}x_{{j}}^{{(k)}}+d_{3}

, tuo on

x_{3}^{(k+1)}=c_{31}x_{1}^{(k+1)}+c_{32}x_{2}^{(k+1)}+ c_{33}x_{3}^{(k)}+d_{3}.

Konvergenssiehto

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

Lause .
Antaa, missäon matriisi käänteinen. Sitten mistä tahansa alkuperäisen likiarvon valinnasta:

\|\mathrm {A} _{2}\|<1

\mathrm {A} _{2}=-(\mathrm {L} +\mathrm {D} )^{-1}\,\mathrm {U} ,\quad (\mathrm {L} +\ matematiikka {D} )^{-1}

(\mathrm {L} +\mathrm {D} )

\vec{x}^{(0)}

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

Päättymisehto

Edellytys Seidelin iteratiivisen prosessin lopettamiselle, kun tarkkuus saavutetaan yksinkertaistetussa muodossa, on muotoa: $\varepsilon$

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

Tarkemmalla ehdolla iteratiivisen prosessin lopettamiselle on muoto

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

ja vaatii enemmän laskentaa. Hyvä harvoille matriiseille .

Toteutusesimerkki C++ :ssa

#include <iostream> #include <cmath> käyttäen nimiavaruutta std ; // Loppuehto bool converge ( double xk [ 10 ], double xkp [ 10 ], int n , double eps ) { kaksinkertainen normi = 0 ; for ( int i = 0 ; i < n ; i ++ ) normi += ( xk [ i ] - xkp [ i ]) * ( xk [ i ] - xkp [ i ]); return ( sqrt ( norm ) < eps ; } double okr ( double x , double eps ) { int i = 0 ; double neweps = eps ; kun ( uudet uutiset < 1 ) { i ++ ; neweps *= 10 ; } int okr = pow ( double ( 10 ), i ); x = int ( x * okr + 0,5 ) / double ( okr ); paluu x ; } bool diagonaali ( double a [ 10 ][ 10 ], int n ) { int i , j , k = 1 ; kaksinkertainen summa ; for ( i = 0 ; i < n ; i ++ ) { summa = 0 ; for ( j = 0 ; j < n ; j ++ ) summa += abs ( a [ i ][ j ]); summa -= abs ( a [ i ][ i ]); jos ( summa > a [ i ][ i ]) { k = 0_ _ cout << a [ i ][ i ] << " < " << summa << endl ; } muu { cout << a [ i ][ i ] << " > " << summa << endl ; } } paluu ( k == 1 ); } int main () { setlocale ( LC_ALL , "" ); double eps , a [ 10 ][ 10 ], b [ 10 ], x [ 10 ], p [ 10 ]; int n , i , j , m = 0 ; int menetelmä _ cout << "Syötä neliömatriisin koko: " ; cin >> n ; cout << "Syötä laskennan tarkkuus:" ; cin >> eps ; cout << "Täytä matriisi 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 << "Matriisi A on: " << endl << endl ; for ( i = 0 ; i < n ; i ++ ) { for ( j = 0 ; j < n ; j ++ ) cout << a [ i ][ j ] << " " ; cout << endl ; } cout << endl ; cout << "Täytä vapaat jäsenet -sarake: " << endl << endl ; for ( i = 0 ; i < n ; i ++ ) { cout << "B[" << i + 1 << "] = " ; cin >> b [ i ]; } cout << endl << endl ; /* Menetelmän edistyminen, missä: a[n][n] - kertoimien matriisi x[n], p[n] - Nykyiset ja aiemmat ratkaisut b[n] - Oikeanpuoleisten osien sarake Kaikki yllä olevat taulukot ovat todellisia ja on määriteltävä pääohjelmassa, myös taulukkoon x[n] tulee laittaa alkukirjain ratkaisusarakkeen likiarvo (esim. kaikki nollat) */ for ( int i = 0 ; i < n ; i ++ ) x [ i ] = 1 ; cout << "Diagonaalinen dominanssi: " << endl ; if ( diagonaali ( a , n )) { tehdä { for ( int i = 0 ; i < n ; i ++ ) p [ i ] = x [ i ]; for ( int i = 0 ; i < n ; i ++ ) { kaksinkertainen 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 ( ! converge ( x , p , n , eps )); cout << "Järjestelmäpäätös:" << endl << endl ; for ( i = 0 ; i < n ; i ++ ) cout << "x" << i << " = " << okr ( x [ i ], eps ) << "" << endl ; cout << "Iteraatiot: " << m << endl ; } else { cout << "Ei diagonaalista dominanssia" << endl ; } system ( "tauko" ); paluu 0 ; }

Toteutusesimerkki Pythonissa

tuonti numpy as np def seidel ( A , b , eps ): n = len ( A ) x = np . nollat ( n ) # nollavektori converge = Väärä , mutta ei konvergoi : x_new = np . kopioi ( x ) i :lle alueella ( n ) : s1 = summa ( A [ i ][ j ] * x_uusi [ j ] j :lle alueella ( i ) ) s2 = summa ( A [ i ][ j ] * x [ j ] j :lle alueella ( i + 1 , n ) ) x_uusi [ i ] = ( b [ i ] - s1 - s2 ) / A [ i ][ i ] konverge = np . sqrt ( summa (( x_uusi [ i ] - x [ i ]) ** 2 i :lle alueella ( n ) )) <= eps x = x_uusi palauta x

Katso myös

Muistiinpanot

Linkit

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