Курсовая работа по курсу "Структурный анализ и синтез" на тему "Параметрическая идентификация" (стр. 5 )

- известные функции.

2. Уравнения =0 суть нелинейные алгебраические или трансцендентные зависимости, нахождение точных значений корней которых чаще всего невозможно.

3. Исследование выпуклости Ф() затруднено. Число стационарных точек Ф() в общем случае нельзя определить, так как система уравнений (IX. 18) не может быть решена. Утверждения о наличии одного или нескольких экстремумов крайне трудно и доказать, и опровергнуть.

4. Поверхность Ф() имеет «овраги» - множество точек , в которых норма градиента зависит существенно от одних частных производных и слабо от других. При расположении точки а в «овраге» вариации некоторых параметров aim, приводят к большому росту Ф(), изменения же остальных aim крайне слабо влияют на величину Ф().

Понятие «оврага» для функции двух переменных Ф(а1, а2) совпадает с нашим обычным представлением об овраге или ущелье. «Овражный» характер Ф(а1,а2) проявляется в том, что линии уровня Ф(а1, а2)=rj (j=1, 2, ...,pj = const) сильно вытянуты и искривлены (рис.5.1). Для хорошо организованных функций линии уровня имеют более гладкий и правильный вид, например, для Ф (а1, а2) = d1 + d2 (d1 > 0; d2 > 0) линии уровня – эллипсы (см. рис.5.2).

Размерность «оврага» определяется числом переменных, в направлении которых частные производные функции Ф изменяются мало. Обычно размерность «оврага» намного ниже размерности функции Ф().

Причины образования «оврагов» заключаются, по-видимому, в трансцендентности и нелинейности функций fi, в недостаточно хорошем усреднении экспериментальных данных и тому подобное.

5. На поверхности Ф() могут иметься участки, во всех точках которых grad Ф()0. Образование таких участков объясняется как свойствами самой Ф(), так и методами вычисления её ординат. В частности, при вычислении Ф на ЦВМ имеет место округление чисел из-за конечного числа разрядов сумматора машины, что приводит к появлению областей стационарности Ф(), то есть областей слабого изменения ее градиента.

Отметим, наконец, многомерность функций Ф(). Чаще всего число переменных аim, в выражениях (5.4), (5.5) превышает 3-4, а в некоторых задачах достигает 10-12. Многомерность Ф() затрудняет геометрическую интерпретацию процедуры поиска минимума и увеличивает затраты машинного времени.

Из второго и третьего приведенных выше свойств плохо организованных функций (5. 4), следует, что определение стационарных точек с из системы уравнений (5.18) возможно только приближенными, итерационными методами. При этом однозначно устанавливается, является ли данная с точкой минимума или максимума.

Каждая функция многих переменных имеет свои, заранее неизвестные, особенности строения поверхности Ф(). Это привело к разработке большого числа различных приближенных методов. Некоторые из них, наиболее приспособленные для исследования плохо организованных функций, разбираются ниже.

Рис.Пример функции с искривленным «оврагом»

Рис.5.2. Линии уровня хорошо организованной функции

Рис.5.3. Области притяжения многоэкстремальной функции

5.1. Метод градиентов

Метод градиентов базируется на предположении о линейности Ф() в малой окрестности точки . Искомая точка локального минимума * лежит на траектории (t), являющейся решением дифференциального уравнения:

, (5.21, а)

где a - коэффициент пропорциональности;

t - условное время с произвольно выбранным начальным условием 0А. В скалярной форме уравнение (5.21, а) запишется следующим образом:

. (5.21, б)

Если Ф() имеет на множестве А несколько локальных минимумов * (1, 2, ..., q), то, в зависимости от выбора , траектория (t) будет приходить в тот или иной минимум. Для функции двух переменных множество А будет разделено на несколько областей притяжения, из точек которых градиентный спуск приводит в соответствующие точки минимума (рис.5.3).

Для практического решения задач важно знать время перехода изображающей точки (t) из в . Скорость движения (t) прямо пропорциональна крутизне поверхности Ф(). Так как gradФ=0, то по мере приближения (t) к * скорость движения убывает. Например, для функции Ф(а1, а2)=d1+d2 система (5.21, б) примет вид:

.

Траектория (t) = {, a2(t)},где=ехр(-2ad1); a2(t)=ехр(-2ad2t), выходит из начальной точки (, ) и попадает в точку минимума ={0,0} в момент времени t=, т. е. получить точное решение задачи оказывается невозможным. При решении экстремальных задач на ЦВМ используется дискретный градиентный метод [3], по которому

. (5.22, а)

Для координаты аi уравнение (5. 22, а) примет вид:

. (5.22, б)

или, при нормировании по норме градиента:

. (5.22, в)

В формулах (5. 22,6), (5. 22, в) и дальше для краткости принята следующая форма записи:

.

Строго говоря, в итерационных формулах (5. 22, б) и (IX. 22,в) величина аг, называемая рабочим шагом, не зависит от номера итерации г. Эти формулы обеспечивают сходимость из любой начальной точки а° в точку минимума а* для постоянного рабочего шага а, удовлетворяющего неравенству

.

где М - постоянная Липшица для градиента Ф (), т. е. такая величина, для которой при любых а1 и а2 выполнено условие:

.

Для строго выпуклых функций Ф () скорость сходимости к не превышает скорости убывания геометрической прогрессии со знаменателем r<1, т. е.:

,

где константа m0 зависит от выбранного шага и начального приближения . Для выпуклых функций скорость сходимости, естественно, еще меньше [4].

Обычно постоянная Липшица неизвестна, поэтому величина рабочего шага в практических задачах рассматривается как переменная и подбирается в процессе решения задачи эмпирическим путем. Чаще всего применяют так называемый способ «дробления» шага, суть которого заключается в следующем.

Зададимся произвольной величиной шага a0, равной, например, нескольким процентам от ||||, и вычислим значение Ф()=Ф[-a0gradФ()]. Сравним между собой значения Ф() и Ф(). Возможны два варианта: Ф()Ф() и Ф()>Ф().

Если Ф()Ф(), то уменьшаем а0 вдвое, находим Ф()=Ф[-gradФ()] и снова сравниваем Ф() с Ф(). Если Ф()Ф(), то берем , вычисляем:

и т. д., пока не будет выполнено неравенство Ф()>Ф(), где , где q=0,1,… Величина принимается постоянной и используется в формулах (5. 22, б), (5.22, в) до тех пор, пока на каком-то r-м шаге не нарушится неравенство Ф()>Ф(), после чего снова начинается „дробление” ar.

Если Ф()>Ф(), то величину шага а0 удваиваем и вычисляем Ф()=Ф[]. При Ф()<() полагаем шаг равным и т. д. Процесс подбора рабочего шага заканчивается как только при каком-то q нарушится неравенство Ф[]. Рабочий шаг принимается постоянным, пока Ф()>Ф() (r = 0, 1, 2, ...).

Частным случаем метода градиентов является метод наискорейшего спуска, в котором на каждой итерации r оптимальная величина аr находится следующим образом. Составим функцию

характеризующую изменение Ф() в направлении градиента. Возьмем величину аr такой, чтобы (аr), а следовательно, и Ф() достигала условного минимума в направлении вектора grad Ф(аr):

. (5.23)

В качестве ar принимается наименьший из положительных корней уравнения

Нахождение корней ar уравнения (5.23) в общем случае представляет задачу не меньшей трудности, чем определение , например, из уравнений =0. Вследствие этого при решении экстремальных задач на ЭВМ величину оптимального рабочего шага ar находят приближенным способом.

Выберем для этого при r=0 достаточно большое значение a0 и сделаем два шага из точки в направлении вектора grad Ф(). Далее в точках =-a0gradФ() и =-2a0gradФ() вычислим значения функций Ф1=Ф() и Ф2 = Ф(). Затем через три точки Ф0=Ф(), Ф1 и Ф2 со значениями аргумента 0, а0 и 2a0 проведем квадратичную параболу Ф=b0+b1a +b2a2, коэффициенты которой нетрудно найти по интерполяционным формулам:

.

Из условия =0 определяем первое приближение оптимального шага ar при r = 0:

. (5.24)

После этого вычисляется значение Ф3=Ф() в точке ; через точки Ф1, Ф2, Ф3 снова проводится парабола, определяются ее коэффициенты и второе приближение оптимального шага , при котором достигается минимум параболы. Процесс подбора a0 прекращается как только два последних значения оптимального шага будут отличаться друг от друга не более, чем на заранее заданную величину Da, т. е. когда (s=1,2,3, ...). Число s таких приближений зависит от меры близости Ф() к квадратичной функции и от выбора a0. Желательно подбирать величину a0 такой, чтобы выполнялись неравенства Ф0>Ф1, Ф2>Ф1 или Ф2>Ф0. Величина , для которой , принимается за оптимальный рабочий шага a0. Затем в точке вычисляется gradФ() и начинается подбор нового оптимального рабочего шага а1.

Рассмотренный способ приближенного определения оптимального рабочего шага требует усложнения программы решения задачи на ЦВМ и далеко не всегда оказывается рациональным. Поэтому иногда поиск минимума методом наискорейшего спуска осуществляется по следующей схеме.

Из начальной точки движение производится с заведомо малым постоянным шагом аr в направлении вектора gradФ() вплоть до достижения условного минимума. В точке этого условного минимума определяется новый вектор gradФ() и снова осуществляется движение с постоянным шагом в направлении gradФ() до достижения условного минимума. При поиске условных минимумов возможно «дробление» рабочего шага до некоторого заданного значения.

В итерационных методах весьма важным является выбор признака окончания поиска минимума. Введем признаки окончания итерационного процесса по функции и по аргументу. В первом случае итерационный процесс можно считать оконченным, если при Ф()0:

. (5.25, a)

где DФ - заранее заданная величина.

При ориентировочно известном значении Ф() можно использовать и ненормированное условие:

, (5.25, б)

где - заданная точность определения локального минимума функции Ф().

При использовании условий окончания процесса поиска (5. 25, а) и (5. 25,6) может оказаться, что ar+1 далеко отстоит от . Подобные случаи встречаются при отыскании минимума плохо организованной функции, имеющей пологие экстремумы или участки с gradФ»0.

Условия окончания процесса поиска по аргументу записываются в виде:

, (), (5.26, a)

или, при переходе через нуль и приближенно известном :

, (5. 26, б).

Условия окончания процесса итераций (5. 26, а) и (5. 26, б) достаточно жестки и часто их заменяют условиями:

. (5.26, в)

В этом случае контроль за окончанием итерационного процесса ведется по скорости изменения ||||. Для плохо организованных |функций условия (5.26,а), (5.26,в), в общем случае более жесткие, чем условие (5. 25, а), все же не могут гарантировать сходимости (t) к . Поиск может прекратиться при попадании (t) на участок поверхности Ф() с gradФ»0.

Наконец, итерационный процесс можно оканчивать при одновременном выполнении двух условий - (5. 25, а) и (5. 26, а) или (5.25,а) и (IX. 26, в) и - Ф()<Ф().

Выбор констант DФ, Dai или Dа в каждой конкретной задаче представляет собой определенные трудности, поэтому величины правых частей неравенств иногда уточняются в процессе самого поиска.

В формулы (5. 22, а) и (5. 22, б) входят значения частных производных Ф() в точках аr (r=0,1,2,...). Для определения их следует предварительно аналитически продифференцировать Ф() по ai и составить программу вычисления производных. Для некоторых плохо организованных функций вычисление на ЭВМ n значений более трудоемко, чем нахождение n+1 значений Ф(). В таких случаях выгоднее (в смысле затрат машинного времени) находить приближенные значения производной - первые разности:

, (5.27)

где Dai - пробный шаг в направлении аi.

Величина Dai не должна быть слишком большой, так как должна характеризовать скорость изменения функции в точке . Если же выбрана очень малой, то из-за ошибок округления и приближенного характера вычислений на ЭВМ функции Ф погрешность определения по формуле (5.27) может оказаться значительной. Обычно пробный шаг подбирается эмпиричес-

Рис.5.4. Пример градиентного поиска минимума плохо организованной функции

Рис.5.5. Поиск минимума методом «оврагов»

ким способом из условий, чтобы двукратное увеличение или уменьшение Dai не существенно изменяло величину , вычисляемую по формуле (5.27). Неправильный выбор часто приводит к появлению ложных движений изображающей точки (t) или прекращению итерационного процесса из-за обращения в нуль grad Ф().

Метод градиента и его частный вариант - метод наискорейшего спуска наиболее широко применяются для нахождения экстремумов функций многих переменных. Для отыскания минимума плохо организованной функции более предпочтителен метод градиентов с постоянным или «дробящимся» шагом a, так как в этом случае на каждой итерации уточняется направление быстрейшего убывания функции Ф(). Объем вычислений при использовании метода градиентов значительно больше, чем при поиске минимума методом наискорейшего спуска. Однако программа поиска на ЭВМ методом градиентов существенно проще, чем аналогичная программа для метода наискорейшего спуска, оптимальный рабочий шаг в котором определяется из уравнения , или приближенным способом. Метод наискорейшего спуска выгодно применять, если известно, что функция Ф() достаточно хорошо организована, например, не имеет «оврагов» или близка к квадратичной функции. При попадании изображающей точки в «овраг» скорость сходимости методов градиента и наискорейшего спуска резко уменьшается, а траектории движения практически совпадают. На рис. 5.4 изображена траектория движения изображающей точки (t) в соответствии с уравнением (5. 22, а) при =const на поверхности Ф(а1, а2). Внутри «оврага» перемещается по зигзагообразной кривой, скорость движения к точке минимума резко падает. На рис. 5. 2 показана траектория поиска минимума хорошо организованной функции Ф (a1,a2) методом наискорейшего спуска, где аr определены из уравнения

5.2. Метод «оврагов»

Этот метод предназначен для определения направления и контуров «оврагов» и исследования его «дна». Суть метода такова [5].

Зададимся двумя начальными точками и будем осуществлять из них спуск к точке минимума каким-либо методом, например, градиентным. При замедлении движения изображающей точки (t) процесс спуска прекращается в некоторых точках . В этих точках, лежащих на «дне» «оврага», начинает выполняться неравенство (5.25, а) при заданном значении DФ или наблюдается «зацикливание» , проявляющееся в поочередной смене направления движения изображающей точки без заметного перемещения в среднем. Проведем через точки вектор и сделаем достаточно большой «овражный» шаг в его направлении (считается, что Ф() > Ф ()), перейдя в точку:

. (5.28)

Точку рассматриваем как начальную и осуществляем из нее спуск по градиенту в . Если Ф()Ф(), то проводится вектор и из делается «овражный» шаг по формуле При Ф()>Ф() проводится вектор и из точки делается шаг с уменьшенной, например, вдвое, величиной ao.ш. Находится точка , из нее производится градиентный спуск и т. д. На рис. 5. 5 на примере функции Ф(a1, а2) показан процесс «нащупывания» «дна» «оврага». Чередование участков вынужденного движения в направлении экстраполирующего вектора или и поиска «дна» «оврага» позволяет определить его конфигурацию. Затраты машинного времени на обследование «оврага», как правило, на порядок меньше, чем при решении задачи градиентным методом. Скорость движения по «оврагу» зависит от его искривленности и величины . Если участки градиентного, спуска велики или возрастают, то, очевидно, надо уменьшить .

Метод «оврагов» имеет ряд модификаций. Иногда, берут несколько начальных точек и проводят экстраполирующий вектор так, чтобы он проходил через наибольшее число точек , лежащих в «овраге». В других вариантах градиентный спуск осуществляют не после каждого «овражного» шага, а при нарушении неравенства Ф()<Ф(). Этот прием целесообразно применять при слабо искривленных линиях уровня. Все модификации имеют примерно такую же скорость поиска, как и основной метод.

Процедура поиска глобального минимума плохо организованной функции Ф() методом «оврагов» может быть следующей.

Находится «овраг» и определяются его контуры при постоянной величине . Координаты и значения Ф () запоминаются. При подозрениях на разветвление найденного «оврага» или на наличие других «оврагов» необходимо задаться еще несколькими начальными точками и произвести градиентный спуск. Дальнейшему исследованию подвергается тот «овраг» или его ответвление, в котором значения Ф() минимальны. В наиболее подозрительных участках «оврага» производится повторный поиск минимума с более мелким шагом , величина которого начинает дробиться на интервалах, где одновременно и .

5.3. Метод «тяжелого шарика»

Этот метод [6] целесообразно применять для поиска минимума плохо организованных функций, у которых имеется много неглубоких-экстремумов или участки поверхности с grad(Ф)»0.

Движение изображающей точки происходит по уравнению

(5.29)

В начальной стадии движения параметр принимается равным нулю, величина выбирается обычными приемами. При уменьшении скорости движения в уравнение вводится слагаемое с , которое учитывает «инерцию» изображающей точки с ненулевой «массой» . Обычно , причем b возрастает с уменьшением скорости сходимости. При удачном выборе br изображающая точка будет «проскакивать» мелкие локальные минимумы или небольшие участки постоянства grad Ф>(). Поэтому «дробление» величины ar с целью отыскания глобального минимума надо начинать не в момент нарушения неравенства Ф()>Ф(), а при систематическом убывании функции. Глубина «проскакиваемых» минимумов определяется, в основном, величиной br.

5.4. Методы случайного поиска

В таких методах крутизна поверхности Ф() исследуется в окрестности точки в направлении некоторого случайного вектора с нормой |||| = 1 и компонентами (i=1,2, ..., n), являющимися равномерно распределенными случайными величинами. Индексы «i» соответствуют индексам ортов . Сделав d пробных шагов в направлении векторов (i= 1,2,..., d) и вычислив соответствующие частные производные, можно построить статистический градиент и осуществлять поиск минимума Ф() в его направлении.

В работе [7] описываются статистические аналоги методов градиента, Гаусса - Зейделя и другие способы случайного спуска.

В целом вопросы скорости сходимости методов случайного спуска исследованы недостаточно подробно. При одинаковом объеме вычислений скорость случайного поиска ниже, чем у регулярного. Методы случайного спуска целесообразно применять для нахождения минимума таких плохо организованных функций, вычисление значений которых требует небольших затрат машинного времени.