Основы теории оптимизации (стр. 25 )

1) на каждом шаге рассматривается некоторый отрезок х'х";

2) на первом шаге вычисляется значение функции f в одной из точек:

3) к началу каждого из последующих шагов с но­мером k (т. е. при 1 < k ≤ n) известно значение f в одной из следующих точек:

(6)

4) на k-м (1 < k ≤ n) шаге вычисляется значение в другой из точек (6);

5) на k-м (1 < k ≤ n) шаге производится сравне­ние чисел f(x1) и f(x2); при этом, если окажется, что f(x1)≤f(x2), то на (k+1)-м шаге рассматривается отрезок х'х2, а если f(x\) ≥ f(x2), то отрезок х1х".

Доказательство ведется индукцией по п.

Если п = 1, то, очевидно, мы имеем дело с отрез­ком от 0 до L; значение функции f вычисляется в точке

последующих же шагов в этом случае воооще нет.

Предположим теперь, что существование некото­рого п-шагового плана с требуемыми в условиях лем­мы свойствами нами уже установлено для любого отрезка. Займемся построением интересующего нас (п + 1) - шагового плана, проверяя параллельно соблюдение условий леммы. Будем на каждом шаге рассматривать некоторый отрезок х'х".

Возьмем в качестве первого шага выбор точки

а в качестве второго — выбор точки

и сравнение значений функции f(x1) и f(x2). В случае, когда f(x1)≤f(x2), мы приходим к рассмотрению отрезка между 0 и х2 (здесь 0 играет роль х', а х2 — роль х"), а в случае f(x1)>f(x2) — к рассмотрению отрезка между х1 и L (здесь х1 вы­ступает в роли х', a L в роли х"}. Длина рассматрииасмого отрезка в обоих случаях равна

После выполнения этих двух шагов мы находимся применительно к рассматриваемому отрезку точно в таких же условиях, что и при осуществлении п-шагового процесса после выполнения его первого шага.

Именно, на отрезке длины известно значение функции f в точке, отстоящей на

От одного из его концов. Поэтому мы можем «перейти» на этот n-шаговый процесс и довести его до конца. На основании индуктивного предположения мы мо­жем считать, что для последних п шагов выполняются условия 3), 4) и 5). Следовательно, нам остается рас­смотреть условия начала второго шага и его прове­дения. Но, очевидно, точка

имеет вид первого из выражений (6) для случая k — 2, если вместо п в него подставить п+1, а роль второго выражения в соответствующей ситуации играет выбираемая нами точка

Этим индуктивный переход обоснован и лемма доказана.

11. Будем называть n-шаговый план, существова­ние которого было доказано в предыдущей лемме, п-шаговым фибоиаччиевым планом, или, короче, пла­ном Фg.

Теорема. 1) План Фg является единственным оптимальным п-шаговым планом.

Доказательство ведется индукцией по п.

Рассмотрим сначала одношаговый план, состоя­щий в выборе в качестве некоторой точки из ин­тервала от х' до х". Очевидно, в наименее благо­приятных условиях ошибка может достигнуть здесь наибольшего из чисел х" — и — х'. Если эти числа различны, то эта максимальная ошибка превосходит , если же они равны, то максимальная ошибка равна .

Таким образом, план Ф1 является оптимальным одношаговым планом, а

При п = 2 мы имеем дело с планом Ф2, состоя­щим в вычислении и сравнении значений функции

и выбора в качестве х точки

Максимальная ошибка в определении истинного зна­чения здесь, как легко видеть, достигает

Любой иной выбор точки будет приводить к большим возможным ошибкам.

Основание индукции, таким образом, доказано.

Предположим теперь, что фибоначчиев план Фп обладает требуемым в условиях теоремы свойством, и рассмотрим (п + 1)-шаговые планы.

Произведя в плане Фп+1 первые два наблюдения над функцией f, мы в результате сравнения двух ее найденных значений сведем дело к применению к от­резку длиныв котором известно значение f и одной из точек, плана Фп, что даст нам в наименее благоприятном случае ошибку

Следовательно,

Нам остается показать, что план Фп+1 оптимален.

Возьмем с этой целью наблюдения над функцией f и двух произвольных точках, и (для определен­ности будем считать, что < ). Сопоставление зна­чения f() с f() приводит к поискам точки либо на отрезке от 0 до , либо на отрезке от до L.

Если

то и случае f()>f() нам придется искать по не которому n-шаговому плану минимизирующую f точку на отрезке длины L — , т. е. большей, чем

Даже если положение точки на этом отрезке наиболее благоприятно, то ошибка в определении окажется на основании индуктивного предположения большей, чем

Симметричные рассуждения показывают, что план, начинающийся выбором некоторой точки

также может при соответствующих неблагоприятных условиях привести к большей ошибке в определении , чем план Фп+1. Пусть теперь

Если в действительности х находится между 0 и то на поиски местоположения этой точки нам остается п — 1 наблюдение, а длина отрезка, заключающего эту точку, больше, чем Значит, даже план Фп+1 (который, по предположению, в этих условиях оптимален) приведет нас к ошибке, большей, чем

Симметрично разбирается случай, когда