Релаксационные методы

Материал из MachineLearning.

Версия от 06:46, 30 октября 2008; Yury Chekhovich (Обсуждение | вклад)
(разн.) ← Предыдущая | Текущая версия (разн.) | Следующая → (разн.)
Перейти к: навигация, поиск

Релаксационные методы — частный случай итерационных методов решения СЛАУ. Итерационные методы являются особенно эффективными при решении систем с большим количеством неизвестных (порядка 1000 и более).

Содержание

Введение

В общем случае сначала задаётся некоторый вектор x0, называемый начальным приближением. В общем случае начальное приближение может быть любым. От него строится последовательность x1, x2,...,xk и так далее, где число k называют номером итерации. Итерационный метод назвается одношаговым, если каждое последующее итерационное приближение строится только по одному предыдущему:

x^{k+1} = F_{k+1} (x^k)

Если F - линейная функция, то соответствующий итерационный метод называется линейным. Согласно определению, можно получить каноническую форму записи одношагового итерационного метода:

B_{k+1}\,\frac{x^{k+1} - x^k}{t^{k+1}} +Ax^k = f

Если  B_{k+1} = E , то соответствующий метод называется явным, в противном случае – неявным.

Изложение метода

Релаксационные методы являются стационарными и неявными решения СЛАУ. Пусть нам требуется решить систему линейных алгебраических уравнений:

 Ax = f

Представим матрицу A в виде суммы трёх матриц A_1, A_2 и D:

 A = A_1 + D + A_2 ,

Где  A_1 - нижнетреугольная,  A_2 - верхнетреугольная,  D - диагональная

Каноническая форма релаксационного метода записывается следующим образом

\left\{\begin{array}{rcl} B_{k+1} &=& D + \omega A_1 ,\\ t_{k+1} &=& \omega \end{array} \right

Где \omega - некий числовой параметр.

Метод Зейделя

Канонический вид метода Зейделя:

\left\{\begin{array}{rcl} B_{k+1} &=& D + A_1 ,\\ t_{k+1} &=& 1. \end{array} \right.

Преобразовав эти уранения приведём их к следющему виду:

 A_1 x^{k+1} + D x^{k+1} + A_2 x^k = f.

Отсюда полученная система будет выглядеть так:

\left\{\begin{array}{ccccccccccc}
{a_{11}}{x_1}^{k+1} &+& {a_{12}}{x_2}^{k} &+& {\ldots} &+& &+& {a_{1n}}{x_n}^{k} &=& f_1 \\
{a_{21}}{x_1}^{k+1} &+& {a_{22}}{x_2}^{k+1} &+& {\ldots} &+& &+& {a_{2n}}{x_n}^{k} &=& f_2 \\
\ldots & & & & & & & & & & \\
{a_{n1}}{x_1}^{k+1} &+& {a_{n2}}{x_2}^{k+1} &+& {\ldots} &+& &+& {a_{nn}}{x_n}^{k+1} &=& f_n
\end{array}\right.,

Выразим из этой системы новое итерационное приближение:

\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{f_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.

Условие сходимости и оценка погрешности метода

Имеет место следующая теорема. Пусть

\left\{\begin{array}{rcl} B_{k+1} &=& D + \omega A_1 ,\\ t_{k+1} &=& \omega, \end{array} \right

где A - симметрическая положительно определенная матрица и \omega \in [0,2]. Тогда метод релаксации является сходящимся для любого начального приближения.

Если для погрешности итерационного метода справедливо неравенство:  || x^k - x || \leq q^k || x^0 - x || , где  q \in (0,1), то метод сходится со скоростью геометрической прогресии.

Справедлива теорема (оценка погрешности одношаговых итерационных методов). Пусть матрицы A и B симметричны и положительно определены и существуют такие положительные константы \gamma _1 и \gamma _2, что \gamma _1 B \leq A \leq \gamma _2 B. Тогда итерационный метод, задаваемый уранением B_{k+1}\,\frac{x^{k+1} - x^k}{t^{k+1}} +Ax^k = f, где  t = \frac{2}{\gamma _1 + \gamma _2} сходится для любого начального приближения со скоростью геометрической прогресии с коэффициентом q, где  q = \frac{1-\xi}{1+\xi} , \xi = \frac{\gamma _1}{\gamma _2}.

Реализация методов

Метод Зейделя

Функция на языке Си, считающая следующую итерацию по методу Зейделя:

// n - число уравнений
// x_pr - предыдущее приближение, массив из n элементов
// x_next - текущее приближение, массив из n элементов
// matrix - матрица A
// d - вектор f
void next_iteration_z(double *x_pr, double *x_next, int n, double *matrix, double *d){
	int i,j;
	double s1,s2;
	for(i=0;i<n;i++){
		s1=0;
		s2=0;
		for (j=0;j<i;j++){
			c[n*i+j]=-matrix[n*i+j]/matrix[n*i+i];
			s1=s1+c[n*i+j]*x_next[j];
		}
		for (j=i+1;j<n;j++){
			c[n*i+j]=-matrix[n*i+j]/matrix[n*i+i];
			s2=s2+c[n*i+j]*x_pr[j];
		}
		d[i]=f[i]/matrix[n*i+i];
		x_next[i]=s1+s2+d[i];
	}	
}

Метод релаксации

Функция на языке Си, считающая следующую итерацию по методу Релаксации:

// n - число уравнений
// x_pr - предыдущее приближение, массив из n элементов
// x_next - текущее приближение, массив из n элементов
// matrix - матрица A
// d - вектор f
// om - параметр ω
void next_iteration_z(double *x_pr, double *x_next, int n, double *matrix, double *d, double om){
	int i,j;
	double s1,s2;
	for(i=0;i<n;i++){
		s1=0;
		s2=0;
		for (j=0;j<i;j++){
			c[n*i+j]=-matrix[n*i+j]*om/matrix[n*i+i];
			s1=s1+c[n*i+j]*x_next[j];
		}
		for (j=i+1;j<n;j++){
			c[n*i+j]=-matrix[n*i+j]*om/matrix[n*i+i];
			s2=s2+c[n*i+j]*x_pr[j];
		}
		d[i]=f[i]*om/matrix[n*i+i];
		x_next[i]=s1+s2+d[i]-x_pr[i]*(om-1);
	}	
}

Примеры работы

Для примера рассмотрим систему:

\left\{\begin{array}{сcссс} x &+& y &=& 3 ,\\ x &+& 3*y &=& 7 \end{array} \right

Точное решение, очевидно: (1, 2).

Тестирование проводилось при \epsilon = 0.0001, начальное приближение (0, 0). Условие остановки - поэлементная разница элементов следующего приближения и предыдущего не больше чем \epsilon.

Метод Зейделя

Решение: (1.00274, 1.99909) получено за 6 итераций

Метод релаксации (ω=0.5)

Решение: (1.002673, 1.98664) получено за 14 итераций

Метод релаксации (ω=1.5)

Решение: (0.995275, 1.99967) получено за 9 итераций

Погрешность методов

Выводы

Список литературы

См. также

Личные инструменты