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

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

(Различия между версиями)
Перейти к: навигация, поиск
Строка 15: Строка 15:
Тогда получим <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>U_r(a) = \{x:|x-a|<r\}</tex>, то есть окрестность с радисом <tex>r</tex>.<br>
Обозначим <tex>U_r(a) = \{x:|x-a|<r\}</tex>, то есть окрестность с радисом <tex>r</tex>.<br>
-
:'''Теорема.''' Если <tex>g(x)</tex> Липшиц непрерывна с константой <tex>q \in (0,1)</tex> на <tex>U_r(a)</tex>, то есть выполняется <tex>|g(x'')-g(x')|<q|x''-x'|</tex>. При этом если также выполнено <tex>|g(a)-a|<(1-q)r</tex>, то уравнение <tex>x = g(x)</tex> имеет решение на <tex>U_r(a)</tex> и метод простой итерации сходится к решению при любом выборе начального приближжения <tex>x_1 \in U_r(a)</tex>.<br>
+
:'''Теорема.''' Если <tex>g(x)</tex> Липшиц непрерывна с константой <tex>q \in (0,1)</tex> на <tex>U_r(a)</tex>,<br> то есть выполняется <tex>|g(x'')-g(x')|<q|x''-x'|</tex>. При этом если также выполнено <tex>|g(a)-a|<(1-q)r</tex>, то уравнение <tex>x = g(x)</tex> имеет решение на <tex>U_r(a)</tex> и метод простой итерации сходится к решению при любом выборе начального приближжения <tex>x_1 \in U_r(a)</tex>.<br>

Версия 08:11, 24 ноября 2008

Содержание

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

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

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

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

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

Метод сходится, если при k \to \infty последовательность {x_n} имеет предел.

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

Положим s(x) = c = const b и рассмотрим метод в этом случае.
Тогда получим f(x_n) = \frac{x_{n+1}-x_{n}}{c}.
Обозначим U_r(a) = \{x:|x-a|<r\}, то есть окрестность с радисом 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).


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

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

Заключение

Ссылки

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

  • А.А.Самарский, А.В.Гулин. Численные методы. Москва «Наука», 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»
Личные инструменты