5.2.5. Минимизация функций

В пакете Mathcad есть функции Minimize, Maximize, Minerr. Если необходимо решать задачу с ограничениями (типа равенств или нера-венств), то последние записываются в блоке Given ... . Функция Minerr минимизирует среднеквадратичную разницу левой и правой части уравнения по выбранным параметрам (специальная минимиза- ция, см. начало главы). "Кухня" процессов минимизации непроста, по-знакомимся лишь с некоторыми простейшими (с точки зрения прог-раммирования) ее аспектами.

5.2.5.1. Функции одной переменной

Если производная функции неизвестна (или не интересует), то стартуя из заданной точки с выбранным шагом, можно всегда двигать-ся в сторону убывания функции (для задач на минимум), считая такое движение "удачным". Для ускорения поиска можно увеличивать шаг при удачном движении и уменьшать шаг, меняя его направление, при неудачном движении до тех пор, пока шаг не станет достаточно ма-лым. Опыт и здравый смысл показывает, что увеличивать шаг следует осторожно, например, заменяя h на 1.2h, уменьшать же шаг следует решительнее, например, заменяя h на - 0.2h. Приведем пример соот-

ветствующей программы-функции:

Min1(f, x, h, ) fx ← f(x), n ← 0

while | h | > 0.2  

a ← x, x ← x + h, n ← n + 1

fa ← fx, fx ← f(x)

h ← if (fx < fa, 1.2  h, - 0.2  h)

Пример 1. Для функции f(x) = , начиная с точки х = 5 с шагом h = 1 и  = 10 ^{– 5}, получим х = - 0.99999, f′(x) = 7.0097  10 ^{- 6} за 70 вычислений функции (встроенная функция minimize возвращает точное значение х = 1).

Если известны значения производной функции f′(x) = g(x), то задача сводится к решению уравнения g(x) = 0 и можно использовать любой оговоренный выше метод. Можно, однако, найти "удачную" пару точек х1, х2: f′(x1)f(x2) < 0, построить в них касательные к гра-фику y = f(x): Y = f(x1) + g(x1)(X - x1) и Y = f(x2) + g(x2)(X - x2) и точку их пересечения x^* = можно ввести в число "удачных", если x^*  [x1, x2]. Процесс заканчивается, когда изменение g(x) на удачной паре точек станет меньше оговоренного уровня. Приведем пример программ, реализующих поиск минимума f(x) через решение уравнения g(x) = 0 (Min2) и использующих пере-сечение касательных (Min3).

Min2(g, x, h, ) n ← 1, gx ← g(x), h ← - |h|  sign(gx)

while |h| > 0.1  

a ← x, ga ← gx, x ← x + h

gx ← g(x), n ← n + 1

h ← if(gx  ga > 0, 1.2  h, - 0.2  h)

Min3(f, g, x, h, ) n ← 1, x2 ← x, g2 ← g(x)

g1 ← g2, h ← - |h|  sign(g2)

while g1  g2 > 0

x1 ← x2, g1 ← g2, h ← 1.2  h

x2 ← x2 + h, g2 ← g(x2), n ← n + 1

y1 ← f(x1), y2 ← f(x2), n ← n + 2

while |g1 - g2) > 0.1  

x ←

x ← 0.5  (x1 + x2) if (x2 - x)  (x - x1)  0

gx ← g(x), n ← n + 2

if g1  g2 > 0

x1 ← x, g1 ← gx, y1 ← f(x)

otherwise

x2 ← x, g2 ← gx, y2 ← f(x)

В условиях предыдущего примера получаем:

f(x) g(x) x 5 h 1  10 ^{- 5}

Min2(g, x, h, ) = Min3(f, g, x, h, ) =

Если требуется искать минимум на ограниченном множестве, то следует доопределить функцию (и ее производную) вне этого множес-тва. Пусть, например, необходимо найти минимум f(x) = arcsin на промежутке [2 + , 5]. Определим функцию (х) на всей число-вой прямой равенством

(х) if ,

аналогично доопределим "производную"

d(x) - 10 ¹⁰ if x < 2 +

10 ¹⁰ if x > 5

(x) otherwise

Тогда при стартовых условиях: x = 3, h = 1,  = 0.00001 программа Min1 выдает в качестве точки минимума х = 5.0807 за 15 шагов, Min2 х = 5.000000 за 10 шагов, Min3 с задачей не справилась (по-

скольку "исправленная" функция  негладкая).