Презентация - Семенкин Е.С. Методы оптимизации

Подождите немного. Документ загружается.

Прямые методы

Классическийметодрешениявариационныхзадач, основанныйна

сведении их к дифференциальным уравнениям Эйлера, зачастую

оказывается недостаточно эффективным, несмотря на большое

теоретическоезначениеэтогометода. Хотямывиделирядпримеров,

когдауравнениеЭйлераоказывалосьвозможнымрешитьвквадратурахи

дажевэлементарныхфункциях, нодлясколько-нибудьболеесложных

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

существует, имыприходимкнеобходимостичисленнорешатьлинейную

илинелинейнуюкраевуюзадачудлядифференциальногоуравнения, что

возможно, ноотнюдьнепростоиздесьрассматриватьсянебудет.

Поэтомуестественно, чтобылиразработаныметодычисленного

решениявариационнойзадачивееисходнойпостановке, безпереходак

уравнению Эйлера; они получили название прямых методов

вариационногоисчисления.

Вразличныхразделахматематическогоанализаимеется, грубоговоря, два

основныхклассаметодовприближенногоотысканиянеизвестныхфункций:

методысужениячисластепенейсвободыиметодыдискретизации.(Конечно,

имеютсяиметодысмешанноготипа, атакженеукладывающиесявэтидва

класса). Вметодахпервогоклассанезависимыепеременныевпринципе

остаютсянепрерывными, нофункцияищетсявтомилииномспециальном

виде, включающемнесколькопараметров, которыезатемподбираютсяиз

требованиянаилучшимобразомудовлетворитьусловиямзадачи; типичными

представителямиздесьявляютсяметодинтерполяцииилиметоднаименьших

квадратов. Вболеесложныхзадачахэтиметодыпредоставляютобширноеполе

приложенияфизическойинтуицииианалитическогоискусства, таккак, если

удаетсяправильнопредвидетьформуискомогорешения, применивлишь

небольшое число параметров, и удачно выбрать критерий качества

приближения, то метод может оказаться чрезвычайно эффективным (в

частности, еслисамаисходнаязадачасодержитпараметры). Вметодахвторого

класса - ониназываютсятакжесеточными - мыссамогоначалазаменяем

искомуюфункциюнаборомеезначенийвузлахнекоторойсетки; здесь

типичными являются методы численного интегрирования обыкновенных

дифференциальных уравнений. Сеточныеметодыобычнобываютменее

специфичны (более универсальны) и более алгоритмичны, чем методы

предыдущегокласса; поэтомуониширокоприменяютсяприработенаЭВМ.

Метод Ритца для квадратичного функционала

МетодРитца, предложенныйв1908 г. немецкимфизикомиматематикомВ.Ритцем

– такжеодинизтипичныхметодовсужениячисластепенейсвободы.

Изложим его сначала на самом простом примере отыскания экстремали

функционалаприграничныхусловиях, предположив, чтофункционалквадратичный:

. (1)

Отметим, что мы здесь рассматриваем более общий - неоднородный вид

квадратичногофункционала. Включениечленовсуу' и у' неприводиткрасширению

общности, таккакихможноустранитьинтегрированиемпочастям, что, впрочем, в

конкретныхпримерахделатьнеобязательно.

МетодРитцасостоитвтом, чтоприближенноевыражениедляискомойэкстремали

строитсяввиде

(2)

где g

(x), g

(x),..., g

(x) - некоторыевыбранныефункции, тогдакакпараметры c

будутподбиратьсяизусловиястационарностизначенияфункционала (1). Функция g

(x)

обычновыбираетсяудовлетворяющейграничнымусловиям, причемжелательно, чтобы

онаповозможностилучшеизображалаискомоерешение, еслиопоследнемчто-либо

известно.(Послееевыбораиногдаделаютзамену y=g

(x)+z, чтобыперейтик

однородным граничным условиям z(a)=z(b)=0). Базисные (иначе координатные)

функции g

(x)(k=1,2,..., n) выбираютсяудовлетворяющимиоднороднымграничным

условиям,

(

)

(

)

;

тогда

при

любых

значениях

сумма

(

)

будет

dxyxRyxQyxPyI

∫

++= ])()(')([}{

∑

xgcxgy

),()(

Втеоретическихисследованияхфункции g

,...,g

составляютчастьбесконечной

системыфункций

(x), g

(x),…, g

(x), g

n+1

(x),… (3)

линейно независимой и полной в пространстве функций ,

удовлетворяющихусловиям f(а)=f(b)=0. Приэтомлинейнаянезависимостьозначает,

чтониоднаизэтихфункцийнеявляетсялинейнойкомбинациейконечногочисла

остальных, аполнота - чтолюбуютакуюфункцию f(x) можнокакугоднохорошо

приблизить (всмысле C

) линейнойкомбинациейконечногочислафункций (3). Чаще

всего, еслинеучитываетсяконкретныйвидфункционала (1), берутсясистемы

,k=1,2,3… (4)

или

, k=1,2,3,… (5)

можнопроверить, чтокаждаяизэтихсистемлинейнонезависимаяиполнаявС

Можнодоказать, чтоесли Р(х)>0 иисходнаязадачаимеетединственноерешение, то

приближенныерешения, построенныепометодуРитца, при сходятсякточному.

Условиеединственностивыполнено, например, если Q(x)≥0.

Вконкретныхприложенияхтеоремыосходимостииспользоватьзатруднительно,

онискорееимеютутешительныйхарактер. Болеереальнытеоремысдвусторонними

оценками

отличия

точного

решения

от

приближенного

;

такие

теоремы

для

метода

Ритца

];[

baCf

∈

))(()(

bxaxxxg

−

)(

sin)(

axk

−

∞

→

Припрактическомпримененииметодастремятсякегопрактическойсходимости,

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

точностью. Здесьтакжеможноиспользоватьпервыечленысистем (4) и (5) иликаких-

либоиныхсистем. Еслиудаетсяиспользоватьконкретныйвидфункционала (1), то

обычноскоростьсходимостиметодаулучшается. Например, если a=-bипосмыслу

задачирешениедолжнобытьчетнойфункцией, тоясно, чтоприприменениисистемы

(4) нужнопользоватьсятольконечетными k; ноесличетностьрешениязаранеенеясна,

тонельзяпользоватьсятолькочетнымифункциями g

(x), таккакприэтоммы

навязываемрешениюсвойствочетности, которымономоглонеобладать. Если

интуицияподсказывает, чтоточноерешениебудетгде-тоиметь «горбик», тожелательно

однуизпервыхфункций g

(x) взятьстакимгорбикомит.п.

Вариационныезадачибываютдвухтипов: можноискатьфункцию, реализующую

экстремальноеилистационарноезначениефункционала, аможноискатьисамоэто

значение функционала. Ясно, чтоискать стационарное значение выгоднее, чем

реализующуюегофункцию, таккакошибкавотысканиитакойфункциидаств

соответствующемстационарномзначенииошибкувысшегопорядкамалости (сравните

сзадачейонахождениистационарногозначенияфункцииоднойпеременной). Поэтому

желательно, когдаэтовозможно, сводитьболеесложныезадачикзадачамнаотыскание

стационарныхзначений.

Вернемсякприближенномурешению (2). Подставивеговправуючасть (1),

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

относительнопокаещепроизвольныхпараметров

(6)

).,..,,(}{

210 nkk

cccVgcgI

∑

Ясно, чтоесли, например, исходнаязадачабылазадачейоминимуме, то

желательноподобратьпараметры c

так, чтобыивыражение (6) приняломинимально

возможное значение. Это же относится и к любому стационарному значению

функционала (1), таккаквзонемедленногоизмененияфункционалаивыражение (6)

должномедленноменятьсяприизменениипараметров. Поэтомумыприходимк

системеуравнений

, k=1,2,…, n, (7)

изкоторойинадонайтипараметры c

Введемрабочееобозначение

Тогдаквадратичнаячастьфункции (6) имеетвид

, (8)

Поэтому (7) представляетсобойсистемулинейныхалгебраическихуравнений

относительно с

,…, с

ссимметрическойматрицей

, k=1,2,…, n.

0),...,,('

cccV

∫

dxxgxfxQxgxfxpgf .)]()()()(')(')([),(

iik

ccgg

∑

=1,

),(

)),((2

iik

Метод Канторовича

Этотметод, предложенныйЛ.В.Канторовичемв1933 г., представляетсобой

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

состоитвтом, чтовкачествекоэффициентовприбазисныхфункцияхберутсяне

неизвестныеконстанты, анеизвестныефункцииотнекоторойоднойпеременной. Тогда

после подстановки в функционал и применения условий стационарности (уже

вариационных!) мы получаем краевую задачу для системы обыкновенных

дифференциальныхуравненийотносительноэтихнеизвестныхфункций. Решаяэту

задачуточноиличисленно (что, покрайнеймере, влинейномслучае, т. е. для

квадратичного функционала, вполне доступно современным вычислительным

средствам), мыиполучаемприближенноерешениеисходнойвариационнойзадачи. Так

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

(оптимальностьобеспечиваетсясамойструктуройметода) удаетсязначительнолучше

приблизитьсякточномурешению, чемвметодеРитца.

Пусть

(9)

∫∫

dxdy

uyxFyxuJ ,),,,,()],([

),(|)},()(,|),{(

yxuxyxbxayxD

≤

ПрипримененииметодаРитцакфункционалу (9) выбираетсяследующаясистема

координатныхфункций:

Решение ищется в виде где С

– неизвестные

постоянные. ВметодеКанторовичавыражениедляэкстремалиберетсяввиде

(10)

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

функционал (9) достигалэкстремальногозначения. Отысканиерешенияввиде (10)

позволяетрасширитьклассэкстремалей.

Послеподстановки (10) в (9) иинтегрированияполученноговыраженияпо у

получаетсяследующийфункционал:

Функции k=1,2,…, n, должныудовлетворятьсистемеуравненийЭйлера-

Лагранжа

),(),...,,(),,(

yxyxyx

∑

kkn

yxCyxyxu

),,(),(),( ϕϕ

∑

kkn

yxxuyxu

),,()(),( ϕ

)(xu

( )

[ ]

() () () ()( )

.,...,,,...,,,

dxxuxuxuxuxyxuJ

nnn

∫

′′

Φ=

(

)

0=Φ−Φ

′

∗

(

)

yxu

∗

Метод Галеркина

Этотметодприменяетсядляотысканияприближенныхрешенийкаквариационных

задач, такикраевыхзадачдляобыкновенныхдифференциальныхуравненийи

уравненийвчастныхпроизводных, вчастности, уравненийЭйлера-Лагранжа.

Пустьнеизвестнаяфункция u(Р) удовлетворяетвнекоторойобласти D следующей

краевойзадаче:

на y (y-граница G). (11)

Здесь L-некоторыйлинейныйдифференциальныйоператор, Г - линейный

операторграничныхусловий. Приближенноерешениекраевойзадачи (11) ищетсяв

видесуммы

где с

- неопределенныекоэффициенты, (P)—системалинейнонезависимых

непрерывнодифференцируемыхфункций, удовлетворяющиходнороднымкраевым

условиям

Обозначим

невязку

∈

(

))

(

))

(

∑

kkn

PcPu

),()( ϕ

).())(( pfPuLf

−

Коэффициенты с

определяютсяизусловияортогональностивобласти D невязки .

кфункциям , k=1,2,…,n.

,k=1,2,…, n. (12)

Таккакоператор L линеен, то (12) запишетсявканоническомвиде, удобномдля

вычислений с

иливвиде

где .

)(P

∫

−

dPPPfPuL 0)()]())(([

dPPPfdPPPLc

)()()())((

ϕϕϕ

∫

∑

∫

dPPPfdPPPfc

)()()()(

ϕϕ

∫

∑

∫

))(()( PLPf

≡