VII Международная студенческая научная конференция Студенческий научный форум - 2015
ЛАБОРАТОРНАЯ РАБОТА «МЕТОД ПОЛОВИННОГО ДЕЛЕНИЯ (ДИХОТОМИИ)»
Морарь А.А. 1
1Южно-Российский государственный политехнический университет (НПИ) имени М.И. Платова
Текст работы размещён без изображений и формул.
Полная версия работы доступна во вкладке "Файлы работы" в формате PDF
Полная версия работы доступна во вкладке "Файлы работы" в формате PDF
Цель работы: овладеть практическими навыками численного нахождения локального минимума функции одной переменной на заданном отрезке в среде электронных таблиц Microsoft Excel, пакета Mathcad и среде программирования Pascal-АВС.
Теоретическая часть
Экстремум максимальное или минимальное значение функции на заданном множестве. Точка, в которой достигается экстремум, называется точкой экстремума. Соответственно, если достигается минимум, точка экстремума называется точкой минимума, а если максимум - точкой максимума.
Значение функции в точке максимума называется локальным максимумом, значение функции в точке минимума - локальным минимумом данной функции. Максимум и минимум функции называются её локальными экстремумами.
Термин «локальный экстремум» обусловлен тем, что введённое понятие экстремума связано с окрестностью данной точки в области определения функции, а не со всей этой областью. Функция может иметь несколько экстремумов, причём минимум в одной точке может быть больше максимума в другой.
Определение.
Точка x0 называется точкой локального минимума функции f(x), если существует такая окрестность точки x0, что для всех x из этой окрестности f(x) ≥ f(x0).
Суть нахождение локального минимума методом половинного деления состоит в уменьшении длины отрезка [a ; b] таким образом, что минимум остается всегда внутри отрезка. Процесс продолжается до тех пор, пока длина отрезка не станет меньше заданной точности нахождения экстремума ε. Уменьшение длины отрезка производится выбором двух точек x1 и x2, расположенных симметрично относительно середины отрезка, т.е. точки
x=(a+b)/2
Абсциссы этих точек находятся по формулам:
x_1=x-Δ/2;〖 x〗_2=x+δ/2
где δ - величина различимости точек, при этом δ < ε.
При этом возможны три случая, приводящие к сужению длины отрезка:
f(x1) > f(x2)
В этом случае в промежутке [a ; x1] функция монотонно убывает, значит минимума нет. Поэтому новый уменьшенный отрезок на котором расположен экстремум, это [x1 ; b]. Для получения отрезка [a ; b] меньшей длины переносим точку a в точку x1 , полагая a:= x1
f(x1) < f(x2)
В этом случае в промежутке [x2 ; b] функция возрастает, значит минимума нет. Поэтому новый уменьшенный отрезок на котором расположен экстремум, это [a ; x2]. Для получения отрезка [a ; b] меньшей длины переносим точку a в точку x1 , полагая b:= x2 f(x1) = f(x2)
В этом случае истинный экстремум находится на интервале [x1 ; x2]. В этом случае получаем новый уменьшенный отрезок [a ; b], полагая a:= x1, b:= x2.
Получив новый отрезок [a ; b] меньшей длины повторяем алгоритм заново, до тех пор пока |b - a| ≤ ε. В этом случае выполняя последнее деление пополам полагая x_min ∶=(a+b)/2. После чего находим значение ymin = f(xmin).
Блок-схема алгоритма метода дихотомии имеет вид: Выполнение задания
Найти минимум функции f(x)= -2∙x^3+20∙x^2-25∙x+10 на интервале [-1 ; 2].
Реализация в среде MS Excel
Надстройка «Поиск решения»
Найдем минимум функции с помощью надстройки «Поиск решения».
Для этого создадим таблицу со значениями x и f(x), и по ним построим график функции, а так же построим еще одну таблицу для определения
xmin и fmin, в ячейку для результата минимального значения функции заносим формулу нашей функции.
Набираем команду Данные → Поиск решения. В появившемся диалоговом окне Поиск решения необходимо выполнить необходимые установки, указанные ниже.
Метод половинного деления
Решим данную задачу, используя алгоритм, указанный ранее.
Формулы, в MS Excel для данного способа, представлены на следующей странице.
В итоге имеем следующие результаты вычислений.
Реализация в Pascal-ABC
Паскаль-программа и результаты вычислений имеют вид:
Модернизируем данную программу, так чтобы она подсчитывала количество разбиений, выполняемых для достижения заданной точности. Из полученных данных заполним таблицу для трех разных значений ε.
Таблица количества разбиений в зависимости от точности ε:
№
п/п ε K
1 0.01 9
2 0.0001 15
3 0.00001 19 Как мы видим, с увеличением заданной точности увеличивается количество разбиений, что вполне логично. Реализация в математическом пакете MathCad
Осуществим метод половинного деления в среде MathCad с применением программирования:
Так же, в MathCad можно использовать более простой метод нахождения минимума функции, а именно минимизацию функции с помощью Minimize.
Вывод: в ходе лабораторной работы были изучены различные средства нахождения минимума функции методом половинного деления (дихотомии), который является довольно простым и легко реализуемым.
Теоретическая часть
Экстремум максимальное или минимальное значение функции на заданном множестве. Точка, в которой достигается экстремум, называется точкой экстремума. Соответственно, если достигается минимум, точка экстремума называется точкой минимума, а если максимум - точкой максимума.
Значение функции в точке максимума называется локальным максимумом, значение функции в точке минимума - локальным минимумом данной функции. Максимум и минимум функции называются её локальными экстремумами.
Термин «локальный экстремум» обусловлен тем, что введённое понятие экстремума связано с окрестностью данной точки в области определения функции, а не со всей этой областью. Функция может иметь несколько экстремумов, причём минимум в одной точке может быть больше максимума в другой.
Определение.
Точка x0 называется точкой локального минимума функции f(x), если существует такая окрестность точки x0, что для всех x из этой окрестности f(x) ≥ f(x0).
Суть нахождение локального минимума методом половинного деления состоит в уменьшении длины отрезка [a ; b] таким образом, что минимум остается всегда внутри отрезка. Процесс продолжается до тех пор, пока длина отрезка не станет меньше заданной точности нахождения экстремума ε. Уменьшение длины отрезка производится выбором двух точек x1 и x2, расположенных симметрично относительно середины отрезка, т.е. точки
x=(a+b)/2
Абсциссы этих точек находятся по формулам:
x_1=x-Δ/2;〖 x〗_2=x+δ/2
где δ - величина различимости точек, при этом δ < ε.
При этом возможны три случая, приводящие к сужению длины отрезка:
f(x1) > f(x2)
В этом случае в промежутке [a ; x1] функция монотонно убывает, значит минимума нет. Поэтому новый уменьшенный отрезок на котором расположен экстремум, это [x1 ; b]. Для получения отрезка [a ; b] меньшей длины переносим точку a в точку x1 , полагая a:= x1
f(x1) < f(x2)
В этом случае в промежутке [x2 ; b] функция возрастает, значит минимума нет. Поэтому новый уменьшенный отрезок на котором расположен экстремум, это [a ; x2]. Для получения отрезка [a ; b] меньшей длины переносим точку a в точку x1 , полагая b:= x2 f(x1) = f(x2)
В этом случае истинный экстремум находится на интервале [x1 ; x2]. В этом случае получаем новый уменьшенный отрезок [a ; b], полагая a:= x1, b:= x2.
Получив новый отрезок [a ; b] меньшей длины повторяем алгоритм заново, до тех пор пока |b - a| ≤ ε. В этом случае выполняя последнее деление пополам полагая x_min ∶=(a+b)/2. После чего находим значение ymin = f(xmin).
Блок-схема алгоритма метода дихотомии имеет вид: Выполнение задания
Найти минимум функции f(x)= -2∙x^3+20∙x^2-25∙x+10 на интервале [-1 ; 2].
Реализация в среде MS Excel
Надстройка «Поиск решения»
Найдем минимум функции с помощью надстройки «Поиск решения».
Для этого создадим таблицу со значениями x и f(x), и по ним построим график функции, а так же построим еще одну таблицу для определения
xmin и fmin, в ячейку для результата минимального значения функции заносим формулу нашей функции.
Набираем команду Данные → Поиск решения. В появившемся диалоговом окне Поиск решения необходимо выполнить необходимые установки, указанные ниже.
Метод половинного деления
Решим данную задачу, используя алгоритм, указанный ранее.
Формулы, в MS Excel для данного способа, представлены на следующей странице.
В итоге имеем следующие результаты вычислений.
Реализация в Pascal-ABC
Паскаль-программа и результаты вычислений имеют вид:
Модернизируем данную программу, так чтобы она подсчитывала количество разбиений, выполняемых для достижения заданной точности. Из полученных данных заполним таблицу для трех разных значений ε.
Таблица количества разбиений в зависимости от точности ε:
№
п/п ε K
1 0.01 9
2 0.0001 15
3 0.00001 19 Как мы видим, с увеличением заданной точности увеличивается количество разбиений, что вполне логично. Реализация в математическом пакете MathCad
Осуществим метод половинного деления в среде MathCad с применением программирования:
Так же, в MathCad можно использовать более простой метод нахождения минимума функции, а именно минимизацию функции с помощью Minimize.
Вывод: в ходе лабораторной работы были изучены различные средства нахождения минимума функции методом половинного деления (дихотомии), который является довольно простым и легко реализуемым.
Просмотров работы: 5279