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

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

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

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

Візьмемо систему: A\vec{x}=\vec{b}, де A=\left(
\begin{array}{ccc}
a_{11} & \ldots & a_{1n} \\
\vdots & \ddots & \vdots \\
a_{n1} & \ldots & a_{nn} 
\end{array} \right),\quad \vec{b}=\left(
\begin{array}{c}
b_1 \\
\vdots \\
b_n 
\end{array} \right)

Або \left\{
\begin{array}{rcl}
a_{11}x_1 + \ldots + a_{1n}x_n& = & b_{1} \\
& &\\
a_{n1}x_1 + \ldots + a_{nn}x_n & = & b_{n} 
\end{array} \right.

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

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

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

\left\{
\begin{array}{lcr}
a_{11}x_1 & = &-a_{12}x_2 - a_{13}x_3 -\ldots - a_{1n}x_n  +  b_1\\
a_{21}x_1 + a_{22}x_2 & = & -a_{23}x_3 - \ldots - a_{2n}x_n  +  b_2\\
\ldots & &\\
a_{(n-1)1}x_1 + a_{(n-1)2}x_2 +\ldots+ 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 +\ldots+ a_{n(n-1)}x_{n-1}+ a_{nn}x_n & = & b_n
\end{array} \right.

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

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

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

Ітеративний процес в методі Гауса-Зейделя будується за формулою (\mathrm{L} + \mathrm{D} )\vec{x}^{(k+1)} = -\mathrm{U} \vec{x}^{(k)} + \vec{b} ,\quad k = 0, 1, 2, \ldots після вибору відповідного початкового наближення \vec{x}^{(0)}.

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

\left\{\begin{array}{ccccccccccc}
{x_{1}}^{(k+1)} &=& c_{12}{x_2^{(k)}} &+& c_{13}x_3^{(k)}&+& {\ldots}&+& c_{1n}{x_n}^{(k)} &+& d_1 \\
{x_{2}}^{(k+1)} &=& c_{21}{x_1^{(k+1)}} &+& c_{23}x_3^{(k)}&+& {\ldots}&+& c_{2n}{x_n}^{(k)} &+& d_2 \\
\ldots & & & & & & & & & & \\
{x_{n}}^{(k+1)} &=& c_{n1}{x_1^{(k+1)}} &+& c_{n2}{x_2^{(k+1)}}&+& {\ldots}&+& c_{n(n-1)}{x_{n-1}}^{(k+1)} &+& d_n
\end{array}\right.,

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

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

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

Logo arte.jpg Теорема.
Нехай \| \mathrm{A}_2 \| < 1\!, де \mathrm{A}_2 = -(\mathrm{L} + \mathrm{D})^{-1} \, \mathrm{U}, \quad (\mathrm{L} + \mathrm{D})^{-1}\! – матриця, обернена до (\mathrm{L} + \mathrm{D})\!. Тоді при довільному виборі початкового наближення \vec{x}^{(0)}\!:
  1. метод Гауса-Зейделя збігається;
  2. швидкість збіжності методу дорівнює швидкості збіжності геометричної прогресії зі знаменником q = \|\mathrm{A}_2\|\!;
  3. справджується оцінка похибки: \|\vec{x}^{(k)}-\vec{x}\|=q^k \, \|\vec{x}^{(0)}-\vec{x}\|\!.

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

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

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

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

\parallel Ax^{(k)}-b\parallel \le \varepsilon

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

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

 // Умова завершення
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) — німецький математик, астроном та фізик

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