Постановка задачі
ред.
Візьмемо систему:
A
x
→
=
b
→
{\displaystyle A{\vec {x}}={\vec {b}}}
, де
A
=
(
a
11
…
a
1
n
⋮
⋱
⋮
a
n
1
…
a
n
n
)
,
b
→
=
(
b
1
⋮
b
n
)
{\displaystyle 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)}
Або
{
a
11
x
1
+
…
+
a
1
n
x
n
=
b
1
a
n
1
x
1
+
…
+
a
n
n
x
n
=
b
n
{\displaystyle \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.}
І покажемо, як її можна розв'язати за допомогою методу Гауса - Зайделя.
Щоб пояснити зміст методу, перепишемо задачу у вигляді:
{
a
11
x
1
=
−
a
12
x
2
−
a
13
x
3
−
…
−
a
1
n
x
n
+
b
1
a
21
x
1
+
a
22
x
2
=
−
a
23
x
3
−
…
−
a
2
n
x
n
+
b
2
…
a
(
n
−
1
)
1
x
1
+
a
(
n
−
1
)
2
x
2
+
…
+
a
(
n
−
1
)
(
n
−
1
)
x
n
−
1
=
−
a
(
n
−
1
)
n
x
n
+
b
n
−
1
a
n
1
x
1
+
a
n
2
x
2
+
…
+
a
n
(
n
−
1
)
x
n
−
1
+
a
n
n
x
n
=
b
n
{\displaystyle \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}+\ldots +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.}
Тут в
j
{\displaystyle j}
-му рівнянні ми перенесли в праву частину всі члени, що містять
x
i
{\displaystyle x_{i}}
, для
i
>
j
{\displaystyle i>j}
. Отримана система може бути представлена:
(
L
+
D
)
x
→
=
−
U
x
→
+
b
→
,
{\displaystyle (\mathrm {L} +\mathrm {D} ){\vec {x}}=-\mathrm {U} \,{\vec {x}}+{\vec {b}},}
де в прийнятих позначеннях D означає матрицю, у якої на головній діагоналі стоять відповідні елементи матриці A, а всі інші - нулі; тоді як матриці U та L містять верхню і нижню трикутні частини A, на головній діагоналі яких нулі.
Ітеративний процес в методі Гауса-Зайделя будується за формулою
(
L
+
D
)
x
→
(
k
+
1
)
=
−
U
x
→
(
k
)
+
b
→
,
k
=
0
,
1
,
2
,
…
{\displaystyle (\mathrm {L} +\mathrm {D} ){\vec {x}}^{(k+1)}=-\mathrm {U} {\vec {x}}^{(k)}+{\vec {b}},\quad k=0,1,2,\ldots }
після вибору відповідного початкового наближення
x
→
(
0
)
{\displaystyle {\vec {x}}^{(0)}}
.
Метод Гауса-Зайделя можна розглядати як модифікацію методу Якобі . Основна ідея модифікації полягає в тому, що нові значення
x
→
(
i
)
{\displaystyle {\vec {x}}^{(i)}}
використовуються тут одразу ж у міру отримання, в той час як у методі Якобі вони не використовуються до наступної ітерації:
{
x
1
(
k
+
1
)
=
c
12
x
2
(
k
)
+
c
13
x
3
(
k
)
+
…
+
c
1
n
x
n
(
k
)
+
d
1
x
2
(
k
+
1
)
=
c
21
x
1
(
k
+
1
)
+
c
23
x
3
(
k
)
+
…
+
c
2
n
x
n
(
k
)
+
d
2
…
x
n
(
k
+
1
)
=
c
n
1
x
1
(
k
+
1
)
+
c
n
2
x
2
(
k
+
1
)
+
…
+
c
n
(
n
−
1
)
x
n
−
1
(
k
+
1
)
+
d
n
,
{\displaystyle \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}\\\ldots &&&&&&&&&&\\{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.,}
де
c
i
j
=
−
a
i
j
a
i
i
,
d
i
=
b
i
a
i
i
,
i
=
1
,
…
,
n
{\displaystyle c_{ij}=-{\frac {a_{ij}}{a_{ii}}},\quad d_{i}={\frac {b_{i}}{a_{ii}}},\quad i=1,\ldots ,n}
Таким чином i-тий компонент
(
k
+
1
)
{\displaystyle (k+1)}
-го наближення обчислюється за формулою:
x
i
(
k
+
1
)
=
∑
j
=
1
i
−
1
c
i
j
x
j
(
k
+
1
)
+
∑
j
=
i
+
1
n
c
i
j
x
j
(
k
)
+
d
i
,
i
=
1
,
…
,
n
{\displaystyle x_{i}^{(k+1)}=\sum _{j=1}^{i-1}c_{ij}x_{j}^{(k+1)}+\sum _{j=i+1}^{n}c_{ij}x_{j}^{(k)}+d_{i},\quad i=1,\ldots ,n}
Умова збіжності
ред.
Наведемо достатню умову збіжності методу.
Умова завершення
ред.
Умова завершення ітераційного процесу Гауса-Зайделя при досягненні точності
ε
{\displaystyle \varepsilon }
у спрощеній формі має вигляд:
∥
x
(
k
+
1
)
−
x
(
k
)
∥≤
ε
{\displaystyle \parallel x^{(k+1)}-x^{(k)}\parallel \leq \varepsilon }
Точніша умова завершення ітераційного процесу має вигляд
∥
A
x
(
k
)
−
b
∥≤
ε
{\displaystyle \parallel Ax^{(k)}-b\parallel \leq \varepsilon }
і потребує більше обчислень. Добре підходить для розріджених матриць .
Приклад алгоритму на С++
ред.
// Умова завершення
bool converge ( double * xk , double * xkp )
{
bool b = true ;
for ( int i = 0 ; i < n ; i ++ )
{
if ( fabs ( xk [ i ] - xkp [ i ]) > eps )
{
b = false ;
break ;
}
}
return b ;
}
while ( ! converge ( x , p ))
{
for ( int i = 0 ; i < n ; i ++ )
{
var = 0 ;
for ( int j = 0 ; j < n ; j ++ )
{
if ( j != i )
var += ( a [ i ][ j ] * x [ j ]);
}
p [ i ] = x [ i ];
x [ i ] = ( b [ i ] - var ) / a [ i ][ i ];
}
}
Примітки
ред.
Див. також
ред.