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

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

1. Упрощенный метод Ньютона.

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

Геометрическая иллюстрация метода приведена на рис. 4.11. В точке к графику функции проводится касательная и за приближение принимается абсцисса точки пересечения этой касательной с осью (как в методе Ньютона). Каждое следующее приближение получается здесь как абсцисса точки пересечения с осью прямой, проходящей через точку с координатами и параллельной касательной

Рис. 4.11.

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

Метод (4.46) можно рассматривать как метод простой итерации с итерационной функцией Так как то для знаменателя соответствующей геометрической прогрессии имеем Следовательно, скорость сходимости тем выше, чем ближе начальное приближение к решению х.

2. Метод ложного положения.

В основе этой и следующих двух модификаций метода Ньютона лежит приближенное равенство

Оно верно при условии и следует из определения производной:

Пусть с — фиксированная точка, расположенная в окрестности простого корня х. Заменим в расчетной формуле метода Ньютона (4.37) производную правой частью приближенного равенства (4.47), полагая . В результате придем к расчетной формуле метода ложного положения:

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

Рис. 4.12

Рис. 4.13

Метод (4.48) обладает только линейной сходимостью. Его можно рассматривать как метод простой итерации с итерационной функцией Так как скорость сходимости определяется вблизи корня величиной то она тем выше, чем ближе окажется выбранная точка с к х.

3. Метод секущих.

Замена в формуле метода Ньютона производной приближением приводит к расчетной формуле метода секущих:

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

На рис. 4.13 приведена геометрическая иллюстрация метода. Очередное приближение получается здесь как абсцисса точек пересечения с осью секущей, соединяющей точки графика функции с координатами

Примечательно то, что эта модификация метода Ньютона сохраняет свойство сверхлинейной сходимости, если вычисляется простой корень

х. Точнее, верно следующее утверждение.

Теорема 4.9. Пусть простой корень уравнения в некоторой окрестности которого функция дважды непрерывно дифференцируема, причем Тогда существует -окрестностъ корня х такая, что при произвольном выборе приближений из этой -окрестности метод секущих сходится с порядком справедлива оценка

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

К сожалению, метод обладает, вообще говоря, только локальной сходимостью. Он требует выбора двух близких к (в общем случае — очень близких) начальных приближений Если эти приближения выбраны неудачно, то метод расходится (рис. 4.14).

Рис. 4.14.

4. Метод Стеффопсена.

Итерационная формула метода Стеффенсена имеет вид

Можно считать, что она получена в результате замены производной входящей в расчетную формулу метода Ньютона, приближением (4.47), где

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

Геометрическая иллюстрация метода Стеффенсена приведена на рис. 4.15. Приближение получается как абсцисса точки пересечения с осью секущей, проходящей через точки с координатами Значение отвечает абсциссе точки пересечения с осью прямой проходящей через точку и параллельной прямой

Рис. 4.15

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

5. Уточнение метода Ньютона для случая кратного корня.

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

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

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

На рис. 4.16, а, б проиллюстрировано поведение последовательных приближений стандартного метода Ньютона и его модификации (4.51) для случая отыскания корня кратности

Рис. 4.16

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

Пример 4.10. Применим методы, рассмотренные в данной главе, для вычисления положительного корня уравнения считая известным, что (см. пример 4.2).

Результаты вычислений приведены в табл. 4.5-4.8. В них для каждого приближения дается число верных знаков и требуемое число вычислений

значений функции упрощенного метода Ньютона учтено вычисление Вычисления выполнены с 10 знаками мантиссы.

Отметим, что выбор начальных приближений был довольно случайным (хотя и разумным). Тем не менее лучший результат показал метод секущих. Решение с 10 верными знаками мантиссы было получено после 5 итераций и для этого потребовалось лишь 6 вычислений функции. Хотя метод Ньютона (см. пример 4.8) при том же начальном приближении дает такое же значение х всего после 4 итераций, для этого требуется 8 вычислений функции (4 вычисления и 4 вычисления

Пример 4.11. Применим метод Ньютона и его модификацию (4.51) для вычисления корня кратности для уравнения Возьмем Результаты вычислений даны в табл. 4.9 и 4.10.

Как видно из табл. 4.9, погрешность метода Ньютона убывает довольно медленно и соответствует примерно геометрической прогрессии со знаменателем . В то же время 5 итераций по формуле (4.51) при дают значение решения с погрешностью, меньшей

Таблица 4.5 (см. скан) Упрощенный метод Ньютона;

Таблица 4.6 (см. скан) Метод ложного положения;

Таблица 4.7 (см. скан) Метод секущих;

Таблица 4.8 (см. скан) Метод Стеффенсена;

Таблица 4.9 (см. скан) Метод Ньютона

Таблица 4.10 (см. скан) Уточнение метода Ньютона для случая

6. Чувствительность к погрешностям.

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

диться в хорошей обусловленности модифицированного метода Ньютона и метода ложного положения.

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

Тем не менее при грамотном использовании метод секущих дает возможность получить почти столько же верных значащих цифр корня I, сколько вообще позволяет обусловленность задачи (см. § 4.2). Возможная (но не обязательная) потеря точности составляет 1—2 верные цифры. Необходимо лишь прервать итерационный процесс в тот момент, когда приближения окажутся в опасной близости к интервалу неопределенности. Один из способов заметить этот момент состоит в использовании правила Гарвика (см. § 4.2).

Отметим, что при попадании очередного приближения в малую окрестность решения теряет устойчивость и метод Стеффенсена.