Метод Гауса — Зейделя

У Вікіпедії є статті про інші значення цього терміна: .

Метод Гаусса — Зайделя є класичним ітераційним методом розв'язку системи лінійних рівнянь.

Постановка задачі

Візьмемо систему: ${\displaystyle A{\vec {x}}={\vec {b}}}$, де ${\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)}$

Або ${\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.}$

І покажемо, як її можна розв'язати за допомогою методу Гаусса — Зайделя.

Метод

Щоб пояснити зміст методу, перепишемо задачу у вигляді:

${\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.}$

Тут в ${\displaystyle j}$-му рівнянні ми перенесли в праву частину всі члени, що містять ${\displaystyle x_{i}}$, для ${\displaystyle i>j}$. Отримана система може бути представлена:

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

де в прийнятих позначеннях D означає матрицю, у якої на головній діагоналі стоять відповідні елементи матриці A, а всі інші — нулі; тоді як матриці U та L містять верхню і нижню трикутні частини A, на головній діагоналі яких нулі.

Ітеративний процес в методі Гаусса — Зайделя будується за формулою

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

після вибору відповідного початкового наближення ${\displaystyle {\vec {x}}^{(0)}}$.

Метод Гаусса — Зайделя можна розглядати як модифікацію (методу Якобі). Основна ідея модифікації полягає в тому, що нові значення ${\displaystyle {\vec {x}}^{(i)}}$ використовуються тут одразу ж у міру отримання, в той час як у методі Якобі вони не використовуються до наступної ітерації:

${\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.,}$

де ${\displaystyle c_{ij}=-{\frac {a_{ij}}{a_{ii}}},\quad d_{i}={\frac {b_{i}}{a_{ii}}},\quad i=1,\ldots ,n}$

Таким чином i-й компонент ${\displaystyle (k+1)}$-го наближення обчислюється за формулою:

${\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 }$ у спрощеній формі має вигляд:

${\displaystyle \parallel x^{(k+1)}-x^{(k)}\parallel \leq \varepsilon }$

Точніша умова завершення ітераційного процесу має вигляд

${\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];  } } 

Примітки

1. МЕТОД ГАУСА-ЗЕЙДЕЛЯ: ПОЯСНЕННЯ, ДОДАТКИ, ПРИКЛАДИ - НАУКА. warbletoncouncil (укр.). Процитовано 11 лютого 2021.
2. Філіп Людвіг Зейдель (1821—1896) — німецький астроном та математик, Карл Фрідріх Гаус (1777—1855) — німецький математик, астроном та фізик

Див. також

• Геометрична прогресія
• (Гаусса — Зайделя)
• (Метод простої ітерації)
• (Метод Якобі)