Буслов, Яковлев - Введение в численный анализ (947494), страница 15

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

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

7.1.2 Метод парабол Если функция обладает достаточной гладкостью (имеет вторую производную) то естественно использовать зто обстоятельство при поиске минимума. В этой точке Ф'(х) = О, и можно искать нуль первой производной, скажем методом Ньютона ф'(х-) фл( ) Эту формулу легко получить и непосредственно разложив Ф(х) в ряд Тейлора в точке х и ограничившись тремя членами, т.е. аппроксимируя кривую параболой ф(х) Ф(х„) + (х — х„)Ф'(х„) ф Ф" (х„) . 2 Минимум этой параболы находится как раз в точке х„+ь В связи с этим метод и называется методом парабол. Вычислять и первую и вторую производную на каждом шаге довольно накладно.

Поэтому их приближенно заменяют разностными производными, вычисленными с помощью вспомогательного шага Ь: ф(х + Ь) — Ф(х — Ь) ф (х„) -+ 2Ь Ф(х„+ Ь) — 2ф(х ) + Ф(х — Ь) Ф (х ) -+ и метод принимает вид Ь Ф(х„+ Ь) — Ф(х„— Ь) 2 Ф(х + Ь) — 2Ф(х ) + Ф(х — Ь) Кстати, этот подход эквивалентен замене кривой на интерполяционную параболу, построенную по трем точкам хз— Ь, х, х„+ Ь с последующим нахождением минимума этой параболы (точки х„~.1). Замечание.

Уместно сравнить методы поиска минимума н методы поиска корня уравнения. Так метод золотого сечения подобен дихотомии. И в том и другом на функцию накладываются минимальные ограничения. Они чрезвычайно просты и надежны, порядок сходнмости в обоих методах линейный. Метод парабол в этом смысле подобен методу Ньютона. От функции требуется больше, сходнмость быстрее. Поиск минимума по методу парабол соответствует поиску корня по методу секущих. 7.2 Функции многих переменных Пусть Ф: йр -з Н:, ЛХ С й.~ и пусть Ф Е См~. В точках минимума ~~ = О,г = 1, ..., зУ, как впрочем и в точках максимума и в седковых точках.

Но разложение в ряд Тейлора в окрестности невырожденной точки минимума х* 78 Ф(х) = Ф(х*) + — ~~~ „Ьх,г".гх + .. ' агФ 2 дх,"" 1 выделено тем, что квадратичная форма ) Ь вЂ” тах,ахг положительно определена (напомним, что квацратичиая эгь ау=1 форма называется положительно определенной, если 2 а, дгг > у~~я~~, у > О, где я = (хм хе..., гк)~ ). 7.2.1 Координатный спуск Пропедуру координатного спуска рассмотрим на примере функции двух переменных Ф(х.у). Пусть (хо, йо) — некоторая точка.

Зафиксируем переменную р и найдем минимум функции Ф(х, ро) каким либо из уже известных способов поиска минимума функции одного переменного (спуск по первой координате). Пусть этот минимум достигается в точке х'. Зафиксировав это значение найдем минимум функции Ф(х', р) (спуск по второй координате). Пусть ои находится в точке р'. Теперь найдем минимум функции Ф(х, у') (следующий спуск по первой координате) и т,д. Такой метод поиска минимума называется коордииатимгг спускохь В зависимости от свойств функции и положения начальной точки, процесс может сойтись к экстремальной точке или нет. Отметим достаточый признак сходимости координатного спуска. Если Ф дважды непрерывно дифференцируема в области М, содержащей точку минимума х" и квадратичная ого форма 2 Ь- Ах, Ахг положительно определена, то в некоторой окрестности х* метод координатного спуска сходится ьг =1 к указанному минимуму, Доказательство проведем для случая двух переменных.

Пусть Фк„> а, Ф„, > Ь, ~Ф„г ~ < с, где а,Ь,с > О и аЬ > с в области М (зто означает в частности, что матрица вторых производных положительно определена). Будем считать, что точка А = (хо, уо) получена в результате спуска по переменной у, т.е. Ф„(А) = О . Пусть ~Фг(А)~ = г."г . В точке В = (х',у~) обращается в нуль Ф„, а модуль Ф„равен некоторому числу О.

Таким образом ~г = ~Ф (А) — Фк(В)! = ~Ф~„(~))р(А,В) > ар(А,В), О = /Фг(А) — Фг(В)/ = )Ф„гф')~Р(А,В) < сР(А, В), откуда сг,'г > аг) . В точке С = (х~,д~): Ф„= О, и Фг = ~г, при этом ~г = )Ф,(С) — Ф,(В)) = ~Ф,г(т) ~р(С, В) < ср(С, В), и = )Ф, (С) — Фг(В)( = )Фгг(т')~р(С, В) > Ьр(С В), и, следовательно, сц > Ььг . (2) Из (Ц и (2) заключаем, что ~,"г < д~м где О < а < — < 1. Таким образом с каждым циклом Ф, уменьшается как сг минимум в о раз. Аналогично убывает и частная производная по переменной р.

Таким образом координатный спуск действительно сходится к точке минимума. 79 7.2.2 Наискорейший спуск Спуск можно осуществлять не только вдоль координатных осей, а вообще вдоль любого направления. Пусть а произ- вольный единичный вектор, задающий направление. Функция ооо(1) = Ф(г Ч- а1) есть функция одной переменной в ее минимум является минимумом функции Ф(г) на прямой г +во . Если выбрать а = а = — дгапФ~„о, то а будет являться направлением наибольшего убывания функции Ф в точке г . Осуществим спуск вдоль этого направления (то есть найдем минимум функции оо(1) ). Пусть он находится в точке г'.

Теперь в этой точке выберем новое направление а = -дгао(Ф~,1 и осуществим спуск вдоль него и т.д. Заметим, кстати, что векторы а и а ортогональны. 1 о Описанный метод спуска называется наискорейшим. Хотя пря ванскорейшем спуске движение происходит вдоль направления набольшего убывания функции в текущей точке г, однако порядок сходнмости остается таким же, как и при покоординатном спуске (при этом приходится в каждой точке г заново считать градиент).

Дело здесь в том, что при сдвиге от точки г" направление наибыстрейшего убывания функции Ф изменяется. Обычно спуск производят не точно до минимума, а несколько меньше. То есть, если оо„(1) = Ф(г" + а" 1), и минимум функции 1о„(1) достигается в точке оч, то спуск осуществляется до точки аг, где о ( 1 . В "идеале" можно спускаться на бесконечно малую величину и заново корректировать направление.

При этом кривая спуска г(Ц будет удовлетворять уравнению с(г(1) Ж = — дгаИФ(г(1)) . Однако интегрирование такой системы уравнений в частных производных представляет собой отдельную непростую задачу. 7.2.3 Метод сопряженных направлений В окрестности точки минимума функция Ф(г) ведет себя обычно как квадратичная функция.

Будем считать для начала, что она является в точности квадратичной, т.е. Ф(г) = (г, Аг) -~- (г, Ь) -~ с . Здесь Ь б К~ (Се), с 6 В., А — положительно определенная матрица. Поскольку А положительно определена, то квадратичная форма (х, у)л = (х, Ау) удовлетворяет всем свойствам скалярного произведения. Введем ортонормированный базис (е*)~, в линейном пространстве с нормой (, )л. Будем называть направления, задаваемые им, сопряженными.

Если г некоторая точка, то о произвольная точка г представляется в виде г = го ч- 2,' о,е'. Тогда 1 Ф(г) = (г + ~~~ о,е',Ага+ ~~~ а,Ае')+ (г + ~~~ о,е*,Ь) +с = = Ф(г ) + ~~~ (а, + 2со,(е', г ) + а,(е', Ь)1 =1 В этой сумме отсутствуют перекрестные члены, таким образом спуск вдоль любого направления е* минимизирует лишь свой член суммы. Это означает, что осуществив спуск по каждому из сопряженных направлений лишь один раз мы в точности достигаем минимума. В точке минимума дФ, о — = 2п, + 2(е', Аг + Ь/2) = О, 1 = 1, 2,... Ж дпч откуда а, = — (е',Аг + — ). 80 Построение базиса сопряженных направлений и спуск по ним Пусть г произвольная точка и е произвольный единичный вектор. Рассмотрим прямую г = г~ Е ое и найдем вдоль этой прямой минимум функции гг(о) = Ф(г + ое ).

Будем считать, что указанный минимум достигается как раз в 1 3 точке г, то есть О = аг = -(е,Аг + Ь/2). Аналогично, пусть на прямой г +ае минимум достигается в точке г 1 г г г г (О = ог = — (е, Аг" + Ь/2)). Таким образом ог — о~ = (е',А(г — г')) = (е',(г — г'))л = О г 1 1 и единичный вектор е = — ~=-))( — оказывается сопряженным к е . Аналогично, пусть имеется гп сопряженных векторов е', е,..., е и в двух параллельных т-мерных сопряженных плоскостях г' + 2,'о,ез и гг + 2 о,е' минимум достигается в точгшх г' и гг соответственно, тогда вектор г — г' сопряжен всем векторам (е'); Опишем теперь последовательность действий по построению базиса, сопряженных направлений.

Пусть (д'),'~, стандартный базис и мы построили т сопряженных векторов, при этом выбросив из рассмотрения т векторов стандартного базиса, скажем, с номерами А' — пг + 1,А' — т+ 2, ...,Х. Пусть ге произвольная точка, произведем из нее спуск по сопряженным векторам (е')г и Попадем при этом в некоторую точку г .

Из нее произведем спуск по 1 оставшимся векторам (д)~, стандартного базиса и попадем в точку гг. Теперь из гг спустимся по сопряженным векторам (е'),',. Попадем при этом в некоторую точку гз. Точки г' и г являются минимумами функции Ф(г), в двух параллельных гиперплоскостях, задаваемых сопряженными направлениями. Таким образом г — г — новое з сопряженное направление. Добавим его к уже построенным и выбросим один из векторов (д) ~:,~. Формально все равно какой из них выбрасывать, однако для повышения точности желательно выбрасывать тот, при спуске вдоль которого функция Ф(г) изменилась меньше всего, даже если случайно он оказался одним из сопряженных.

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

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