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

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

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

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

Содержание

1 Постановка задачи
2 Метод простых итераций в общем виде
- 2.1 Сходимость метода простых итераций
3 Метод релаксации
4 Числовые примеры
5 Рекомендации программисту
6 Заключение
7 Ссылки
8 Список литературы

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

Пусть есть функция $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$ b и рассмотрим метод в этом случае.
Тогда получим $f(x_n) = \frac{x_{n+1}-x_{n}}{c}$ .

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

Заключение

Ссылки

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

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

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

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

Источник — «http://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»

Категория: Незавершённые статьи

@@ Строка 11: / Строка 11: @@
 <center><tex>|g(x'')-g(x')|<q|x''-x'|</tex>,</center>
 при этом если также выполнено
-<center><tex>|g(a)-a|<(1-q)r</tex>,</center>то уравнение <tex>x = g(x)</tex> имеет единственное решение на <tex>U_r(a)</tex> и метод простой итерации сходится к решению при любом выборе начального приближжения <tex>x_1 \in U_r(a)</tex>.Так же справедлива оценка:
+<center><tex>|g(a)-a|<(1-q)r</tex>,</center>то уравнение <tex>x = g(x)</tex> имеет единственное решение на <tex>U_r(a)</tex> и метод простой итерации сходится к решению при любом выборе начального приближения <tex>x_1 \in U_r(a)</tex>.Так же справедлива оценка:
 <center><tex>|x_k-x_*|<q^k|x_0-x_*|</tex>,</center>
-где <tex>x_*</tex> - точное решение.<br>
+где <tex>x_*</tex> - точное решение.<br><br>
 Пусть <tex>g(x)</tex> непрерывно дифференцируема на <tex>U_r(a)</tex>, тогда из теоремы вытекают следующие утверждения:<br>
-'''Следствие 1.''' Если <tex>|g'(x)| \le q < 1</tex> для <tex>x \in U_r(a)</tex>, выполнено <tex>|g(a)-a|<(1-q)r</tex>, и <tex>x_0 \in U_r(a)</tex>, тогда уравнение <tex>x = g(x)</tex> имеет единственное решение на <tex>U_r(a)</tex> и метод простой итерации сходится к решению.<br>
+'''Следствие 1.''' Если <tex>|g'(x)| \le q < 1</tex> для <tex>x \in U_r(a)</tex>, выполнено <tex>|g(a)-a|<(1-q)r</tex>, и <tex>x_0 \in U_r(a)</tex>, тогда уравнение <tex>x = g(x)</tex> имеет единственное решение на <tex>U_r(a)</tex> и метод простой итерации сходится к решению.<br><br>
 '''Следствие 2.''' Если уравнение <tex>x = g(x)</tex> имеет решение  <tex>x_*</tex>, <tex>g(x)</tex> непрерывно дифференцируема на <tex>U_r(x_*)</tex> и <tex>|g'(x_*)|<1</tex>. Тогда существует ε>0 такое, что на <tex>U_ε(x_*)</tex> уравнение не имеет других решений и метод простой итерации сходится к решению при <tex>x_0 \in U_ε(x_*)</tex><br>
 ==Метод релаксации==

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

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

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

Содержание

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

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

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

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

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

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

Заключение

Ссылки

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

Просмотры

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

Навигация

Поиск

Инструменты