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

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

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

Візьмемо систему: $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)$

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

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

Метод

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

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

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

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

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

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

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

Метод Гаусса — Зайделя можна розглядати як модифікацію методу Якобі. Основна ідея модифікації полягає в тому, що нові значення ${\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}\\\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_{ij}=-{\frac {a_{ij}}{a_{ii}}},\quad d_{i}={\frac {b_{i}}{a_{ii}}},\quad i=1,\ldots ,n$

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

$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$

Умова збіжності

Наведемо достатню умову збіжності методу.

Умова завершення

Умова завершення ітераційного процесу Гаусса — Зайделя при досягненні точності $\varepsilon$ у спрощеній формі має вигляд:

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

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

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

Див. також

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