Метод деления отрезка пополам (метод половинного деления)

Вводные замечания

Численное решение нелинейных уравнений

Пока будет рассматриваться решение 1-го уравнения. В общем виде нелинейное уравнение записывается: , где - некоторая непрерывная функция. Нелинейные уравнения делятся на алгебраические и трансцендентные.

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

.

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

; .

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

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

а) отыскание приближенного значения корня или содержащего его отрезка;

б) уточнение приближенного значения до некоторой заданной степени точности.

Начальное приближение может быть найдено из физических соображений, с помощью графических методов. Если начальное приближение найти не удается, то находят две близко расположенные точки и , в которых непрерывная функция принимает значения разных знаков, т.е. . В этом случае между точками aи bесть, по крайней мере, одна точка, в которой , х^* - корень. В качестве начального приближения х₀ можно принять середину отрезка [a, b], т.е. х₀ = (a+b)/2.

Итерационный процесс состоит в последовательном уточнении начального приближении х₀. Каждый такой шаг называют итерацией. В результате итераций находят последовательность приближенных значений корня х₀, х₁, х₂, …, х_n. Если эти значения с ростом nприближаются к истинному значению корня х^*, то говорят, что итерационный процесс сходится.

Позволяет решать нелинейные трансцендентные, а также алгебраические уравнения. Это один из простейших численных методов. На первом шаге необходимо найти отрезок [a; b], в котором расположено искомое значения корня х = х^*; a < x^*< b; .

В качестве начального приближения корня х₀ принимаем середину отрезка [a, b], т.е. х₀ = (a+b)/2. Далее определяем значение функции f(x) в точках a, x₀, b; т.е. на концах отрезков [a, x₀] и [x₀, b]. Тот из них, на концах которого f(x) имеет разные знаки, содержит искомый корень. Поэтому его принимают в качестве нового отрезка. Вторую половину отрезка [a, b], на которой знак f(x) не меняется, отбрасываем. В качестве первой итерации корня принимаем середину нового отрезка и т.д. Таким образом, после каждой итерации отрезок, на котором расположен корень, уменьшается вдвое. Т.е. после nитераций он сокращается в 2ⁿраз.

Пусть для определенности f(a) < 0, f(b) > 0 (рис. 3.1).

Начальное приближение корня х₀ = (a+b)/2. Т.к. f(x₀) < 0, то x₀ < x^* < b и рассмотрим только [x₀, b]. Следующее приближение: х₁ = (х₀+b)/2. Сейчас отбрасываем отрезок [x₁, b], т.к. f(x₁) > 0 и f(b) > 0. Т.е. x₀ < x^*< x₁. Аналогично находим другие приближения: x₂ = (x₀+x₁) /2 и т.д.

Рис. 3.1. Графическая иллюстрация метода половинного деления

Итерационный процесс продолжается до тех пор, пока значение функции

f(x) после n-ой итерации не станет меньшим по модулю некоторого малого заданного числа e, т.е. .