Использование квадратичной интерполяции для ускорения сходимости непрерывного аналога метода Ньютона

При решении широкого круга вычислительных задач в различных областях науки и техники возникает потребность численного решения уравнений одного или нескольких переменных, в частности при использовании неявных разностных схем для решения обыкновенных дифференциальных уравнений и уравнений в частных производных, интегральных и других, как правило, нелинейных уравнений. Использование традиционных итерационных методов часто является малоэффективным из-за довольно большого количества итераций, что неминуемо приводит к значительному увеличению времени вычислений. Вопрос о построении эффективных алгоритмов решения нелинейных уравнений остается актуальным в вычислительной математике и ее приложениях, в частности математическом моделировании, например, при моделировании методом молекулярной динамики, где на каждом временном шаге необходимо решать от 10³ до 10⁷-10¹⁰ дифференциальных уравнений. В этом случае цена даже одной итерации при решении одного уравнения возрастает в миллионы раз [1] . Одним из эффективных итерационных методов решения нелинейных уравнений является метод Ньютона и различные его модификации в том числе на основе НАМН.

В данной работе проанализированы итерационные численные схемы, основанные на методе Ньютона. Проведено сравнение различных численных методов ньютоновского типа. Исследовано влияние итерационного параметра в непрерывном аналоге метода Ньютона на область и скорость сходимости. Предложен подход к оптимизации процесса сходимости непрерывного аналога метода Ньютона (НАМН). На основании данного подхода разработан механизм управления скоростью сходимости непрерывного аналога метода Ньютона с использованием в качестве управляющего параметра коэффициента изменения шага разностной схемы для численного решения дифференциального уравнения НАМН. На основе разработанного механизма управления процессом сходимости была предложена модификация непрерывного аналога метода Ньютона.

Метод Ньютона для решения нелинейных уравнений

При необходимости численного решения нелинейного уравнения:

f(x) = 0.                                              (1)

определяется участок [ a, b ] где, согласно теореме Канторовича [2], должны выполняться условия:

Гт

< В;

F(x)

F'(x)

< A;

3F''(%) G [a,b],|F''(x)|

la-bl <-^(1-V1-2ABC).

AB

Если условия (2) выполнены, тогда на отрезке [a, b] существует единственный корень уравнения (1), который может быть найден итерационным методом Ньютона:

f⁽Xi1)

x_t = X_t-1 - ^,₍^^^,i = 1,2,3, ™,H.

Значительный недостаток метода Ньютона - это крайне малая область [a, b] из-за этого необходимо х₀подбирать достаточно близко к корню уравнения х*, иначе, возможна расходимость метода. Для решения проблемы сходимости метода Ньютона на, в достаточной степени, произвольном отрезке [а, 6] авторы предлагают ввести условие, в случае выполнения которого, применяется алгоритм, обеспечивающий сходимость, близкую к теоретической.

Теорема 1. Пусть на отрезке [а, 6] существует точное решение х* уравнения (1) и при решении данного уравнения итерационным методом Ньютона для некоторого значения I выполняется условие:

< 0.                                               (4)

/(^i-i)

Тогда х* е [хг,хг-1] при этом |х, - хг-1| < |а - 6|.

Доказательство

В случае применения метода Ньютона необходимо выполнение условия:

.     /(х,-1)

1 °   |2|лх-1)|'

При невыполнении условия (5) следующая итерация /(%;) по методу (3) удовлетворяет условию:

/(х,) g [а,6].

Что значит расходимость метода Ньютона, поэтому для сходимости метода (3) необходимо выполне- ние условия:

[х,,х,-1] с [а,6].                                                        (7)

Из этого следует что |хг - хг-1| < |а - 6|, тогда, в соответствии с теоремой об отделении корней [3], если выполняется утверждение (7) и утверждение (4) то, следовательно, х* е [хг,хг-1]. Теорема дока- зана.

Зная границы области [х,,х,_-1], несложно найти условия для х такие что:

х,+1 е [х1,х1-1],

что исключит расходимость итерационного процесса.

Алгоритм решения уравнения до выполнения условия

/М

/⁽х,-1⁾

< 0.

В данном случае необходимо выполнение условия достаточно близкого расположения х₀к корню уравнения для успешной сходимости метода Ньютона на участке [a, b].

Для уменьшения величины расходимости используется метод, предложенный Гавуриным [4].

х,

^х,-1 ^-

^т,

_ f^(xi-1⁾

* —-----:

Г(х<-1)’

0 < т, < 1.

Преимущество, связанное с уменьшением области сходимости этого метода по сравнению с методом Ньютона, представлено в статье [5] и реализуется при условии применения алгоритма для поиска значения коэффициента:

Tt-1 * |/(xt-1)|

№)|  ■

Использование алгоритма (10) наиболее эффективно только при достаточно малых т₀, что приводит к очевидному уменьшению значения kt—1 - ^xt| по сравнению с методом Ньютона.

Теорема 2. Сходимость для метода (9), при использовании алгоритма (10) определения коэффициента

T , возможна только при выполнении условия:

I     то*|^(xо)|

lZ (^-la-W-kl

Доказательство

При C_i = C_i-i+ ^|x_i-i^-x_i-2^|, со = о.

В статье [5] упоминается зависимость:

Т, * |/(Хг)| = Т,+1 * |/(xi+i)| = Т,+2 * |/(xi+2)| = То * |/(Хо)|

Формулу (10) для расчёта значения Tt, можно представить в виде:

Tj-1 * |f(xi-i)| Т,-2 * |/(xi-2)| * |/(xi-i)|   То*|/(Хо)|

Т     |Ж)|

|f(xi-1)| * lf(xt)l

lf(xt)l   '

Если применить (13) для расчёта по методу (9), получим

_         Tо*|/(Хо)|   f(xt-i)

Хi=Хi-1     |f(xi-i)|  *f'(xi-i).

В соответствии с утверждением о том, что мы рассматриваем случай, где

/x о

/(xf-i)     '

можно сделать вывод о том, что при введении дополнительного условия, т₀* |/(%₀)| < |/(^xt)| будет выполнено ограничение 0 < Tt < 1.

Рассмотрим условия сходимости для метода (14):

|a — 6| —

To*|/(%o)[ kC^o)  .

Учитывая (15) очевидно, что условие (16) не гарантирует сходимость, поскольку

k - ^ - kJ — kt - Xt-J значение |a - 6| уменьшается на kt-1 - xt | после каждой итерации, участком сходимости метода (14) будет:

(|a - й| - |с,|) — T^*‘^(Х22!,                                                    (17)

|/ (^л при Ci = Ci-1 + K-1 -Xi-21, Co = 0.

Из (17) получается условие (11). Теорема доказана.

Условие (11) значит, что метод (10) сильно зависит от значения |/'(Xi)|, это доказывает необходимость алгоритма, учитывающего её поведение.

Для контроля сходимости метода (9) предлагается ввести управляющий коэффициент, рассчитывающийся в зависимости от поведения функции на предыдущих итерациях:

е, = *о — Оч»

-^тс^-

Значение 6i является решением уравнения прямой, проходящей через точки /(х₀) и f(Xi_-1) это позволяет использовать его для контроля значения |/'(Xi)| в случае её уменьшения, что приводит к выполнению условия (11). Это позволяет привести следующий алгоритм:

Ax, = xt—i - т,

f(xt-i) f'(xt-iY

У = | /(хо)*(хо 9i)  |, о < У < 2 ;

If(xt_1)*(xo-Axt) I x, = e.+yAxL^y.

Алгоритм (19) способен обеспечивать устойчивую сходимость при достаточно малом т₀ и применять его для расчёта Xi стоит только при условиях:

|f'(x,-i)| < |f'(x,-2)|;

|xf_i -Axf| > |xi_i - ej;

f(x_t-i) f(X_t-2)

> 0.

Очевидно уменьшение значения |Xi_-1 - xj по сравнению с (9), для этого алгоритма.

Алгоритм решения уравнения при условии

f(xt) f(xt-1)

< о

Согласно Теореме 1 для этого случая необходим алгоритм, при котором выполнялось бы условие (8). В таком случае справедливо неравенство:

|x, -xi—i| > |xi-xi+i|.

/Сч)

Подставив значение т |p^—y|

вместо |Xi - Xi₊₁| в неравенство (21) мы получим:

I I ^1 ^-^^Hx^

Из чего следует:

т <

kt-Xt-J

Wi-^riXi-o-iV

Очевидно, что выполнение условия (23) гарантирует выполнение условия (8) для значения %t₊₁. Однако для значений следующих итераций, получаемых по методу (9), необходимо задать параметр к, обозначающий такое %t—1, при котором последний раз выполнялось условие (4), и, в таком случае, выполнение условия:

т <

^|x_i - fc^| lr(x_i)r'(x_i)^-l|

гарантирует сходимость метода (9) на участке [х_п, к], где n - номер текущей итерации.

Применение метода Ньютона в случае выполнения условия (4) может столкнуться с такими проблемами, как зацикливание. В этом случае приближенное решение уравнения с заданной точностью не может быть получено, в принципе.

Теорема 3. При решении нелинейного уравнения (1) с помощью метода (9), при выполнении условия (4), показателем сходимости, является:

^|x_i - x*^| > ^|Xt-i -xj - а|х,-₂ - x^²;

О < а < го.

Доказательство

Согласно теореме Канторовича (2), сходимость метода (9) при условии (15) определяется неравенством :

|x_t - x*| < a|x_t-l - x*|².

Настолько высокая скорость сходимости возможна, потому что выполняется условие:

[x₁,X‘] c [Xj-i,X*].                                                    (27)

В этом случае очевидно, что в случае (15) для метода Ньютона будет верно равенство:

|x_t - x*| = |x_t - x_t-l| + |x_t-l - x*|.                                          (28)

И при достаточно большом значении

1ZC^il If'CxD

очевидно:

|x_i-i-X‘| « |x_i-x*|.                                            (29)

Согласно теореме 1 в случае применения метода (9) при условии (4):

x* e ^[x_i,x_i—i^].                                                          (30)

При этом %* ^ х^ и %*^%j_-1и это значит, что:

[X^X*] £ ^[Xt-i,X*^].

Из этого следует что погрешность приближенного решения %[ для алгоритма (9) при выполнении условия (4) можно выразить следующим образом:

Выпуск №3, 2019 год

|x, — x*| = |х_; -Xj-11 - ^|x_i_i -x*|.                                          (32)

Подставив (26) в (28) для значения |Xj_1 — х*| мы получим:

|x, — х*| < |х_; — x_;-1| + a|x_i-2 — x*|².                                         (33)

Аналогичным образом, использовав (26) для случая (32) мы получаем (25). Теорема доказана.

Выполнение неравенства (24) исключает расходимость метода (9) в случае (4) тем не менее, из-за небольшой скорости сходимости, выраженной неравенством (25), возможно выполнение условия |/| = |Xj₊₁|, в этом случае произойдёт зацикливание.

Настолько низкая скорость сходимости, возможна только при выполнении условия:

|x* — x_i+i| «

|x — x,|.

На основе выполнения условия (25) и недопущения (34) возникает необходимость ввести алгоритм расчёта параметра у, позволяющий контролировать размер величины | /< — Xj₊₁1 при выполнении условия ^^(к) > 0 особенно он необходим, когда (24) не выполняется.

№+1)

^x;+i = ^{x; —у}Жз^:

>■          °^./.;   •   ¹

Алгоритм (35) использует минимально возможное значение т для выполнения условия (24), умноженное на 0.8, данное значение было наиболее эффективным в ходе ряда тестовых расчётов.

Так же стоить отметить возможность применения метода интерполяции по трём точкам, для определения значения т. Коэффициенты квадратичной интерполяции вида ^(х) = ах2 + Ьх + с, вычисляются по следующим формулам:

((/(xQ-AmOtk-m^Cfto-ffm^Cri-m)) _

((xi²_m²)(k_m)_(k²_m²)(xi-m))    ^;

(/⁽k ) — /⁽Ф) — a⁽k² — m²⁾) ⁽k — m)

с = /(m) — (am2 + bm);

^x*i

X»2 =

b2+V4ac

= —;—;

2 a b2 — V4ac

2a .

Если /'(т) <0 и к< т < Xj или /' (т) > 0 и к > т > Xj, где т точка в которой ^(т) = 0 тогда т = х*1 иначе т = х*₂.

Алгоритм (35) обеспечивает лучшую сходимость при условии (4) по сравнению с методом (9) из-за особенностей поведения метода Ньютона при угрозе расходимости или зацикливания.

Примеры применения представленных алгоритмов

Алгоритм (19) обеспечивает лучшую сходимость в сравнении с методом (9) при малом значении производной на участке [a, b]. В таком случае коэффициент 9j находится в области сходимости алгоритма (9), и это позволяет уменьшить |Xj_₁— Xj | таким образом что Xj 6 [a, b].

f(^Xi) fCxt-t)

В случае

< 0 применение алгоритма (9) может привести к зацикливанию или расходимо- сти, на рисунке 2 приведён пример применения алгоритма (35), пунктирными линиями обозначены касательные проведённые с использованием алгоритма (9), применение алгоритма (35) гарантирует сходимость не более чем за 4 итерации.

X4=3.2705

Рис. 2. Применение алгоритма (35) для решения уравнения при условии

f(xQ f(^Xi-i)

< 0

Заключение

В данной статье был рассмотрен процесс решения нелинейных уравнений при помощи непрерывного аналога метода Ньютона, на основе проведённых исследований были предложены модификации, позволяющие улучшить характеристики сходимости НАМН при задании подходящих значений для коэффициентов управления итерационным процессом решения нелинейных уравнений.