Метод Ньютона
Инструкция . Введите выражение F(x) , нажмите Далее . Полученное решение сохраняется в файле Word . Также создается шаблон решения в Excel .
- Решение онлайн
- Видеоинструкция
- Оформление Word
Правила ввода функции, заданной в явном виде
- Примеры правильного написания F(x) :
- 10•x•e 2x = 10*x*exp(2*x)
- x•e -x +cos(3x) = x*exp(-x)+cos(3*x)
- x 3 -x 2 +3 = x^3-x^2+3
- Выражение 0.9*x=sin(x)+1 необходимо преобразовать к виду: sin(x)+1-0.9*x . Аналогично, x^2-7=5-3x к виду x^2+3x-12 .
Пусть дано уравнение f(x)=0 , где f(x) определено и непрерывно в некотором конечном или бесконечном интервале a ≤ x ≤ b . Всякое значение ξ, обращающее функцию f(x) в нуль, то есть такое, что f(ξ)=0 называется корнем уравнения или нулем функции f(x) . Число ξ называется корнем k -ой кратности, если при x = ξ вместе с функцией f(x) обращаются в нуль ее производные до (k-1) порядка включительно: f(ξ)=f’(ξ)= … =f k-1 (ξ) = 0 . Однократный корень называется простым.
Приближенное нахождение корней уравнения складывается из двух этапов:- Отделение корней, то есть установление интервалов [αi,βi] , в которых содержится один корень уравнения.
- f(a)•f(b) , т.е. значения функции на его концах имеют противоположные знаки.
- f’(x) сохраняет постоянный знак, т.е. функция монотонна (эти два условия достаточны, но НЕ необходимы) для единственности корня на искомом отрезке).
- f”(x) сохраняет постоянный знак, т.е. функция выпукла вверх, либо – вниз.
- Уточнение приближенных корней, то есть доведение их до заданной точности.
Геометрическая интерпретация метода Ньютона (метод касательных)
Критерий завершения итерационного процесса имеет вид
Метод Ньютона
Единственные требования, накладываемые на функцию $f$ — что у неё есть хотя бы один корень и что она непрерывна и дифференцируема на интервале поиска.
#Описание алгоритма
Алгоритм начинает с какого-то изначального приближения $x_0$ и затем итеративно строит лучшее решение, строя касательную к графику в точке $x = x_i$ и присваивая в качестве следующего приближения $x_$ координату пересечения касательной с осью $x$. Интуиция в том, что если функция $f$ «хорошая», и $x_i$ уже достаточно близок к корню, то $x_$ будет ещё ближе.
Чтобы получить точку пересечения для $x_i$, нужно приравнять уравнение касательной к нулю:
$$ 0 = f(x_i) + (x_ — x_i) f'(x_i) $$ откуда можно выразить $$ x_ = x_i — \frac
$$ Метод Ньютона крайне важен в вычислительной математике: в большинстве случаев именно он используется для нахождения численных решений уравнений.
#Поиск квадратных корней
В качестве конкретного примера рассмотрим задачу нахождения квадратных корней, которую можно переформулировать как решение следующего уравнения:
$$ x = \sqrt n \iff x^2 = n \iff f(x) = x^2 — n = 0 $$ Если в методе Ньютона подставим $f(x) = x^2 — n$, мы получим следующее правило: $$ x_ = x_i — \frac
<2 x_i>= \frac <2>$$ Если нам нужно посчитать корень с некоторой заданной точностью $\epsilon$, можно на каждой итерации делать соответствующую проверку:
Алгоритм успешно сходится к правильному ответу для многих функций, однако это происходит надежно и доказуемо только для определенного множества функций (например, выпуклых). Другой вопрос — как быстра эта сходимость, если она происходит.
#Скорость сходимости
Запустим метод Ньютона для поиска квадратного корня $2$, начиная с $x_0 = 1$, и посмотрим, сколько первых цифр оказались правильными после каждой итерации:
Можно заметить, что число корректных цифр примерно удваивается после каждой итерации. Такая прекрасная скорость сходимости не просто совпадение.
Чтобы оценить скорость сходимости численно, рассмотрим небольшую относительную ошибку $\delta_i$ на $i$-ой итерации и посмотрим, насколько меньше станет ошибка $\delta_$ на следующей итерации.
$$ |\delta_i| = \frac<|x_n - x|>
$$ В терминах относительных ошибок, мы можем выразить $x_i$ как $x \cdot (1 + \delta_i)$. Подставляя это выражение в формулу для следующей итерации и деля обе стороны на $x$ получаем $$ 1 + \delta_ = \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_$, получаем
что означает, что относительная ошибка примерно возводится в квадрат и делится пополам на каждой итерации, когда мы уже близки к решению. Так как логарифм $(- \log_ <10>\delta_i)$ примерно равен числу правильных значимых цифр числа $x_i$, возведение ошибки в квадрат соответствует удвоению значимых цифр ответа, что мы и наблюдали ранее.
Это свойство называется квадратичной сходимостью, и оно относится не только к нахождению квадратных корней. Оставляя формальное доказательство в качестве упражнения, можно показать, что в общем случае
$$ |\delta_| = \frac<|f''(x_i)|> <2 \cdot |f'(x_n)|>\cdot \delta_i^2 $$ что означает хотя бы квадратичную сходимость при нескольких дополнительных предположениях, а именно что $f'(x)$ не равна нулю и $f»(x)$ непрерывна.
Численные методы решения нелинейных уравнений. Метод Ньютона для решения уравнений с одной переменной
Численные методы решения нелинейных уравнений. Метод Ньютона для решения уравнений с одной переменной
Метод Ньютона (также известный как метод касательных) — это итерационный численный метод нахождения корня (нуля) заданной функции. Метод был впервые предложен английским физиком, математиком и астрономом Исааком Ньютоном (1643-1727), под именем которого и обрёл свою известность.
Метод был описан Исааком Ньютоном в рукописи De analysi per aequationes numero terminorum infinitas ( лат .О б анализе уравнениями бесконечных рядов), адресованной в 1669 году Барроу , и в работе De metodis fluxionum et serierum infinitarum ( лат.Метод флюксий и бесконечные ряды) или Geometria analytica ( лат.Аналитическая геометрия) в собраниях трудов Ньютона, которая была написана в 1671 году. Однако описание метода существенно отличалось от его нынешнего изложения: Ньютон применял свой метод исключительно к полиномам. Он вычислял не последовательные приближения xn , а последовательность полиномов и в результате получал приближённое решение x.
Впервые метод был опубликован в трактате Алгебра Джона Валлиса в 1685 году, по просьбе которого он был кратко описан самим Ньютоном. В 1690 году Джозеф Рафсон опубликовал упрощённое описание в работе Analysis aequationum universalis (лат. Общий анализ уравнений). Рафсон рассматривал метод Ньютона как чисто алгебраический и ограничил его применение полиномами, однако при этом он описал метод на основе последовательных приближений xn вместо более трудной для понимания последовательности полиномов, использованной Ньютоном.
Наконец, в 1740 году метод Ньютона был описан Томасом Симпсоном как итеративный метод первого порядка решения нелинейных уравнений с использованием производной в том виде, в котором он излагается здесь. В той же публикации Симпсон обобщил метод на случай системы из двух уравнений и отметил, что метод Ньютона также может быть применён для решения задач оптимизации путём нахождения нуля производной или градиента.
В соответствии с данным методом задача поиска корня функции сводится к задаче поиска точки пересечения с осью абсцисс касательной, построенной к графику функции .
Рис.1 . График изменение функции
Проведенная в любой точке касательная линия к графику функции определяется производной данной функции в рассматриваемой точке, которая в свою очередь определяется тангенсом угла α ( ). Точка пересечения касательной с осью абсцисс определяется исходя из следующего соотношения в прямоугольном треугольнике: тангенс угла в прямоугольном треугольнике определяется отношением противолежащего катета к прилежащему катету треугольнику. Таким образом, на каждом шаге строится касательная к графику функции в точке очередного приближения . Точка пересечения касательной с осью Ox будет являться следующей точкой приближения . В соответствии с рассматриваемым методом расчет приближенного значения корня на i -итерации производится по формуле:
Наклон прямой подстраивается на каждом шаге наилучшим образом, однако следует обратить внимание на то, что алгоритм не учитывает кривизну графика и следовательно в процессе расчета остается неизвестно в какую сторону может отклониться график.
Условием окончания итерационного процесса является выполнение следующего условия:
где ˗ допустимая погрешность определения корня.
Метод обладает квадратичной сходимостью. Квадратичная скорость сходимость означает, что число верных знаков в приближённом значении удваивается с каждой итерацией.
Математическое обоснование
Пусть дана вещественная функция , которая определена и непрерывна на рассматриваемом участке. Необходимо найти вещественный корень рассматриваемой функции.
Вывод уравнения основано на методе простых итераций, в соответствии с которым уравнение приводят к эквивалентному уравнению при любой функции . Введем понятие сжимающего отображения, которое определяется соотношением .
Для наилучшей сходимости метода в точке очередного приближения должно выполняться условие . Данное требование означает, что корень функции должен соответствовать экстремуму функции .
Производная сжимающего отображения определяется в следующем виде:
Выразим из данного выражение переменную при условии принятого ранее утверждения о том, что при необходимо обеспечить условие . В результате получим выражение для определения переменной :
С учетом этого сжимающая функция прием следующий вид:
Таким образом, алгоритм нахождения численного решения уравнения сводится к итерационной процедуре вычисления:
Алгоритм нахождения корня нелинейного уравнения по методу Ньютона для уравнения с одной переменной
1. Задать начальную точку приближенного значения корня функции , а также погрешность расчета (малое положительное число ) и начальный шаг итерации ( ).
2. Выполнить расчет приближенного значения корня функции в соответствии с формулой:
3. Проверяем приближенное значение корня на предмет заданной точности, в случае:
— если разность двух последовательных приближений станет меньше заданной точности , то итерационный процесс заканчивается.
— если разность двух последовательных приближений не достигает необходимой точности , то необходимо продолжить итерационный процесс и перейти к п.2 рассматриваемого алгоритма.
Пример решения уравнений
по методу Ньютона для уравнения с одной переменной
В качестве примера, рассмотрим решение нелинейного уравнения методом Ньютона для уравнения с одной переменной . Корень необходимо найти с точностью в качестве первого приближения .
Вариант решения нелинейного уравнения в программном комплексе MathCAD представлен на рисунке 3.
Результаты расчетов, а именно динамика изменения приближенного значения корня, а также погрешности расчета от шага итерации представлены в графической форме (см. рис.2).
Рис.2 . Результаты расчета по методу Ньютона для уравнения с одной переменной
Для обеспечения заданной точности при поиске приближенного значения корня уравнения в диапазоне необходимо выполнить 4 итерации. На последнем шаге итерации приближенное значение корня нелинейного уравнения будет определяться значением: .
Рис.3 . Листинг программы в MathCad
Модификации метода Ньютона для уравнения с одной переменной
Существует несколько модификаций метода Ньютона, которые направлены на упрощение вычислительного процесса.
Упрощенный метод Ньютона
В соответствии с методом Ньютона требуется вычислять производную функции f(x) на каждом шаге итерации, что ведет к увеличению вычислительных затрат. Для уменьшения затрат, связанных с вычислением производной на каждом шаге расчета, можно произвести замену производной f’( xn ) в точке xn в формуле на производную f’(x0) в точке x0. В соответствии с данным методом расчета приближенное значение корня определяется по следующей формуле:
Таким образом, на каждом шаге расчета строятся прямые , которые параллельны касательной к кривой y=f(x) в точке B0 (см. рис.4). Преимуществом данного метода является то, что производная функции вычисляется один раз.
Разностный метод Ньютона
В соответствии с методом Ньютона требуется вычислять производную функции f(x) на каждом шаге итерации, что не всегда удобно, а иногда практически невозможно. Данный способ позволяет производную функции заменить разностным отношением (приближенным значением):
В результате приближенное значение корня функции f(x) будет определяться выражением разностного метода Ньютона:
Двух шаговый метод Ньютона
В соответствии с методом Ньютона требуется вычислять производную функции f(x) на каждом шаге итерации, что не всегда удобно, а иногда практически невозможно. Данный способ позволяет производную функции заменить разностным отношением (приближенным значением):
В результате приближенное значение корня функции f(x) будет определяться следующим выражением:
Метод секущих является двух шаговым, то есть новое приближение определяется двумя предыдущими итерациями и . В методе необходимо задавать два начальных приближения и . Скорость сходимости метода будет линейной.
Для того, чтобы добавить Ваш комментарий к статье, пожалуйста, зарегистрируйтесь на сайте.
источники:http://ru.algorithmica.org/cs/numerical/newton/
http://simenergy.ru/math-analysis/solution-methods/45-method-newton-s