Теория некоторых методов - 2003 / теория метода половинного деления

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

Это один из простейших методов нахождения корней нелинейных уравнений. Он состоит в следующем. Допустим, что нам удалось найти отрезок (а,b), на котором расположено искомое значение корня x=c, т.е. c (a,b). В качестве начального приближения корня c₀ принимаем середину этого отрезка: с₀=(a+b)/2. Далее исследуем значения функции F(x) на концах отрезков (a,c₀) и (c₀,b), т.е. в точках a,c₀,b. Тот из отрезков, на концах которого F(x) принимает значения разных знаков, содержит искомый корень; поэтому его принимаем в качестве нового отрезка (a₁,b₁). Вторую половину отрезка (a,b), на которой знак F(x) не меняется, отбрасываем. В качестве первого приближения корня принимаем середину нового отрезка c₁=(a₁+b₁)/2 и т.д. Таким образом, k-е приближения вычисляются как

C_k=(a_k+b_k)/2 (1.1)

после каждой итерации отрезок, на котором расположен корень, уменьшается вдвое, а после k итерации он сокращается в 2^л раз:

b_k-a_k=(b-a)/2^k (1.2)

Пусть приближенное решение x_* требуется найти с точностью до некоторого заданного малого числа e>0:

x-x_* <e (1.3)

Взяв в качестве приближенного решения k-е приближение корня: x_*=c_k, запишем (1.3) с учетом обозначения x=c в виде

c-c_k <e. (1.4)

Как легко видеть, из (1.1) следует, что (1.4) выполнено, если

b_k-a_k<2e (1.5)

Таким образом, итерационный процесс нужно продолжать до тех пор, пока не будет выполненно условие (1.5).

y

F(b)

y=F(x)

a c₀ c₂

0

c c₁ b x

F(a)

Метод деления отрезка пополам проиллюстрирован на рисунке. Пусть для определенности F(a)<0, F(b)>0. В качестве начального приближения корня примем c₀=(a+b)/2. Поскольку в рассматриваемом случае F(с₀)<0, то c (c₀,b), и рассматриваем только отрезок (c₀,b), т.е. a₁=c₀, b₁=b. Следующее приближение: c₁=(c₀+b)/2. При этом отрезок (c₁,b) отбрасываем, поскольку F(c₁)>0 и F(b)>0. Таким образом, c (c₀,c₁), a₂=c₀, b₂=c₁. Аналагично находим другие приближения: c₂=(c₀+c₁)/2 и т.д. до выполнения условия (1.5).

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