Метод Фибоначчи: Минимизация Функции Шаг за Шагом

Метод Фибоначчи — это один из классических численных методов, который применяют для поиска минимума функции одной переменной на заданном отрезке. Его ценность состоит в том, что он позволяет последовательно сужать интервал поиска и при этом рационально использовать уже выполненные вычисления. Почему это важно? Потому что в задачах оптимизации не всегда удобно находить точное решение в явном виде. Именно поэтому на практике часто ищут не точное, а достаточно точное приближение. В этой статье мы рассмотрим, какую задачу решает метод Фибоначчи, почему в нём используют числа Фибоначчи и как строятся внутренние точки. Также мы увидим, каким образом в конце получают приближённое значение точки минимума.

Метод Фибоначчи: Какую Задачу Решает Этот Подход

Начнём с постановки задачи. Пусть задана функция

\[
f(x), \qquad x \in [a,b].
\]

Нужно найти такую точку \( x^* \) на отрезке \( [a,b] \), в которой функция принимает наименьшее значение:

\[
f(x^*)=\min_{x\in[a,b]} f(x).
\]

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

При этом нужно помнить важное условие. Обычно метод Фибоначчи применяют к унимодальной функции на отрезке \( [a,b] \). Это означает, что на этом отрезке функция имеет только один минимум. На практике это можно понимать так: до точки минимума значения функции убывают, а после неё — возрастают. Почему это условие настолько важно? Потому что именно оно позволяет правильно отбрасывать часть интервала после сравнения значений функции в двух внутренних точках.

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

Числа Фибоначчи: Почему Метод Фибоначчи Опирается Именно на Них

Теперь возникает вполне естественный вопрос: почему в этом методе появляются именно числа Фибоначчи? Дело в том, что они позволяют очень удобно организовать последовательное сужение интервала. Благодаря этому после каждого шага одну из уже найденных точек можно использовать повторно, а значит, не приходится каждый раз заново вычислять значение функции в обеих точках.

Последовательность чисел Фибоначчи задаётся рекуррентно:

\[
\begin{gathered}
F_1=1,\qquad F_2=1,
\\[4pt]
F_k=F_{k-1}+F_{k-2}, \qquad k>2.
\end{gathered}
\]

Первые её элементы имеют вид:

\[
F_3=2,\quad F_4=3,\quad F_5=5,\quad F_6=8,\quad F_7=13,\quad F_8=21,\dots
\]

Именно эти числа используют для выбора положения внутренних точек на текущем интервале. Кроме того, они помогают связать длину начального отрезка с требуемой точностью поиска.
Пусть \( \varepsilon \) — заданная погрешность. Тогда выбирают наименьшее число \( F_n \), для которого выполняется неравенство

\[
F_n \geq \frac{b-a}{\varepsilon}.
\]

Что означает это условие? Оно позволяет заранее определить, сколько шагов потребуется, чтобы интервал поиска стал достаточно малым. Итак, количество итераций в методе Фибоначчи не является случайным. Напротив, его определяют заранее через длину начального интервала и требуемую точность.

Здесь полезно заметить ещё одну важную вещь. Если нужно получить более точный результат, то есть взять меньшее \( \varepsilon \), тогда значение

\[
\frac{b-a}{\varepsilon}
\]

возрастает. А это означает, что придётся брать большее число Фибоначчи и, соответственно, выполнять больше шагов. Следовательно, точность и количество итераций в этом методе напрямую связаны между собой.

Начальный Интервал: Как Вычисляют Внутренние Точки

После того как выбрано нужное число \( F_n \), можно перейти к построению двух внутренних точек на отрезке \( [a_0,b_0]=[a,b] \). Именно в этих точках на первом шаге вычисляют значения функции.

Точки \( x_1^{(0)} \) и \( x_2^{(0)} \) задаются формулами

\[
x_1^{(0)}=a_0+\frac{F_{n-2}}{F_n}\cdot (b_0-a_0), \qquad
x_2^{(0)}=a_0+\frac{F_{n-1}}{F_n}\cdot (b_0-a_0).
\]

Эти точки лежат внутри отрезка \( [a_0,b_0] \), причём они расположены в таком порядке:

\[
a_0<x_1^{(0)}<x_2^{(0)}<b_0.
\]

Почему это важно подчеркнуть? Потому что дальше именно порядок точек позволяет правильно понять, какую часть интервала можно отбросить после сравнения значений функции.

Далее вычисляют \( f\left(x_1^{(0)}\right) \) и \( f\left(x_2^{(0)}\right) \), а затем сравнивают полученные значения. Если \( f\left(x_1^{(0)}\right)\leq f\left(x_2^{(0)}\right) \), то по условию унимодальности это означает, что точка минимума не находится правее \( x_2^{(0)} \). Следовательно, правую часть интервала можно отбросить, и новыйинтервал поиска имеет вид \( [a_1,b_1]=[a_0,x_2^{(0)}] \).

Если же \( f \left(x_1^{(0)}\right)>f \left(x_2^{(0)}\right) \), то точка минимума не находится левее \( x_1^{(0)} \). В таком случае отбрасывают левую часть, и новый интервал становится таким: \( [a_1,b_1]=[x_1^{(0)},b_0] \).

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

Метод Фибоначчи: Как Последовательно Сужается Интервал Поиска

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

Если \( f \left(x_1^{(0)}\right)\leq f \left(x_2^{(0)}\right) \), то полагают

\[
a_1=a_0, \qquad b_1=x_2^{(0)}, \qquad x_2^{(1)}=x_1^{(0)},
\]

а новую точку \( x_1^{(1)} \) вычисляют по формуле

\[
x_1^{(1)}=a_1+\frac{F_{n-3}}{F_{n-1}}\cdot (b_1-a_1).
\]

Если же \( f \left(x_1^{(0)}\right)>f \left(x_2^{(0)}\right) \), то берут

\[
a_1=x_1^{(0)}, \qquad b_1=b_0, \qquad x_1^{(1)}=x_2^{(0)},
\]

а новую точку \( x_2^{(1)} \) находят так:

\[
x_2^{(1)}=a_1+\frac{F_{n-2}}{F_{n-1}}\cdot (b_1-a_1).
\]

После этого вычисляют значение функции только в новой точке и выполняют следующее сравнение. Затем процедура повторяется шаг за шагом. Таким образом, интервал неопределённости каждый раз становится меньше.

Что получаем в итоге? Не точное аналитическое решение, а достаточно узкий интервал, внутри которого находится точка минимума. Именно поэтому метод Фибоначчи относится к численным методам приближённого поиска.

После завершения алгоритма возникает естественный вопрос: какую именно точку брать в качестве приближённого значения точки минимума? Поскольку в конце мы имеем малый интервал \( [a_k,b_k] \), внутри которого находится искомая точка, то на практике чаще всего берут середину этого интервала:

\[
x^* \approx \frac{a_k+b_k}{2}.
\]

Тогда приближённое минимальное значение функции вычисляют так:

\[
f_{\min}\approx f\left(\frac{a_k+b_k}{2}\right).
\]

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

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

Метод Фибоначчи: Практическое Применение Шаг за Шагом

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

Пример 1. Найти минимум функции \( f(x)=(x-2)^2+1 \) на отрезке \( [a,b]=[1,3] \) с точностью \( \varepsilon=0.1 \), используя метод Фибоначчи

Рассмотрим функцию \( f(x)=(x-2)^2+1 \) на отрезке \( [1,3] \). На этом промежутке она является унимодальной, потому что имеет только один минимум при \( x=2 \). Следовательно, сравнение значений функции в двух внутренних точках действительно позволяет безопасно сужать интервал поиска.

Сначала определим, какое число Фибоначчи нужно взять. Имеем

\[
\frac{b-a}{\varepsilon}=\frac{3-1}{0.1}=20.
\]

Последовательность чисел Фибоначчи имеет вид

\[
F_1=1,\quad F_2=1,\quad F_3=2,\quad F_4=3,\quad F_5=5,\quad F_6=8,\quad F_7=13,\quad F_8=21.
\]

Наименьшее число, которое удовлетворяет условию

\[
F_n\geq \frac{b-a}{\varepsilon},
\]

— это \( F_8=21 \). Итак, начинаем с интервала

\[
[a_0,b_0]=[1,3].
\]

Строим две внутренние точки:

\[
\begin{gathered}
x_1^{(0)}=a_0+\frac{F_6}{F_8}\cdot (b_0-a_0)=1+\frac{8}{21}\cdot 2=1.762,
\\[6pt]
x_2^{(0)}=a_0+\frac{F_7}{F_8}\cdot (b_0-a_0)=1+\frac{13}{21}\cdot 2=2.238.
\end{gathered}
\]

Вычисляем значения функции:

\[
\begin{gathered}
f\left(x_1^{(0)}\right)=(1.762-2)^2+1\approx 1.057,
\\[6pt]
f\left(x_2^{(0)}\right)=(2.238-2)^2+1\approx 1.057.
\end{gathered}
\]

Получаем равенство. В таком случае можно сузить интервал в любую из двух сторон. Для определённости возьмём

\[
[a_1,b_1]=[1,2.238].
\]

Здесь полезно обратить внимание на одну особенность именно этого примера. Функция \( f(x)=(x-2)^2+1 \) симметрична относительно точки \( x=2 \). Поэтому точки \( 1.762 \) и \( 2.238 \), которые одинаково удалены от \( 2 \), дают одинаковые значения функции.

Теперь важно заметить следующее: точка \( x_1^{(0)}=1.762 \) осталась внутри нового интервала. Следовательно, её удобно использовать повторно, и значение \( f(1.762)\approx 1.057 \) уже не нужно вычислять ещё раз.

Для нового интервала \( [a_1,b_1]=[1,2.238] \) строим только одну новую точку:

\[
x_1^{(1)}=a_1+\frac{F_5}{F_7}\cdot (b_1-a_1)=1+\frac{5}{13}\cdot (2.238-1)=1.476.
\]

Вторая точка уже известна с предыдущего шага:

\[
x_2^{(1)}=x_1^{(0)}=1.762.
\]

Теперь имеем

\[
\begin{gathered}
f\left(x_1^{(1)}\right)=(1.476-2)^2+1\approx 1.275,
\\[6pt]
f\left(x_2^{(1)}\right)=f(1.762)\approx 1.057.
\end{gathered}
\]

Поскольку \( f \left(x_1^{(1)}\right)>f \left(x_2^{(1)}\right) \), минимум лежит правее точки \( x_1^{(1)} \). Поэтому берём новый интервал

\[
[a_2,b_2]=[1.476,2.238].
\]

Для интервала \( [a_2,b_2] \) точку \( x_1^{(2)}=x_2^{(1)}=1.762 \) используют повторно. Новую точку находим так:

\[
x_2^{(2)}=a_2+\frac{F_5}{F_6}\cdot (b_2-a_2)=1.476+\frac{5}{8}\cdot (2.238-1.476)=1.952.
\]

Вычисляем

\[
\begin{gathered}
f\left(x_1^{(2)}\right)=f(1.762)\approx 1.057,
\\[6pt]
f\left(x_2^{(2)}\right)=(1.952-2)^2+1\approx 1.002.
\end{gathered}
\]

Поскольку \( f \left(x_1^{(2)}\right)>f \left(x_2^{(2)}\right) \), получаем новый интервал

\[
[a_3,b_3]=[1.762,2.238].
\]

Переходим дальше. Точка \( x_1^{(3)}=x_2^{(2)}=1.952 \) уже известна, поэтому её значение функции повторно не вычисляем. Новую точку находим по формуле

\[
x_2^{(3)}=a_3+\frac{F_4}{F_5}\cdot (b_3-a_3)=1.762+\frac{3}{5}\cdot (2.238-1.762)=2.048.
\]

Итак,

\[
\begin{gathered}
f\left(x_1^{(3)}\right)=f(1.952)\approx 1.002,
\\[6pt]
f\left(x_2^{(3)}\right)=(2.048-2)^2+1\approx 1.002.
\end{gathered}
\]

Получаем равенство. Как и раньше, можно сузить интервал в любую сторону. Возьмём, например,

\[
[a_4,b_4]=[1.762,2.048].
\]

Теперь для интервала \( [a_4,b_4] \) имеем \( x_2^{(4)}=x_1^{(3)}=1.952 \), а новую точку вычисляем так:

\[
x_1^{(4)}=a_4+\frac{F_2}{F_4}\cdot (b_4-a_4)=1.762+\frac{1}{3}\cdot (2.048-1.762)=1.857.
\]

Тогда

\[
\begin{gathered}
f\left(x_1^{(4)}\right)=(1.857-2)^2+1\approx 1.020,
\\[6pt]
f\left(x_2^{(4)}\right)=f(1.952)\approx 1.002.
\end{gathered}
\]

Поскольку \( f\left(x_1^{(4)}\right)>f\left(x_2^{(4)}\right) \), берём новый интервал

\[
[a_5,b_5]=[1.857,2.048].
\]

Теперь длина интервала равна

\[
b_5-a_5=2.048-1.857=0.191.
\]

Это всё ещё больше, чем \( 0.1 \), поэтому делаем ещё один шаг. На завершающем этапе в качестве приближённого значения точки минимума берём середину последнего достаточно малого интервала. Для наглядности можно сначала сузить интервал до

\[
[a_6,b_6]=[1.952,2.048],
\]

поскольку точка минимума находится внутри него. Его длина равна

\[
b_6-a_6=2.048-1.952=0.096<0.1.
\]

Следовательно, условие точности выполнено.

Теперь в качестве приближённого значения точки минимума берём середину последнего интервала:

\[
x^*\approx \frac{a_6+b_6}{2}=\frac{1.952+2.048}{2}=2.
\]

Тогда приближённое минимальное значение функции равно

\[
f_{\min}\approx f(2)=(2-2)^2+1=1.
\]

Итак, методом Фибоначчи мы получили

\[
x^*\approx 2,
\qquad
f_{\min}\approx 1.
\]

Это полностью согласуется с точным результатом, ведь для функции \( f(x)=(x-2)^2+1 \) минимум действительно достигается при \( x=2 \), а минимальное значение равно \( 1 \). Кроме того, на этом примере хорошо видна ещё одна важная особенность метода: после каждого сужения интервала одна из точек и значение функции в ней сохраняются, а значит, последующие вычисления выполняются экономнее.

Следующие Шаги: Что Стоит Прочитать Дальше

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

Метод дихотомии: Последовательное сужение интервала — В этой статье пойдёт речь о простом способе поиска минимума через деление интервала и сравнение значений функции в близких точках.
Равномерный поиск: Первый шаг к минимизации — В этой теме будет показано, как находить минимум функции через последовательный просмотр точек на отрезке с одинаковым шагом.
Метод Ньютона: Быстрый поиск точки минимума — В этой статье будет показано, как использовать производные для более быстрого приближения к точке минимума функции одной переменной.

Метод Фибоначчи в Коде: Напишите Собственный Поиск Минимума

Теперь посмотрите на блок-схему ниже не только как на иллюстрацию, но и как на готовую основу для небольшого учебного проекта. Почему бы не использовать её как понятную подсказку и не написать на любимом языке программирования компактную программу, которая определяет минимальное значение унимодальной функции методом Фибоначчи? Такая работа хорошо показывает, как теоретический материал переходит в реальное вычисление, с которым можно экспериментировать на разных функциях и отрезках. Кроме того, это отличная возможность проверить себя и понять, насколько уверенно вы ориентируетесь в логике метода не только в записях и формулах, но и в программной реализации.

Метод Фибоначчи: От Основной Идеи к Практическому Примеру