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

Если известно достаточно хорошее начальное приближение к решению системы уравнений

то эффективным методом повышения точности является метод Ньютона.

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

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

Рассмотрим случай скалярного уравнения . В качестве такой вспомогательной задачи естественно взять линейную задачу

Ее решение принимается за следующее приближение к решению исходного уравнения, т.е. итерации ведутся по формуле

Рассмотрим более общий случай — решение нелинейного функционального уравнения.

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

Линейный оператор Р, действующий из пространства Н в пространство Y, назовем производной оператора в точке , если

В дальнейшем будем обозначать такой оператор Р через . Пусть, например,

Если функции непрерывно дифференцируемы в окрестности данной точки , то

Совокупность этих соотношений можно переписать в виде (2), если за Р принять оператор умножения слева на матрицу

В простейшем случае оператор Р превращается в оператор умножения на производную .

Пусть X — решение уравнения — некоторое приближение к X. В предположении существования производной , согласно (2), имеем

Если величина мала, то можно написать приближенное равенство

Поскольку , то

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

если такое решение существует. Между прочим, последнее уравнение имеет вид (1.11). В предположении, что оператор обратим, это решение можно записать в виде

Такой итерационный процесс называют методом Ньютона.

Пусть . Пусть при некоторых , выполнены условия:

при Обозначим

Теорема (о сходимости метода Ньютона). При условиях (5), (6) и итерационный процесс Ньютона (4) сходится с оценкой погрешности

Примечание. Если в рассматривавшемся выше примере в некоторой окрестности решения функции имеют ограниченные вторые производные, то, согласно формуле Тейлора, имеем

и, таким образом, условие (2) выполнено.

Доказательство. Пусть . Индукцией по докажем, что все . Пусть это утверждение доказано при некотором так как , то тогда . Подставив в и , получим

Поскольку , то это соотношение может быть переписано в виде

Воспользовавшись (5), получаем неравенство

Отсюда следует, что

поэтому также принадлежит . Таким образом, при все принадлежат и, следовательно, для них выполняется (8).

Пусть . После умножения на неравенство (8) запишется в виде . Индукцией по докажем справедливость неравенства

При оно очевидно. Предположив его верным при , получаем

Таким образом, при всех . Это означает, что

Отсюда следует (7). Согласно определению и

и поэтому . Теорема доказана.

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

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

Рассмотрим геометрическую интерпретацию метода Ньютона в случае решения скалярного уравнения , когда расчетная формула (4) приобретает вид

Для получения геометрически надо найти абсциссу точки пересечения с осью касательной к кривой в точке (рис. 7.2.1). Уже в случае, когда — многочлен третьей степени, может случиться, что последовательность не сходится к корню при плохом начальном приближении.

Рис. 7.2.1

Рис. 7.2.2

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

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

Чтобы погрешность стала меньше , согласно этой оценке достаточно взять

В случае метода Ньютона правая часть (7) будет меньше , если

Таким образом, асимптотически, при метод Ньютона требует меньшего числа итераций.

Задача 1. Доказать, что для метода порядка, , при наличии достаточно хорошего начального приближения число итераций, требуемое для достижения точности , будет .

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

Рис. 7.2.3

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

Задача 2. Рассматривается алгоритм вычисления при полагается равным значению многочлена наилучшего равномерного приближения для на .

Убедиться в справедливости неравенства .

В случае решения одного скалярного уравнения наряду с методом Ньютона употребителен метод секущих.

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

Более эффективен способ, где за принимается абсцисса точки пересечения с осью прямой, проходящей через точки (рис. 7.2.5). Уравнение этой прямой

Из условия получаем

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

При решении системы уравнений

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

Пусть — уравнение плоскости, проходящей через точки

за следующее приближение принимаем решение системы уравнений

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

Рис. 7.2.4

Рис. 7.2.5

В последнее время появились более совершенные обобщения метода секущих.

Дело в том, что для этого метода при характерно «сплющивание» -мерного тетраэдра с вершинами в точках . Следствием этого является быстрое ухудшение обусловленности системы уравнений . В результате алгоритм вычисления становится неустойчивым к вычислительной погрешности и часто перестает сходиться.

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

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