Инструменты сайта


§

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


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

§

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

Пусть $ 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 $.

Обобщения

Целые числа

Задача. Для заданного натурального числа $ B_{} $ установить является ли оно полным квадратом и в этом случае определить $ \sqrt{B} $.

Т

Теорема. Пусть $ B_0 $ — произвольное целое такое, что $ B_0^2>B $. Последовательность

$$ B_j = \begin{array}{c} \left\lfloor \begin{array}{c} B_{j-1}+ \left\lfloor \displaystyle \frac{B}{B_{j-1}} \right\rfloor_{} \\ \hline 2 \end{array} \right\rfloor \\ \end{array} \quad npu \ \ j\in \{1,2,\dots \ \} \ , $$ монотонно убывая, сойдется за конечное число шагов к значению $ \left\lfloor\sqrt{B} \right\rfloor $, если только число $ B+1 $ не является полным квадратом. Здесь $ \lfloor \ \ \ \rfloor $ означает целую часть числа.

Доказательство ЗДЕСЬ.

Комплексные числа

Формально ничто не мешает нам применить последовательность метода Ньютона для поиска мнимых корней полинома $ 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)
Оригинал первого рисунка ЗДЕСЬ, второй рисунок предоставлен Д.В.Абрамовым.
polynomial/newton.txt · Последние изменения: 2020/10/29 00:06 — au