Интервал неопределенности после i итераций /1 + -ф/-фг --фJ

(16 59)

уменьшается по сравнению с интервале уменьшения составляет

I / При этом К0Э(]

После я /1

(16 60)

1 итерации оций коэффициент уменьшения составляет --F. (1661)

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

На последней, т. е. (п - 1)-и итерации, Ф- и Ф- определяют ся как /"-/2 !- Ф)-*. В этом случае становится необходимым вы полнить одно из вычислений значения функции в /"-/2 + Ф~ ± ± й, где й - малое отклонение Конечный интервал неопределенно сти - /"-/2 или /"-/2 + й

Для достижения точности о значение п дочжно быть таким чтобы

Fn 1<(Ф«-Ф;) oF (16 62)

Приведем точный алгоритм процедуры поиска Фибоначчи

Поиск Фибоначчи

«-и-/

.-(id

IJ.-U(a)

i-1 Loop

II V,>hb

j -II t Ihm EXIT

a - b he,

1ф -1ЧЬ)

th n

i п \ !h FXn

, F„--.

a b then d и -6

j J ; 1

j n- n E.\n

и (a) Ub - L (b)

Weuer

Пи(ск золотым сечением. Другой метод размещения внутренних точек прн одномерной минимизации известен как поиск золотым сечением 18,14). Его достоинство состоит ВТОМ, что при эффективности, прн мерно такой же, как при методе Фибоначчи общее число вычислений значений функции п не обязательно фиксировать в начале процесса

И в этом случае интервалы неогределенности на последовательных итерациях связаны друг с другом соотношением (16.52). Кроме того,

этот метод уменьшает интервал неопределенности на каждой итерации в т раз. Таким обазом, т задается формулой

/......IrKL - т. (1663)

Соотношения (16 52) и (16 53) приводят к уравнению

ттч! (1664)

решение которого

т -1М J 5") 2-Л 6i80i4 (1665)

Деление отрезка по формулам (16.52) и (16 63) дает две неравные ча сти. такие что отношение целого к большей части равно отношению большей части к меньшей. Такой тип деления отрезка называется золо тым сечением.

Алгоритм Фибоначчи может быть использован также Д1я [юиска .золотым сечением, где d - (т - 1) {и - I).

При исгюльзовании поиска золотым сечением в одномерной мини мизации коэффициент уменьшения после г; вычиспений значения функ ций

(/ (16 66)

Можно [юказать. что для поиска Фибоначчи при « - оо

(1 /") - F .т"- j "5. (16.67)

Опюшение эффективности поиска Фибоначчи к эффективности [Юиска золотым сечением составляет

F т i 5 =-1.1708 (1668)

Сравнивая (16 60) и (16.63) при / -- 1 и большом значении п, мож ио заметить, что поиск Фибоначчи и поиск золотым сечением начинаются практически с одинаковой скоростью, а в конечном счете интервал неопределенности для последнего метода только на !7 % больше, чем в первом Поиск золотым сечением часто является более предпочтительным, поскольку число операций вычисления значения функции не нужно фиксировать заранее.

164 2 ИНТЕРПОЛЯЦИОННЫ!: методы

Эт методы аппроксимируют изменение целевой функции вблизи минимума многочленами небольшой степени, которые совпадают с целевой функцией в некотором числе точек до тех пор, пока с требуемой точностью минимум не будет достигнут. Наиболее часто используются методы аппроксимации многочленами второй и третьей степеней. Сог ласно методам предполагается, что функция унимодальна, непрерыв иа и имеет непрерывные производные в области поиска. Наклон целе вой функции в начальной точке (обычно при Ф =0) предполагается от рица тельным 3!6

е методы П5,8. Квадратичный мно

Квадратичные Интерпол»

гочлен - многочлен минимальной степени, для которого может су шествовать минимум Пусть

1г{Ф) а + 6Ф -г гФ

(16 69)

квадратичная функция, используемая для аппроксимации целевой функции и (Ф). Необходимое условие минимума h (Ф) состоит в том что {1Н/{1Ф b - 2сФ 0. т. е.

Ф* - -Ь (2с)

(16 70)

где Ф* - точка минимума h (Ф) Достаточные условия минимума h (Ф) состоят в том что

>0 т е >0

(671)

Лчя определения переменных а b и с в (16 69) следует вычислить зна чения и (Ф) в трех точках. Пусть А В, С - три значения аргумента Ф. в которых вычнслсеш значения U (Ф) равные соответственно Ua и в. Uc, у е

Ьа- а- ЬА сА-

Un-a-i-bB-i- сВ (16 72)

Ur----a+bCcC\ В качестве решений (16 72) получаем

а. {илВСф-С} и„СА{С А)и, АВ{В--Л)) Р b-iU(B-a)- UlO - А} I UciA-B)) Р с ---{UAiB -С] \ Ue(C -А) • и, (4 -fi)S Р

Р{А--В){В -С\1С А] Из (16 70) (16 74) и (16 75) минимум h (Ф) получается, как

2{U(B-C)-i-Ug(C-A) I li-{A-B

(16.73) (16,74) (16 75j

(16 76)

(16 77)

Для обеспечения неравенства О О на первой итерации прибли жения кривой квадратным трехчленом может быть использована еле дующая процедура;

1) для и Ua в точке Ф =- О прн заданном начальном шаге /„ вычислить и в точке Ф - t,, н обозначить это значение через U,,

2) если Ui > Ua, to положить Uc Vi и вычислить функцию и в точке Ф /„/2; обозначить это значение через U-i и положить (о -

3) если Ui < Ua. то положить Ud и использовать (16.77) для вычисления Ф*: если и>- Ua то положить Uc U вычислить

функцию V в точке Ф t,J2, получить новое Vи положить „ - 2; повторить шаг 3;

4) если Vi и а, то положить Ии - Ui. вычислить U (2/„) и получить U->:

5) если Up. то положить lie ~ V., и, используя (16.77), вычислитьФ*. Если (/„ Ни, то положить и л (Jr. Он (/ н ia ~ 2 /„; вычислить V в точке Ф - 2 и повторить шаг 5.

Значение Ф*. найденное в описанной процедуре, есть точка минимума аппроксимирующей функции h (Ф), Необ.ходимо добиться, чтобы Ф* было достаточш) близко к депствителышму минимуму функ-

ции и (Ф). о достигается сравнением U (Ф*) с h (Ф*). Точку Ф* считаем достаточ1Ю хороигей аппроксимацией, если при достаточно малом i- вы1юлняетсн условие

(16.78)

[/)(Ф) -•(Ф*) I I Г(Ф) 1"""

Если (16.78) не выполняется, то для аппроксимации [/ (Ф) ищем новую квадратичную функцию h (Ф) - а • ЬФ - с Ф-. Для опредезе-ния постоянных о. Ь и с могут быть использованы три наилучшие из текущих значений Vа. Ua, и Ц (Ф*). Они выбираются следующим обрагюм:

если Ф*>В, UiOXiVH. переобозначагм АВ, В*-Ф*. СС.

-В, В

если ФЙ, и(Ф)>иц. нереобозначаем

АА. В*~В, СФ*. если Ф*<Й, (/(Ф*)</н, переобозначаем

АА, Й-Ф*. C-fi,

если Ф*<Й, (Ф*)>(/л, переобозначаем ф", С-С

(16,79) (16,80) (16,81) (16,82)

Новые значения А. В » С получаются из (16,79) - (16.82). Новое значение Ф* может быть получено за счет одного дополнительного зачисления значения функции. Если и это Ф* не удовлетворяет условиям (16.78), то следует подобрать новую квадратичную функцию. Оформленная в виде алгоритма процедура интерполяции имеет вид Квадратичная интерполяция i ~0 Л - О ид:-и(0} t-, = U(t«l

then

В to

и, - и,

L,-: U(2t„) Vihile L, do

A В

а 2i„

Ur и,

to - 2t„ Uj- U(2lft) end (while) С-.21,

Repeat С-to V,- U, to >e 2 U, и (to)

В--Ц Ub

Полечить Ф*. исподьчуя (16.[7) Repeat

Уф и(Ф)

В<Ф then

begin

If 1в>иф tUen

begin

A В