Беллман Р. Прикладные задачи динамического программирования (2013) (1246769), страница 38
Текст из файла (страница 38)
(5.20) Чтобы установигь это, нам достаточно положить д(х) = = гчт — гРгег Ых. Тогда подынтегральная функция в (5.19) будет полным квадратом, откуда следует (5.20). Однако, как указывалось выше, мы в действительности рассматриваем не все возможные д(х), а только те, которые имеют производные, более того, только те функции, производные которых ведут себя достаточно хорошо, настолько, что имеют смысл выписанные интегралы. Поскольку нам заранее не известен вид решения, нет никакой гарантии, что функция Рт — г)гч,: ах— допустимая.
Тем не менее в одном из основных результатов вариационного исчисления (яосновная лемма вариационного исчисления») установлено, что если (5.19) выполняется для всех допустимых д(х), то имеет место урзвнение (5.20). Строгие формулировки этих вариационных задач и подробные доказательства перечисленных результатов можно найти н стандартных руководствах, перечисленных в конце главы. Мы не будем здесь углубляться далее в предмег, поскольку, как мы увидим ниже, имеюгся разные пути обхода ряда вопросон строгого обоснования.
Уравнение (5.20) в раскрытом виде предсгавляег собой уравнение вгорого порядка, оказываюшееся, за исключением легко определяемых случаен, нелинейным. Оно называется уравненггелг Эйлера вариационной задачи н является необходимым условием, полностью аналогичным условию, которое получается в конечномерном случае, когда приравнивают нулю первые производные.
Лишь в редких случаях удается получить точное аналитическое решение этого уравнения в элементарных функциях анализа. Классические примеры можно найти в ссылках, дак. ных в конце главы. 240 (гл. в Влгилционпов исчислении 4. НЕОБХОДИМЫЕ УСЛОВИЯ Как и в анализе, для минимизируюгцей и максимизируюшей функций, а также для функций, дающих точки стационарности более сложной природы, получается одно и то же уравнение. Правила для различения этих случаев до некоторой степени извесп<ы, но общая картина весьма туманна.
Двумя наиболее важными условиями минимума являются: Условие Вейерштрасса. Пусть г(х) — функция, отличная от экстремальной функции у (х), а г (х) — ее производная. Тогда должно выполняться неравенство Р(х, у, г') — Р(х, у, у') — (г' — у')Рх (х, у, у')~0. (о.21) Левая часть этого неравенства называется В-функцией Вейерштрасса. Условссе Лежандра. Для того чтобы у(х) была минимизирующей функцией, должно выполняться неравенство Рхч (х, У, У') (5.22) что в анализе соответствует обычному условию на вгорую производную.
Эти условия, не являющиеся интуитивными с точки зрения классического вариационного подхода к проблемам оптимизации, как будет показано ниже, логически и просто вытекают из подхода с точки, зрения динамического программирования. б. ЕСТЕСТВЕННЫЕ ГРАНИЧНЫЕ УСЛОВИЯ Иногда в вариационных задачах на экстремальную функцию налагают условия на концах вида 6(у(а), у'(а)) =О, ст'(у(Ь), у'(Ь)) = О.
(о 23) Чаше ограничение задается на левом конце интервала, а условие на правом конце включается в саму вариационную задачу. Обратившись к уравнению (0.19), мы видим, что, если у должно принимать в точках а и Ь фиксированные значения, то разумно требовать, чтобы в (х) в этих точках обращалась в нуль. С другой стороны, если у определена только в точке Ь или вообще не определена, то вариация функции а(х) в точке нвдостатки влвилциоп«ого исчислвния 241 7! х=а приводит к соотношению (5.24) се=О при х=а. Это последнее условие называется естественным граничны.н услоаиелг. й. ИЗОПЕРИМЕТРИЧЕСКИЕ ЗАДАЧИ Часто мы сталкиваемся с задачей максимизации или минимизации функционала !(у) при интегральном ограничении вида Ь ') 0 (у, у", х) <Тх = с<, (5.25) а $)Р(у, у', х) — Л0(у, у', х))а<х.
а (5.26) Таким образом мы получаем видоизмененное уравнение Эйлера (Р— Л0)г — — (Ре — Л0х ) = О, (5,27) где Л вЂ” пос<оянная, ко<орая подлежит определению с помощью соотношения (о.25). Как будет показано ниже, этот результат следует также пз метода функциональных уравнений динамического програмл<ирования.
По-видимому, довести решение задачи такого рода до самого конца — депо не простое. 7. НЕДОСТАТКИ ВАРИАЦИОННОГО ИСЧИСЛЕНИЯ Трудности, которые мы перечисляли в связи с применением знализа при рассмотрении конечпомерных задач оптимизации, как и следовало ожидать, имеют место и в этих более трудных вариационных задачах над пространствами функций, и пригом в более сложных формах. что в приложениях обычно ознзчает ограниченность некоторого ресурса. При разных условиях можно показать, что, как и в обычном анализе, мы л<ожем применить лсножителп Лагранжа и рассматривать новую задачу отыскания экстремума функционала 242 влгизционное исчислений ~гл.
ч После первоначальной сз адин развития вариационпого исчисления, связанной с именами Эйлера, Вагранжа, Вейерштрасса, Гильберта, Больна, Блисса и других, этот предмет в гораздо большей степени был пригоден для изложения в учебниках, чем для практического использования.
Разумеется, трудно было надеяться на получение какого-либо решения более приятного вида, чем решение, даваемое дифференциальным уравнением Эйлера. А потому последующие работы были посвящены приданию дальнейшей строгости известному формальному аппарату и привели к получению различных необходимых и достаточных условий для разных типов экстремумов, а также к расширению класса функционалов, к которым можно было бы применить этот аппараг. Некоторое значение придавалось проблеме получения численных результа~ов, но основной упор делался на теоремы существования и единственности. Однако появление быстродействуюпгих вычислительных машин сильно повлияло на математическое мышление.
Имея в распоряжении такое мощное орудие, мы теперь оцениваем аналитический аппарат не только с точки зрения его изящества, но также со стороны его вычислительной осущесавимости. К сожалению, именно с этой точки зрения оп весьма неудовлетворителен, В действительности имеется несколько различного родэ трудностей, связанных с классической формулировкой вариационных вопросов. Некоторые из них вытекаюг из самой вариационной задачи, а некоторые — из уравнения Эйлера.
Рассмотрим сначала вопрос о численном решении уравнения Эйлера. Как указывалось выше, это в большинстве случаев нелинейное уравнение. Кроме того, это нелинейное уравнение с граничными условиями в двух точках. Чгобы понягь аначение э~ого последнего утверждения, рассмо~рим вкратце, что требуешься для численного решения дифференциального уравнения. Поскольку вероятность получения удобного анзлитического решения пренебрежимо мзла, для численных рзсчетов мы должны прибегнуть к помощи мзшин-аналогов, включающих использование методов Монте-Карло, или же к помощи цифровых вычислительных машин. В большинстве случзев Следует использовать цифровую вычислительную машину.
71 недостатки втггкыгионного исчисления 24з Так как вычислительная машина производит только обычные арифметические операции, приходится преобразовать рассматриваемое уравнение к виду, требующему только использования этих операций и не содержащему каких-либо трансцендентных операций, таких, как дифференцирование или интегрирование. Это значит, что мы должны приближаться к интегралам с помощью сумм, а к производным с помощью разнос~ей. Такое приближение можно сделать бесконечным числом способов, требующих тщательного взвешивания факторов точности, устойчивости и времени.
Все это, конечно означает, что в настоящее время численный анализ является, скорее искусством, чем наукой. Избегая всех тонких де~алей, неизбежно входящих в любой конкретный вычислительный процесс, изложим общую идею решения дифференциального уравнения с помощью счетной машины. В заданном уравнении у' = у(х, у), у (х,) = с, (5.28) (задаче с заданным начальным значеннелг) заменяем производную приближенным выражением вида у'(х) ('( + или (5.29) у'(х) ~у(х+ а) — у(х — а)] При использовании первого представления (в некотором смысле худшего из возможных) дифференциальное уравнение (5.28) заменится следующим разностным уравнением: + ) у( )=у(х, у), у(хь)=с, где х предполагается теперь принимающим только значения х„, х, + Ь, хя+ 25, х,+ 35 и так далее.
Задавая начальное значение у(х,), мы вычисляем по формуле (5.30) значение у(ха+ Ь). Далее с помощью найденного зна ~ения у(ха+ 5) по этой формуле определяется значение у при х=хь+2Ь и т. д. Такого типа итеративный алгоритм идеально подходит для цифровой машины, так как здесь требуется только последовательное повторение одной и той же операции. Следовательно, для выполнения всего процесса достаточно одного набора команд. вхяилционнов исчислвния !гл. ч Выбор Ь зависит от требуемой точности и от времени, отведенного на вычисления.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
