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

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

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

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

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

Або

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

Метод[ред.ред. код]

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

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

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

Ітеративний процес в методі Гауса-Зейделя будується за формулою після вибору відповідного початкового наближення .

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

де

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

Умова збіжності[ред.ред. код]

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

Logo arte.jpg Теорема.
Нехай , де – матриця, обернена до . Тоді при довільному виборі початкового наближення :
  1. метод Гауса-Зейделя збігається;
  2. швидкість збіжності методу дорівнює швидкості збіжності геометричної прогресії зі знаменником ;
  3. справджується оцінка похибки: .

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

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

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

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

Приклад алгоритму на С++[ред.ред. код]

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

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