15412 skrypt

Liniowa proomota

7A ^ncnNIOKWAPRATOWA SVGNAlć>W STACJONARNYCH

JłEKUREMCYJNE ME TOPY ROZWIĄZANIA p_nnH| _C1„,

PROGNOZY

*

Zależności (c można zapisać jako

Pn+1 =

= (I-Pa+i)'’[^rf".»+' + P"+<]if*."+'-l] < ¹ = 2,3,...    (2.197)

żht-tl.n+i — (l^— Pn+l) ^[#n,n+t-l *ł*Pn+l^n,n+i] t i— 2,3,...

Zauważmy, że wyprowadzony tułaj metodą algebraiczną algorytm Schura (2.197) stanowi konkurencyjne, w stosunku do algorytmu Levinsona. rozwiązanie problemu prognozy, gdyż współczynnik p„+i (zwany współczynnikiem Scliura) jest numerycznie identyczny jak we wzorze (2.140), a zależność

gn hl.n+l ⁼ ( I ^— Pn+\) ^ Ign.n + Pn+ Idn,n+ 11    (2.198)

jest identyczna z (2.141). Algorytm Schura - jak wcześniej wspomnieliśmy -odgrywa kluczową rolę we współczesnej teorii ortogonalnej cyfrowej filtracji optymalnej sygnałów losowych. Dlatego też w dalszej części będzie on szczegółowo omówiony w wielu aspektach Tutaj ograniczmy się do porównania liczby operacji w algorytmie Lcvinsona i Schura. Zauważmy, że kluczową rolę w obydwu algorytmach odgrywa wyznaczenie współczynników Schura

{pi.....Pn] , n= 1,2,...    (2.199)

Znajomość tycli współczynników jest wystarczająca do

•    realizacji optymalnego filtru prognozującego (bez konieczności wyznaczania explicile odpowiedzi impulsowej (2.134) lego filtru);

•    parametryzacji sygnałów losowych za pomocą filtracji innowacyjnej i ich odtwarzania (cyfrowej syntezy) za pomocą filtracji modelującej 117],

•    estymacji statystyk sygnałów losowych metodami parametrycznymi ( według kryterium maksimum entropii) [2. 9];

•    rozwiązania tzw. problemu odwrotnego bezstratnego rozproszenia (17];

•    rozwiązania problemu optymalnej filtracji odszuiniającej i realizacji ortogonalnych filtrów odszumiających;

•    rozwiązania problemu tzw. ślepej identyfikacji;

•    modelowania sygnałów i systemów za pomocą modeli o niskim stopniu złożoności (rozwiązanie problemu interpolacyjnego) 112. 14, 15. 38. 481.

Dlatego też szybkie algorytmy wyznaczania współczynników Schura mają tutaj zasadnicze znaczenie. Poprzednio stwierdziliśmy, że algorytm Leunsona wykorzystujący właściwości strukturalne macierzy Toeplitza - umożliwia reduk cję liczby operacji z o(iP) w metodzie eliminacji Gaussa, do o(n²) i wyznacza w każdym kroku, jak to obecnie wiemy, współczynnik Schura p„ Poszukując szybkich algorytmów wyznaczania współczynników Schura. należałoby oczekiwać. że zastosowanie przetwarzania równoległego (z. użyciem n procesorów) powinno dać w rezultacie zmniejszenie liczby operacji o kolejny rząd - do o(n). Niestety, n-proccsorowa realizacja algorytmu Ievinsona umożliwia wprawdzie zmniejszenie liczby operacji, ale tylko do o{n log n) Natomiast n-procesorowa realizacja algorytmu Schura daje obniżenie liczby operacji do o(n). Wniosek ten jest natychmiastowy, jeśli porówna się sposób wyliczania współczynników Schura w algorytmie Lcvinsona (patrz. (2.140) i (2.139)) ze wzorem określającym ten współczynnik w algorytmie Schura (patrz (2.197)). Wprawdzie mianowniki w obydwu wyrażeniach są identyczne, lecz w algorytmie Schura licznik d„„yi jest stałą wyliczana w poprzednim kroku, natomiast w algorytmie Levinsona w każdym kroku jest konieczne wyliczenie licznika jako iloczynu skalarnego (2.139). co wymaga n dodatkowych operacji mnożenia i dodawania. Z tego względu, jak i z uwagi na lepszą stabilność numeryczną, w rozwiązywaniu zagadnień cyfrowej filtracji optymalnej jest stosowany przede wszystkim algorytm Schura. w kilku równoważnych postaciach, które kolejno omówimy

Podsumowując, algorytm Schura działa następująco;

•    dane c(0),c(l).....c(n)

•    inicjalizacja (patrz (2.190) (2.191) dla n — 0): for i ~ 0 to N do

,    c(i)

“o.i — gn,i — - y—— , dno = 0

V ^c(0)

end;

> algorytm

for n = 0 to N - I do

Pn + I — '

8n.fi

for i = 2 to N do

^tAl+l,n+i⁼(l ~ Pn+ l) ‘ [tAi.ir-t-i 4-Pn+tgn.n-ti-t] for r = 1 to N do

£/i+t,n+i ⁼ ( 1 “ Pn+ 1) ' [Pn+ldn.n+i + £n,n+i-I ]

(2.200)

(2.201)

^an,/i+1

60

Liniowa prognoza Sredniokwadratowa sygnałów stacjonarnych______

Uwaga: Przykład 7.3 iv rozdziale 7 stanowi implementacje iv Środowisku MATLAB omówionego w niniejszym punkcie algebraic znego algorytmu Sc hura Przedstawiono w nim również przykładowe wyniki symulacji.

•i

61

Rekurencyjne metody rozwiązania problemu prognozy

2.2.6. Metoda geometryczna

Niniejszy punkt jest poświęcony omówieniu rekurcncyjnych rozwiązań problemu optymalnej prognozy średniokwadratowej metodą geometryczną w trzech wprowadzonych wcześniej, izomorficznych przestrzeniach Hilberta

•    zmiennych losowych - Li {Ił, 91, p).

•    wielomianów zmiennej z -

•    wektorów współczynników - ii.

Prezentowana metoda geometryczna z jednej strony umożliwia w jednolity spo sóbtozwiązanie problemu prognozy, zarówno pod względem estymacji sygnału losowego, jak i wyznaczenia transmitancji lub odpowiedzi impulsowej optymalnego filtru prognozującego, z drugiej zaś implikuje tzw realizacje ottogo nałną filtrów optymalnych (prognozujących, innowacyjnych i modelujących) Ponadto, przedstawione rozwiązania odgrywają kluczową rolę w rozwiązaniu problemu ortogonalnej realizacji optymalnych filtrów odszumiających

*

Przestrzeń L2{1l,')\,p)

Wykorzystując podprzeslrzeń S* (2.44) oraz podprzestrzeń S" (2.48) rozpiętą na n-krokowej przeszłości sygnału y. rozważmy podprzestrzeń .Sg rozpiętą na obserwacjach {y(t),y(t- I),.. . ,y(f — n)}. Zauważmy, że - korzystając z (2.48) - podpi7.eslrzeń tę możemy wyrazić w sposób rekurencyjny jako

.Vj; = spri/i{y(r),^ }    (2 204)

i przypomnijmy, że optymalny (średniokwadrntowo) estymator u przód rzędu n %(t) (2.54) zmiennej losowej v(r) otrzymuje się, dokonując projekcji ortogonalnej elementu y(r) na podprzestrzeń S", rozpiętą na u krokowej przeszłości

Mt) = P{Sⁿ{)y(t) 6S-;    (2 205)

Wówczas l>lqd u> przód ft„(l) rzędu n estymacji zmiennej losowej y(r) za pomocą estymatora y„(r) wyraża się jako projekcja (2.55) zmiennej losowej y(f) na ortogonalne uzupełnienie podprzestrzeni S" względem Sg

<#) = P[sⁿnesr_i)y[t) = (/ - P{SU)y(t) = y(r) - *,(») 1 Sg    (2 206)

Wprowadźmy obecnie unormowany błąd w przód, definiując tj. mamy

(2.207)

(2.208)

Jest oczywiste, że unormowanie (2 207), a więc przemnożenie przez dodatni skalar ||«:„(/)||. nie zmienia kierunku elementu e„(r) (względem kierunku elementu £„(/)), a w konsekwencji pozostają w mocy warunki ortogonalności

(2.206). Z (2 207) mamy

£„(') = e.>(0lk(r)||t/

Podstawiając (2.209) do (2.206), otrzymujemy

(2.209)

tn(t) =

9n(t)

IIMOIIo IMOlIti

(2.210)

gdzie y(r) oraz %{t) oznaczają. odpowiednio, unormowaną zmienną losową y(t) oraz unormowany estymator y„(t) Schematycznie ilustruje to rys. 2.10.

Przepiszmy przestrzeń óg (2.204) w sposób rekurencyjny jako

óg = span{S% v(r - n) }    (2.211)

i zdefiniujmy estymator w tył(rzędu n)y„{t) zmiennej losowej y(r - n) jako

y„(r)4 7>(Sg-')y(/-«) 6 5g-'

Mi)

S" — .ipan (y(t — ł), - - -. y(^r — ^f,}l

RYS 2.10.    Optymalny estymator ..w przód"

(2.212)

63

62