Амосов А.А., Дубинский В.А., Копченова Н.В. Вычислительные методы для инженеров (1994) (1095853), страница 52
Текст из файла (страница 52)
Нередко вместо критериев (10.16), (10.17) применяют их аналоги, основанные на сочетании понятий относительной и абсолютной погрешностей: (10.19) (10.20) ~хгп+» хгп> ~ < ~(1 г ~хг>г+>> ~) ~у( .> и+>>) ~( > п>)~ < ~ (] ф ~ ~(х> и+>>) ~) тальных координат фиксируют, а хг "'> выбирают из условия у(х>п+и х>п> ..., хгп>) = т>п ~(хп хр, ... х'и>), х> Фактически решается задача минимизации функции одной перемен- ной 7(х) = ~(х> х> "> х>п>) 270 а также другие критерии. К сожалению, надежные критерии окончания счета, которые были бы применимы к широкому классу задач и гарантировали бы достижение нужной точности, пока не известны.
5. Покаординатный спуск. В методе покоординатн ого спуска в качестве очередного направления спуска выбирают направление одной из координатных осей. Наиболее известным является ггегпод ггггклггческого покоордипагпного спуска. Опишем очередной (и + 1)-й цикл одного из вариантов этого метода, считая приближение х> "> уже найденным.
Цикл с номером, и + 1 состоит из гп шагов. На первом шаге производят спуск по координате х>. Значения хг — — х~г ">, ..., х,„= х~~ "> ос- На второ шаге производят спуск по координате хг. Значения х~ = = х'и+~', хз х<и> ... х,„= х~и' остальных координат фиксируют и х' и'~' выбир как решение задачи одномерной минимизации ~(в<""' т<~~> х<"' ... л< ">) = т!и ~(~<""', гр х'"', ..., *< ">).
х2 Аналогично осуществляют остальные шаги. На последнем т-м шаге координату х' " '~ определяют из условия ~(х[ и+1) х( и+1) х( п+1) ) — ш1п у'(х(а+1) х( и+1) х, ) хи В результате получается очередное приближение х'""' к точке минимума. Далее цикл метода снова повторяют. На рис, 10.4 изображена геометрическая иллюстрация циклического покоординатного спуска. Рис.
10.~ Применим метод циклического покоординатного спуска для минимизации квадратичной функции (10.5). Так как на й-м шаге очередного цикла значение координаты хай'И определяется из условия мини- мизации функции г" по направлению ц„то необходимо, чтобы в точке (х(и+1) хай+1) хай+1) х~й) х( и) )т производная ~3~/~1х обращалась в нуль.
Учитывая формулу (10.7), получаем уравнение й Я$ Е ацх<.й'~> + Е ацх'.и~ — Ь~, = О, р й+~ откуда находим «-1 и Х),п+1' = а<,~,(бЬ вЂ” Е ацХ<.и+11 — Е аЬ Х<.п1). 1=1 1 <=1„1 1 1 (10.21) Последовательные вычисления по формуле (10.21) для 1 = 1, 2, ..., т и составляют один цикл метода покоординатного спуска. Заметим, что этот метод применительно к решению системы линейных алгебраических уравнений Ах = й с симметричной положительно определенной матрицей дает известный итерационный метод Зейделя (см. гл, 6), сходящийся со скоростью геометрической прогрессии. $10.3. Градиентный метод Рассмотрим задачу безусловной минимизации дифференцируемой функции многих переменных 7 (х).
Пусть х< и> — приближение к точке МИНИМуиа Х, а у<и< = у (Х'"') — ЗНаЧЕНИЕ ГрадИЕНта В ТОЧКЕ Х'"'. Выше уже отмечалось, что в малой окрестности точки х< т направление наискорейшего убывания функции ~ задается антиградиентом -у'и'. Это свойство существенно используется в ряде методов минимизации. В рассматриваемом ниже <радиентно.и иетоде эа направление СПуСКа Иэ ТОЧКИ Х'"1 НЕПОСрЕдСтВЕННО ВЫбИраЕтея р'п1 = — у<п1. ТаКИМ образом, согласно градиентному методу (10.22) Х< и+11 — Х< п) а у< п) Рп(ап) = Ш<П ~Рп(а) 0(а (10.23) Этот метод, предложенный в 1845 г. О. Коши<, принято теперь назы- вать методол< наисхорейше<о спуска. Огюстен Луи Коши (1789 — 1857) — французский математик, один из создателей современного математического анализа, теории дифференциальных уравнений и др.
272 Существуют различные способы выбора шага а„, каждый из которых задает определенный вариант градиентного метода. 1. Метод наискорейшего спуска. Рассмотрим функцию ~р„(а) = 1(х<п< — ау<"') одной скалярной переменной а 1 0 и выберем в качестве а„то значение, для которого выполняется равенство Г(х) = — (А*, х)-(Ь, х) (10.24) с симметричной положительно определенной матрицей А. Согласно формуле (10.8), в этом случае у< "' = Ах' и> — Ь. Поэтому формула (10.22) выглядит здесь так: х< и+Ы = х< п~ ап(Ах< п> Ь) (10.25) Заметим, что (а) — (А (х( и) оу( и) ) х( И) — оф п) ) — (ф х( и) — оу( а) ) 1 2 1 — (А~(п) ~(п) ) о2 (У(п) фи)) о + (Ах(п) х(п) ) (в х(п) ) 1 Эта функция является квадратичной функцией параметра а и дости- гает минимума при таком значении а = ап, для которого 1~'(ап) = (Ау~п~ фп~) оьп — (у~п~ фп~) — 0 Таким образом, применительно к минимизации квадратичной функ- 273 На рис.
10,5 изображена геомет— рическая иллк1страция этого метода и для минимизации функции двух к") переменных. Из начальной точки перпендикулярно линии уровня + ~(х) = 1 (х~а> ) в направлении у< а' = = -у~ а! спуск продолжают до тех / пор, пока не будет достигнуто минимальное вдоль луча ~4а~ + ау<а~ у (а ) О) значение функции ~ В найденной точке х"> этот луч касается линии уровня ~(х) = 1 (х~").
Затем из точки х'" проводят спуск в перпендикулярном линии уровня направлении р' " = -у'~' до тех пор, пока соответствующий луч не коснется в точке х'~' проходящей через эту точку линии уровня, и т. д. Отметим, что на каждой итерации выбор шага ап предполагает решение задачи одномерной минимизации (10.23). Иногда эту операцию удается выполнить аналитически, например для квадратичной функции.
Применим метод наискорейшего спуска для минимизации квадратичной функции ции (10.24) метод наискорейшего спуска эквивалентен р чету по формуле (10.25), где (у(п> фп) ) (10.26) ( 3 а м е ч а н и е 1. Поскольку точка минимума функции (10.24) совпадает с решением системы Ав = Ь, метод наискорейшего спуска (10.25), (10.26) может применяться и как итерационный метод решения систем линейных алгебраических уравнений с симметричными положительно определенными матрицами. 3 а м е ч а н и е 2.
Отметим, что а,,~ = р (у~">), где р (в) = (Ая, в)/(я, в) — отношение Рэлея (см. 3 8.1). Пример 10.1. Применим метод наискорейшего спуска для минимизации квадратичной функции /(г1, вг) = Я + 24 — 4г1 — 4гг. Заметим, что /(г1, гь) = (г1 — 2)г + 2(гь — 1)г — 6. Поэтому точное значение в = (2, 1)т точки минимума нам заранее известно. Запишем данную Г2 01 функцию в виде (10.24), где матрица А = ~ ! и вектор Ь = (4, 4)т. Как (О 4! нетрудно видеть, А = Ат > О. Возьмем начальное приближение я~о' = (О, 0)т и будем вести вычисления по формулам (10,25), (10.26).
со) „~о~а итерация. у(о) — Ав(о) Ь=(4 1)т н (,4 со> ~о~) 4г+ 4г 1 — дл Ы вЂ” в~ о> о ус о) — (4/3, 4/3)т. 2.4г + 4.4г 3 С1> С 111 П итерация. у~Ы=Аа~1~ — Ь=( — 4/3,4/3)т, о (Аус1) у<1)) (4/3)г + (4/3) г 1 г) — ы ы 2 ° (4/3)г + 4 (4/3)г 3 ' — в( и) — ~. (2 ( 1)п)т — п 3' 3" ф п) — (1 ( 1)п)т ,/5 в~ = — -+ 0 при и оо. Таким образом последова— 3" ! Заметим, что ~в~ "~— Можно показать, что для всех а ~ ~1 на и-й итерации будут получены значения тельность к'">, полученная методом наискорейшего спуска, сходится со скоростью геометрической прогрессии, знаменатель которой у = 1/3. На рис. 10.5 изображена именно та траектория спуска, которая была получена в данном примере.
Для случая минимизации квадратичной функции справедлив следующий общий результат [ 181. Т е о р е и а 10.1. Пусть А — сим иетричная положительно определенная иатрица и минимизируется квадратичная функция (10.24). 'Гогда при любом выборе нача*ьного приб*ихения метод наискорейшего спуска (10.25), (10.26) сходится и верна сяедуюигая оценка погрешнооти: Взх пих пОЛ ~ г о1 4Л,. (Л +Л (10.27) 3десь Л;„и Лиях — минимальное и максимальное собственные значения иатрицы А.
Отметим, что этот метод сходится со скоростью геометрической прогрессии, знаменатель которой у = (Лиах — Лшг„)/(Лиах + Л,пг„), причем если Лшг„и Л„„близки, то у мало и метод сходится достаточно быстро. Например, в примере 10.1 имеем Л;„= 2, Лиах = 4 и поэтому д = (4 — 2)(4 + 2) = '/з. Если же Л„д„< Лиах, то д и 1 и следует ожидать медленной сходимости метода наискорейшего спуска.
Пример 10.2. Применение метода наискорейшего спуска для минимизации ( 91п — 2~ — ~ (1, (-1)")т, где к = (2, 0.2)т. Траектория спуска изображена на Ы рис. 10.6. Риа 10.б Последовательность я' "' сходится здесь со скоростью геометрической прогрессии, знаменатель которой равен д = 9/11, т. е. существенно медленнее, 275 квадратичной функции /(ег, з~) = гг + 10г$ — 4х1 — 4гь при начальном приближении яг о> = (О, 0)т дает последовательность приближений к' т = ив ~20 чем в пРедыдУщем пРимеРе. Так как здесь А = ~, то Лщ1о = 2, Лщщ, —— (О 20Я' = 20, (Лщад, — Лщ1о)/(Лщз„+ Лщ1о) = 9/11, и полученный результат вполне согласуется с оценкой (10.27). 3 а м е ч а н и е 1.
Мы сформулировали теорему о сходимости метода наискорейшего спуска в случае, когда целевая функция является квадратичной, В общем случае, если минимизируемая функция строго выпуклая и имеет точку минимума я, то также независимо от выбора начального приближения полученная указан- ным методом последовательность к<"' сходится к х при а -~ ю. При этом после попадания к'"' в достаточно малую окрестность точки минимума сходимость становится линейной и знаменатель соответствующей геометрической прогрессии оценивается сверху величиной д щ (Лщак — Лщ1„)/(Лщзк + Лщ1„), где Лщ1п и Лпщх — минимальное и максимальное собственные числа матрицы Гессе С (к). 3 а м е ч а н и е 2. Для квадратичной целевой функции (10.24) решение задачи одномерной минимизации (10.23) удается найти в виде простой явной формулы (10.26).
Однако для большинства других нелинейных функций этого сделать нельзя и для вычисления а„методом наискорейшего спуска приходится применять численные методы одномерной минимизации типа тех, которые были рассмотрены в предыдущей главе. 2. Проблема "оврагов". Из проведенного выше обсуждения следует, что градиентный метод сходится достаточно быстро, если для минимизируемой функции поверхности уровня близки к сферам (при ти = = 2 линии уровня близки к окружностям). Для таких функций е = = Лщзх/Лщ1„щ 1.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
