Применение Принципа Лагранжа для построения оптимальных алгоритмов решения линейных обратных задач математической физики (1104487), страница 3
Текст из файла (страница 3)
Òàêæå áóäåì ñ÷èòàòü, ÷òî âìåñòî îïåðàòîðà A ìûóìååì òî÷íî âû÷èñëÿòü ëèøü ëèíåéíûé îïåðàòîð F : Z → Y , ÿâëÿþùèéñÿ ïðèáëèæåíèåì äëÿ îïåðàòîðà Qm A. Ïóñòü â çàäà÷å èçâåñòíî âûïóêëîåóðàâíîâåøåííîå ïîäìíîæåñòâî O ⊂ Y , òàêîå ÷òîO ⊃ Ω + (Qm A − F )(M ).Ëåãêî ïðîâåðèòü, ÷òî v − F z̄ ∈ O. Ýòî ìîæíî èíòåðïðåòèðîâàòü ñëåäóþùèì îáðàçîì: ñ÷èòàåì, ÷òî îïåðàòîð Qm A èçâåñòåí òî÷íî è ðàâåí F , àïðàâàÿ ÷àñòü îáðàòíîé çàäà÷è èçâåñòíà ñ ïîãðåøíîñòüþ, çàäàâàåìîé óæå íåìíîæåñòâîì Ω, à ìíîæåñòâîì O. Âñþ èíôîðìàöèþ î ïîãðåøíîñòè çàäàíèÿîïåðàòîðà A è ïðàâîé ÷àñòè ū îáúåäèíèì â ìíîæåñòâî O.Èòàê, ñ÷èòàåì, ÷òî â îáðàòíîé çàäà÷å ïîèñêà ýëåìåíòà z̄ èçâåñòíû ìíîæåñòâî M ⊂ Z , îïåðàòîð F : Z → Y , âåêòîð v ∈ Y è ìíîæåñòâî O ⊂ Y ,òàêèå ÷òîz̄ ∈ M,v − F z̄ ∈ O.(3)Ýòó ïîñòàíîâêó îáðàòíîé çàäà÷è áóäåì íàçûâàòü ñýò-ïîñòàíîâêîé îáðàòíîé çàäà÷è. êà÷åñòâå îòâåòà çàäà÷è èìååò ñìûñë òðåáîâàòü ëèøü êîíå÷íûé íàáîð÷èñåë.
Ðàçîáü¼ì çàäà÷ó èõ ïîèñêà íà íåñêîëüêî çàäà÷ ïîèñêà îäíîãî ÷èñëà.Ýòè çàäà÷è ñôîðìóëèðóåì â âèäå ñëåäóþùåé çàäà÷è: íàéòè ïðèáëèæåíèåäëÿ ÷èñëà `(z̄), ãäå ` ëèíåéíûé ôóíêöèîíàë íà Z . Âìåñòî ïîèñêà ýëåìåíòà z̄ èç óñëîâèé (3) áóäåì ðåøàòü çàäà÷ó îïòèìàëüíîãî âîññòàíîâëåíèÿôóíêöèîíàëà ` ïî èíôîðìàöèè (M, F, O), à èìåííî, ïóñòü èçâåñòíû ôóíêöèîíàë `, ìíîæåñòâî M , îïåðàòîð F è ìíîæåñòâî O, à òðåáóåòñÿ íàéòèðåøåíèå òàêîé ýêñòðåìàëüíîé çàäà÷è:sup|h`, zi − ϕ(y)| → min,ϕz∈M,y∈Y : y−F z∈Oϕ ∈ Y ∗.(4)Ìíîæåñòâî M íàçûâàåòñÿ ìíîæåñòâîì àïðèîðíûõ îãðàíè÷åíèé, îïåðàòîðF íàçûâàåòñÿ èíôîðìàöèîííûì îïåðàòîðîì, ìíîæåñòâî O íàçîâ¼ì îêðåñòíîñòüþ ïîãðåøíîñòè.
Ýëåìåíò ϕb, íà êîòîðîì äîñòèãàåòñÿ ìèíèìóì â çàäà÷å (4) íàçûâàåòñÿ ìåòîäîì îïòèìàëüíîãî âîññòàíîâëåíèÿ, à çíà÷åíèåìèíèìóìà â ýòîé çàäà÷å íàçûâàåòñÿ ïîãðåøíîñòüþ îïòèìàëüíîãî âîññòàíîâëåíèÿ è îáîçíà÷àåòñÿ E(`, M, F, O). Ëþáîå îòîáðàæåíèå ϕ : Y → Ríàçûâàåòñÿ ìåòîäîì âîññòàíîâëåíèÿ â çàäà÷å (4). Âûðàæåíèå, ìèíèìèçèðóåìîå â çàäà÷å (4), íàçûâàåòñÿ àïðèîðíîé ïîãðåøíîñòüþ ìåòîäà âîññòàíîâëåíèÿ ϕ è îáîçíà÷àåòñÿ E(`, M, F, O, ϕ). Åñëè ` è F ëèíåéíû, à M è O9âûïóêëû è óðàâíîâåøåíû, òîE(`, M, F, O) = infY E(`, M, F, O, ϕ),ϕ∈RÝòî ñëåäóåò, íàïðèìåð, èç [15].
 êà÷åñòâå ïðèáëèæåíèÿ äëÿ ÷èñëà `(z̄)âîçüì¼ì ÷èñëî ϕ(v)b . Òîãäà ïîãðåøíîñòüþ ýòîãî ïðèáëèæåíèÿ áóäåò ÷èñëîE(`, M, F, O).Çàäà÷åé, àññîöèèðîâàííîé ê çàäà÷å (4), íàçûâàåòñÿ ñëåäóþùàÿ çàäà÷à:h`, zi → max,(z,y)(z, y) ∈ Z × Y,z ∈ M,y − F z ∈ O,y = 0.(5) äèññåðòàöèè äîêàçàíà òåîðåìà ñóùåñòâîâàíèÿ ðåøåíèÿ àññîöèèðîâàííîéçàäà÷è. Ñôîðìóëèðóåì å¼.Òåîðåìà. Ïóñòü Z íîðìèðîâàííîå ïðîñòðàíñòâî, Y = Rm , ` ∈ Z ∗ ,ìíîæåñòâî M ⊂ Z ñëàáî ñåêâåíöèàëüíî êîìïàêòíî â Z , ëèíåéíûé îïåðàòîð F : Z → Y íåïðåðûâåí, ìíîæåñòâî O ⊂ Y âûïóêëî è çàìêíóòî.Òîãäà ñóùåñòâóåò ðåøåíèå çàäà÷è (5).Ñôîðìóëèðóåì Ïðèíöèï Ëàãðàíæà, äîêàçàííûé â [16].Òåîðåìà (Ïðèíöèï Ëàãðàíæà äëÿ çàäà÷è îïòèìàëüíîãî ñâîññòàíîâëåíèÿ).
Ïóñòü M è O âûïóêëû è óðàâíîâåøåíû, ôóíêöèîíàë ` è îïåðàòîð F ëèíåéíû. Îïðåäåëèì ôóíêöèþ Ëàãðàíæà L : (Z × Y ) × Y ∗ → R,defL((z, y), λ) = −h`, zi + hλ, yi. Åñëè ýëåìåíò (bz , 0) ∈ Z × Y ÿâëÿåòñÿ äîïóñòèìîé òî÷êîé â çàäà÷å (5) (ò.å. zb ∈ M è −F zb ∈ O), òîãäà1. ñëåäóþùèå äâà óñëîâèÿ ýêâèâàëåíòíû:à) (bz , 0) ÿâëÿåòñÿ ðåøåíèåì çàäà÷è (5);b ∈ Y ∗ : L((bb =b;á) ∃λz , 0), λ)infL((z, y), λ)z∈M,y∈Y : y−F z∈O2.
ïðè âûïîëíåíèè ýòèõ äâóõ ýêâèâàëåíòíûõ óñëîâèé ëèíåéíûé ôóíêöèb ÿâëÿåòñÿ ìåòîäîì îïòèìàëüíîãî âîññòàíîâëåíèÿ â çàäà÷åîíàë ϕ = λ(4), è åãî ïîãðåøíîñòü òàêîâà: E(`, M, F, O) = h`, zb i.Àðãóìåíò λ ôóíêöèè Ëàãðàíæà íàçûâàåòñÿ ìíîæèòåëåì Ëàãðàíæà. òðåòüåé ãëàâå ïðåäëîæåí àëãîðèòì ðåøåíèÿ ëèíåéíûõ îáðàòíûõ çàäà÷ ñ âûïóêëûìè è óðàâíîâåøåííûìè ìíîæåñòâîì àïðèîðíûõ îãðàíè÷åíèé è îêðåñòíîñòüþ ïîãðåøíîñòè. Îáðàòíàÿ çàäà÷à (3) ñâîäèòñÿ ê çàäà÷åîïòèìàëüíîãî âîññòàíîâëåíèÿ (4), äëÿ èññëåäîâàíèÿ êîòîðîé ïðèìåíÿþòñÿòåîðåìû, ïðèâåä¼ííûå â ïðåäûäóùèõ ãëàâàõ. Îñíîâíóþ ðîëü â èññëåäîâàíèè çàäà÷ èãðàåò Ïðèíöèï Ëàãðàíæà.Ïðîñòðàíñòâî Z â çàäà÷å (2) âî ìíîæåñòâå ñëó÷àåâ áûâàåò áåñêîíå÷íîìåðíûì.
Äëÿ ðåàëèçàöèè ÷èñëåííûõ àëãîðèòìîâ èñõîäíóþ çàäà÷ó ìîæíîñâåñòè ê çàäà÷å, ãäå âìåñòî ïðîñòðàíñòâà Z è åãî ïîäìíîæåñòâà M ïðèñóòñòâóþò èõ êîíå÷íîìåðíûå àíàëîãè. Ýòî íàïðàâëåíèå áûëî ïðèíÿòî àâòîðîì10çà îñíîâíîå íàïðàâëåíèå ïîèñêà àëãîðèòìîâ ðåøåíèÿ çàäà÷è îïòèìàëüíîãî âîññòàíîâëåíèÿ.  ðåçóëüòàòå óäàëîñü ïîñòðîèòü àëãîðèòì íàõîæäåíèÿìåòîäà è ïîãðåøíîñòè îïòèìàëüíîãî âîññòàíîâëåíèÿ äëÿ âåñüìà øèðîêîãîêëàññà ëèíåéíûõ çàäà÷. Ê òîìó æå ýòîò êëàññ çàäà÷ îõâàòûâàåò àáñîëþòíîå áîëüøèíñòâî ïðàêòè÷åñêèõ çàäà÷ ìàòåìàòè÷åñêîé ôèçèêè. Åñëè áûòüòî÷íûì, òî áûëè íàéäåíû íå ìåòîä è ïîãðåøíîñòü îïòèìàëüíîãî âîññòàíîâëåíèÿ, à ìåòîä, ïîãðåøíîñòü êîòîðîãî ñêîëü óãîäíî áëèçêà ê ïîãðåøíîñòèîïòèìàëüíîãî âîññòàíîâëåíèÿ. Äëÿ ðåøåíèÿ çàäà÷è ïî ïóòè êîíå÷íîìåðíîé àïïðîêñèìàöèè æåëàòåëüíî óñòàíîâèòü ñâÿçü ðåøåíèé èñõîäíîé çàäà÷èè å¼ êîíå÷íîìåðíîãî àíàëîãà. Àíàëèç ýòîé ñâÿçè âïåðâûå ïðîâåä¼í â [29].Âàðèàíòû àëãîðèòìîâ ðåøåíèÿ çàäà÷è îïòèìàëüíîãî âîññòàíîâëåíèÿ â êîíå÷íîìåðíûõ ïðîñòðàíñòâàõ áûëè ïðåäëîæåíû â [29, 28].
Ðåçóëüòàòû ýòèõðàáîò ïðåäñòàâëåíû â òðåòüåé ãëàâå.Îïèøåì èñïîëüçóåìóþ ñõåìó êîíå÷íîìåðíîé àïïðîêñèìàöèè. Åñëè ïðîñòðàíñòâî Z êîíå÷íîìåðíî, òî íèêàêîãî ñâåäåíèÿ ê çàäà÷å â êîíå÷íîìåðíîìïðîñòðàíñòâå íå òðåáóåòñÿ. Äàëåå â îïèñàíèè ñîäåðæàíèÿ òðåòüåé ãëàâû áóäåì ñ÷èòàòü, ÷òî ïðîñòðàíñòâî Z áåñêîíå÷íîìåðíî. Çàìåíà ïðîñòðàíñòâàZ íà íåêîòîðûé êîíå÷íîìåðíûé àíàëîã ìîæåò áûòü ïðåäñòàâëåíà â âèäåäåéñòâèÿ ëèíåéíîãî îïåðàòîðà. Ðàññìîòðèì ïàðó ëèíåéíûõ ïðîñòðàíñòâ Zè Rn , ãäå n ∈ N, è ïàðó ëèíåéíûõ îïåðàòîðîâ Pn : Z → Rn è Ln : Rn → Z .Îïåðàòîð Pn ñîïîñòàâëÿåò ýëåìåíòó èç Z åãî êîíå÷íîìåðíûé àíàëîã, àîïåðàòîð Ln ïî êîíå÷íîìåðíîìó âåêòîðó ñòðîèò áåñêîíå÷íîìåðíûé âåêòîðïðîñòðàíñòâà Z .
Ðàññìîòðåíèå ïðîèçâîëüíûõ îïåðàòîðîâ Pn è Ln ÿâëÿåòñÿáåññìûñëåííûì, ïîýòîìó ââåä¼ì óñëîâèÿ, ñâÿçûâàþùèå ýòè îïåðàòîðû ñäðóãèìè ïàðàìåòðàìè çàäà÷è:∃κ n ∈ (Rn )∗ : ` = κ n ◦ Pn ,(6)Ln Pn (M ) ⊂ M,(7)Pn Ln = 1̂Rn ,(8)ãäå 1̂Rn åäèíè÷íûé îïåðàòîð â Rn .Ïðåäïîëîæèì, ÷òî ìû óìååì âû÷èñëÿòü ëèíåéíûé îïåðàòîð A0 : Z →U , ÿâëÿþùèéñÿ ïðèáëèæåíèåì äëÿ îïåðàòîðà A èç çàäà÷è (2). Îáîçíà÷èìdefdefB = Qm A0 Ln è Mn = Pn (M ), ò.å. B : Rn → Rm è Mn ⊂ Rn . Ýòî êîíå÷íîìåðíûå àíàëîãè îïåðàòîðà F è ìíîæåñòâà M . Ðàññìîòðèì âñïîìîãàòåëüíóþ çàäà÷ó îïòèìàëüíîãî âîññòàíîâëåíèÿ ôóíêöèîíàëà íà êîíå÷íîìåðíîìïðîñòðàíñòâå Rn :sup|hκ n , xi − hϕ, yi| → min,ϕx∈Mn ,y∈Y : y−Bx∈O11ϕ ∈ Rm .(9)Ýòî çàäà÷à îïòèìàëüíîãî âîññòàíîâëåíèÿ ôóíêöèîíàëà κ n ïî èíôîðìàöèè(Mn , B, O). Àññîöèèðîâàííîé áóäåò çàäà÷àhκ n , xi → max,(x,y)(x, y) ∈ Rn × Rm , x ∈ Mn , y − Bx ∈ O, y = 0.(10)Ôóíêöèÿ Ëàãðàíæà çàäà÷è (9) òàêîâà:Ln : (Rn × Rm ) × Rm → R,Ln ((x, y), λ) = −hκ n , xi + hλ, yi.Àâòîðîì â äèññåðòàöèè äîêàçàíî ìíîæåñòâî òåîðåì î ñâÿçè çàäà÷ îïòèìàëüíîãî âîññòàíîâëåíèÿ â áåñêîíå÷íîìåðíîì ïðîñòðàíñòâå è â êîíå÷íîìåðíîì.
Ñôîðìóëèðóåì äâå èç ýòèõ òåîðåì. Ñíà÷àëà ñôîðìóëèðóåì äîêàçàííóþ â äèññåðòàöèè òåîðåìó î ñâåäåíèè ê êîíå÷íîìåðíîé çàäà÷å. żäîêàçàòåëüñòâî îïèðàåòñÿ íà Ïðèíöèï Ëàãðàíæà.Òåîðåìà (Î ñâåäåíèè ê êîíå÷íîìåðíîé çàäà÷å). ÏîëîæèìF := Qm A0 Ln Pnâ çàäà÷àõ (4) è (5). Ïóñòü âûïîëíåíî óñëîâèå (6).b ìíîæèòåëü Ëàãðàí1) Åñëè (bz , 0) ∈ Z × Rm ðåøåíèå çàäà÷è (5), à λæà, ïðè êîòîðîì ìèíèìóì ôóíêöèè Ëàãðàíæà äëÿ çàäà÷è (4) äîñòèãàåòñÿ íà (bz , 0), ò.å.³´b−h`, zb i =inf−h`, zi + h λ, yi ,z∈M,y∈Rm : y−Qm A0 Ln Pn z∈Ob ÿâëÿåòñÿòîãäà (Pn zb, 0) ∈ Rn × Rm ÿâëÿåòñÿ ðåøåíèåì çàäà÷è (10), λìåòîäîì îïòèìàëüíîãî âîññòàíîâëåíèÿ çàäà÷è (9), è åãî ïîãðåøíîñòüðàâíà h`, zb i.b n ìíîæèòåëü2) Åñëè (bx, 0) ∈ Rn × Rm ðåøåíèå çàäà÷è (10), à λËàãðàíæà, ïðè êîòîðîì ìèíèìóì ôóíêöèè Ëàãðàíæà äëÿ çàäà÷è (9) äîñòèãàåòñÿ íà (bx, 0), ò.å.³´b n , yi ,−hκ n , xbi =inf−hκ n , xi + h λx∈Mn ,y∈Rm : y−Bx∈Oòîãäà ïðè ëþáîì zb ∈ M , òàêîì ÷òî Pn zb = xb, òî÷êà (bz , 0) ∈ Z × Rmb n ÿâëÿåòñÿ ìåòîäîì îïòèìàëüíîãî âîñÿâëÿåòñÿ ðåøåíèåì çàäà÷è (5), λñòàíîâëåíèÿ çàäà÷è (4), è åãî ïîãðåøíîñòü ðàâíà hκ n , xb i.
Åñëè ïðè ýòîìâûïîëíåíû óñëîâèÿ (7) è (8), òî ýëåìåíò Ln xb óäîâëåòâîðÿåò óñëîâèÿìíà zb.Ýòà òåîðåìà ïîçâîëÿåò ðåøàòü âìåñòî èñõîäíîé çàäà÷è ïîèñêà ìåòîäàè ïîãðåøíîñòè îïòèìàëüíîãî âîññòàíîâëåíèÿ çàäà÷ó îïòèìàëüíîãî âîññòàíîâëåíèÿ â êîíå÷íîìåðíîì ïðîñòðàíñòâå.12Ñôîðìóëèðóåì äîêàçàííóþ â äèññåðòàöèè òåîðåìó î ñâÿçè ïîãðåøíîñòåé è ìåòîäîâ îïòèìàëüíîãî âîññòàíîâëåíèÿ äëÿ çàäà÷ â êîíå÷íîìåðíîì èáåñêîíå÷íîìåðíîì ïðîñòðàíñòâå. Äëÿ ýòîãî íàäî ìîäèôèöèðîâàòü îêðåñòíîñòü ïîãðåøíîñòè.
Áóäåì ñ÷èòàòü, ÷òî â çàäà÷å èçâåñòåí âåêòîð ∆n ∈ Rm ,óäîâëåòâîðÿþùèé óñëîâèÿì∆nj ≡ (∆n )j > sup |(Qm A0 (z − Ln Pn z))j |∀j ∈ {1; . . . ; m}.z∈M(11)Ââåä¼ì íåâîçìóù¼ííóþ è âîçìóù¼ííóþ îêðåñòíîñòè ïîãðåøíîñòè. ÏóñòüO0 ⊂ Y âûïóêëîå óðàâíîâåøåííîå ìíîæåñòâî, òàêîå ÷òîO0 ⊃ Ω + Qm (A − A0 )(M );On := O0 + {y ∈ Rm | |yj | 6 ∆nj ∀j ∈ {1; . . .
; m} }.b n ∈ Y ∗ ðåøåíèå çàäà÷è (9) ïðè O = On , íàéäåííîå èç ÏðèíöèÏóñòü λb n ÿâëÿåòñÿ òåì ìíîæèòåëåì Ëàãðàíæà, ñóùåñòâîâàíèåïà Ëàãðàíæà, ò.å. λêîòîðîãî óòâåðæäàåò Ïðèíöèï Ëàãðàíæà. Ââåä¼ì îáîçíà÷åíèå äëÿ ïîãðåøíîñòè ýòîãî ìåòîäà.b n ).En := E(κ n , Mn , B, On ) = E(κ n , Mn , B, On , λÐàññìîòðèì íåâîçìóù¼ííóþ áåñêîíå÷íîìåðíóþ çàäà÷ó (4) ïðè F = Qm A0b ∈ Y ∗ å¼ ðåøåíèå, íàéäåííîå èç Ïðèíöèïà Ëàãðàíæà,è O = O0 . Ïóñòü λbèλb n â ýòîé çàäà÷å, ò.å.à Ē è Ēn ïîãðåøíîñòè ìåòîäîâ λb = E(`, M, Qm A0 , O0 ),Ē := E(`, M, Qm A0 , O0 , λ)b n ).Ēn := E(`, M, Qm A0 , O0 , λÀâòîðîì äîêàçàíà ñëåäóþùàÿÒåîðåìà. [29, 25] Ïóñòü Z ÿâëÿåòñÿ íîðìèðîâàííûì ïðîñòðàíñòâîì,ëèíåéíûé ôóíêöèîíàë ` íåïðåðûâåí, âûïóêëîå óðàâíîâåøåííîå ìíîæåñòâî M ñëàáî ñåêâåíöèàëüíî êîìïàêòíî â Z , ëèíåéíûé îïåðàòîð Qm A0íåïðåðûâåí, O0 çàìêíóòî, âûïóêëî è óðàâíîâåøåíî.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
