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

1.3 Метод половинного деления (метод дихотомии)

Метод половинного деления основан на последовательном делении отрезка локализации корня пополам.

Для этого выбирается начальное приближение к отрезку [a, b], такое, что f(a)×f(b)<0, затем определяется знак функции в точке — середине отрезка [a, b]. Если он противоположен знаку функции в точке a, то корень локализован на отрезке [a, c], если же нет – то на отрезке [c, b]. Схема метода дихотомии приведен на рисунке 2.

Рисунок 2. Последовательное деление отрезка пополам и приближение к корню

Алгоритм метода дихотомии можно записать так:

1. представить решаемое уравнение в виде

2. выбрать a, b и вычислить

3. если f(a)×f(с)<0, то a=a; b = c иначе a = c; b=b

4. если критерий сходимости не выполнен, то перейти к п. 2

Пример решения уравнения методом дихотомии

Найти решение заданного уравнения методом дихотомии с точностью до 10 -5 .

Пример создания расчетной схемы на основе метода дихотомии на примере уравнения: на отрезке [1, 2]

Данный метод заключается в проверке на каждой итерации условия:

если f(a)×f(с)<0и выбор соответствующего отрезка для следующей итерации.

Рисунок 3. Последовательность итераций метода дихотомии при поиске корня уравнения на отрезке [1, 2]

a) схема расчета (зависимые ячейки); b) режим отображения формул;

Для нашего примера итерационная последовательность для нахождения решения принимает вид:

Точность до пятой значащей цифры достигается за 20 итераций.

Скорость сходимости этого метода является линейной.

При выполнении начального условия он сходится к решению всегда.

Метод половинного деления удобен при решении физически реальных уравнений, когда заранее известен отрезок локализации решения уравнения.

2 Решение уравнений, используя “Подбор параметра”

Используя возможности Excel можно находить корни нелинейного уравнения вида f(x)=0 в допустимой области определения переменной. Последовательность операций нахождения корней следующая:

Производится табулирование функции в диапазоне вероятного существования корней;

По таблице фиксируются ближайшие приближения к значениям корней;

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

При подборе параметра Excel использует итерационный (циклический) процесс. Количество итераций и точность устанавливаются в меню Сервис/Параметры/вкладка Вычисления. Если Excel выполняет сложную задачу подбора параметра, можно нажать кнопку Пауза в окне диалога Результат подбора параметра и прервать вычисление, а затем нажать кнопку Шаг, чтобы выполнить очередную итерацию и просмотреть результат. При решении задачи в пошаговом режиме появляется кнопка Продолжить — для возврата в обычный режим подбора параметра.

2.1 Пример решения уравнения, используя “Подбор параметра”

Например, найдем все корни уравнения 2x 3 -15sin(x)+0,5x-5=0 на отрезке [-3 ; 3].

Для локализации начальных приближений необходимо определить интервалы значений Х, внутри которых значение функции пересекает ось абсцисс, т.е. функция меняет знак. С этой целью табулируем функцию на отрезке [–3; 3] с шагом 0,2, получим табличные значения функции. Из полученной таблицы находим, что значение функции трижды пересекает ось Х, следовательно, исходное уравнение имеет на заданном отрезке все три корня.

Рисунок 4. Поиск приближенных значений корней уравнения

Выполните команду меню Сервис/Параметры, во вкладке Вычисления установите относительную погрешность вычислений E=0,00001, а число итераций N=1000, установите флажок Итерации.

Выполните команду меню Сервис/Подбор параметра. В диалоговом окне (рисунок 9) заполните следующие поля:

Установить в ячейке: в поле указывается адрес ячейки, в которой записана формула правой части функции;

Значение: в поле указывается значение, которое должен получить полином в результате вычислений, т.е. правая часть уравнения (в нашем случае 0);

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

Рисунок 5. Диалоговое окно Подбор параметра для поиска первого корня

После щелчка на ОКполучим значение первого корня-1,65793685.

Выполняя последовательно операции аналогичные предыдущим, вычислим значения остальных корней: -0,35913476 и 2,05170101.

ПОЛОВИННОГО ДЕЛЕНИЯ МЕТОД

метод дихотомии,- 1) Один из методов численного решения уравнений с одним неизвестным. Пусть имеется уравнение f(x) = 0 с непрерывной на отрезке [а, b]функцией f(х), принимающей на концах отрезка значения разных знаков и имеющей внутри [а, b]единственный корень х * . Для приближенного нахождения х * отрезок [ а, b]делят пополам и вычисляют значение f(x 1 ). в средней точке x 1 =(a+b)/2. Если , то из двух отрезков [ а, х 1 ]и [ х 1 , b]. для последующего деления пополам выбирается тот, на концах к-рого значения функции различны по знаку. Возникающая в процессе такого дробления последовательность середин отрезков х 1 , х 2 , . . . сходится к корню х * со скоростью геометрич. прогрессии:

(1)

причем в рассматриваемом классе функций оценка (1) неулучшаема. В случае, когда функция f(x).имеет на [ а, b] более одного корня, последовательность будет сходиться к одному из них.

2) Один из методов минимизации функций одного переменного. Пусть требуется найти минимум

унимодальной функции f(х).на отрезке [ а, b]и указать точку x * , в к-рой он достигается. Тогда отрезок [а, b]делят пополам и вблизи его середины вычисляют значения функции f(x).в двух точках , где число e>0, являющееся параметром метода, достаточно мало. Затем значения f(x 1 ).и f(x 2 ) сравнивают и с учетом унимодальности функции f(x).из двух отрезков [ а, х 2 ] и [x l , b]выбирают тот, к-рый заведомо содержит точку х * . Так, если , это будет отрезок [ а, х 2 ], в противном случае — отрезок [a, b]. Выбранный отрезок вновь делят пополам, вблизи его середины берут две точки , сравнивают в них значения функции и т. д. В результате возникает последовательность срединных точек , для к-рой

(2)

За приближения к f * принимают значения при достаточно больших n.

Название метода объясняется тем, что на каждом следующем шаге описанного алгоритма отрезок, содержащий точку минимума, становится примерно вдвое короче. На классе унимодальных, функций П. д. м. не является наилучшим. Существуют более эффективные методы, позволяющие при том же количестве вычислений значений функции достигнуть лучшей по сравнению с (2) точности (см., напр., Фибоначчи метод).

Лит.:[1] Демидович Б. П., Марон И. А., Основы вычислительной математики, 3 изд., М., 196В; [2] Уайлд Д.-Дж., Методы поиска экстремума, пер. с англ., М., 1967.

Математическая энциклопедия. — М.: Советская энциклопедия . И. М. Виноградов . 1977—1985 .

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

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

Метод половинного деления или дихотомии (дихотомия — сопоставленность или противопоставленность двух частей целого) при нахождении корня уравнения 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

Методы дихотомии

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

1. Задать начальный интервал ;
2. Убедиться, что на концах функция имеет разный знак;
3. Повторять
   • выбрать внутри интервала точку ;
   • сравнить знак функции в точке со знаком функции в одном из концов;
     • если совпадает, то переместить этот конец интервала в точку ,
     • иначе переместить в точку другой конец интервала;

Варианты метода дихотомии различаются выбором точки деления. Рассмотрим варианты дихотомии: метод половинного деления и метод хорд.

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

Метод половинного деления известен также как метод бисекции. В данном методе интервал делится ровно пополам.

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

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

1. Один из простых способов поиска корней функции одного аргумента.
2. Применяется для нахождения значений действительно-значной функции, определяемому по какому-либо критерию (это может быть сравнение на минимум, максимум или конкретное число).

Метод половинного деления как метод поиска корней функции

Изложение метода

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

Будем считать, что корень функции отделён на отрезке . Задача заключается в том, чтобы найти и уточнить этот корень методом половинного деления. Другими словами, требуется найти приближённое значение корня с заданной точностью .

Пусть функция непрерывна на отрезке ,

и — единственный корень уравнения .

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

Поделим отрезок пополам. Получим точку и два отрезка .

• Если , то корень найден ().
• Если нет, то из двух полученных отрезков и надо выбрать один такой, что , то есть
  • , если или
  • , если .

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

  Реализация метода на С++ и числовой пример

  Решим уравнение методом половинного деления. Графическим методом находим отрезок , которому принадлежит искомый корень. Так как , то принимаем .

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

  Программа 1. Корень уравнения

  Искомый корень . Вычисления проводились с точностью .

  Промежуточные вычисления представлены в таблице ниже.

  n	an	bn	cn	bn-cn
  1	0	1	0.5	0.5
  2	0.5	1	0.75	0.25
  3	0.75	1	0.875	0.125
  4	0.875	1	0.9375	0.0625
  5	0.875	0.9375	0.90625	0.03125
  6	0.875	0.90625	0.890625	0.015625
  7	0.875	0.890625	0.8828125	0.0078125

  Метод половинного деления как метод оптимизации

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

  Рассмотрим метод половинного деления как простейший однопараметрический метод безусловной оптимизации. Данный метод является методом прямого поиска. В нем при поиске экстремума целевой функции используются только вычисленные значения целевой функции.

  Дана функция . Необходимо найти , доставляющий минимум (или максимум) функции на интервале с заданной точностью , т.е. найти

  Запишем словесный алгоритм метода.

  1. На каждом шаге процесса поиска делим отрезок пополам, — координата середины отрезка .
  2. Вычисляем значение функции в окрестности вычисленной точки , т.е.
     .
  3. Сравниваем и и отбрасываем одну из половинок отрезка (рис. 1).
     • При поиске минимума:
       • Если , то отбрасываем отрезок , тогда . (рис. 1.а)
       • Иначе отбрасываем отрезок , тогда . (рис. 1.б)
     • При поиске максимума:
       • Если , то отбрасываем отрезок , тогда .
       • Иначе отбрасываем отрезок , тогда .
  4. Деление отрезка продолжается, пока его длина не станет меньше заданной точности , т.е. .

  Схема алгоритма метода представлена на рис 2.

  При выводе – координата точки, в которой функция имеет минимум (или максимум), – значение функции в этой точке.

  Метод хорд

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

  Изложение метода

  Метод основан на замене функции на каждом шаге поиска хордой, пересечение которой с осью дает приближение корня.

  

  При этом в процессе поиска семейство хорд может строиться:

  1. при фиксированном левом конце хорд, т.е. , тогда начальная точка (рис. 3а);
  2. при фиксированном правом конце хорд, т.е. , тогда начальная точка (рис. 3б);

  В результате итерационный процесс схождения к корню реализуется рекуррентной формулой:

  • для случая а):
  • для случая б):

  

  Процесс поиска продолжается до тех пор, пока не выполнится условие или .

  Метод обеспечивает быструю сходимость, если , т.е. хорды фиксируются в том конце интервала , где знаки функции и ее кривизны совпадают.

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

  Комбинация метода хорд и метода половинного деления

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

  Если применять аналогичное уточнение к интервалу, полученному методом хорд, то эффект будет значительно слабее. Это ещё раз иллюстрирует тот факт, что метод хорд очень хорошо работает в условиях малого интервала (близости обеих границ интервала к корню), но неспособен сам создать себе эти условия (приблизить обе границы к корню).

  На вопрос о том, стоит ли использовать попеременное применение метода половинного деления и метода хорд, ответ отрицателен. После того, как метод хорд приближает одну из границ почти вплотную к корню, методу половинного деления придётся долго работать, чтобы гарантировать заданную точность, т.к. метод хорд ее гарантировать не может.

  Поэтому лучше использовать в качестве точки деления что-то среднее: если метод половинного деления предлагает использовать , а метод хорд — , то возьмем . Коэффициент .

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

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

  Похожие публикации:

  1. Астра линукс как настроить wi fi
  2. Как включить содержимое в excel
  3. Когда будет обновление в хай дей
  4. Тоже что иконка программы