Метод Ньютона

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

Описание метода

Обоснование

Чтобы численно решить уравнение $f(x)=0\!$ методом простой итерации, его необходимо привести к следующей форме: $x=\varphi(x)\!$, где $\varphi\!$ — сжимающее отображение.

Для наилучшей сходимости метода в точке очередного приближения $x^*\!$ должно выполняться условие $\varphi'(x^*)=0\!$. Решение данного уравнения ищут в виде $\varphi(x)=x+\alpha(x)f(x)\!$, тогда:

$\varphi'(x^*)=1+\alpha'(x^*)f(x^*)+\alpha(x^*) f'(x^*)=0.\!$

В предположении, что точка приближения «достаточно близка» к корню $\tilde{x}\!$, и что заданная функция непрерывна $(f(x^*)\approx f(\tilde{x})=0)\!$, окончательная формула для $\alpha(x)\!$ такова:

$\alpha(x)=-\frac{1}{f'(x)}.\!$

С учётом этого функция $\varphi(x)\!$ определяется выражением:

$\varphi(x)=x-\frac{f(x)}{f'(x)}.\!$

Эта функция в окрестности корня осуществляет сжимающее отображение^[1], и алгоритм нахождения численного решения уравнения $f(x)=0\!$ сводится к итерационной процедуре вычисления:

$x_{n+1}=x_{n}-\frac{f(x_n)}{f'(x_n)}.\!$

По теореме Банаха последовательность приближений стремится к корню уравнения $f(x)=0\!$.

Иллюстрация метода Ньютона (синим изображена функция $\scriptstyle{f(x)}$, нуль которой необходимо найти, красным — касательная в точке очередного приближения $\scriptstyle{x_n}$). Здесь мы можем увидеть, что последующее приближение $\scriptstyle{x_{n+1}}$ лучше предыдущего $\scriptstyle{x_n}$.

Геометрическая интерпретация

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

Пусть $f(x)\colon[a,\;b]\to\R\!$ — определённая на отрезке $[a,\;b]$ и дифференцируемая на нём вещественнозначная функция. Тогда формула итеративного исчисления приближений может быть выведена следующим образом:

$f'(x_n)=\mathrm{tg}\,\alpha=\frac{\Delta y}{\Delta x}=\frac{f( x_n)-0}{x_n-x_{n+1}}=\frac{0-f(x_n)}{x_{n+1}-x_n},\,\!$

где $\alpha$ — угол наклона касательной в точке $x_n\!$.

Следовательно искомое выражение для $x_{n+1}\!$ имеет вид:

$x_{n+1}=x_n-\frac{f(x_n)}{f'(x_n)}.\,\!$

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

Алгоритм

1. Задается начальное приближение $x_0$.
2. Пока не выполнено условие остановки, в качестве которого можно взять $|x_{n+1}-x_n|<\varepsilon\!$ или $|f(x_{n+1})|<\varepsilon\!$ (то есть погрешность в нужных пределах), вычисляют новое приближение: $x_{n+1}=x_n-\frac{f(x_n)}{f'(x_n)}\!$.

Пример

Иллюстрация применения метода Ньютона к функции $f(x)=\cos x-x^3$ с начальным приближением в точке $x_0=0{,}5$.
График последовательных приближений.	График сходимости.
Согласно способу практического определения скорость сходимости может быть оценена как тангенс угла наклона графика сходимости, то есть в данном случае равна двум.

Рассмотрим задачу о нахождении положительных $x$, для которых $\cos x=x^3$. Эта задача может быть представлена как задача нахождения нуля функции $f(x)=\cos x-x^3$. Имеем выражение для производной $f'(x)=-\sin x-3x^2$. Так как $\cos x\leqslant 1$ для всех $x$ и $x^3>1$ для $x>1$, очевидно, что решение лежит между 0 и 1. Возьмём в качестве начального приближения значение $x_0 = 0{,}5$, тогда:

$\begin{matrix} x_1 & = & x_0-\dfrac{f(x_0)}{f'(x_0)} & = & 1{,}112\;141\;637\;097, \\ x_2 & = & x_1-\dfrac{f(x_1)}{f'(x_1)} & = & \underline{0{,}9}09\;672\;693\;736, \\ x_3 & = & x_2-\dfrac{f(x_2)}{f'(x_2)} & = & \underline{0{,}86}7\;263\;818\;209, \\ x_4 & = & x_3-\dfrac{f(x_3)}{f'(x_3)} & = & \underline{0{,}865\;47}7\;135\;298, \\ x_5 & = & x_4-\dfrac{f(x_4)}{f'(x_4)} & = & \underline{0{,}865\;474\;033\;1}11, \\ x_6 & = & x_5-\dfrac{f(x_5)}{f'(x_5)} & = & \underline{0{,}865\;474\;033\;102}. \end{matrix}$

Подчёркиванием отмечены верные значащие цифры. Видно, что их количество от шага к шагу растёт (приблизительно удваиваясь с каждым шагом): от 1 к 2, от 2 к 5, от 5 к 10, иллюстрируя квадратичную скорость сходимости.

Условия применения

Иллюстрация расхождения метода Ньютона, применённого к функции $\scriptstyle{f(x)=x^3-2x+2}$ с начальным приближением в точке $\scriptstyle{x_0=0}$.

Рассмотрим ряд примеров, указывающих на недостатки метода.

Контрпримеры

• Если начальное приближение недостаточно близко к решению, то метод может не сойтись.

Пусть

$f(x)=x^3-2x+2.\!$

Тогда

$x_{n+1}=x_{n}-\frac{x_n^3-2x_n+2}{3x_n^2-2}.$

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

График производной функции $\scriptstyle{f(x)=x+x^2\sin(2/x)}$ при приближении $\scriptstyle{x}$ к нулю справа.

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

Рассмотрим функцию:

$f(x)=\begin{cases} x, & x=0, \\ x+x^2\sin\left(\dfrac{2}{x}\right), & x\neq 0. \end{cases}$

Тогда $f'(0)=1\!$ и $f'(x)=1+2x\sin(2/x)-2\cos(2/x)\!$ всюду, кроме 0.

В окрестности корня производная меняет знак при приближении $x$ к нулю справа или слева. В то время, как $f(x)\geqslant x-x^2>0\!$ для $0<x<1\!$.

Таким образом $f(x)/f'(x)\!$ не ограничено вблизи корня, и метод будет расходиться, хотя функция всюду дифференцируема, её производная не равна нулю в корне, $f\!$ бесконечно дифференцируема везде, кроме как в корне, а её производная ограничена в окрестности корня.

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

Рассмотрим пример:

$f(x)=x+x^{4/3}.\!$

Тогда $f'(x)=1+(4/3)x^{1/3}\!$ и $f''(x)=(4/9)x^{-2/3}\!$ за исключением $x=0\!$, где она не определена.

На очередном шаге имеем $x_n\!$:

$x_{n+1}=x_n-\frac{f(x_n)}{f'(x_n)}=\frac{(1/3)x_n^{4/3}}{(1+(4/3)x_n^{1/3})}.\!$

Скорость сходимости полученной последовательности составляет приблизительно 4/3. Это существенно меньше, нежели 2, необходимое для квадратичной сходимости, поэтому в данном случае можно говорить лишь о линейной сходимости, хотя функция всюду непрерывно дифференцируема, производная в корне не равна нулю, и $f\!$ бесконечно дифференцируема везде, кроме как в корне.

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

Пусть

$f(x)=x^2.\!$

Тогда $f'(x)=2x\!$ и следовательно $x-f(x)/f'(x)=x/2\!$. Таким образом сходимость метода не квадратичная, а линейная, хотя функция всюду бесконечно дифференцируема.

Ограничения

Пусть задано уравнение $f(x)=0\!$, где $f(x)\colon\mathbb{X}\to\R\!$ и надо найти его решение.

Ниже приведена формулировка основной теоремы, которая позволяет дать чёткие условия применимости. Она носит имя советского математика и экономиста Леонида Витальевича Канторовича (1912—1986).

Теорема Канторовича.

Если существуют такие константы $A,\;B,\;C\!$, что:

1. $\frac{1}{|f'(x)|}<A\!$ на $[a,\;b]\!$, то есть $f'(x)\!$ существует и не равна нулю;
2. $\left|\frac{f(x)}{f'(x)}\right|<B\!$ на $[a,\;b]\!$, то есть $f(x)\!$ ограничена;
3. $\exist f''(x)\!$ на $[a,\;b]\!$, и $|f''(x)|\leqslant C\leqslant\frac{1}{2AB}\!$;

Причём длина рассматриваемого отрезка $|a-b|<\frac{1}{AB}\left(1-\sqrt{1-2ABC}\right)\!$. Тогда справедливы следующие утверждения:

1. на $[a,\;b]\!$ существует корень $x^*\!$ уравнения $f(x)=0\colon\exist x^*\in[a,\;b]\colon f(x^*)=0\!$;
2. если $x_0=\frac{a+b}{2}\!$, то итерационная последовательность сходится к этому корню: $\left\{ x_{n+1}=x_n-\frac{f(x_n)}{f'(x_n)}\right\}\to x^*\!$;
3. погрешность может быть оценена по формуле $|x^*-x_n|\leqslant\frac{B}{2^{n-1}}(2ABC)^{2^{n-1}}\!$.

Из последнего из утверждений теоремы в частности следует квадратичная сходимость метода:

$|x^*-x_n|\leqslant\frac{B}{2^{n-1}}(2ABC)^{2^{n-1}}=\frac{1}{2}\frac{B}{2^{n-2}}\left((2ABC)^{2^{n-2}}\right)^2=\alpha |x^*-x_{n-1}|^2.\!$

Тогда ограничения на исходную функцию $f(x)\!$ будут выглядеть так:

1. функция должна быть ограничена;
2. функция должна быть гладкой, дважды дифференцируемой;
3. её первая производная $f'(x)\!$ равномерно отделена от нуля;
4. её вторая производная $f''(x)\!$ должна быть равномерно ограничена.

Историческая справка

Метод был описан Исааком Ньютоном в рукописи «Об анализе уравнениями бесконечных рядов» (лат. «De analysi per aequationes numero terminorum infinitas»), адресованной в 1669 году Барроу, и в работе «Метод флюксий и бесконечные ряды» (лат. «De metodis fluxionum et serierum infinitarum») или «Аналитическая геометрия» (лат. «Geometria analytica») в собраниях трудов Ньютона, которая была написана в 1671 году. В своих работах Ньютон вводит такие понятия, как разложение функции в ряд, бесконечно малые и флюксии (производные в нынешнем понимании). Указанные работы были изданы значительно позднее: первая вышла в свет в 1711 году благодаря Уильяму Джонсону, вторая была издана Джоном Кользоном в 1736 году уже после смерти создателя. Однако описание метода существенно отличалось от его нынешнего изложения: Ньютон применял свой метод исключительно к полиномам. Он вычислял не последовательные приближения $x_n$, а последовательность полиномов и в результате получал приближённое решение $x$.

Впервые метод был опубликован в трактате «Алгебра» Джона Валлиса в 1685 году, по просьбе которого он был кратко описан самим Ньютоном. В 1690 году Джозеф Рафсон опубликовал упрощённое описание в работе «Общий анализ уравнений» (лат. «Analysis aequationum universalis»). Рафсон рассматривал метод Ньютона как чисто алгебраический и ограничил его применение полиномами, однако при этом он описал метод на основе последовательных приближений $x_n$ вместо более трудной для понимания последовательности полиномов, использованной Ньютоном. Наконец, в 1740 году метод Ньютона был описан Томасом Симпсоном как итеративный метод первого порядка решения нелинейных уравнений с использованием производной в том виде, в котором он излагается здесь. В той же публикации Симпсон обобщил метод на случай системы из двух уравнений и отметил, что метод Ньютона также может быть применён для решения задач оптимизации путём нахождения нуля производной или градиента.

В 1879 году Артур Кэли в работе «Проблема комплексных чисел Ньютона — Фурье» (англ. «The Newton-Fourier imaginary problem») был первым, кто отметил трудности в обобщении метода Ньютона на случай мнимых корней полиномов степени выше второй и комплексных начальных приближений. Эта работа открыла путь к изучению теории фракталов.

Обобщения и модификации

Иллюстрация последовательных приближений метода одной касательной, применённого к функции $\scriptstyle{f(x)=e^x-2}$ с начальным приближением в точке $\scriptstyle{x_0=1{,}8}$.

Метод одной касательной

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

Формула итераций этого метода имеет вид:

$x_{n+1}=x_n-\frac{1}{f'(x_0)}f(x_n).\!$

Суть метода заключается в том, чтобы вычислять производную лишь один раз, в точке начального приближения $x_0\!$, а затем использовать это значение на каждой последующей итерации:

$\alpha(x)=\alpha_0=-\dfrac{1}{f'(x_0)}.\!$

При таком выборе $\alpha_0\!$ в точке $x_0\!$ выполнено равенство:

$\varphi'(x_0)=1+\alpha_0f'(x_0)=0,\!$

и если отрезок, на котором предполагается наличие корня $x^*\!$ и выбрано начальное приближение $x_0\!$, достаточно мал, а производная $\varphi'(x)\!$ непрерывна, то значение $\varphi'(x^*)\!$ будет не сильно отличаться от $\varphi'(x_0)=0\!\!$ и, следовательно, график $y=\varphi(x)\!$ пройдёт почти горизонтально, пересекая прямую $y=x\!$, что в свою очередь обеспечит быструю сходимость последовательности точек приближений к корню.

Этот метод можно также рассматривать, как модернизацию метода хорд (секущих), где число $\gamma\!$ следует выбрать равным $\max\limits_x|\varphi'(x)|.\!$

Многомерный случай

Обобщим полученный результат на многомерный случай.

Пусть необходимо найти решение системы:

$\left\{\begin{array}{lcr} f_1(x_1,\;x_2,\;\ldots,\;x_n) & = & 0, \\ \ldots & & \\ f_n(x_1,\;x_2,\;\ldots,\;x_n) & = & 0. \end{array}\right.$

Выбирая некоторое начальное значение $\vec{x}^{[0]}\!$, последовательные приближения $\vec{x}^{[j+1]}\!$ находят путём решения систем уравнений:

$f_i+\sum_{k=1}^n\frac{\partial f_i}{\partial x_k}(x^{[j+1]}_k-x_k^{[j]})=0,\qquad i=1,\;2,\;\ldots,\;n,\!$

где $\vec{x}^{[j]}=(x_1^{[j]},\;x_2^{[j]},\;\ldots,\;x_n^{[j]}),\quad j=0,\;1,\;2,\;\ldots\!$.

Применительно к задачам оптимизации

Пусть необходимо найти минимум функции многих переменных $f(\vec{x})\colon\R^n\to\R\!$. Эта задача равносильна задаче нахождения нуля градиента $\nabla f(\vec{x})\!$. Применим изложенный выше метод Ньютона:

$\nabla f(\vec{x}^{[j]})+H(\vec{x}^{[j]})(\vec{x}^{[j+1]}-\vec{x}^{[j]})=0,\quad j=1,\;2,\;\ldots,\;n,\!$

где $H(\vec{x})\!$ — гессиан функции $f(\vec{x})\!$.

В более удобном итеративном виде это выражение выглядит так:

$\vec{x}^{[j+1]}=\vec{x}^{[j]}-H^{-1}(\vec{x}^{[j]})\nabla f(\vec{x}^{[j]}).\!$

Следует отметить, что в случае квадратичной функции метод Ньютона находит экстремум за одну итерацию.

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

Метод Ньютона — Рафсона

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

$\vec{x}^{[j+1]}=\vec{x}^{[j]}-\lambda_j H^{-1}(\vec{x}^{[j]})\nabla f(\vec{x}^{[j]}),\!$

где $\lambda_j=\arg\min_\lambda f(\vec{x}^{[j]}-\lambda H^{-1}(\vec{x}^{[j]})\nabla f(\vec{x}^{[j]})).\!$ Для оптимизации вычислений применяют следующее улучшение: вместо того, чтобы на каждой итерации заново вычислять гессиан целевой функции, ограничиваются начальным приближением $H(f(\vec{x}^{[0]}))\!$ и обновляют его лишь раз в $m\!$ шагов, либо не обновляют вовсе.

Применительно к задачам о наименьших квадратах

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

$F(\vec{x})=\|\vec{f}(\vec{x})\|=\sum_{i=1}^m f_i^2(\vec{x})=\sum_{i=1}^m (\varphi_i(\vec{x})-\mathcal{F}_i)^2\to\min.$

Эти задачи отличаются особым видом градиента и матрицы Гессе:

$\nabla F(\vec{x})=2J^T(\vec{x}) f(\vec{x}),$

$H(\vec{x})=2J^T(\vec{x})J(\vec{x})+2Q(\vec{x}),\qquad Q(\vec{x})=\sum_{i=1}^m f_i(\vec{x})H_i(\vec{x}),$

где $J(\vec{x})$ — матрица Якоби вектор-функции $\vec{f}(\vec{x})$, $H_i(\vec{x})$ — матрица Гессе для её компоненты $f_i(\vec{x})$.

Тогда очередное направление $\vec{p}$ определяется из системы:

$\left[J^T(\vec{x})J(\vec{x})+\sum_{i=1}^m f_i(\vec{x})H_i(\vec{x})\right]\vec{p}=-J^T(\vec{x})f(\vec{x}).$

Метод Гаусса — Ньютона

Метод Гаусса — Ньютона строится на предположении о том, что слагаемое $J^T(\vec{x})J(\vec{x})$ доминирует над $Q(\vec{x})$. Это требование не соблюдается, если минимальные невязки велики, то есть если норма $\|\vec{f}(\vec{x})\|$ сравнима с максимальным собственным значением матрицы $J^T(\vec{x})J(\vec{x})$. В противном случае можно записать:

$J^T(\vec{x})J(\vec{x})\vec{p}=-J^T(\vec{x})f(\vec{x}).$

Таким образом, когда норма $\|Q(\vec{x})\|$ близка к нулю, а матрица $J(\vec{x})$ имеет полный столбцевой ранг, направление $\vec{p}$ мало отличается от ньютоновского (с учётом $Q(\vec{x})$), и метод может достигать квадратичной скорости сходимости, хотя вторые производные и не учитываются. Улучшением метода является алгоритм Левенберга — Марквардта, основанный на эвристических соображениях.

Обобщение на комплексную плоскость

Бассейны Ньютона для полинома пятой степени $\scriptstyle{p(x)=x^5-1}$. Разными цветами закрашены области притяжения для разных корней. Более тёмные области соответствуют большему числу итераций.

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

$z_{n+1}=z_n-\frac{f(z_n)}{f'(z_n)}.\!$

Особый интерес представляет выбор начального приближения $z_0\!$. Ввиду того, что функция может иметь несколько нулей, в различных случаях метод может сходиться к различным значениям, и вполне естественно возникает желание выяснить, какие области обеспечат сходимость к тому или иному корню. Этот вопрос заинтересовал Артура Кейли ещё в 1879 году, однако разрешить его смогли лишь в 70-х годах двадцатого столетия с появлением вычислительной техники. Оказалось, что на пересечениях этих областей (их принято называть областями притяжения) образуются так называемые фракталы — бесконечные самоподобные геометрические фигуры.

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

Литература

1. Акулич И. Л. Математическое программирование в примерах и задачах: Учеб. пособие для студентов эконом. спец. вузов. — М.: Высш. шк., 1986.
2. Амосов А. А., Дубинский Ю. А., Копченова Н. П. Вычислительные методы для инженеров. — М.: Мир, 1998.
3. Бахвалов Н. С., Жидков Н. П., Кобельков Г. Г. Численные методы. — 8-е изд.. — М.: Лаборатория Базовых Знаний, 2000.
4. Вавилов С. И. Исаак Ньютон. — М.: Изд. АН СССР, 1945.
5. Волков Е. А. Численные методы. — М.: Физматлит, 2003.
6. Гилл Ф., Мюррей У., Райт М. Практическая оптимизация. Пер. с англ. — М.: Мир, 1985.
7. Корн Г., Корн Т. Справочник по математике для научных работников и инженеров. — М.: Наука, 1970. — С. 575-576.
8. Коршунов Ю. М., Коршунов Ю. М. Математические основы кибернетики. — Энергоатомиздат, 1972.
9. Максимов Ю. А.,Филлиповская Е. А. Алгоритмы решения задач нелинейного программирования. — М.: МИФИ, 1982.
10. Морозов А. Д. Введение в теорию фракталов. — МИФИ, 2002.

Примечания

1. ↑ Доказательство: Пусть дана функция вещественного переменного дважды непрерывно дифференцируемая в своей области определения, производная которой нигде не обращается в нуль:

   $\scriptstyle{f(x)\colon\mathbb{X}\to\R,\;f(x)\in\mathrm{C}^2(\mathbb{X});\quad\forall x\in\mathbb{X}\;f'(x)\neq 0.}$

   И необходимо доказать, что функция $\scriptstyle{\varphi(x)=x-\frac{f(x)}{f'(x)}}$ осуществляет сжимающее отображение вблизи корня уравнения $\scriptstyle{f(x)=0}$. В силу непрерывной дифференцируемости функции $\scriptstyle{f(x)}$ и неравенства нулю её первой производной $\scriptstyle{\varphi(x)}$ непрерывна. Производная $\scriptstyle{\varphi'(x)}$ равна:

   $\scriptstyle{\varphi'(x)=\frac{f(x)f''(x)}{\left(f'(x)\right)^2}.}$

   В условиях, наложенных на $\scriptstyle{f(x)}$, она также непрерывна. Пусть $\scriptstyle{\tilde{x}}$ — искомый корень уравнения: $\scriptstyle{f(\tilde{x})=0}$, следовательно в его окрестности $\scriptstyle{\varphi'(x)\approx 0}$:

   $\scriptstyle{\forall\varepsilon\colon 0<\varepsilon<1,\;\exist\delta>0\;\forall x\in\mathbb{X}\;|x-\tilde{x}|<\delta\colon|\varphi'(x)-0|<\varepsilon.}$

   Тогда согласно теореме Лагранжа:

   $\scriptstyle{\forall x_1,\;x_2\in\mathrm{U}_\delta(\tilde{x})\;\exist\xi\in\mathrm{U}_\delta(\tilde{x})\colon|\varphi(x_1)-\varphi(x_2)|=|\varphi'(\xi)| |x_1-x_2|<\varepsilon|x_1-x_2|.}$

   В силу того, что $\scriptstyle{\varphi(\tilde{x})=\tilde{x}}$ в этой же дельта окрестности выполняется:

   $\scriptstyle{\forall x\in U_{\delta}(\tilde{x})\colon\;|\varphi(x)-\tilde{x}|<\varepsilon|x-\tilde{x}|.}$

   Таким образом полученная функция $\scriptstyle{\varphi(x)}$ в окрестности корня $\scriptstyle{U_\delta(\tilde{x})}$ осуществляет сжимающее отображение.

См. также

• Метод простой итерации
• Двоичный поиск
• Метод дихотомии
• Метод секущих
• Метод Мюллера
• Метод хорд
• Фрактал
• Численное решение уравнений

Ссылки

• «Бассейны Ньютона» на сайте fractalworld.xaoc.ru
• «Исаак Ньютон» на сайте www.scottish-wetlands.org
• «Математические работы Канторовича» на сайте Института математики СО РАН