5. Решение нелинейных уравнений. Метод Ньютона-Рафсона, метод хорд. Общая характеристика методов. Сходимость, скорость сходимости, устойчивость к вычислительным погрешностям

Метод хорд

 

Если известно, что корень уравнения

                                                                         (1)  

,  а функция  непрерывна на  и  имеет производные  и , которые сохраняют знак на, то для уточнения   можно использовать метод хорд  в приведенной ниже редакции.

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

  если  ,    (4)

и          если     (4а)

где 

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

 

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

 

Критерий остановки расчетов: .   Приближенным значением корня функции f(x) считают последнее вычисленное значение:    .

 

В общем случае метод хорд можно записать с помощью следующего соотношения:

              k = 0,1,2,..             (4b)

За начальный промежуток   принимают . После вычисления по формуле (4b) новый промежуток формируется на основании сравнения знака функции в точке    и   в точках .

 

Скорость сходимости линейная, при определенных условиях может быть сверхлинейной.

 

Метод Ньютона – Рафсона (метод касательных)

 

Пусть по-прежнему - корень уравнения

                                                             (1)  

и . Будем считать, что на  функция  имеет производные   и , причем  ,  а   сохраняет знак на . Если начальное приближение  взять так, чтобы было выполнено условие

                                         (5)

то последовательность , где

                 (6)    

будет монотонно сходиться к решению уравнения - точке . Геометрический смысл формулы (6) заключается в том, что на каждом шаге определяется - точка пересечения касательной к графику функции , проведенной в точке , с осью OX. На следующем шаге касательную строим в точке  и т.д.

x

 

Метод Ньютона сходится быстрее метода хорд, для него справедливо при указанных выше свойствах функции  f(x)  соотношение

2 ,

что соответствует так называемой квадратичной скорости сходимости. Этот метод не обладает свойством глобальной сходимости, при выборе  нужно следить за выполнением  условия (5). К недостаткам метода Ньютона - Рафсона следует отнести также необходимость вычисления на каждом шаге метода не только значения функции, но и ее производной, что на практике может существенно увеличить объем вычислений, требуемых для выполнения каждой итерации метода.

 

Модификации метода Ньютона

Для решения уравнения   в общем случае можно использовать следующие модификации метода Ньютона.

1). Метод Ньютона с регулировкой шага.

            (7)

Здесь  - константа, регулирующая длину шага. Если , то выполняется неполный ньютоновский шаг. Процесс может быть стационарным, если  не зависит от k. Регулировка длины шага позволяет обеспечить сходимость метода для достаточно произвольно выбранного значения .

2). Конечно-разностный метод  Ньютона – Рассела.

                    (8)

Здесь  - шаг конечно-разностной аппроксимации производной. Эта модификация лишена одного из недостатков  метода Ньютона – не нужно вычислять производную . Но нужно вычислять одно дополнительное значение функции на каждом шаге. При достаточно малых h скорость сходимости практически сохраняется.

 

Метод хорд и касательных

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

Если  , то расчеты ведут по формулам:

     (9)

Если   , то

      (10)

За начальный промежуток   принимают . В результате расчетов получаем последовательность вложенных промежутков , таких, что . В качестве критерия остановки расчетов может быть использовано выполнение неравенства: . Тогда приближенное решение считают равным   .