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

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

(Различия между версиями)

Версия 09:39, 23 октября 2008

Содержание

1 Введение
2 Изложение метода
- 2.1 Метод Зейделя
- 2.2 Условие сходимости и оценка погрешности метода
3 Реализация методов
- 3.1 Метод Зейделя
- 3.2 Метод релаксации
4 Примеры работы
5 Погрешность методов
6 Выводы
7 Список литературы
8 См. также

Введение

Релаксационные методы - частный случай итерационных методов решения СЛАУ. Итерационные методы являются особенно эффективными при решении систем с большим количеством неизвестных (порядка 1000 и более). В общем случае сначала задаётся некоторый вектор x⁰, называемый начальным приближением. В общем случае начальное приближение может быть любым. От него строится последовательность x¹, x²,...,x^k и так далее, где число 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} {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.$

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

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

$\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 итераций

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

Выводы

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

См. также

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

Это незавершённая статья. Вы поможете проекту, исправив и дополнив её.

Источник — «http://machinelearning.ru/wiki/index.php?title=%D0%A0%D0%B5%D0%BB%D0%B0%D0%BA%D1%81%D0%B0%D1%86%D0%B8%D0%BE%D0%BD%D0%BD%D1%8B%D0%B5_%D0%BC%D0%B5%D1%82%D0%BE%D0%B4%D1%8B»

Категории: Незавершённые статьи | Учебные задачи

@@ Строка 61: / Строка 61: @@
 === Условие сходимости и оценка погрешности метода ===
-Имеет место следующая теорема:
+Имеет место следующая теорема. Пусть
-Пусть
-<tex>\left\{\begin{array}{rcl} B_{k+1} &=& D + \omega A_1 ,\\ t_{k+1} &=& \omega \end{array} \right </tex>,
+<tex>\left\{\begin{array}{rcl} B_{k+1} &=& D + \omega A_1 ,\\ t_{k+1} &=& \omega, \end{array} \right </tex>
-<tex>A</tex> - симметрическая положительно определенная матрица  и  <tex>\omega \in [0,2]</tex>, тогда метод релаксации является сходящимся для любого начального приближения.
+где <tex>A</tex> - симметрическая положительно определенная матрица  и  <tex>\omega \in [0,2]</tex>. Тогда метод релаксации является сходящимся для любого начального приближения.
 Если для погрешности итерационного метода справедливо неравенство:
-<tex> || x^k - x || \leq q^k || x^0 - x || </tex>, где <tex> q \in (0,1) </tex>,
+<tex> || x^k - x || \leq q^k || x^0 - x || </tex>, где <tex> q \in (0,1), </tex>
-То метод сходится со скоростью геометрической прогресии.
+то метод сходится со скоростью геометрической прогресии.
-Справедлива теорема (оценка погрешности одношаговых итерационных методов): Пусть матрицы <tex>A</tex> и <tex>B</tex> симметричны и положительно определены,  и существуют такие положительные константы <tex>\gamma _1</tex> и <tex>\gamma _2</tex>, что <tex>\gamma _1 B \leq A \leq \gamma _2 B</tex>.
+Справедлива теорема (оценка погрешности одношаговых итерационных методов). Пусть матрицы <tex>A</tex> и <tex>B</tex> симметричны и положительно определены  и существуют такие положительные константы <tex>\gamma _1</tex> и <tex>\gamma _2</tex>, что <tex>\gamma _1 B \leq A \leq \gamma _2 B</tex>.
 Тогда итерационный метод, задаваемый уранением
 <tex>B_{k+1}\,\frac{x^{k+1} - x^k}{t^{k+1}} +Ax^k = f</tex>, где <tex> t = \frac{2}{\gamma _1 + \gamma _2} </tex>
-Сходится для любого начального приближения со скоростью геометрической прогресии с коэффициентом <tex>q</tex>, где
+сходится для любого начального приближения со скоростью геометрической прогресии с коэффициентом <tex>q</tex>, где
 <tex> q = \frac{1-\xi}{1+\xi} </tex>, <tex>\xi = \frac{\gamma _1}{\gamma _2}</tex>.
 == Реализация методов ==

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

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

Версия 09:39, 23 октября 2008

Содержание

Введение

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

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

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

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

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

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

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

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

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

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

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

Выводы

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

См. также

Просмотры

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

Навигация

Поиск

Инструменты