8.3. Метод Фибоначчи

Будем выбирать числа c_k из следующих соображений: при заранее заданном числе шагов n (то есть k = 1, 2, .... n) числа c_k выберем такими, чтобы длина отрезка [а_n, b_n] была наименьшей.

Так как из (8.7)

(8.13)

то возникает задача

(8.14)

при условиях

(8.3)

(8.15)

(8.16)

(8.17)

Условия (8.15) -(8.17) с очевидностью вытекают из (8.9)-(8.11).

Из (8.14), (8.15), (8.16) и (8.17) следует

Таким образом,

(8.18)

Пользуясь индуктивным предположением, легко проверить, что из условия 0≤c_k≤1/2, k = 0, l, ..., и из соотношения

следует для k≥3

если k четное,

если k нечетное,

и 0≤c_n-1≤1/2, 1/3≤c_n-2≤1/2.

Тогда задача (8.14), (8.3), (8.15),-(8.16), (8.17) сведется к следующим двум.

Если n-нечетное, то для n≥3

откуда

(8.19)

Если n - четное, то для n≥4

откуда

и, кроме того, с₀ = 1/2 при n = 1, с₀ = 1/3 при n = 2. Наконец, вычислим минимальное значение величины

Для этого воспользуемся известным соотношением (также легко доказывается по индукции):

Тогда из (8.18) и (8.19) вытекает, что

Таким образом,

(8.20)

Это соотношение позволяет выбрать число n при заданной точности ε > 0 вычисления точки х^*. Так как

то величина n должна обеспечить выполнение неравенств

или

Проведенные рассмотрения можно резюмировать в виде следующей теоремы об оптимальном методе Фибоначчи (см. (8.1), (8.2), (8.9), (8.19), а также свойства A и В).

Теорема 8.1.Среди всех методов, обладающих свойствами А и В, метод Фибоначчи при заданном числе шагов n обеспечивает минимальную длину отрезка [а_n, b_n], содержащего точку х^*.