Диссертация (1150593), страница 7

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 7)

. . ñëó÷àéíûå âåëè÷èíû rti,k íåçài,kâèñèìû äëÿ îäíîãî çíà÷åíèÿ k . Ñëó÷àéíûå âåëè÷èíû r̃t , k =1, . . . , m, èìåþò ìàòåìàòè÷åñêèå îæèäàíèÿ: Er̃ti,k = r̄k è äèñïåð2ñèè σr,k.Êðîìå òîãî, âñå óïîìÿíóòûå â ïðåäïîëîæåíèÿõ A2.aA2.e íåçàâèñèìûå ñëó÷àéíûå âåëè÷èíû è âåêòîðû íå çàâèñÿò äðóã îò äðóãà.Çàìåòèì, åñëè ïðåäïîëîæåíèÿ A2.b è A2.c âûïîëíÿþòñÿ, òî óñðåäíåííàÿ ìàòðèöà B̄av = EB̄t , ñîñòîèò èç ýëåìåíòîâ(2.8)b̄i,javi,j mod n i,j mod nDj÷nb, åñëè i ∈ N, j mod n 6= 0 Di,n bi,n , åñëè i ∈ N, j mod n = 0j÷n=1/γ, åñëè i = n + 1, .

. . , n̄, j = i − n, 0, èíà÷å.Çäåñü mod îïåðàöèÿ âçÿòèÿ îñòàòêà îò äåëåíèÿ, à ÷ äåëåíèåáåç îñòàòêà.Åñëè d¯ = 0, òî B̄av = Bav .• A3. Ðàçìåð øàãà ïðîòîêîëà óïðàâëåíèÿ γ > 0 óäîâëåòâîðÿåò ñëå39äóþùèì óñëîâèÿì:(2.9) 2(1 − γRe(λ2 L(B̄av )T ) − γRe(λ2 L(B̄av ))++ γ 2 Eλmax (L(B̄t )T L(B̄t ))) < 1,è(2.10)γ≤1indegmax (B̄av ).Óñðåäíåííàÿ ìîäåëü?,kÏóñòü {Xt }, k = 1 .

. . m òðàåêòîðèè óñðåäíåííûõ ñèñòåì?,kXt+1= Xt?,k + Z̄ k − R̄k ,(2.11)ãäå n-ìåðíûå âåêòîðû Z̄ k = [z̄ k ] è R̄k = [r̄k ] ñîñòîÿò èç ìàòåìàòè÷åñêèõîæèäàíèé, çàäàííûõ â ïðåäïîëîæåíèÿõ A2.d, A2.e.Äèôôåðåíöèðîâàííûé êîíñåíñóñ?,kÐàññìîòðèì âåêòîðû X̄tt = 0, 1, . . ..TTT?,k?,k?,k= 1d+1, Xt−1.

. . Xt−)T ∈ Rn̄ ,¯ ⊗ (Xtd¯Ò å î ð å ì à 2. Åñëè äëÿ ñèñòåì ñ îáðàòíûìè ñâÿçÿìè (2.5) è (2.11)âûïîëíåíû ïðåäïîëîæåíèÿ A1A3, òî ñïðàâåäëèâî ñëåäóþùåå íåðàâåíñòâî:(2.12)EkX̄tk−X̄t?,k k2t+1≤QkX̄0k−X̄0?,k k21 − Qt+1,+∆1−QãäåQ = 2 1 − γRe(λ2 L(B̄av )T ) − γRe(λ2 L(B̄av )) + γ 2 Eλmax L(B̄t )T L(B̄t ) , d(¯ d¯ + 1)(2d¯ + 1)∆ = 2γ 2 E λmax (B̃tT B̃t )n(z̄ k − r̄k )2 +6222+ nσz,k+ nσr,k+ γ 2 indeg(Bt )T indeg(Bt )σw,k.40òî åñòü, åñëè EkX̄0k − X̄0?,k k2 < ∞, òî àñèìïòîòè÷åñêèé ñðåäíåêâàäðà-òè÷åñêèé ε-êîíñåíñóñ â (2.5) äîñòèãàåòñÿ ñ(2.13)ε≤∆1−Qäëÿ êàæäîãî ïðèîðèòåòà k .Äîêàçàòåëüñòâî.

Ðàññìîòðèì âåêòîðû X̄t?,k ∈ Rn̄ , t = 0, 1, . . ., óäîâëåòâîðÿþùèå óðàâíåíèþ:?,kX̄t+1= U X̄t?,k +(2.14)kZ̄ − R̄0k!ãäå U ìàòðèöà ðàçìåðà n̄ × n̄:U =0 00 00 0... .. . . In 0In 0 . . .In 0 . . .0 In . . ... ..... ..0 0 ...Îáîçíà÷èì Ftk = Z̃tk − Rtk , F̄ k = Z̄ k − R̄k .Äëÿ ðàçíîñòè òðàåêòîðèé òðàåêòîðèé ñèñòåì (2.7) è (2.20) èìååì?,kkkνt+1= X̄t+1− X̄t+1= X̄tk − U Xt?,k − γL(B̄t )X̄tk ++Ftkk− F̄ + γ indeg Bt ◦0nd×1¯Wtk!?,kÄîáàâëÿÿ è âû÷èòàÿ γL(B̄t )X̄t , ïîëó÷àåìXtk k Xt−1 Xt?,kXt?,kγ(D(Bt ) − B̃t )X̄tkk −Xtk + Xt−1γ(D(Bt ) − B̃t )X̄t?,k?,k −Xt?,k + Xt−1−.... ...   ...  − +−..   ?,k?,k?,kkkkXt−d+1−Xt−d+1Xt−d¯−Xt+d+1¯ + Xt−d¯¯¯ + Xt−d¯41γ(D(Bt ) − B̃t )X̄t?,k?,k −Xt?,k + Xt−1−...?,k?,k−Xt−¯ + Xt−d¯d+1+Ftkk− F̄ + γ indeg(Bt ◦0nd×1¯!Wtk ),ãäå B̃t ìàòðèöà n × n(d¯+ 1), ñîñòîÿùàÿ èç n ïåðâûõ ñòðîê ìàòðèöû B̄t .?,kÇàìåíèì â ïîëó÷èâøåìñÿ âûðàæåíèè X̄tk − X̄tνtk −γL(B̄t )νtk −B̃t )X̄t?,kγ(D(Bt ) −0nd×1¯!+Ftk?,kíà νtk :k− F̄ + γ indeg(Bt ◦0nd×1¯?,kÐàññìîòðèì âûðàæåíèå γ(D(Bt ) − B̃t )X̄t .

γ(D(Bt ) − B̃t )X̄t!Wtk ).=?,kk¯Xt−+dF̄Xt?,k¯ ?,k  ?,k d ¯Xt−1 X ¯ + (d − 1)F̄ k  t−d=γ(D(Bt ) − B̃t ) .. ...  = γ(D(Bt ) − B̃t ) .?,k?,kXt−d¯Xt−d¯?,kó÷èòûâàÿ, ÷òî (D(Bt ) − B̃t ) · 1n(d+1)xt−d¯ = 0, ïîñêîëüêó (D(Bt ) − B̃t ) ¯ïåðâûå n ñòðîê ëàïëàñèàíà L(B̄t ) è ÷òî 1n(d+1) åãî ñîáñòâåííûé âåêòîð,¯ñîîòâåòñòâóþùèé íóëåâîìó ñîáñòâåííîìó çíà÷åíèþ, ïîëó÷àåì ¯d0 ¯ d − 1 1 .  ⊗ F̄ k  = γ B̃t  .  ⊗ F̄ k  .= γ(D(Bt ) − B̃t )  ..

 ..  0d¯¯ T ⊗ F̄ k .Îáîçíà÷èì d˜ âåêòîð (0, 1, . . . d)kÐàññìîòðèì óñëîâíîå ìàòåìàòè÷åñêîå îæèäàíèå êâàäðàòà íîðìû νt+1îòíîñèòåëüíî σ -àëãåáðû âåðîÿòíîñòíûõ ñîáûòèé F̃t−1 , ïîðîæäåííîé ñëói,ki,j,ki,j,ki,ki,ji,k, . . . , wt−1, z0i,k , . . . , zt−1, di,j0 , . . . , dt−1 , r0 ,i, j ∈ N.÷àéíûìè âåëè÷èíàìè x0 , w0i,ki,ji,j. . . , rt−1, bi,j0 , . .

. , bt−1 , bt42k||2 =EF̃t−1 ||νt+1EF̃t−1 νtk − γL(B̄t )νtk −!˜γ B̃t d+0nd×1¯Ftkk− F̄ + γ indeg(Bt ◦0nd×1¯!2 =Wtk )2˜2 k γ B̃t d = EF̃t−1 In(d+1)− γL(B̄t ) νt + EF̃t−1 +¯0nd×1¯ F k − F̄ k + γ indeg(B ◦ W k )2tt +EF̃t−1 t +0nd×1¯!˜T γ B̃t dT−2EF̃t−1 νtk In(d+1)− γL(B̄t )+¯0nd×1¯T+2EF̃t−1 νtk!Ftk − F̄ k + γ indeg(Bt ◦ Wtk )+0nd×1¯!Ftk − F̄ k + γ indeg(Bt ◦ Wtk )=0nd×1¯TIn(d+1)− γL(B̄t )¯−2EF̃t−1!Tγ B̃t d˜0nd×1¯ïîñêîëüêó νtk , B̄t èçìåðèìû îòíîñèòåëüíî F̃t−1 , è Z̃tk , Rtk , Wtk íåçàâèñèìûîòíîñèòåëüíî F̃t−12 γ B̃ d˜2 t = In(d+1)− γL(B̄t ) νtk + +¯0nd×1¯ F k − F̄ k + γ indeg(B ◦ W k )2tt +E t +0nd×1¯−2νtk+2νtkTTTIn(d+1)− γL(B̄t )¯TIn(d+1)− γL(B̄t ) E¯Ftk43k!γ B̃t d˜+0nd×1¯− F̄ + γ indeg(Bt ◦0nd×1¯!Wtk )+!Tγ B̃t d˜−2E0nd×1¯!Ftk − F̄ k + γ indeg(Bt ◦ Wtk ).0nd×1¯Â ñèëó íåçàâèñèìîñòè Z̃tk , Rtk , Wtk , B̄t ìåæäó ñîáîéEFtkk− F̄ + γ indeg(Bt ◦0nd×1¯!Wtk )=E=Ftk− F̄0nd×1¯k!+γ indeg(Bt ◦0nd×1¯!EWtk ).E(Ftk − F̄ k ) = 0, E(γ indeg(Bt ◦ EWtk )) = 0.F k − F̄ k + γ indeg(B ◦ W k )2tt E t = EkFtk − F̄ k + γ indeg(Bt ◦ Wtk )k2 =0nd×1¯= EkFtk −F̄ k k2 +2E(Ftk −F̄ k )T γ indeg(Bt ◦EWtk )+Ekγ indeg(Bt ◦Wtk )k2 =2= EkZ̃tk − Rtk − (Z̄ k − R̄k )k2 + 0 + γ 2 indeg(Bt )T indeg(Bt )σw,k=2= Ek(Z̃tk − Z̄ k ) − (Rtk − R̄k )k2 + γ 2 indeg(Bt )T indeg(Bt )σw,k≤222≤ nσz,k+ nσr,k+ γ 2 indeg(Bt )T indeg(Bt )σw,k.kEF̃t−1 kνt+1k2 k2˜ 2 + nσ 2 + nσ 2 +≤ In(d+1)− γL(B̄t ) νt + kγ B̃t dk¯z,kr,k2+γ 2 indeg(Bt )T indeg(Bt )σw,k− 2νtkTTIn(d+1)− γL(B̄t )¯!γ B̃t d˜.0nd×1¯Ðàññìîòðèì óñëîâíîå ìàòåìàòè÷åñêîå îæèäàíèå ïîëó÷åííîãî âûðàæåíèÿ îòíîñèòåëüíî σ -àëãåáðû âåðîÿòíîñòíûõ ñîáûòèé Ft−1 , ïîðîæäåííîéi,ki,j,kñëó÷àéíûìè âåëè÷èíàìè x0 , w0i,j,ki,ki,j, .

. . , wt−1, z0i,k , . . . , zt−1, di,j0 , . . . , dt−1 ,i,ki,jr0i,k , . . . , rt−1, bi,j0 , . . . , bt−1 , i, j ∈ N.kEFt−1 kνt+1k2 k2˜ 2 + nσ 2 +≤ EFt−1 In(d+1)− γL(B̄t ) νt + EFt−1 kγ B̃t dk¯z,k44 22+nσr,k+ γ 2 EFt−1 indeg(Bt )T indeg(Bt ) σw,k+!!˜T γ B̃t dT−2EFt−1 νtk In(d+1)− γL(B̄t )=¯0nd×1¯ïîñêîëüêó B̄t íå çàâèñèò îò Ft−1 k2˜ 2 + nσ 2 + nσ 2 += E In(d+1)− γL(B̄t ) νt + Ekγ B̃t dk¯z,kr,k2+ γ 2 E indeg(Bt )T indeg(Bt ) σw,k+− 2EνtkTTIn(d+1)− γL(B̄t )¯!!˜γ B̃t d.0nd×1¯Ñîãëàñíî íåðàâåíñòâó Êîøè-Áóíÿêîâñêîãî2EνtkTTIn(d+1)− γL(B̄t )¯!!γ B̃t d˜≤0nd×1¯!˜ k γ B̃t d 2E In(d+1)− γL(B̄t ) νt .¯0nd×1¯  òî æå âðåìÿ2E!˜ k γ B̃t d − γL(B̄t ) νt In(d+1) ≤¯0nd×1¯ 2 γ B̃ d˜2 t E In(d+1)− γL(B̄t ) νtk + E .¯0nd×1¯ kÏîäñòàâèì â âûðàæåíèå äëÿ EFt−1 kνt+1k2 :kEFt−1 kνt+1k2 k2˜ 2 + nσ 2 + nσ 2 +≤ E In(d+1)− γL(B̄t ) νt + Ekγ B̃t dk¯z,kr,k 2 k2˜2+γ E indeg(Bt ) indeg(Bt ) σw,k +E In(d+1)−γL(B̄)ν¯tt +Ekγ B̃t dk .

k2Çàìåòèì, ÷òî E In(d+1)− γL(B̄t ) νt =¯2T45TνtkT kIn(d+1)− γL(B̄t )In(d+1)− γL(B̄t ) νt =¯¯=E T kkT2T= E νt In(d+1)− γL(B̄t ) − γL(B̄t ) + γ L(B̄t ) L(B̄t ) νt =¯ïîñêîëüêó νtk èçìåðèìî îòíîñèòåëüíî Ft−1TTTT= νtk νtk − γνtk EL(B̄t )T νtk − γνtk EL(B̄t )νtk + γ 2 νtk E L(B̄t )T L(B̄t ) νtk =ïîñêîëüêó B̄t íå çàâèñèò îò Ft−1TTTT= νtk νtk − γνtk L(B̄av )T νtk − γνtk L(B̄av )νtk + γ 2 νtk E L(B̄t )T L(B̄t ) νtk ≤≤ 1 − γλmin L(B̄av )T − γλmin L(B̄av ) + γ 2 Eλmax L(B̄t )T L(B̄t ) kνtk k2 .TÏðè îöåíêå âûðàæåíèÿ νtk L(B̄av )νtk ôàêòè÷åñêè ðàññìàòðèâàåòñÿ ïðîåêTöèÿ νtk L(B̄av )νtk íà ïîäïðîñòðàíñòâî, îðòîãîíàëüíîå ñîáñòâåííîìó âåê-òîðó L(B̄av ), êîòîðûé ñîîòâåòñòâóåò íóëåâîìó ñîáñòâåííîìó ÷èñëó ëàïëà-ñèàíà.

Ïóñòü νtk =Pnk ki=1 ηi ei ðàçëîæåíèå νtk ïî îðòîíîðìèðîâàííîìóTáàçèñó ñîáñòâåííûõ âåêòîðîâ L(B̄av ). Òîãäà èìååì νtk L(B̄av )νtk =PPP= ( ni=1 ηik eki )T L(B̄av )( ni=1 ηik eki ) = ni=1 ηi2 eTi L(B̄av )ei =P= ni=1 ηi2 eTi λi (L(B̄av ))ei . Ïîñêîëüêó λ1 (L(B̄av )) = 0 (ïóñòü, íå óìàëÿÿPnPnîáùíîñòè, λ1 ≤ . . . ≤ λn ), i=1 ηi2 eTi λi (L(B̄av ))ei = i=2 ηi2 eTi λi (L(B̄av ))eiPn 2 Tk 2≤i=2 ηi ei λ2 (L(B̄av ))ei = λ2 (L(B̄av ))kνt k . Ïîýòîìó ìîæíî îöåíèòüλmin L(B̄av ) äåéñòâèòåëüíîé ÷àñòüþ âòîðîãî ïî âåëè÷èíå ñîáñòâåííîãî÷èñëà ëàïëàñèàíà Re(λ2 L(B̄av )).

k2E In(d+1)− γL(B̄t ) νt ≤ (1 − γRe(λ2 L(B̄av )T ) − γRe(λ2 L(B̄av ))+¯+ γ 2 Eλmax (L(B̄t )T L(B̄t )))kνtk k2 .22T˜˜2=Îöåíèì âûðàæåíèå Ekγ B̃t dk ≤ γ E λmax (B̃t B̃t ) kdkT¯ T ⊗ (Z̄ k − R̄k )k2 == γ E λmax (B̃t B̃t ) k(0, 1, . . . d)246nd¯ XXl2(z̄ k − r̄k )2  == γ 2 E λmax (B̃tT B̃t ) i=1l=12=γ E d(¯ d¯ + 1)(2d¯ + 1)λmax (B̃tT B̃t )6kk 2n(z̄ − r̄ ).kk2 .Ïîñ÷èòàåì ìàòåìàòè÷åñêîå îæèäàíèå Ekνt+1kEkνt+1k2 ≤ 2(1 − γRe(λ2 L(B̄av )T ) − γRe(λ2 L(B̄av ))++ γ 2 Eλmax (L(B̄t )T L(B̄t )))kνtk k2 + d(¯ d¯ + 1)(2d¯ + 1)+2γ 2 E λmax (B̃tT B̃t )n(z̄ k − r̄k )2 +6222+nσz,k+ nσr,k+ γ 2 indeg(Bt )T indeg(Bt )σw,k.Îáîçíà÷èìQ = 2(1 − γRe(λ2 L(B̄av )T ) − γRe(λ2 L(B̄av ))++ γ 2 Eλmax (L(B̄t )T L(B̄t ))), d(¯ d¯ + 1)(2d¯ + 1)∆ = 2γ 2 E λmax (B̃tT B̃t )n(z̄ k − r̄k )2 +6222+ nσz,k+ nσr,k+ γ 2 indeg(Bt )T indeg(Bt )σw,k.Ïðîâîäÿ ðàññóæäåíèÿ àíàëîãè÷íî Ëåììå 1 èç âòîðîé ãëàâû [39], ïîëó÷àåìkkEkνt+1k2 ≤ Qkνtk k2 + ∆ ≤ Q(Qkνt−1k2 + ∆) + ∆ ≤ .

. .≤ Qt+1 kν0k k2 + ∆ + ∆Q + . . . ∆Qt = Qt+1 kν0k k2 + ∆Ïî ïðåäïîëîæåíèþ A3 |Q| < 1. Ïðè t → ∞ ïîëó÷àåìkk2 ≤Ekνt+147∆.1−Q1 − Qt+1.1−QÇàìåòèì çäåñü, ÷òî ðåçóëüòàò Òåîðåìû 2 ïîêàçûâàåò, ÷òî î÷åðåäè ñðàçëè÷íûìè ïðèîðèòåòàìè äîñòèãàþò m ðàçëè÷íûõ êîíñåíñóñíûõ çíà÷åíèé ðàçäåëüíî. Íàçîâåì òàêîå ïîâåäåíèå äèôôåðåíöèðîâàííûì êîíñåí-ñóñîì.2.3Îöåíêà îïòèìàëüíîãî ðàçìåðà øàãààëãîðèòìàÒ å î ð å ì à 3.

Åñëè âûïîëíåíû ïðåäïîëîæåíèÿ A1A3 òî îïòèìàëüíîå çíà÷åíèå øàãà γ ? äëÿ ïðîòîêîëà èç (2.4) ìîæåò áûòü ïîëó÷åíî èç ñëåäóþùåé ôîðìóëû:KS − J+γ? = −JV(2.15)sKS − JJV2+K,Jãäå d(¯ d¯ + 1)(2d¯ + 1)J = 2E λmax (B̃tT B̃t )n(z̄ k − r̄k )2 +62+ indeg(Bt )T indeg(Bt )σw,k,22K = nσz,k+ nσr,k, S = 2Eλmax L(B̄t )T L(B̄t ) , V = 4(Re(λ2 L(B̄av )T ) +Re(λ2 L(B̄av ))).Äîêàçàòåëüñòâî.

 âûáðàííûõ îáîçíà÷åíèÿõ∆=1−QJγ 2 + K.1 − (Sγ 2 − V γ + 2)Íàéäåì íàèìåíüøèå âîçìîæíûå âåðõíèå ãðàíèöû äëÿ ε. Äëÿ ïðîèçâîä-48íîé∆1−Qïî γ èìååì:Jγ 2 + K−Sγ 2 + V γ − 10=2Jγ(−Sγ 2 + V γ − 1) − (−2Sγ + V )(Jγ 2 + K)=(−Sγ 2 + V γ − 1)2−2JSγ 3 + 2JV γ 2 − 2Jγ + 2JSγ 3 − JV γ 2 + 2KSγ − KV==(−Sγ 2 + V γ − 1)2JV γ 2 + (2KS − 2J)γ − KV=.(−Sγ 2 + V γ − 1)2Ïðèðàâíÿåì ÷èñëèòåëü íóëþ è ðåøèì êâàäðàòíîå óðàâíåíèå:JV γ 2 + (2KS − 2J)γ − KV = 0.2KS − 2J±γ=−2JVs2KS − 2J2JV2+4JKV 2(2JV )2Ó÷èòûâàÿ, ÷òî ðàçìåð øàãà γ ïîëîæèòåëüíàÿ âåëè÷èíà, â ðåçóëüòàòåïîëó÷àåì îïòèìàëüíîå çíà÷åíèå äëÿKS − Jγ =−+JV?Ç à ì å ÷ à í è åsKS − JJV2+K.J1.

Îïòèìàëüíîñòü âûáîðà ðàçìåðà øàãà äëÿàëãîðèòìà ëîêàëüíîãî ãîëîñîâàíèÿ ïîíèìàåòñÿ â ñìûñëå îáåñïå÷åíèÿòàêîé ñêîðîñòè ñõîäèìîñòè è òàêîé ÷óâñòâèòåëüíîñòè ê ïîìåõàì,êîòîðûå ïîçâîëÿþò äîñòè÷ü íàèáîëüøåé òî÷íîñòè ñõîäèìîñòè (èëèíàèìåíüøåãî îòêëîíåíèÿ îò çíà÷åíèÿ êîíñåíñóñà) â ñèñòåìå ïðè çàäàííûõ óñëîâèÿõ.Ç à ì å ÷ à í è å2. Äëÿ ñåìåéñòâà óïðàâëÿþùèõ ïðîòîêîëîââ (2.4) ìîæíî âûáèðàòü ðàçìåð øàãà γ ïî ôîðìóëå (2.15) â çàâèñèìîñòè îò æåëàåìîãî ïîâåäåíèÿ ñèñòåìû. Åñëè æåëàòåëüíî óìåíüøèòü÷óâñòâèòåëüíîñòü ñèñòåìû ê ïîìåõàì, òî, ñëåäóåò óìåíüøèòü ðàçìåð øàãà γ .

Характеристики

Список файлов диссертации