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

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

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

Візьмемо систему: $A\overrightarrow{x}=\overrightarrow{b}$, де $A=\left(\begin{array}{ccc}{a}_{11}& \dots & a_{1n}\\ ⋮& \ddots & ⋮\\ a_{n1}& \dots & a_{nn}\end{array}\right),\overrightarrow{b}=\left(\begin{array}{c}{b}_1\\ ⋮\\ b_n\end{array}\right)$

Або $\{\begin{array}{ccc}{a}_{11}{x}_1+\dots +a_{1n}{x}_n& =& b_1\\ & & \\ a_{n1}{x}_1+\dots +a_{nn}{x}_n& =& b_n\end{array}$

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

Метод

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

$\{\begin{array}{ccc}{a}_{11}{x}_1& =& -a_{12}{x}_2-a_{13}{x}_3-\dots -a_{1n}{x}_n+b_1\\ a_{21}{x}_1+a_{22}{x}_2& =& -a_{23}{x}_3-\dots -a_{2n}{x}_n+b_2\\ \dots & & \\ a_{(n-1)1}{x}_1+a_{(n-1)2}{x}_2+\dots +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+\dots +a_{n(n-1)}{x}_{n-1}+a_{nn}{x}_n& =& b_n\end{array}$

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

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

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

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

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

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

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

$\{\begin{array}{ccccccccccc}{x_1}^{(k+1)}& =& c_{12}{x}_2^{(k)}& +& c_{13}{x}_3^{(k)}& +& \dots & +& c_{1n}{x_n}^{(k)}& +& d_1\\ {x_2}^{(k+1)}& =& c_{21}{x}_1^{(k+1)}& +& c_{23}{x}_3^{(k)}& +& \dots & +& c_{2n}{x_n}^{(k)}& +& d_2\\ \dots & & & & & & & & & & \\ {x_n}^{(k+1)}& =& c_{n1}{x}_1^{(k+1)}& +& c_{n2}{x}_2^{(k+1)}& +& \dots & +& c_{n(n-1)}{x_{n-1}}^{(k+1)}& +& d_n\end{array},$

де $c_{ij}=-\frac{a_{ij}}{a_{ii}},d_i=\frac{b_i}{a_{ii}},i=1,\dots ,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,i=1,\dots ,n$

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

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

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

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

$\parallel x^{(k+1)}-x^{(k)}\parallel \le \epsilon$

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

$\parallel A{x}^{(k)}-b\parallel \le \epsilon$

і потребує більше обчислень. Добре підходить для розріджених матриць.

Приклад алгоритму на С++

 // Умова завершення
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];
    }
}

Див. також

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