Как найти значение корня методом ньютона – Сайт, где вы сможете решить свои вопросы

У этого термина существуют и другие значения, см. Метод (значения).

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

Описание метода[править | править код]

Обоснование[править | править код]

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

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

${displaystyle varphi '(x^{*})=1+alpha '(x^{*})f(x^{*})+alpha (x^{*})f'(x^{*})=0.}$

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

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

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

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

При некоторых условиях эта функция в окрестности корня осуществляет сжимающее отображение.

В этом случае алгоритм нахождения численного решения уравнения $f(x)=0$ сводится к итерационной процедуре вычисления:

${displaystyle 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}}$ .

Геометрическая интерпретация[править | править код]

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

Пусть 1) вещественнозначная функция ${displaystyle f(x)colon (a,,b)to mathbb {R} }$ непрерывно дифференцируема на интервале ${displaystyle (a,,b)}$ ;
2) существует искомая точка ${displaystyle x^{*}in (a,,b)}$ : ${displaystyle f(x^{*})=0}$ ;
3) существуют $C > 0$ и $delta >0$ такие, что
${displaystyle vert f'(x)vert geqslant C}$
для ${displaystyle xin (a,,x^{*}-delta ]cup [x^{*}+delta ,,b)}$
и ${displaystyle f'(x)neq 0}$
для ${displaystyle xin (x^{*}-delta ,,x^{*})cup (x^{*},,x^{*}+delta )}$ ;
4) точка ${displaystyle x_{n}in (a,,b)}$ такова, что ${displaystyle f(x_{n})neq 0}$ .
Тогда формула итеративного приближения $x_{n}$ к $x^{{*}}$
может быть выведена из геометрического смысла касательной следующим образом:

${displaystyle f'(x_{n})=mathrm {tg} ,alpha _{n}={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}}},}$

где ${displaystyle alpha _{n}}$ — угол наклона касательной прямой
${displaystyle y(x)=f(x_{n})+(x-x_{n})cdot mathrm {tg} ,alpha _{n}}$
к графику $f$
в точке ${displaystyle (x_{n};f(x_{n}))}$ .

Следовательно (в уравнении касательной прямой полагаем ${displaystyle y(x_{n+1})=0}$ ) искомое выражение для $x_{{n+1}}$ имеет вид :

${displaystyle x_{n+1}=x_{n}-{frac {f(x_{n})}{f'(x_{n})}}.}$

Если ${displaystyle x_{n+1}in (a,,b)}$ , то это значение можно использовать в качестве следующего приближения к
$x^{{*}}$ .

Если ${displaystyle x_{n+1}notin (a,,b)}$ , то имеет место «перелёт» (корень $x^{{*}}$ лежит рядом с границей ${displaystyle (a,,b)}$ ). В этом случае надо (воспользовавшись идеей метода половинного деления) заменять
$x_{{n+1}}$ на
${displaystyle {frac {x_{n}+x_{n+1}}{2}}}$
до тех пор, пока точка «не вернётся» в область поиска
${displaystyle (a,,b)}$ .

Замечания. 1) Наличие непрерывной производной даёт возможность строить непрерывно меняющуюся касательную на всей области поиска решения ${displaystyle (a,,b);}$ .
2) Случаи граничного (в точке $a$ или в точке $b$ ) расположения искомого решения $x^{{*}}$ рассматриваются аналогичным образом.
3) С геометрической точки зрения равенство
${displaystyle f'(x_{n})=0}$
означает, что касательная прямая к графику
$f$
в точке
${displaystyle (x_{n};f(x_{n}))}$ –
параллельна оси
$OX$
и при
${displaystyle f(x_{n})neq 0}$
не пересекается с ней в конечной части.
4) Чем больше константа $C > 0$ и чем меньше константа $delta >0$ из пункта 3 условий,
тем для ${displaystyle x_{n}in (a,,x^{*}-delta ]cup [x^{*}+delta ,,b)}$
пересечение касательной к графику $f$ и оси $OX$ ближе к точке ${displaystyle (x^{*};;0)}$ ,
то есть тем ближе значение $x_{{n+1}}$ к искомой ${displaystyle x^{*}in (a,,b)}$ .

Итерационный процесс начинается с некоторого начального приближения
${displaystyle x_{0}in (a,,b)}$ ,
причём между
${displaystyle x_{0}in (a,,b)}$
и искомой точкой
${displaystyle x^{*}in (a,,b)}$
не должно быть других нулей функции
$f$ ,
то есть «чем ближе $x_{0}$
к искомому корню $x^{{*}}$ ,
тем лучше». Если предположения о нахождении $x^{{*}}$ отсутствуют, методом проб и ошибок можно сузить область возможных значений, применив теорему о промежуточных значениях.

Для предварительно заданных ${displaystyle varepsilon _{x}>0}$ , ${displaystyle varepsilon _{f}>0}$
итерационный процесс завершается если
${displaystyle leftvert {frac {f(x_{n})}{f'(x_{n})}}rightvert approx vert x_{n+1}-x_{n}vert <varepsilon _{x}}$ и
${displaystyle vert f(x_{n+1})vert <varepsilon _{f}}$ .
В частности, для матрицы дисплея ${displaystyle varepsilon _{x}}$ и ${displaystyle varepsilon _{f}}$ могут быть рассчитаны,
исходя из масштаба отображения графика $f$ ,
то есть если $x_{n}$ и $x_{{n+1}}$ попадают в один вертикальный, а ${displaystyle f(x_{n})}$ и ${displaystyle f(x_{n+1})}$ в один горизонтальный ряд.

Алгоритм[править | править код]

Задается начальное приближение $x_{0}$ .
Пока не выполнено условие остановки, в качестве которого можно взять ${displaystyle |x_{n+1}-x_{n}|<varepsilon }$ или ${displaystyle |f(x_{n+1})|<varepsilon }$ (то есть погрешность в нужных пределах), вычисляют новое приближение: ${displaystyle 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 xleqslant 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{,}}909;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}$ .

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

Контрпримеры[править | править код]

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

Пусть

${displaystyle 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}$ к нулю справа.

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

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

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

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

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

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

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

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

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

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

На очередном шаге имеем $x_{n}$ :

${displaystyle 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$ бесконечно дифференцируема везде, кроме как в корне.

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

Пусть

${displaystyle f(x)=x^{2}.}$

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

Ограничения[править | править код]

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

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

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

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

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

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

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

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

${displaystyle |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)$ будут выглядеть так:

функция должна быть ограничена;
функция должна быть гладкой, дважды дифференцируемой;
её первая производная $f'(x)$ равномерно отделена от нуля;
её вторая производная $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}$ .

Метод секущих[править | править код]

Родственный метод секущих является «приближённым» методом Ньютона и позволяет не вычислять производную. Значение производной в итерационной формуле заменяется её оценкой по двум предыдущим точкам итераций:

${displaystyle f'(x_{n})approx {frac {f(x_{n})-f(x_{n-1})}{x_{n}-x_{n-1}}}}$ .

Таким образом, основная формула имеет вид

${displaystyle x_{n+1}=x_{n}-f(x_{n})cdot {frac {x_{n}-x_{n-1}}{f(x_{n})-f(x_{n-1})}}.}$

Этот метод схож с методом Ньютона, но имеет немного меньшую скорость сходимости. Порядок сходимости метода равен золотому сечению — 1,618…

Замечания. 1) Для начала итерационного процесса требуются два различных значения
$x_{0}$ и
$x_{1}$ .
2) В отличие от «настоящего метода Ньютона» (метода касательных), требующего хранить только ${displaystyle x_{n}}$
(и в ходе вычислений — временно ${displaystyle f(x_{n})}$ и ${displaystyle f'(x_{n})}$ ),
для метода секущих требуется сохранение
${displaystyle x_{n-1}}$ ,
${displaystyle x_{n}}$ ,
${displaystyle f(x_{n-1})}$ ,
${displaystyle f(x_{n})}$ .
3) Применяется, если вычисление $f'(x)$ затруднено
(например, требует большого количества машинных ресурсов: времени и/или памяти).

Метод одной касательной[править | править код]

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

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

${displaystyle x_{n+1}=x_{n}-{frac {1}{f'(x_{0})}}f(x_{n}).}$

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

${displaystyle alpha (x)=alpha _{0}=-{dfrac {1}{f'(x_{0})}}.}$

При таком выборе $alpha _{0}$ в точке $x_{0}$ выполнено равенство:

${displaystyle varphi '(x_{0})=1+alpha _{0}f'(x_{0})=0,}$

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

Этот метод является частным случаем метода простой итерации. Он имеет линейный порядок сходимости.

Метод Ньютона-Фурье[править | править код]

Метод Ньютона-Фурье – это расширение метода Ньютона, выведенное Жозефом Фурье для получения оценок на абсолютную ошибку аппроксимации корня, в то же время обеспечивая квадратичную сходимость с обеих сторон.

Предположим, что f(x) дважды непрерывно дифференцируема на отрезке [a, b] и что f имеет корень на этом интервале. Дополнительно положим, что f′(x), f″(x) ≠ 0 на этом отрезке (например, это верно, если f(a) < 0, f(b) > 0, и f″(x) > 0 на этом отрезке). Это гарантирует наличие единственного корня на этом отрезке, обозначим его α. Эти рассуждения относятся к вогнутой вверх функции. Если она вогнута вниз, то заменим f(x) на −f(x), поскольку они имеют одни и те же корни.

Пусть x₀ = b будет правым концом отрезка, на котором мы ищем корень, а z₀ = a – левым концом того же отрезка. Если x_n найдено, определим

${displaystyle x_{n+1}=x_{n}-{frac {f(x_{n})}{f'(x_{n})}},}$

которое выражает обычный метод Ньютона, как описано выше. Затем определим

${displaystyle z_{n+1}=z_{n}-{frac {f(z_{n})}{f'(x_{n})}},}$

где знаменатель равен f′(x_n), а не f′(z_n). Итерации x_n будут строго убывающими к корню, а итерации z_n – строго возрастающими к корню. Также выполняется следующее соотношение:

${displaystyle lim _{nto infty }{frac {x_{n+1}-z_{n+1}}{(x_{n}-z_{n})^{2}}}={frac {f''(alpha )}{2f'(alpha )}}}$ ,

таким образом, расстояние между x_n и z_n уменьшается квадратичным образом.

Многомерный случай[править | править код]

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

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

${displaystyle left{{begin{array}{lcr}f_{1}(x_{1},;x_{2},;ldots ,;x_{n})&=&0,\ldots &&\f_{m}(x_{1},;x_{2},;ldots ,;x_{n})&=&0.end{array}}right.}$

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

${displaystyle f_{i}+sum _{k=1}^{n}{frac {partial f_{i}}{partial x_{k}}}(x_{k}^{[j+1]}-x_{k}^{[j]})=0,qquad i=1,;2,;ldots ,;m,}$

где ${displaystyle {vec {x}}^{[j]}=(x_{1}^{[j]},;x_{2}^{[j]},;ldots ,;x_{n}^{[j]}),quad j=0,;1,;2,;ldots }$ .

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

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

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

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

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

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

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

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

Метод Ньютона — Рафсона[править | править код]

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

${displaystyle {vec {x}}^{[j+1]}={vec {x}}^{[j]}-lambda _{j}H^{-1}({vec {x}}^{[j]})nabla f({vec {x}}^{[j]}),}$

где ${displaystyle lambda _{j}=arg min _{lambda }f({vec {x}}^{[j]}-lambda H^{-1}({vec {x}}^{[j]})nabla f({vec {x}}^{[j]})).}$
Для оптимизации вычислений применяют следующее улучшение: вместо того, чтобы на каждой итерации заново вычислять гессиан целевой функции, ограничиваются начальным приближением ${displaystyle 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}}){vec {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}}){vec {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}}){vec {f}}({vec {x}}).$

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

Обобщение на комплексную плоскость[править | править код]

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

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

${displaystyle z_{n+1}=z_{n}-{frac {f(z_{n})}{f'(z_{n})}}.}$

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

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

Реализация[править | править код]

Scala[править | править код]

object NewtonMethod {

  val accuracy = 1e-6

  @tailrec
  def method(x0: Double, f: Double => Double, dfdx: Double => Double, e: Double): Double = {
    val x1 = x0 - f(x0) / dfdx(x0)
    if (abs(x1 - x0) < e) x1
    else method(x1, f, dfdx, e)
  }

  def g(C: Double) = (x: Double) => x*x - C

  def dgdx(x: Double) = 2*x

  def sqrt(x: Double) = x match {
    case 0 => 0
    case x if (x < 0) => Double.NaN
    case x if (x > 0) => method(x/2, g(x), dgdx, accuracy) 
  }
}

Python[править | править код]

from math import sin, cos
from typing import Callable
import unittest


def newton(f: Callable[[float], float], f_prime: Callable[[float], float], x0: float, 
	eps: float=1e-7, kmax: int=1e3) -> float:
	"""
	solves f(x) = 0 by Newton's method with precision eps
	:param f: f
	:param f_prime: f'
	:param x0: starting point
	:param eps: precision wanted
	:return: root of f(x) = 0
	"""
	x, x_prev, i = x0, x0 + 2 * eps, 0
	
	while abs(x - x_prev) >= eps and i < kmax:
		x, x_prev, i = x - f(x) / f_prime(x), x, i + 1

	return x


class TestNewton(unittest.TestCase):
	def test_0(self):
		def f(x: float) -> float:
			return x**2 - 20 * sin(x)


		def f_prime(x: float) -> float:
			return 2 * x - 20 * cos(x)


		x0, x_star = 2, 2.7529466338187049383

		self.assertAlmostEqual(newton(f, f_prime, x0), x_star)


if __name__ == '__main__':
	unittest.main()

PHP[править | править код]

<?php
// PHP 5.4
function newtons_method(
	$a = -1, $b = 1, 
	$f = function($x) {
	
		return pow($x, 4) - 1;
	
	},
	$derivative_f = function($x) {

		return 4 * pow($x, 3);
	
	}, $eps = 1E-3) {

        $xa = $a;
        $xb = $b;

        $iteration = 0;

        while (abs($xb) > $eps) {

            $p1 = $f($xa);
            $q1 = $derivative_f($xa);
            $xa -= $p1 / $q1;
            $xb = $p1;
            ++$iteration;

        }

        return $xa;

}

Octave[править | править код]

function res = nt()
  eps = 1e-7;
  x0_1 = [-0.5,0.5];
  max_iter = 500;
  xopt = new(@resh, eps, max_iter);   
  xopt
endfunction
function a = new(f, eps, max_iter)
  x=-1;
  p0=1;
  i=0;
 while (abs(p0)>=eps)
    [p1,q1]=f(x);
    x=x-p1/q1;
   p0=p1;
   i=i+1;
 end
 i
 a=x;
endfunction
function[p,q]= resh(x)   % p= -5*x.^5+4*x.^4-12*x.^3+11*x.^2-2*x+1;
   p=-25*x.^4+16*x.^3-36*x.^2+22*x-2;
   q=-100*x.^3+48*x.^2-72*x+22;
endfunction

Delphi[править | править код]

// вычисляемая функция
function fx(x: Double): Double;
begin
  Result := x * x - 17;
end;

// производная функция от f(x)
function dfx(x: Double): Double;
begin
  Result := 2 * x;
end;

function solve(fx, dfx: TFunc<Double, Double>; x0: Double): Double;
const
  eps = 0.000001;
var
  x1: Double;
begin
  x1 := x0 - fx(x0) / dfx(x0); // первое приближение
  while (Abs(x1-x0) > eps) do begin // пока не достигнута точность 0.000001
    x0 := x1;
    x1 := x1 - fx(x1) / dfx(x1); // последующие приближения
  end;
  Result := x1;
end;

// Вызов
solve(fx, dfx,4));

C++[править | править код]

#include <stdio.h>
#include <math.h>

#define eps 0.000001
double fx(double x) { return x * x - 17;} // вычисляемая функция
double dfx(double x) { return 2 * x;} // производная функции

typedef double(*function)(double x); // задание типа function

double solve(function fx, function dfx, double x0) {
  double x1  = x0 - fx(x0) / dfx(x0); // первое приближение
  while (fabs(x1 - x0) > eps) { // пока не достигнута точность 0.000001
    x0 = x1;
    x1 = x0 - fx(x0) / dfx(x0); // последующие приближения
  }
  return x1;
}

int main () {
  printf("%fn", solve(fx, dfx, 4)); // вывод на экран
  return 0;
}

C[править | править код]

typedef double (*function)(double x);

double TangentsMethod(function f, function df, double xn, double eps) {
   double x1  = xn - f(xn)/df(xn);
   double x0 = xn;
   while(abs(x0-x1) > eps) {
      x0 = x1;
      x1 = x1 - f(x1)/df(x1);
   }
   return x1;
}

//Выбор начального приближения
xn = MyFunction(A)*My2Derivative(A) > 0 ? B : A;

double MyFunction(double x) { return (pow(x, 5) - x - 0.2); } //Ваша функция
double MyDerivative(double x) { return (5*pow(x, 4) - 1); } //Первая производная
double My2Derivative(double x) { return (20*pow(x, 3)); } //Вторая производная

//Пример вызова функции
double x = TangentsMethod(MyFunction, MyDerivative, xn, 0.1)

Haskell[править | править код]

import Data.List ( iterate' )

main :: IO ()
main = print $ solve ( x -> x * x - 17) ( * 2) 4

-- Функция solve универсальна для всех вещественных типов значения которых можно сравнивать.
solve = esolve 0.000001

esolve epsilon func deriv x0 = fst . head $ dropWhile pred pairs
  where
    pred (xn, xn1) = (abs $ xn - xn1) > epsilon -- Функция pred определяет достигнута ли необходимая точность.
    next xn = xn - func xn / deriv xn -- Функция next вычисляет новое приближение.
    iters   = iterate' next x0        -- Бесконечный список итераций.
    pairs   = zip iters (tail iters)  -- Бесконечный список пар итераций вида: [(x0, x1), (x1, x2) ..].

Литература[править | править код]

Акулич И. Л. Математическое программирование в примерах и задачах : Учеб. пособие для студентов эконом. спец. вузов. — М. : Высшая школа, 1986. — 319 с. : ил. — ББК 22.1 А44. — УДК 517.8^(G).
Амосов А. А., Дубинский Ю. А., Копченова Н. П. Вычислительные методы для инженеров : Учеб. пособие. — М. : Высшая школа, 1994. — 544 с. : ил. — ББК 32.97 А62. — УДК 683.1^(G). — ISBN 5-06-000625-5.
Бахвалов Н. С., Жидков Н. П., Кобельков Г. Г. Численные методы. — 8-е изд. — М. : Лаборатория Базовых Знаний, 2000.
Вавилов С. И. Исаак Ньютон. — М. : Изд. АН СССР, 1945.
Волков Е. А. Численные методы. — М. : Физматлит, 2003.
Гилл Ф., Мюррей У., Райт М. Практическая оптимизация. Пер. с англ. — М. : Мир, 1985.
Корн Г., Корн Т. Справочник по математике для научных работников и инженеров. — М. : Наука, 1970. — С. 575—576.
Коршунов Ю. М., Коршунов Ю. М. Математические основы кибернетики. — Энергоатомиздат, 1972.
Максимов Ю. А.,Филлиповская Е. А. Алгоритмы решения задач нелинейного программирования. — М. : МИФИ, 1982.
Морозов А. Д. Введение в теорию фракталов. — МИФИ, 2002.

См. также[править | править код]

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

Ссылки[править | править код]

«Бассейны Ньютона» на сайте fractalworld.xaoc.ru
«Исаак Ньютон» на сайте www.scottish-wetlands.org
«Математические работы Канторовича» на сайте Института математики СО РАН
Hazewinkel, Michiel, ed. (2001), Newton method, Encyclopedia of Mathematics, Springer, ISBN 978-1-55608-010-4
Weisstein, Eric W. Newton’s Method (англ.) на сайте Wolfram MathWorld.
Newton’s method, Citizendium.
Mathews, J., The Accelerated and Modified Newton Methods, Course notes.
Wu, X., Roots of Equations, Course notes.

Источник

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

Метод
Ньютона, алгоритм Ньютона (также известный
как метод касательных) — это итерационный
численный метод нахождения корня (нуля)
заданной функции.

Достоинства
метода Ньютона:
Метод Ньютона – самый быстрый способ
нахождения корней уравнений: обычно
заданная точность достигается за 2-3
итерации. Очень быстрая сходимость по
сравнению с методом половинного деления
и методом простой итерации к заданной
точности.

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

Значение
корня новой итерации вычисляется по
формуле

Алгоритм

Задается
начальное приближение x₀.
Пока
не выполнено условие остановки, в
качестве которого можно взять

или

(то есть погрешность в нужных пределах),
вычисляют новое приближение:

[1].

Производные
функции

;
;
если

>0

если

Точное значение корня

Первое
уравнение – кубическое уравнение

Решение
кубического уравнения по формуле Кардано

Кубическое
уравнение в каноническом виде:

Обозначим
дискриминант кубического уравнения

По
формулам Кардано 3 корня уравнения
определяются следующим образом:

где

При
этом количество корней уравнения
определяются следующим образом:

Если

, уравнение имеет три действительных
корня.

Если

,
уравнение имеет один действительный и
два комплексно сопряженных корня.

Если

, уравнение имеет два действительных
корня. Если p = q = 0, уравнение имеет один
действительный корень [2].

Разрабатываемая
функция будет вычислять только первый
корень. При наличии других действительных
корнях будет сообщать об этом.

Наше
уравнение имеет вид:

Следовательно

Вычисление
корня по формуле Кардано:

float
al, be,//альфа, бетта

p,
q,//коэффициенты канонического уравнения

de;//дискриминант
(дельта)

p
= b / a;

q
= c / a;

de
= pow(p / 3, 3) + pow(q / 2, 2);

al
= pow(-q / 2 + pow(de, 0.5), (float)1/3);

be
= pow(-q / 2 – pow(de, 0.5), (float)1/3);

if(de
<= 0)

cout<<“nYravnenie
imeet neskol’ko deistvitelnuh kornei.”;

return
al + be;

Второе
уравнение – тригонометрическое уравнение

Найдем
точное решение уравнения

Уравнение
имеет множество корней. Нас интересует
ближайший корень к точке x0,
следовательно, необходимо найти ближайшее
целое значение k.

Тогда
точное решение будет в соответствии с
найденным k:

int
k;

k
= (x0 – asin(-c / a) + b) / (2 * M_PI);

return
asin(-c / a) + 2 * M_PI * k – b;

Третье
уравнение – логарифмическое уравнение

Два
возможных точных решения:

Нам
необходимо выбрать ближайший к x0.
То есть сравниваем расстояния х1х0 и
х2х0 и выбираем ближайший:

if
(fabs(exp(-c / a) – b – x0) < fabs(-exp(-c / a) – b – x0))

return
exp(-c / a) – b;

else

return
-exp(-c / a) – b

Абсолютная и относительная погрешность вычисления

Абсолютная
погрешность вычисления находится как
модуль разности между точным и приближенным
решением [3].

А
относительной погрешностью приближённого
числа называется отношение абсолютной
погрешности приближённого числа к
самому этому числу в процентном
соотношении.

Так
в нашем случае

fabs(pribl
– toch)
– абсолютная погрешность;

fabs(pribl
– toch)
/ toch
* 100 – относительная погрешность.

Где
pribl
– приближенное решение интеграла
(методом левых прямоугольников), toch
– точное решение интеграла.

Соседние файлы в предмете [НЕСОРТИРОВАННОЕ]

Источник

Метод Ньютона, также иногда называемый методом Ньютона-Рафсона, это простой и эффективный алгоритм для приближенного нахождения корней действительнозначных функций, то есть решения уравнений вида:
$$
f(x) = 0
$$

Единственные требования, накладываемые на функцию $f$ — что у неё есть хотя бы один корень и что она непрерывна и дифференцируема на интервале поиска.

#Описание алгоритма

Алгоритм начинает с какого-то изначального приближения $x_0$ и затем итеративно строит лучшее решение, строя касательную к графику в точке $x = x_i$ и присваивая в качестве следующего приближения $x_{i+1}$ координату пересечения касательной с осью $x$. Интуиция в том, что если функция $f$ «хорошая», и $x_i$ уже достаточно близок к корню, то $x_{i+1}$ будет ещё ближе.

Чтобы получить точку пересечения для $x_i$, нужно приравнять уравнение касательной к нулю:

$$
0 = f(x_i) + (x_{i+1} – x_i) f'(x_i)
$$
откуда можно выразить
$$
x_{i+1} = x_i – frac{f(x_i)}{f'(x_i)}
$$

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

#Поиск квадратных корней

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

$$
x = sqrt n iff x^2 = n iff f(x) = x^2 – n = 0
$$
Если в методе Ньютона подставим $f(x) = x^2 – n$, мы получим следующее правило:
$$
x_{i+1} = x_i – frac{x_i^2 – n}{2 x_i} = frac{x_i + n / x_i}{2}
$$

Если нам нужно посчитать корень с некоторой заданной точностью $epsilon$, можно на каждой итерации делать соответствующую проверку:

const double eps = 1e-9;

double sqrt(double n) {
    double x = 1;
    while (abs(x * x - n) > eps)
        x = (x + n / x) / 2;
    return x;
}

Алгоритм успешно сходится к правильному ответу для многих функций, однако это происходит надежно и доказуемо только для определенного множества функций (например, выпуклых). Другой вопрос — как быстра эта сходимость, если она происходит.

#Скорость сходимости

Запустим метод Ньютона для поиска квадратного корня $2$, начиная с $x_0 = 1$, и посмотрим, сколько первых цифр оказались правильными после каждой итерации:

1.0000000000000000000000000000000000000000000000000000000000000
1.5000000000000000000000000000000000000000000000000000000000000
1.4166666666666666666666666666666666666666666666666666666666675
1.4142156862745098039215686274509803921568627450980392156862745
1.4142135623746899106262955788901349101165596221157440445849057
1.4142135623730950488016896235025302436149819257761974284982890
1.4142135623730950488016887242096980785696718753772340015610125
1.4142135623730950488016887242096980785696718753769480731766796

Можно заметить, что число корректных цифр примерно удваивается после каждой итерации. Такая прекрасная скорость сходимости не просто совпадение.

Чтобы оценить скорость сходимости численно, рассмотрим небольшую относительную ошибку $delta_i$ на $i$-ой итерации и посмотрим, насколько меньше станет ошибка $delta_{i+1}$ на следующей итерации.

$$
|delta_i| = frac{|x_n – x|}{x}
$$
В терминах относительных ошибок, мы можем выразить $x_i$ как $x cdot (1 + delta_i)$. Подставляя это выражение в формулу для следующей итерации и деля обе стороны на $x$ получаем
$$
1 + delta_{i+1} = frac{1}{2} (1 + delta_i + frac{1}{1 + delta_i}) = frac{1}{2} (1 + delta_i + 1 – delta_i + delta_i^2 + o(delta_i^2)) = 1 + frac{delta_i^2}{2} + o(delta_i^2)
$$

Здесь мы разложили $(1 + delta_i)^{-1}$ в ряд Тейлора в точке $0$, используя предположение что ошибка $d_i$ мала: так как последовательность $x_i$ сходится к $x$, то $d_i ll 1$ для достаточно больших $n$.

Наконец, выражая $delta_{i+1}$, получаем

$$
delta_{i+1} = frac{delta_i^2}{2} + o(delta_i^2)
$$

что означает, что относительная ошибка примерно возводится в квадрат и делится пополам на каждой итерации, когда мы уже близки к решению. Так как логарифм $(- log_{10} delta_i)$ примерно равен числу правильных значимых цифр числа $x_i$, возведение ошибки в квадрат соответствует удвоению значимых цифр ответа, что мы и наблюдали ранее.

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

$$
|delta_{i+1}| = frac{|f”(x_i)|}{2 cdot |f'(x_n)|} cdot delta_i^2
$$
что означает хотя бы квадратичную сходимость при нескольких дополнительных предположениях, а именно что $f’(x)$ не равна нулю и $f’’(x)$ непрерывна.

Источник

Содержание

Вспомогательная страница к разделу

☞

ПОЛИНОМ ОДНОЙ ПЕРЕМЕННОЙ

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

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

Пусть $ 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_{} $ при $ jto + infty $.

Метод поиска вещественного решения уравнения $ f(x)=0 $ построением указанной последовательности известен как метод Ньютона или же (см.

☟

ПУНКТ) как метод каcательных.

Биографические заметки о Ньютоне

☞

ЗДЕСЬ.

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

Доказательство. Пусть
$$ lim_{jto + infty} x_j = A , $$
тогда и
$$lim_{jto + infty} x_{j-1} = A . $$
По непрерывности $ f_{}(x) $ и $ f^{prime}(x) $ будет выполнено
$$lim_{jto + infty} f(x_{j-1})= f(A) , quad lim_{jto + 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})}
$$
к пределу при $ jto + 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] $
у полинома нет.

♦

При выполнении условий теоремы $3$ скорость сходимости последовательности метода Ньютона оценивается неравенством

$$
|x_j-lambda|le frac{M}{2m} |x_{j-1}-lambda|^2 ; quad mbox{здесь} quad m= min_{xin [a,b]} | f^{prime}(x)|, M=
max_{xin [a,b]} | f^{prime prime}(x)| , .
$$

Пример. Найти положительный корень полинома $ 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 xin ]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) $ с осью абсцисс.

Легко вычислить координаты этой точки:
$$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} $ ближе к левому концу интервала.

Чувствительность корней

Если мы хотим найти приближенное значение корня полинома применением
метода Ньютона, то мы должны предварительно дать оценку точности вычислений: сколько значащих цифр мы должны сохранять в промежуточных выкладках, чтобы гарантировать достоверность получаемых результатов?

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

☞

ЗДЕСЬ.

Развитие

Методу Ньютона можно дать интерпретацию, отличную от изложенной в пункте МЕТОД КАСАТЕЛЬНЫХ. Если выполнены условия теоремы $ 3 $, то на интервале $ [a,b] $ существует обратная функция к $ 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) $. Но, по крайней мере, для таких функций можно представить обратную функцию в виде ряда Тейлора в окрестности некоторой точки $ 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)} ,
$$
т.е. в точности формулу первой итерации метода Ньютона.

Если взять три слагаемых разложения, то приближение корня второго порядка получается в виде
$$
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}
$$
необходимые для решения примера из пункта МЕТОД НЬЮТОНА.

Пример. Найти корень полинома $ x^5-4, x -2 $ на интервале $[1,2] $ с точностью до $ 0.001 $.

Решение. При выборе $ x_0 =2 $ требуемая точность достигается за три итерации
$$
x_1 = frac{22255}{13718} approx 1.622321,
x_2approx 1.521381, x_3 approx 1.518512 , .
$$

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

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

Геометрическая идея, лежащая в основе метода Галлея¹⁾, обобщает идею метода касательных. К графику функции $ 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) $).

Обобщения

Целые числа

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

Следующий результат получается «округлением» итераций метода Ньютона, примененного к уравнению $ x^2-B=0 $.

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

$$
B_j =
begin{array}{c}
leftlfloor
begin{array}{c}
B_{j-1}+ leftlfloor displaystyle frac{B}{B_{j-1}} rightrfloor_{} \
hline
2
end{array}
rightrfloor
\

end{array}
quad npu jin {1,2,dots } ,
$$
монотонно убывая, сойдется за конечное число шагов к значению
$ leftlfloorsqrt{B} rightrfloor $, если только число $ 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} $ «выведет» нас при $ jto infty $
к какому-то значению корня. Итак, вся комплексная плоскость может быть
поделена на три «области притяжения» каждого из корней. Раскрасим
эти множества в разные цвета. Какова будет граница между этими областями?
— Оказывается, эта граница имеет так называемую фрактальную структуру; и каждая граничная
точка любой области является также граничной для двух других
областей²⁾.

Если начальную точку $ 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 $ — произвольных полиномах с вещественными коэффициентами обсуждается

☞

ЗДЕСЬ

Задачи

Источники

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

[2]. Uspensky J.V. Theory of Equations. New York. McGraw-Hill. 1948

Источник

Численные методы решения нелинейных уравнений

Корни нелинейных уравнений

Пусть дано нелинейное уравнение

f(x)=0,qquad mathsf{(3.1)}

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

Требуется найти корни нелинейного уравнения (3.1), т.е. числа $x_{ast1},x_{ast2},ldots$ которые путем подстановки их в (3.1) превращают уравнение в верное числовое равенство. Числа $x_{ast1},x_{ast2},ldots$ называются также нулями функции f(x) .

На практике часто бывает выгодно уравнение (3.1) заменить равносильным ему уравнением (уравнения равносильны, если имеют одинаковые корни):

f_1(x)-f_2(x)=0,

(3.2)

где функции f_1(x),,f_2(x) — более простые, чем функция f(x) . Тогда при задании уравнения в виде (3.1) нулями функции f(x) являются точки пересечения f(x) с осью (рис. 3.1,д), а при задании в виде (3.2) — абсциссы точек пересечения функций f_1(x) и f_2(x) (рис. 3.1,б).

Точки пересечения функции с осью абсцисс

Замечания

1. Если $f(x)=a_nx^n+a_{n-1}x^{n-1}+ldots+a_0=P_n(x)$ — алгебраический многочлен, то уравнение (3.1) называется также алгебраическим n-й степени:

$P_n(x)equiv a_nx^n+a_{n-1}x^{n-1}+ldots+a_0=0,$

(3.3)

где a_n,ldots,a_0 — действительные числа, коэффициенты уравнения.

График сеточной функции

2. На практике встречаются задачи нахождения корней уравнения f(x_i)=0 , левая часть которого задана сеточной функцией y_i=f(x_i),~i=1,2,ldots,N (рис. 3.2).

Число $x_{ast}$ есть корень уравнения (3.1) кратности , если при $x=x_{ast}$ вместе с функцией f(x) обращаются в нуль ее производные до (k-1)-го порядка включительно, т.е. $f(x_{ast})= f'(x_{ast})= ldots= f^{(k-1)}(x_{ast})=0$ , а $f^{(k)}(x_{ast})ne0$ . Корень кратности к = 1 называется простым. На рис 3.1,с простыми корнями являются $x_{ast1},x_{ast2},x_{ast3}$ , a корни $x_{ast4},x_{ast5}$ — кратные.

В соответствии с классическим результатом Галуа алгебраическое уравнение (3.1) при ngeqslant5 не имеет решения в замкнутом (формульном) виде. Сеточные уравнения вообще не имеют формульных решений. Поэтому корни алгебраических (n>2) , трансцендентных и сеточных уравнений, как правило, определяются приближенно с заданной точностью.

Решение осуществляется в два этапа:

Первый этап. Находятся отрезки [a_i,b_i] , внутри каждого из которых содержится один простой или кратный корень $(x_{ast i}in[a_i,b_i])$ (см. рис. 3.1). Этот этап называется процедурой отделения корней. По сути на нем осуществляется грубое нахождение корней $x_{ast i}$ .

Второй этап. Грубое значение каждого корня $x_{ast i}$ уточняется до заданной точности одним из численных методов, в которых реализуются последовательные приближения. Порядок (скорость) сходимости метода определяется так же, как в методе простых итераций.

Отделение корней уравнения

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

Теорема 3.1 (о числе корней алгебраического уравнения (3.3)). Алгебраическое уравнение (3.3) n-й степени имеет ровно корней, действительных или комплексных, при условии, что каждый корень считается столько раз, какова его кратность.

Теорема 3.2 (о свойстве парной сопряженности комплексных корней уравнения (3.3)). Если $x_{ast i}=alpha+beta i$ — корень алгебраического уравнения (3.3) кратности , то число $overline{x_{ast i}}=alpha-beta i$ также является корнем той же кратности.

Следствие. Алгебраическое уравнение нечетной степени имеет по крайней мере один действительный корень.

Теорема 3.3 (об оценке модулей корней уравнения (3.3)). Пусть

$A=max bigl{|a_{n-1}|,ldots,|a_0|bigr},qquad B=max bigl{|a_n|,|a_{n-1}|,ldots, |a_1|bigr},$

где $a_k,~k=overline{0,n}$ — коэффициенты уравнения $a_nx^n+a_{n-1}x^{n-1}+ ldots+ a_{1}x+a_0=0$ . Тогда модули всех корней $x_{ast i}~(i=1,2,ldots,n)$ уравнения удовлетворяют неравенству

$frac{1}{1+dfrac{B}{|a_0|}}<|x_{ast i}| leqslant 1+frac{A}{|a_n|},quad i=1,2,ldots,n,$

(3.4)

т.е. корни уравнения расположены в кольце.

Следствие. Числа $r=frac{1}{1+dfrac{B}{|a_0|}}$ и $R=1+ frac{A}{|a_n|}$ являются соответственно нижней и верхней границами положительных корней алгебраического уравнения: $r<x_{ast i}^{+}<R$ . Аналогично числа и служат нижней и верхней границами отрицательных корней уравнения: $-R<x_{ast i}^{-}<-r$ .

Приведем полезные теоремы, используемые для более точного установления границ действительных корней алгебраических уравнений.

Теорема 3.4 (теорема Лагранжа о верхней границе положительных корней уравнения (3.3)). Пусть a_n>0 и a_i — первый отрицательный коэффициент в последовательности $a_n,a_{n-1},a_{n-2},ldots,a_1,a_0;~C$ — наибольшая из абсолютных величин отрицательных коэффициентов. Тогда за верхнюю границу положительных корней уравнения (3.3) может быть принято число

$R=1+sqrt[LARGE{n-i}]{frac{C}{a_n}},.$

(3.5)

Теорема 3.5 (о нижних и верхних границах положительных и отрицательных корней алгебраического уравнения). Пусть — верхняя граница положительных корней уравнения P_n(x)=0 ,

R_1 — верхняя граница положительных корней уравнения $P^1(x)= x^nP_n! left(frac{1}{x}right)=0$ ,
R_2 — верхняя граница положительных корней уравнения P^2(x)= P_n(-x)=0 ,
R_3 — верхняя граница положительных корней уравнения $P^3(x)= x^nP_n! left(-frac{1}{x}right)=0$ .

Тогда положительные корни $x_{ast i}^{+}$ и отрицательные корни $x_{ast i}^{-}$ уравнения (3.3) удовлетворяют неравенствам

$frac{1}{R_1}leqslant x_{ast i}^{+}leqslant R,qquad-R_2 leqslant x_{ast i}^{-}leqslant-frac{1}{R_3},.$

(3.6)

Теорема 3.6 (теорема Декарта о количестве действительных корней алгебраических уравнений). Число S_1 положительных корней (с учетом их кратностей) алгебраического уравнения P_n(x)=0 равно числу перемен знаков в последовательности коэффициентов $a_n,a_{n-1},ldots,a_0$ (коэффициенты, равные нулю, не учитываются) многочлена P_n(x) или меньше этого числа на четное число. Число S_2 отрицательных корней (с учетом их кратностей) алгебраического уравнения P_n(x)=0 равно числу перемен знаков в последовательности $a_n,a_{n-1},ldots,a_0$ многочлена P_n(-x) или меньше этого числа на четное число.

Теорема 3.7 (теорема Гюа о необходимом условии действительности всех корней алгебраического уравнения). Если алгебраическое уравнение (3.3) имеет все действительные корни, то квадрат каждого некрайнего коэффициента больше произведения двух его соседних коэффициентов.

Следствие. Если при каком-нибудь выполнено неравенство $a_k^2 leqslant a_{k-1}a_{k+1}$ , то уравнение (3.3) имеет по крайней мере одну пару комплексных корней.

Для отделения корней применяется следующая теорема.

Теорема 3.8. Если функция f(x) , определяющая уравнение f(x)=0 , на концах отрезка [a_i,b_i] принимает значения разных знаков, т.е. f(a_i)cdot f(b_i)<0 , то на этом отрезке содержится по крайней мере один корень уравнения. Если же f(x) непрерывна и дифференцируема и ее первая производная сохраняет знак внутри отрезка [a_i,b_i] $Bigl(mathop{operatorname{sign}}limits_{xin[a_i,b_i]} f'(x)=text{const}Bigr)$ , то на находится только один корень уравнения.

Способы отделения корней

В вычислительной практике обычно используются следующие способы отделения корней:

1) средствами машинной графики: функция f(x) представляется на дисплее и приближенно определяются отрезки, которым принадлежат точки $x_{ast i}$ ;

2) средствами математического анализа с помощью исследования функций и построения графиков (см. рис. 3.1,д);

3) формированием простых функций f_1(x) и f_2(x) таких, что получается равносильное уравнение в виде (3.2), и дальнейшим построением графиков этих функций (см. рис. 3.1,б).

▼ Примеры 3.1-3.3

Пример 3.1. Определить число положительных и отрицательных корней, а также их границы для уравнения

P_5(x)= x^5+2x^4-5x^3+8x^2-7x-3=0.

Решение

В данной задаче n=5,~ a_5=1,~ a_4=2,~ a_3=-5,~ a_2=8,~ a_1=-7,~ a_0=-3 . Согласно теореме 3.1 уравнение имеет пять корней. Поскольку n=5 , то по следствию из теоремы 3.2 уравнение имеет по крайней мере один действительный корень.

Оценим модули корней по теореме 3.3. Так как

A=max bigl{|2|,|-5|,|8|,|-7|,|-3|bigr}=8,qquad B=max bigl{|1|,|2|,|-5|, |8|,|-7|bigr}=8,

то $frac{1}{1+frac{8}{|-3|}}<|x_{ast i}|<1+frac{8}{|1|}$ или $frac{3}{11}<|x_{ast i}|<9$ , т.е. все корни лежат внутри данного кольца. По следствию из теоремы 3.3 это означает, что положительные корни удовлетворяют неравенству $frac{3}{11}<x_{ast i}^{+}<9$ , а отрицательные — неравенству $-9<x_{ast i}^{-}<-frac{3}{11}$ .

Применим теоремы 3.4 и 3.5 для уточнения приведенных результатов. Найдем верхнюю границу положительных корней. Так как a_3=-5 — первый отрицательный коэффициент в последовательности 1,2,-5,8,-7,-3 , то i=3 , а C=max bigl{|-5|,|-7|,|-3|bigr}=7 — наибольшая из абсолютных величин отрицательных коэффициентов. Следовательно, $R=1+sqrt[LARGE{(5-3)}]{frac{7}{1}}= 1+sqrt{7}cong3,!646$ .

Найдем нижнюю границу положительных корней. Составим уравнение:

$begin{aligned}P^{1}(x)&= x^nP_n! left(frac{1}{x}right)= x^5P_5!left(frac{1}{x} right)= x^5! left(frac{1}{x^5}+ frac{2}{x^4}-frac{5}{x^3}+frac{8}{x^2}-frac{7}{x}-3right)=\ &=-3x^5-7x^4+8x^3-5x^2+2x+1=0.end{aligned}$

или 3x^5+7x^4-8x^3+5x^2-2x-1=0 (старший коэффициент должен быть положительным). Для этого уравнения i=3,~ C=max bigl{|-8|,|-2|,|-1|bigr}=8 , поэтому $R_1=1+sqrt[LARGE{(5-3)}]{frac{8}{3}}=1+sqrt{frac{8}{3}}cong2,!632$ . Отсюда $frac{1}{R_1}=0,!38 leqslant x_{ast i}^{+}leqslant R=3,!646$ .

Уточним границы отрицательных корней. Составим уравнение:

P^2(x)=P_5(-x)= или x^5-2x^4-5x^3-8x^2-7x+3=0 .

Для этого уравнения i=4,~ C=maxbigl{|-2|,|-5|,|-8|,|-7|bigr}=8 , поэтому $R_2=1+ sqrt[LARGE{5-4}]{frac{8}{1}}=9$ . Составим уравнение

$begin{aligned}P^3(x)&= x^nP_n! left(-frac{1}{x}right)= x^5P_5! left(-frac{1}{x}right)= x^5! left(-frac{1}{x^5}+frac{2}{x^4}+frac{5}{x^3}+frac{8}{x^2}+frac{7}{x}-3right)=\ &=-3x^5+7x^4+8x^3+2x-1=0.end{aligned}$

или 3x^5-7x^4-8x^3-5x^2-2x+1=0 . Для этого уравнения i=4,~ C=max bigl{|-7|,|-8|,|-5|,|-2|bigr}=8 , поэтому $R_3=1+sqrt[LARGE{5-4}]{frac{8}{3}}=1+ frac{8}{3}cong3,!666$ . Отсюда находим: $-R_2=-9 leqslant x_{ast i}^{-}leqslant-frac{1}{R_3}=-0,!272$ . Заметим, что данный результат совпадает с полученным ранее.

Исследуем структуру корней уравнения. Так как квадрат каждого некрайнего коэффициента больше произведения двух его соседних коэффициентов, то по теореме 3.7 необходимое условие действительности всех корней уравнения выполняется.

На основе теоремы 3.6 определим число положительных и отрицательных корней. Выписываем коэффициенты многочлена P_n(x)=P_5(x)colon, 1,,2,-5,,8,-7,-3 . Так как число перемен знака S_1=3 , то число положительных корней равно трем или меньше на четное число, т.е. равно 1. Далее выписываем коэффициенты многочлена P_5(-x)colon, -1,,2,,5,,8,,7,-3 . Так как число перемен знаков S_2=2 , то число отрицательных корней равно двум или меньше на четное число, т.е. их вообще нет.

Пример 3.2. Отделить корни кубического уравнения x^3-x+1=0 .

Решение

Точка пересечения кубической параболы и прямой

Согласно теореме 3.1 уравнение имеет три корня, среди которых по крайней мере один действительный (следствие из теоремы 3.2, поскольку это уравнение нечетной степени).

Оценим модули корней уравнения по теореме 3.3. Так как

A=max bigl{|0|,|-1|,|1|bigr}=1,quad B=max bigl{|1|,|0|,|-1|bigr}=1 , то $frac{1}{1+dfrac{1}{|1|}}<|x_{ast i}|<1+frac{1}{|1|}$ или $frac{1}{2}<|x_{ast i}|<2$ .

Отсюда $frac{1}{2}<x_{ast i}^{+}<2$ и $-2<x_{ast i}^{+}<-frac{1}{2}$ .

Определим число положительных и отрицательных корней. Выписываем коэффициенты многочлена P_3(x)colon, 1,,0,-1,,1 . Так как число перемен знака S_1=2 (нулевой коэффициент не учитывается), то число положительных корней равно двум или меньше на четное число, т.е. они отсутствуют. Далее выписываем коэффициенты многочлена P_3(-x)=-x^3+x+1colon, -1,,0,,1,,1 . Так как число перемен знака S_2=1 (нулевой коэффициент не учитывается), то число отрицательных корней равно единице.

Отделим корни третьим способом. Для этого преобразуем уравнение к равносильному виду (3.2): x^3=x-1 и найдем точки пересечения фафиков y=x^3 и y=x-1 (рис. 3.3).

Очевидно, корень уравнения $x_{ast}in[-2;-1]$ .

Пример 3.3. Отделить корни уравнения третьего порядка x^3-x^2-9x+9=0 .

Решение

Процедура уточнения положения корня функции

Метод половинного деления

Пусть дано уравнение f(x)=0 и отделен простой корень $x_{ast}$ , т.е. найден такой отрезок [a_0,b_0] , что $x_{ast}in[a_0,b_0]$ и на концах отрезка функция имеет значения, противоположные по знаку (f(a_0)cdot f(b_0)<0) . Отрезок называется начальным интервалом неопределенности, потому что известно, что корень ему принадлежит, но его местоположение с требуемой точностью не определено.

Процедура уточнения положения корня заключается в построении последовательности вложенных друг в друга отрезков, каждый из которых содержит корень уравнения. Для этого находится середина текущего интервала неопределенности $c_k=frac{a_k+b_k}{2},~ k=0,1,2,ldots$ , и в качестве следующего интервала неопределенности из двух возможных выбирается тот, на концах которого функция f(x) имеет разные знаки (рис. 3.5).

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

Алгоритм метода половинного деления

1. Найти начальный интервал неопределенности L_0=[a_0,b_0] одним из методов отделения корней, задать малое положительное число varepsilon . Положить k=0 .

2. Найти середину текущего интервала неопределенности: $c_k=frac{a_k+b_k}{2}$ .

3. Если f(a_k)cdot f(c_k)<0 , то положить $a_{k+1}=a_k,~ b_{k+1}= c_k$ , а если f(c_k)cdot f(b_k)<0 , то принять $a_{k+1}=c_k,~ b_{k+1}= b_k$ . В результате находится текущий интервал неопределенности $L_{k+1}= [a_{k+1},b_{k+1}]$ .

4. Если $b_{k+1}-a_{k+1}leqslant varepsilon$ , то процесс завершить: $x_{ast}in L_{k+1}= [a_{k+1},b_{k+1}]$ . Приближенное значение корня можно найти по формуле $x_{ast}cong frac{a_{k+1}+b_{k+1}}{2}$ .

Если $b_{k+1}-a_{k+1}>varepsilon$ , положить k=k+1 и перейти к п.2.

Замечания

1. Метод имеет линейную, но безусловную сходимость, и его погрешность за каждую итерацию уменьшается в два раза:

$|b_1-a_1|=frac{|b_0-a_0|}{2};quad |b_2-a_2|= frac{|b_1-a_1|}{2}= frac{|b_0-a_0|}{2^2},quad ldots,quad |b_k-a_k|= |b_0-a_0|cdot2^{-k}.$

Из последнего соотношения можно оценить число итераций для достижения заданной точности varepsiloncolon

$|b_0-a_0|cdot2^{-k} leqslant varepsilon;qquad k geqslant log_{2}frac{|b_0-a_0|}{varepsilon},.$

Отсюда видно, что, например, для достижения точности $varepsilonapprox10^{-3}$ при (b_0-a_0)cong1 необходимо выполнить примерно десять итераций.

2. К достоинствам метода следует отнести то, что он позволяет найти простой корень уравнения $x_{ast}in[a_0,b_0]$ любых непрерывных функций f(x) при любых значениях a_0,,b_0 таких, что f(a_0)cdot f(b_0)<0 . Недостатки метода — он не обобщается на системы нелинейных уравнений и не может использоваться для нахождения корней четной кратности.

▼ Примеры 3.4-3.6

Пример 3.4. Найти корень уравнения x^3-x+1=0 методом половинного деления с точностью varepsilon_1=0,!01 и varepsilon_2=0,!0005 .

Решение

Пример 3.5. Найти корень уравнения x^3-x^2-9x+9=0 методом половинного деления с точностью varepsilon=0,!001 .

Решение

В примере 3.3 были отделены корни уравнения. Уточним корень, лежащий на отрезке [2,!5;4] . Результаты расчетов поместим в табл. 3.2.

$begin{aligned} mathit{Table~3.2}~&\ begin{array}{|c|c|c|c|c|c|c|c|} hline begin{matrix}{}\[-2pt]{}end{matrix} k& f(a_k)& a_k& b_k& f(b_k)& c_k=dfrac{a_k+b_k}{2}& f(c_k)& b_k-a_k\hline 0& -4,!125& 2,!5& 4& 21& 3,!25& 3,!5156& 1,!5\hline 1& -4,!125& 2,!5& 3,!25& 3,!5156& 2,!875& -1,!3769& 0,!75\hline 2& -1,!3769& 2,!875& 3,!25& 3,!5156& 3,!0625& 0,!78149& 0,!375\hline 3& -1,!3769& 2,!875& 3,!0625& 0,!7815& 2,!96875& -0,!3672& 0,!1875\hline 4& -0,!3672& 2,!9687& 3,!0625& 0,!7815& 3,!01562& 0,!18945& 0,!09375\hline 5& -0,!3672& 2,!9687& 3,!0156& 0,!1894& 2,!99218& -0,!0933& 0,!04687\hline 6& -0,!0933& 2,!9921& 3,!0156& 0,!1894& 3,!0039& 0,!0469& 0,!02344\hline 7& -0,!0933& 2,!9921& 3,!0039& 0,!0469& 2,!99804& -0,!02349& 0,!01172\hline 8& -0,!02349& 2,!99804& 3,!0039& 0,!0469& 3,!00097& 0,!011647& 0,!00586\hline end{array}& end{aligned}$

В результате найден интервал [2,!99804;3,!0039] и приближенное значение корня $x_{ast}cong3,!00097$ .

Пример 3.6. Отделить корни трансцендентного уравнения $x^2-e^{-x}=0$ и найти один из корней с точностью varepsilon=0,!01 .

Решение

1. Можно отделить корни уравнения, преобразовав его к равносильному виду $x^2=e^{-x}$ и определив абсциссу точек пересечения графиков функций y=f_1(x)=x^2 и $y=f_2(x)=e^{-x}colon, x_{ast}in[0,!5;1]$ . При этом f(0,!5)cdot f(1)<0 .

2. Уточним корень. Результаты расчетов приведем в табл. 3.3.

$begin{aligned} mathit{Table~3.3}~&\ begin{array}{|c|c|c|c|c|c|c|c|} hline begin{matrix}{}\[-2pt]{}end{matrix} k& f(a_k)& a_k& b_k& f(b_k)& c_k=dfrac{a_k+b_k}{2}& f(c_k)& b_k-a_k\hline 0& -0,!3565& 0,!5& 1& 0,!6321& 0,!75& 0,!09013& 0,!5\hline 1& -0,!3565& 0,!5& 0,!75& 0,!09013& 0,!625& -0,!1446& 0,!251\hline 2& -0,!1446& 0,!625& 0,!75& 0,!09013& 0,!6875& -0,!0301& 0,!125\hline 3& -0,!0301& 0,!6875& 0,!75& 0,!09013& 0,!7187& 0,!0292& 0,!0625\hline 4& -0,!0301& 0,!6875& 0,!7187& 0,!0292& 0,!7031& -0,!00069& 0,!0312\hline 5& -0,!00069& 0,!7031& 0,!7187& 0,!0292& 0,!7109& 0,!0142& 0,!0156\hline 6& -0,!00069& 0,!7031& 0,!7109& 0,!0142& 0,!707& 0,!0067& 0,!0078\hline end{array}& end{aligned}$

Вычисления показывают, что b_6-a_6=0,!7109-0,!7031=0,!0078< varepsilon= 0,!01 .

Поэтому $x_{ast}cong frac{0,!7109+0,!7031}{2}= c_6=0,!707$ .

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

Метод хорд

Этот метод при тех же предположениях обеспечивает более быстрое нахождение корня, чем метод половинного деления. Для этого отрезок [a,b] делится не пополам, а в отношении |f(a)|,colon|f(b)| .

Геометрически метод хорд эквивалентен замене кривой y=f(x) хордой, проходящей через точки (a,f(a)) и (b,f(b)) (рис. 3.6).

Уравнение хорды имеет вид $frac{x-a}{b-a}= frac{y-f(a)}{f(b)-f(a)}$ . Полагая $x=x^{(1)}$ и y=0 , получаем

$x^{(1)}= a-frac{f(a)}{f(b)-f(a)}cdot(b-a).$

Предположим, что вторая производная f''(x) сохраняет постоянный знак, и рассмотрим два случая: f(a)>0,~ f''(a)>0 (рис. 3.7,д) и f(a)<0,~ f''(x)>0 (рис. 3.7,б). Случай f''(x)<0 сводится к рассматриваемому, если уравнение записать в форме: -f(x)=0 . Первому случаю (см. рис. 3.7,д) соответствует формула (3.7), а второму случаю (3.8) (см. рис. 3.7,б):

$begin{aligned}&x^{(0)}=b,\ &x^{(k+1)}=x^{(k)}-frac{f(x^{(k)})}{f(x^{(k)})-f(a)} bigl(x^{(k)}-abigr),quad k=0,1,2,ldotsend{aligned}$

(3.7)

$begin{aligned}&x^{(0)}=a,\ &x^{(k+1)}=x^{(k)}-frac{f(x^{(k)})}{f(b)-f(x^{(k)})}bigl(b-x^{(k)}bigr),quad k=0,1,2,ldots end{aligned}$

(3.8)

В первом случае остается неподвижным конец , а во втором случае конец .

Метод хорд

Замечание. Для выявления неподвижного конца используется условие f''(x)cdot f(t)>0 , где t=a или t=b . Если неподвижен конец , применяется формула (3.7), а если конец , — формула (3.8).

Пример 3.7. Найти корень уравнения x^3-x+1=0 методом хорд с точностью varepsilon=0,!001 .

Решение

Рассмотрим задачу нахождения корня на отрезке [-2;-1] (см. пример 3.2). Так как f(a)=f(-2)=-5, f(b)=f(-1)=-1 , a f''(x)=3x^2-1>0 на отрезке [-2;-1] , то f''(x)cdot f(b)>0 и, следовательно, имеем второй случай (см. рис. 3.7,б).

Положим $x^{(0)}=a=-2,~k=0$ . Тогда по формуле (3.8) получаем

$x^{(1)}= x^{(0)}-frac{f(x^{(0)})}{f(b)-f(x^{(0)})}bigl(b-x^{(0)}bigr)=-2-frac{-5}{1-(-5)}cdot(-1-(-2))=-1,!1666.$

Так как $Delta_1=|x^{(1)}-x^{(0)}|=0,!8334>varepsilon$ , то положим k=1 и продолжим процесс:

$x^{(2)}= x^{(1)}-frac{f(x^{(1)})}{f(b)-f(x^{(1)})}bigl(b-x^{(1)}bigr)=-1,!1666-frac{-0,!5786}{1-0,!5786}cdot bigl(-1-(-1,!1666)bigr)=-1,!3953.$

Так как $Delta_2=|x^{(2)}-x^{(1)}|=0,!2287>varepsilon$ , то положим k=2 и продолжим процесс:

$x^{(3)}= x^{(2)}-frac{f(x^{(2)})}{f(b)-f(x^{(2)})}bigl(b-x^{(2)}bigr)=-1,!3953-frac{-0,!3214}{1+0,!3214}cdot bigl(-1-(-1,!3953)bigr)=-1,!2991.$

Поскольку $Delta_3=|x^{(3)}-x^{(2)}|=0,!0962>varepsilon$ , положим k=3colon

$x^{(4)}= x^{(3)}-frac{f(x^{(3)})}{f(b)-f(x^{(3)})}bigl(b-x^{(3)}bigr)=-1,!2991-frac{-0,!1064}{1+0,!1064}cdot bigl(-1-(-1,!2991)bigr)=-1,!3347.$

Так как $Delta_4=|x^{(4)}-x^{(3)}|=0,!0356>varepsilon$ , положим k=4colon

$x^{(5)}= x^{(4)}-frac{f(x^{(4)})}{f(b)-f(x^{(4)})}bigl(b-x^{(4)}bigr)=-1,!3347-frac{-0,!043}{1+0,!043}cdot bigl(-1-(-1,!3347)bigr)=-1,!3209.$

Поскольку $Delta_5=|x^{(5)}-x^{(4)}|=0,!0138>varepsilon$ , положим k=5colon

$x^{(6)}= x^{(5)}-frac{f(x^{(5)})}{f(b)-f(x^{(5)})}bigl(b-x^{(5)}bigr)=-1,!3209-frac{-0,!0162}{1+0,!0162}cdot bigl(-1-(-1,!3209)bigr)=-1,!3261.$

Так как $Delta_6=|x^{(6)}-x^{(5)}|=0,!0052>varepsilon$ , положим k=6colon

$x^{(7)}= x^{(6)}-frac{f(x^{(6)})}{f(b)-f(x^{(6)})}bigl(b-x^{(6)}bigr)=-1,!3261-frac{-0,!0059}{1+0,!0059}cdot bigl(-1-(-1,!3261)bigr)=-1,!3241.$

Поскольку $Delta_7=|x^{(7)}-x^{(6)}|=0,!0020>varepsilon$ , положим k=7colon

$x^{(8)}= x^{(7)}-frac{f(x^{(7)})}{f(b)-f(x^{(7)})}bigl(b-x^{(7)}bigr)=-1,!3241-frac{-0,!00217}{1+0,!00217}cdot bigl(-1-(-1,!3241)bigr)=-1,!3248.$

Так как $Delta_8=|x^{(8)}-x^{(7)}|=0,!0007<varepsilon=0,!001$ , то корень уравнения $x_{ast}cong-1,!3248$ . Из анализа поведения Delta_k следует, что сходимость метода хорд линейная, однако более быстрая, чем сходимость метода половинного деления.

Абсцисса точки пересечения прямой и кривой

Метод простых итераций

Пусть известно, что корень $x_{ast}$ уравнения f(x)=0 лежит на отрезке G={aleqslant xleqslant b} .

Методика решения задачи

1. Уравнение f(x)=0 равносильным преобразованием привести к виду x=varphi(x) . Это преобразование может быть осуществлено различными путями, но для сходимости нужно обеспечить выполнение условия |varphi'(x)|leqslantchi<1 ( chi — некоторая константа). При этом задача сводится к нахождению абсциссы точки пересечения прямой y=x и кривой y=varphi(x) (рис. 3.8).

2. Задать начальное приближение $x^{(0)}in[a,b]$ и малое положительное число varepsilon . Положить k=0 .

3. Вычислить следующее приближение:

$x^{(k+1)}= varphi(x^{(k)}).$

(3.9)

4. Если $|x^{(k+1)}-x^{(k)}|leqslantvarepsilon$ , итерации завершаются и $x_{ast}cong x^{(k+1)}$ . Если $|x^{(k+1)}-x^{(k)}|>varepsilon$ , положить k=k+1 и перейти к п.3.

Замечание. В качестве условия завершения итераций при известном значении chi может быть использовано неравенство

$bigl|x^{(k+1)}-x^{(k)}bigr|leqslant frac{1-chi}{chi}cdot varepsilon.$

Проблемы сходимости и единственности численного решения, являющиеся главными при использовании этого метода, решаются и исследуются с помощью понятия о сжимающем отображении и теоремы о достаточном условии сходимости метода.

Отображение (функция) varphi(x) называется сжимающим в области с коэффициентом chi~(0leqslantchi<1) , если для любых двух x',,x'' из выполнено неравенство

bigl|varphi(x'')-varphi(x')bigr|leqslantchicdotbigl|x''-x'bigr|.

(3.10)

Теорема 3.9 (о сходимости метода простых итераций и единственности получаемого численного решения)

Пусть выполнены условия:

1. Нелинейное уравнение x=varphi(x) имеет решение $x_{ast}in G$ .

2. Отображение varphi(x) является сжимающим в области с некоторым коэффициентом chi~(0leqslantchi<1) .

Тогда:

а) решение $x_{ast}$ является единственным решением в области ;

б) последовательность $x^{(0)},x^{(1)},ldots,x^{(k+1)},ldots$ , определяемая по отображению на основе итерационного процесса, сходится к решению $x_{ast}$ со скоростью геометрической прогрессии, т.е. при выборе $x^{(0)}$ из условия $|x_{ast}-x^{(0)}|<R$ , где R>0 — некоторое малое число, справедливо неравенство

$bigl|x_{ast}-x^{(k)}bigr| leqslant chi^kcdot bigl|x_{ast}-x^{(0)}bigr|,quad k=0,1,2,ldots$

Теорема 3.9 утверждает, что при выполнении условий 1,2 существует окрестность $G(x_{ast},R)$ такая, что если взять $x^{(0)}$ в этой окрестности и вычислять $x^{(1)},x^{(2)},ldots$ по формуле (3.9), то в результате с любой наперед заданной точностью можно вычислить $x^{(k+1)}approx x_{ast}$ , соответствующее искомому (единственному) корню. Но так как эта окрестность неизвестна, то можно взять произвольное $x^{(0)}in G$ . Если при этом вычисляется последовательность $x^{(0)},x^{(1)},x^{(2)},ldots,x{(k)},ldots$ , сходящаяся к некоторому значению widehat{x} , то в силу теоремы $widehat{x}=x_{ast}$ . Если сходимость отсутствует, то надо взять другое $x^{(0)}in G$ и повторить расчет.

Теорема 3.10 (о достаточном условии сходимости метода простых итераций). Пусть выполнены условия:

1. Функция varphi(x) имеет производные для всех xin G .

2. Существует число chi,(0 leqslantchi<1,~chi=text{const}) , такое, что |varphi'(x)|leqslantchi для всех xin G .

Тогда отображение varphi(x) является сжимающим в с коэффициентом сжатия х и последовательность $x^{(0)},x^{(1)},ldots,x^{(k+1)},ldots$ , определяемая на основе итерационного процесса, сходится к решению $x_{ast}$ , то есть $x^{(k)}to x_{ast}$ при ktoinfty .

▼ Доказательство

В силу условия 1 справедлива теорема Лагранжа о конечных приращениях:

varphi(x'')-varphi(x')leqslant (x''-x')varphi'(delta) для forall x',x''in G ,

где delta — точка, лежащая между и x'' . Но тогда с учетом условия 2 и замены varphi'(delta) ее мажорантой chi получим

bigl|varphi(x'')-varphi(x')bigr|leqslant chicdot bigl|x''-x'bigr|,

т.е. отображение varphi(x) — сжимающее, и, таким образом, последовательность $x^{(0)},x^{(1)},ldots,x^{(k+1)},ldots$ сходится к некоторому widehat{x} . Но тогда в силу непрерывности в имеет место равенство $widehat{x}=x_{ast}$ .

Геометрическая интерпретация процесса сходимости и расходимости в зависимости от выполнения или невыполнения достаточного условия сходимости представлена на рис. 3.9.

Сходимость итерационных последовательностей

Из рис. 3.9 видно, что при 0<varphi'(x)<1 и при -1<varphi'(x)<0 (см.рис. 3.9,д,б) итерационные последовательности $x^{(0)},x^{(1)},x^{(2)},ldots$ сходятся к $x_{ast}$ . Причем в первом случае реализуется односторонняя (монотонная) сходимость, а во втором — двусторонняя (немонотонная). При |varphi'(x)|>1 (см.рис. 3.9,в,г) процесс расходится несмотря на то, что точка $x^{(0)}$ очень близка к $x_{ast}$ . Процессы на рис. 3.9,а,б соответствуют сжимающему отображению.

Преобразование уравнения f(x)=0 к равносильному виду x=varphi(x) может быть выполнено неоднозначно. Рассмотрим универсальные практические приемы равносильного преобразования f(x)=0 , дающие сжимающие отображения.

1. Можно заменить уравнение f(x)=0 на равносильное x=x+cf(x) , где c=text{const}ne0 . Тогда, принимая правую часть этого уравнения за varphi(x) и раскрывая |varphi'(x)|= |1+cf'(x)|<1 , получаем условие

-2<ccdot f'(x)<0.

(3.11)

Таким образом, можно найти константу на отрезке G=[a,b] так, чтобы удовлетворялись неравенства (3.11). При этом надо стремиться получить такую постоянную , которая бы больше отличалась от нуля, и тогда будет реализовы-ваться более быстрая сходимость.

Можно показать, что абсолютная погрешность метода оценивается по формуле (эта оценка выражается через два последовательных приближения)

$bigl|x^{(k+1)}-x_{ast}bigr|leqslant frac{chi}{1-chi}cdot bigl|x^{(k+1)}-x^{(k)}bigr|$

(3.12)

или по формуле (эта оценка выражается через два приближения $x^{(0)}$ и $x^{(1)}$ )

$bigl|x^{(k+1)}-x_{ast}bigr|leqslant frac{chi^{k+1}}{1-chi}cdot bigl|x^{(1)}-x^{(0)}bigr|.$

(3.13)

Из оценки следует условие выхода из итерационного процесса. Если значение chi неизвестно, то выход осуществляется по условию

$bigl|x^{(k+1)}-x^{(k)}bigr|leqslant varepsilon.$

2. Уравнение f(x)=0 заменяется равносильным (где знак в правой части выбирается из условия |varphi'(x)|<1 ):

$x=xmp frac{f(x)}{max|f'(x)|}equiv varphi(x)$ при xin G ,

3. Можно выразить из уравнения f(x)=0 так, чтобы для полученного уравнения x=varphi(x) выполнялось условие сходимости |varphi'(x)|<1 в окрестности искомого корня.

Замечание к доказательству. Выполнение условия $Delta_{k+1}= bigl|x^{(k+1)}-x^{(k)}bigr|leqslant varepsilon$ не гарантирует близости к точному решению (на рис. 3.10 достигается область, где условие окончания выполняется, но корень $x_{ast}$ расположен достаточно далеко от этой области).

Итерационный процесс и корень

▼ Примеры 3.8-3.10

Пример 3.8. Методом простых итераций с точностью varepsilon=0,!001 уточнить корень трансцендентного уравнения $x^2-e^{-x}=0$ , причем искомый корень $x_{ast}in[0,!5;1,!0]equiv G$ .

Решение

Пример 3.9. Найти решение уравнения x^3-x+1=0 методом простых итераций с точностью varepsilon_1=0,!01 и varepsilon_2=0,!001 .

Решение

Пример 3.10. Найти корни уравнения x^3-x^2-9x+9=0 методом простых итераций с точностью varepsilon=0,!001 .

Решение

1. Преобразуем уравнение к виду $x=varphi(x)colon, x=sqrt[LARGE{3}]{x^2+9x-9}$ .

В примере 3.3 была выполнена операция отделения корней и получены отрезки [-4;-2],,[0,5;2],,[2;4] .

Можно показать, что на отрезках [2;4],,[-4;-2] функция $varphi(x)= sqrt[LARGE{3}]{x^2+9x-9}$ удовлетворяет условию |varphi'(x)|<1 .

На отрезке [0,!5;2] используем другой вид уравнения: $x=frac{x^3}{9}-frac{x^2}{9}+1$ . Также легко проверить, что функция $varphi(x)=frac{x^3}{9}-frac{x^2}{9}+1$ удовлетворяет достаточному условию сходимости на отрезке [0,!5;2] .

2. В качестве начальных приближений выберем:
– точку $x^{(0)}=-2$ на отрезке [-4;-2] ;
– точку $x^{(0)}=0,!5$ на отрезке [0,!5;-2] ;
– точку $x^{(0)}=2$ на отрезке [2;4] ;.
В поставленной задаче varepsilon=0,!001 .

3,4. Выполним расчеты по формуле

$x^{(k+1)}= sqrt[LARGE{3}]{(x^{(k)})^2+9x^{(k)}-9},quad k=0,1,2,ldots$

с начальными значениями $x^{(0)}=-2$ и $x^{(0)}=2$ и по формуле

$x^{(k+1)}=frac{(x^{(k)})^3}{9}-frac{(x^{(k)})^2}{9}+1,quad k=0,1,2,ldots$

с начальным значением $x^{(0)}=0,!5$ .

Результаты расчетов занесены в табл. 3.6–3.8.

$begin{aligned}& begin{aligned} mathit{Table~3.6}~&\ begin{array}{|c|c|c|c|c|c|c|c|c|c|c|c|c|c|}hline k&! scriptstyle{0}!&! scriptstyle{1}!&! scriptstyle{2}!&! scriptstyle{3}!&! scriptstyle{4}!&! scriptstyle{5}!&! scriptstyle{6}!&! scriptstyle{7}!&! scriptstyle{8}!&! scriptstyle{9}!&! scriptstyle{10}!&! scriptstyle{11}!&! scriptstyle{12}!\hline x^{(k)}&! scriptstyle{2,0000}!&! scriptstyle{2,3513}!&! scriptstyle{2,6056}!&! scriptstyle{2,7694}!&! scriptstyle{2,8682}!&! scriptstyle{2,9255}!&! scriptstyle{2,9582}!&! scriptstyle{2,9767}!&! scriptstyle{2,9870}!&! scriptstyle{2,9927}!&! scriptstyle{2,9959}!&! scriptstyle{2,9977}!&! scriptstyle{2,9987}!\hline bigl|x^{(k)}-x^{(k-1)}bigr|&! -!&! scriptstyle{0,3513}!&! scriptstyle{0,2543}!&! scriptstyle{0,1638}!&! scriptstyle{0,0988}!&! scriptstyle{0,0573}!&! scriptstyle{0,0327}!&! scriptstyle{0,0185}!&! scriptstyle{0,0102}!&! scriptstyle{0,0057}!&! scriptstyle{0,0032}!&! scriptstyle{0,0018}!&! scriptstyle{0,0010}!\hline end{array}& end{aligned}<br />\[6pt] & begin{aligned} mathit{Table~3.7}~&\ begin{array}{|c|c|c|}hline k& x^{(k)}& bigl|x^{(k)}-x^{(k-1)}bigr|\hline 0&-2,!0000&-\hline 1&-2,!8438& 0,!8438\hline 2&-2,!9816& 0,!1378\hline 3&-2,!9979& 0,!0163\hline 4&-2,!9997& 0,!0018\hline 5&-2,!99997& 0,!00027\hline end{array}&end{aligned} qquadqquadqquad begin{aligned} mathit{Table~3.8}~&\ begin{array}{|c|c|c|} hline k& x^{(k)}& bigl|x^{(k)}-x^{(k-1)}bigr|\hline 0& 0,!50000&-\hline 1& 0,!98611& 0,!4861\hline 2& 0,!99849& 0,!01238\hline 3& 0,!99983& 0,!00134\hline 4& 0,!99998& 0,!00015\hline end{array}& end{aligned}end{aligned}$

В результате получены приближенные значения корней:

$x_{1ast}cong-2,!99997,qquad x_{2ast}cong0,!99998,qquad x_{3ast}cong2,!9987.$

Обратим внимание на сильное различие в числе итераций, потребовавшихся для нахождения корней $x_{ast}=3$ (табл. 3.6) и $x_{ast}=-3$ (табл. 3.7), с помощью одной и той же формулы. Заметим, что в окрестности корня $x_{ast}=3$ значения модуля производной функции $varphi(x)=sqrt[LARGE{3}]{x^2+9x-9}$ равны:

С другой стороны, в окрестности корня $x_{ast}=-3$ имеем:

Анализ результатов показывает, что чем меньше значения модуля производной |varphi'(x)| , тем быстрее сходимость.

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

Метод Ньютона (метод касательных, или метод линеаризации) является одним из наиболее популярных численных методов. Он быстро сходится (имеет квадратичную сходимость) и допускает различные модификации, приспособленные для решения векторных задач и сеточных уравнений. Однако этот метод эффективен при весьма жестких ограничениях на характер функции f(x)colon

Геометрическая интерпретация метода Ньютона

1) существование второй производной функции f(x) на множестве G={aleqslant xleqslant b} ;
2) удовлетворение первой производной условию f(x)ne0 для всех xin G ;
3) знакопостоянство f'(x),,f''(x) для всех xin G .

Поэтому его желательно использовать совместно с другими методами, например методом половинного деления, чтобы достигнуть диапазона widetilde{a}leqslant x leqslant widetilde{b} , где указанные условия начинают выполняться.

Геометрическая интерпретация метода Ньютона состоит в следующем. Задается начальное приближение $x^{(0)}$ . Далее проводится касательная к кривой y=f(x) в точке $x^{(0)}$ (рис. 3.11), т.е. кривая заменяется прямой линией. В качестве следующего приближения выбирается точка пересечения этой касательной с осью абсцисс. Процесс построения касательных и нахождения точек пересечения с осью абсцисс повторяется до тех пор, пока приращение не станет меньше заданной величины varepsilon .

Получим расчетную формулу метода Ньютона. Вместо участка кривой (точка соответствует $x_{ast}$ ) возьмем участок — касательную, проведенную в точке $(x^{(0)},f(x^{(0)}))$ ). Для этого отрезка справедливо конечное соотношение:

$frac{f(x^{(0)})-0}{x^{(0)}-x^{(1)}}= f'(x^{(0)})equiv operatorname{tg}alpha,$

где alpha — угол наклона касательной в точке $(x^{(0)},f(x^{(0)}))$ к оси абсцисс. Разрешая это соотношение относительно $x^{(1)}$ , получаем $x^{(1)}= x^{(0)}-frac{f(x^{(0)})}{f'(x^{(0)})}$ . Повторяя процесс, находим общую формулу:

$x^{(k+1)}= x^{(0)}-frac{f(x^{(k)})}{f'(x^{(k)})},quad k=0,1,2,ldots$

(3.14)

Подчеркнем, что если отбросить итерационный индекс, то (3.14) записывается в виде нелинейного уравнения

$x=x-frac{f(x)}{f'(x)}equiv varphi(x),$

(3.15)

которое, однако, на [a,b] не равносильно исходному, а является таковым только в одной точке при $x=x_{ast}$ . Поэтому данный метод не служит разновидностью метода простых итераций.

Применим теперь для вывода формулы (3.14) метод линеаризации. Положим, что итерационный процесс имеет вид

$x^{(k+1)}=x^{(k)}+delta^{(k)},quad k=0,1,2,ldots$

(3.16)

где $delta^{(0)}$ — поправка к k-му приближению, которую необходимо найти. Предполагая, что f(x) имеет непрерывную вторую производную, разложим $f(x^{(k)}+delta^{(k)})$ по формуле Тейлора относительно точки $x^{(k)}colon$

$f(x^{(k)}+delta^{(k)})= f(x^{(k)})+ delta^{(k)}f'(x^{(k)})+ frac{1}{2}(delta^{(k)})^2 f''(xi),$

где $xiin bigl(x^{(k)},x^{(k+1)}bigr)$ . Учитывая, что $fbigl(x^{(k)}+ delta^{(k)}bigr)=0$ (это соответствует нахождению точки пересечения с осью абсцисс), и оставляя только линейную (относительно $delta^{(k)}$ ) часть разложения (отсюда и название — метод линеаризации), записываем линейное относительно $delta^{(k)}$ уравнение

$f(x^{(k)})+ delta^{(k)} f'(x^{(k)})=0.$

Отсюда выражается поправка $delta^{(k)}=-frac{f(x^{(k)})}{f'(x^{(k)})}$ . Подставляя $delta^{(k)}$ в (3.16), получаем (3.14).

Теорема 3.11 (о достаточных условиях сходимости метода Ньютона). Пусть выполняются следующие условия:

1. Функция f(x) определена и дважды дифференцируема на [a,b] .

2. Отрезку [a,b] принадлежит только один простой корень $x_{ast}$ , так что f(a)cdot f(b)<0 .

3. Производные f'(x),,f''(x) на [a,b] сохраняют знак, и f'(x)ne0 .

4. Начальное приближение $x^{(0)}$ удовлетворяет неравенству $f(x^{(0)})cdot f''(x^{(0)})>0$ (знаки функций f(x) и f''(x) в точке $x^{(0)}$ совпадают).

Тогда с помощью метода Ньютона (3.14) можно вычислить корень уравнения f(x)=0 с любой точностью.

Замечания

1. Метод Ньютона характеризуется вторым порядком сходимости вблизи корня и первым порядком — вдали от него. Данную оценку проверяем для двух случаев, когда $x^{(k)}$ находится далеко от корня $x_{ast}$ (это возможно на первых итерациях) и когда $x^{(k)}$ располагается вблизи $x_{ast}$ .

Первый случай. Пусть отрезок $omega=[x^{(k)},x_{ast}]$ не мал. Тогда на основе теоремы Лагранжа получим (где $m_1=minlimits_{omega}|f'(x)|$ )

$bigl|f(x^{(k)})bigr|= bigl|f(x_{ast})-f(x^{(k)})bigr|= bigl|f'(xi)bigr|cdot bigl|x_{ast}-x^{(k)}bigr| geqslant m_1 bigl|x_{ast}-x^{(k)}bigr|.$

(3.17)

Преобразуем с использованием (3.17) итерационную формулу (3.14) (где $M_1= maxlimits_{xin[a,b]}|f'(x)|$ ):

$x^{(k+1)}=x^{(k)}-frac{f(x^{(k)})}{f'(x^{(k)})};qquad bigl|x^{(k+1)}-x^{(k)}bigr|= frac{|f(x^{(k)})|}{f'(x^{(k)})} geqslant frac{m_1}{M_1} bigl|x_{ast}-x^{(k)}bigr|.$

В силу монотонности последовательности $x^{(0)},x^{(1)},ldots$ имеем

$begin{gathered}x_{ast}-x^{(k+1)}= x_{ast}-x^{(k)}-bigl(x^{(k+1)}-x^{(k)}bigr),\ bigl|x_{ast}-x^{(k+1)}bigr|= bigl|x_{ast}-x^{(k)}bigr|-bigl|x^{(k+1)}-x^{(k)}bigr| geqslant bigl|x_{ast}-x^{(k)}bigr|- frac{m_1}{M_1} bigl|x_{ast}-x^{(k)}bigr|= left(1-frac{m_1}{M_1}right)! bigl|x_{ast}-x^{(k)}bigr|. end{gathered}$

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

$bigl|x_{ast}-x^{(k+1)}bigr| leqslant ccdot bigl|x_{ast}-x^{(k)}bigr|$ , где $0 leqslant c=1-frac{m_1}{M_1}<1$ .

Второй случай. Пусть теперь отрезок $omega=[x^{(k)},x]$ мал, т.е. итерации выполняются вблизи корня. Тогда, полагая, что указанные выше предположения 1–4 теоремы 3.10 выполнены, разложим функцию f(x) в окрестности корня $x_{ast}$ относительно точки $x^{(k)}$ , учитывая члены до второго порядка. Получим

$Bigl.{f(x)}Bigr|_{x=x^{(k)}}= f(x^{(k)})+ bigl(x_{ast}-x^{(k)}bigr) f'(x^{(k)})+ bigl(x_{ast}-x^{(k)}bigr)^2 frac{1}{2}f''(xi)=0,$

где $xiin bigl(x^{(k)}-delta,,x^{(k)}+deltabigr)$ ( delta>0 — малая величина). Из данного соотношения выражаем $x_{ast}colon$

$x_{ast}=x^{(k)}-frac{f(x^{(k)})}{f'(x^{(k)})}-frac{(x_{ast}-x^{(k)})^2}{2f'(x^{(k)})},f''(xi).$

Но первые два слагаемых в правой части в соответствии с (3.14) равны $x^{(k+1)}$ . Тогда будем иметь

$x_{ast}-x^{(k)}=-frac{(x_{ast}-x^{(k)})^2}{2f'(x^{(k)})},f''(xi).$

Из последнего соотношения следует оценка погрешности (k+1)-го приближения через погрешность k-го приближения:

$bigl|x_{ast}-x^{(k+1)}bigr|leqslant frac{M_2}{2m_1} bigl|x_{ast}-x^{(k)}bigr|^2,$

(3.18)

где принято $M_2=maxlimits_{omega}|f''(x)|,~ m_1=minlimits_{omega}|f'(x)|$ . Оценка (3.18) свидетельствует о квадратичной сходимости метода касательных вблизи корня. С вычислительной точки зрения это означает, что на каждом приближении количество верных цифр результата удваивается.

2. Для нахождения комплексных корней уравнения f(z)=0 можно также использовать (3.14) в форме (где z=x+iy — комплексная переменная)

$z^{(k+1)}=z^{(k)}-frac{f(z^{(k)})}{f'(z^{(k)})},quad k=0,1,2,ldots$

Метод Ньютона может применяться не только для нахождения простых корней, но для определения кратных корней, т.е. когда на отрезке [a,b] содержащем корень, не выполняется условие f(a)cdot f(b)<0 (условие 2 теоремы 3.11). Наряду с теоремой 3.11 удобно также пользоваться следующей теоремой.

Достаточные условия сходимости метода Ньютона

Теорема 3.12 (достаточные условия сходимости метода Ньютона). Пусть:

а) дана функция f(x)colon Dto mathbb{R} , где — открытый интервал, и $f'(x)in operatorname{Lip}_{gamma}(D)$ ;

б) для некоторого rho>0 выполняется условие |f'(x)|leqslantrho при всех из .

Если уравнение f(x)=0 имеет решение $x_{ast}in D$ , то существует некоторое eta>0 , такое, что если $|x^{(0)}-x_{ast}|<eta$ , то последовательность $bigl{x^{(0)},x^{(1)},x^{(2)},ldotsbigr}$ , задаваемая формулой (3.14), существует и сходится к $x_{ast}$ . Более того, справедлива оценка

$bigl|x^{(k+1)}-x_{ast}bigr| leqslant frac{gamma}{2rho} bigl|x^{(k)}-x_{ast}bigr|^2,quad k=0,1,2,ldots$

Здесь обозначение $f'(x)in operatorname{Lip}_{gamma}(D)$ означает, что функция f'(x) непрерывна по Липшицу с константой gamma на множестве , то есть |f'(x)-f'(y)| leqslant gamma cdot|x-y| для любых x,,y из .

Замечания

1. Требование теоремы 3.12, чтобы производная f'(x) имела ненулевую нижнюю границу в , определяет, что значение $f'(x_{ast})$ должно быть ненулевым для квадратичной сходимости метода Ньютона. Если же $f'(x_{ast})=0$ , то $x_{ast}$ является кратным корнем, а метод Ньютона сходится лишь линейно.

2. Выполнение условий теоремы 3.12 гарантирует сходимость метода Ньютона только из “хорошего” начального приближения $x^{(0)}$ .

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

Методика решения задачи

1. Задать начальное приближение $x^{(0)}$ так, чтобы выполнялось неравенство $f(x^{(0)})cdot f''(x^{(0)})>0$ , а также малое положительное число varepsilon . Положить k=0 .

2. Вычислить $x^{(k+1)}$ по формуле $x^{(k+1)}= x^{(k)}-frac{f(x^{(k)})}{f'(x^{(k)})}$ .

3. Если $|x^{(k+1)}-x^{(k)}|leqslant varepsilon$ , процесс завершить и положить $x_{ast}cong x^{(k+1)}$ .

Если $|x^{(k+1)}-x^{(k)}|>varepsilon$ , положить k=k+1 и перейти к п.2.

▼ Примеры 3.11-3.14

Пример 3.11. Методом Ньютона с точностью varepsilon=0,!001 уточнить корень трансцендентного уравнения $x^2-e^{-x}=0$ , причем искомый корень $x_{ast}in[0,!5;1,!0]equiv G$ .

Решение

Можно проверить, что на множестве удовлетворяются условия 1, 2, 3 теоремы 3.11, обеспечивающие сходимость метода касательных.

1. Зададим начальное приближение из условия 4. Так как для $f(x)=x^2-e^{-x}$ справедливо $f''(x)=2-e^{-x}>0$ на множестве G,~ f(a)=f(0,!5)<0, f(b)=f(1)>0 , то f(1)cdot f''(1)>0 , поэтому $x^{(0)}=1$ .

2,3. Результаты расчетов по формуле (3.14) $x^{(k+1)}= x^{(k)}-frac{(x^{(k)})^2-e^{-x^{(k)}}}{2x^{(k)}+e^{-x^{(k)}}},~k=0,1,2,ldots$ помещены в табл. 3.9.

$begin{aligned} mathit{Table~3.9}~&\ begin{array}{|c|c|c|c|c|} hline k& 0& 1& 2& 3\hline begin{matrix}{}\[-8pt]{}end{matrix} x^{(k)}& 1,!000& 0,!73304& 0,!70381& 0,!703467\hline begin{matrix}{}\[-8pt]{}end{matrix} bigl|x^{(k)}-x^{(k-1)}bigr|&-& 0,!27& 0,!029& 0,!00034\hline begin{matrix}{}\[-8pt]{}end{matrix} f(x^{(k)})& 0,!63212& 0,!05690& 0,!00065& 8,!25cdot10^{-7}\hline end{array}& end{aligned}$

Из табл. 3.9 можно сделать следующие выводы:

1. Для достижения заданной точности, проверяемой по модулю разности $bigl|x^{(k)}-x^{(k-1)}bigr|$ , потребовалось выполнить три приближения. Если же выход организовать по условию $bigl|f(x^{(k)})bigr|leqslant varepsilon$ , то достаточно двух приближений.

2. Вблизи корня $x_{ast}$ количество верных цифр в результатах $x^{(k)}$ удваивается, так что все цифры в $x^{(3)}$ являются верными, тогда как в $x^{(2)}$ верными являются первые три цифры после запятой.

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

Пример 3.12. Методом Ньютона найти корень уравнения x^3-x+1=0 .

Решение

Пример 3.13. Найти корни уравнения x^3-x^2-9x+9=0 методом Ньютона с точностью varepsilon=0,!001 .

Решение

Процедура отделения корней была выполнена в примере 3.3. В качестве отрезков [a_i;b_i] , которым принадлежат корни уравнения, выберем [-4;-2], [2,!5;4], [0,!5;2] .

Так как f(-4)=-3,!5;~ f(-2)=15 , то есть f(-4)f(-2)<0 , производные f''(x)=6x-2<0, f'(x)=3x^2-2x-9>0 сохраняют знак при xin[-4;-2] , то условия сходимости выполняются.

Так как f(2,!5)=-4,!125;~ f(4)=21 , то есть f(2,!5)f(4)<0 , и производные f'(x)>0,~ f''(x)>0 сохраняют знак при xin[2,!5;4] , то условия сходимости на этом отрезке тоже выполняются.

Так как f(0,!5)=4,!375;~ f(2)=-5 , то есть f(0,!5)f(2)<0 , и производные f'(x)<0,~ f''(x)>0 сохраняют знак при xin[0,!5;2] , то условия сходимости выполняются.

1. Зададим начальные приближения: на отрезке [0,!5;2] выберем $x^{(0)}= 0,!5$ , так как f(0,!5)cdot f''(0,!5)>0 ; на отрезке [-4;-2] выберем $x^{(0)}=-4$ , так как f(4)cdot f''(4)>0 ; аналогично на отрезке [2,!5;4] выберем $x^{(0)}=4$ . В поставленной задаче varepsilon= 0,!001 .

2,3. Результаты расчетов по формуле (3.14) $x^{(k+1)}= x^{(k)}-frac{(x^{(k)})^3-(x^{(k)})^2-9x^{(k)}+9}{3(x^{(k)})^2-2x^{(k)}-9},~ k=0,1,2,ldots$ приведены в табл. 3.11–3.13.

$begin{aligned}& begin{aligned} mathit{Table~3.11}~&\ begin{array}{|c|c|c|c|c|c|} hline k& 0& 1& 2& 3& 4 \hline begin{matrix}{}\[-8pt]{}end{matrix} x^{(k)}&-4,!00000&-3,!255319&-3,!023383&-3,!000225&-3,!000000 \hline begin{matrix}{}\[-8pt]{}end{matrix} bigl|x^{(k)}-x^{(k-1)}bigr|&-& 0,!744681& 0,!231936& 0,!023158& 0,!000225 \hline end{array}& end{aligned}\[2pt] & begin{aligned} mathit{Table~3.12}~&\ begin{array}{|c|c|c|c|c|} hline k& 0& 1& 2& 3 \hline begin{matrix}{}\[-8pt]{}end{matrix} x^{(k)}&0,!5000& 0,!972973& 0,!9998246& 1,!0000000 \hline begin{matrix}{}\[-8pt]{}end{matrix} bigl|x^{(k)}-x^{(k-1)}bigr|&-& 0,!472973& 0,!0268516& 0,!0001754 \hline end{array}& end{aligned}\[2pt] & begin{aligned} mathit{Table~3.13}~&\ begin{array}{|c|c|c|c|c|c|c|} hline k& 0& 1& 2& 3& 4& 5 \hline begin{matrix}{}\[-8pt]{}end{matrix} x^{(k)}& 4,!0000& 3,!322581& 3,!051484& 3,!001674& 3,!000002& 3,!0000 \hline begin{matrix}{}\[-8pt]{}end{matrix} bigl|x^{(k)}-x^{(k-1)}bigr|&-& 0,!6774194& 0,!2710969& 0,!049809& 0,!001671& 2cdot10^{-6} \hline end{array}& end{aligned} end{aligned}$

В результате получены приближенные значения корней:

$x_{ast1}cong-3,!0000;qquad x_{ast2}cong1,!0000;qquad x_{ast3}cong 3,!0000.$

Пример 3.14. Найти корень уравнения x^2-2x+1=0 методом Ньютона с точностью varepsilon=0,!01 .

Решение

Очевидно, уравнение имеет один кратный корень $x_{ast}=1$ . Согласно замечанию к теореме 3.12 применение метода Ньютона для решения поставленной задачи сопровождается линейной сходимостью (табл. 3.14).

$begin{aligned} mathit{Table~3.14}~&\ begin{array}{|c|c|c|c|c|c|c|c|c|} hline k& 0& 1& 2& 3& 4& 5& 6& 7\hline begin{matrix}{}\[-8pt]{}end{matrix} x^{(k)}& 2& 1,!5& 1,!25& 1,!125& 1,!0625& 1,!03125& 1,!015625& 1,!007813 \hline begin{matrix}{}\[-8pt]{}end{matrix} bigl|x^{(k)}-x^{(k-1)}bigr|&-& 0,!5& 0,!25& 0,!125& 0,!0625& 0,!03125& 0,!015625& 0,!0078125 \hline end{array}& end{aligned}$

Полученное приближенное решение $x_{ast}cong1,!007813$ .

Нарушение знакопостоянства производных функции

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

Метод касательных, являясь весьма эффективным средством численного анализа, к сожалению, имеет достаточно жесткие ограничения. Действительно, он не может применяться для сеточных уравнений (см. рис. 3.2); при нарушении знакопостоянства производных (рис. 3.12); при существовании неограниченных вторых производных и др. Так, если даже условие знакопостоянства нарушено вдали от корня, где выбрано $x^{(0)}$ , а вблизи корня выполняется, то все равно метод касательных неприменим (см. рис. 3.12), если не произвести сужения начального отрезка.

Кроме того, если функция f(x) очень сложная, то будет сложной и ее производная, и поэтому на каждой итерации приходится рассчитывать две функции, что снижает эффективность метода касательных.

Процесс последовательных приближений по методу Ньютона

В силу этого в ряде случаев могут оказаться более предпочтительными модификации метода касательных. Рассмотрим три из них.

Упрощенный метод Ньютона. Методика его применения совпадает с изложенной ранее, но вместо формулы (3.14) используется

$x^{(k+1)}=x^{(k)}-frac{f(x^{(k)})}{f'(x^{(0)})},quad k=0,1,2,ldotsqquad mathsf{(3.19)}$

Отличие от метода Ньютона заключается в том, что производная функции f(x) подсчитывается только в точке начального приближения, а на последующих итерациях не уточняется. Процесс последовательных приближений отражен на рис. 3.13. Первая итерация совпадает с первой итерацией метода Ньютона. На последующих итерациях соответствующие отрезки параллельны касательной, проведенной в начальной точке.

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

Пример 3.15. Найти корень уравнения x^3-x+1=0 упрощенным методом Ньютона.

Решение

Корень уравнения отделен в примере 3.2: $x_{ast}in[-2;-1]$ .

1. Выберем начальное приближение $x^{(0)}=-2$ и зададим varepsilon_1=0,!01 и varepsilon_2=0,!001 .

2,3. Выполним расчеты по формуле (3.19):

$x^{(k+1)}= x^{(k)}-frac{(x^{(k)})^3-x^{(k)}+1}{3(x^{(0)})^2-1}= x^{(k)}-frac{(x^{(k)})^3-x^{(k)}+1}{11},quad k=0,1,2,ldots$

Результаты расчетов приведены в табл. 3.15.

$begin{aligned} mathit{Table~3.15}~&\ begin{array}{|c|c|c||c|c|c|} hline begin{matrix} {}\[-6pt]{}end{matrix} k& x^{(k)}& bigl|x^{(k)}-x^{(k-1)}bigr|& k& x^{(k)}& bigl|x^{(k)}-x^{(k-1)}bigr|\hline 0&-2,!00001&-& 6&-1,!3388& 0,!0092\hline 1&-1,!5455& 0,!4545& 7&-1,!3333& 0,!0005\hline 2&-1,!4413& 0,!1042& 8&-1,!3299& 0,!00034\hline 3&-1,!3911& 0,!0502& 9&-1,!3279& 0,!002\hline 4&-1,!3637& 0,!0274& 10&-1,!3267& 0,!0012\hline 5&-1,!348& 0,!0157& 11&-1,!3259& 0,!0008\hline end{array}& end{aligned}$

При varepsilon=0,!01 получено решение $x_{ast}cong-1,!3388$ , а при varepsilon=0,!001 — решение $x_{ast}cong-1,!3259$ . Очевидно, по сравнению с методом Ньютона сходимость замедляется (см. пример 3.12).

Метод Ньютона-Бройдена

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

$x^{(k+1)}= x^{(k)}-c_kcdot frac{f(x^{(k)})}{f'(x^{(k)})},quad k=0,1,2,ldots$

(3.20)

где c_k — число, которое выбирается на каждой итерации так, чтобы уменьшить значение $bigl|f(x^{(k+1)})bigr|$ по сравнению с $bigl|f(x^{(k)})bigr|$ . При c_k=1 метод Ньютона-Бройдена совпадает с методом Ньютона.

Как правило, при плохой сходимости или ее отсутствии полагают 0<c_k<1 (рис. 3.14,д), а при хорошей сходимости для c_k=1 полагают c_k>1 (это ускоряет сходимость (рис. 3.14,б)).

Сходимость при методе Ньютона-Бройдена

На рис. 3.14 прямоугольниками отмечены точки $x^{(1)}$ , полученные при $c_0=1,~ delta^{(k)}= frac{f(x^{(k)})}{f'(x^{(k)})},~k=0,1,2,ldots$ , — поправка, соответствующая методу Ньютона, а точки $x^{(1)}=x^{(0)}-c_0delta^{(0)}$ получены по методу Ньютона-Бройдена.

Тангенс угла наклона секущей

Метод секущих

В этом методе производная функции f(x) подсчитывается с помощью конечно-разностных соотношений:

– в точке $x^{(0)}$ используется формула $f'(x^{(0)})approx frac{f(x^{(0)})-f(x^{(0)}-delta)}{delta}$ , где delta — малая положительная величина;

– в точках $x^{(k)},~k=1,2,ldots$ , используется формула $f'(x^{(k)})approx frac{f(x^{(k)})-f(x^{(k-1)})}{x^{(k)}-x^{(k-1)}}$ .

Вычисленное значение $f'(x^{(k)})$ определяет тангенс угла наклона секущей (рис. 3.15).

Методика применения метода секущих совпадает с описанной ранее, но вместо (3.14) используется формула

$x^{(k+1)}= x^{(k)}-frac{f(x^{(k)})}{f(x^{(k)})-f(x^{(k-1)})}cdot bigl(x^{(k)}-x^{(k-1)}bigr),quad k=1,2,ldots$

(3.21)

Аппроксимация сеточной функции

Замечания

1. Метод секущих является более экономичным по сравнению с методом Ньютона по количеству функций, подлежащих расчету: на каждой итерации в методе секущих необходимо рассчитать только значение $f(x^{(k)})$ , так как величина $f(x^{(k-1)})$ уже подсчитана на предыдущей итерации.

2. Метод секущих может применяться и для решения сеточных уравнений. Для сеточной функции производные в методе секущих определяются так же, но для определения $f(x^{(k)})$ в промежуточных точках осуществляется аппроксимация (как правило, интерполяция) функции f(x_i) (рис. 3.16). На этом рисунке штриховой линией показана аппроксимационная кривая.

3. Для всех описанных модификаций скорость сходимости по сравнению с методом касательных снижается: p<2 . Однако для некоторых из них (метод секущих) значение p>1 и может достигать p=1,!5 .

Пример 3.16. Методом секущих найти корень уравнения x^3-x+1=0 с точностью varepsilon=0,!001 .

Решение

1. Зададим начальное приближение $x^{(0)}=-2$ (см. пример 3.12).

2. Для вычисления $f'(x^{(0)})$ зададим delta=0,!1 . Тогда

$f'(x^{(0)})cong frac{f(-2)-f(-2,!1)}{0,!1}= frac{-5-(-6,!161)}{0,!1}= 11,!61.$

Отсюда $x^{(1)}= x^{(0)}-frac{f(x^{(0)})}{f'(x^{(0)})}=-2-frac{-5}{11,!61}=-1,!36934$ .

Дальнейшие расчеты выполняются по формуле (3.21):

$begin{aligned}x^{(2)}&=x^{(1)}-frac{f(x^{(1)})}{f(x^{(1)})-f(x^{(0)})}cdot bigl(x^{(1)}-x^{(0)}bigr)=-1,!56934-frac{-1,!29567}{3,!704325}cdot0,!43066=-1,!41871;\[2pt] x^{(3)}&=x^{(2)}-frac{f(x^{(2)})}{f(x^{(2)})-f(x^{(1)})}cdot bigl(x^{(2)}-x^{(1)}bigr)=-1,!41871-frac{-1,!43678}{0,!858893}cdot0,!15063=-1,!34211;\[2pt] x^{(4)}&=x^{(3)}-frac{f(x^{(3)})}{f(x^{(3)})-f(x^{(2)})}cdot bigl(x^{(3)}-x^{(2)}bigr)=-1,!34211-frac{-1,!07538}{0,!361404}cdot0,!0766=-1,!32613;\[2pt] x^{(5)}&=x^{(4)}-frac{f(x^{(4)})}{f(x^{(4)})-f(x^{(3)})}cdot bigl(x^{(4)}-x^{(3)}bigr)=-1,!32613-frac{-1,!00603}{0,!069348}cdot0,!01598=-1,!32474;\[2pt] x^{(6)}&=x^{(5)}-frac{f(x^{(5)})}{f(x^{(5)})-f(x^{(4)})}cdot bigl(x^{(5)}-x^{(4)}bigr)=-1,!32474-frac{-1,!000139}{0,!005936}cdot0,!00139=-1,!32472cong x_{ast}.\[2pt] end{aligned}$

Результаты расчетов приведены в табл. 3.16.

$begin{aligned} mathit{Table~3.16}~&\ begin{array}{|c|c|c|c|c|c|c|c|} hline k& 0& 1& 2& 3& 4& 5& 6\hline begin{matrix}{}\[-8pt]{}end{matrix} x^{(k)}&-2,!00000&-1,!56934&-1,!41871&-1,!34211&-1,!32613&-1,!32474&-1,!32472\hline begin{matrix}{}\[-8pt]{}end{matrix} bigl|x^{(k)}-x^{(k-1)}bigr|&-& 0,!43066& 0,!15063& 0,!07660& 0,!01598& 0,!00139& 0,!00002 \hline end{array}& end{aligned}$

Очевидно, метод сходится чуть хуже метода Ньютона (см. пример 3.12), однако скорость сходимости выше линейной.

Математический форум (помощь с решением задач, обсуждение вопросов по математике).

Кнопка "Поделиться"

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

Источник

Описание метода[править | править код]

Обоснование[править | править код]

Геометрическая интерпретация[править | править код]

Алгоритм[править | править код]

Пример[править | править код]

Условия применения[править | править код]

Контрпримеры[править | править код]

Ограничения[править | править код]

Историческая справка[править | править код]

Обобщения и модификации[править | править код]

Метод секущих[править | править код]

Метод одной касательной[править | править код]

Метод Ньютона-Фурье[править | править код]

Многомерный случай[править | править код]

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

Метод Ньютона — Рафсона[править | править код]

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

Метод Гаусса — Ньютона[править | править код]

Обобщение на комплексную плоскость[править | править код]

Реализация[править | править код]

Scala[править | править код]

Python[править | править код]

PHP[править | править код]

Octave[править | править код]

Delphi[править | править код]

C++[править | править код]

C[править | править код]

Haskell[править | править код]

Литература[править | править код]

См. также[править | править код]

Ссылки[править | править код]

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

Точное значение корня

Абсолютная и относительная погрешность вычисления

#Описание алгоритма

#Поиск квадратных корней

#Скорость сходимости

Содержание

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

Геометрическая интерпретация: метод касательных

Чувствительность корней

Развитие

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

Обобщения

Целые числа

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

Системы нелинейных уравнений с несколькими неизвестными

Задачи

Источники

Численные методы решения нелинейных уравнений

Корни нелинейных уравнений

Отделение корней уравнения

Способы отделения корней

Метод половинного деления

Алгоритм метода половинного деления

Метод хорд

Метод простых итераций

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

Достаточные условия сходимости метода Ньютона

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

Метод Ньютона-Бройдена

Метод секущих

Вам также может понравиться

Как в горизонте найти топливный элемент

Как найти по фамилии телефон алматы

Как составить характеристику для сотрудников

Добавить комментарий Отменить ответ