В чем заключается метод половинного деления

Метод дихотомии в Excel

Чтобы отыскать предварительные интервалы, строим график функции.

Как видно, первый корень лежит в интервале [-2;2], второй корень функции находится в интервале [2;4].
Уточним интервалы, в которых будут находиться корни уравнения. Для этого исходный интервал [2;4] разобьем на 10 подынтервалов.
h₅ = 2 + 5*(4-2)/10 = 3
h₆ = 2 + (5+1)*(4-2)/10 = 3.2
Поскольку F(3)*F(3.2)Итерация 1.
Находим середину отрезка: c = (3 + 3.2)/2 = 3.1
F(c) = 0.13
F(x) = 0.42
Поскольку F(c)•F(x) > 0, то a=3.1
Итерация 2.
Находим середину отрезка: c = (3.1 + 3.2)/2 = 3.15
F(c) = -0.0265
F(x) = 0.13
Поскольку F(c)•F(x) < 0, то b=3.15
Итерация 3.
Находим середину отрезка: c = (3.1 + 3.15)/2 = 3.13
F(c) = 0.0518
F(x) = 0.13
Поскольку F(c)•F(x) > 0, то a=3.13
Итерация 4.
Находим середину отрезка: c = (3.13 + 3.15)/2 = 3.14
F(c) = 0.0128
F(x) = 0.0518
Поскольку F(c)•F(x) > 0, то a=3.14
Остальные расчеты сведем в таблицу.

N	c	a	b	f(c)	f(x)
1	3.1	3	3.2	0.1289	0.1289
2	3.15	3.1	3.2	0.1289	-0.02648
3	3.125	3.1	3.15	0.05185	0.05185
4	3.1375	3.125	3.15	0.01284	0.01284
5	3.1438	3.1375	3.15	0.01284	-0.00678
6	3.1406	3.1375	3.1438	0.00304	0.00304
7	3.1422	3.1406	3.1438	0.00304	-0.00187
8	3.1414	3.1406	3.1422	0.000586	0.000586

Ответ: x = 3.14; F(x) = 0.000586
Количество итераций, N = 8
Параметр сходимости.

Метод дихотомии в Excel

Чтобы отыскать предварительные интервалы, строим график функции.

Как видно, первый корень лежит в интервале [-2;2], второй корень функции находится в интервале [2;4].
Уточним интервалы, в которых будут находиться корни уравнения. Для этого исходный интервал [2;4] разобьем на 10 подынтервалов.
h₅ = 2 + 5*(4-2)/10 = 3
h₆ = 2 + (5+1)*(4-2)/10 = 3.2
Поскольку F(3)*F(3.2)Итерация 1.
Находим середину отрезка: c = (3 + 3.2)/2 = 3.1
F(c) = 0.13
F(x) = 0.42
Поскольку F(c)•F(x) > 0, то a=3.1
Итерация 2.
Находим середину отрезка: c = (3.1 + 3.2)/2 = 3.15
F(c) = -0.0265
F(x) = 0.13
Поскольку F(c)•F(x) < 0, то b=3.15
Итерация 3.
Находим середину отрезка: c = (3.1 + 3.15)/2 = 3.13
F(c) = 0.0518
F(x) = 0.13
Поскольку F(c)•F(x) > 0, то a=3.13
Итерация 4.
Находим середину отрезка: c = (3.13 + 3.15)/2 = 3.14
F(c) = 0.0128
F(x) = 0.0518
Поскольку F(c)•F(x) > 0, то a=3.14
Остальные расчеты сведем в таблицу.

N	c	a	b	f(c)	f(x)
1	3.1	3	3.2	0.1289	0.1289
2	3.15	3.1	3.2	0.1289	-0.02648
3	3.125	3.1	3.15	0.05185	0.05185
4	3.1375	3.125	3.15	0.01284	0.01284
5	3.1438	3.1375	3.15	0.01284	-0.00678
6	3.1406	3.1375	3.1438	0.00304	0.00304
7	3.1422	3.1406	3.1438	0.00304	-0.00187
8	3.1414	3.1406	3.1422	0.000586	0.000586

Ответ: x = 3.14; F(x) = 0.000586
Количество итераций, N = 8
Параметр сходимости.
Финансовый анализ онлайн

Анализ и диагностика финансово-хозяйственной деятельности предприятия:
· Оценка имущественного положения
· Анализ ликвидности и платежеспособности
· Анализ финансовой устойчивости
· Анализ рентабельности и оборачиваемости
· Анализ движения денежных средств
· Анализ финансовых результатов и многое другое

Аннуитетные платежи онлайн

Расчет аннуитетных платежей по схеме постнумерандо и пренумерандо с помощью удобного калькулятора.

Профессии будущего

РБК Тренды изучили прогнозы российских и зарубежных футурологов, и составили список самых востребованных профессий в ближайшие 30 лет. Это профессии из 19 отраслей: от медицины и транспорта до культуры и космоса

• Задать вопрос или оставить комментарий
• Помощь в решении
• Поиск
• Поддержать проект

Правила ввода данных

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

Поиск

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

Метод половинного деления — Структура и интерпретация компьютерных программ

Остались вопросы? Задайте их в разделе «Обсуждение»

Вам ответят команда поддержки Хекслета или другие студенты

Об обучении на Хекслете

• Статья «Как учиться и справляться с негативными мыслями»
• Статья «Ловушки обучения»
• Статья «Сложные простые задачи по программированию»
• Вебинар « Как самостоятельно учиться »

Открыть доступ

Курсы программирования для новичков и опытных разработчиков. Начните обучение бесплатно

• 130 курсов, 2000+ часов теории
• 1000 практических заданий в браузере
• 360 000 студентов

Наши выпускники работают в компаниях:

Используйте Хекслет по-максимуму!

• Задавайте вопросы по уроку
• Проверяйте знания в квизах
• Проходите практику прямо в браузере
• Отслеживайте свой прогресс

Для перемещения по курсу нужно зарегистрироваться
1. Информатика как наука ↳ теория
2. Примитивные выражения, комбинирование и абстракция ↳ теория
3. Процедуры как абстракции ↳ теория / упражнение
4. Процедуры и порождаемые ими процессы 1 ↳ теория
5. Процедуры и порождаемые ими процессы ↳ теория / упражнение
6. Древовидная рекурсия ↳ теория / упражнение
7. Порядки роста ↳ теория
8. Возведение в степень ↳ теория
9. Наибольший общий делитель ↳ теория
10. Проверка на простоту ↳ теория
11. Процедуры в качестве аргументов ↳ теория
12. Построение процедур с помощью lambda ↳ теория
13. Создание локальных переменных ↳ теория
14. Метод половинного деления ↳ теория
15. Нахождение неподвижных точек функций ↳ теория
16. Процедуры как возвращаемые значения ↳ теория / упражнение
17. Метод Ньютона ↳ теория

Поможем, если трудно

Порой обучение продвигается с трудом. Сложная теория, непонятные задания… Хочется бросить. Не сдавайтесь, все сложности можно преодолеть. Рассказываем, как

Не понятна формулировка, нашли опечатку?

Выделите текст, нажмите ctrl + enter и опишите проблему, затем отправьте нам. В течение нескольких дней мы улучшим формулировку или исправим опечатку

Что-то не получается в уроке?

Загляните в раздел «Обсуждение»:

1. Изучите вопросы, которые задавали по уроку другие студенты — возможно, ответ на ваш уже есть
2. Если вопросы остались, задайте свой. Расскажите, что непонятно или сложно, дайте ссылку на ваше решение. Обратите внимание — команда поддержки не отвечает на вопросы по коду, но поможет разобраться с заданием или выводом тестов
3. Мы отвечаем на сообщения в течение 2-3 дней. К «Обсуждениям» могут подключаться и другие студенты. Возможно, получится решить вопрос быстрее!

Подробнее о том, как задавать вопросы по уроку

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

Данный метод описывает алгоритм нахождение корней (нулей) функции. Чтобы найти минимум целевой функции методом дихотомии используйте этот калькулятор.

Считаем, что отделение корней произведено и на интервале [a,b] расположен один корень, который необходимо уточнить с погрешностью ε.
Итак, имеем f(a)f(b)1. Если |f(c)| < ε, то c – корень. Здесь ε - заданная точность.
2. Если f(c)f(a)3. Если f(c)f(b)Продолжая процесс половинного деления в выбранных подынтервалов, можно дойти до сколь угодно малого отрезка, содержащего корень ξ.
Так как за каждую итерацию интервал, где расположен корень уменьшается в два раза, то через n итераций интервал будет равен:
при этом a_n≤ξ≤b_n, , .
В качестве корня ξ. возьмем =½(b_n+a_n). Тогда погрешность определения корня будет равна (b_n – a_n)/2. Если выполняется условие (b_n–a_n)/2n+a_n).
см. более подробный алгоритм метода бисекции.

Теорема 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)|ξ₁— ξ₀|, |ξ₂— ξ₁|, …, |ξ_n— ξ_n-1|.
Имеем |ξ₁-ξ₀|=½(b₁+a₁-b₀-a₀). Так как всегда имеем либо b₁=b₀, a₁=½(b₀+a₀), либо a₁=a₀, b₁=½(a₀+b₀), поэтому , если, b₁=b₀
либо , если a₁=a₀.
Повторяя аналогичные рассуждения и учитывая, что всегда выполняется соотношение либо b_i=b_i-1, a_i=½(b_i-1+a_i-1), либо b_i=½(b_i-1+a_i-1), a_i=a_i-1. Получим
;
;
, где a₀=a, b₀=b.
Отсюда видно, что какое бы малое число ε>0 мы ни задали, всегда можно найти такое n , что ч.т.д.
Графически метод дихотомии выглядит следующим образом

Сходимость метода дихотомии линейная с коэффициентом α=0,5. Покажем это.
Если в качестве x_n брать a_n, то из формулы (6) мы можем записать , . Отсюда следует .
Отметим, что за 10 итераций (n=10) интервал уменьшается в 2 10 = 1024 ≈ 10 3 раз. За 20 итераций (n=2) уменьшается в 2 20 ≈ 10 6 раз.

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

Находим производную функции: y ‘ = 10x-4. Найдем нули функции методом дихотомии: y’=0.
Поскольку F(0)*F(10) Пример №2 . Методом дихотомического поиска найдите максимумы функций, пологая, что Δ=0,05.
f(x) = x*cos(x), 0 ≤x≤ π

Пример №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. Для метода простой итерации обосновать сходимость и оценить достаточное для достижения заданной точности ε₂ число итераций.