Ядерное оружие | Графика | Математика | Физика | Заказать курсовую | Информатика | ТКМ | Электротехника | Атомная энергетика | Лекции

Ядерное оружие | Графика | Математика | Физика | Заказать курсовую | Информатика | ТКМ | Электротехника | Атомная энергетика | Лекции

Метод Ньютона (метод касательных) нахождение корней уравнения


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

$\displaystyle x_{i+1}=x_i-\dfrac{1}{f'(x_i)}f(x_i)$(9.1)
 


(сравните с формулой метода одной касательной). Этот метод называется методом касательных, или методом Ньютона. Действительно, последовательные приближения метода Ньютона сходятся гораздо быстрее, чем в общем методе итераций (скорость сходимости приближений в котором, напомним, та же, что у геометрической прогрессии со знаменателем $ {\gamma}$ при $ 0<{\gamma}<1$).

Поскольку для метода Ньютона

$\displaystyle {\varphi}(x)=x-\dfrac{f(x)}{f'(x)},$

то

$\displaystyle {\varphi}'(x)=1-\dfrac{(f'(x))^2-f(x)f''(x)}{(f'(x))^2}= \dfrac{f(x)f''(x)}{(f(x))^2}.$

В точке $ x^*$ получаем $ {\varphi}'(x^*)=0$, так как $ f(x^*)=0$. Тем самым, в этом методе график $ y={\varphi}(x)$ пересекает прямую $ y=x$ в точности по горизонтали, что приводит к очень быстрой сходимости итераций к $ x^*$. Именно, имеет место оценка

$\displaystyle \vert x_{i+1}-x^*\vert\leqslant c\vert x_i-x^*\vert^2\leqslant \dfrac{1}{c}(c\vert x_0-x^*\vert)^{2^{i+1}},$(9.2)
 


где $ c$ -- некоторая постоянная (не зависящая от $ i$). Если начальное приближение $ x_0$ взято достаточно близко от корня $ x^*$, то можно взять $ c=\dfrac{1}{\vert x_0-x^*\vert}$.

Заметим, что по сравнению с общей оценкой метода итераций

$\displaystyle \vert x_{i+1}-x^*\vert\leqslant {\gamma}\vert x_i-x^*\vert,$
Заказать перевод

постоянная $ {\gamma}<1$ заменяется в оценке метода Ньютона (9.2) на стремящуюся к 0 величину $ c\vert x_i-x^*\vert$; отсюда и высокая скорость сходимости.

Скорость сходимости итераций, которая задаётся формулой (9.2), называется квадратичной. Квадратичная скорость сходимости означает, примерно говоря, что число верных знаков в приближённом значении $ x_i$ удваивается с каждой итерацией. Действительно, если $ c\approx1$, и $ \vert x_i-x^*\vert\approx10^{-n}$, то $ \vert x_{i+1}-x^*\vert\approx10^{-2n}$. Это и означает, что число верных знаков при переходе к следующему приближению возросло с $ n$ до $ 2n$, то есть удвоилось.

Геометрический смысл метода Ньютона состоит в том, что на каждом шаге мы строим касательную к графику $ y=f(x)$ в точке очередного последовательного приближения $ x_i$, а за следующее приближение $ x_{i+1}$ берём точку пересечения этой касательной с осью $ Ox$. Тем самым наклон прямой подстраивается на каждом шаге наилучшим образом (ведь кривизну графика, связанную с второй производной, мы не учитываем, и поэтому неизвестно, в какую сторону от касательной отклонится график).

Рис.9.13.Последовательные приближения метода Ньютона

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

$\displaystyle f(x_i)+f'(x_i)(x-x_i)=0,$

в котором левая часть -- это многочлен Тейлора первого порядка для функции $ f(x)$ в точке $ x_i$, то есть линейная функция

$\displaystyle \ell_{x_i}(x)=f(x_i)+f'(x_i)(x-x_i).$

Решением линеаризованного уравнения $ \ell_{x_i}(x)=0$ служит следующее приближение $ x_{i+1}$, в то время как решением исходного точного уравнения $ f(x)=0$ служит искомый корень $ x^*$.

Идея замены точной (но сложной) задачи последовательностью более простых линеаризованных задач весьма продуктивна в приближённых методах; например, такая идея даёт эффективный способ решения многомерных задач с ограничениями (метод Франка - Вулфа в нелинейном программировании, см., например, [Киселёв В.Ю., Экономико-математические методы и модели. -- Иваново: изд. ИГЭУ, 1998]).

   

Главы учебника "Курс лекций высшей математики"

 

Платформу клиент-сервер | ActiveX-компоненты | Базы данных | Конструктор форм | Электро | ТОЭ | Linux | Интегралы | Лекции физика | Windows 2003 | Архитектура ЭВМ | Рисунок | Световые волны | Операционные системы
Pascal | Эксперт | Учебник Java | Кодирование | Пефирия ПК | Информатика | Сети | Моделирование | Язык SQL Расчет надежности | Задачи