Метод дихотомии. Метод половинного деления. Метод хорд

Предположим, что процесс локализации корней уравнения (4.1) осуществлен и нам требуется определить корень , на концах которого функция принимает значения разных знаков, т.е.

(4.8)

Метод дихотомии основан на построении последовательности приближений к корню , по следующей схеме ([5], стр. 197): внутри отрезка произвольным образом выбирается точка с, её называют пробной точкой (это первое приближение ). Затем вычисляют значение , которое приведет к одной из трех взаимоисключающих ситуаций:

a) ; b) ; c) .

Данные результаты, применительно к рассматриваемой задаче означают, что:

а) корень находится в интервале ;

b) корень находится в интервале ;

c) точка с является искомым корнем .

Таким образом, одно вычисление значения функции позволяет уменьшить промежуток локализации корня (случай а) или b)) или указать его значение (случай c)). Конечно, ситуация с) маловероятна, но вполне реальная в смысле выполнения приближенного равенства, когда длина промежутка локализации корня близка к длине его промежутка неопределенности ([5], стр. 197).

В зависимости от того, какая ситуация а) или б) имеет место, рассмотренная выше процедура сужения отрезка локализации корня применяется либо к отрезку (случай a)), либо к отрезку (случай b)) соответственно и далее повторяется циклически.

Если способ задания пробных точек с (последовательности приближений к точному корню) определен так, что последовательность длин получающихся в процессе отрезков локализации корня стремится к нулю, то методом дихотомии можно найти приближенное значение корня уравнения (4.1) на отрезке с наперед заданной точностью ([5], стр. 197).

Более того, этот метод позволяет найти с заданной точностью какой–либо корень уравнения (4.1) и в том случае, когда на отрезке несколько корней (в этом случае отрезок называется отрезком существования). ([5], стр. 197).

Метод дихотомии (название которого произошло от греческого слова, обозначающего деление пополам) также называют ([5], стр. 197 ) методом бисекции, методом вилки или методом проб.

Наиболее употребительным частным случаем среди методов дихотомии является метод деления отрезка пополам. Рассмотрим его более подробно. Сначала для ситуации, когда не учитывается погрешность вычисления значений функции .

Для обобщения расчетов отрезок обычно обозначают .

В качестве первого приближения корня выбирают значение , равное середине отрезка , т.е.

. (4.9)

Очевидно, что погрешность этого приближения не превышает половины длины исходного отрезка локализации

. (4.10)

Затем вычисляют , если (что практически встречается очень редко), то расчет прекращают, полагая ; если , то из двух отрезков и в качестве нового отрезка локализации выбирают тот, на котором функция на концах отрезка принимает значения разных знаков.

В качестве второго приближения корня выбирают середину отрезка :

. (4.11)

Погрешность этого корня не превышает половины длины второго отрезка локализации и соответственно четверти длины исходного отрезка локализации :

. (4.12)

Если , то процесс прекращают, полагая ; если , то из двух отрезков и в качестве нового отрезка локализации выбирают тот, на котором функция на концах отрезка принимает значения разных знаков.

В качестве третьего приближения корня выбирают середину отрезка :

. (4.13)

Погрешность этого приближения корня не превышает половины длины третьего отрезка локализации и соответственно восьмой части длины исходного отрезка локализации:

. (4.12)

Продолжая процесс дальше, получим, что если , то n -ое приближение корня будет определяться как середина отрезка :

. (4.13)

Погрешность n -го приближения корня удовлетворяет неравенству (4.14):

. (4.14)

Строгое доказательство сходимости данной последовательности приближений к точному значению корня и вывод оценки (4.14) можно найти в [7], стр. 388.

Критерием окончания данного итерационного процесса в случае требования вычисления приближенного значения корня с точностью , является выполнение условия:

, (4.15)

Следовательно, деление на отрезки продолжается до тех пор, пока длина отрезка не станет меньше , тогда , вычисленное по формуле (4.13) – приближенное значение корня с точностью .

Число итераций, необходимых для достижения требуемой точности удовлетворяет неравенству (4.16):

. (4.16)

Достоинством данного метода является простота и однотипность вычислений (не создающих трудностей в написании программы или проведении расчетов в вручную), а также - отсутствие серьезных ограничений на функцию: достаточно, чтобы она была только непрерывной и принимала на концах исходного отрезка локализации значения разных знаков.

Недостаток – небольшая скорость сходимости (метод сходится со скоростью геометрической прогрессии, со знаменателем ([3], стр. 90, 96)).

Исследования показали ([3], стр. 97), что при выполнении условия (4.8) метод сходится даже, если на отрезке находится не один, а несколько корней.

В тех случаях, когда дополнительно учитывается допуск d, связанный с реальной точностью вычислений значений функции , в методе вместо равенств , …, используют неравенства .. Описание одного из вариантов алгоритма для расчетов в этом случае можно найти в [5], стр. 198.

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

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

Геометрически (смотрите рисунок 1) это означает, что точка с определяется как абсцисса точки пересечения прямой, проходящей через точки A (a; f (a)) и B (b; f (b)), с осью ОХ (т.е. точка пересечения хорды АВ с осью ОX).

Рисунок 1

Уравнение прямой, проходящей через две заданные точки А и В, т.е. уравнение прямой, содержащей хорду АВ, имеет вид:

. (4.17)

Откуда следует, что

.

Так как точка пересечения данной хорды имеет координаты (с;0), получаем, что абсцисса с определяется по формуле (4.18):

. (4.18)

Метод хорд также называют методом пропорциональных частей, методом линейной интерполяции, правилом ложного положения или regual falsi ([5], стр. 200).

Существует несколько версий реализации этого метода. Одна из них состоит в следующем - значения с определяются по формуле (4.18), а выбор нового отрезка, в случае необходимости, осуществляют также, как и в методе половинного деления. Длина промежутка локализации при этом может не стремиться к нулю, поэтому обычно расчет ведется до совпадения значений с в двух соседних итерациях с точностью ([5], стр. 200), т.е. пока не начнет выполняться условие: . В [9] дается рекомендация вести расчет с точностью , где .

Так как для линейной функции метод хорд дает корень точно за один шаг при любой дине отрезка локализации, то можно рассчитывать на его довольно быструю сходимость, если функция близка к линейной ([5], стр. 200). В [9] имеются доказательства признаков монотонной сходимости метода хорд при различных дополнительных ограничениях на свойства функций.

В общем же случае, если на функцию не накладывать дополнительных ограничений, то может оказаться, что метод хорд будет проигрывать в скорости сходимости методу половинного деления, например для ситуации, представленной на рисунке 2 ([5], стр. 200).

Рисунок 2

Методы дихотомии относят к глобально сходящимся методам, так как с их помощью можно получить какой-либо корень уравнения (4.1), начиная с отрезка любой длины входящего в область непрерывности функции , на концах которого она принимает значения разных знаков.

Метод Ньютона

Метод Ньютона является одним из популярнейших методов, в связи с его идейной простотой и быстрой сходимостью.

Правила построения итерационной последовательности приближений к точному значению корня получают одним из двух способов ([5], стр. 204):

· из геометрических соображений, они дают второе название этого метода – метод касательных;

· из аналитических соображений – заменой нелинейной функции её линейной моделью с помощью формулы конечных приращений или формулы Тейлора, в связи с чем, появляется еще одно название метода – метод линеаризации.

Любой из этих подходов накладывает на свойства функции дополнительные ограничения, она должна быть как минимум непрерывно дифференцируемой на отрезке локализации корня функцией, сохраняющей знак своей производной (необходимость этих требований станет понятным из ниже следующих рассуждений).

Метод касательных

Суть метода касательных состоит в следующем. На отрезке локализации выбирают точку , которая называется начальным приближением к корню , затем через точку проводят касательную к графику функции и определяют точку пересечения касательной с осью ОХ (смотрите рисунок 3). Абсциссу этой точки выбирают за новое приближение к корню .

Если , то задача решена, если нет, то проводят касательную через точку и определяют её точку пересечения с осью ОХ, абсциссу которой рассматривают как следующее приближение к корню .

Если , то задача решена, если нет, то проводят касательную через точку и определяют её точку пересечения с осью ОХ, абсциссу которой рассматривают как следующее приближение к корню .

Продолжая этот процесс, получают последовательность приближений к корню .

Рисунок 3 – Приближение к корню нелинейного уравнения методом касательных

Так как уравнение касательной (для её существования функция должна быть как минимум дифференцируемой), проведенной к графику функции в точке , имеет вид:

, (4.19)

то, в предположении, что , нетрудно получить абсциссу точки пересечения данной касательной с осью ОХ:

, (4.20)

, (4.21)

следовательно, формула для расчета n -го приближения к корню имеет вид:

. (4.22)

Поиск по сайту: