Найти значение корня уравнения методом половинного деления

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

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

Метод половинного деления. Алгоритм

Решение алгебраического уравнения. Для численного решения алгебраических уравнений существует множество способов. Среди самых известных можно назвать метод Ньютона, метод Хорд, и «всепобеждающий» метод Половинного Деления. Сразу оговоримся, что любой метод является приближенным, и по сути дела лишь уточняющим значение корня. Однако уточняющим до любой точности, заданной Нами.

Метод половинного деления или дихотомии (дихотомия — сопоставленность или противопоставленность двух частей целого) при нахождении корня уравнения f(x)=0 состоит в делении пополам отрезка [a; b], где находится корень. Затем анализируется изменение знака функции на половинных отрезках, и одна из границ отрезка [a; b] переносится в его середину. Переносится та граница, со стороны которой функция на половине отрезка знака не меняет. Далее процесс повторяется. Итерации прекращаются при выполнении одного из условий: либо длина интервала [a; b] становится меньше заданной погрешности нахождения корня ?, либо функция попадает в полосу шума ?1 — значение функции сравнимо с погрешностью расчетов.

Сначала поставим задачу. Дана монотонная, непрерывная функция f(x), которая содержит корень на отрезке [a,b], где b>a. Определить корень с точностью ?, если известно, что f(a)*f(b) Дано уравнение вида:

необходимо найти удовлетворяющие ему значения x.

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

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

Ученикам метод половинного деления можно преподнести в виде решения задачи.

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

Над моделью этой задачи физики изрядно поработали. Оно и понятно: ведь многие научные задачи, как и эта, возникали прежде всего в военном деле. И решение этих задач почти всегда считалось приоритетным.

Какие же факторы принять за существенные в этой задаче? Поскольку речь идет о средневековье, то скорость снаряда и дальность полета невелики. Значит можно считать несущественным, что Земля круглая (помните обсуждение в параграфе 27), и пренебречь сопротивлением воздуха. Остается единственный фактор — сила земного притяжения.

Математик тут бы сказал, что надо решить уравнение. Мы тоже будем решать, только приближенно и очень похоже на то, как делают настоящие артиллеристы. Они же поступают следующим образом: производят несколько выстрелов, беря цель «в вилку», т.е. одно попадание выше цели, а другое ниже. Затем делят пополам угол между этими выстрелами, и при стрельбе под таким углом снаряд ложится к цели намного ближе. Но если все же не попали, то новую «вилку» снова делят пополам и т.д.

Мы заранее можем указать «вилку» для угла: 0 и ?/4 (мы надеемся, что вы помните какой угол имеет радианную меру ?/4 и чему приближенно равно ?). А дальше будем делить пополам эту «вилку» и смотреть, куда попадает снаряд, пока не добьемся нужного результата.

Как же долго нам придется вести «пристрелку», чтобы получить угол ?, с нужной точностью? Чтобы ответить на этот вопрос, отвлечемся от нашей задачи и сформулируем на чисто математическом языке, что и как мы находили.

Нам даны некоторая функция f(x) и отрезок [a;b], причем на концах этого отрезка эта функция принимает значения противоположных знаков. Если функция непрерывна, т.е. ее график — непрерывная линия, то ясно, что график функции пересекает ось абцисс в некоторой точке с отрезка [a;b], как показано на рисунке 1. Иными словами, f(c)=0, т.е. с — корень уравнения f(x)=0.

Как же предлагается находить этот корень? А вот так. Делим отрезок [a;b] пополам, т.е. берем середину отрезка а+b/2. В этой точке вычисляем значение функции f(x) (рис. 2). Если это значение 0, то корень найден; если нет, то оно имеет тот же знак, что и значение на одном из концов отрезка [a;b]. Тогда этот конец заменям точкой а+b/2. Новый отрезок тоже содержит корень уравнения f(x)=0, поскольку на его концах функция f(x) снова имеет разные знаки. Однако этот отрезок в 2 раза короче предыдущего. И самое главное — с ним можно поступить точно так же. со следующим отрезком еще раз проделать то же самое и т.д. поскольку длина отрезка каждый раз уменьшается вдвое, мы можем получить отрезок сколь угодно малой длины, внутри которого содержится корень уравнения f(x)=0. Например, если исходный отрезок был [3;4], т.е. имел длину 1, то через десять шагов мы получим отрезок длиной. Это означает, что концы отрезка дают нам приближенное значение корня с точностью, равной длине отрезка: левый конец отрезка — приближенное значение корня с недостатком, правый конец — приближенное значение корня с избытком.

Фактически мы сейчас сформулировали метод приближенного решения уравнения f(x)=0. Его можно было бы назвать методом артиллерийской пристрелки. Но математики называют его методом половинного деления.

Далее ученикам предлагается записать алгоритм и блок-схему нахождения корня уравнения с помощью метода половинного деления.

1) Найдем середину отрезка [a; b]: c=(a+b)/2;

2) Вычислим значения функции в точках a и c и найдем произведение полученных значений: d=f(c)?f(a);

3) Если d>0, то теперь точкой a станет c: a=c; Если d ?, то идем в пункт 1) если нет, то корень с нужной нам точностью найден, и он равен: x=(a+b)/2;

Метод половинного деления. Один из методов уточнения корней уравнения (1) – метод половинного деления

Один из методов уточнения корней уравнения (1) – метод половинного деления. Исходные данные: уравнение f(x)=0; отрезок [a,b], на котором существует единственный корень уравнения (корень отделен), т.е. f(x) удовлетворяет условиям: f(x) непрерывна на [a,b], монотонна нем и f(a)f(b) 0 (знаки функции f(x) в точках a и c одинаковы), то левый конец отрезка заменяется на середину (а=с) иначе правый конец заменяется на середину (b=c).

4. Если длина отрезка не превосходит заданной точности (b-a 4 -x 3 -2x 2 +3x-3=0.

Полагая f(x)= x 4 -x 3 -2x 2 +3x-3, имеем f’(x)=4x 3 -3x 2 -4x+3.

Найдем нули производной: 4x 3 -3x 2 -4x+3=0; 4x(x 2 -1)-3(x 2 -1)=0;(x 2 -1)(4x-3)=0;

Составим таблицу знаков функции f(x):

x	-∞	-1	3/4	+∞
f(x)	+	—	—	—	+

Из таблицы видно, что уравнение имеет два действительных корня x₁ (-∞;-1) и x₂ (1;+ ∞). Уменьшим промежутки, на которых находятся корни, до единичной длины:

x	-2	-1
f(x)	+	—	—	+

Следовательно, x₁ (-2;-1) и x₂ (1;2).

Уточним один из корней, например, x₁, методом половинного деления до сотых долей. Все вычисления удобно производить, используя следующую таблицу:

Второй корень, уточняемый аналогичным образом, равен 1,73.

2. Отделить корни графически и уточнить их методом половинного деления.

Перепишем уравнение в виде . Обозначим , и построим графики этих функций:

Из рисунка видно, что уравнение имеет три корня: точный x=0 и еще два, расположенных симметрично на отрезках [-3;-2] и [2;3].

Уточним корень на отрезке [2;3]:

Задания

1)Отделить корни аналитически и уточнить их методом половинного деления до 0,01, используя электронные таблицы.

1. 3x 4 +4x 3 -12x 2 -5=0

2. 2x 3 -9x 2 -60x+1=0

5. 3x 4 +3x 3 +6x 2 -10=0

7. x 4 +4x 3 -3x 2 -17=0

8. x 4 -x 3 -2x 2 +3x-3=0

9. 3x 4 +4x 3 -12x 2 +1=0

10. 3x 4 -8x 3 -18x 2 +2=0

11. 2x 4 -3x 3 +8x 2 -1=0

12. 2x 4 +8x 3 +3x 2 -1=0

13. x 4 -4x 3 -8x 2 +1=0

14. 3x 4 +4x 3 -12x 2 -5=0

15. 2x 3 -8x 2 -30x+1=0

17. 2x 4 -2x 2 -7=0

18. 3x 4 +8x 3 +6x 2 -10=0

19. x 4 -18x 2 +6=0

20. x 4 +4x 3 -3x-7=0

21. x 4 -2x 3 -x 2 +3x-3=0

22. 3x 4 +4x 3 -3x 2 -17=0

23. 2x 4 -5x 3 -12x 2 +2=0

24. 3x 4 +9x 3 -14x 2 +1=0

25. x 4 +2x 3 -x-1=0

26. x 4 +8x 3 -6x 2 -72x=0

28. x 4 -3x 2 +75x-10000=0

2) Отделить корни графически и уточнить их методом половинного деления до 0.01, используя электронные таблицы.

Лабораторная работа №3

Решение нелинейных уравнений методом хорд

Краткая теория

Будем рассматривать уравнения вида f(x)=0 (1). Пусть корень уравнения отделен и находится на отрезке [a,b]. Уточним этот корень методом хорд. Геометрически метод хорд означает замену на отрезке [a,b] графика функции y=f(x) хордой, проведенной через точки (a,f(a)) и (b,f(b)):

Здесь ξ — точный корень уравнения (1), x — начальное приближение к корню, x -точка пересечения хорды с осью Ох – первое приближение к корню. Далее метод хорд применяется на отрезке [a, x ] и получается второе приближение к корню — x . В случае, изображенном на рис.1, конец отрезка а остается неподвижным. Из уравнения хорды и условия, что точка (x ,0) принадлежит хорде, получается формула для вычисления n-го приближения к корню для случая, когда а – неподвижный конец: x =b,

x =a- (2)

Для случая неподвижного конца b используется формула: x =a,

x =x — (3)

Правило определения неподвижного конца хорды:

Если знаки первой и второй производных функции f(x) на отрезке [a, b] совпадают, то неподвижным являются конец b, иначе — конец a.

Метод хорд обеспечивает на n-м шаге абсолютную погрешность приближения к корню уравнения (1), не превосходящую длину n-го отрезка:

1. Определить, какой конец отрезка будет неподвижным и принять за x другой конец отрезка.

2. Вычислить новое приближение к корню x по формуле (2) или (3).

3. Если длина отрезка [x , x ] не превосходит заданной точности, то процесс заканчивается и в качестве точного корня можно взять x или x , иначе идти к п.2

Решение одного варианта

1.Отделить корни графически и уточнить их методом хорд с точностью до 0.001: tg(0.5x+0.1)=x .