Решение уравнений с одной переменной метод половинного деления

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

Теорема 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
Остальные расчеты сведем в таблицу.

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

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

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

Домашняя лабораторная работа по теме «Приближенное решение уравнений с одной переменной»

Задание. Найти один из корней уравнения методом деления отрезка пополам (методом Фибоначчи, «золотого сечения», рандомизации) с точностью до : 1) отделить корень на отрезке , проверить его единственность; 2) реализовать один из методов деления отрезка в заданном отношении (использовать ЭВМ или калькулятор); 3) сделать проверку точности найденного решения подстановкой его в исходное уравнение.

Порядок выполнения работы

1) Графическое отделение корня в случае достаточно сложного выражения y=f(х) можно производить следующим образом. Допустим, что уравнение можно представить в виде f₁(x) = f₂(x). В этом случае строим графики функций у=f₁(x) и y=f₂(x); абсциссы точек пересечения кривых будут действительными корнями уравнения. Найдем, например, приближенно корни уравнения x-sin x-1 = 0, записав это уравнение в виде x-1 = sin x. Построим графики функций y = sin x и у = х-1 (рис.2). Точка пересечения этих линий имеет абсциссу х ≈ 1,9, что можно считать грубым приближением значения корня.

Интервал [а;b] является интервалом изоляции корня, если его можно считать настолько малым, что на нем лежит точно один корень исходного уравнения. Выбор этого интервала производится на основании свойства непрерывных функций: если функция у=f(x) непрерывна на отрезке [а;b] и на концах отрезка принимает значения разных знаков (f(a)f(b) 3 +x 2 -1=0. Для этого представим уравнение в виде: х 3 =1-x 2 , т. е. f(x)=x 3 и g(x)=1-x 2 . Построим приближенно графики функций y=f(x) и y=g(x) (рис 4). Точка пересечения графиков двух функций, а значит, и корень уравнения находится на отрезке [0;1]. Проверим аналитические условия: f(0)=0 3 +0 2 -1=-1 3 +1 2 -1=1>0, и f'(х)=3х²+2x>0 на отрезке [0;1]. Таким образом, мы определили интервал изоляции корня, для нахождения которого достаточно применить любой из аналитических методов численного решения уравнений.

Задача отыскания корней уравнений может считаться практически решенной, если удалось определить корни с нужной степенью точности и указать пределы возможной погрешности.

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

Рассмотрим один из самых простых численных методов решения уравнений – метод половинного деления. Пусть для уравнения найден интервал изоляции корня – отрезок [а;b]. Для уточнения искомого корня отрезок [а;b] делим пополам и из двух, полученных в результате этого деления отрезков выбираем тот, для которого выполняются условия существования и единственности корня (на концах отрезка функция принимает значения разных знаков). Середину отрезка находим по формуле х_i=(a+b)/2, i=1,2,3…, и продолжаем данный процесс пока не достигнем необходимой точности (рис.5).

Рассмотрим применение метода половинного деления на примере решения уравнения х 3 +x 2 -1 = 0 на отрезке [0;1]. Разделим интервал изоляции пополам – это точка х=0,5. Получим два подотрезка – [0;0,5] и [0,5;1]. Вычислим значения функции на концах отрезков, f(0)=-1 3 +0,5 2 -1=0,125+0,25-1=-0,625 3 +1 2 -1=1+1—1=1>0, т. е. на концах отрезка [0,5;1] функция имеет значения разных знаков, следовательно, корень уравнения принадлежит отрезку [0,5;1]. Выбираем этот отрезок для дальнейшего рассмотрения.

Повторяем метод половинного деления уже для нового отрезка. Середина отрезка x=(0,5+1)/2=0,75, и из двух полученных отрезков выбираем правый отрезок [0,75;1], т.к. f(0,75) = -0,015625 0. Процесс продолжается до получения корня с заданной степенью точности.

Если делить отрезок [a;b] сразу на десять частей, то на следующем шаге можно получить отрезок в десять раз меньший, чем [a;b].

2. Метод Фибоначчи

Рассмотрим одну из разновидностей метода половинного деления – метод Фибоначчи.

Пусть дано уравнение , где функция у= непрерывна на и . Для уточнения корня данного уравнения введем последовательность чисел Фибоначчи: , , , это будут числа 1,1,2,3,5,8,13,21 и т.д. Согласно данному методу, на каждом ом этапе отрезок делят в отношении , где и соответственно е и е число из последовательности Фибоначчи. Так на первом шаге отрезок делят в отношении (пополам) и выбирают тот из них, на концах которого функция имеет разные знаки. На втором этапе выбранный суженный отрезок делят в отношении , следующие в отношениях , , В результате получаем на некотором этапе точный корень уравнения, или же бесконечную последовательность отрезков таких, что (n=1,2,…). Формула для вычисления имеет вид: В качестве корня можем принять .

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

Считаем, что отделение корней уравнения f ( x) = 0 проведено и на отрезке [ a, b] расположен один корень, который необходимо уточнить с погрешностью ε. В качестве начального приближения корня принимаем середину этого отрезка: c₀ = (a + b) / 2 (рис. 4):

Рис. 4. Метод половинного деления.

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

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

Прекратить итерационный процесс следует, когда будет достигнута заданная точность, т.е. при выполнении условия |x₀ – c_k|

Дата добавления: 2017-09-19 ; просмотров: 3750 ; ЗАКАЗАТЬ НАПИСАНИЕ РАБОТЫ