Метод Гаусса — ЗайделяФіліп Людвіг Зейдель (1821—1896) — німецький астроном та математик, Карл Фрідріх Гаус (1777—1855) — німецький математик, астроном та фізик є класичним ітераційним методом розв'язку системи лінійних рівнянь.
Постановка задачі Візьмемо систему: , де
Або
І покажемо, як її можна розв'язати за допомогою методу Гаусса — Зайделя.
Метод Щоб пояснити зміст методу, перепишемо задачу у вигляді:
Тут в -му рівнянні ми перенесли в праву частину всі члени, що містять , для . Отримана система може бути представлена:
,
де в прийнятих позначеннях 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];
Див. також Геометрична прогресія Метод покоординатного спуску (Гаусса — Зайделя) Метод простої ітерації Метод Якобі Теорема Банаха
Примітки
Джерела