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

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

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

Візьмемо систему:

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

і потребує більше обчислень.