Метод золотого сечения

В основу метода положено разбиение отрезка неопределенности [a;b] в соотношении золотого сечения, такого, что отношение длины его большей части ко всей длине отрезка равно отношению длины его меньшей части к длине его большей части:

l

l₂ l₁

Положим l =1, тогда l₂²= 1 - l₂, а l₂² + l₂ -1= 0, откуда

где k₁, k₂ - коэффициенты золотого сечения.

В методе золотого сечения каждая точка (х₁ и х₂)осуществляет золотое сечение отрезка (рис. 6.6.3-1).

Рис. 6.6.3-1

или

Нетрудно проверить, что точка х₁ осуществляет золотое сечение не только отрезка [a;b], но и отрезка [a;х₂]. Точно так же точка х₂ осуществляет золотое сечение не только отрезка [a;b], но и отрезка [х₁;b]. Это приводит к тому, что значение целевой функции на каждой итерации (кроме первой) вычисляется один раз.

После каждой итерации длина отрезка неопределенности сокращается в 1.618 раза. Длина конечного отрезка неопределенности D_n = 0.618ⁿD₀, где D₀= (b-a) – начальная длина отрезка.

Условие окончания процесса итераций D_n e. Отсюда можно найти количество итераций, необходимое для достижения точки минимума:

отсюда логарифмируя, получим

Пример 6.6.3-1. Пусть минимум функции f(x) = x³ – x + e^-x отделен на отрезке [0;1]. Определить количества итераций и конечные длины отрезков неопределенности, необходимые для достижения заданных точностей e=0.1 и e=0.01.

N	a	b	x1	x2	f(x1)	f(x2)	Dn
			0.38196	0.61803	0.35628	0.15704	0.61803
	0.38196		0.61803	0.76393	0.15704	0.14772	0.382
	0.61803		0.76393	0.85410	0.14772	0.19462	0.236
	0.61803	0.85410	0.70820	0.76393	0.13953	0.14772	0.146
	0.61803	0.76393	0.67376	0.70820	0.14188	0.13953	0.090

При e = 0.1 x*=0.718847, f(x*)=0.139925.

При e = 0.01 x*=0.704139, f(x*)=0.139516.

Дата добавления: 2014-12-27