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

Следовательно, план Фп+1 является оптимальным, и теорема доказана.

Итак, единственная минимизирующая функцию f точка может быть с помощью п наблюдений опреде­лена на отрезке длины L с ошибкой, не превосходя­щей

Поэтому п наблюдений позволяют определить точку, минимизирующую f, с ошибкой ε или меньше, на отрезке, длина которого не превосходит εип+2.

Наконец, чтобы быть уверенным в том, что точка, минимизирующая функцию f, определена на отрезке длины L с ошибкой, не превосходящей ε, необходимо произвести такое число п наблюдений, что

Таким образом, мы ответили на все вопросы п. 3.

12. Решение задачи Б можно получить из описан­ного выше решения задачи А без особого труда.

Пусть нам дан отрезок длины L. Проделаем на этом отрезке первые п — 2 шага фибоначчиева плана Фп-1. В результате мы придем к отрезку длины с концами х' и х' 'и с известным значением f в одной из точек

Ограничимся рассмотрением первого из этих случаев (второй рассматривается симмет­рично).

Итак, пусть f(x1) нам уже известно. Выберем произвольное число γ, по абсолютной величине меньшее, чем

вычислим f(x2 — γ) (это есть (п—1)-е вычисленное значение функции f) и (4>:шпим f(x1) и f(x2 — γ).

Если (случай ○ на рис. 7), то, очевидно, находится между х' и х2 — γ.

Рис. 7.

Вычислим

(это — последнее, n-е вычисленное значение функ­ции f).

Если при этом

(случай × на рис. 7), то расположено между х' и х1. Положим

Ошибка в определении не превосходит половины длины отрезка от х' до х1, т. е. Если

(случай ○ на рис. 7), то находится междуи х2 — γ. Положив мы совершим ошибку, не большую, чем

Пусть теперь (рис. 8).

Рис. 8

Тогда находится между х1 и х".

Вычислим f (х2) (по­следнее вычисленное зна­чение f).

Если

(случай ○ на рис. 8), то расположено между х1 и х2; беря мы допустим ошибку, достигающую лишь

Если, наконец,

(случай × на рис. 8), то расположено между х2 — γ и х". положив мы совершаем ошибку, не превосходящую

В наихудшем для нас случае при γ > 0 ошиб­ка может таким образом достигнуть величины а при γ < 0 — величины Поскольку, однако, число γ находится в нашем распоря­жении, мы можем сделать ошибку, сколь угодно близ­кой к

Нам остается убедиться в том, что ошибку уменьшить нельзя.

В самом деле, отклонения от описанного плана на каком-либо из первых п — 2 шагов могут привести, как видно из теоремы п. 11, только к увеличению длины отрезка, в котором местоположение минимизи­рующей точки определяется последующими измере­ниями, и тем самым к заведомому увеличению макси­мальной ошибки. Остается проверить оптимальность действий, совершаемых на последних двух шагах.

Прежде всего, отклонение от описанных действий может означать окончательный выбор в качестве не середины отрезка, где эта точка действительно распо­ложена, а другой точки. Ясно, что это приведет к тому, что возможная ошибка окажется равной боль­шей части отрезка, т. е. возрастет. Следовательно, должна быть выбрана именно середина отрезка.

Далее, мы могли бы выбрать для последнего опре­деления f точку, не близкую к точке x1 (или соответ­ственно к x2). Но тогда возможная ошибка увеличи­лась бы и притом пропорционально расстоянию меж­ду этими точками.

Наконец, к таким же последствиям привел бы выбор точки для предпоследнего определения f, дале­кой от х2 (соответственно от х1).

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

Это показывает, что задача Б нами решена.

Мы предоставляем читателю сформулировать в случае задачи Б ответы на остальные вопросы, пере­численные в п. 3.

13. В предыдущих пунктах описание самого пла­на поиска сопровождалось уточнениями постановки задачи, формулировками, связанными с понятием оптимальности и обоснованиями оптимальности конст­руируемою плана. Все эти отступления от прямого описания являются неотъемлемыми элементами вся­кого математического рассуждения, цель которого состоит не только в указании какого-то процесса, но и в доказательстве того, что этот процесс — именно тот, который нас интересует. Вместе с тем во многих случаях существенным является четкое описание дей­ствий как таковых, а вся аргументация этих действий становится совершенно неважной. Это бывает тогда, когда, например, после решения задачи имеется в виду фактическое осуществление этого решения. В та­ких случаях для реализации решения задачи на прак­тике необходимо располагать не столько математи­ческим обоснованием верности решения, сколько предельно четкими, не допускающими каких бы то ни было кривотолков, предписаниями по его претво­рению в жизнь.

План наиболее точных поисков на отрезке от х' до х" точки , минимизирующей функцию f в условиях задачи А в изложении, преследующем только что описанные, так сказать, «практические» цели, напо­минает план установления вида растения по ботани­ческому определителю (заметим, что определение ра­стения есть тоже поиск!). Он принимает следующий вид (если в конце пункта не указывается, к какому пункту следует переходить, то нужно переходить к следующему пункту):

1°. Сравнить 1 и п:

а) если п = 1, то перейти к п. 2°;

б) если п > 1, то перейти к п. 4°.

2°. Вычислить

3°. Вычислить f(x); на этом процесс кончается.

4°. Вычислить

5°. Вычислить f (x1) и f (х2).

6°. Сравнить 2 и п:

а) если п = 2, то перейти к п. 7°;

б) если п > 2, то перейти к п. 10°.

7°. Сравнить f (xi) и f(x2):

а) если то перейти к п. 8°;

б) если f (x1) > f (x2), то перейти к п. 9°.

8°. Положить = х1 и закончить процесс.