Парадигма развития науки. Методологическое обеспечение (стр. 86 )

Решение эволюционной задачи на ограниченном интер­вале времени, как и задачи Коши, сводится к последовательной перестройке начального ус­ловия шагами во времени; для этого разработаны разнооб­разные эффективные методы. Решение стационарной задачи после дискретизации координат приводится к решению системы конечных уравнений, число которых равно числу узловых точек в области, где строится решение, т. е. обычно достаточно велико. (Кстати, подобные системы воз­никают и при решении эволюционных задач, если применя­ются неявные методы.) Существует большое число методов решения таких систем. Укажем на интересный класс методов: чтобы найти решение уравнения стационар­ного состояния, строится такое эволюционное уравнение, для которого заданное состояние получается в результате установления, т. е. при t→∞; построенное уравнение решается шагами по времени, пока решение практические не уста­новится.

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

Численное решение уравнений с частными производ­ными описано во многих книгах.

3.6.13. Задачи на экстремум с конечным числом степеней свободы

Как уже указывалось, при математическом моделировании широко применяются задачи на экстремум.

Эти задачи можно условно подразделить на два класса: задачи с конечным числом степеней свободы, для которых искомыми являются точка экстремума и экстремальное значение функции конечного числа аргументов, и задачи на экстремум функционала, в которых искомой является функ­ция. (Для задач второго класса обычно говорят о целевом функционале.) Мы будем рассматривать только задачи на минимум, так как задачи на максимум сводятся к ним переменой знака у целевой функции.

Отыскание минимума функции одного аргумента, т. е. решение задачи

для функций f простого вида можно осуществить с помощью решения уравнения и исследования знака f'. Для более сложных функций f бывает проще вычислять после­довательные значения с доста­точно малым шагом h и сравнивать их друг с другом. Найдя точку минимума на выбранной сетке, можно для уточнения провести аналогичную процедуру на интервалах длины h, примыкающих к этой точке, но существенно уменьшив шаг, и т. д. Имеются способы, позволяющие ускорить этот процесс.

Минимизацию функцииаргументов поясним, взяв п = 3:

(1)

Наиболее ясен случай, когда функция f определена при всех значениях своих аргументов и непрерывна вместе со своими частными производными; тогда обычно применяется один из методов спуска. Так, метод наискорейшего спуска основан на том, что антиградиент функции f, т. е. вектор - grad f с проекциями

указывает направление наибыстрейшего убывания этой функции в точке (х, у, z). Отправляясь от некоторой началь­ной точки по направлению антиградиента в ней и следя вдоль (прямой) линии движения за значением функции f, т. е. переходя к функции одного аргумента

мы можем найти точку в которой функция f минимальна вдоль этой линии. Затем мы отправляемся от точки по направлению антиградиента в ней, т. е. вновь переходим к функции одного аргумента

и т. д. (Множители k1 вводятся для того, чтобы при при­ближении к точке минимума движение не слишком замед­лялось; например, можно положить

Применяются и другие методы спуска: покоординатный спуск, спуск по случайным направлениям и др. Направление спуска может и непрерывно подправляться: так, в методе градиентного спуска мы задаемся малым шагом h и пере­ходим от точки к точке по формулам

Известны многочисленные варианты этих методов, приспо­собленные к решению различных классов задач.

Функция f может иметь несколько локальных миниму­мов, а данный метод приводит лишь к одному из них, быть может, не самому глубокому. Для поиска более глубокого минимума можно попробовать повторить процесс несколько раз, начиная с различных точек М0. Однако достаточно представительный выбор таких точек можно получить, толь­ко если число аргументов не слишком велико — скажем, порядка 10 или менее (чем меньше, тем лучше). Впрочем, выбор М0 вблизи от искомой точки минимума позволяет увеличить число аргументов и существенно ускорить проце­дуру. Поэтому неформальные обсуждения и прикидки, поз­воляющие хотя бы грубо нащупать искомую точку, весьма желательны.

Ecли задача на минимум содержит параметр, то можно, найдя точку минимума при некотором начальном значении параметра, последовательно ее перестраивать, совершая ша­ги по параметру наподобие. Впрочем, при таком про­должении точка минимума может для некоторого критичес­кого значения параметра пропасть; кроме того, если рас­сматриваемый минимум был первоначально самым глу­боким, то в процессе продолжения он может перестать быть таковым.

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

(2)

так что полная задача имеет вид (1), (2). В ней остается 3 — 1=2 степени свободы. Наиболее благоприятен слу­чай, когда совокупность уравнений связи можно заменить эквивалентным параметрическим представлением аргумен­тов. Для задачи (1), (2) это означает, что переменные х, у, z, удовлетворяющие уравнению (2), можно пред­ставить в виде

Тогда рассматриваемая задача сведется к задаче на безус­ловный минимум

к которой можно применить указанные выше методы.

Однако чаще такой переход осуществить не удается и тогда приходится проводить спуск в пространстве аргументов вдоль поверхности (S), определенной уравнением (2) (в общем случае — вдоль многообразия, определенного сово­купностью уравнений связи). Так, в градиентном методе мы, отправляясь от точки совершаем шаг по направлению — получаем точку приближенно проецируя которую на (S) (для этого приходится приближенно решить конечное уравнение

находим точку Далее проделываем ту же процедуру, отправляясь от точки и т. д.

В качестве математических моделей широко распространились задачи на экстремум с ограни­чениями, т. е. задачи, в которых аргументы целевой функ­ции связаны конечными неравенствами (высвобождающи­ми связями), число которых в отличии от уравнений связи может быть любым. Рассмотрим для определенности задачу (1), в которой аргументы связаны неравенствами

(3)

и обозначим (V) (трехмерную) область в пространстве х, у, z, определенную этими неравенствами. Пока оба они являются строгими, мы можем пользоваться градиентным методом в простейшем варианте. Но пусть после очередного шага одно из неравенств (3), например первое, оказалось нарушенным. Это означает, что точка вышла за пределы (V) и потому ее нужно спроецировать на поверхность этой области. При дальнейших шагах, пока вектор - grad f направлен из (V) (что распознается по знаку h1, мы производим проецирование точек на эту поверхность, как при отыскании условного экстремума. Мо­жет оказаться, что через какое-то число шагов век­тор - grad f будет направлен внутрь (V) и тогда при даль­нейшем спуске неравенства (3) становятся строгими, т. е. связь снимается (во всяком случае, до следующего выхода на границу). Но может получиться и так, что при спуске по поверхности h1 = 0 мы приходим к точке, где и второе неравенство (3) нарушено. Тогда надо ее спроецировать на ребро и в дальнейшем в соответствии с направлением вектора - grad f спускаться либо по этому ребру, либо по примыкающим к нему граням Для выбора того, по какому именно многообразию надо идти, здесь и в общем случае имеется алгоритм, определяе­мый так называемой теоремой Куна — Такера и содер­жащийся в курсах нелинейного программирования.