Wykład 9 Przypadek ogólny wyrównania

• Nieliniowa metoda najmniejszych kwadratów

• Linearyzacja sukcesywna

• Przypadek najogólniejszy

  • metoda warunkowa z parametrami

  • metoda parametryczna z warunkami wiążącymi parametry FREE

• Metoda wielkich wag

NIELINIOWA METODA NAJMNIEJSZYCH KWADRATÓW

Szacujemy wartości wektorów: parametrów i obserwacji dla których zachodzi minimum funkcji celu (funkcji oceny)

gdzie

z restrykcjami

Dla istnienia rozwiązania liczba równań nie może być mniejsza od liczby niewiadomych

gdzie oznacza liczbę obserwacji

oznacza liczbę warunków

oznacza liczbę parametrów

• Jeśli macierz jest dodatnio określona czyli dla każdego to w przestrzeni (dla otrzymamy wielowymiarową metrykę euklidesową).

• forma dwuliniowa określa iloczyn skalarny wektorów

• forma kwadratowa określa metrykę

• Jeśli wektor obserwacji ma -wymiarowy rozkład normalny o macierzy wariancyjno-kowariancyjnej to wszystkie estymowane wielkości mają własności stochastyczne

• wektory mają wielowymiarowe rozkłady normalne

• wariancja resztkowa ma rozkład o stopniach swobody

Rys 1. Zadanie MNK dla obserwacji skorelowanych w przestrzeni metrycznej

Rys 2. Zadanie MNK dla obserwacji nieskorelowanych w przestrzeni euklidesowej

Wynika stąd, że możemy wyznaczyć rzut punktu na krzywą jako rozwiązanie zadania z restrykcjami . Można zauważyć, że otrzymana korelata stanowi odpowiednik wysokości normalnej bo jest odległością punktu od krzywej mierzoną w jednostkach modułu gradientu w punkcie.

Wstawiając poprawki wyrównawcze zadanie MNK przybiera postać

z restrykcjami

jest ono równoważne znalezieniu punktu stacjonarnego funkcji Lagrange’a

spełniającego warunki konieczne Kuhna-Tuckera

gdzie

gdzie

Wartość funkcji Lagrange’a jest skalarna: pierwszy człon jest formą kwadratową wektora a drugi iloczynem skalarnym wektorów kolumnowych - oczywiście

Funkcja Lagrange’a jest nieograniczona z dołu ani z góry, nie posiada żadnych ekstremów, jej punkt stacjonarny jest siodłem.

Linearyzacja sukcesywna

Dla wyznaczenia gdzie z restrykcjami

chcemy zbudować zbieżny proces iteracyjny

startujemy od a przybliżenie inicjalne musimy określić metodami jednoznacznymi. Zastosujemy metodę quasi-linearyzacji Gaussa-Newtona. Oznaczamy różniczkowe zmiany rozwiązania

wówczas zlinearyzujemy restrykcje rozwijając je w szereg Taylora z pominięciem wyrazów rzędy drugiego i wyższych

gdzie

w tej parametryzacji poprawki określają wzory

gdzie

a zakończenie procesu oznacza

Rys 3. Proces iteracyjny Newtona oparty na linearyzacji sukcesywnej

W konwencji informatycznej proces iteracyjny określają wzory

Przypadek najogólniejszy, macierzowa postać funkcji Lagrange’a i warunków Kuhna-Tuckera

Funkcję Lagrange’a

zapiszemy macierzą blokową

łatwo zauważyć, że ta macierz pozwala również na interpretację warunków Kuhna-Tuckera

w formie

Macierz będziemy nazywali rozszerzoną macierzą Lagrange’a, a jej blok Λ = Ψ₁₁ macierzą Lagrange’a.

Macierz Lagrange’a posiada duże rozmiary, z tego powodu nie była stosowana w praktyce. Macierz ta posiada wiele bloków zerowych, co znakomicie ułatwia znalezienie rozwiązania ogólnego. Przypadki szczególne: A=I metoda parametryczna, A=0 metoda warunkowa.

Synonimem przypadku najogólniejszego wyrównania jest metoda warunkowa z parametrami.

4.3.4. Rozwiązanie ogólnego przypadku zadania wyrównawczego

W praktyce rozwiązanie uzyskujemy rozwiązując układ równań Kuhna-Tuckera w postaci blokowej albo redukując algorytmem Gaussa macierz Lagrange’a. Przedstawiamy ogólne rozwiązanie macierzowe umożliwiające pełną analizę dokładności i niezawodności.. Zestawiamy macierz blokową poszerzoną macierzą jednostkową dla przeprowadzenia analizy dokładności

Redukujemy macierz Lagrange’a do postaci trójkątnej algorytmem Gaussa

• po redukcji poprawek otrzymamy

• po redukcji korelat otrzymamy

• po redukcji parametrów otrzymamy

gdzie

Redukujemy trójkąt górny algorytmem Gaussa, stąd rozwiązanie ogólne

(4.3.9)

Czwarta kolumna zawiera estymowane wartości niewiadomych a rozszerzenie ich macierze wariancyjne i kowariancyjne. Czwarty wiersz zawiera wariancję resztkową oraz ujemne wartości niewiadomych - wynika stąd, że z postaci trójkątnej macierzy rozszerzonej możemy bezpośrednio uzyskać niewiadome.

4.3.5. Rozwiązania standardowych zadań wyrównawczych

Większość zastosowań nie korzysta bezpośrednio z zadania ogólnego, tylko z jego szczególnych przypadków nazwanych zadaniami standardowymi.

A. Zadanie warunkowe (bezparametrowe)

gdzie

(4.3.10)

B. Zadanie parametryczne

Redukujemy układ do postaci trójkątnej algorytmem Gaussa

gdzie

Redukujemy trójkąt górny algorytmem Gaussa

(4.3.11)

4.3.4. Rozwiązanie ogólnego przypadku zadania wyrównawczego

W praktyce rozwiązanie uzyskujemy rozwiązując układ równań Kuhna-Tuckera w postaci blokowej albo redukując algorytmem Gaussa macierz Lagrange’a. Przedstawiamy ogólne rozwiązanie macierzowe umożliwiające pełną analizę dokładności i niezawodności.. Zestawiamy macierz blokową poszerzoną macierzą jednostkową dla przeprowadzenia analizy dokładności

Redukujemy macierz Lagrange’a do postaci trójkątnej algorytmem Gaussa

• po redukcji poprawek otrzymamy

• po redukcji korelat otrzymamy

• po redukcji parametrów otrzymamy

gdzie

Redukujemy trójkąt górny algorytmem Gaussa, stąd rozwiązanie ogólne

(4.3.9)

Czwarta kolumna zawiera estymowane wartości niewiadomych a rozszerzenie ich macierze wariancyjne i kowariancyjne. Czwarty wiersz zawiera wariancję resztkową oraz ujemne wartości niewiadomych - wynika stąd, że z postaci trójkątnej macierzy rozszerzonej możemy bezpośrednio uzyskać niewiadome.

Analiza dokładości

$$\begin{bmatrix} \mathbf{- bC}\mathbf{b}^{\mathbf{T}} & \mathbf{- a} \\ \mathbf{-}\mathbf{a}^{\mathbf{T}} & \mathbf{0} \\ \end{bmatrix}^{\mathbf{- 1}}\mathbf{=}\left\lfloor \begin{matrix} \mathbf{- Q} & \mathbf{- Qa}\mathbf{\Xi} \\ \mathbf{-}\mathbf{\Xi}\mathbf{a}^{\mathbf{T}}\mathbf{Q} & \mathbf{\Xi} \\ \end{matrix} \right\rfloor\mathbf{=}\left\lfloor \begin{matrix} \mathbf{\Lambda}_{\mathbf{\text{kk}}}^{\mathbf{- 1}} & \mathbf{\Lambda}_{\mathbf{\text{kx}}}^{\mathbf{- 1}} \\ \mathbf{\Lambda}_{\mathbf{\text{xk}}}^{\mathbf{- 1}} & \mathbf{\Lambda}_{\mathbf{\text{xx}}}^{\mathbf{- 1}} \\ \end{matrix} \right\rfloor$$

1. bCb^TQ + a Ξa^TQ = I

2. bCb^TQaΞ − aΞ = 0

3. a^TQ = 0

4. a^T QaΞ = I

$$\mathbf{C}_{\mathbf{\text{ww}}}\mathbf{=}\frac{\mathbf{\text{dW}}}{\mathbf{\text{dL}}}\mathbf{C}_{\mathbf{\text{LL}}}\left( \frac{\mathbf{\text{dW}}}{\mathbf{\text{dL}}} \right)^{\mathbf{T}}\mathbf{= bC}\mathbf{B}^{\mathbf{T}}$$

$$\mathbf{C}_{\mathbf{\text{ss}}}\mathbf{=}\frac{\mathbf{\text{ds}}}{\mathbf{\text{dw}}}\mathbf{C}_{\mathbf{\text{ww}}}\left( \frac{\mathbf{\text{ds}}}{\mathbf{\text{dw}}} \right)^{\mathbf{T}}\mathbf{= bC}\mathbf{B}^{\mathbf{T}}$$

z wyrazow wolnych Π x=Ξa^TΩs=Ξa^T (bCB^T)⁻¹s

$$\mathbf{C}_{\mathbf{\text{xx}}}\mathbf{=}\frac{\mathbf{\text{dx}}}{\mathbf{\text{ds}}}\mathbf{C}_{\mathbf{\text{ss}}}\left( \frac{\mathbf{\text{dx}}}{\mathbf{\text{ds}}} \right)^{\mathbf{T}}\mathbf{=}\mathbf{\Xi}\mathbf{a}^{\mathbf{T}}\left( \mathbf{\text{bC}}\mathbf{B}^{\mathbf{T}} \right)^{\mathbf{- 1}}\mathbf{\ }\mathbf{\text{bC}}\mathbf{B}^{\mathbf{T}}\mathbf{\ }\left( \mathbf{\text{bC}}\mathbf{B}^{\mathbf{T}} \right)^{\mathbf{- 1}}\mathbf{a}\mathbf{\Xi}$$

=Ξa^T(bCB^T)⁻¹ aΞ = Ξ Ξ⁻¹ Ξ = Ξ=Λ_xx⁻¹

Z reduktu x=Ξa^TQs

$$\mathbf{C}_{\mathbf{\text{xx}}}\mathbf{=}\frac{\mathbf{\text{dx}}}{\mathbf{\text{ds}}}\mathbf{C}_{\mathbf{\text{ss}}}\left( \frac{\mathbf{\text{dx}}}{\mathbf{\text{ds}}} \right)^{\mathbf{T}}\mathbf{=}\mathbf{\Xi}\mathbf{a}^{\mathbf{T}}\mathbf{Q}\mathbf{\text{bC}}\mathbf{B}^{\mathbf{T}}\mathbf{\text{Qa}}\mathbf{\Xi}$$

Z ii) mamy bCb^TQaΞ = aΞ

Wstawiając C_xx=Ξa^TQaΞ

Z iv) mamy a^T QaΞ = I

Ostatecznie C_xx=Ξ=Λ_xx⁻¹

k = Qs

$$\mathbf{C}_{\mathbf{\text{kk}}}\mathbf{=}\frac{\mathbf{\text{dk}}}{\mathbf{\text{ds}}}\mathbf{C}_{\mathbf{\text{ss}}}\left( \frac{\mathbf{\text{dk}}}{\mathbf{\text{ds}}} \right)^{\mathbf{T}}\mathbf{= QbC}\mathbf{B}^{\mathbf{T}}\mathbf{Q}$$

Z i) mamy bCb^TQ = I − a Ξa^TQ

Po podstawieniu otrzymamy C_kk=Q − Qa Ξa^TQ

Z iii) mamy Qa = 0

Ostatecznie C_kk=Q = −Λ_kk⁻¹

z wyrazow wolnych Π v=Cb^TQs

$$\mathbf{C}_{\mathbf{\text{vv}}}\mathbf{=}\frac{\mathbf{\text{dv}}}{\mathbf{\text{ds}}}\mathbf{C}_{\mathbf{\text{ss}}}\left( \frac{\mathbf{\text{dv}}}{\mathbf{\text{ds}}} \right)^{\mathbf{T}}\mathbf{=}\mathbf{C}\mathbf{b}^{\mathbf{T}}\mathbf{\text{Q\ }}\mathbf{\text{bC}}\mathbf{B}^{\mathbf{T}}\mathbf{\text{\ QbC}}$$

Z analizy korelaty wynika, że QbCB^TQ = Q

Stąd C_vv=Cb^TQbC

Z pierwszego równania normalnego v = Cb^Tk

$$\mathbf{C}_{\mathbf{\text{vv}}}\mathbf{=}\frac{\mathbf{\text{dv}}}{\mathbf{\text{dk}}}\mathbf{C}_{\mathbf{\text{kk}}}\left( \frac{\mathbf{\text{dv}}}{\mathbf{\text{dk}}} \right)^{\mathbf{T}}\mathbf{=}\mathbf{C}\mathbf{b}^{\mathbf{T}}\mathbf{QbC = C -}\mathbf{\Lambda}_{\mathbf{\text{LL}}}^{\mathbf{- 1}}$$

Zadanie Baar’a