Метод золотого сечения: различия между версиями
(отмена правки 121188024 участника 176.193.252.92 (обс.)) |
Patarakin (обсуждение | вклад) |
||
(не показана 1 промежуточная версия этого же участника) | |||
Строка 3: | Строка 3: | ||
== Описание метода == | == Описание метода == | ||
Пусть задана [[Функция (программирование)|функция]] <math>f(x):\;[a,\;b]\to\mathbb{R},\;f(x)\in\mathrm{C}([a,\;b])</math>. Тогда для того, чтобы найти неопределённое значение этой функции на заданном отрезке, отвечающее критерию поиска (пусть это будет [[минимум]]), рассматриваемый отрезок делится в пропорции золотого сечения в обоих направлениях, то есть выбираются две точки <math>x_1</math> и <math>x_2</math> такие, что: | Пусть задана [[Функция (программирование)|функция]] <math>f(x):\;[a,\;b]\to\mathbb{R},\;f(x)\in\mathrm{C}([a,\;b])</math>. Тогда для того, чтобы найти неопределённое значение этой функции на заданном отрезке, отвечающее критерию поиска (пусть это будет [[минимум]]), рассматриваемый отрезок делится в пропорции золотого сечения в обоих направлениях, то есть выбираются две точки <math>x_1</math> и <math>x_2</math> такие, что: | ||
Таким образом: <br /> | Таким образом: <br /> | ||
Строка 67: | Строка 66: | ||
#* Иначе возврат к шагу 2. | #* Иначе возврат к шагу 2. | ||
== См. также == | == См. также == | ||
Строка 82: | Строка 72: | ||
* [[Числа Фибоначчи]] | * [[Числа Фибоначчи]] | ||
[[Категория:Алгоритмы поиска]] | [[Категория:Алгоритмы поиска]] | ||
Текущая версия на 21:05, 19 октября 2022
Метод золотого сечения — метод поиска экстремума действительной функции одной переменной на заданном отрезке. В основе метода лежит принцип деления отрезка в пропорциях золотого сечения. Является одним из простейших вычислительных методов решения задач оптимизации. Впервые представлен Джеком Кифером в 1953 году.
Описание метода
Пусть задана функция [math]\displaystyle{ f(x):\;[a,\;b]\to\mathbb{R},\;f(x)\in\mathrm{C}([a,\;b]) }[/math]. Тогда для того, чтобы найти неопределённое значение этой функции на заданном отрезке, отвечающее критерию поиска (пусть это будет минимум), рассматриваемый отрезок делится в пропорции золотого сечения в обоих направлениях, то есть выбираются две точки [math]\displaystyle{ x_1 }[/math] и [math]\displaystyle{ x_2 }[/math] такие, что:
Таким образом:
- [math]\displaystyle{ \begin{array}{ccc} x_1 &=& b-\frac{(b-a)}{\Phi}\\ x_2 &=& a+\frac{(b-a)}{\Phi} \end{array} }[/math]
То есть точка [math]\displaystyle{ x_1 }[/math] делит отрезок [math]\displaystyle{ [a,\;x_2] }[/math] в отношении золотого сечения. Аналогично [math]\displaystyle{ x_2 }[/math] делит отрезок [math]\displaystyle{ [x_1,\;b] }[/math] в той же пропорции. Это свойство и используется для построения итеративного процесса.
Алгоритм
- На первой итерации заданный отрезок делится двумя симметричными относительно его центра точками и рассчитываются значения в этих точках.
- После чего тот из концов отрезка, к которому среди двух вновь поставленных точек ближе оказалась та, значение в которой максимально (для случая поиска минимума), отбрасывают.
- На следующей итерации в силу показанного выше свойства золотого сечения уже надо искать всего одну новую точку.
- Процедура продолжается до тех пор, пока не будет достигнута заданная точность.
Формализация
- Шаг 1. Задаются начальные границы отрезка [math]\displaystyle{ a,\;b }[/math] и точность [math]\displaystyle{ \varepsilon }[/math].
- Шаг 2. Рассчитывают начальные точки деления: [math]\displaystyle{ x_1 = b-\frac{(b-a)}{\Phi},\quad x_2 = a+\frac{(b-a)}{\Phi} }[/math] и значения в них целевой функции: [math]\displaystyle{ y_1=f(x_1),\;y_2=f(x_2) }[/math].
- Если [math]\displaystyle{ y_1 \ge y_2 }[/math] (для поиска max изменить неравенство на [math]\displaystyle{ y_1 \le y_2 }[/math]), то [math]\displaystyle{ a=x_1 }[/math]
- Иначе [math]\displaystyle{ b=x_2 }[/math].
- Шаг 3.
- Если [math]\displaystyle{ |b-a|\lt \varepsilon }[/math], то [math]\displaystyle{ x=\frac{a+b}{2} }[/math] и останов.
- Иначе возврат к шагу 2.
Алгоритм взят из книги Мэтьюза и Финка «Численные методы. Использование MATLAB».
Реализация данного алгоритма на языке F#, в которой значения целевой функции используются повторно:
let phi = 0.5 * (1.0 + sqrt 5.0)
let minimize f eps a b =
let rec min_rec f eps a b fx1 fx2 =
if b - a < eps then
0.5 * (a + b)
else
let t = (b - a) / phi
let x1, x2 = b - t, a + t
let fx1 = match fx1 with Some v -> v | None -> f x1
let fx2 = match fx2 with Some v -> v | None -> f x2
if fx1 >= fx2 then
min_rec f eps x1 b (Some fx2) None
else
min_rec f eps a x2 None (Some fx1)
min_rec f eps (min a b) (max a b) None None
// Примеры вызова:
minimize cos 1e-6 0.0 6.28 |> printfn "%.10g"
// = 3.141592794; функция f вызвана 34 раза.
minimize (fun x -> (x - 1.0)**2.0) 1e-6 0.0 10.0 |> printfn "%.10g"
// = 1.000000145; функция f вызвана 35 раз.
Метод чисел Фибоначчи
В силу того, что в асимптотике [math]\displaystyle{ \Phi=\lim_{n\to\infty}\frac{F_{n+1}}{F_{n}} }[/math], метод золотого сечения может быть трансформирован в так называемый метод чисел Фибоначчи. Однако при этом в силу свойств чисел Фибоначчи количество итераций строго ограничено. Это удобно, если сразу задано количество возможных обращений к функции.
Алгоритм
- Шаг 1. Задаются начальные границы отрезка [math]\displaystyle{ a,\;b }[/math] и число итераций [math]\displaystyle{ n }[/math], рассчитывают начальные точки деления: [math]\displaystyle{ x_1 = a+(b-a)\frac{F_{n-2}}{F_n},\quad x_2 = a+(b-a)\frac{F_{n-1}}{F_n} }[/math] и значения в них целевой функции: [math]\displaystyle{ y_1=f(x_1),\;y_2=f(x_2) }[/math].
- Шаг 2. [math]\displaystyle{ n=n-1 }[/math].
- Если [math]\displaystyle{ y_1\gt y_2 }[/math], то [math]\displaystyle{ a=x_1,\; x_1=x_2,\; x_2=b-(x_1-a),\;y_1=y_2,\;y_2=f(x_2) }[/math].
- Иначе [math]\displaystyle{ b=x_2,\;x_2=x_1,\;x_1=a+(b-x_2),\;y_2=y_1,\;y_1=f(x_1) }[/math].
- Шаг 3.
- Если [math]\displaystyle{ n=1 }[/math], то [math]\displaystyle{ x=\frac{x_1+x_2}{2} }[/math] и остановка.
- Иначе возврат к шагу 2.