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

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

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

Версия 08:56, 22 октября 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)$

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

$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»

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

@@ Строка 1: / Строка 1: @@
 == Введение ==
 Релаксационные методы - частный случай итерационных методов решения СЛАУ. Итерационные методы являются особенно эффективными при решении систем с большим количеством неизвестных (порядка 1000 и более).
-Релаксационные методы являются неявными, стационарными итерационными методами.
 В общем случае сначала задаётся некоторый вектор x<sup>0</sup>, называемый начальным приближением. В общем случае начальное приближение может быть любым. От него строится последовательность x<sup>1</sup>, x<sup>2</sup>, ..., x<sup>k</sup> и так далее, где число k называют номером итерации.
-В случае релаксационных методов (k+1)-е приближение:
+Итерационный метод назвается одношаговым, если каждое последующее итерационное приближение строится только по одному предыдущему:
 <tex>x^{k+1} = F_{k+1} (x^k)</tex>
-От последовательности, естественно, ожидается сходимость к вектору х, который будет являться решением исходной системы.
+Если  - линейная функция, то соответствующий итерационный метод называется линейным.
+Согласно определению, можно получить каноническую форму записи одношагового итерационного метода:
+<tex>B_{k+1}\,\frac{x^{k+1} - x^k}{t^{k+1}} +Ax^k = f</tex>
+Если <tex> B_{k+1} = E </tex> , то соответствующий метод называется явным, в противном случае – неявным.
 == Изложение метода ==
+Релаксационные методы являются стационарными и неявными решения СЛАУ.
+Пусть нам требуется решить систему линейных алгебраических уравнений:
+<tex> Ax = f </tex>
+Представим матрицу <tex>A</tex> в виде суммы трёх матриц <tex>A_1</tex>, <tex>A_2</tex> и <tex>D</tex>:
+<tex> A = A_1 + D + A_2 </tex>,
+Где <tex> A_1 </tex> - нижнетреугольная, <tex> A_2 </tex> - верхнетреугольная, <tex> D </tex> - диагональная
+Каноническая форма релаксационного метода записывается следующим образом
+<tex>\left\{\begin{array}{rcl} B_{k+1} &=& D + \omega A_1 ,\\ t_{k+1} &=& \omega \end{array} \right </tex>
+Где <tex>\omega</tex> - некий числовой параметр.
 === Метод Зейделя ===
-=== Метод релаксации ===
+Канонический вид метода Зейделя:
+<tex>\left\{\begin{array}{rcl} B_{k+1} &=& D + A_1 ,\\ t_{k+1} &=& 1 \end{array} \right </tex>
+Преобразовав эти уранения приведём их к следющему виду:
+<tex> A_1 x^{k+1} + D x^{k+1} + A_2 x^k = f </tex>.
+Отсюда полученная система будет выглядеть так:
+Выразим из этой системы новое итерационное приближение:
+<tex>\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.,</tex>
+где <tex>c_{ij}=-\frac{a_{ij}}{a_{ii}},\quad d_i=\frac{b_i}{a_{ii}},\quad i=1,\ldots,n</tex>
+Таким образом i-тая компонента <tex>(k+1)</tex>-го приближения вычисляется по формуле:
+:<tex>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</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> || 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>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 = \frac{1-\xi}{1+\xi} </tex>, <tex>\xi = \frac{\gamma _1}{\gamma _2}</tex>.
 == Реализация методов ==
 === Метод Зейделя ===
+Функция на языке Си, считающая следующую итерацию по методу Зейделя:
+<source lang="C">
+// 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];
+	}
+}
+</source>
 === Метод релаксации ===
+Функция на языке Си, считающая следующую итерацию по методу Релаксации:
+<source lang="C">
+// 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);
+	}
+}
+</source>
 == Примеры работы ==
+Для примера рассмотрим систему:
+<tex>\left\{\begin{array}{сcссс} x &+& y &=& 3 ,\\ x &+& 3*y &=& 7 \end{array} \right </tex>
+Точное решение, очевидно: (1, 2).
+Тестирование проводилось при <tex>\epsilon = 0.0001</tex>, начальное приближение (0, 0).
+Условие остановки - поэлементная разница элементов следующего приближения и предыдущего не больше чем <tex>\epsilon</tex>.
 === Метод Зейделя ===
+Решение: (1.00274, 1.99909) получено за 6 итераций
 === Метод релаксации (ω=0.5) ===
+Решение: (1.002673, 1.98664) получено за 14 итераций
 === Метод релаксации (ω=1.5) ===
+Решение: (0.995275, 1.99967) получено за 9 итераций
 == Погрешность методов ==
 == Выводы ==
 == Список литературы ==
+== См. также ==
+* [[Практикум ММП ВМК, 4й курс, осень 2008]]
 {{Заготовка}}
 [[Категория:Учебные задачи]]

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

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

Версия 08:56, 22 октября 2008

Содержание

Введение

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

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

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

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

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

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

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

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

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

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

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

Выводы

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

См. также

Просмотры

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

Навигация

Поиск

Инструменты