MN05LAB

Ćwiczenia: normy i uwarunkowanie

Ćwiczenie: Normy macierzowe

Pokazać, że dla macierzy Parser nie mógł rozpoznać (nieznana funkcja „\inR”): {\displaystyle \displaystyle A=(a_{i,j})_{i.j=1}^n\inR^{n\times n}} mamy

$\Vert A{\Vert }_1=\Vert A^T{\Vert }_{\mathrm{\infty }}=\underset{1\le j\le n}{\max }\sum _{i=1}^n|a_{i,j}|$

oraz

$\Vert A{\Vert }_{\mathrm{\infty }}=\underset{1\le i\le n}{\max }\sum _{j=1}^n|a_{i,j}|.$

Rozwiązanie

Pokażemy pierwszą równość, druga dowodzi się analogicznie.

Najpierw udowodnimy, że dla dowolnego wektora $x$ o normie $||x|{|}_1=1$,

$||Ax|{|}_1\le \underset{1\le j\le n}{\max }\sum _{i=1}^n|a_{i,j}|,$

a następnie wskażemy taki wektor $x$, dla którego zachodzi równość.

Istotnie, dla $||x|{|}_1=1$,

$|(Ax{)}_i|=|\sum _{j=1}^n{a}_{ij}{x}_j|\le \sum _{j=1}^n|a_{ij}|\cdot |x_j|\le \underset{j}{\max }|a_{ij}|\sum _{j=1}^n|x_j|=\underset{j}{\max }|a_{ij}|,$

bo $\sum _{j=1}^n|x_j|=||x|{|}_1=1$, zatem

$||Ax|{|}_1=\sum _i|(Ax{)}_i|\le \underset{j}{\max }\sum _{i=1}^n|a_{ij}|.$

Niech teraz $i_0$ będzie indeksem kolumny macierzy $A$, dla którego powyższe maksimum jest przyjmowane. Wtedy w powyższym oszacowaniu równość jest przyjmowana dla wektora $x=e_{i_0}$, czyli wektora, który na współrzędnej $i_0$ ma jedynkę, a poza nią --- same zera.

Ćwiczenie

Pokaż, że dla macierzy rzeczywistej $N\times M$,

$||A|{|}_2=\max \{\sqrt{\lambda }:\lambda \text{ jest wartością własną macierzy }{A}^{T}A\}.$

Wskazówka

Macierz $A^{T}A$ jest macierzą symetryczną, co można powiedzieć o jej wartościach i wektorach własnych?

Rozwiązanie

Niech $B=A^{T}A$. Jako macierz symetryczna, ma ona rozkład

$B=Q^T\mathrm{\Lambda }Q,$

gdzie $Q$ jest macierzą ortogonalną, $Q^{T}Q=I$, natomiast $\mathrm{\Lambda }$ jest macierzą diagonalną (z wartościami własnymi $B$ na diagonali). Poza tym $B$ jest nieujemnie określona (dlaczego?), więc wartości własne $B$ są nieujemne, zatem wyciąganie z nich pierwiatka ma sens!

Dla dowolnego wektora $x$ mamy

$||Ax|{|}_2^2=(Ax{)}^{T}Ax=x^T{A}^{T}Ax=x^{T}Bx=x^T{Q}^T\mathrm{\Lambda }Qx,$

skąd, definiując $y=Qx$,

$||A|{|}_2^2=\underset{x}{\max }\frac{||Ax|{|}_2^2}{||x|{|}_2^2}=\underset{y}{\max }\frac{||\mathrm{\Lambda }y|{|}_2^2}{||y|{|}_2^2}=\max \{{\lambda }_i\},$

bo $||Qx|{|}_2=||y|{|}_2$.

Ćwiczenie

Dla wektora Parser nie mógł rozpoznać (nieznana funkcja „\inR”): {\displaystyle \displaystyle x=(x_j)_{j=1}^n\inR^n} , niech $r{d}_{\nu }(x)=(r{d}_{\nu }(x_j){)}_{j=1}^n$. Pokazać, że

$\Vert x-r{d}_{\nu }(x){\Vert }_p\le \nu \Vert x{\Vert }_p$

dla $1\le p\le \mathrm{\infty }$.

Ćwiczenie

Dla macierzy $A=(a_{i,j}{)}_{i,j=1}^n$, niech $r{d}_{\nu }(A)=(r{d}_{\nu }(a_{i,j}){)}_{i,j=1}^n$. Pokazać, że

$\Vert A-r{d}_{\nu }(A){\Vert }_p\le \nu \Vert A{\Vert }_p,$

dla $p=1,\mathrm{\infty }$, oraz

$\Vert A-r{d}_{\nu }(A){\Vert }_2\le \Vert A-r{d}_{\nu }(A){\Vert }_E\le \nu \Vert A{\Vert }_E\le \sqrt{n}\nu \Vert A{\Vert }_2.$

Ćwiczenie

Czy algorytm eliminacji Gaussa dla $Ax=b$, gdzie macierz $A$ jest symetryczna i dodatnio określona zawsze da wynik $\tilde{x}$ o dużej dokładności, rzędu precyzji arytmetyki?

Wskazówka

Oceń wskaźnik wzrostu i skorzystaj z twierdzenia o numerycznej poprawności

Rozwiązanie

Dla naszej macierzy wskaźnik wzrostu ${\rho }_N\le 2$, zatem algorytm eliminacji Gaussa jest numerycznie poprawny. Ale nie znaczy to, że da wynik $\tilde{x}$ taki, że

$\frac{||x-\tilde{x}||}{||x||}\approx \nu .$

Ponieważ $\tilde{x}$ jest dokładnym rozwiązaniem równania z macierzą zaburzoną, $\tilde{A}\tilde{x}=b$, należy ocenić wpływ zaburzenia macierzy na jakość wyniku, a tu już wiemy, że jeśli zaburzenie jest dostatecznie małe (czyli, gdy precyzja arytmetyki jest dostatecznie duża), to

$\frac{||x-\tilde{x}||}{||x||}\approx K\cdot \text{cond}(A)\cdot \nu ,$

a więc błąd będzie mały tylko wtedy, gdy uwarunkowanie $A$ będzie niewielkie! Dobrym przykładem jest tu macierz Hilberta, która jest symetryczna i dodatnio określona, lecz mimo to już dla średnich $N$ algorytm eliminacji Gaussa daje wyniki obarczone stuprocentowym błędem! Potwierdź to eksperymentalnie!

Ćwiczenie: Numeryczne kryterium "numerycznej poprawności"

Jeśli

$(A+E)z=b,$

gdzie $\Vert E{\Vert }_p\le K\nu \Vert A{\Vert }_p$, to oczywiście dla residuum $r=b-Az$ mamy

$\Vert r{\Vert }_p\le K\nu \Vert A{\Vert }_p\Vert z{\Vert }_p.$

Pokazać, że dla $p=1,2,\mathrm{\infty }$ zachodzi też twierdzenie odwrotne, tzn. jeśli spełniony jest powyższy warunek dla residuum, to istnieje macierz pozornych zaburzeń $E$ taka, że $\Vert E{\Vert }_p\le K\nu \Vert A{\Vert }_p$ oraz spełniona jest równość $(A+E)z=b$.

Jest to tak zwane numeryczne kryterium "numerycznej poprawności", bo (dla konkretnych danych) pozwala, wyłącznie na podstawie obliczonych numerycznie wartości ocenić zaburzenie pozorne macierzy, dla którego numeryczny wynik jest dokładnym rozwiązaniem.

Wskazówka

Rozpatrzyć

$E=r(\text{sgn}{z}_i{)}_{1\le i\le n}^T/\Vert z{\Vert }_1$ dla $p=1$, $E=r{z}^T/\Vert z{\Vert }_2^2$ dla $p=2$, oraz $E=r(\text{sgn}{z}_k)e_k^T/\Vert z{\Vert }_{\mathrm{\infty }}$ dla $p=\mathrm{\infty }$,

gdzie $k$ jest indeksem dla którego $|z_k|=\Vert z{\Vert }_{\mathrm{\infty }}$.