Метод основан на делении текущего отрезка [а , b ], где содер­жится искомый экстремум, на две равные части с последующим выбором одной из половин, в которой локализуется минимум (максимум) в качестве следующего текущего отрезка. Экстремум локализуется путем сравнения двух значений критерия оптимальности в точках, отстоящих от середины отрезка на ε /2, где ε –погрешность решения задачи оптимизации.

Если R (x + ε /2) > R (x – ε /2), то максимум располагается на правой половине текущего отрезка [а, b ], в противном случае – на левой.

Процесс поиска завершается при достижении отрезком [а, b ] величины заданной погрешности е ε .

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

На рис. 2 приведены три этапа метода половинного деления. Сплошными вертикальными линиями отмечены середины отрезков, а пунктирными – вычисляемые значения критерия оптимальности слева и справа на ε /2 от середин.

Рис. 2. Иллюстрация метода половинного деления: 1 – интервал, включающий в себя искомый максимум функции после первого этапа (первого деления пополам); 2, 3 – то же соответственно после второго и третьего этапов

Существует и другой вари­ант алгоритма, заключающийся в следующем. После нахожде­ния середины отрезка (например, точка с 1) в одной из половинок (допустим, в левой) находят среднюю точку (точка с 2 и, сравнивая значения функции в этих точках, определяют, в какой из половинок находится экстремум. Если R (с 1)< R (с 2), то в качестве следующего отрезка выбираем отрезок [а, с 1 ], если же R (с 1)> R (с 2), то берут новую точку в середине правой половины (точка с 3) и в ней вычисляют функцию. В зависимости от сравнения зна­чений функции в точках с 3 и с 1 выбирают новый отрезок [с 1 , b ] или [с 2 , с 3 ] и т.д.

Второй вариант метода не имеет с точки зрения эффективности принципиального отличия от первого, так как эффективность принято оценивать по наихудшему варианту (т.е. по двум вычислениям R (x ) на каждом шаге). В первом варианте метода есть одна особенность, которая его делает очень эффективным при экспериментальном отыскании экстремума (например, при автоматической настройке технических систем или при практическом поиске наилучших условий деятельности экономического объекта). Малые отклонения от текущей точки обеспечивают в процессе поиска отсутствие "шараханий", сопровождающихся резкими отклонениями состояния системы.

Алгоритм метода дихотомии для минимизации функции.

Начальный этап. Выбрать константу различимости 2ε > 0 и допустимую конечную длину интервала неопределённости l > 0. Пусть [а 1 , b 1 ] – начальный интервал неопределённости. Положить k = 1 и перейти к основному этапу.

Основной этап.

Шаг 1. Если b ­ k – a k < l , то остановиться; точка минимума принадлежит интервалу [а k , b k ]. В противном случае вычислить
и
и перейти к шагу 2.

Шаг 2. Если R(p k ) < R(q k ), положить a k +1 = a k и b k +1 = q k . В противном случае положить a k +1 = p k и b k +1 = b k . Заменить k на k + 1 и перейти к шагу 1.

Пример.

Дана функция R (x ) = D sin(Ах B + С), где коэффициенты имеют следующие значения: А = 1,0, В = 1,0, С = 1,0, D = 1,0. Найти максимум на интервале: [-1, 2]. Ошибка задается по х: ε =0,05.

Результаты расчетов. Середина отрезка x 0 = 0,5000, значение критерия R 0 = 0,9975, значение R (0,5 – ε /2) = R (0,475) = 0,97922273, значение R (0,5 + ε /2) = R (0,525) = 0,9989513. Следо­вательно, искомый максимум лежит в правой половине отрезка, т.е. теперь отрезком является .

x 1 = 1,25000000 R 1 = 0,77807320 левый

х 2 = 0,87500000 R 2 = 0,95408578 левый

x 3 = 0,68750000 R 3 = 0,99319785 левый

x 4 = 0,59375000 R 4 = 0,99973658 левый

x 5 = 0,54687500 R 5 = 0,99971390

|х 4 – x 5 | < ε , поэтому в качестве решения можно принять лю­бое из этих значений или середину между ними.

Всего восемь раз (4·2 = 8) вычислялся критерий оптимально­сти (не считая вычислений непосредственно в середине отрезка, которые не используются в алгоритме метода).

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

Пусть на отрезке имеется только один корень уравнения (1). Найдем середину отрезка . Если f (с) = 0 , то корень найден. В противном случае из двух отрезков и выбираем тот, в котором содержится корень.

Как только |b n - a n | < E, где Е - заданная точность, то в качестве приближённого значения корня можно взять середину этого отрезка: .

· Метод хорд.

Пусть на отрезке имеется единственный корень, т.е. f(a) · f(b) < 0;
f " (x) сохраняет свой знак на ;
f "" (x) сохраняет свой знак на .

Заменим дугу кривой y = f (x) на отрезке хордой, проходящей через точки (a; f (a)) и(b; f (b)) . Абсцисса точки пересечения хорды с осью Ох есть приближение к корню уравнения (1). Обозначим её через x 1 .

Если f " (x) · f "" (x) >

Если f " (x) · f "" (x) < 0 для любого x , то для вычисления х 1 , х 2 , ... , х i , ... используются следующие формулы:

или

Заканчиваем процесс уточнения корня, когда расстояние между очередными приближениями х n и x n-1 станет меньше заданной погрешности E: |х n - x n-1 | < E или когда значение функции |f (x n) | < E.

· Метод касательных (метод Ньютона)

Пусть на отрезке :

1. Уравнение f (x) = 0 имеет единственный корень, т.е. f (a) · f (b) < 0;

2. f " (х) и f "" (х) сохраняют свои знаки.

В результате получим последовательность приближённых значений {x n }, монотонно сходящуюся к точному значению корня с.
При этом корень уравнения f (x) = 0 находится между x i и одним из концов промежутка в зависимости от свойств функции y = f (x) .

Если f " (x) · f "" (x) > 0 для любого x , то для вычисления х 1 , х 2 , ... , х i , ... используются следующие формулы:

Если f " (x) · f "" (x) < 0 для любого x , то для вычисления х 1 , х 2 , ... , х i , ... используются следующие формулы:

Процесс уточнения корня заканчивается, когда выполняется условие |х n - x n-1 | < E, где E - допустимая погрешность вычисления или когда |f (x n) | < E.

· Комбинированный метод хорд и касательных

Соединяя метод хорд с методом касательных, получаем метод, на каждом шаге которого находим приближённые значения корня с по недостатку и по избытку: x n < c < , причем каждое значение x n и стремится к с.

Если f " (x) · f "" (x) < 0 для любого x , то для вычисления значений по недостатку и по избытку используются следующие формулы:

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

Метод дихотомии необходимо отличать от обычного деления. Например, слово "человек" может быть разделено на понятия "мужчины" и "женщины", а может делиться на "мужчины" и "не мужчины". Так вот, в первом случае два понятия не противоречат друг другу, поэтому здесь дихотомия отсутствует. Во втором случае "мужчина" и "не мужчина" - два определения, противоречащие друг другу и не пересекающиеся, а это и является определением дихотомии.

Метод дихотомии привлекателен свой простотой, так как здесь всегда присутствует только два класса, которые исчерпываются объемом делимого понятия. Иными словами, в дихотомическом делении всегда присутствует соразмерность. Следующим основным свойством является исключение друг друга членами деления в связи с тем, что каждое делимое множество может попасть только в один из классов "b" или "не b", а деление осуществляется только по одному основанию, связанному с наличием или отсутствием определенного признака.

При всех своих достоинствах метод дихотомии имеет и недостаток, заключающийся в неопределенности той его части, которая имеет частицу "не". Например, если всех ученых разделить на математиков и не математиков, то относительно второй группы присутствует определенная неясность. Кроме этого недостатка, существует еще один, заключающийся в затруднительном установлении понятия, противоречащего первому значению, по степени удаления от первой пары.

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

Довольно часто используется неосознанно метод дихотомии, алгоритм которого может быть описан буквально пошагово. Например, в игре «Угадай число» один из игроков загадывает число в диапазоне от 1 до 100, а другой делает попытки его отгадать на основе подсказок "меньше" или "больше" первого. Если размышлять логически, в качестве первого числа всегда называется 50, а в случае загаданного меньшего - 25, большего - 75. Поэтому на каждом этапе неопределенность загаданного числа уменьшается вдвое, и даже невезучий человек отгадает это неизвестное приблизительно за 7 попыток.

При использовании метода дихотомии в решении различных уравнений нахождение правильного решения возможно лишь тогда, когда достоверно известно нахождение единственного корня на заданном интервале. Это совсем не означает, что применение данного метода возможно для нахождения корней только При решении уравнений более высокого порядка с использованием метода половинного деления нужно в первую очередь разделить корни по отрезкам. При этом процесс их отделения осуществляется с помощью нахождения первой и второй производных от функции и приравнивания полученных уравнений к нулю (f"(x)=0, f""(x)=0). Следующим этапом является определение значений f(x) в граничных и критических точках. Результатом всех проведенных расчетов является интервал |a,b|, на котором у значения функции меняется знак и где f(a)*f(b)< 0.

При рассмотрении графического метода решения уравнения с использованием дихотомии алгоритм решения довольно прост. Например, существует отрезок |a,b|, в пределах которого находится один корень х.

Первым этапом является вычисление среднего алгебраического x=(a+b)/2. далее рассчитывается значение функции в данной точке. Если f(x)< 0, то , в противном случае - . Таким образом, осуществляется сужение интервала, в результате которого формируется определенная последовательность х. Расчет прекращается при достижении разности b-a меньшей погрешности.

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

Дихотомия применяется, когда требуется надежность счета, а скорость сходимости не имеет значения.

х n х cр2 х * х cр1 х n+1 Х

Рисунок 5.2 – Геометрическая интерпретация метода дихотомии

Пусть дано уравнение f(x)=0 и отделен простой корень х * , то есть найден такой отрезок [х n , х n +1 ], х * принадлежит [х n , х n +1 ] и на концах интервала функция имеет значения, противоположные по знаку. Отрезок

[х n , х n +1 ] называется начальным интервалом неопределенности,потому что известно, что корень ему принадлежит, но его местоположение с требуемой точностью не определено.

Алгоритм метода дихотомии.

1. Вычисляют значения функции через равные интервалы значений х до смены знака, при переходе от f(x n) к f(x n +1)

2. Вычисляют среднее значение аргумента x ср и находят f(x ср).

3. Если знак f(x ср) совпадает со знаком f(x n), то в дальнейших расчетах вместо x n используют x cp . Если f(x cp) совпадает с f(x n+1), то вместо x n+1 берут x cp .

4. Интервал, в котором заключено значение корня, сужается. Если f(x cp k) ≤ 0 + ε, где ε положительное наперед заданное достаточное малое число – точность расчета, то процесс заканчивается за k итераций, при этом ширина интервала уменьшается в 2 k раз. Если f(x cp k) >

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

Метод не применим к корням четной кратности, т.е. тогда когда, f(x)=g(x)(x-x 1) m , где x 1 корень кратности m.

Метод хорд

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

x 1 * x 2 * x 3 * x 4 * x *

Рисунок 5.3 – Геометрическая интерпретация метода хорд

Алгоритм метода хорд.

1. Вычисляют значения функции через равные интервалы значений х до смены знака при переходе от f (x n) к f (x n +1).

х * = x n – f (x n)(x n +1 - x n)/ (f (x n +1) – f (x n)) (5.1)

3. Находят значение f (x k *), которое сравнивают с известными f (x n),

f (x n +1). Если знак f(x к *) совпадает со знаком f(x n), то в дальнейших расчетах вместо x n используют x k * . Если f(x k *) совпадает с f(x n+1), то вместо x n+1 берут x k * .

4. Проверяют близость f(x k *) к нулю c заданной точностью ε. Если f(x k *) ≤ 0 + ε, то процесс заканчивается за k итераций. Если f(x k *) > 0 + ε, повторяют пп.2-3 алгоритма.

В знаменателе формулы (5.1) стоит разность значений функций. Вдали от корня она несущественна, но вблизи корня эти значения близки и малы. Возникает потеря значащих цифр, приводящая к «разболтке» счета. Это ограничивает точность, с которой можно найти корень. Для простых корней это ограничение невелико, а для кратных – существенно. Можно использовать метод Гарвика. Выбирают не очень малое ε, ведут итерации до выполнения условия |x n +1 - x n | < ε и затем продолжают расчет до тех пор, пока |x n +1 - x n | убавает.

Метод Ньютона

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

Функция f(x), дважды дифференцируемая на отрезке , который содержит корень х * . При этом f(x *)=0. Для определения интервала, в котором заключен корень, в методе Ньютона не требуется находить значения функции с противоположными знаками. Вместо интерполяции по двум значениям функции будем проводить экстраполяцию с помощью касательной в данной точке.

М 0

Рисунок 5.4 – Геометрическая интерпретация метода Ньютона

Алгоритм метода:

1. Находят значение x n+1 , которое соответствует точке, в которой касательная к кривой в точке x n пересекает ось х

x n+1 = x n - f(x n)/f ′(x n) (5.2)

2. Процедуру повторяют до выполнения условия близости функции к нулю с заданной точностью f(x n) ≈ ε

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

Метод секущих

Одним из недостатков метода Ньютона является необходимость дифференцирования заданной функции f(x). Если нахождение производной затруднено, можно воспользоваться некоторым приближением, которое положено в основу метода секущих. Заменим производную f ′(x n) для расчета

x n+1 = x n - f(x n)/f ′(x n) разностью последовательных значений функции, отнесенных к разности последовательных значений аргумента, т.е. разделенной разностью первого порядка

F*(x n)= (f(x n)- f(x n-1))/(x n - x n-1),

x n+1 = x n - f(x n)/ F*(x n). (5.3)

Схема алгоритма остается, как и в методе Ньютона, изменяется только вид итерационной формулы (5.3).

5.6 Метод простой итерации (последовательных приближений)

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

х = g(х). Задаются начальным значением х 0 , а последующие приближения вычисляются с помощью итерационной процедуры

x n+1 = g(х n). (5.4)

Для сходимости метода необходимо выполнение условия

0< g′ (х n)<1

x

Метод дихотомии имеет свое название от древнегреческого слова, что в переводе означает деление надвое. Именно поэтому данные метод имеет еще второе название: метод половинного деления. Его мы используем довольно часто. Допустим, играя в игру "Угадай число", где один игрок загадывает число от 1 до 100, а другой пытается его отгадать, руководствуясь подсказками "больше" или "меньше". Логично предположить, что первым числом будет названо 50, а вторым в случае если оно меньше - 25, если больше - 75. Таким образом, на каждом этапе (иттерации) неопределенность неизвестного уменьшается в 2 раза. Т.е. даже самый невезучий в мире человек отгадает загаданное число в данном диапазоне за 7 предположений вместо 100 случайных утверждений.

Метод половинного деления в решении уравнения

Правильное решение уравнения методом половинного деления возможно лишь в том случае, если известно, что на заданном интервале имеется корень и он является единственным. Это совсем не означает что метод дихотомии может использоваться только для решения линейных уравнений. Для нахождения корней уравнений более высокого порядка методом половинного деления необходимо сначала отделить корни по отрезкам. Процесс отделения корней осуществляется путем отыскания первой и второй производной от функции и приравнивании их нулю f"(x)=0 и f""(x)=0. Далее определяются знаки f(x) в критических и граничных точках. Интервал, где функция меняет знак |a,b|, где f(a)*f(b)< 0.

Алгоритм метода дихотомии

Алгоритм метода дихотомии очень прост. Рассмотрим отрезок |a,b| в пределах которого имеется один корень x 1

На первой этапе вычисляется x 0 =(a+b)/2

Далее определеяется значение функции в этой точке: если f(x 0)< 0, то , если наоборот, то ,т.е происходит сужение интервала. Таким образом в результате формируется последовательность x i , где i - номер иттерации.

Вычисления прекращаются, когда разность b-a меньше требуемой погрешности.

В качестве примера использования метода половинного деления найдем корень на интервале уравнения x 3 -3*x+1=0 с точностью в 10 -3

Как видно из таблицы корнем является 0,347. Колличество иттераций равно 10. Условие завершения: a-b=0,0009< 10 -3

Метод половинного деления или метод дихотомии является наиболее простым для решения уравнения в численных методах.

Скачать:

Решение уравнения методом дихотомии - Решение уравнения методом половинного деления в Паскале.