Модифицированный метод Ньютона (метод секущих)
В этом методе для вычисления производных на каждом шаге поиска используется численное дифференцирование по формуле:
Тогда рекуррентная формула (4.6) будет иметь вид:
|
(4.10) |
где 
Метод ньютона-рафсона
Повышение эффективности метода за счёт использования информации о производной накладывает дополнительные ограничения на функцию. Кроме унимодальности функция должна быть непрерывной и дважды дифференцируемой.
2.5.1. Метод Ньютона-Рафсона.
Пусть 
-
непрерывная и дважды дифференцируемая
функция.
Требуется
найти корень уравнения 
.
Зададим 
–
начальную точку поиска. Построим линейную
аппроксимацию функции 
в
точке
.
Для этого разложим
в
ряд Тейлора в точке
и
отбросим все члены второго порядка и
выше.
Сходимость метода зависит от выбора начальной точки и вида функции.
не сходится
Условие
выхода 
11. Численное решение уравнения методом секущих. Эффективность данного алгоритма. Привести фрагмент программы, поясняющий данный алгоритм.
Метод секущих — один из численных методов решения уравнений.
В
качестве функции 
берут
любую постоянную 
,
знак которой совпадает со
знаком производной 
в окрестности 
(и,
в частности, на отрезке, соединяющем 
и 
).
Постоянная
не
зависит также и от номера шага. Тогда
формула итераций оказывается
очень проста:
и
на каждой итерации нужно один раз
вычислить значение функции 
.
Выясним
смысл этой формулы, а также смысл условия
о совпадении знаков 
и
.
Рассмотрим прямую, проходящую через
точку 
на
графике 
с
угловым коэффициентом .
Тогда уравнением этой прямой будет
Иллюстрация последовательных приближений метода секущих.
Найдём
точку пересечения этой прямой с осью 
из
уравнения
откуда 
.
Следовательно, эта прямая пересекает
ось 
как
раз в точке следующего приближения. Тем
самым получаем следующую геометрическую
интерпретацию последовательных
приближений. Начиная с точки
,
через соответствующие точки
графика
проводятся
секущие с угловым коэффициентом 
того
же знака, что производная 
.
(Заметим, что, во-первых, значение
производной вычислять не обязательно,
достаточно лишь знать, убывает функция
или
возрастает; во-вторых, что прямые,
проводимые при разных 
,
имеют один и тот же угловой
коэффициент 
и,
следовательно, параллельны друг другу.)
В качестве следующего приближения к
корню берётся точка пересечения
построенной прямой с осью
.
На
чертеже справа изображены итерации
при 
в
случае 
и
в случае 
.
Мы видим, что в первом случае меняющаяся
точка
уже
на первом шаге «перепрыгивает» по другую
сторону от корня
,
и итерации начинают приближаться к
корню с другой стороны. Во втором случае
последовательные точки
приближаются
к корню, оставаясь всё время с одной
стороны от него.
Условие сходимости
Достаточное условие сходимости, таково:
Это неравенство может быть переписано в виде
откуда получаем, что сходимость гарантируется, когда, во-первых,
так
как 
(тем
самым проясняется смысл выбора знака
числа
),
а во-вторых, когда 
при
всех 
на
всём рассматриваемом отрезке, окружающем
корень. Это второе неравенство заведомо
выполнено, если
где 
.
Таким образом, угловой коэффициент
не
должен быть слишком мал по абсолютной
величине: при малом угловом коэффициенте
уже на первом шаге точка 
может
выскочить из рассматриваемой окрестности
корня
,
и сходимости итераций к корню может не
быть.