Метод простых итераций

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

(Различия между версиями)
Перейти к: навигация, поиск
Строка 51: Строка 51:
<center><tex> x_{k+2}-x_{*} \approx aq^{k+2}</tex> </center>
<center><tex> x_{k+2}-x_{*} \approx aq^{k+2}</tex> </center>
Где <tex> x_{k},x_{k+1},x_{k+2}</tex> нам известны (вычисленны по какому то линейному алгоритму),а <tex>a,q,x_*</tex> найдем из системы. Получим:
Где <tex> x_{k},x_{k+1},x_{k+2}</tex> нам известны (вычисленны по какому то линейному алгоритму),а <tex>a,q,x_*</tex> найдем из системы. Получим:
-
<center><tex> x_{*} \approx x_{k+2} - \frac{(x_{k+2}-x_{k+1})^2}{x_{k+2}-2x_{k+1}+x_{k}}</tex> </center>
+
<center><tex> x_{*} \approx x_{k+2} - \frac{(x_{k+2}-x_{k+1})^2}{x_{k+2}-2x_{k+1}+x_{k}}</tex> <tex>(1)</tex></center>
 +
Метод ускорения сходимости заключается в том, что после вычисления 3 приближений по линейно сходящемуся алгоритму, вычисляется новое приближение по уточняющему правилу (1)
==Метод Вегстейна==
==Метод Вегстейна==
== Числовые примеры ==
== Числовые примеры ==

Версия 12:10, 24 ноября 2008

Содержание

Постановка задачи

Пусть есть функция y = f(x).
Требуется найти корень этой функции, то есть x при котором f(x)=0
Решение необходимо найти численно, то есть для реализации на ЭВМ. Для решения этой задачи предлагается использовать метод простых итераций.

Метод простых итераций в общем виде

Заменеим исходное уравнение f(x)=0 на эквивалентное g(x)=x,и будем строить итерации по правилу x_{n+1} = g(x_n). Таким образом метод простой итерации - это одношаговый итерационный процесс. Для того, что бы начать данный процесс, необходимо знать начальное приближение x_0. Выясним условия сходимости метода.

Сходимость метода простых итераций

Метод сходится, если при k \to \infty последовательность {x_n} имеет предел.
Обозначим U_r(a) окресность точки a радиуса r, то есть U_r(a) = \{x:|x-a|<r\}.
Теорема. Если g(x) липшиц-непрерывна с константой q \in (0,1) на U_r(a), то есть выполняется

|g(x'')-g(x')|<q|x''-x'|,

при этом если также выполнено

|g(a)-a|<(1-q)r,
то уравнение x = g(x) имеет единственное решение на U_r(a) и метод простой итерации сходится к решению при любом выборе начального приближения x_1 \in U_r(a).Так же справедлива оценка:
|x_k-x_*|<q^k|x_0-x_*|,

где x_* - точное решение.

Из оценки видно, что метод линеен. Пусть g(x) непрерывно дифференцируема на U_r(a), тогда из теоремы вытекают следующие утверждения:
Следствие 1. Если |g'(x)| \le q < 1 для x \in U_r(a), выполнено |g(a)-a|<(1-q)r, и x_0 \in U_r(a), тогда уравнение x = g(x) имеет единственное решение на U_r(a) и метод простой итерации сходится к решению.

Следствие 2. Если уравнение x = g(x) имеет решение x_*, g(x) непрерывно дифференцируема на U_r(x_*) и |g'(x_*)|<1. Тогда существует \eps > 0 такое, что на U_{\eps}(x_*) уравнение не имеет других решений и метод простой итерации сходится к решению при x_0 \in U_{\eps}(x_*)

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

Так как для сходимости метода очень важен выбор функции g(x), ее обычно берут вида g(x)=x+s(x)f(x). Где s(x) не меняет знака на отрезке, на котором ищется корень функции.
Положим s(x) = c = const и рассмотрим метод в этом случае.
Тогда получим метод 'релаксации':

f(x_n) = \frac{x_{n+1}-x_{n}}{c},

для которого g'(x) = 1+cf'(x), и метод сходится при условии

-2<cf'(x_*)<0,

Пусть в некоторой окресности корня выполняются условия

f'(x)<0, 0<m_1<|f'(x)|<M_1,

Тогда метод релаксации сходится при c \in (0,\frac{2}{M_1}).

Выбор параметра

Оценим погрешность метода релаксации z_k=x_k-x_*

f(x_*+z_n) = \frac{z_{n+1}-z_{n}}{c},

Применяя теорему о среднем получаем

f'(x_*+{\theta}z_n)z_n = \frac{z_{n+1}-z_{n}}{c},

Отсюда

|z_{n+1}|\le|1+cf'(x_*+{\theta}z_n)||z_n|\le max|1+cf'(x_*+oz_n)||z_n|,

Следовательно

|z_{n+1}|\le max\{|1-cM_1|,|1-cm_1|\}|z_n|,

Таким образом задача сводится к нахождению минимума функции F(c)

F(c) = max\{|1-cM_1|,|1-cm_1|\},

Из рассмотрения графика функции видно, что точка минимума определяется

|1-cM_1| = |1-cm_1| при c\ne 0 ,

и равна

c = \frac{2}{M_1+m_1}

Ускорение сходимости

Как следует из Теоремы, метод простых итераций линеен, то есть

x_n-x_* \approx aq^n

Воспользуемся этим для оценки погрешности на каждой итерации. Запомним 3 последние итерации и выпишем их оценки:

 x_{k}-x_{*} \approx aq^{k}
 x_{k+1}-x_{*} \approx aq^{k+1}
 x_{k+2}-x_{*} \approx aq^{k+2}

Где  x_{k},x_{k+1},x_{k+2} нам известны (вычисленны по какому то линейному алгоритму),а a,q,x_* найдем из системы. Получим:

 x_{*} \approx x_{k+2} - \frac{(x_{k+2}-x_{k+1})^2}{x_{k+2}-2x_{k+1}+x_{k}} (1)

Метод ускорения сходимости заключается в том, что после вычисления 3 приближений по линейно сходящемуся алгоритму, вычисляется новое приближение по уточняющему правилу (1)

Метод Вегстейна

Числовые примеры

Рекомендации программисту

Заключение

Ссылки

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

  • А.А.Самарский, А.В.Гулин. Численные методы. Москва «Наука», 1989.
  • Н.Н.Калиткин. Численные методы. Москва «Наука», 1978.
Личные инструменты