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

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

(Различия между версиями)
Перейти к: навигация, поиск
Строка 2: Строка 2:
Пусть есть функция <tex>y = f(x)</tex>.<br>
Пусть есть функция <tex>y = f(x)</tex>.<br>
Требуется найти корень этой функции, то есть <tex>x</tex> при котором <tex>f(x)=0</tex><br>
Требуется найти корень этой функции, то есть <tex>x</tex> при котором <tex>f(x)=0</tex><br>
-
Решение необходимо найти численно, то есть для реализации на ЭВМ. Для решения этой задачи предлагается использовать метод простых итераций и его обобщения.
+
Решение необходимо найти численно, то есть для реализации на ЭВМ. Для решения этой задачи предлагается использовать метод простых итераций.
== Метод простых итераций в общем виде ==
== Метод простых итераций в общем виде ==
-
Заменеим исходное уравнение <tex>f(x)=0</tex> на эквивалентное <tex>g(x)=x</tex>.<br>
+
Заменеим исходное уравнение <tex>f(x)=0</tex> на эквивалентное <tex>g(x)=x</tex>будем строить итерации по правилу <tex>x_{n+1} = g(x_n)</tex>. Таким образом метод простой итерации - это одношаговый итерационный процесс. Для того, что бы начать данный процесс, необходимо знать начальное приближение <tex>x_1</tex>. Выясним условия сходимости метода.
-
Итерации будем строить по правилу <tex>g(x_n)=x_{n+1}</tex><br>
+
-
Для сходимости метода очень важен выбор функции <tex>g(x)</tex>, поэтому ее обычно берут вида <tex>g(x)=x+s(x)f(x).</tex><br>
+
-
Где <tex>s(x)</tex> не меняет знака на отрезке, на котором ищется корень функции.<br>
+
-
Таким образом метод простой итерации - это одношаговый итерационны процесс.<br>
+
===Сходимость метода простых итераций===
===Сходимость метода простых итераций===
Метод сходится, если при <tex>k \to \infty </tex> последовательность {<tex>x_n</tex>} имеет предел.<br>
Метод сходится, если при <tex>k \to \infty </tex> последовательность {<tex>x_n</tex>} имеет предел.<br>
Строка 15: Строка 11:
===Метод релаксации===
===Метод релаксации===
 +
Так как для сходимости метода очень важен выбор функции <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> b и рассмотрим метод в этом случае.<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>

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

Содержание

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

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

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

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

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

Метод сходится, если при k \to \infty последовательность {x_n} имеет предел.
Обозначим U_r(a) окресность точки a радиуса r<tex>, то есть <tex>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).

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

Так как для сходимости метода очень важен выбор функции 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}.

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

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

Заключение

Ссылки

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

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