8.2. Методы с однократным вычислением значения функции

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

Эти методы, состоящие в построении последовательности отрезков [a_k, b_k], стягивающихся к точке х^* минимума функции φ(x) на исходном отрезке [а₀, b₀], обладают следующими свойствами.

А. Для любого k = 0, 1, ... k-м приближением x_k точки х^* является одна из двух точек: y_k либо z_k, отстоящих на одинаковых расстояниях

от соответствующих концов отрезка [a_k-1, b_k-1]. Для этого должны выполняться следующие соотношения:

где число c_k-1 выбирается таким, что

В. На каждом шаге (за исключением первого) допускается вычисление лишь одного значения функции φ(х).

Пользуясь формулами (8.1)-(8.3), будем находить отрезок [a_k, b_k] следующим образом.

(8.4)

(8.5)

Анализ процедуры (8.1)-(8.5). Из (8.1), (8.2) следует, что

Отсюда и из (8.4), (8.5) и (8.1) получаем

Обращаясь к (8.4) и (8.5), мы видим, что

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

(8.8)

Для того чтобы обеспечить выполнение условий (8.8),

необходимо соответствующим образом подбирать числа c_k.

Пуст φ(y_k)≤φ(z_k). Тогда (см. (8.4), (8.1) и (8.7))

Если

то есть

(8.9)

то (см. (8.2))

Если

то (см. (8.5), (8.2), (8.1), (8.9))

Таким образом, соотношения (8.9)обеспечивают выполнение условия (8.8)

Из (8.9) получаем

(8.10)

и, далее, из индуктивных предположений следует

(8.11)

где

Числа F_j, удовлетворяющие соотношению (8.12) и условию F₁ = F₂ = 1, называются числами Фибоначчи. Приведем несколько первых из них: