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

Матеріал з Вікіпедії — вільної енциклопедії.
Перейти до навігації Перейти до пошуку

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

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

[ред. | ред. код]

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

Або

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

Метод

[ред. | ред. код]

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

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

,

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

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

після вибору відповідного початкового наближення .

Метод Гаусса — Зайделя можна розглядати як модифікацію методу Якобі. Основна ідея модифікації полягає в тому, що нові значення використовуються тут одразу ж у міру отримання, в той час як у методі Якобі вони не використовуються до наступної ітерації:

де

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

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

[ред. | ред. код]

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

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

[ред. | ред. код]

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

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

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

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

[ред. | ред. код]
 // Умова завершення
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. Філіп Людвіг Зейдель (18211896) — німецький астроном та математик, Карл Фрідріх Гаус (17771855) — німецький математик, астроном та фізик

Див. також

[ред. | ред. код]