Regularyzacja Tichonowa


Regularyzacja Tichonowa w encyklopedii

Z Wikipedii, wolnej encyklopedii Przejdź do nawigacji Przejdź do wyszukiwania

Regularyzacja Tichonowa – metoda regularyzacji zagadnień nie postawionych poprawnie opracowana niezależnie przez Andrieja Tichonowa[1] i Davida Phillipsa[2], jednak nazwana od nazwiska rosyjskiego matematyka.

Spis treści

Regularyzacja za pomocą parametru regularyzacyjnego | edytuj kod

Rozważmy układ równań typu:

A x = b , {\displaystyle A\mathbf {x} =\mathbf {b} ,}

gdzie A {\displaystyle A} to macierz układu (macierz przekształcenia), x {\displaystyle \mathbf {x} } wektor niewiadomych, b {\displaystyle \mathbf {b} } wektor wyjściowy. Jeśli zagadnienie to jest źle postawione (np. rozwiązanie nie istnieje, lub jest niejednoznaczne) wtedy standardowym podejściem jest rozwiązanie w sensie najmniejszych kwadratów. Oznacza to poszukiwanie minimum następującego funkcjonału Π {\displaystyle \Pi } [3]:

Π = { A x b } T { A x b } . {\displaystyle \Pi =\{A\mathbf {x} -\mathbf {b} \}^{T}\{A\mathbf {x} -\mathbf {b} \}.}

Aby poprawić właściwości funkcjonału Π {\displaystyle \Pi } (np. żeby wyeliminować niefizyczne oscylacje w rozwiązaniu) do powyższej postaci dodaje się człon regularyzacyjny α x T x : {\displaystyle \alpha \mathbf {x} ^{T}\mathbf {x} {:}}

Π = { A x b } T { A x b } + α x T x . {\displaystyle \Pi =\{A\mathbf {x} -\mathbf {b} \}^{T}\{A\mathbf {x} -\mathbf {b} \}+\alpha \mathbf {x} ^{T}\mathbf {x} .}

Wyrażenie x T x {\displaystyle \mathbf {x} ^{T}\mathbf {x} } to kwadrat długości wektora x , {\displaystyle \mathbf {x} ,} zaś α {\displaystyle \alpha } to parametr regularyzacyjny zwany również współczynnikiem tłumienia.

Szukanie minimum funkcjonału Π {\displaystyle \Pi } oznacza rozwiązanie równania:

Π x = 0 , {\displaystyle {\frac {\partial \Pi }{\partial x}}=0,}

co daje:

2 A T { b A x } + 2 α x = 0 {\displaystyle -2A^{T}\{\mathbf {b} -A\mathbf {x} \}+2\alpha \mathbf {x} =0}

i po przekształceniu:

A T b = A T A + α I x , {\displaystyle A^{T}\mathbf {b} =\left[A^{T}A+\alpha \mathbf {I} \right]\mathbf {x} ,}

gdzie I {\displaystyle \mathbf {I} } to macierz jednostkowa.

Macierz stojąca po prawej stronie powyższego równania jest macierzą symetryczną, ponadto dzięki obecności członu α I {\displaystyle \alpha \mathbf {I} } jest również odwracalna. Poza tym parametr regularyzacyjny wpływa na określoność macierzy i poprawia jej uwarunkowanie. W związku z tym rozwiązanie wyjściowego równania może być wyznaczone za pomocą:

x = A T A + α I 1 A T b . {\displaystyle \mathbf {x} =\left[A^{T}A+\alpha \mathbf {I} \right]^{-1}A^{T}\mathbf {b} .}

Dobór parametru regularyzacyjnego może być wykonany za pomocą tzw. metody L-curve[4].

Regularyzacja za pomocą macierzy regularyzacji | edytuj kod

Jeśli dana jest informacja a priori na temat wektora niewiadomych x {\displaystyle \mathbf {x} } może ona zostać uwzględniona w funkcjonale Π {\displaystyle \Pi } w następujący sposób:

Π = { A x b } T { A x b } + α R x T R x , {\displaystyle \Pi =\{A\mathbf {x} -\mathbf {b} \}^{T}\{A\mathbf {x} -\mathbf {b} \}+\alpha \left[R\mathbf {x} \right]^{T}\left[R\mathbf {x} \right],}

gdzie R {\displaystyle R} to macierz regularyzacji oraz α {\displaystyle \alpha } kontroluje stopień regularyzacji.

Pochodna funkcjonału Π {\displaystyle \Pi } względem wektora x {\displaystyle \mathbf {x} } wynosi:

Π x = 2 A T { b A x } + 2 α R T R x . {\displaystyle {\frac {\partial \Pi }{\partial x}}=-2A^{T}\{\mathbf {b} -A\mathbf {x} \}+2\alpha R^{T}R\mathbf {x} .}

Co daje:

A T b = A T A + α R T R x . {\displaystyle A^{T}\mathbf {b} =\left[A^{T}A+\alpha R^{T}R\right]\mathbf {x} .}

Ponownie macierz stojąca po prawej stronie jest symetryczna i w większości przypadków odwaracalna. Postać macierzy regularyzacji zależy od rodzaju informacji, który jest wprowadzany do zagadnienia. Na przykład jeśli rozwiązaniem zagadnienia powinny być w przybliżeniu stałe wartości i-ty wiersz macierzy R {\displaystyle R} powinien wynosić:

r i = 0 , , 0 , 1 i 1 , 1 i , 0 , , 0 . {\displaystyle r_{i}=[0,\dots ,0,{\underset {i-1}{\underbrace {-1} }},{\underset {i}{\underbrace {1} }},0,\dots ,0].}

Inne przykłady sformułowania macierzy R {\displaystyle R} w zależności od informacji, która ma być w niej zawarta można odnaleźć w literaturze[3].

Przykład | edytuj kod

Przykład zastosowania regularyzacji Tichonowa. Szczegóły w tekście.

Rozpatrzmy następujący przykład:

A = 1 2 3 4 1 3 1 5 1,999 99999 3,999 99999 6,000 00001 8,000 0001 7 5 3 1 , {\displaystyle A={\begin{bmatrix}1&2&3&4\\1&3&1&5\\1{,}99999999&3{,}99999999&6{,}00000001&8{,}0000001\\7&5&3&1\end{bmatrix}},} x = 1 2 2 1 . {\displaystyle \mathbf {x} ={\begin{bmatrix}1\\2\\2\\1\end{bmatrix}}.}

Wtedy b {\displaystyle \mathbf {b} } wynosi:

b = A x 15 14 30,000 00009 24 . {\displaystyle \mathbf {b} =A\mathbf {x} \approx {\begin{bmatrix}15\\14\\30{,}00000009\\24\end{bmatrix}}.}

Załóżmy teraz, że na podstawie A {\displaystyle A} i b {\displaystyle \mathbf {b} } chcemy wyznaczyć x . {\displaystyle \mathbf {x} .} Ze względu na fakt, że wyznacznik macierzy jest bliski zera ( det ( A ) = 3 , 6 10 6 ) {\displaystyle (\det(A)=3{,}6\cdot 10^{-6})} i wskaźnik uwarunkowania macierzy wynosi w przybliżeniu 909460299 wyznaczenie macierzy odwrotnej może nastręczać kłopotów, dlatego rozwiązanie poszukiwane jest za pomocą metody najmniejszych kwadratów. Na wykresie obok zielonym kolorem naniesiono przykładowy wynik rozwiązania tą metodą. Widać duże odstępstwa od założonych wcześniej wartości x {\displaystyle \mathbf {x} } oznaczonych za pomocą niebieskich kółek. Dodanie członu regularyzacyjnego zgodnie ze schematem przedstawionym we wcześniejszej części artykułu zdecydowanie poprawia uzyskane rozwiązanie (czerwona linia na wykresie obok). Przy czym parametr regularyzacyjny w tym przypadku wynosi α = 0,000 00007. {\displaystyle \alpha =0{,}00000007.} Poniżej znajduje się kod źródłowy w pakiecie MATLAB z omawianym przykładem:

a = 0.00000007;% parametr regularyzacyjny %macierz A A=[1 2 3 4; 1 3 1 5; 1.99999999 3.99999999 6.00000001 8.0000001;7 5 3 1]; %wektor x x = [1;2;2;1]; % wektor b b = A*x; % uchwyt do funkcji bez regularyzacji fun = @(xx)(A*xx-b)*(A*xx-b)'; % uchwyt do funkcji z regularyzacją fun2 = @(xx)(A*xx-b)*(A*xx-b)'+a*xx*xx'; %rozwiązanie metodą najmniejszych kwadratów x1 = lsqnonlin(fun,0*x); x2 = lsqnonlin(fun2,0*x); hold all plot(x,'o') plot(x1) plot(x2) grid on legend('szukane wartości','rozwiązanie bez regularyzacji',... 'rozwiązanie z regularyzacją') 

Zobacz też | edytuj kod

Przypisy | edytuj kod

  1. A. N. Tikhonov, Solution of incorrectly formulated problems and the regularization method, Soviet Math. Dokl., 4 (1963), s. 1035–1038; English translation of Dokl. Akad. Nauk. SSSR, 151 (1963), s. 501–504.
  2. D. L. Phillips, A technique for the numerical solution of certain integral equations of the first kind, J. Assoc. Comput. Mach., 9 (1962), s. 84–97.
  3. a b G.R. Liu, X. Han: Computational Inverse Techniques in Nondestructive Evaluation. CRC Press, 2003. ISBN 978-0-8493-1523-7.
  4. D. Calvetti, S. Morigi, L. Reichel, F. Sgallari, Tikhonov regularization and the L-curve for large discrete ill-posed problems, Journal of Computational and Applied Mathematics, Volume 123, Issues 1–2, 1 November 2000, Pages 423-446, ISSN 0377-0427, http://dx.doi.org/10.1016/S0377-0427(00)00414-3.

Linki zewnętrzne | edytuj kod

Na podstawie artykułu: "Regularyzacja Tichonowa" pochodzącego z Wikipedii
OryginałEdytujHistoria i autorzy