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

                                            31
1. Проверим условие f ′(0) f ′(1) <0 .                     Условие выполнено.
2. Положим k =0 .
3. Вычислим точку y 0 =0,216; f ′( y 0 ) =−0,766 .
4. Так как f ′( y 0 ) >ε =0,05 , то переходим к шагу 3.
5. Поскольку f ′( y 0 ) <0 положим a1 = y 0 , b1 =b0 , f ′( a1 ) =−0,766 .
6. Присваиваем k =1 и переходим к шагу 2.
7. Вычислим точку y1 =0,352; f ′( y1 ) =−0,528 .
8. Так как f ′( y1 ) >ε =0,05 , то переходим к шагу 3.
9. Поскольку f ′( y1 ) <0 положим a 2 = y1 , b2 =b1 , f ′(a 2 ) =−0,528 .
10. Присваиваем k =2 и переходим к шагу 2.
          На 6-й итерации получаем промежуток с концами a 5 =0,504, b5 =1.
На данном промежутке метод генерирует точку y 5 =0,516 , в которой
 f ′( y 5 ) =−0,046 . Алгоритм завершает работу, поскольку достигнута
требуемая точность f ′( y 5 ) <ε =0,05 .
                                              Метод Ньютона
          Метод Ньютона является последовательным методом второго порядка.
Предполагается, что функция f (x) дважды дифференцируема, причем
 f ′′( x) >0 (это гарантирует выпуклость функции f (x) ). В этом случае корень
уравнения f ′( x) =0 можно приближенно искать методом касательных. В
отличие от предыдущих методов, метод Ньютона не относится к методу
сокращения промежутков. Для начала работы метода вместо задания
начального промежутка неопределенности требуется задание начальной
точки x 0 , в которой вычисляется f ′( x 0 ) и f ′′( x 0 ) . В процессе работы
метода генерируется последовательность x k , k =1,2... В очередной точке x k
строится линейная аппроксимация функции f ′(x) (касательная к графику
 f ′(x) ). Точка, в которой линейная аппроксимирующая функция обращается
в нуль, используется в качестве следующего приближения x k +1 .
          Уравнение касательной к графику f ′(x) в точке x k имеет вид
 y = f ′( x k ) + f ′′( x k )( x −x k ) , поэтому точка x k +1 , найденная из условия y =0 ,
                                                 f ′( x k )
определяется формулой x k +1 =x k −                          .
                                                 f ′′( x k )
          Процедура нахождения точек x k продолжается до тех пор, пока не
будет достигнута требуемая точность, т.е. f ′( x k ) ≤ε .
                                                 Алгоритм
      Шаг 1. Задать начальную точку x 0 , ε >0 - требуемую точность.
Положить k =0 .
      Шаг 2. Вычислить f ′( x k ) .
   Шаг 3. Если f ′( x k ) ≤ε , то положить x * =x k , f ( x * ) = f ( x k ) и поиск
завершить, иначе перейти к шагу 4.