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

РЕШЕНИЕ АЛГЕБРАИЧЕСКИХ И ТРАНСЦЕНДЕНТНЫХ УРАВНЕНИЙ

Постановка задачи и этапы решения.

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

1. ЛОКАЛИЗАЦИЯ корней, т.е. выделение непересекающихся отрезков, каждый из которых содержит по одному корню.

2. УТОЧНЕНИЕ корней, т.е. вычисление корня на каждом из отрезков с нужной точностью.

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

Пример локализации корней.

Приведем лишь один ПРИМЕР: определить количество и приближенное расположение корней уравнения sinX - 0.2X=0.

Для решения перепишем уравнение в виде sinX=0.2X. Поскольку значения функции y=sinX лежат между -1 и 1, то корни уравнения могут быть только на отрезке [-5, 5]. Ясно, что один из корней - это X=0. Если же на отрезке [-5, 5] нарисовать графики функций y₁(X)= sinX и y₂(X)=0.2X, то сразу будет видно, что точки их пересечения (а это и есть корни нашего уравнения) расположены на отрезках [-3, -2] и [2, 3].

Ответ: исходное уравнение имеет 3 корня: Х₁=0, Х₂Î [-3, -2] и Х₃Î [2, 3].

Упражнения: определить количество и месторасположение корней уравнений:

1.1 9 – Х² - e^х = 0

1.2 sin 2X – X²+6=0

1.3 1/(1+X²) - 0.1 X⁴ = 0

1.4 ln(2+X) - 0.4X³= 0

В дальнейшем мы будем считать, что уравнение f(X)=0 задано на отрезке [a, b], на котором расположен ровно один его корень, и исследовать решение второй части задачи - уточнение корней. По-видимому, эта задача является самой простой из всех вычислительных задач, встречающихся на практике. Существуют несколько хороших методов решения данной задачи.

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

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

Алгоритм данного метода можно записать так:

1.Ввести данные (a, b, e).

2.Если нужная точность достигнута (| b - a | < 2e) то иди к п.6

3.Возьми середину очередного отрезка (С = (a + b)/ 2).

4.Если значения функции в точках а и С одного знака (f(a)*f(C)> 0), то в качестве следующего отрезка возьми правую половину (а=С), иначе левую (b=C).

5.Иди к п.2.

6.Напечатать ответ ((a + b) / 2)

Упражнение 1.5 Перевести данный алгоритм на один из языков программирования.