q(x) = ao + a1(x - x1) + a2(x - x1)(x - x2) (1.25)
совпадут со значением W(x) в трех указанных точках. Вычислим q(x) в трех указанных точках (см. табл.1.1).
Таблица 1.1 - Вычисление значений
1.7.1.1Метод Пауэлла
Если известны значения функции f(x) в трех разных точках ?, ?, ?? равные соответственно f?, f?, f?, то функция f(x) может быть аппроксимирована квадратичной функцией
Ж(x)=Ax2+Bx+C, (1.26)
где А, В и С определяются из уравнений
A±2+B±+C=f±,
AІ2+BІ+C=fІ,
Aі2+Bі+C=fі. (1.27)
После преобразований этих уравнений получаем
A=[(і-І)f±+(±-і)fІ+(І-±)fі]--/--D,
B=[(І2-і2)f±+(і2-±2)fІ+(±2-І2)fі]--/--D,
C=[Іі(і-І)f±+і±(±-і)fІ+±І(І-і)fі]--/--D, (1.28)
где D=(±-І)(І-і)(і-±)
Ясно, что ?(x) будет иметь минимум в точке
x=-B/2A,
если А>0. Следовательно, можно аппроксимировать точку минимума функции f(x) значением
(1.29)
Этот метод может непосредственно применяться к функциям одной переменной. Он может быть очень полезен для выполнения линейного поиска в процедурах, описанных в теме №3. В этих процедурах требуется найти минимум функции f(x) в точках прямой x0+?d, где x0- заданная точка, а d определяет заданное направление. Значение функции f(x0+?d) на этой прямой является значениями функции одной переменной ?:
???? = f(x0+?d). (1.30)
Идеи и результаты, изложенные выше, преобразуются в вычислительные процедуры, описанные далее. Предположим, что заданы унимодальная функция одной переменной f(x), начальная аппроксимация положения минимума и длинна шага D, является величиной того же порядка, что и расстояние от точки А до точки истинного минимума x*(условие, которое не всегда просто удовлетворить). Вычислительная процедура имеет следующие шаги:
Шаг 1. x2 = x1 + D x.
Шаг 2. Вычислить W(x1) и W(x2).
Шаг 3.
если W(x1) > W(x2), то x3 = x1 + 2 D x;
если W(x1)< W(x2), то x3 = x1 - D x;
W(x1) > W(x2),
Шаг 4. Вычислить W(x3) и найти
Wmin = min{ W(x1),W(x2), W(x3)},
Xmin = xi, соответствующая Wmin.
Шаг 5. По x1, x2, x3 вычислить x*, используя формулу для оценивания с помощью квадратической аппроксимации.
Шаг 6. Проверка окончания
если | Wmin - W(x*)| < W, то закончить поиск. В противном случае к шагу 7;
если | Xmin - x*| < x, то закончить поиск. В противном случае к шагу 7.
Шаг 7. Выбрать Xmin или x* и две точки по обе стороны от нее. Обозначить в естественном порядке и перейти к шагу 4.
Заметим, что если точка Е задана слишком малой, то ±,--І,--і,--а также f±, fІ, fі будут очень близко друг к другу и значение--d (1.29) может стать вообще недостижимыми. Чтобы преодолеть эту трудность, перепишем (1.29) для второй и последней интерполяции:
(1.31)
1.7.2 Кубическая интерполяция
Квадратичная интерполяция, которая рассматривалась в предыдущем разделе, называется методом Пауэлла и аппроксимирует функцию квадратным трехчленом. В этом разделе рассматривается метод Давидона [6,7], который гарантирует большую точность и аппроксимирует функцию кубическим полиномом.
Для кубической интерполяции в этом методе используются значения функции и ее производной, вычисленных в двух точках.
Рассмотрим задачу минимизации функции f(x) на прямой x0 + hd , то есть минимизацию функции
(1.32)
Предположим, что известные следующие значения:
(1.33)
Эту информацию можно использовать для построения кубического полинома a+bh+ch2+dh3, который будет аппроксимировать функцию ?(h) Если p=0 , то уравнения, которые определяют a, b, c, d имеют вид :
(1.34)
Следовательно, если r является точкой минимума кубического полинома,
(1.35)
где
Одно из значений этого выражения является минимумом. Друга производная равна 2c +6dh.
Если мы выберем положительный знак, то при
другая производная будет
(1.36)
(1.37)
Выбор точки q зависит от нас. Если Gp >0 , то надо выбрать значение q положительным, то есть сделать шаг в направлении уменьшения функции ??(h) , в другом случае значения q надо выбирать отрицательным. Значение должно быть таким, чтобы интервал (0, ) включал в себя минимум. Это будет верным, если ??q > ? p или Gp >0.
Если ни одно из этих условий не исполняется, то мы удваиваем значения q , повторяя это в случае необходимости, пока указанный интервал не будет содержать в себе минимум.
Давидон, Флетчер и Пауэлл предложили выбирать q следующим путем:
(1.38)
где ?m - оценка самого малого значения истинного минимума ??(h),
h?- константа, значение которой обычно берут 2 или 1.
1.7.3 Квадратичные функции
Квадратичная функция [7,8]
(1.39)
где a - константа;
b - постоянный вектор;
G - положительно определенная симметричная матрица - имеет минимум в точке x* , где x* определяется следующим путем:
(1.40)
откуда
Любую функцию можно аппроксимировать в окрестности точки x0 функцией
(1.41)
где G(x0) - матрица Гессе, вычисленная в точке x0.
Аппроксимацией минимума функции f(x) может быть минимум функции ?(x). Если последний находится в точке xm, то
(1.42)
или
(1.43)
Таким образом точкой xи следующей аппроксимации минимума будет:
(1.44)
(1.45)
где ?и - длина шага, определяется одномерным поиском в направлении G-1(xи)g(xи).
1.8 Метод Нелдера-Мида
Метод Нелдера-Мида (поиск по деформируемому многограннику) является развитием симплексного метода Спендли, Хекста и Химсворта [7,8]. Множество (n+1)-й равноудаленной точки в n-мерном пространстве называется регулярным симплексом. Эта конфигурация рассматривается в методе Спендли, Хекста и Химсворта. Следовательно, в двумерном пространстве симплексом является равносторонний треугольник, а в трехмерном пространстве правильный тетраэдр. Идея метода состоит в сравнении значений функции в (n+1) вершинах симплекса и перемещении в направлении оптимальной точки с помощью итерационной процедуры. В симплексном методе, предложенном первоначально, регулярный симплекс использовался на каждом этапе. Нелдер и Мид предложили несколько модификаций этого метода, допускающих, чтобы симплексы были неправильными. В результате получился очень надежный метод прямого поиска, являющийся одним из самых эффективных, если n<=6.
В методе Спендли, Хекста и Химсворта симплекс перемещается с помощью трех основных операций: отражения, растяжения и сжатия. Смысл этих операций станет понятным при рассмотрении шагов процедуры.
Шаг 1. Найдем значения функции в вершинах симплекса:
f1=f( x1), f2=f(x2) ... fn+1=f(xn+1) (1.46)
Шаг 2. Найдем наибольшее значение функции fh, следующее за наибольшим значением функции fg , наименьшее значение функции fl и соответствующие им точки xh, xg и xl.
Шаг 3. Найдем центр тяжести всех точек, за исключением точки xh. Пусть центром тяжести будет
(1.47)
и вычислим f(x0)=f0.
Шаг 4. Удобнее всего начать перемещение от точки xh. Отразив точку xh относительно точки x0, получим точку xr и найдем f(xr) = fr.
Операция отражения иллюстрируется рис. 1.6.
Рисунок 1.6 - Операция отражения
Если ?>0 - коэффициент отражения, то положение точки xr определяется следующим образом:
xr-x0=? (x0-xh), т.е.
xr=(1+?)x0 -?xh. (1.48)
Замечание.
?= |xr-x0| / |x0 -xh|.
Шаг 5. Сравним значения функций fr и fl.
Если fr<fl, то мы получили наименьшее значение функции. Направление из точки x0 в точку xr наиболее удобно для перемещения. Таким образом, мы производим растяжение в этом направлении и находим точку xe и значение функции fe=f(xe). Рисунок 1.7. иллюстрирует операцию растяжения симплекса. Коэффициент растяжения ?1 можно найти из следующих соотношений: xe-x0=? (xr-x0), т.е.
xe=?xr+ (1-?)x0. (1.49)
Рисунок 1.7 - Операция растяжения
Замечание
??=|xe-x0| / |xr-x0|
Если fe<fl, то заменяем точку xh на точку xe и проверяем (n+1)-ую точку симплекса на сходимость к минимуму (см. шаг 8). Если сходимость достигнута, то процесс останавливается; в противном случае возвращаемся на шаг 2.
Если fe=fl , то отбрасываем точку xe. Очевидно, мы переместились слишком далеко от точки x0 к точке xr. Поэтому следует заменить точку xh на точку xr, в которой было получено улучшение (шаг 5, 1) проверить сходимость и, если она достигнута, вернуться на шаг 2.
Если fr>fl, но fr <=fgто xr является лучшей точкой по сравнению с другими двумя точками симплекса и мы заменяем точку xh на точку xr и, если сходимость не достигнута, возвращаемся на шаг 2, т.е. выполняем пункт 1,б, описанный выше.
Если fr>fl и fr>fgто перейдем на шаг 6.
Страницы: 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14
