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

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

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

Введение

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

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

Если , то соответствующий метод называется явным, в противном случае – неявным.

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

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

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

,

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

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

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

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

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

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

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

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

где

Таким образом -я компонента -го приближения вычисляется по формуле:

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

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

где - симметрическая положительно определенная матрица и . Тогда метод релаксации является сходящимся для любого начального приближения.

Если для погрешности итерационного метода справедливо неравенство: , где то метод сходится со скоростью геометрической прогресии.

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

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

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

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

// 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);
	}	
}

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

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

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

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

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

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

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

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

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

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

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

Выводы

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

См. также

• Практикум ММП ВМК, 4й курс, осень 2008
• Пример реализации