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

Расположим такое симметричное расположение точек Х1 и Х2 на отрезке [а,в], при котором одна из них становится пробной точкой на новом отрезке, полученном после исключения части исходного отрезка. Использование таких точек позволяет на каждой итерации метода исключения отрезка, кроме первой, ограничиться определением только одного значения f(x), т.к. другое значение уже найдено на одной из предыдущих итераций.

Найдем точки Х1 и Х2, обладающие указанным свойством.

Рассмотрим сначала отрезок [0,1] и для определенности предположим, что при его уменьшении исключается правая часть этого отрезка.

Пусть Х2=τ, тогда симметрично распложающаяся точка Х1=1-τ.

Пробная точка Х1 отрезка [0,1] перейдет в пробную точку Х=1-τ нового отрезка [0;τ]. Чтобы точки Х2=τ и Х=1-τ делили отрезки [0,1] и [0;τ] в одном и том же отношении, должно выполняться равенство =или =1-, откуда находим положительное значение .

Для произвольного отрезка [а,в] выражения для пробных точек имеют вид:

Х1=а+*(в-а); Х2=а+*(в-а) [1]

Замечания:

1. Точки Х1 и Х2 из [1] обладают следующим свойством: каждая из них делит [а,в] на две равные части так, что отношение длины всего отрезка к длине большей части равно отношению длин большей и меньшей частей отрезка.

Точки с таким свойством называю точками золотого сечения [а,в].

2. На каждой итерации исключения отрезков с пробными точками [1] одна из них переходит на следующий отрезок и значение f(x) в этой точке вычислять не следует.

Если новым отрезком становится [а;Х2], то на него переходит пробная точка =Х1 исходного отрезка, становясь его второй пробной точкой (=Х1).

В случае перехода к [Х1;в] пробная точка =Х2 исходного отрезка становится первой пробной точкой отрезка [Х1;в].

3. Легко проверить, что Х1=а+в-Х2 и Х2=а+в-Х1. Поэтому на каждой итерации золотого сечения недостающую пробную точку нового отрезка можно найти по перешедшей на него пробной точке с помощью сложения и вычитания, не используя [1].

4. В конце вычислений по методу золотого сечения в качестве приближенного значения Х* можно взять середину последнего из полученных отрезков =.

Точность Е n определения точки Х* после n-итераций находится из равенства:

Е n==**(в-а) [2]

а условием окончания поиска точки Х* с точностью Е служит первенство Е n Е.

Алгоритм метода золотого сечения:

ШАГ1:

Найти Х1 и Х2 по формуле [1]. Вычислить f(x1) и f(x2). Положить =, Е n=.

ШАГ2:

Проверка на окончание поиска: если Е n> Е, то перейти к шагу 3, иначе к шагу 4.

ШАГ3:

Переход к новому отрезку и новым пробным точкам. Если f(x1)f(x2), то положить в=Х2, Х2=Х1, f(x2)=f(x1), Х1=в-(в-а) и вычислить f(x1), иначе – положить а=Х1, Х1=Х2, f(x1)=f(x2), Х2=а+(в-а) и вычислить f(x2). Положить Е n= Е n и перейти к шагу2.

ШАГ4:

Окончание поиска: положить Х*≈=, f*≈f().

Дата добавления: 2014-01-07