Численные методы поиска минимума функции одной переменной.
Определения. Функция f (x) имеет локальный минимум при некотором Точка, в которой функция достигает наименьшего на множестве X значения, называется абсолютным минимумом функции. Для нахождения абсолютного минимума требуется найти все локальные минимумы и выбрать наименьшее значение. Задачу называют детерминированной, если погрешностью вычисления (или экспериментального определения) функции f (x) можно пренебречь. В противном случае задачу называют стохастической. Все изложенные далее методы применимы только к детерминированным задачам. Методы поиска минимума по нахождению корней уравнений. Если функция f (x) аналитически дифференцируема, то решаем f /(x) = 0 методами, изложенными в предыдущих главах. При этом условие f //(x) > 0 в найденной точке указывает нам на минимум. Для использования этих методов необходимо знать либо аналитический вид первой и второй производных, либо рассчитать их численно, если это не приведет к потере точности. Метод дробления.
| x k+1 – x k| ≤ ξ. (1)
Данный метод является одним из самых медленных для поиска минимума. Основное достоинство данного алгоритма – возможность использования в программах управления экспериментальными исследованиями, когда значения функции f(x) последовательно измеряются с шагом h ≥ h min. Метод золотого сечения. Пусть f (x) задана и кусочно-непрерывна на [ xL, xR ], и имеет на этом отрезке только один локальный минимум. Золотое сечение, о котором упоминал ещё Евклид, состоит в разбиении интервала [ xL, xR ] точкой x 1 на две части таким образом, что отношение длины всего отрезка к его большей части равно отношению большей части к меньшей:
Таким образом, возьмем на отрезке две точки x 1и x 2, симметрично относительно границ делящие исходный отрезок в отношении золотого сечения:
где коэффициент Если f (x 1) < f (x 2), мы должны сузить отрезок справа, т.е. новое значение x R = x 2, в противном случае x L = x 1. Оставшаяся внутри нового отрезка точка является первым приближением к минимуму и делит этот отрезок в отношении золотого сечения. Таким образом, на каждой итерации приближения к минимуму (см. рисунок) нам нужно ставить только одну точку (x 1 или x 2), в которой считать значение функции и сравнивать его с предыдущим. Условием выхода из итерационного процесса будет, подобно предыдущему случаю, условие | x 2 – x 1| ≤ ξ. Метод отличается высокой скоростью сходимости, обычно изысканной компактностью программной реализации и всегда находит точку, минимальную на заданном интервале. Метод парабол. Пусть f (x) имеет первую и вторую производную. Разложим f (x) в ряд Тейлора в некоторой точке x k, ограничиваясь при этом тремя членами разложения:
Обычно в практических реализациях данного метода не используют аналитический вид первой и второй производных f (x). Их заменяют конечно-разностными аппроксимациями. Наиболее часто берут симметричные разности с постоянным шагом h:
Это эквивалентно аппроксимации функции параболой, проходящей через три близкие точки x k+ h, x k, x k– h. Окончательное выражение, по которому можно строить итерационный процесс, таково:
Данный метод отличается от вышеизложенных высокой скоростью сходимости. Вблизи экстремума, вплоть до расстояний ~ h 2, сходимость практически не отличается от квадратичной. Однако алгоритм требует постоянного контроля сходимости. Например, итерационный процесс будет сходиться к минимуму, если 1) знаменатель формулы (4) должен быть >0. Если это не так, нужно сделать шаг в обратном направлении, причем достаточно большой. Обычно в итерационном процессе полагают 2)
Воспользуйтесь поиском по сайту: ![]() ©2015 - 2025 megalektsii.ru Все авторские права принадлежат авторам лекционных материалов. Обратная связь с нами...
|