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

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

(Различия между версиями)
Перейти к: навигация, поиск
Строка 11: Строка 11:
<center><tex>|g(x'')-g(x')|<q|x''-x'|</tex>,</center>
<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>
<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>
Пусть <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>
'''Следствие 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>
==Метод релаксации==
==Метод релаксации==

Версия 09:13, 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. Тогда существует ε>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}.

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

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

Заключение

Ссылки

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

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