Амосов А.А., Дубинский В.А., Копченова Н.В. Вычислительные методы для инженеров (1994) (1095853), страница 51
Текст из файла (страница 51)
Диффе ренцирование Г по х~ дает дГ 1 а 1 %р'9 + ~ айх~ Ис. дх~ 2 ~=1 2;.1 Пользуясь симметрией матрицы А, получим формулу дГ Я вЂ” — Е И~ух;-4. дх~ (10.7) Таким образом, Г'(х) = Ах- $. д~Г Дифференцируя обе части равенства (10.7) по хь получим — = ац~. дх~ да~ Это означает, что для квадратичной функции (10.5) матрица Гессе не зависит от х и равна А.
Задача минимизации квадратичной функции представляет интерес по многим причинам. Отметим две основные из них. Во-первых, в малой окрестности точки минимума гладкая целевая функция хорошо аппроксимируется суммой первых трех слагаемых ее разложения по формуле Тейлора: Пх) ~ Г«(х) = У(х ) + (У(х )1 х х )+ 2(~~~(х )(х- х )> х- х ) (10.9) 1 с центром в точке х* м х.
Функция Г, с точностью до постоянного (10.10) Более того, решение хо системы (10.10) дает точку минимума функции 266 слагаемого может быть записана в виде (10.6) с матрицей А = С (х') м й С (х). Поэтому можно ожидать, что вблизи точки минимума качественный характер поведения последовательности х'">, генерируемой методом минимизации, для функции ~окажется почти таким же,как и для квадратичной функции Г.
Во-вторых, хорошо известно, что в случае, когда А — симметричная положительно определенная матрица, задача минимизации квадратичной функции (10.6) эквивалентна задаче решения системы линейных алгебраических уравнений (10.6). Действительно, Р'(во) = Ахе — $ = О, т. е. во является стационарной точкой функции Г. Так как матрица Гессе Г"(зс) = А положительно определена, то в точке зо выполнены достаточные условия минимума и, значит, зо = т.
Таким образом, всякий метод безусловной минимизации, будучи примененным к поиску минимума функции (10.6), порождает некоторый метод решения системы (10.10). Отметим, что поверхностями уровня квадратичной функции (10.6) служат т-мерные эллипсоиды (при т = 2 — эллипсы) с центром в точке в. Отношение большей оси каждого из этих эллипсоидов (эллипсов) к меньшей оси равно сопй2(А) = Лпйй,й/Лрп,„— числу обусловленности матрицы А.
Здесь Лрпщ, и Лп~„— максимальное и минимальное собственные значения матрицы А. Чем больше отношение Лрра„/Л~„, тем сильнее вытянуты поверхности (линии) уровня. 5. Обусловленность задачи минимизации. В ~ 9.2 достаточно подробно обсуждалась обусловленность задачи поиска строгого локального минимума функции одной переменной. Так как ситуация в многомерном случае аналогична, то здесь изложим соответствующие положения более кратко.
Пусть я — точка строго локального минимума дважды непрерывно дифференцируемой функции ~ матрица Гессе которой в точке х положительно определена. Предположим, что в некоторой окрестности точки минимума вычисляемые приближенные значения ~*(х) удовлетворяют неравенству ~~(в) — ~й~я)~ 4 Ь = Ь(~*). Тогда для радиуса соответствующей области неопределенности справедлива грубая оценка г е 2 Е Цй „, где йш„> Π— мпмммюгьпое сойствеммое апачемме матрицы Гессе ~"(я). Отсюда следует, что методы приближенного решения задачи минимизациии, в которых используются только значения ~й, не могут, вообще говоря, гарантировать получение приближенного решения в* с погрешностью меньшей чем Ь(~') 2 Г йггйм, Это оемачаег, мапример, что даже для хорошо масштабированных задач (т.
е. при 14 - 1, )У(я) ) " 1, Лы„- 1) неизбежна потеря примерно половины из того числа верных значащих цифр, которые содержались в приближенных значениях ~й(в), Пусть теперь для решения задачи минимизации доступны приб- 267 лиженные значения градиента (7') '. Тогда сведение задачи поиска точки минимума я к эквивалентной задаче решения системы уравне- ний у'(я) = 0 существенно улучшает обусловленность задачи. В част- ности, справедлива такая оценка границы абсолютной погрешности: Здесь Ь Я ) ') — граница абсолютной погрешности значений (~') ', считающаяся достаточно малой величиной.
Поэтому если для вычисления а можно использовать значения градиента, то такой возможностью не следует пренебрегать. 5 10 2. Понятие о методах спуска. Покоординатный спуск 1. Методы спуска. Большинство итерационных методов, применяемых для решения задачи безусловной минимизации функций многих переменных, относятся к классу .иетодов спуска, т. е. таких методов, для которых каждая итерация (шаг) приводит к уменьшению значения целевой функции: ~(х< "'~>) < ~(Ы "~ ) для всех и ~ 1О.
Опишем структуру типичной (а + 1)-й итерации метода спуска в предположении, что приближение з< "> к точке минимума уже найдено и я~ "> 1 я. 1е. Находят ненулевой вектор у' "', называемый иааравлеиие.а спуска. Этот вектор должен быть таким, чтобы при всех достаточно малых а ) 0 выполнялось неравенство Х(з( а) + оя( й~ ) < у(в( ~~) ). Если ввести функцию одной переменной а, имеющую вид ~ (~) — ~(в( п~ ~ о1~(и) ) (10.11) (10.12) ~(з( ~й) + д у( ~~) ) < ~(з[ ~~) ) (10.13) или, что то же самое,.неравенство у„(а„) < ~ра(0).
268 то неравенство (10.11) можно записать так: р„(а) < у„(0). 2е. Вычисляют положительное число а„(ма~ спуска), для которого выполняется неравенство 3«. За очередное приближение к точке минимума принимают х< л+<) х<<п> + „р< а! 4с. Проверяют выполнение критерия окончания итераций. Если критерий выполняется, то итерации прекращают и полагают х м х<"">. В противном случае итерации продолжают далее. Последовательность точек х< с', х' ' >, ..., х' ".<, ..., генерируемую методом спуска, иногда называют траекторией спуска. 2. Направление спуска Заметим, что вектор р< "> не может быть задан произвольно.
В силу требования (10.11) функция у„(а), определяемая формулой (10.12), должна убывать в точке а = О. Для того чтобы это условие выполнялось, достаточно потребовать выполнения неравенства <р„(0) < О. Так как р„'(а) = (~'(х< "> + ар< "~), р'"'), то вектор р< "> является направлением спуска, т. е. удовлетворяет условию (10.11), если (10.14) Можно показать, что для строго выпуклой функции ~ это неравенство выполняется тогда и только тогда, когда вектор р< "< задает направление спуска. Обычно именно способ выбора направления спуска р' "' определяет конкретный численный метод, а различные варианты метода определяются далее алгоритмом вычисления шага спуска а„.
Например, выбор в качестве р< "> антиградиента р< "> = -У'(х< "~) задает градиентный метод (см. 9 10.3). В этом случае (~'(х<"'), р< ">) = -<1'(х< ">))~ < < О, т. е. условие (10.14) выполняется. 3. Выбор шага спуска. Следует иметь в виду, что шаг а„спуска определяет "истинную" величину шага Ь„= ~ х' ""' — х' "> ~ = а„~ р< "~ ~, но совпадает с ней только тогда, когда вектор р< "' имеет единичную длину. В качестве а„ можно выбирать значение параметра а, которое обеспечивает достижение наименьшего значения функции ~вдоль луча х = х< "< + ар«<>, а 1 О.
В этом случае для вычисления а„требуется решение одномерной задачи минимизации функции р„(а). Этот путь достаточно надежен, однако может быть связан с большими вычислительными затратами. Существуют и активно применяются другие подходы к выбору а„, гарантирующие выполнение условия (10.13). Один из простейших подходов, называемый дроблеяием ша<а, состоит в следующем. Фикси— руют начальное значение шага а и выбирают параметр т, 0 < у < 1 269 (часто у = >/г).
За шаг спуска принимают а„= гг у'и, где г„— первый из номеров г = О, 1, 2, ..., для которого выполнено условие У(хг™> ~ а,.~гр>п>) ~(х>п>) ~ (~,'а.7г(У(х>™>) у>п>) 1 (10 15) Здесь 0 < Д < 1, р — некоторый дополнительный параметр. 4. Критерии окончания итераций. На практике ча>сто используют следующие критерии окончания итераций: (10.16) (10.17) (10.18) ! х(п+1> хгп> ! < е ~~(х'и'>) -Дх>п>) ~ < ер, 1У( >и>)! < где е>, ег, ез — заданные положительные числа. Нередко используют различные их сочетания, например требуют, чтобы одновременно выполнялись условия (10.16) и (10.17) или даже все три условия (10.16) — (10.18).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
