MN07LAB

Normy i uwarunkowanie

<<< Powrót do strony głównej przedmiotu Metody numeryczne

Oglądaj wskazówki i rozwiązania __SHOWALL__
Ukryj wskazówki i rozwiązania __HIDEALL__

Ćwiczenie: Normy macierzowe

Pokazać, że dla macierzy $A=(a_{i,j}{)}_{i.j=1}^n\in R^{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ść, drugą dowodzi się analogicznie.

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

$||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 mamy 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 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 pierwiastka 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 $x=(x_j{)}_{j=1}^n\in R^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 }$.

Rozwiązanie

Pokażemy dla $p<+\mathrm{\infty }$, dla $p=+\mathrm{\infty }$ jest jeszcze łatwiej. dowodzi się analogicznie. Ponieważ $|x_i-r{d}_{\nu }(x_i)|\le \nu |x_i|$, to

$\Vert x-r{d}_{\nu }(x){\Vert }_p^p=\sum _i|x_i-r{d}_{\nu }(x_i){|}^p\le \sum _i{\nu }^p|x_i{|}_p^p={\nu }^p\Vert x{\Vert }_p^p$

Ć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$

Wskazówka

To zadanie robi się podobnie jak zadanie poprzednie.

Ć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 }}$.