Методы оптимизации. Азарнова Т.В - 26 стр.

                                              28
таким образом, чтобы одна из них использовалась с той же целью и на
следующем уже сокращенном промежутке. Такое правило выбора точек
приводит к тому, что число вычислений функции сокращается вдвое и одна
итерация требует расчета только одного нового значения функции. Такими
свойствами обладают точки, называемые точками золотого сечения. Говорят,
что точка производит золотое сечение промежутка, если отношение длины
всего промежутка к длине большей части равно отношению длин большей
части к меньшей.
        В методе золотого сечения на промежутке [ a, b] симметрично
относительно его концов выбираются точки y и z , такие что
                                     b −a b − y b −a z −a
                                             =        =     =
                                     b − y y −a z −a b −z
При этом точка y производит золотое сечение промежутка [ a, z ] , а точка z -
промежутка [ y, b] .
                                                 Алгоритм
    Шаг 1. Задать начальный промежуток неопределенности L0 =[a 0 , b0 ] и
ε >0 - требуемую точность. Положить k =0 .
                                                         3− 5
    Шаг         2.     Вычислить:             y 0 =a 0 +        (b0 −a 0 ), z 0 =a 0 +b0 − y 0 ,
                                                          2
3− 5
         =0,38196 .
     2
    Шаг 3. Вычислить f ( y k ), f ( z k ) .
    Шаг 4. Сравнить f ( y k ) и f ( z k ) :
    а)    если       f ( yk ) ≤ f (zk ) ,     то     положить       a k +1 =a k , bk +1 =z k  и
 y k +1 =a k +1 +bk +1 − y k , z k +1 = y k . Перейти к шагу 5.
    б) если f ( y k ) > f ( z k ) , то положить a k +1 = y k , bk +1 =bk и y k +1 =z k ,
z k +1 =a k +1 +bk +1 − y k . Перейти к шагу 5.
                                                            � k +1, k ≠0
    Шаг 5. Вычислить L N = a k +1 −bk +1 , N =�                                   и проверить
                                                             � 2 ,       k =0
условие окончания. Если L N ≤ε , то процесс поиска завершается и
x * ∈[ a k +1 , bk +1 ] . В качестве приближенного решения можно взять середину
                                      a   +bk +1
последнего промежутка x * = k +1                 . Если L N >ε , положить k =k +1 и
                                          2
перейти к шагу 3.
       Для метода золотого сечения характеристика относительного
уменьшения промежутка неопределенности равна R ( N ) =(0,618) N −1 , где N -
количество вычислений функции.
                                                           127 2 61
       Пример 3. Найти минимум функции f ( x) =               x − x +2 методом
                                                            4       4
золотого сечения.