Рассмотрим следующую задачу. Имеются две величины x и y, связанные функциональной зависимостью. Известно, что когда x пробегает промежуток [a, b], величина y сначала убывает, затем возрастает и в некоторой точке принимает свое наименьшее значение. Более формально: на промежутке [a, ] величина y убывает, на промежутке [, b] возрастает, а в точке принимает наименьшее значение. При этом не исключается, что a = (величина y возрастает на всем промежутке) или = b (величина y убывает на всем промежутке). Требуется указать оптимальный алгоритм определения минимума, т. е. приближенного нахождения точки минимума и значения функции в этой точке при условии, что разрешается произвести n наблюдений: можно произвольным образом выбрать n точек x1, x2, …, xn на промежутке [a, b] и получить соответствующие им значения y1, y2, …, yn.
Уточним понятие оптимальности. Пусть Ω – некоторый
алгоритм определения точки минимума. Параметрами, определяющими его работу, служат величины n, a, b. Алгоритм Ω может быть применен к любой функции y = f(x), определенной на промежутке [a, b], которая убывает на [a, ] и
возрастает на [, b], где – некоторая (неизвестная) точка из
[a, b]. Будем для краткости называть такие функции функциями с одним минимумом (рис. 3).
a b
Рис. 3
Множество всех функций с одним минимумом на промежутке [a, b] обозначим через V(a, b) (или просто V, если из контекста ясно, о каком промежутке идет речь). Результатом применения алгоритма Ω к функции f ∈ V является некоторая пара чисел (, ) такая, что ∈ [a, b] – приближенное значение точки минимума, а = f(). Мы будем писать = Ω(f; n, a, b) или просто = Ω(f), когда ясно, каковы значения параметров n, a, b. Качество алгоритма будем оценивать абсолютной величиной погрешности определения точки минимума в наихудшем случае:
(Ω) = sup {| – | : f ∈ V}.
Будем считать алгоритм Ω оптимальным, если он дает наименьшую ошибку, т. е. (Ω) ≤ (Ω′) для любого алгоритма определения минимума Ω′.
Таким образом, если положить
ф0 min
sup
щ− о ,
Ω f
то 0 = (Ω′) для оптимального алгоритма Ω.
Вообще говоря, значение 0 зависит от числа допустимых наблюдений n и промежутка [a, b]. Легко понять, что при фиксированном числе наблюдений существенным является не сам отрезок [a, b], а его длина l = b – a, так что 0 = 0(n, l). Далее, относительно переменной l функция 0 = 0(n, l) является однородной первой степени: 0(n, l) = 0(n, l) для > 0 (оптимальность алгоритма не зависит от выбора единицы измерения длины). В оставшейся части параграфа будет
установлено, что
0(n, l) =
l ,
Fn 2
где Fn+2 – число Фибоначчи. При этом в оптимальном алгоритме в качестве первых точек наблюдения берутся
«фибоначчиевы узлы»:
c a
Fn
Fn2
b − a ;
d a
Fn1 b − a .
Fn2
Начнем с анализа алгоритмов поиска минимума при малом числе наблюдений.
1. При n = 0 алгоритма поиска минимума не существует: чтобы указать (пусть и произвольным образом) точку и значение функции в ней, нужно произвести хотя бы одно
наблюдение – вычисление значения функции в этой точке. При n = 1 оптимальный алгоритм состоит в том, чтобы в качестве указать середину отрезка [a, b]. В этом случае | – | ≤ l/2, где бы ни располагалась точка минимума . При этом одно наблюдение не дает никакой информации о расположении точки минимума. В частности, возможно = a или = b. Какова бы ни была точка , имеем | – | ≥ l/2 для функции с минимумом в точке a, или | – | ≥ l/2 для функции с минимумом в точке b. Значит,
sup {| – | : f ∈V} ≥ l/2.
Таким образом,
0(1, l) = l/2.
2. Рассмотрим случай, когда допустимы два наблюдения, n = 2. Пусть x1 и x2 – точки, в которых производились наблюдения, а y1, y2 – значения функции в точках x1 и x2 соответственно. Для определенности будем считать, что x1 <x2. Если y1 ≤ y2, то можно утверждать, что точка
минимума расположена на отрезке [a, x2] (рис. 4).
a x1
x2 b
a x1 x2 b
Рис. 4
Так как лимит наблюдений (вычислений значения функции) исчерпан, лучшим претендентом на роль точки минимума в этом случае служит x1. Наибольшее отклонение 1 от настоящей точки минимума получится в том случае, когда минимум достигается в концевой точке отрезка [a, x2], наиболее удаленной от x1, то есть
1 = max {x1 –a, x2 – x1 }.
Аналогично при y2 ≤ y1 лучшим претендентом на роль точки минимума служит x2. Отклонение от настоящей точки минимума в «наихудшем» случае составляет
2 = max {b – x2, x2 – x1 }.
Положим
= max {1, 2 } = max {x1 –a, b – x2, x2 – x1 }.
Так как
(x1 –a) + (b – x2) + (x2 – x1) = b – a,
то принимает наименьшее значение 0 в случае, когда
x1 –a = b – x2 = x2 – x1 = (b – a)/3,
и при этом 0 = (b – a)/3. Следовательно,
0(2, l) = l/3.
3. Случай трех наблюдений, n = 3, особенно поучителен.
Покажем, что в этом случае 0 = l/5, а в оптимальном алгоритме две точки наблюдения суть
3223
x10
5 a 5 b,
x20
5 a 5 b,
а третья точка определяется как
41
при f(x10) ≤ f(x20),и
x30
5 a 5 b
14
при f(x10) > f(x20).
x30
5 a 5 b
Если f(x30) ≤ f(x10) ≤ f(x20) (в этом случае ∈[a, x10]), то полагаем = x30. Если f(x10) ≤ f(x20), но f(x30) > f(x10) (в этом
случае ∈[x30, x20]), то полагаем = x10.
a x30 x10 x20
b a x30 x10 x20 b
Рис. 5
Погрешность в худшем случае составит x30 – a = x20–x10 = l/5 (рис. 5).
Аналогично, если f(x10) > f(x20), полагаем = x20 при f(x20) ≤ f(x30), или = x30 при f(x20) < f(x30). Здесь погрешность в худшем случае также равна l/5.
Покажем теперь, что при ином выборе точек наблюдения погрешность (в неблагоприятном случае) окажется больше чем l/5.
Предположим, что произведены два наблюдения в точках x1
и x2, для определенности пусть x1 <x2. Если f(x1) ≤ f(x2), то
можно утверждать, что точка минимума расположена на отрезке [a, x2]. Погрешность, с которой можно, произведя два наблюдения, найти точку минимума на отрезке длины x2 – a,
оценивается величиной
0(2, x2 – a) =
2
x2 − a l
3
ф0 (2, l ) =
x2 − a l
⋅1=
x2 − a .
3l
Если
x2 x20
5 a 5 b , то 0(2, x2 – a) > (b – a)/5 = l/5.
Аналогично можно показать, что и при x2 < x20 погрешность определения точки минимума в худшем случае превосходит l/5. Таким образом, если x2 ≠ x20, погрешность в определении минимума превосходит l/5. Точно так же доказывается, что и при x1 ≠ x10 погрешность в определении минимума превосходит l/5.
Тем самым описанный в начале этого пункта алгоритм оказывается оптимальным алгоритмом определения минимума
при трех наблюдениях, и
0(3, l) = l/5.
Приведем теперь общее рекурсивное описание оптимального алгоритма поиска минимума.
Обозначим описанные выше оптимальные алгоритмы поиска минимума при одном, двух или трех допустимых наблюдениях через 1, 2, 3 соответственно. Мы дадим рекурсивное описание последовательности алгоритмов 1, 2, 3, …, в которой k – алгоритм поиска минимума при k допустимых наблюдениях. Параметрами алгоритма k служат
концы отрезка [a, b], на котором ищется минимум, аргументом
– функция y = f(x), определенная на отрезке [a, b]. Результатом работы алгоритма является пара чисел и = f().
Предположим, что уже имеются описания алгоритмов 1,
2, …, n. При этом алгоритмы удовлетворяют следующим требованиям:
1) при исполнении алгоритма k значения функции f
вычисляются k раз;
2) если k ≥ 2, первые два вычисления производятся в точках
Fk 1
Fk 2
a Fk b ,
Fk 2
Fk
Fk 2
a Fk 1 b ;
Fk 2
3) погрешность определения точки минимума в худшем случае составляет k(l) = l/Fk+2, где l = b – a – длина отрезка;
4) алгоритм k является оптимальным алгоритмом поиска минимума с числом наблюдений, не превосходящим k.
Дадим теперь описание алгоритма n+1. Положим
x Fn 2 a
Fn1 b, x
Fn1 a Fn 2 b.
1 Fn3
Fn3
2 Fn3
Fn3
Вычисляем f(x1) и f(x2). Пусть сначала f(x1) ≤ f(x2).
Применим алгоритм n для поиска минимума на отрезке [a, x2]. Пусть и = f() – результат этого применения. Примем пару чисел и = f() в качестве результата применения алгоритма n+1 к отрезку [a, b]. При исполнении
алгоритма n применительно к отрезку [a, x2] первые два
так что одно из двух вычислений уже выполнено, и для последующего исполнения алгоритма n потребуется n – 1 вычисление. В общей сложности (с учетом вычислений f(x1) и f(x2)) выполнено n + 1 вычисление значений функции f. Таким образом, алгоритм n+1 удовлетворяет первым двум требованиям, предшествующим его описанию. Оценим теперь
возникающую погрешность = n(x2 – a) . Так как
F F F −F F
x2 – a =
n 1 a n2 b − a = n 1 n3a n2 b=
Fn3
Fn3
Fn3
Fn3
= −Fn 2 a Fn 2 b= Fn2 (b − a) ,
Fn 3
то
Fn 3
Fn3
= n(x2 – a) = (x2 – a)/Fn+2 = (b – a)/Fn+3.
Следовательно, третье условие для n+1 также выполняется.
Пусть теперь f(x1) > f(x2). Применим алгоритм n для поиска минимума на отрезке [x1, b]. Пусть и = f() – результат этого применения. Примем пару чисел и = f() в качестве результата применения алгоритма n+1 к отрезку [a, b]. Так же,
как и в предыдущем случае, имеем:
Fn1 x
Fn b =
Fn1 Fn2 a
Fn1 b
Fn b =
Fn2 1
Fn2
Fn2
Fn3
Fn3
Fn2
F F 2 F F
= n1 a n1 n3 n b =
F F 2 ( F F )( F − F )
n1 a n1 n2 n1 n2 n1 b =
Fn3
Fn2 Fn3
Fn3
Fn2 Fn3
= Fn1 a
F
n2
b = Fn1 a Fn2 b x ,
Fn3
Fn2 Fn3
Fn3
Fn3 2
так что для исполнения алгоритма n потребуется n – 1 вычисление. Как и в предыдущем случае, алгоритм n+1 удовлетворяет обоим требованиям, предшествующим его
описанию. Третье требование тоже выполняется. Так как
b –x1 = b –
Fn2 a−
Fn1 b=
− Fn2 a
Fn3
−Fn1 b=
Fn3
Fn3
Fn3
Fn3
− Fn2 a Fn 2 b= Fn2 (b − a) ,
Fn3
то
Fn3
Fn3
= n(b –x1) = (b –x1 )/Fn+2 = (b – a)/Fn+3.
Осталось доказать, что алгоритм n+1 является оптимальным при условии, что используется не более n + 1 наблюдения.
Пусть t1 и t2, t1 < t2, – точки первых двух наблюдений. Если f(t1) ≤ f(t2), точку минимума нужно искать на отрезке [a, t2], в противном случае – на отрезке [t1, b]. Поскольку минимум
может оказаться в одной из концевых точек этих отрезков,
сузить область поиска нельзя. Предположим, что
t1
Fn2 a
Fn3
Fn1 b .
Fn3
При f(t1) > f(t2) требуется найти точку минимума на отрезке [t1, b], произведя не более n – 1 наблюдения. Можно, правда воспользоваться тем, что значение в точке t2 ∈ [t1, b] уже вычислено. По индуктивному предположению оптимальным алгоритмом определения минимума за n наблюдений служит n. Если точка t2 выбрана в соответствии с алгоритмом n, то применение этого алгоритма обеспечит
погрешность
= n(b – t1) = (b – t1)/Fn+2.
Применение любого другого алгоритма даст большую погрешность. Если
t1
то
Fn2 a
Fn3
Fn1 b ,
Fn3
и, значит,
b – t > Fn 2 (b −a)
Fn3
> (b – a)/Fn+3.
Следовательно, в оптимальном алгоритме должно быть
t1 ≥
Fn2 a
Fn3
Fn1 b .
Fn3
Если точка минимума находится на отрезке [a, t1], то на ее поиск остается n – 1 наблюдение (знание f(t1) не дает в этом случае никакой дополнительной информации о расположении точки минимума). По индуктивному предположению оптимальным алгоритмом определения минимума за n – 1 наблюдение является n–1. Этот алгоритм обеспечивает определение минимума с погрешностью
= n–1(t1 – a) = (t1 – a)/Fn+1.
Если
то
t1
Fn2 a
Fn3
Fn1 b,
Fn3
t1 – a >
Значит, и в этом случае
Fn 1 (b − a) .
Fn3
> (b – a)/Fn+3.
Следовательно, в оптимальном алгоритме
t1
Fn2 a
Fn3
Fn1 b.
Fn3
По симметрии в оптимальном алгоритме должно также
выполняться и равенство
t Fn1 a Fn2 b.
2 Fn3
Fn3
Но справедливость последних двух равенств и означает, что алгоритм n+1 является оптимальным.
[a, b]. Будем для краткости называть такие функции функциями с одним минимумом (рис. 3).
a b
Fn 2
Fn2
Fn2
2. Рассмотрим случай, когда допустимы два наблюдения, n = 2. Пусть x1 и x2 – точки, в которых производились наблюдения, а y1, y2 – значения функции в точках x1 и x2 соответственно. Для определенности будем считать, что x1 <x2. Если y1 ≤ y2, то можно утверждать, что точка
a x1 
Рис. 4
случае ∈[x30, x20]), то полагаем = x10.
a x30 x10 x20
Рис. 5
0(2, x2 – a) =
ф0 (2, l ) =
3l
Fk 2
Fk 2
Fn a 
Fn1
= n n3 n1 a 
Fn2
Fn2
= n1 a n1 n3 n b =
Fn3