УказательРазделыОбозначенияАвторО проекте


§

Вспомогательная страница к разделу ПОЛИНОМ ОДНОЙ ПЕРЕМЕННОЙ


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

§

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

Пусть f_{}(x) — полином с вещественными коэффициентами, \deg f \ge 2, и \lambda_{} его корень, лежащий на интервале ]a,b[. Пусть, кроме того, f^{\prime}(x)\ne 0 на указанном интервале, тогда \lambda_{} — единственный корень полинома на ]a,b[. При произвольном x_0 \in ]a,b[ выпишем формулу Тейлора

f(x)=f(x_0)+f'(x_0)(x-x_0)+\dots \ ,

ограничившись в ней двумя первыми слагаемыми. Вместо уравнения f_{}(x)=0 будем рассматривать его линейное приближение f(x_0)+f'(x_0)(x-x_0)=0. Утверждается, что достаточно часто (в смысле выбора точки x_{0}) решение этого уравнения, т.е. точка

x_1= x_{0}-\frac{f(x_{0})}{f'(x_{0})}

лежит ближе к (неизвестному нам заранее) значению корня \lambda_{}, чем точка x_{0}. Можно утверждать и большее: при подходящем выборе x_{0} итерационная последовательность

\left\{ x_j= x_{j-1}-\frac{f(x_{j-1})}{f'(x_{j-1})} \right\}_{j=1}^{\infty}

будет сходиться к \lambda_{} при j\to + \infty.

Т

Теорема 1. Если полином f_{}(x) не имеет кратных корней и последовательность \{x_j\}_{j=1}^{\infty} сходится к конечному пределу, то этот предел является корнем f_{}(x).

Доказательство. Пусть

\lim_{j\to + \infty} x_j = A ,

тогда и

\lim_{j\to + \infty} x_{j-1} = A .

По непрерывности f_{}(x) и f^{\prime}(x) будет выполнено

\lim_{j\to + \infty} f(x_{j-1})= f(A) \ , \quad \lim_{j\to + \infty} f^{\prime}(x_{j-1})= f^{\prime}(A) \ ,

и, по предположению, числа f(A) и f^{\prime}(A) не могут одновременно обращаться в нуль. Если бы число f^{\prime}(A) было равно нулю, то последовательность \{x_j\}_{j=1}^{\infty} была бы неограниченной, а у нее же, по предположению теоремы, существует конечный предел. Следовательно f^{\prime}(A)\ne 0. При переходе в равенстве

x_j= x_{j-1}-\frac{f(x_{j-1})}{f'(x_{j-1})}

к пределу при j\to + \infty, равенство должно сохраниться:

A= A- \frac{f(A)}{f'(A)} \quad \Rightarrow \quad \frac{f(A)}{f'(A)}=0 \quad \Rightarrow \quad f(A)=0 \ .

Наша задача теперь заключается в подборе такого стартового (начального) значения x_{0}, чтобы последовательность \{x_j\}_{j=1}^{\infty} сходилась к определенному корню полинома, например, лежащему на данном интервале [a,b]. Нам потребуется следующий результат из математического анализа.

Т

Теорема 2. Если функция F_{}(x) и ее производные F^{\prime}(x) и F^{\prime \prime}(x) непрерывны в ]a,b[, то для любых значений x_{} и x_{0} из этого интервала будет справедлива формула Тейлора с остаточным членом в форме Лагранжа:

F(x)\equiv F(x_0)+F^{\prime}(x_0)(x-x_0)+ \frac{F^{\prime \prime}(c)}{2!}(x-x_0)^2

где значение c_{} принадлежит интервалу ]x_0,x[ при x>x_0 или ]x,x_0[ при x<x_0.

Т

Теорема 3. Если для f(x)\in \mathbb R[x] на интервале ]a,b[ выполнены условия:

а) f(a)f(b)<0;

б) f^{\prime}(x) и f^{\prime \prime}(x) не имеют корней на ]a,b[;

то при любом выборе x_{0} таком, что

\operatorname{sign} f(x_0) = \operatorname{sign} f^{\prime \prime}(x)

последовательность \{x_j\}_{j=1}^{\infty} монотонно сходится к единственному корню полинома f_{}(x), лежащему на ]a,b[.

Доказательство. Существование корня \lambda \in ]a,b[ гарантировано теоремой Больцано; его единственность на рассматриваемом интервале является следствием предположения б) и теоремы Ролля.

Для определенности, будем предполагать f^{\prime}(x)>0 и f^{\prime \prime}(x)>0 на ]a,b[, иначе говоря, функция возрастает и выпукла вниз; согласно правилу выбора начальной точки x_{0} мы должны взять ее из условия f(x_0)>0, т.е. ближе к правому концу интервала. Имеем, следовательно x_0>\lambda. Докажем, что значение x_{1}, вычисляемое по формуле

x_1= x_{0}-\frac{f(x_{0})}{f'(x_{0})} \ ,

будет удовлетворять условиям \lambda < x_1 < x_0.

Правое из этих неравенств очевидно следует из формулы, определяющей x_{1}: из x_{0} вычитается положительная величина. Для доказательства неравенства x_{1} > \lambda запишем для f_{}(x) формулу Тейлора с остаточным членом в форме Лагранжа:

f(x)\equiv f(x_0)+f^{\prime}(x_0)(x-x_0)+ \frac{f^{\prime \prime}(c)}{2!}(x-x_0)^2 \ .

Подставим вместо x_{} значение корня \lambda_{}:

0=f(x_0)+f^{\prime}(x_0)(\lambda-x_0)+ \frac{f^{\prime \prime}(c)}{2!}(\lambda-x_0)^2 \ ,

перенесем первые два слагаемые в левую часть и поделим получившееся равенство на f^{\prime}(x_0):

\left(x_{0}-\frac{f(x_{0})}{f^{\prime}(x_{0})} \right) - \lambda = \frac{f^{\prime \prime}(c)}{2!\, f^{\prime}(x_{0})}(\lambda-x_0)^2 \ .

В левой части получили x_1 - \lambda. По предположению, f^{\prime \prime}(c)>0 и f^{\prime}(x_{0})>0, следовательно правая часть неотрицательна. Итак, x_1 > \lambda.

Совершенно аналогично доказывается, что \lambda < x_2 < x_1 и т.д. Последовательность \{x_j\}_{j=1}^{\infty} монотонно убывает и ограничена снизу. Такая последовательность всегда сходится, и ее предел должен принадлежать интервалу [\lambda, x_0]. По доказанному в теореме 1_{} она сходится к какому-то корню полинома f(x), но тогда она сходится именно к \lambda_{}, поскольку другого корня на [a,b] у полинома нет.

§

Геометрическая интерпретация метода Ньютона заключается в следующем. Для определенности предположим, что f^{\prime}(x)>0,\, f^{\prime \prime}(x)>0 на ]a,b[. Возьмем x_{0} ближе к правому концу указанного интервала, т.е. пусть f(x_0)>0. Проведем касательную к графику функции y=f(x) в точке (x_0,f(x_0)):

\frac{y-f(x_0)}{x-x_0}=f^{\prime}(x_0)

и найдем ее точку пересечения (x_1,y_1) с осью абсцисс.

Легко вычислить координаты этой точки:

y_1=0,\ x_1=x_0 - \frac{f(x_0)}{f^{\prime}(x_0)} \ ;

иначе говоря, x_{1} определяется как раз по формуле метода Ньютона. Из рисунка видно (а в теореме 3_{} строго доказывается), что точка x_{1} лежит ближе к неизвестному нам значению корня \lambda_{} полинома f_{}(x), чем точка x_{0}. Поэтому имеет смысл повторить процедуру: построить касательную к графику в точке (x_1,f(x_{1})), найти ее пересечение (x_{2},y_2) с осью абсцисс и т.д.

В конце концов, монотонно убывающая и ограниченная снизу последовательность точек x_0,x_1,x_2,\dots попадет в сколь угодно малую окрестность \lambda_{}. Эти геометрические соображения обосновывают и другое название метода Ньютона; он также называется методом касательных.

Выбор стартового значения ближе к правому концу интервала обеспечивает монотонное убывание последовательности \{x_j\}_{j=1}^{\infty} также в случае когда на этом интервале имеют место неравенства f^{\prime}(x)<0 и f^{\prime \prime}(x)<0; в двух же оставшихся случаях

f^{\prime}(x)<0,\, f^{\prime \prime}(x)>0 \quad u \quad f^{\prime}(x)>0,\, f^{\prime \prime}(x)<0

последовательность будет сходиться к \lambda_{}, монотонно возрастая, если выбрать x_{0} ближе к левому концу интервала.

П

Пример. Найти положительный корень полинома x^5-4\, x -2 с точностью до 0.001.

Решение. На основании правила знаков Декарта делаем вывод, что f_{}(x) имеет положительный корень и этот корень единствен. Далее, f(1)<0,f(2)>0 и, на основании теоремы Больцано, этот корень принадлежит интервалу ]1,2[. Далее,

f^{\prime}(x)=5\,x^4-4>0, f^{\prime \prime}(x)>0 \quad npu \quad x\in ]1,2[ ,

т.е. мы находимся точно в условиях случая, рассмотренного в доказательстве теоремы 3_{}. Запускаем итерационную последовательность, полагая x_0=2:

x_1 =x_0-\frac{x_0^5-4\, x_0 -2}{5\, x_0^4 -4}=\frac{65}{38} \approx 1.710526316 \ .

Далее, последовательное применение формулы метода Ньютона дает:

\begin{array}{lll} x_2 &= x_1- \displaystyle \frac{x_1^5-4\, x_1 -2}{5\, x_1^4 -4} =\frac{2399816418}{1537339039} &\approx 1.561019630 \ , \\ x_3 &= x_2- \displaystyle \frac{x_2^5-4\, x_2 -2}{5\, x_2^4 -4} & \approx 1.521115751 \ , \\ x_4 & & \approx 1.518522614 \ , \\ x_5 & & \approx 1.518512153 \ . \end{array}

Ответ. \lambda \approx 1.518.

Обобщения

Комплексная плоскость

Формально ничто не мешает нам применить последовательность метода Ньютона для поиска мнимых корней полинома f_{}(x). Можно доказать комплексный аналог теоремы 3_{} , а также показать сходимость итерационной последовательности к конкретному корню полинома при условии, что стартовое (начальное) значение выбирается достаточно близко к искомому корню. Интересно посмотреть на поведение последовательности уже для самых простых случаев. Пусть, например, f(z)=z^3-1, т.е. наша задача заключается в поиске трех корней кубических из 1_{}:

1,\quad -\frac{1}{2} + \mathbf i \frac{\sqrt{3}}{2}\ ,\quad -\frac{1}{2} - \mathbf i \frac{\sqrt{3}}{2} \ .

Комплексный вариант последовательности метода Ньютона:

\left\{z_j = \frac{2\,z_{j-1}^3+1}{3\,z_{j-1}^2} \right\}_{j=1}^{\infty}

при задании стартового значения z_{0} «выведет» нас при j\to \infty к какому-то значению корня. Итак, вся комплексная плоскость может быть поделена на три «области притяжения» каждого из корней. Раскрасим эти множества в разные цвета. Какова будет граница между этими областями? — Оказывается, эта граница имеет так называемую фрактальную структуру; и каждая граничная точка любой области является также граничной для двух других областей1).

.

Метод Галлея (касательных гипербол)

Сначала изложим геометрию метода. К графику функции y=f(x) строится гипербола вида

(x-\alpha)(y-\beta)=k \ ,

имеющая с графиком касание второго порядка в точке (x_0,f(x_0)), т.е. значения функции

y=\beta+\frac{k}{x-\alpha} \ ,

а также значения ее первой и второй производных в точке x_0 совпадают с соответствующими значениями функции f_{}(x). В качестве очередного приближения x_{1} к неизвестному корню \lambda_{} берется точка пересечения гиперболы с осью абсцисс.

\left\{x_j=x_{j-1}- \frac{f(x_{j-1})f^{\prime}(x_{j-1})}{\left[f^{\prime}(x_{j-1})\right]^2-\frac{1}{2}f(x_{j-1})f^{\prime \prime}(x_{j-1})} \right\}_{j=1}^{\infty} \ .
§

Эта же формула может быть формально получена применением формулы метода Ньютона к функции f(x)/\sqrt{\pm f^{\prime}(x)} (имеющей корни, совпадающие с корнями f_{}(x)).




Статья не закончена!







Задачи

Источники

Березин И.С., Жидков Н.П. Методы вычислений. Т.2. М.Физматгиз. 1960

1) Оригинал первого рисунка ЗДЕСЬ, второй рисунок предоставлен Д.В.Абрамовым.

2017/07/10 09:40 редактировал au