Метод Гауса — Зейделя — Вікіпедія

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

Постановка задачі[ред. | ред. код]

Візьмемо систему: ${\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 \|\mathrm {A} _{2}\|<1\!}$, де ${\displaystyle \mathrm {A} _{2}=-(\mathrm {L} +\mathrm {D} )^{-1}\,\mathrm {U} ,\quad (\mathrm {L} +\mathrm {D} )^{-1}\!}$ – матриця, обернена до ${\displaystyle (\mathrm {L} +\mathrm {D} )\!}$. Тоді при довільному виборі початкового наближення ${\displaystyle {\vec {x}}^{(0)}\!}$: метод Гауса-Зейделя збігається; швидкість збіжності методу дорівнює швидкості збіжності геометричної прогресії зі знаменником ${\displaystyle q=\|\mathrm {A} _{2}\|\!}$; справджується оцінка похибки: ${\displaystyle \|{\vec {x}}^{(k)}-{\vec {x}}\|=q^{k}\,\|{\vec {x}}^{(0)}-{\vec {x}}\|\!}$.

Умова завершення[ред. | ред. код]

Умова завершення ітераційного процесу Гауса-Зайделя при досягненні точності ${\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) — німецький математик, астроном та фізик

Див. також[ред. | ред. код]

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