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

Каждое положительное значение ε определяет здесь некоторый план. Чем ближе ε к нулю, тем этот план лучше. Так как для любого ε > 0 найдется еще меньшее положительное число, для любого плана най­дется еще лучший. Следовательно, оптимального плана для задачи Б нет.

Однако для задачи Б существуют «почти опти­мальные» планы, приводящие к таким результатам, которые можно улучшить лишь незначительно. Го­воря точнее, каково бы ни было число γ> 0, суще­ствует такой план Рγ, что никакой другой план не сможет уменьшить даваемую планом Рγ ошибку больше, чем на γ.

7. План, описываемый последовательностью (1) при ε, достаточно малом по сравнению с длиной L рассматриваемого нами отрезка, оптимальным не является. Придерживаясь этого плана, нам придется в наихудших условиях выполнить все r вычислений.

Попробуем, однако, поступить несколько иначе. Будем вычислять члены последовательности (1) че­рез один:

f (0), f(2ε), f (4ε), ...;

найдем в полученной последовательности наименьший из членов (пусть им будет f(2kε)) и вычислим два значения функции f((2k—1)ε) и f ((ε k +1)ε). То из трех значений переменной (2k—1) ε, 2kε и (2k + 1) ε, при котором значение функции f будет наименьшим из трех

очевидно, и есть с точностью до ε. Этот новый план приводит в наихудших условиях к цели после выпол­нения примерно +2 вычислений. При больших r это существенно меньше, чем число вычислений, тре­буемых первым планом.

Итак, первый план не является оптимальным. По сходным причинам второй план также нельзя, вообще говоря, считать оптимальным.

Однако второй план отличается от первого одной весьма сущестпенной чертой: предусматриваемые им точки определения значений функции планируются за­ранее лишь частично, а выбор оставшихся точек осу­ществляется на основе сравнений уже вычисленных значений функции. Интуитивно совершенно ясно, что пыбор наилучших действий всегда должен быть свя­зан с использованием информации о результатах действий, которые мы уже произвели. Второй план яв­ляется в этом отношении более совершенным, чем первый. Но и он, вообще говоря, поддается дальней­шим усовершенствованиям, которые в конце концов приведут нас к оптимальному плану.

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

Очевидно, такой процесс последовательного вычисления зна­чений функции f вполне определяется некоторым законом, ставя­щим в соответствие для любого k≥0 произвольным наборам точек х1, х2, … хk и значений функции f в этих точках ту или иную точку xk+1 или же решение закончить наблюдения над функцией f, приняв ту или иную точку в качестве . Этот закон соответствия принято называть решающей функцией.

Каждый план определяет некоторую решающую функцию. Точно так же и всякая решающая функция определяет некото­рый план. В сущности, решающая функция — это и есть четкое и формализованное описание плана. Например, решающая функ­ция, определяющая первый из рассмотренных в предыдущем пункте планов, ставит в соответствие каждому числу 0 ≤k < r точку (k + 1)ε, а числу r — окончание процесса.

Понятие решающей функции принадлежит к числу важней­ших понятий математики.

8. Пусть цель плана Р состоит в определении с наименьшей погрешностью точки , минимизирующей функцию f на отрезке длины L на основе п наблюде­ний. Такой план мы далее будем называть п-шаговым.

Пусть в условиях некоторого n-шагового плана Р удается определить на отрезке длины L с точностью до ε. Эта точность зависит от самого плана Р, а также от n и от L. Поэтому мы можем считать ее функцией от Р, п и L и обозначать для задачи А через τАР (n, L), а для задачи Б — через Под τР (n,L) далее будет подниматься любое (но, конечно, в пределах одногорассуждения одно и то же) из выражений

n-шаювый план Р0 определения минимума f на отрезке длины L является оптимальным в задаче А, если не более, чем

для любого другого плана Р, т. е.

Это можно также записать как

(2)

Число таким образом, оказывается характеристикой уже не плана, а самой задачи (именно, задачи нахождения за п шагов минимизирующей точки функции f на отрезке длины L). Поэтому оно не зависит от какого-либо плана, а зависит только от п и L и может быть просто обозначено через τА(п, L).

В условиях задачи Б дело обстоит несколько слож­нее. Здесь, как мы уже видели, нет оптимального плана, гарантирующего в наихудших условиях наи­меньшую погрешность. Однако существует такая по - решность, к которой можно подойти сколь угодно близко, если только выбрать подходящий план. Эта погрешность, которую называют предель­ной погрешностью, также зависит только от условий задачи. Поэтому ее можно обозначить через τБ(п, L). Любой план приводит к большей погреш­ности:

и поэтому мы не можем написать здесь равенство, аналогичное (2).

Забегая несколько вперед, скажем, что итог всех наших рассуждений состоит в получении явных выражений для Как окажется, в эти выражения входят числа Фибоначчи:

(3)

(4)

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

раз.

Для достаточно больших п это отношение близко к что соответствует увеличению точности примерно на 23%.

9. Совершенно ясно, что для всех дальнейших рас­суждений важны не каждое из чисел L и ε само по себе, а отношение L и ε. Это отношение является относительной ошибкой положения . Если это отно­шение нам дано, то мы можем, выбирая надлежащим образом единицу измерения величины х (т. е. единицу измерения длины нашего отрезка), взять одно из чи­сел L и ε совершенно произвольно.

Это соображение приводит к выводу.

Изменение масштаба вдоль оси х изменяет как численное выражение длины отрезка L, так и ошибку в определении положения искомой точки любым планом Р в одно и то же число раз. Другими словами, для любого положительного λ должно быть

(5)

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

Отсюда непосредственно следует, что равномерное растяжение (или сжатие) интервала изменения функ­ции f в любое число раз осуществляет лишь «подоб­ное преобразование» оптимального плана, не нарушая при этом его оптимальности.

Значит, ошибки τР (п, λL) и τР (п, L), фигурирующие в равенстве (5), достигаются не просто в результате осуществления тех или иных планов, а могут быть достигнуты в результате применения одного и того же плана, различным образом «подобно преобразован­ного».

10. После всех этих предварительных рассмотрений перейдем к нахожде­нию оптимального плана для задачи А и к доказа­тельству формул (3) и (4).

Лемма. Каковы бы ни были п ≥ 1 и L, суще­ствует п-шаговый план поиска точки , минимизи­рующей значение функции f (с одним минимумом) на отрезке длины L за п шагов и обладающей сле­дующими свойствами: