Метод касательных

Метод Ньютона (также известный как метод касательных) — это итерационный численный метод нахождения корня (нуля) заданной функции. Метод был впервые предложен английским физиком, математиком и астрономом Исааком Ньютоном (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\!$.

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

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

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

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

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

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

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

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

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

Алгоритм

1. Задаются начальным приближением x₀.
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) = cosx − x3 с начальным приближением в точке x0 = 0,5.
График последовательных приближений.	График сходимости.
Согласно способу практического определения скорость сходимости может быть оценена как тангенс угла наклона графика сходимости, то есть в данном случае равна двум.

Рассмотрим задачу о нахождении положительных x, для которых cosx = x³. Эта задача может быть представлена как задача нахождения нуля функции f(x) = cosx − x³. Имеем выражение для производной $f^\prime(x) = -\sin x - 3x^2$. Так как $\cos x\leqslant 1$ для всех x и x³ > 1 для x > 1, очевидно, что решение лежит между 0 и 1. Возьмём в качестве начального приближения значение x₀ = 0,5, тогда:
$\begin{matrix} x_1 & = & x_0 - \frac{f(x_0)}{f'(x_0)} & = & 1{,}112141637097 \\ x_2 & = & x_1 - \frac{f(x_1)}{f'(x_1)} & = & \underline{0{,}9}09672693736 \\ x_3 & = & x_2 - \frac{f(x_2)}{f'(x_2)} & = & \underline{0{,}86}7263818209 \\ x_4 & = & x_3 - \frac{f(x_3)}{f'(x_3)} & = & \underline{0{,}86547}7135298 \\ x_5 & = & x_4 - \frac{f(x_4)}{f'(x_4)} & = & \underline{0{,}8654740331}11 \\ x_6 & = & x_5 - \frac{f(x_5)}{f'(x_5)} & = & \underline{0{,}865474033102} \end{matrix}$

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

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

Иллюстрация расхождения метода Ньютона, применённого к функции f(x) = x³ − 2x + 2 с начальным приближением в точке x₀ = 0.

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

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

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

Пусть

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

Тогда

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

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

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

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

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

$f(x) = \begin{cases} x & ,\;x = 0\\ x + x^2\sin\left(\frac{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) \ge 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):\;\mathbb{X} \to \mathbb{R}\!$ и надо найти его решение.

Ниже приведена формулировка основной теоремы, которая позволяет дать чёткие условия применимости. Она носит имя советского математика и экономиста, лауреата Нобелевской премии по экономике 1975 года «за вклад в теорию оптимального распределения ресурсов» Леонида Витальевича Канторовича (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)|\leq C \leq \frac{1}{2AB}\!$;

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

1. на $[a,\;b]\!$ существует корень x ^* уравнения $f(x)=0:\quad\exist x^*\in[a,\;b]: 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|\leq\frac{B}{2^{n-1}}(2ABC)^{2^{n-1}}\!$.

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

$|x^*-x_n|\leq\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 (англ. Проблема комплексных чисел Ньютона-Фурье) был первым, кто отметил трудности в обобщении метода Ньютона на случай мнимых корней полиномов степени выше второй и комплексных начальных приближений. Эта работа открыла путь к изучению теории фракталов.

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

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

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

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

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

$\displaystyle 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\!$ выполнено равенство

$\displaystyle {\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\vert{\varphi}'(x)\vert\!$.

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

Обобщим полученный результат на многомерный случай. Пускай необходимо найти решение системы:

$\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}(\vec{x}^{[j+1]}_k - \vec{x}_k^{[j]})=0, \qquad i=1,2,\ldots,n\!$,

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

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

Пускай необходимо найти минимум функции многих переменных $f(\vec{x}):\mathbb{R}^n \to \mathbb{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 (\phi_i(\vec{x})-\mathcal{F}_i)^2 \to \min$

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

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

$H(\vec{x})=J^T(\vec{x})J(\vec{x})+Q(\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}$ определяется из системы:

$[J^T(\vec{x})J(\vec{x})+\sum_{i=1}^m f_i(\vec{x})H_i(\vec{x})]\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})$), и метод может достигать квадратичной скорости сходимости, хотя вторые производные и не учитываются. Улучшением метода является алгоритм Левенберга — Марквардта, основанный на эвристических соображениях.

Бассейны Ньютона для полинома пятой степени p(x) = x⁵ − 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. ↑ Доказательство:
   Пусть дана функция действительного переменного дважды непрерывно дифференцируемая в своей области определения, производная которой нигде не обращается в нуль:
   

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

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

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

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

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

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

   $\forall x\in\mathrm{U}_{\delta}(\tilde{x}):\quad |\varphi(x)-\tilde{x}|<\varepsilon|x-\tilde{x}|$.

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

См. также

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

Ссылки

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