7.2. Метод половинного деления

Пожалуй, самым простым и надежным методом яляется метод половинного деления. В литературе также встречается другое название этого метода – метод бисекций.

Пусть на отрезке непрерывная функция , корень которой надо найти, меняет знак (см рис.7.2). Это значит, что на этом отрезке имеется точка , в которой .

В методе половинного деления очередное приближение (исходными приближениями являются и ) определяется как точка, лежащая посередине, между точками и :

(7.7)

Для этой точки вычисляется и далее определяется, на какой из двух половин отрезка находится корень. В случае приведенном на рисунке – на правой: .

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

Метод половинного деления отличается высокой надежностью. Правда скорость сходимости его невелика. Оценим количество итераций, которое потребуется для определения корня. Рассмотрим для простоты случай, когда корень ишется на отрезке [0,1]. Пусть точность, которую нам надо обеспечить 0.0001. То есть, мы хотим определить корень с точностью до 4-х значащих цифр. Тогда после первой итерации наш отрезок станет равным 1/2; после второй – 1/4; …; после k-й – 1/2^k. Следовательно, необходимая точность будет гарантированно достигнута при .

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

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

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

На рис.7.3 наглядно иллюстрируется идея метода. Сначала выбирается начальное приближение  . Из точки графика функции для этого значения проводится касательная к графику. Точка пересечения этой касательной с осью абсцисс считается новым приближением. Далее эта операция повторяется до тех пор, пока очередная поправка не окажется меньше требуемой точности.

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

И, таким образом, для очередного приближения получается формула:

(7.8)

Эта формула и определяет метод касательных. В литературе этот метод часто назвается методом Ньютона, либо методом Ньютона-Рафсона. Здесь формула (7.8) получена, исходя из наглядных геометрических представлений.

Возможно более строгое получение этой формулы с использованием ряда Тейлора (см, например, [5.2]).

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

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

Однако, при высокой скорости сходимости, метод касательных оказывается и более капризным. Возможные неприятности иллюстрируются рисунком 7.4.

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