2.4. Метод половинного деления (дихотомии, бисекции)
Содержание метода заключается в следующем.
Пусть
нелинейное уравнение (1.1)
y 
на отрезке
имеет один ко-
рень
(рис. 1.4). Интервал
делит-
ся пополам
(середина интервала
,
обозначенная
через с,
принимается за ну-
0
a c =
b x левое
приближение корня: с
=
.
Если
,
то выбирается одна из поло-
винок
или
,
на концах которой
Рис. 1.4. Метод
деления 
меняет знак (на рис. 1.4 таким ин-
отрезка
пополам тервалом будет
).
Выбирая в каж-
дом случае тот из отрезков, на котором
функция меняет
знак, и продолжая процесс половинного
деления дальше, можно дойти до сколь
угодно малого отрезка
,
содержащего корень уравнения. При
достижении
за значение корня принимается
=
,
ошибка которого не превышает величины
.
2.5. Метод касательных (метод Ньютона)
Содержание метода заключается в следующем.
Пусть дано нелинейное
уравнение
= 0 и пусть на интервале изоляции корня
(рис. 1.6) производные
непрерывны и сохраняют знаки. В качестве
начального приближения корня
выбираем конец интервала изоляции
корня, на котором знаки
и
совпадают (на рис. 1.6,
например,
и
положительны, поэтому можно принять
= a).
Через точку
проводим касательную к
и
y точку пересечения касатель-
с
осью абсцисс
принимаем
за
следующее приближение к
корню, т.е.
.
Рассуждая подобным образом, находим
следующее
приближение к
корню,
т.е.
.
Напоми-
b наем,
если угловой коэффи-
ент
прямой
равен
,
то
0 a
x данная
прямая касается гра-
фика функции
.
Рис. 1.6
Итерационная формула метода касательных имеет следующий вид:
(1.9)
где
Вычислительный
процесс по этой формуле продолжают до
тех пор, пока значение функции
не станет меньше заданной точности
,
т.е. при некотором n
имеет место неравенство
.
(Пример решения нелинейного уравнения по методу простой итерации приведен в Методических указаниях.)
Замечания к методу Ньютона.
1). Важным преимуществом метода Ньютона является высокая скорость сходимости, обеспечивающая значительную экономию времени при решении сложных нелинейных уравнений. Этот метод используется наиболее часто среди всех итерационных алгоритмов.
2). Популярность этого метода оправдана также тем, что для определения интервала, в котором заключен корень, не требуется находить значения функции с противоположными знаками, как это необходимо сделать в большинстве других итерационных методов. Вместо интерполяции по двум значениям функции экстраполяцию в методе Ньютона осуществляют с помощью касательной к кривой в данной точке.
3) При нахождении
корня нелинейного уравнения методом
Ньютона следует ясно представить себе,
какую из точек
(см. рис. 2.6) принять за начальную (другими
словами, значение абсциссы которой из
точек принять за
для вычисления по формуле (2.5)), и выбрать
нужно ту из точек, для которой будет
выполняться условие:
. Например,
(рис. 2.6, а),
так как совпадают знаки
и
,
и
(рис. 2.6, б),
потому что совпадают знаки
и
(
< 0 и
<0). Если за начальное приближение
принять тот из концов интервала изоляции,
в котором знаки
и
противоположны, то есть не выполняется
условие
,
то в результате вычислений получим
точку
(рис 2.6, а),
которая не является приближением к
корню.
4) Если в процессе
итерации
обращается в нуль, то применение метода
усложняется.
4) В случае бесконечно
большого
метод также не является эффективным.
6) Метод Ньютона
достаточно эффективен, если начальное
приближение
выбрано достаточно близко к истинному
корню уравнения, что не всегда осуществимо.
Поэтому методу Ньютона предшествует
какой-либо надежно сходящийся алгоритм
(например, метод деления отрезка
пополам), и тогда метод Ньютона работает
в завершающей стадии решения уравнения.
7) Иногда решение методом Ньютона оказывается невозможным, так как он требует вычисления производной, который в некоторых точках может не существовать.
8) С помощью метода
Ньютона число верных знаков после
запятой искомого корня
удваивается на каждом шаге итерации.
Пример на применение метода Ньютона для вычисления корня нелинейного уравнения дан в программе.