ФедотовА.А. Численные методы интегрирования .. 2015 (864364), страница 8

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 8)

5.1):а) если F ( x1 )  F ( x2 ), то x *  [ x1 , b];б) если F ( x1 )  F ( x2 ), то x*  [a , x2 ];в) если F ( x1 )  F ( x2 ), то x*  [ x1 , x2 ] .Пользуясь утверждением, перейдем теперь к конкретным методам одномерной оптимизации.61Рис. 5.1. Сужение интервала неопределенности для унимодальной функции:а — F ( x1 )  F ( x 2 ); б — F ( x1 )  F ( x 2 ); в — F ( x1 )  F ( x 2 )Метод дихотомий (половинного деления).

В условиях, когдана k-м шаге проводятся два опыта, аргументы x1,k и x2,k должнывыбираться на расстоянии δ 2 справа и слева от середины интервала:a b a b x1,k  k k  ; x2,k  k k  ,2222где ak , bk — границы интервала неопределенности; ck  ak  bk 2(рис. 5.2).Рис. 5.2. Метод дихотомийЕсли F ( x1, k ) > F ( x2,k ), то ak 1  x1, k , bk 1  bk ;если F ( x1, k ) < F ( x2,k ), то ak 1  ak , bk 1  x2,k ;если F ( x1, k ) = F ( x2,k ), то ak 1  x1, k , bk 1  x2, k .Оценим (сверху) длину интервала неопределенности l(n) послеn шагов:ba   (b  a)  21    21 ;22l (2)  (l (1)  ) 2  (b  a)  22    22    21;l (3)  (l (2)  ) 2  (b  a)  23    23    22    21  (b  a)  23  (1  23 );.................................................................................l (n)  (b  a)  2 n   (1  2 n ).l (1) 62Рассмотрим метод золотого сечения.Определение.

Говорят, что точка y k осуществляет золотое сечение отрезка [ak , bk ] (рис. 5.3), еслиbk  ak bk  yk.bk  yk yk  akРис. 5.3. Золотое сечение отрезка [ak , bk ]Другими словами, золотое сечение — это деление отрезка надве части таким образом, что большая его часть является среднимгеометрическим между всем отрезком и меньшей его частью.Термин «золотое сечение» ввел Леонардо да Винчи (конец XV в.).Золотое сечение или близкие ему пропорциональные отношения легли в основу композиционного построения многих произведений мирового искусства (главным образом, в архитектуре античности и Возрождения, например, капелла Пацци во Флоренции, архитекторФ. Брунеллески, XV в.).Вычислим, чему равно отношение длины большей части отрезка l k к длине всего отрезка:ll.l l  lОтсюдаl5 1 0,62.l25 1называется золотым сечением.2В методе золотого сечения делим интервал неопределенностина три части (рис. 5.4).

Точки x1,k и x2,k осуществляют золотоесечение отрезка [a k , bk ] :Число  x1, k  ak  (1  )(bk  ak );x2, k  bk  (1  )(bk  ak ).63Рис. 5.4. Пример золотого сечения отрезкаМожно показать, что точки x1,k и x2,k являются золотым сечением отрезков [ak , x2, k ] и [ x1, k , bk ] соответственно и, следовательно, одна из двух точек x1,k или x2,k используется и на следующемшаге, что уменьшает количество вычислений.Пример. Пусть F ( x )  ( x  1)2 . Несмотря на очевидность результата, будем сужать интервал неопределенности:a1  0; b1  3;x1,1  0  0, 38(3  0)  1,14; x2,1  3  0, 38(3  0)  1,86;F ( x1,1 )  0,142  0, 0196; F ( x2,1 )  0, 862  F ( x1,1 );a2  a1  0; b2  x2,1  1, 86;x1,2  a2  0, 38(1, 86  0)  0, 7128; x2,2  x1,1  1,14;F ( x1,2 )  0, 292  F ( x2,2 ).Следовательно, a3  x1,2  0, 7128; b3  b2  1, 86 и т.

д.5.2. Многомерная оптимизацияТребуется найтиmin F ( x1 , x2 , ..., xn ).x1 , x2 ,..., xnДля простоты рассуждений далее будем рассматривать функцию F ( x, y ) двух переменных.5.2.1. Метод покоординатного спускаВыберем начальное приближение ( x0 , y0 ) (рис. 5.5). Фиксируем значение координаты y  y0 , тогда F ( x, y ) будет зависетьтолько от переменной x, обозначим ее f1 ( x )  F ( x , y0 ).64Используя описанные выше методы одномерной оптимизации,найдем минимум функций одной переменной f1 ( x ) и обозначим егоx1 .

Мы сделали шаг из точки ( x0 , y0 ) в точку ( x1 , y0 ) по направлению, параллельному оси OX, на этом шаге значение функции уменьшилось. Затем из новой точки делаем спуск по направлению, параллельному оси OY, т. е. рассмотрим функцию f 2 ( y )  F ( x1 , y ),найдем ее минимум и обозначим его y1. Приход в точку ( x1 , y1 ) завершает цикл спусков. Будем повторять циклы.Утверждение. Если функция F ( x, y ) гладкая, то в некоторойокрестности минимума процесс спуска по координатам сходитсяк этому минимуму.Рис.

5.5. Метод покоординатногоспускаПример.(рис. 5.6);ПустьРис. 5.6. Пример нахождения минимума функции F ( x, y ) методомпокоординатного спускаF ( x, y )  4( x, y )2  ( x  y )2  5 x 2  6 xy  5 y 2x0  1; y0  1;f1 ( x )  5 x 2  6 x  5; f ( x1 )  10 x1  6  0; x1  0, 6;f 2 ( y )  x12  6( x1 ) y  5 y 2 ;f 2( y1 )  10 y1  6 x1  0; y1  0, 6 x1  0, 36и т. д.655.2.2.

Метод наискорейшего (градиентного) спускаВ этом методе следующее приближение отыскивается в видеx n 1  x n  n grad F ( x n ).Значение δn определяется из условияmin F  x n  n grad F ( x n )  ,nт. е. алгоритм состоит в последовательной минимизации функцииодной переменной n .Пример. Пусть F ( x1 , x2 )  x12  4 x22 (рис. 5.7);x10  2; x20  1;grad F ( x1 , x2 )  (2 x1 ,8 x2 );grad F (2,1)  (4,8); 2 4   2  4 0 x1 (0 )     0    .1 8   1  80 _Рис. 5.7. Метод наискорейшего (градиентного) спускаНайдемmin (),66где( 0 )  (2  40 )2  4(1  80 )2 ;( 0 )  2(2  40 )( 4)  8(1  80 )( 8)  0; 0 5.34Отсюдаx11 324; x12  1717и т. д.5.2.3. Метод сопряженных градиентовДо сих пор в итерационной процедуре в качестве направленияубывания функции F ( x ) мы использовали направление антиградиента: p k  grad F ( x k ).

Однако такой выбор направления невсегда бывает удачным. В частности, для плохо обусловленныхзадач минимизации направление антиградиента в точке x k можетзначительно отличаться от направления к точке минимума x  .В результате траектория приближения к точке минимума будетиметь зигзагообразный характер (см. рис. 5.7). Метод сопряженных градиентов лишен этого недостатка.Определение. Ненулевые векторы p1 , p 2 , ..., p k называютсясопряженными относительно матрицы А размеров (n  n), илиА-ортогональными, если( Api , p j )  0, i  j; i, j  1, ..., k .(5.1)Рассмотрим минимизацию в R n квадратичной функции1F ( x )  ( Ax, x )  (b, x)  c с положительно определенной матри2цей А с помощью итерационного процессаx k 1  x k   k p k , k  0,1, ..., x 0  R n ;p0   grad F ( x 0 ),(5.2)где векторы p k А-ортогональны, а величина шага k определяется из условия исчерпывающего спуска по направлению p k .67После вычисления очередной точки x k 1 , k  0,1, ...

новоенаправление поиска pk 1 находят по формулеp k 1  grad F ( x k )  k p k , k  0,1, ...,(5.3)где коэффициенты  k выбирают так, чтобы при минимизацииквадратичной функции F ( x ) с положительно определенной матрицей А получилась последовательность А-ортогональных векторов p0 , p1 , ... .Из условия ( Ap k 1 , p k )  0 имеемk A  grad F ( p k 1 ), p k .(5.4)( Ap k , p k )Для квадратичной функции шаг исчерпывающего спуска понаправлению p k равенkgrad F ( x k ),pk .(5.5)( Ap k , p k )Можно показать, что описанный процесс минимизации(см.

(5.2)–(5.5)) квадратичной функции с положительно определеннойсимметричной матрицей А дает точки x 0 , x1 , ..., x k и векторыp0 , ..., p k , такие, что если grad F ( x i )  0 при 0  i  k  n  1, товекторы p0 , ..., p k А-ортогональны, а градиенты grad F ( x 0 ), …,grad F ( x i ) взаимно ортогональны.Обращение градиента в нуль в очередной точке x k итерационного процесса свидетельствует о достижении точки глобальногоминимума.

Рассматриваемый метод гарантирует нахождение точки минимума квадратичной функции не более чем за n шагов.С учетом взаимной ортогональности градиентов grad F ( x i ) иусловий исчерпывающего спуска по направлениям p k можноупростить выражения (5.4) и (5.5). Запишем числитель дроби (5.5)в виде grad F ( x k ), p k    grad F ( x k ),  grad F ( x k )  k 1 pk 1    grad F ( x k )  k 1  grad F ( x k ), pk 1    grad F ( x k ) .22(5.6)68Умножив обе части равенства (5.2) слева на матрицу А и прибавив к ним по вектору b, получимgrad F ( x k 1 )  grad F ( x k )   k Ap k .(5.7)С учетом формулы (5.7) упростим числитель в выражении (5.4)для  k следующим образом: Agrad F ( x k 1 ),  grad F ( xk 1), (grad F ( xp k    grad F ( x k 1 ), Aр k  k 1)  grad F ( xk 1grad F ( x k )2) k  grad F ( x k 1 )k.В результате получимk k grad F ( x k 1 )grad F ( x k )(5.8),( Aр k , р k )22.(5.9)Выражение (5.9) для коэффициента  k не содержит в явномвиде матрицу А квадратичной функции.

Поэтому метод сопряженных градиентов может применяться и для минимизации неквадратичных функций. В этом случае итерационный процесс методаописывается соотношениямиx k 1  x k   k p k , x 0  R n ,p k  grad F ( x 0 ), k  0, 1, 2, ... ;(5.10)F ( x k   k p k )  min F ( x k   p k ), k  0, 1, 2, ... ;(5.11)p k 1  grad F ( x k 1 )  k p k , k  0, 1, ... ;(5.12) 0k grad F ( x k 1 )gradF ( x k ), k  1, 2, ... .(5.13)69Разумеется, процесс (5.10)–(5.13) может не приводить к точке минимума функции F ( x ), отличной от квадратичной, за конечное число итераций.

Точное определение k из условия (5.11) возможно получить лишь в редких случаях. Поэтому реализация каждой итерациибудет сопровождаться неизбежными погрешностями. Эти погрешности, накапливаясь, могут привести к тому, что векторы p k перестанут указывать направление убывания функции и сходимость методаможет нарушиться. Поэтому на практике в методе сопряженных градиентов через N шагов производят обновление метода, полагая mN  0, m  1, 2, ... . Номера mN называют моментами обновленияметода (рестарта). Часто полагают N = n, где n — размерность пространства R n .

Характеристики

Список файлов книги