Математическая энциклопедия - вариационное исчисление

численные методы раздел вычислительной математики, посвященный методам отыскания экстремальных значений функционалов.

Численные методы В. и. принято разделять на два больших класса: непрямые и прямые методы. Непрямые методы основаны на использовании необходимых условий оптимальности (см. Вариационное исчисление, Эйлера уравнение, Вейерштрасса условия, Трансверсальности условие, Понтрягина принцип максимума), с помощью к-рых исходная вариационная задача сводится к краевой задаче. Поэтому вычислительные достоинства и недостатки непрямых методов полностью определяются свойствами соответствующей краевой задачи. Прямые методы ориентированы на непосредственное отыскание экстремума функционала. Используемые при этом методы оптимизации являются развитием идей математнч. программирования.

Разделение численных методов В. и. на прямые и непрямые весьма условно. Нек-рые алгоритмы используют элементы обоих подходов. Кроме того, существуют методы, к-рые непосредственно не относятся к двум выделенным классам. Например, методы, основанные на достаточных условиях оптимальности, образуют самостоятельную группу.

Первые численные методы В. и. появились в работах Л. Эйлера (L. Euler). Однако наибольшее развитие они получили с 50-х гг. 20 в. в результате распространения вычислительной техники и открывшейся в связи с этим возможностью решения сложных технич. задач. При этом разработка численных методов В. и. шла в основном применительно к задачам теории оптимального управления наиболее важного для практич. приложений раздела В. и. (см. Оптимального управления математическая теория).

Непрямые методы. С появлением принципа максимума Понтрягина (1956) сведение вариационных задач к краевым стало особенно популярным.

Пусть в задаче оптимального управления требуется найти траекторию и управление , доставляющие минимум функционалу

при дифференциальных связях:

граничных условиях:

и ограничениях на управление:

где векторы фазовых координат и управлений, , замкнутое множество m-мерного пространства, t - независимое переменное (время).

Согласно принципу максимума Понтрягина, оптимальное управление должно при каждом tдоставлять абсолютный максимум Гамильтона функции

где определяется системой уравнений

Из условия (6) находится управление и подставляется в (2) и (7). В результате получается замкнутая краевая задача для системы 2n дифференциальных уравнений (2) и (7) с 2n граничными условиями (3) и (4).

Наиболее распространенной схемой численного решения этой краевой задачи является схема, использующая метод Ньютона с дроблением шага (см. [3]). При этом вводится вектор невязки

где значение получается из решения задачи Коши для системы (2), (7) с начальными условиями (3) и Невязки (8) рассматриваются как функции от неизвестных к-рые определяются из системы уравнений

Решение системы (9) проводится Ньютона методом;используемые при этом частные производные

определяются численно по формуле

где значения получаются путем решения задачи Коши для системы (2), (7) с начальными условиями (3) и условпями

малое приращение величины .

Для определения частных производных известен более точный, но громоздкий метод (см. [4]), в к-ром используется интегрирование системы 2n уравнений в вариациях для системы (2), (7).

Трудности в использовании метода Ньютона связаны, во-первых, с проблемой выбора удачного начального приближения для и, во-вторых, с неустойчивостью задачи Коши, к-рая особенно сильно проявляется на больших интервалах . Для преодоления первой трудности не существует универсального подхода. Для преодоления неустойчивости задачи Коши имеется ряд приемов (Коши задача;численные методы).

В тех случаях, когда граничные условия и функционал заданы в более общем виде, чем в (3), (4) и (1) [напр., Больца задача с подвижными концами, вариационная задача со свободными (подвижными) концами], к необходимым условиям оптимальности (6), (7) добавляются трансверсальности условия. После исключения входящих в эти условия произвольных постоянных получаются замкнутая краевая задача и отвечающая ей система уравнений типа (9).

Решение системы (9) может отыскиваться любым другим методом, применяемым для решения нелинейных систем.

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

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

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

рассматривается на непрерывных ломаных x(t), удовлетворяющих заданным граничным условиям

и состоящих из Nпрямолинейных отрезков с заданными абсциссами концов. Таким образом, функционал превращается в функцию от ординат вершин этих ломаных, а исходная задача в задачу минимизации функции многих переменных (см. Эйлера метод).

Из-за сложности подобных задач для ручного счета прямые методы долгое время оставались в стороне от традиционных исследований по В. и. Интерес к ним вновь возрос в нач. 20 в. Были предложены новые способы редукции к задаче об отыскании экстремума функции многих переменных. Наиболее важным из них является Ритца метод, согласно к-рому решение задачи о минимуме (10) при условии (11) разыскивается на классе функций вида

где элементы бесконечной полной системы линейно независимых функций, удовлетворяющих граничным условиям

Задача сводится к отысканию минимума функции Nпеременных

Метод Ритца является достаточно общим. Он применяется для решения вариационных задач математич. физики, заключающихся в минимизации функционала, зависящего от функций многих переменных. Его дальнейшим обобщением для данного класса задач является метод (см. [2]), в к-ром коэффициенты считаются неизвестными функциями одного из независимых переменных (напр., если в задаче две независимые переменные tи , то а,могут задаваться в виде ). Исходный функционал становится зависящим от Nфункций , к-рые могут определяться с помощью необходимых условий, т. е., в конечном счете, из решения краевой задачи для системы Nуравнений Эйлера.

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

Методы спуска в пространстве управлений основаны на получении последовательности управлений вида

к-рой соответствует монотонно убывающая последовательность значений функционала. Пусть, напр., ищется минимум функционала

при условиях (2), (3) и (5) (U - выпуклое и односвяз-ное множество). Отыскание производится следующим образом. С помощью уравнений в вариациях для (2) и сопряженной системы (7) с условиями на правом конце

линейная часть приращения функционала (13) от вариации представляется в виде

Для уменьшения функционала (13) следует на каждой итерации выбирать приращение

где величина вычисляется на управлении и соответствующей ему траектории . Законность линеаризации, а следовательно, и уменьшение функционала (13) обеспечиваются выбором достаточно малой величины . Процесс спуска (12) начинается с нек-рого и заканчивается, когда на нек-рой итерации становится меньше нек-рого заданного Для описанного случая свободного правого конца алгоритм получается наиболее простым (см. [5], [6], [7]). Весьма эффективным для решения задач со свободным концом является метод (см. [8]), к-рый не использует линеаризации исходной задачи. В случае, когда граничные условия заданы и на правом конце, все эти алгоритмы существенно усложняются. Для учета граничных условий в [5] привлекается процедура проектирования градиента, а в [6] вводится штраф за невыполнение граничных условий, т. е. вместо (13) рассматривается функционал

К градиентным методам примыкает метод [9], в к-ром приращение управления определяется из решения вспомогательной задачи линейного программирования. Большая группа прямых методов численного решения задач оптимального управления овнована на идеях последовательного анализа вариантов.,(см. [10], [11], [12]). Важным достоинством этих методов является то, что с их помощью удается решать задачи с фазовыми ограничениями вида

где С замкнутое множество n-мерного пространства. Их основной недостаток существенное возрастание трудностей с увеличением размерности пространства. Эти методы используют редукцию исходной задачи к задаче нелинейного программирования специального вида. Распространены два способа такой редукции. Согласно первому способу в конечном итоге получается задача минимизации функции, зависящей только от управлений, заданных в точках дискретной сетки на оси (см. [13]), Во втором способе (см. [12]) управление исключается и задача сводится к минимизации функции вида