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

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

(Различия между версиями)
Перейти к: навигация, поиск
(Новая: == Введение == Релаксационные методы - частный случай итерационных методов решения СЛАУ. Итерационные ...)
Текущая версия (06:46, 30 октября 2008) (править) (отменить)
м (викификация)
 
(9 промежуточных версий не показаны.)
Строка 1: Строка 1:
 +
'''Релаксационные методы''' — частный случай итерационных методов решения СЛАУ. Итерационные методы являются особенно эффективными при решении систем с большим количеством неизвестных (порядка 1000 и более).
 +
== Введение ==
== Введение ==
-
Релаксационные методы - частный случай итерационных методов решения СЛАУ. Итерационные методы являются особенно эффективными при решении систем с большим количеством неизвестных (порядка 1000 и более).
+
В общем случае сначала задаётся некоторый вектор x<sup>0</sup>, называемый начальным приближением. В общем случае начальное приближение может быть любым. От него строится последовательность x<sup>1</sup>, x<sup>2</sup>,...,x<sup>k</sup> и так далее, где число k называют номером итерации.
-
Релаксационные методы являются неявными, стационарными итерационными методами.
+
Итерационный метод назвается одношаговым, если каждое последующее итерационное приближение строится только по одному предыдущему:
-
В общем случае сначала задаётся некоторый вектор 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>x^{k+1} = F_{k+1} (x^k)</tex>
-
От последовательности, естественно, ожидается сходимость к вектору х, который будет являться решением исходной системы.
+
Если <tex>F</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}
 +
{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.,</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{f_i}{a_{ii}},\quad i=1,\ldots,n.</tex>
 +
 
 +
Таким образом <tex>i</tex>-я компонента <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) ===
=== Метод релаксации (ω=0.5) ===
 +
 +
Решение: (1.002673, 1.98664) получено за 14 итераций
 +
=== Метод релаксации (ω=1.5) ===
=== Метод релаксации (ω=1.5) ===
 +
 +
Решение: (0.995275, 1.99967) получено за 9 итераций
 +
== Погрешность методов ==
== Погрешность методов ==
== Выводы ==
== Выводы ==
== Список литературы ==
== Список литературы ==
 +
 +
== См. также ==
 +
* [[Практикум ММП ВМК, 4й курс, осень 2008]]
 +
* [http://www.machinelearning.ru/wiki/images/d/d0/Lastone.zip Пример реализации]
 +
 +
{{Заготовка}}
 +
 +
[[Категория:Учебные задачи]]

Текущая версия

Релаксационные методы — частный случай итерационных методов решения СЛАУ. Итерационные методы являются особенно эффективными при решении систем с большим количеством неизвестных (порядка 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 итераций

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

Выводы

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

См. также

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