Метод Гаусса — Зейделя решения системы линейных уравнений

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

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

Постановка задачи[править | править код]

Возьмём систему: ${\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

В статье есть список источников, но не хватает сносок. Без сносок сложно определить, из какого источника взято каждое отдельное утверждение. Вы можете улучшить статью, проставив сноски на источники, подтверждающие информацию. Сведения без сносок могут быть удалены. (17 января 2024)