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

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

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

Версия 09:15, 24 ноября 2008

Содержание

1 Постановка задачи
2 Метод простых итераций в общем виде
- 2.1 Сходимость метода простых итераций
3 Метод релаксации

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

Пусть есть функция $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$ . Тогда существует ε>0 такое, что на $U_ε(x_*)$ уравнение не имеет других решений и метод простой итерации сходится к решению при $x_0 \in U_ε(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}$ .
$\eps<\tex> == Числовые примеры == == Рекомендации программисту == == Заключение == == Ссылки == <ul><li> [[Практикум ММП ВМК, 4й курс, осень 2008|Практикум ММП ВМК, 4й курс, осень 2008]] </li></ul> == Список литературы == <ul><li> ''А.А.Самарский, А.В.Гулин.'' Численные методы. Москва «Наука», 1989. </li><li> ''Н.Н.Калиткин.'' Численные методы. Москва «Наука», 1978. </li></ul> {{stub}}$

Источник — «http://www.machinelearning.ru/wiki/index.php?title=%D0%9C%D0%B5%D1%82%D0%BE%D0%B4_%D0%BF%D1%80%D0%BE%D1%81%D1%82%D1%8B%D1%85_%D0%B8%D1%82%D0%B5%D1%80%D0%B0%D1%86%D0%B8%D0%B9»

@@ Строка 19: / Строка 19: @@
 ==Метод релаксации==
 Так как для сходимости метода очень важен выбор функции <tex>g(x)</tex>,  ее обычно берут вида <tex>g(x)=x+s(x)f(x)</tex>. Где <tex>s(x)</tex> не меняет знака на отрезке, на котором ищется корень функции.<br>
-Положим <tex>s(x) = c = const </tex> b и рассмотрим метод в этом случае.<br>
+Положим <tex>s(x) = c = const </tex> и рассмотрим метод в этом случае.<br>
-Тогда получим <tex>f(x_n) = \frac{x_{n+1}-x_{n}}{c}</tex>. <br>
+Тогда получим <tex>f(x_n) = \frac{x_{n+1}-x_{n}}{c}</tex>. <br><tex>\eps<\tex>
 == Числовые примеры ==

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

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

Версия 09:15, 24 ноября 2008

Содержание

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

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

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

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

Просмотры

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

Навигация

Поиск

Инструменты