Вычислительные методы
Метод деления отрезка пополам (метод дихотомии, метод бисекции)
Метод Ньютона (метод касательных)
Метод секущих (метод хорд)
Постановка задачи
Метод исключения Гаусса с выбором главного элемента по столбцу
Вычисление определителя методом исключения Гаусса
Метод Зейделя
Интерполяция функции многочленами Лагранжа
Аппроксимация функций. Метод наименьших квадратов
Квадратичная аппроксимация (m = 2)
Линейная аппроксимация (m =1)
Постановка задачи численного интегрирования
Метод трапеций
Правило Рунге практической оценки погрешности
Метод Эйлера
Модифицированные методы Эйлера
Метод Рунге – Кутта
Методом деления отрезка пополам найти корень уравнения
Решение системы линейных алгебраических уравнений простым методом исключения Гаусса
Навигация
Метод Ньютона (метод касательных)
Вычислительная математика
100779
знаков
18
таблиц
23
изображения
2.5 Метод Ньютона (метод касательных)
Метод Ньютона является наиболее эффективным методом решения нелинейных уравнений.
Пусть корень x* Î [a, b], так, что f(a)f(b) < 0. Предполагаем, что функция f(x) непрерывна на отрезке [a, b] и дважды непрерывно дифференцируема на интервале (a, b). Положим x0 = b. Проведем касательную к графику функции y = f(x) в точке B0 = (x0, f(x0)) (рис. 2.8).
Рис. 2.8
Уравнение касательной будет иметь вид:
y – f(x0) = f '(x0)(x – x0). (2.11)
Первое пересечение получим, взяв абсциссу точки пересечения этой касательной с осью OX, т. е. положив в (2.11) y = 0, x = x1:
x1 = x0 – 
. (2.12)
Аналогично поступим с точкой B1(x1, f(x1)), затем с точкой B2(x2, f(x2)), и т. д. в результате получим последовательность приближений x1, x2, …, xn , …,причем
xn +1 = xn – 
. (2.13)
Формула (2.13) является расчетной формулой метода Ньютона.
Метод Ньютона можно рассматривать как частный случай метода простых итераций, для которого
j(x) = x - 
. (2.14)
Сходимость метода. Сходимость метода Ньютона устанавливает следующая теорема.
Теорема 2.3. Пусть x* – простой корень уравнения f(x) = 0, и в некоторой окрестности этого корня функция f дважды непрерывно дифференцируема. Тогда найдется такая малая s-окрестность корня x*, что при произвольном выборе начального приближения x0 из этой окрестности итерационная последовательность, определенная по формуле (2.13) не выходит за пределы этой окрестности и справедлива оценка:
|xn + 1 – x*| £ C |xn – x*|2, n
0, (2.15)
где С = s -1. Оценка (2.15) означает, что метод сходится с квадратичной скоростью.
Сходимость метода Ньютона зависит от того, насколько близко к корню выбрано начальное приближение. Неудачный выбор начального приближения может дать расходящуюся последовательность. Полезно иметь в виду следующее достаточное условие сходимости метода. Пусть [a, b] – отрезок, содержащий корень. Если в качестве начального приближения x0 выбрать тот из концов отрезка, для которого
f(x)f"(x) ³ 0, (2.16)
то итерации (2.13) сходятся, причем монотонно. Рис. 2.8 соответствует случаю, когда в качестве начального приближения был выбран правый конец отрезка: x0 = b.
Погрешность метода. Оценка (2.15) является априорной и неудобна для практического использования. На практике удобно пользоваться следующей апостериорной оценкой погрешности:
|xn – x*| £ |xn – xn – 1|. (2.17)
Критерий окончания. Оценка (2.17) позволяет сформулировать следующий критерий окончания итераций метода Ньютона. При заданной точности e > 0 вычисления нужно вести до тех пор, пока не будет выполнено неравенство
|xn – xn – 1| < e. (2.18)
Пример 2.3.
Применим метод Ньютона для вычисления 
. где a > 0, p – натуральное число. Вычисление эквивалентно решению уравнения xp = a. Таким образом, нужно найти корень уравнения f(x) = 0, f(x) = xp – a, f '(x) = pxp – 1. Итерационная формула метода (2.13) примет вид:
xn +1 = xn – 
= 
xn + 
.
(2.19)
Используя формулу (2.19), найдем 
с точностью e = 10-3.
xn +1 = 
xn + 
.
Простой корень уравнения x3 – 7 = 0 расположен на отрезке [1, 2]. Действительно, на концах отрезка [1, 2] функция f(x) = x3 – 7 принимает разные знаки, f (1) < 0, f (2) > 0. Кроме того, при x = 2 выполнено достаточное условие сходимости (2.16): f (2)f" (2) ³ 0.
Поэтому в качестве начального приближения можно взять x0 = 2.
Результаты приведены в табл. 2.3.
Таблица 2.3
| n | xn |
| 0 1 2 3 4 5 | 2 0.8415 0.8861 0.8742 0.8774 0.8765 |
Похожие работы
... . Рассмотрение метода ветвей и границ для решения задачи о коммивояжере удобнее всего проводить на фоне конкретного примера. Пользуясь введенными здесь обозначениями, мы проводим это описание в следующей лекции. Введем некоторые термины. Пусть имеется некоторая чис- ловая матрица. Привести строку этой матрицы означает выде-лить в строке минимальный элемент (его называют константой приведения) ...
... если - предельная абсолютная погрешность приближённого числа , то (1.2) отсюда следует, что (1.3) Значение предельной абсолютной погрешности, обычно, подбирается интуитивно по смыслу задачи. Пример 2: Определить предельную абсолютную погрешность числа , заменяющего число , точное значение которого нам неизвестно. Так как мы знаем, что , ...
... удивили меня…, хоть речь идёт обо мне самой. Они действительно написаны прекрасным стилем, который превосходит стиль самого очерка" /2/. 2.3. Рождение первенца и критическое перенапряжение Августа Ада Лавлейс работает с большим напряжением. В письмах к Бэббиджу она неоднократно жалуется на утомление, болезни, плохое самочувствие. Наконец, 6 августа Бэббидж отсылает Аде свои последние замечания ...
... в Украине, бывшем Советском Союзе и за рубежом научная школа теоретического программирования. В 2001-м году ее не стало... Но не только в научном плане велика роль женщин в развитии вычислительной техники. Со временем образуется огромное количество различных фирм по разработке и продаже программного и аппаратного обеспечения. Следовательно, разыгрываются человеческие трагедии капиталистического ...
0 комментариев