Методы поиска минимума одномерных функций
Методика проведения оптимизации заданного выражения. Нахождение числа, при котором функция принимает оптимальное значение. Аналитический способ нахождения локального минимума. Методы одномерного поиска. Одномерная оптимизация с использованием производных.
| Рубрика | Математика |
| Вид | реферат |
| Язык | русский |
| Дата добавления | 21.11.2013 |
| Размер файла | 143,5 K |
Отправить свою хорошую работу в базу знаний просто. Используйте форму, расположенную ниже
Студенты, аспиранты, молодые ученые, использующие базу знаний в своей учебе и работе, будут вам очень благодарны.
Размещено на http://www.allbest.ru
Методы поиска минимума одномерных функций
Постановка: требуется оптимизировать х (формальная постановка)
минимум функция одномерная производная
- функция одной переменной
- целевая функция.
Решение: найти х, при котором принимает оптимальное значение.
2 варианта:
минимизировать - задача минимизации;
максимизировать - задача максимизации.
Рассмотрим случай минимизации
2 способа:
аналитический
численный
В аналитическом задается в виде формулы, в численном задается в виде черного ящика, на входе подается х, на выходе значение целевой функции в этой точке.
Пусть функция определена в некоторой области S (), в случае одномерной оптимизации S - интервал :
точка называется глобальным минимумом, если для
точка называется строгим глобальным минимумом, если для
точка называется локальным минимумом, если для
точка называется строгим локальным минимумом, если для
Следствие: любая точка глобального минимума является локальным минимумом, обратное не верно.
Аналитический способ нахождения локального минимума
- дифференцируема
- необходимое условие точки локального минимума.
Численные методы
Пусть функция задана на интервале , при этом существует такая точка , что на - монотонно убывает, а на - монотонно возрастает, то функция унимодальная.
а b
Если из того что следует, что , то функция называется монотонно возрастающей. Если из того что следует, что , то функция называется монотонно убывающей.
Методы одномерного поиска
Разобьем и вычислим значение функции в каждой точке.
искомый минимум
В результате остается интервал меньшего размера, к которому применяется тот же метод, и находим еще один интервал, в конце находим интервал с заведомо нужной точкой.
Интервал неопределенности - интервал, в котором заведомо находится точка минимума. Наиболее эффективное разбиение - двумя точками на 3 равных отрезка.
1)
2)
- после выполнения n шагов сокращение исходного интервала
- точность с которой надо найти решение задачи.
N=2n, где n - число шагов, N - число вычислений (мера эффективности данного решения).
Метод золотого сечения
Точки должны быть расположены на равном расстоянии.
а b
; ; ;
; - золотое сечение.
сокращения на каждом шаге
число итераций растет как логарифм функции.
Одномерная оптимизация с использованием производных
. Пусть целевая функция дифференцируема .
|
точка локального минимума |
точка локального максимума |
точка перегиба |
Методы для нахождения корня уравнения функции 1-ой переменной
Деление пополам:
Имеется хотя бы 1 корень. Выбираем любую точку и смотрим какой знак она имеет, такой знак нам и искать. Выбираем точку приблизительно в середине интервала, исследуя значения в 3-х можно отбросить половину интервала.
+
а b
ГРАДИЕНТНЫЕ МЕТОДЫ
Метод Коши
В методе Коши или методе наискорейшего спуска в качестве направления поиска выбирается направление антиградиента.
,
f = - градиент функции f(x)
Алгоритм метода выглядит следующим образом:
x(k + 1) = x(k) - (k)f(x(k)), где f (x) - градиент.
Значение (k) на каждой итерации вычисляется путем решения задачи одномерного поиска экстремума f(x) вдоль направления градиента f(x(k)). Если в качестве (k) взять некоторое положительное число, то получится простейший градиентный алгоритм:
f(k + 1) = x(k) - f(x(k))
Одно из главных достоинств метода Коши является его устойчивость, так как всегда выполняется условие
f(x(k + 1)) f(x(k))
Однако вблизи экстремума скорость сходимости алгоритма становится недопустимо низкой, так как вблизи экстремума значение градиента стремится к нулю.
Метод Ньютона (метод касательной)
В случае если известна производная, то выбираем - начальное приближение.
Допустим, что точка достаточно близка к корню функции и примерно себя ведет линейно не отклоняется. Проведем касательную и находим точку ближе чем , и повторяем до .
Для метода Ньютона необходимо:
функция должна иметь производную;
точка должна быть взята близко к корню;
функция изменяется близко к линейной функции.
;
- уравнение касательной;
.
Если , то вычисления можно прекратить и считать что нужный нам корень - условие прекращения поиска. (Е - значение корня с некоторой точностью).
В методе Ньютона каждая его итерация удваивает количество значащих цифр. Если все условия выполнены, то эти методы удваивают (ускоряют) количество значащих цифр:
;
Представим что линейная функция, то метод Ньютона позволяет найти ее корень за 1-у итерацию. Целевая функция представляет собой квадратичную зависимость следовательно метод Ньютона позволяет найти минимум или максимум квадратичной функции за 1-у итерацию.
Замена функции на касательную, называется - линейная аппроксимация, и ее применение к целевой функции парабола в точке приближения.
Замена заданной зависимости квадратичной зависимостью, называется - квадратичной аппроксимацией. Метод Ньютона основан на замене заданной зависимости более простой зависимостью.
Методы прямого поиска.
Должны задать начальное приближение точки х0;
- некоторое приближение полученное после к - итераций;
вычислить значение точки в окрестности точки ;
Из данных точек выбрать точку в которой функция принимает наименьшее значение, выбираем ее и строим вокруг нее окрестность.
Выбираем точку где хуже. В окрестности существующей точки выбираем точку с меньшим значением, опять в ее окрестности есть точки с меньшим значением и т.д.
Метод координатного спуска.
Существует приближенная точка минимума. Минимизируя функцию по направлению к х1, на прямой используется любой метод одномерной минимизируют, х2 - фиксируют. Далее выполняют одномерную оптимизацию по х2, фиксируя х1.
Этот процесс повторяют до тех пор пока следующая точка не окажется близка к точке приближения.
Размещено на Allbest.ru
...Подобные документы
Изучение методов одномерной оптимизации и сравнение эффективности их применения для конкретных целевых функций. Нахождение минимума функции 1/|x-3|3 методами перебора, поразрядного поиска, дихотомии, золотого сечения, средней точки, хорд и Ньютона.
курсовая работа [761,8 K], добавлен 25.12.2015Методы нахождения минимума функций градиентным методом наискорейшего спуска. Моделирование метода и нахождение минимума функции двух переменных с помощью ЭВМ. Алгоритм программы, отражение в ней этапов метода на языке программирования Borland Delphi 7.
лабораторная работа [533,9 K], добавлен 26.04.2014Методы нахождения минимума функции одной переменной и функции многих переменных. Разработка программного обеспечения вычисления локального минимума функции Химмельблау методом покоординатного спуска. Поиск минимума функции методом золотого сечения.
курсовая работа [95,1 K], добавлен 12.10.2009Численные методы поиска безусловного экстремума. Задачи безусловной минимизации. Расчет минимума функции методом покоординатного спуска. Решение задач линейного программирования графическим и симплексным методом. Работа с программой MathCAD.
курсовая работа [517,9 K], добавлен 30.04.2011Поиск оптимальных значений некоторых параметров в процессе решения задачи оптимизации. Сравнение двух альтернативных решений с помощью целевой функции. Теорема Вейерштрасса. Численные методы поиска экстремальных значений функций. Погрешность решения.
презентация [80,6 K], добавлен 18.04.2013Развитие численных линейных методов решения задач линейного программирования. Знакомство с методами поиска целевой функции: равномерный симплекс, методы Коши, Ньютона, сопряжённого градиенты, квазиньютоновский метод. Алгоритмы нахождения экстремума.
курсовая работа [716,1 K], добавлен 12.07.2012Рассмотрение эффективности применения методов штрафов, безусловной оптимизации, сопряженных направлений и наискорейшего градиентного спуска для решения задачи поиска экстремума (максимума) функции нескольких переменных при наличии ограничения равенства.
контрольная работа [1,4 M], добавлен 16.08.2010Условия существования предела в точке. Расчет производных функции, заданной параметрически. Нахождение точки экстремума, промежутков возрастания и убывания функций, выпуклости вверх и вниз. Уравнение наклонной асимптоты. Точка локального максимума.
курсовая работа [836,0 K], добавлен 09.12.2013Математическое программирование - область математики, в которой изучаются методы решения задач условной оптимизации. Основные понятия и определения в задачах оптимизации. Динамическое программирование – математический метод поиска оптимального управления.
презентация [112,6 K], добавлен 23.06.2013Методы условной и безусловной нелинейной оптимизации. Исследование функции на безусловный экстремум. Численные методы минимизации функции. Минимизация со смешанными ограничениями. Седловые точки функции Лагранжа. Использование пакетов MS Excel и Matlab.
лабораторная работа [600,0 K], добавлен 06.07.2009Нахождение экстремума функции нескольких переменных не на всей области определения, а на множестве, удовлетворяющему некоторому условию. Практический пример нахождения точки максимума и минимума функции. Главные особенности метода множителей Лагранжа.
презентация [112,6 K], добавлен 17.09.2013Нахождение производных функций, построение графика функции с помощью методов дифференциального исчисления, нахождение точки пересечения с осями координат. Исследование функции на возрастание и убывание, нахождение интегралов, установка их расходимости.
контрольная работа [130,5 K], добавлен 09.04.2010Определение допустимого решения задачи линейного программирования методом введения искусственного базиса. Целочисленное линейное программирование с булевскими переменными. Поиск минимума функции методом градиентного спуска. Одномерная минимизация.
курсовая работа [281,7 K], добавлен 27.05.2013Изучение способов нахождения пределов функций и их производных. Правило дифференцирования сложных функций. Исследование поведения функции на концах заданных промежутков. Вычисление площади фигуры при помощи интегралов. Решение дифференциальных уравнений.
контрольная работа [75,6 K], добавлен 23.10.2010Сущность сопряженных направлений, знакомство с основными алгоритмами. Особенности поиска минимума функции методом Пауэлла. Разработка приложений с графическим интерфейсом. Исследование квадратичных функций, решение задач методом сопряженных направлений.
курсовая работа [2,8 M], добавлен 14.07.2012Общие свойства функций. Правила дифференциального исчисления. Неопределенный и определенный интегралы, методы их вычисления. Функции нескольких переменных, производные и дифференциалы. Классические методы оптимизации. Модель потребительского выбора.
методичка [2,0 M], добавлен 07.01.2011Нахождение пределов функций. Определение значения производных данных функций в заданной точке. Проведение исследования функций с указанием области определения и точек разрыва, экстремумов и асимптот. Построение графиков функций по полученным данным.
контрольная работа [157,0 K], добавлен 11.03.2015Обзор таблицы производных элементарных функций. Понятие промежуточного аргумента. Правила дифференцирования сложных функций. Способ изображения траектории точки в виде изменения ее проекций по осям. Дифференцирование параметрически заданной функции.
контрольная работа [238,1 K], добавлен 11.08.2009Правило нахождения производной произведения функций. Формулы нахождения производных для функций, заданных параметрически. Геометрический смысл производной. Приращение и дифференциал функции. Наибольшее и наименьшее значения на замкнутом множестве.
контрольная работа [75,5 K], добавлен 07.09.2010Математическая задача оптимизации. Минимум функции одной и многих переменных. Унимодальные и выпуклые функции. Прямые методы безусловной оптимизации и минимизации, их практическое применение. Методы деления отрезка пополам (дихотомия) и золотого сечения.
курсовая работа [2,0 M], добавлен 26.08.2009
