Відкрити головне меню

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

Постановка задачіРедагувати

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

Або  

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

МетодРедагувати

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

 

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

 

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

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

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

 

де  

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

 

Умова збіжностіРедагувати

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

  Теорема.
Нехай  , де   – матриця, обернена до  . Тоді при довільному виборі початкового наближення  :
  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];
    }
}

ПриміткиРедагувати

Див. такожРедагувати