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

ЗАДАНИЕ

на курсовую работу студента

Матушкина Михаила Николаевича

Группа ПЗ 197

 

 

1 Дисциплина (специализация) «Вычислительная математика»

2 Тема работы: Выполнить минимизацию целевой функции методом дихотомииF(x)= .

3 Срок сдачи студентом законченной работы ___________________2018г.

4 Пояснительная записка должна содержать.:

1) Анализ численных методов одномерной оптимизации.

2) Математическое описание заданного метода

3) Подробный ход решения

 

 

Руководитель проекта_____________________________/Чернецкий В.О.

 

Студент _____________________________/Матушкин М.Н.

 

АННОТАЦИЯ

Матушкин М.Н. Курсовой проект по предмету «Вычислительная математика» - Челябинск: ЮУрГУ; 2018, 15стр., библиографический список наименований.

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

 

ОГЛАВЛЕНИЕ

Оглавление

ВВЕДЕНИЕ.. 6

1. Анализ численных методов одномерной оптимизации. 7

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

1.2 Метод хорд. 7

1.4 Метод золотого сечения. 8

1.5 Метод Ньютона. 8

2.Математическое описание заданного метода. 9

3.Подробный ход решения. 10

ЗАКЛЮЧЕНИЕ.. 13

БИБЛИОГРАФИЧЕСКИЙ СПИСОК.. 14

 

 

 

ВВЕДЕНИЕ

 

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

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

Метод дихотомии(метод половинного сечения) — метод является методом прямого поиска. В нем при поиске экстремума целевой функции используются только вычисленные значения целевой функции.

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

Анализ численных методов одномерной оптимизации.

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

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

Достоинства.

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

1. Один из простых способов поиска корней функции одного аргумента.

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

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

Метод хорд

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

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

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