Методы вычислений. Часть I. Численные методы алгебры. Курцева К.П - 59 стр.

Допустим, что для x * имеется начальное приближение x0 . В простейшем методе
итерации все дальнейшие приближения строятся по формуле
                                   xn+1 = ϕ ( xn ), n = 0,1,...                             (2)
       Этот процесс называется одношаговой итерацией.
       Геометрическое значение процесса вычислений xn указано на рисунке 1. По x0
находится на l точка M 0 [ x0 ,ϕ ( x0 )] , через нее проводится прямая параллельная оси х
и находится точка ее пересечения с биссектрисой. Абсцисса этой точки принимается за
следующее приближение x1 к x * и т.д.
       Рассмотрим поведение приближений xn , когда они находятся вблизи x * .
Для этого рассмотрим их погрешности            ε n = xn − x * . Зависимость между ε n и ε n+1
получится,    если     в    (2)   вместо      xn    и     xn+1      подставить   их   выражения
xn = x * +ε n , xn+1 = x * +ε n+1 :
    x * +ε n+1 = ϕ ( x * +ε n ) = ϕ ( x*) + ε nϕ ′( x*) + o(ε n )
       Если воспользоваться равенством x* = ϕ ( x*) и пренебречь малой величиной
более высокого порядка малости o(ε n ) , то зависимость между ε n и ε n+1 запишется в
виде приближенного равенства


       1. Когда ϕ ′( x*) > 1, погрешность           ε n+1 > ε n и приближение xn+1 будет
отстоять от x * дальше, чем xn . Решение x * будет “точкой отталкивания” для
приближений xn , близких к нему, и в этом случае не будет сходимости
последовательности xn к x * .
       2.    Если ϕ ′( x*) < 1 , то погрешность          ε n+1 < ε n и можно ожидать, что
последовательность xn , если x0 взято достаточно близким к x * , будет сходится к x *
приблизительно со скоростью геометрической прогрессии со знаменателем q = ϕ ′( x) .
       Приϕ ′ ( x *) > 0 ε n+1 и ε n будут иметь одинаковые знаки, и сходимость xn к
x * будет монотонной. Если ϕ ′ ( x *) < 0 , то погрешности ε n+1 и ε n имеют разные
знаки, и приближение xn будет сходиться к x * , колеблясь около x * .
       3. Случайϕ ′( x*) = 0 требует специального рассмотрения, так как тогда ε n+1
будет малой величиной высшего порядка сравнительно с ε n . Поэтому, если x0 взято
достаточно близким к x * , то xn будет весьма быстро сходится к x * : при возрастании
n погрешность         ε n будет стремиться к нулю со скоростью, превосходящей
сходимость геометрической прогрессии со сколь угодно малым знаменателем. Это
часто используют для ускорения сходимости последовательности xn к x * путем
преобразования заданного уравнения (1) к новому x = ψ ( x) , имеющему то же
решение x * , но такому, что ψ ′ ( x*) = 0
      Укажем порядок малости ε n+1 сравнительно с ε n . Пусть ϕ                           имеет
непрерывную производную порядка m вблизи x * , и выполняются равенства
                       ϕ ′( x*) = ... = ϕ ( m−1) ( x*) = 0 и ϕ ( m ) ( x*) ≠ 0
       В этом случае разложение ϕ ( xn ) = ϕ ( x * +ε n ) около x * будет иметь форму
                                                                                             59