Метод золотого сечения - История изменений

Patarakin в 18:05, 19 октября 2022

2022-10-19T18:05:11Z

← Предыдущая версия		Версия от 21:05, 19 октября 2022
Строка 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> такие, что:
	~~[[Файл:Golden-section search.png\|frame\|Иллюстрация выбора промежуточных точек метода золотого сечения.]]~~
	:<math>\frac{b-a}{b-x_1}=\frac{b-a}{x_2-a}=\Phi=\frac{1+\sqrt{5}}{2}=1.618\ldots</math>, где <math>\Phi</math> — пропорция [[золотое сечение\|золотого сечения]]. <br />

	Таким образом: <br />		Таким образом: <br />
Строка 67:		Строка 66:
	#* Иначе возврат к шагу 2.		#* Иначе возврат к шагу 2.

	~~== Литература ==~~
	# {{книга\|автор = Акулич И. Л.\|заглавие = Математическое программирование в примерах и задачах: Учеб. пособие для студентов эконом. спец. вузов\|оригинал = \|ссылка = \|издание = \|место = М.\|издательство = Высш. шк.\|год = 1986\|страницы =\|isbn = }}
	# {{книга\|автор = Гилл Ф., Мюррей У., Райт М.\|заглавие = Практическая оптимизация. Пер. с англ\|оригинал = \|ссылка = \|издание =\|место = М.\|издательство = Мир\|год = 1985\|страницы =\|isbn = }}
	# {{книга\|автор = Коршунов Ю. М.\|заглавие = Математические основы кибернетики\|оригинал = \|ссылка = \|издание =\|место= М.\|издательство = Энергоатомиздат\|год = 1972\|страницы =\|isbn = }}
	# {{книга\|автор = Максимов Ю. А., Филлиповская Е. А.\|заглавие = Алгоритмы решения задач нелинейного программирования\|оригинал = \|ссылка = \|издание =\|место = М.\|издательство = МИФИ\|год = 1982\|страницы =\|isbn = }}
	# {{книга\|автор = Максимов Ю. А.\|заглавие = Алгоритмы линейного и дискретного программирования\|оригинал = \|ссылка = \|издание = \|место = М.\|издательство = МИФИ\|год = 1980\|страницы =\|isbn = }}
	# {{книга\|автор = Корн Г., Корн Т.\|заглавие = Справочник по математике для научных работников и инженеров\|оригинал = \|ссылка =
	~~\|издание = \|место = М.\|издательство = Наука\|год = 1970\|страницы = 575—576\|isbn = }}~~
	# {{книга \|автор=Корн Г., Корн Т. \|заглавие=Справочник по математике для научных работников и инженеров \|место=М. \|издательство=Наука \|год=1973 \|часть= \|страницы=832 с илл. \|ссылка=http://eqworld.ipmnet.ru/ru/library/books/Korn1973ru.djvu}}
	# {{книга\|автор = Джон Г. Мэтьюз, Куртис Д. Финк.\|заглавие = Численные методы. Использование MATLAB\|оригинал = \|ссылка = \|издание = 3-е издание \|место = М., СПб.\|издательство = Вильямс\|год = 2001\|страницы = 716\|isbn = }}

	== См. также ==		== См. также ==
Строка 82:		Строка 72:
	* [[Числа Фибоначчи]]		* [[Числа Фибоначчи]]

	~~{{Методы оптимизации}}{{Золотое сечение}}~~
	[[Категория:Алгоритмы поиска]]		[[Категория:Алгоритмы поиска]]
	~~[[Категория:Алгоритмы оптимизации]]~~
	~~[[Категория:Золотое сечение]]~~

Patarakin: 1 версия импортирована

2022-10-19T17:54:59Z

1 версия импортирована

← Предыдущая версия	Версия от 20:54, 19 октября 2022
(нет различий)

195.209.246.233: отмена правки 121188024 участника 176.193.252.92 (обс.)

2022-04-05T08:24:53Z

отмена правки 121188024 участника 176.193.252.92 (обс.)

Новая страница

'''Метод золотого сечения''' — метод поиска [[экстремум]]а действительной функции одной переменной на заданном отрезке. В основе метода лежит принцип деления отрезка в пропорциях [[золотое сечение|золотого сечения]]. Является одним из простейших [[Вычислительные методы|вычислительных методов]] решения [[задача оптимизации|задач оптимизации]]. Впервые представлен [[Кифер, Джек|Джеком Кифером]] в 1953 году.

== Описание метода ==
Пусть задана [[Функция (программирование)|функция]] <math>f(x):\;[a,\;b]\to\mathbb{R},\;f(x)\in\mathrm{C}([a,\;b])</math>. Тогда для того, чтобы найти неопределённое значение этой функции на заданном отрезке, отвечающее критерию поиска (пусть это будет [[минимум]]), рассматриваемый отрезок делится в пропорции золотого сечения в обоих направлениях, то есть выбираются две точки <math>x_1</math> и <math>x_2</math> такие, что:
[[Файл:Golden-section search.png|frame|Иллюстрация выбора промежуточных точек метода золотого сечения.]]
:<math>\frac{b-a}{b-x_1}=\frac{b-a}{x_2-a}=\Phi=\frac{1+\sqrt{5}}{2}=1.618\ldots</math>, где <math>\Phi</math> — пропорция [[золотое сечение|золотого сечения]]. <br />

Таким образом: <br />
:<math>\begin{array}{ccc}
x_1 &=& b-\frac{(b-a)}{\Phi}\\
x_2 &=& a+\frac{(b-a)}{\Phi}
\end{array}</math>

То есть точка <math>x_1</math> делит отрезок <math>[a,\;x_2]</math> в отношении золотого сечения. Аналогично <math>x_2</math> делит отрезок <math>[x_1,\;b]</math> в той же пропорции. Это свойство и используется для построения итеративного процесса.

=== Алгоритм ===
# На первой итерации заданный отрезок делится двумя симметричными относительно его центра точками и рассчитываются значения в этих точках.
# После чего тот из концов отрезка, к которому среди двух вновь поставленных точек ближе оказалась та, значение в которой максимально (для случая поиска [[минимум]]а), отбрасывают.
# На следующей итерации в силу показанного выше свойства золотого сечения уже надо искать всего одну новую точку.
# Процедура продолжается до тех пор, пока не будет достигнута заданная точность.

=== Формализация ===
# '''Шаг 1.''' Задаются начальные границы отрезка <math>a,\;b</math> и точность <math>\varepsilon</math>.
# '''Шаг 2.''' Рассчитывают начальные точки деления: <math>x_1 = b-\frac{(b-a)}{\Phi},\quad x_2 = a+\frac{(b-a)}{\Phi}</math> и значения в них [[целевая функция|целевой функции]]: <math>y_1=f(x_1),\;y_2=f(x_2)</math>.
#* Если <math>y_1 \ge y_2</math> (для поиска max изменить неравенство на <math>y_1 \le y_2</math>), то <math> a=x_1</math>
#* Иначе <math>b=x_2</math>.
# '''Шаг 3.'''
#* Если <math>|b-a|<\varepsilon</math>, то <math>x=\frac{a+b}{2}</math> и останов.
#* Иначе возврат к шагу 2.

Алгоритм взят из книги Мэтьюза и Финка «Численные методы. Использование MATLAB».

Реализация данного алгоритма на языке [[F Sharp|F#]], в которой значения целевой функции используются повторно:<syntaxhighlight lang="fsharp">
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 раз.
</syntaxhighlight>

== Метод чисел Фибоначчи ==
В силу того, что в асимптотике <math>\Phi=\lim_{n\to\infty}\frac{F_{n+1}}{F_{n}}</math>, метод золотого сечения может быть трансформирован в так называемый метод [[числа Фибоначчи|чисел Фибоначчи]]. Однако при этом в силу свойств чисел Фибоначчи количество итераций строго ограничено. Это удобно, если сразу задано количество возможных обращений к функции.

=== Алгоритм ===
# '''Шаг 1.''' Задаются начальные границы отрезка <math>a,\;b</math> и число итераций <math>n</math>, рассчитывают начальные точки деления: <math>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>y_1=f(x_1),\;y_2=f(x_2)</math>.
# '''Шаг 2.''' <math>n=n-1</math>.
#* Если <math>y_1>y_2</math>, то <math>a=x_1,\; x_1=x_2,\; x_2=b-(x_1-a),\;y_1=y_2,\;y_2=f(x_2)</math>.
#* Иначе <math>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>n=1</math>, то <math>x=\frac{x_1+x_2}{2}</math> и остановка.
#* Иначе возврат к шагу 2.

== Литература ==
# {{книга|автор = Акулич И. Л.|заглавие = Математическое программирование в примерах и задачах: Учеб. пособие для студентов эконом. спец. вузов|оригинал = |ссылка = |издание = |место = М.|издательство = Высш. шк.|год = 1986|страницы =|isbn = }}
# {{книга|автор = Гилл Ф., Мюррей У., Райт М.|заглавие = Практическая оптимизация. Пер. с англ|оригинал = |ссылка = |издание =|место = М.|издательство = Мир|год = 1985|страницы =|isbn = }}
# {{книга|автор = Коршунов Ю. М.|заглавие = Математические основы кибернетики|оригинал = |ссылка = |издание =|место= М.|издательство = Энергоатомиздат|год = 1972|страницы =|isbn = }}
# {{книга|автор = Максимов Ю. А., Филлиповская Е. А.|заглавие = Алгоритмы решения задач нелинейного программирования|оригинал = |ссылка = |издание =|место = М.|издательство = МИФИ|год = 1982|страницы =|isbn = }}
# {{книга|автор = Максимов Ю. А.|заглавие = Алгоритмы линейного и дискретного программирования|оригинал = |ссылка = |издание = |место = М.|издательство = МИФИ|год = 1980|страницы =|isbn = }}
# {{книга|автор = Корн Г., Корн Т.|заглавие = Справочник по математике для научных работников и инженеров|оригинал = |ссылка =
|издание = |место = М.|издательство = Наука|год = 1970|страницы = 575—576|isbn = }}
# {{книга |автор=Корн Г., Корн Т. |заглавие=Справочник по математике для научных работников и инженеров |место=М. |издательство=Наука |год=1973 |часть= |страницы=832 с илл. |ссылка=http://eqworld.ipmnet.ru/ru/library/books/Korn1973ru.djvu}}
# {{книга|автор = Джон Г. Мэтьюз, Куртис Д. Финк.|заглавие = Численные методы. Использование MATLAB|оригинал = |ссылка = |издание = 3-е издание |место = М., СПб.|издательство = Вильямс|год = 2001|страницы = 716|isbn = }}

== См. также ==
* [[Золотое сечение]]
* [[Числа Фибоначчи]]

{{Методы оптимизации}}{{Золотое сечение}}
[[Категория:Алгоритмы поиска]]
[[Категория:Алгоритмы оптимизации]]
[[Категория:Золотое сечение]]