Решение алгебраических и трансцендентных уравнений методом половинного деления бисекций (8 видео)

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

Теорема 2. Итерационный процесс половинного деления сходится к искомому корню ξ с любой наперед заданной точностью ε.
Доказательство: Рассмотрим последовательность чисел ξ_i являющихся приближением корня на i -ом шаге.
ξ_i=½(b_i+a_i), i=0,1.
где a₀=a; b₀=b; a_i;b_i — границы подынтервалов, в которых f(a_i)f(b_i) 0 мы ни задали, всегда можно найти такое n , что ч.т.д.
Графически метод дихотомии выглядит следующим образом

|f(c)|≤δ f(a)f(c) 10 = 1024 ≈ 10 3 раз. За 20 итераций (n=2) уменьшается в 2 20 ≈ 10 6 раз.

Пример №1 . Найти экстремум функции: y=5x 2 -4x+1 методом дихотомии, если ε=0.1, а исходный интервал [0,10].

Решение
Видео решение

Пример №3 . Методом бисекции найти решение нелинейного уравнения на отрезке [a,b] с точностью ε = 10 -2 . Выбрав полученное решение в качестве начального приближения, найти решение уравнения методом простой итерации с точностью ε = 10 -4 . Для метода простой итерации обосновать сходимость и оценить достаточное для достижения заданной точности число итераций.
sqrt(t)+x 2 = 10, a = 2.6, b = 3

Найдем корни уравнения:
Используем для этого Метод половинного деления (метод дихотомии)..
Считаем, что отделение корней произведено и на интервале [a,b] расположен один корень, который необходимо уточнить с погрешностью ε.
Итак, имеем f(a)f(b) 1 /₂(a+b) и вычисляем f(c). Проверяем следующие условия:
1. Если |f(c)| 1 /₂ n (b-a)
В качестве корня ξ. возьмем 1 /₂(a_n+b_n). Тогда погрешность определения корня будет равна (b_n – a_n)/2. Если выполняется условие:
(b_n – a_n)/2 1 /₂(a_n+b_n).
Решение.
Поскольку F(2.6)*F(3) 0, то a=2.8
Итерация 2.
Находим середину отрезка: c = (2.8 + 3)/2 = 2.9
F(x) = 0.113
F(c) = -0.487
Поскольку F(c)•F(x) 0, то a=2.825
Остальные расчеты сведем в таблицу.

N	c	a	b	f(c)	f(x)
1	2.6	3	2.8	-1.6275	-0.4867
2	2.8	3	2.9	-0.4867	0.1129
3	2.8	2.9	2.85	0.1129	-0.1893
4	2.8	2.85	2.825	-0.1893	-0.3386
5	2.825	2.85	2.8375	-0.3386	-0.2641
6	2.8375	2.85	2.8438	-0.2641	-0.2267

Ответ: x = 2.8438; F(x) = -0.2267
Решение было получено и оформлено с помощью сервиса Метод Ньютона онлайн

Пример №2 . Локализовать корень нелинейного уравнения f(x) = 0 и найти его методом бисекции с точностью ε₁ = 0,01. Выбрав полученное решение в качестве начального приближения, найти решение уравнения методом простой итерации с точностью ε₂ = 0,0001. Для метода простой итерации обосновать сходимость и оценить достаточное для достижения заданной точности ε₂ число итераций.

Содержание

Метод бисекции
Метод бисекции
Метод бисекции
Метод половинного деления (бисекции)
📸 Видео

Видео:14 Метод половинного деления Ручной счет Численные методы решения нелинейного уравненияСкачать

Метод бисекции

Метод бисекции или метод деления отрезка пополам — простейший численный метод приближённого нахождения корня уравнения.

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

Метод бисекции

Существует довольно очевидная теорема: «Если непрерывная функция на концах некоторого интервала имеет значения разных знаков, то внутри этого интервала у нее есть корень (как минимум, один, но может быть и несколько)». На базе этой теоремы построено несколько методов численного нахождения приближенного значения корня функции. Обобщенно все эти методы называются методами дихотомии, т. е. методами деления отрезка на две части (необязательно равные).

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

Итерационная формула проста:

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

В качестве критерия останова берут один из следующих:

— значение функции на данной итерации стало меньше заданого ε.

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

Видео:Метод половинного деления. ДихотомияСкачать

Метод половинного деления (бисекции)

Пусть функция y=f(x) удовлетворяет условиям теоремы 2.1 на отрезке [a,b], т.е. уравнение (2.1) имеет единственный корень на этом отрезке.

Метод половинного деления (бисекции) это один из простейших методов решения нелинейных уравнений. Приводим алгоритм и геометрическую интерпретацию (рис.2.5) этого метода.

Алгоритм метода бисекции.

1. Делим отрезок [a, b] пополам.

2. Если , то является корнем уравнения (2.1).

3. Если , то из двух отрезков выбираем тот, на концах которого функция f(x) имеет разные знаки.

Рис. 2.5. Схема метода бисекции

4. Новый «суженный» отрезок [a₁, b₁] снова делим пополам и проводим тот же анализ и т.д.

5. В результате получаем на каком-то этапе или точный корень уравнения (2.1), или же бесконечную последовательность вложенных друг в друга отрезков,

Для нахождения приближенного значения корня уравнения (2.1) с заданной точностью e необходимо циклически повторить следующую последовательность действий:

1. отрезок [a, b] делим пополам ,

2. если │f(x)│ > ε, переходим на пункт 3, иначе – на пункт 5,

3. если f(x)*f(b) ≤ 0, то принимаем a = x, иначе b = х. Т.е. из двух отрезков выбираем тот, на концах которого функция имеет разные знаки, и новый «суженный» отрезок вновь называем отрезком [a, b],

4. если │a-b│>ε, то выполняется пункт 1 , иначе – пункт 5.

5. в качестве приближенного решения уравнения (2.1) с заданной точностью ε принимается .

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

Метод хорд

Пусть функция y=f(x) на отрезке [a,b] удовлетворяет условиям теорем 2.1, т.е. уравнение f(x)=0 имеет на этом отрезке единственный корень x * .

Положим для определенности f ’’ (x)>0 (рис.2.6). Вместо деления отрезка пополам, разделим его в отношении f(a): f(b).

С геометрической точки зрения способ пропорциональных частей эквивалентен замене кривой y=f(x) хордой, проходящей через точки A[a, f(a)] и B[b, f(b)].

Для построения итерационной последовательности по методу хорд необходимо выбрать начальное приближение (нулевую итерацию) х_0.

Если функция y=f(x) имеет 2-ую производную, сохраняющую знак на этом отрезке, то начальное приближение х₀ выбирается, исходя из условия:

1. В качестве нулевого приближения корня выбирается тот конец отрезка [a,b], для которого выполняется условие (2.11), т.е выбираемправый конец отрезка [a, b], х₀=b.

2. Проводим хорду АВ₀ и за первое приближение (первую итерацию) х₁ принимаем абсциссу точки пересечения хорды с осью ОХ.

3. Второе приближение х₂ получаем как абсциссу точки пересечения хорды АВ₁ с осью ОХ.

4. Аналогичным образом строим итерационную последовательность:

В математическом анализе доказывается теорема, что эта итерационная последовательность сходится к корню уравнения х * (2.1).

Для получения формулы (n+1)-ой итерации х_n₊₁ запишем уравнение хорды AB_n :

Рис.2.6. Схема метода хорд (1-й случай)

В этом случае левый конец отрезка [a,b] неподвижен и последовательные приближения (итерации) определяются по формуле:

(2.13)

Второй случай. Полагаем f(а) 0 и f ’’ (x)>0 для xÎ[a,b] (рис.2.7).

В качестве нулевого приближения корня выбираем тот конец отрезка [a,b], для которого справедливо условие (2.11).

Для данного случаявыбирается левый конец отрезка [a,b], т.е. х₀ =а, а в качестве неподвижного конца: х=b.

Аналогично первому случаю строим последовательность приближений, сходящуюся к точному решению х * уравнения (2.1) и определяемую следующим соотношением:

(2.14)