Главная страница Случайная страница
КАТЕГОРИИ:
АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника
Метод Ньютона (метод касательных). Пусть известно начальное приближение х0 корня уравнения
|
|
Пусть известно начальное приближение х 0 корня уравнения. Метод Ньютона заключается в построении итерационной последовательности
, (3.5)
сходящейся к корню уравнения х *.
Сформулируем достаточные условия сходимости метода.
Теорема 3.3. Пусть функция f определена и дважды дифференцируема на отрезке [ а; b ]: f Î C2[ a; b ], причем на концах отрезка она принимает значения разных знаков 
, а производные 
и 
не меняют знак на отрезке [ a; b ]. Тогда, исходя из начального приближения х 0, удовлетворяющего неравенству 
(в качестве начального приближения выбирается тот конец отрезка, на котором функция по знаку совпадает со своей второй производной), можно построить указанную итерационную последовательность, сходящуюся к единственному на этом отрезке корню функции f.
Метод Ньютона допускает простую геометрическую интерпретацию. Очередное приближение 
представляет собой абсциссу точки пересечения касательной к графику функции в точке 
с осью ОХ (рис. 3.3).
Рис. 3.3. Метод Ньютона
Оценим скорость сходимости метода Ньютона.
Положим
; 
; 
.
Поскольку х * - корень уравнения, то 
и, следовательно,
Рассмотрим разность:
,
откуда
Из (3.5) для k -го приближения имеем:
,
где 
.
В силу условий теоремы сходимость итераций будет монотонной, поэтому неравенство треугольника превращается в равенство:
.
Тогда
, (3.6)
т.е. имеет место сходимость со скоростью геометрической прогрессии.
Однако такая сходимость имеет место только при первых итерациях, а затем скорость сходимости возрастает.
Воспользуемся формулой Тейлора:
,
разложим функцию f (x) в окрестности точки xk и подставим x = x*:
. (3.7)
Из (3.5) и (3.7) следует, что
;
.
Оценим полученное выражение по модулю, учитывая (3.6):
, где 
,
т.е. сходимость еще более быстрая.
Если по каким-либо причинам невозможно каждый раз считать производные и значения функций в точках, то допустимо каждый раз вместо f /(xk -1) брать f /(x 0), т.е. производную в начальной точке.
Рассмотрим модификацию метода Ньютона для решения нелинейных систем.
Пусть имеется нелинейное уравнение 
, где f - вектор-функция, т.е. дана система:
.
Предположим, что в любой точке шара 
матрица Якоби рассматриваемой системы
невырождена, т.е. 
. Тогда в каждой точке шарасуществует обратная матрица 
и последовательность приближений строится следующим образом:
.