!!§!! Вспомогательная страница к разделу ☞ ((:polynomial ПОЛИНОМ ОДНОЙ ПЕРЕМЕННОЙ)) ---- ~~TOC~~ ==Метод Ньютона решения уравнения== Метод применяется для решения широкого класса уравнений, но в настоящем разделе мы будем излагать его только в применении к уравнению алгебраическому. Пусть $ f_{}(x) $ --- полином с вещественными коэффициентами, $ \deg f \ge 2 $, и $ \lambda $ обозначает его корень, лежащий на интервале $ ]a,b[ $. Пусть, кроме того, $ f^{\prime}(x)\ne 0 $ на указанном интервале, тогда $ \lambda_{} $ --- единственный корень полинома на $ ]a,b[ $. При произвольном $ x_0 \in ]a,b[ $ выпишем ((:polynomial#формула_тейлора формулу Тейлора)) $$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 $. Метод поиска вещественного решения уравнения $ f(x)=0 $ построением указанной последовательности известен как **метод Ньютона** или же (см. ☟ ((#geometricheskaja_interpretacijametod_kasatelnyx ПУНКТ))) как **метод каcательных**. !!И!! Биографические заметки о Ньютоне ☞ ((:biogr#njuton ЗДЕСЬ)). !!Т!! **Теорема 1.** //Если полином// $ f_{}(x) $ //не имеет ((:polynomial#основная_теорема_высшей_алгебры кратных корней)) и последовательность// $ \{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[ $ //при// $ x0 $ и $ 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] $ у полинома нет. ♦ !!=>!! При выполнении условий теоремы $3$ скорость сходимости последовательности метода Ньютона оценивается неравенством $$ |x_j-\lambda|\le \frac{M}{2m} |x_{j-1}-\lambda|^2 ; \quad \mbox{здесь} \quad m= \min_{x\in [a,b]} | f^{\prime}(x)|, M= \max_{x\in [a,b]} | f^{\prime \prime}(x)| \, . $$ !!П!! **Пример.** Найти положительный корень полинома $ x^5-4\, x -2 $ с точностью до $ 0.001 $. **Решение.** На основании ((:polynomial/descartes правила знаков Декарта)) делаем вывод, что $ 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^{\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) $ с осью абсцисс. {{ polynomial:newt_iter11.png |}} Легко вычислить координаты этой точки: $$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) $ с осью абсцисс и т.д. {{ polynomial:newt_iter12.png |}} В конце концов, монотонно убывающая и ограниченная снизу последовательность точек $ 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} $ ближе к левому концу интервала. ===Чувствительность корней== Если мы хотим найти приближенное значение корня полинома применением метода Ньютона, то мы должны предварительно дать оценку точности вычислений: сколько значащих цифр мы должны сохранять в промежуточных выкладках, чтобы гарантировать достоверность получаемых результатов? Это порождает более общую задачу оценки **чувствительности** корней, т.е. оценки их изменения при некотором возмущении коэффициентов полинома. Обсуждение этой задачи ☞ ((:polynomial/zero_local#chuvstvitelnost_kornej ЗДЕСЬ)). ==Развитие== Методу Ньютона можно дать интерпретацию, отличную от изложенной в пункте ((#geometricheskaja_interpretacijametod_kasatelnyx МЕТОД КАСАТЕЛЬНЫХ)). Если выполнены условия теоремы $ 3 $, то на интервале $ [a,b] $ существует ((:algebra2/dets/jacobian#zamena_peremennyx_i_obratnoe_otobrazhenie обратная функция)) к $ y=f(x) $, т.е. функция $ x=\varphi(y) $ такая что $$ f(\varphi(y)) \equiv y \quad \mbox{ или, эквивалентно } \quad \varphi(f(x)) \equiv x \, . $$ Если эту функцию удается построить, то поиск корня уравнения $ f(x)=0 $ на интервале $ [a,b] $ сведется к вычислению значения $ \varphi (0) $. Проблема состоит в том, что как правило, представить обратную функцию в виде конечной комбинации сравнительно простых функций не представляется возможным даже для полиномиальных $ f(x) $. Но, по крайней мере, для таких функций можно представить ((:algebra2/dets/jacobian#zamena_peremennyx_i_obratnoe_otobrazhenie обратную функцию в виде ряда Тейлора)) в окрестности некоторой точки $ x_0 \in [a,b] $: $$ \varphi(y)=x_0+ B_1(y-f(x_0))+B_2(y-f(x_0))^2+ \dots $$ при $$ B_1=\frac{1}{f^{\prime}(x_0)}\ , \ B_2 = - \frac{f^{\prime \prime}(x_0)}{2[f^{\prime}_x(x_0)]^3}\ , B_3=\frac{3\,[f^{\prime \prime}(x_0)]^2- f^{\prime}_x(x_0)f^{\prime \prime \prime}(x_0) }{6[f^{\prime}_x(x_0)]^5}\ , \ \dots $$ Бесконечного количества слагаемых мы не вычислим, но если ограничиться первыми двумя, то получим линейное приближение обратной функции $$ \varphi(y)\approx x_0+ \frac{1}{f^{\prime}(x_0)}(y-f(x_0)) \, $$ из которого получаем **приближение корня первого порядка** $$ \varphi(0) \approx x_0 - \frac{f(x_0)}{f^{\prime}(x_0)} \ , $$ т.е. в точности ((#metod_njutona_reshenija_uravnenija формулу первой итерации метода Ньютона)). Если взять три слагаемых разложения, то **приближение корня второго порядка** получается в виде $$ \varphi(0) \approx x_0 - \frac{f(x_0)}{f^{\prime}(x_0)} - \frac{f^2(x_0)f^{\prime \prime}(x_0)}{2[f^{\prime}(x_0)]^3} \ , $$ и т.д. Посчитаем итерации, задаваемые этой функцией, $$ \left\{ x_{j}= x_{j-1} - \frac{f(x_{j-1})}{f^{\prime}(x_{j-1})} - \frac{f^2(x_{j-1})f^{\prime \prime}(x_{j-1})}{2[f^{\prime}(x_{j-1})]^3} \right\}_{j=1}^{\infty} $$ необходимые для решения примера из пункта ((:polynomial/newton#metod_njutona_reshenija_uravnenija МЕТОД НЬЮТОНА)). !!П!! **Пример.** Найти корень полинома $ x^5-4\, x -2 $ на интервале $[1,2] $ с точностью до $ 0.001 $. **Решение.** При выборе $ x_0 =2 $ требуемая точность достигается за три итерации $$ x_1 = \frac{22255}{13718} \approx 1.622321, \ x_2\approx 1.521381, \ x_3 \approx 1.518512 \, . $$ По сравнению с пятью итерациями метода Ньютона --- существенный выигрыш. Проблема только в том, что каждая итерация теперь стоит **дороже**: она более сложна при вычислении. ===Метод Галлея (касательных гипербол) == Геометрическая идея, лежащая в основе метода Галлея[[**Галлей Эдмунд** (Halley Edmond, 1656-1742) --- английский астроном, геофизик, математик, метеоролог и демограф. Современник Ньютона и спонсор издания его знаменитой книги "Математические начала натуральной философии". Разработчик теории движения комет, и первая комета, подтвердившая его теорию, носит название "комета Галлея".]], обобщает идею метода касательных. К графику функции $ 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) $). {{ :polynomial:halley12c.png?600 |}} ==Обобщения== ===Целые числа== **Задача.** Для заданного натурального числа $ B_{} $ установить является ли оно полным квадратом и в этом случае определить $ \sqrt{B} $. Следующий результат получается "округлением" итераций метода Ньютона, примененного к уравнению $ x^2-B=0 $. !!Т!! **Теорема.** //Пусть// $ 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 $ //означает ((:algebra2:notations#целая_часть_числа целую часть числа))//. **Доказательство** ☞ ((:numtheory:issquare ЗДЕСЬ)). ===Комплексные числа== Формально ничто не мешает нам применить последовательность метода Ньютона для поиска __мнимых__ корней полинома $ f_{}(x) $. Можно доказать комплексный аналог теоремы $ 3_{} $ , а также показать сходимость итерационной последовательности к конкретному корню полинома при условии, что стартовое (начальное) значение выбирается достаточно близко к искомому корню. Интересно посмотреть на поведение последовательности уже для самых простых случаев. Пусть, например, $$ f(z)=z^3-1 \, , $$ т.е. наша задача заключается в поиске трех ((:complex_num#obschij_sluchaj корней кубических из)) $ 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 $ к какому-то значению корня. Итак, вся комплексная плоскость может быть поделена на три "области притяжения" каждого из корней. Раскрасим эти множества в разные цвета. Какова будет граница между этими областями? --- Оказывается, эта граница имеет так называемую ((http://en.wikipedia.org/wiki/Newton_fractal фрактальную структуру)); и каждая граничная точка любой области является также граничной для двух других областей[[Оригинал первого рисунка ☞ ((http://commons.wikimedia.org/wiki/File:Julia_set_for_the_rational_function.png ЗДЕСЬ))]]. {{ polynomial:newton_31.png |}} ((polynomial:newton:kapusta .)) Если начальную точку $ z_0 $ выбрать на этой границе, то последовательность метода Ньютона будет бесконечно долго скакать по ней, не сходясь ни к какому корню. При выборе $ z_0 $ близко к границе, мы, теоретически, должны получить последовательность, сходящуюся к какому-то корню. Однако ошибки округления, накапливающиеся с каждой итерацией, могут снова привести к непредсказуемости ни качества сходимости (к конкретному корню) ни количества итераций, требуемых для достижения заданной точности. === Системы нелинейных уравнений с несколькими неизвестными== Проблемы сходимости комплексного варианта метода Ньютона, отмеченные в предыдущем пункте, наследуются и обобщением метода Ньютона для задачи решения системы нелинейных уравнений с несколькими неизвестными. Действительно, задача поиска комплексных корней уравнения $ z^3-1=0 $ эквивалентна поиску вещественных решений системы уравнений $$ x^3-3\, xy^2-1=0, \ 3\, x^2y-y^3=0 \, . $$ !!§!! Развитие метода Ньютона для решения системы уравнений $$ f(x,y)=0, g(x,y)=0 $$ при $ f, g $ --- произвольных полиномах с вещественными коэффициентами обсуждается ☞ ((:algebra2:dets:jacobian:newton_mult ЗДЕСЬ)) ==Задачи== ☞ ((:polynomial:newton:problems ЗДЕСЬ)) ==Источники== [1]. **Березин И.С., Жидков Н.П.** //Методы вычислений. Т.2//. М.Физматгиз. 1960 [2]. **Uspensky J.V.** //Theory of Equations.// New York. McGraw-Hill. 1948