<<
>>

3.2.1. Метод дихотомии (половинного деления, бисекций).

Постановка задачи:

Дано нелинейное уравнение ¦(x) = 0.

Корень отделен, т.е. известно, что x* Î [a,b].

Требуется вычислить корень с заданной точностью ε.

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

Алгоритм метода.

1. Вычислить координату середины отрезка [a,b] x = (a+b)/2 и значение ¦(x) в этой точке.

2. Уменьшить отрезок, отбросив ту его половину, на которой корня нет.

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

если ¦(a) ·¦(x)>0 => x*Î [x,b] => a=x, иначе x*Î [a, x] => b=x

3. Проверить условие завершения вычислений : длина отрезка не превышает заданную точность и значение функции близко к 0 с заданной точностью:

b-a ≤ ε ∩ |¦(x)| ≤ ε.

Если условие достигнуто, расчет завершен, иначе повторить алгоритм сначала.

x

/
/
a

/
/

Рис. 3.4 Геометрическая иллюстрация метода бисекций.

b=x

Рис.

3.5 Схема алгоритма метода бисекций (дихотомии)

Количество итераций n, требуемых для достижения требуемой точности ε можно оценить заранее из соотношения

(3.6)

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

Недостатки метода: скорость сходимости низкая, не обобщается на систему уравнений.

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

Рис. 3.6. Непростой корень уравнения.

Пример 3.1. Требуется решить уравнение x3+2x=1

Сначала нужно отделить решения.

Удобно записать уравнение в виде x3=1-2x и построить графики двух элементарных функций ¦1(x)= x3 и ¦2(x)=1-2x

Рис. 3.7 Отделение корней уравнения x3 = 1 - 2 x.

Из графика следует, что корень один: x* Î [0;1].

Проверим наличие корня на отрезке

¦(a) = ¦(0) = 03+2·0 = -1, ¦(b) = ¦(1) = 13+2·1 = 2

Знаки на концах отрезка разные, следовательно, корень отделен верно.

Выполним несколько итераций уточнения корня.

1 итерация. Середина отрезка x = ( 0 + 1) / 2 = 0,5

Значение функции в середине ¦(x)=¦(0,5)= 0,53+2·0,5-1=0,125>0

Функция меняет свой знак на первой половине отрезка, следовательно, корень на первой половине, поэтому отбросим вторую половину, переместив конец отрезка в середину: x* Î [0;0,5]

2 итерация. Середина отрезка x = ( 0 + 0,5) / 2 = 0,25

Значение функции в середине

¦(x)=¦(0,25)= 0,253+2·0,25-1=0,0115625-0,5=-0,484375

Функция не меняет свой знак на первой половине отрезка, поэтому отбросим ее: x* Î [0,25;0,5]

Вычисления следует продолжить до достижения требуемой точности. Например, если ε=0,001 то потребуется не менее 10 итераций:

<< | >>
Источник: Мухамадеев И.Г.. АЛГОРИТМЫ ВЫЧИСЛИТЕЛЬНОЙ МАТЕМАТИКИ. КУРС ЛЕКЦИЙ. 2007

Еще по теме 3.2.1. Метод дихотомии (половинного деления, бисекций).:

  1. 2.2.1. МОДЕЛИРОВАНИЕ ЧАСТИЦ ВЗВЕСИ.
  2. Информационная структура АСУ ТП.
  3. 3.2. МЕТОДЫ УЧЕБНОЙ ДЕЯТЕЛЬНОСТИ
  4.   Жиль Делез ПЛАТОН И СИМУЛЯКР  
  5. Дихотомия
  6. ПРОГРАММА КУРСА
  7. Система правовых норм и отраслевое подразделение права
  8. УПРАВЛЕНИЕ ОБОРОТНЫМИ АКТИВАМИ
  9. МЕТОДИКА ДЕЛЕНИЯ
  10. ДИЭРЕЗА
  11. 4.2. Методические указания к выполнению лабораторных работ
  12. 2.1 Содержание дисциплины (наименование и номера тем).
  13. 5.2. Вопросы к экзамену (1 семестр).
  14. 3. Дихотомия
  15. § 1. Введение.
  16. 3.3.2. Внутреннее пространство дома
  17. 1.3. Метод половинного деления