Метод Зейделя - NiNa.Az

Не следует путать с методом покоординатного спуска Гаусса — Зейделя — методом поиска экстремума.

Термин «Метод Гаусса» имеет также другие значения.

Ме́тод Га́усса — Зе́йделя (метод Зейделя, процесс Либмана, метод последовательных замещений) — является классическим итерационным методом решения системы линейных уравнений.

Назван в честь Зейделя и Гаусса.

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

Возьмём систему: ${\displaystyle A{\vec {x}}={\vec {b}}}$, где ${\displaystyle 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)}$

Или ${\displaystyle \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.}$

И покажем, как её можно решить с использованием метода Гаусса-Зейделя.

Метод

Чтобы пояснить суть метода, перепишем задачу в виде

${\displaystyle \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.}$

Здесь в ${\displaystyle j}$-м уравнении мы перенесли в правую часть все члены, содержащие ${\displaystyle x_{i}}$, для ${\displaystyle i>j}$. Эта запись может быть представлена как

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

где в принятых обозначениях ${\displaystyle \mathrm {D} }$ означает матрицу, у которой на главной диагонали стоят соответствующие элементы матрицы ${\displaystyle A}$, а все остальные нули; тогда как матрицы ${\displaystyle \mathrm {U} }$ и ${\displaystyle \mathrm {L} }$ содержат верхнюю и нижнюю треугольные части ${\displaystyle A}$, на главной диагонали которых нули.

Итерационный процесс в методе Гаусса — Зейделя строится по формуле

${\displaystyle (\mathrm {L} +\mathrm {D} ){\vec {x}}^{(k+1)}=-\mathrm {U} {\vec {x}}^{(k)}+{\vec {b}},\quad k=0,1,2,\ldots }$

после выбора соответствующего начального приближения ${\displaystyle {\vec {x}}^{(0)}}$.

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

${\displaystyle \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.,}$

где

${\displaystyle c_{ij}={\begin{cases}-{\frac {a_{ij}}{a_{ii}}},&j\neq i,\\0,&j=i.\end{cases}}\quad d_{i}={\frac {b_{i}}{a_{ii}}},\quad i=1,\ldots ,n.}$

Таким образом, i-я компонента ${\displaystyle (k+1)}$-го приближения вычисляется по формуле

${\displaystyle x_{i}^{(k+1)}=\sum _{j=1}^{i-1}c_{ij}x_{j}^{(k+1)}+\sum _{j=i}^{n}c_{ij}x_{j}^{(k)}+d_{i},\quad i=1,\ldots ,n.}$

Например, при ${\displaystyle n=3}$:

${\displaystyle x_{1}^{(k+1)}=\sum _{j=1}^{1-1}c_{1j}x_{j}^{(k+1)}+\sum _{j=1}^{3}c_{1j}x_{j}^{(k)}+d_{1}}$, то есть ${\displaystyle x_{1}^{(k+1)}=c_{11}x_{1}^{(k)}+c_{12}x_{2}^{(k)}+c_{13}x_{3}^{(k)}+d_{1},}$

${\displaystyle x_{2}^{(k+1)}=\sum _{j=1}^{2-1}c_{2j}x_{j}^{(k+1)}+\sum _{j=2}^{3}c_{2j}x_{j}^{(k)}+d_{2}}$, то есть ${\displaystyle x_{2}^{(k+1)}=c_{21}x_{1}^{(k+1)}+c_{22}x_{2}^{(k)}+c_{23}x_{3}^{(k)}+d_{2},}$

${\displaystyle x_{3}^{(k+1)}=\sum _{j=1}^{3-1}c_{3j}x_{j}^{(k+1)}+\sum _{j=3}^{3}c_{3j}x_{j}^{(k)}+d_{3}}$, то есть ${\displaystyle x_{3}^{(k+1)}=c_{31}x_{1}^{(k+1)}+c_{32}x_{2}^{(k+1)}+c_{33}x_{3}^{(k)}+d_{3}.}$

Условие сходимости

Приведём достаточное условие сходимости метода.

Теорема. Пусть ${\displaystyle \|\mathrm {A} _{2}\|<1}$, где ${\displaystyle \mathrm {A} _{2}=-(\mathrm {L} +\mathrm {D} )^{-1}\,\mathrm {U} ,\quad (\mathrm {L} +\mathrm {D} )^{-1}}$ – матрица, обратная к ${\displaystyle (\mathrm {L} +\mathrm {D} )}$. Тогда при любом выборе начального приближения ${\displaystyle {\vec {x}}^{(0)}}$: метод Гаусса-Зейделя сходится; скорость сходимости метода равна скорости сходимости геометрической прогрессии со знаменателем ${\displaystyle q=\|\mathrm {A} _{2}\|}$; верна оценка погрешности: ${\displaystyle \|{\vec {x}}^{(k)}-{\vec {x}}\|=q^{k}\,\|{\vec {x}}^{(0)}-{\vec {x}}\|}$.

Условие окончания

Условие окончания итерационного процесса Зейделя при достижении точности ${\displaystyle \varepsilon }$ в упрощённой форме имеет вид:

${\displaystyle \parallel x^{(k+1)}-x^{(k)}\parallel \leq \varepsilon }$

Более точное условие окончания итерационного процесса имеет вид

${\displaystyle \parallel Ax^{(k)}-b\parallel \leq \varepsilon }$

и требует больше вычислений. Хорошо подходит для разреженных матриц.

Пример реализации на C++

#include <iostream> #include <cmath>  using namespace std;  // Условие окончания bool converge(double xk[10], double xkp[10], int n, double eps) { double norm = 0; for (int i = 0; i < n; i++) norm += (xk[i] - xkp[i]) * (xk[i] - xkp[i]); return (sqrt(norm) < eps); }  double okr(double x, double eps) { int i = 0; double neweps = eps; while (neweps < 1) { i++; neweps *= 10; } int okr = pow(double(10), i); x = int(x * okr + 0.5) / double(okr);  return x; }  bool diagonal(double a[10][10], int n) { int i, j, k = 1; double sum; for (i = 0; i < n; i++) { sum = 0; for (j = 0; j < n; j++) sum += abs(a[i][j]); sum -= abs(a[i][i]); if (sum > a[i][i])  { k = 0;  cout << a[i][i] << " < " << sum << endl; } else { cout << a[i][i] << " > " << sum << endl; }   }  return (k == 1);  }  int main() { setlocale(LC_ALL, "");  double eps, a[10][10], b[10], x[10], p[10]; int n, i, j, m = 0; int method; cout << "Введите размер квадратной матрицы: "; cin >> n; cout << "Введите точность вычислений: "; cin >> eps; cout << "Заполните матрицу А: " << endl << endl; for (i = 0; i < n; i++) for (j = 0; j < n; j++) { cout << "A[" << i << "][" << j << "] = "; cin >> a[i][j]; } cout << endl << endl; cout << "Ваша матрица А: " << endl << endl; for (i = 0; i < n; i++) { for (j = 0; j < n; j++) cout << a[i][j] << " "; cout << endl; }  cout << endl;  cout << "Заполните столбец свободных членов: " << endl << endl; for (i = 0; i < n; i++) { cout << "В[" << i + 1 << "] = "; cin >> b[i]; }  cout << endl << endl;   /* Ход метода, где: a[n][n] - Матрица коэффициентов x[n], p[n] - Текущее и предыдущее решения b[n] - Столбец правых частей Все перечисленные массивы вещественные и должны быть определены в основной программе, также в массив x[n] следует поместить начальное приближение столбца решений (например, все нули) */  for (int i = 0; i < n; i++) x[i] = 1;  cout << "Диагональное преобладание: " << endl; if (diagonal(a, n)) { do { for (int i = 0; i < n; i++) p[i] = x[i]; for (int i = 0; i < n; i++) { double var = 0; for (int j = 0; j < n; j++)  if(j!=i) var += (a[i][j] * x[j]);  x[i] = (b[i] - var) / a[i][i]; } m++; } while (!converge(x, p, n, eps));    cout << "Решение системы:" << endl << endl; for (i = 0; i < n; i++) cout << "x" << i << " = " << okr(x[i], eps) << "" << endl; cout << "Итераций: " << m << endl; } else { cout << "Не выполняется преобладание диагоналей" << endl; }  system("pause"); return 0; } 

Пример реализации на Python

import numpy as np def seidel(A, b, eps): n = len(A) x = np.zeros(n) # zero vector converge = False while not converge: x_new = np.copy(x) for i in range(n): s1 = sum(A[i][j] * x_new[j] for j in range(i)) s2 = sum(A[i][j] * x[j] for j in range(i + 1, n)) x_new[i] = (b[i] - s1 - s2) / A[i][i] converge = np.linalg.norm(x_new - x) <= eps x = x_new 

См. также

• Геометрическая прогрессия
• Метод простой итерации
• Метод Якоби
• Теорема Банаха
• Метод итерации

Примечания

Ссылки

• https://www.maa.org/press/periodicals/loci/joma/iterative-methods-for-solving-iaxi-ibi-gauss-seidel-method
• https://www3.nd.edu/~zxu2/acms40390F12/Lec-7.3.pdf
• http://mathworld.wolfram.com/Gauss-SeidelMethod.html