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

Содержание

6.1. Метод простой итерации#

Задачу поиска корня \(f(x) = 0\) можно свести к поиску неподвижной точки.

Определение 6.3 (Задача поиска неподвижной точки)

Пусть дана функция \(g(x)\), тогда требуется найти её неподвижную точку \(x = p\)

\[ p: g(p) = p. \]

Например, в качестве \(g\) можно взять \(g(x) = f(x) + x\) или, в более общем случае, \(g(x) = c f(x) + x\), где \(c \neq 0\). Тогда получим

\[p = g(p) = c f(p) + p \implies f(p) = 0.\]

Алгоритм метода простой итерации (fixed point iteration) сводится к следующему. Пусть дано начальное приближение корня \(x_1\), тогда вычислим следующие приближения из рекуррентного соотношения

\[x_{k+1} = g(x_k), \quad k = 1, 2, ...\]
Функция 6.4 (fixedpoint)

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

"""
Ищет неподвижную точку функции `g`, начиная с `x₁`. Выполняет итерации до тех пор,
пока подшаг к ответу ≥ `xtol`, но не более `maxiter` раз.
"""
function fixedpoint(g, x₁; xtol=eps(), maxiter=25)
    x = float(x₁)
    for i in 1:maxiter
        xprev = x
        x = g(xprev)
        abs(x - xprev) < xtol && return x
    end
    error("Число итераций превышено.")
end

6.1.1. Сходимость#

Допустим, мы получаем серию приближений \(x_k\) неподвижной точки \(p\). Вместо серии \(x_k\) рассмотрим серию ошибок \(\epsilon_k = x_k - p\), тогда в окрестности \(p\) получим

\[\epsilon_{k+1} + p = g(\epsilon_k + p) = g(p) + g'(p)\epsilon_k + O(\epsilon_k^2).\]

Отсюда, поскольку \(g(p) = p\)

(6.1)#\[\epsilon_{k+1} = g'(p)\epsilon_k + O(\epsilon_k^2).\]

Или \(\epsilon_{k+1} \approx g'(p)\epsilon_k\). Значит, ошибка может как расти (метод не сходится), так и убывать (метод сходится). Поэтому имеет место

Утверждение 6.5 (Сходимость метода простой итерации)

Метод простой итерации для дифференциируемой \(g\) может сойтись к неподвижной точке \(p\) при условии \(|g'(p)| < 1\).

Кроме того, из (6.1) видно, что отношение \(\epsilon_{k+1} / \epsilon_k\) стремится к константе \(\sigma = g'(p)\). Такой вид сходимости распространён в задачах оптимизации и решения нелинейных уравнений. Для него введено определение.

Определение 6.6 (Линейная сходимость)

Пусть последовательность приближений \(x_k\) сходится к \(x^*\). Если при этом для ошибки \(\epsilon_k = x_k - x^*\) верно

\[ \lim_{k\to \infty}\frac{|\epsilon_{k+1}|}{|\epsilon_k|} = \sigma < 1, \]

то говорят, что последовательность обладает линейной сходимостью. А число \(\sigma\) называют скоростью сходимости.

Из-за особенностей сходимости метод простой итерации применяется не часто. Однако в задачах, для которых выполняется условие сходимости (хотя бы постфактум), метод является дешёвым способом получить грубое решение задачи. Метод активно применяется в NPT расчётах фазового равновесия и некоторых разностных схемах.

Демонстрация 6.7 (Метод простой итерации)

Пусть необходимо найти корни полинома \(f(x) = -x^2 + x\). Возьмём тогда \(g(x) = f(x) + x\).

Если взять начальное приближение \(x_1 \in (0, 2)\), то метод сойдётся к точке \(x=1\).

g = (x) -> -x*(x-1) + x
@show fixedpoint(g, 1.9) fixedpoint(g, 0.1);

fixedpoint(g, 1.9) = 1.0
fixedpoint(g, 0.1) = 1.0

Этот случай предсказывается ограничением на производную \(g'(x) = -2x + 2\) в неподвижной точке \(g'(1) = 0\).

А вот для корня \(x = 0\) тогда ожидать сходимости не стоит, поскольку \(g'(0) = 2\).

fixedpoint(g, -0.1; maxiter=100)

Число итераций превышено.

Stacktrace:
 [1] error(s::String)
   @ Base ./error.jl:35
 [2] fixedpoint(g::var"#47#48", x₁::Float64; xtol::Float64, maxiter::Int64)
   @ Main ~/book/src.jl:272
 [3] top-level scope
   @ In[3]:1

Однако, можно взять другую функцию \(g_1(x) = -f(x) + x\), для неё уже \(g_1'(0) = 2x|_0 = 0\)

g1 = (x) -> -(-x*(x-1)) + x
@show fixedpoint(g1, -0.1);

fixedpoint(g1, -0.1) = 1.232595164407831e-32

Аналогично приходится поступать и для более «интересной» функции \(f(x) = xe^x - 2\), здесь \(g(x) = -0.25 f(x) + x\)

f = (x) -> x * exp(x) - 2
g = (x) -> -0.25 * f(x) + x
root = fixedpoint(g, 0.8)
@show root f(root);

root = 0.8526055020137255
f(root) = 0.0
Содержание