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

1.3. Метод половинного делении

Этот метод приближенного решения базируется на следующей теореме.

Теорема 2. Если функция – непрерывная на функция и принимает на концах этого отрезка значения разных знаков ( ), то на интервале имеется не менее одного корня уравнения (1.1).

Вообще говоря, найдя отрезок изоляции корня , можно в качестве первого приближения точного значения корня взять середину этого отрезка . Конечно, точность такого приближения будет невелика, а именно, .

Смысл метода половинного деления (метод бисекции) состоит в уменьшении длины отрезка изоляции корня в 2 раза (а, значит, и увеличение точности в 2 раза). Дело в том, что если мы нашли отрезок изоляции корня , то, разбив его пополам, мы получим 2 отрезка: и , причем только один из них (!) содержит корень (редкую удачную ситуацию, когда точное значение корня совпадет с серединой отрезка изоляции можно не рассматривать). Таким образом, проверив условия теоремы 2 для каждого из полученных отрезков, один из них (для которого это условие будет выполнено) мы примем за новый отрезок изоляции корня. Отметим, что, так как при каждом делении пополам длина нового отрезка изоляции корня (а, значит, и погрешность) будет уменьшаться в 2 раза, то процесс деления следует продолжать до достижения заданной точности вычислений.

Алгоритм построения приближающих последовательностей и здесь такой:

1) находим отрезок изоляции корня и проверяем условия применения метода: и ;

2) задаем начальные приближения: , и приступаем к процессу деления;

3) если элементы и определены ( ), то полагаем и определяем элементы и по правилу:

Остановка вычислений производится при выполнении условия (1.2), приближенное значение корня определяется по формуле (1.3).

Достоинство метода: простота реализации, что позволяет самостоятельно и быстро запрограммировать алгоритм при использовании вычислительной техники.

Недостаток метода: при высокой заданной точности требуется находить достаточно большое число элементов приближающих последовательностей (хотя это несущественно при использовании компьютера).

Упражнение 1. Сделайте обоснование теоремы 2.

Упражнение 2. Докажите, что последовательности и будут приближающими, причем первая из них – монотонно неубывающая, а вторая – невозрастающая.

Упражнение 3. Покажите, что для данного метода неравенство (1.2) будет выполнено, если , где квадратная скобка означает взятие целой части числа.

Упражнение 4. Сделайте иллюстрацию для метода половинного деления.

Упражнение 5. Почему данный метод нельзя использовать в ситуации, указанной на рис. 1.2?

Пример 2. Найти все корни уравнения методом половинного деления с точностью до 0,01.

Решение. Представляя заданное уравнение в виде , и построив графики функций (сделайте это самостоятельно!) и , убеждаемся, что уравнение имеет только один корень, и он находится на отрезке . Итак, известен отрезок изоляции корня и задана точность . Рассматриваемое уравнение имеет вид (1.1) с левой частью . Найдём значения этой функции на концах отрезка: , .

Примем , . Проверим выполнение неравенства (1.4): – условие выполняется, значит можно применить метод половинного деления.

Найдём середину отрезка и вычислим значение функции в полученной точке:

Так как значения и имеют одинаковые знаки, а и – разные, то, согласно алгоритму метода половинного деления полагаем: . Т.е. отрезок примем за новый отрезок изоляции корня, и мы опять находим середину отрезка и вычисляем значение функции в этой точке:

, , , и – новый отрезок изоляции корня. Так как , то условие (1.2) не выполнено, и мы продолжим вычисления.

, , , , , . Итак, условие (1.2) выполнено, и мы по формуле (1.3) полагаем .

Применив правила округления, можем считать, что приближенное значение корня уравнения с точностью до 0,01.

Отметим, что согласно упражнению 3 необходимое для достижения заданной точности значение числа элементов приближающих последовательностей равно . Это же мы получили в процессе вычислений!

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

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

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

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

Дано уравнение вида:

необходимо найти удовлетворяющие ему значения 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<0, то точкой b станет c: b=c;

4) Вычислим разность a и b, сравним ее с точностью ?: если |a-b|> ?, то идем в пункт 1) если нет, то корень с нужной нам точностью найден, и он равен: x=(a+b)/2;

Определить корни уравнения x2 -3.2×2 -2.5x -5.4=0 аналетически и уточните их метдом половинного деления с точностью до 0.01

Описание метода половинного деления

Метод половинного деления один из методов решения нелинейных уравнений и основан на последовательном сужении интервала, содержащего единственный корень уравнения F(x)=0 до того времени, пока не будет достигнута заданная точность Е. Метод используется в задачах по математике при решении квадртных уравнений и уравнений высших степеней. Пусть задан отрезок [а,b], содержащий один корень уравнения. Этот отрезок может быть предварительно найден с помощью шагового метода.

Алгоритм метода половинного деления:

· Определить новое приближение корня х в середине отрезка [а,b]: х=(а+b)/2.

· Найти значения функции в точках а и х: F(a) и F(x).

· Проверить условие F(a)*F(x) < 0. Если условие выполнено, то корень расположен на отрезке [а,х]. В этом случае необходимо точку b переместить в точку х (b=х). Если условие не выполнено, то корень расположен на отрезке [х,b]. В этом случае необходимо точку а переместить в точку х (а=х).

· Перейти к пункту 1 и вновь поделить отрезок пополам. Алгоритм продолжить до того времени, пока не будет выполнено условие /F(x)/ < e.

Рис. 1. Иллюстрация метода половинного деления

Достоинство метода половинного деления: более быстрая сходимость к заданной точности, чем у шагового. Недостаток: если на отрезке [а,b] содержится более одного корня, то метод не работает.

6. Критерий останова процесса приближений значения искомого корня в методе дихотомии для решения нелинейного уравнения:

Алгоритм продолжить до того времени, пока не будет выполнено условие /F(x)/ < e.

Т,е пока не будет выполнена требуемая точность

7. Альтернативное название метода Ньютона для решения нелинейного уравнения по признаку используемого правила формирования итерационной формулы:

8. Основная итерационная формула, применяемая в методе Ньютона для решения нели-нейного уравнения:

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

Найти корень уравнения, принадлежащий интервалу [a,b] , с заданной точностью $\varepsilon$ .

Для уточнения корня методом половинного деления последовательно осуществляем следующие операции :

Делим интервал пополам:

$t=\frac<a+b> <2>\text < – координаты середины отрезка>[a,b];» /></p> <p><img decoding=$

a) Вычисляем значение функции f(x) в точках a и t .

b) Проверяем: если f(a)f(t) < 0 , то корень находится в левой половине интервала [a,b] (рис.4.4.а). Тогда отбрасываем правую половину интервала и делаем переприсвоение b=t .

c) Если f(a)f(t) < 0 не выполняется, то корень находится в правой половине интервала [a,b] (рис.4.4.б). Тогда отбрасываем левую половину и делаем переприсвоение a=t . В обоих случаях мы получим новый интервал [a,b] в 2 раза меньший предыдущего.

$\lvert b-a \rvert \le \varepsilon.$

Схема алгоритма уточнения корней по методу половинного деления представлена на рис. 4.5.

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

Метод простых итераций

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

Пусть с точностью $\varepsilon$ необходимо найти корень уравнения f(x)=0 , принадлежащий интервалу изоляции [a,b] . Функция f(x) и ее первая производная непрерывны на этом отрезке.

Для применения этого метода исходное уравнение f(x)=0 должно быть приведено к виду

$x=\varphi(x)$