Personal tools

MN07LAB

From Studia Informatyczne


Normy i uwarunkowanie

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

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

Ćwiczenie: Normy macierzowe

Pokazać, że dla macierzy \displaystyle A=(a_{i,j})_{i.j=1}^n\inR^{n\times n} mamy

\displaystyle \|A\|_1 \,=\, \|A^T\|_\infty \,=\,          \max_{1\le j\le n}\sum_{i=1}^n |a_{i,j}|

oraz

\displaystyle \|A\|_\infty \,=\, \max_{1\le i\le n}\sum_{j=1}^n |a_{i,j}|.
Rozwiązanie

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

Najpierw udowodnimy, że dla dowolnego wektora \displaystyle x o normie \displaystyle ||x||_1 = 1 zachodzi

\displaystyle ||Ax||_1 \leq \max_{1\le j\le n}\sum_{i=1}^n |a_{i,j}|,

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

Istotnie, dla \displaystyle ||x||_1 = 1,

\displaystyle  |(Ax)_i| = |\sum_{j=1}^n a_{ij}x_j| \leq \sum_{j=1}^n |a_{ij}|\cdot|x_j| \leq \max_j|a_{ij}|\sum_{j=1}^n |x_j| = \max_j|a_{ij}|,

bo \displaystyle \sum_{j=1}^n |x_j|  = ||x||_1 = 1, zatem

\displaystyle  ||Ax||_1 = \sum_i |(Ax)_i|\leq \max_j \sum_{i=1}^n |a_{ij}|.

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

Ćwiczenie

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

\displaystyle  ||A||_2 = \max \{\sqrt{\lambda} : \lambda  \mbox{ jest wartością własną macierzy }  A^TA\}.

Wskazówka

Macierz \displaystyle A^TA jest macierzą symetryczną, co można powiedzieć o jej wartościach i wektorach własnych?

Rozwiązanie

Niech \displaystyle B= A^TA. Jako macierz symetryczna, ma ona rozkład

\displaystyle  B = Q^T\Lambda Q,

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

Dla dowolnego wektora \displaystyle x mamy

\displaystyle  ||Ax||_2^2  = (Ax)^TAx = x^T A^TA x = x^T B x = x^TQ^T\Lambda Q x,

skąd, definiując \displaystyle y=Qx,

\displaystyle  ||A||_2^2 = \max_x\frac{||Ax||_2^2 }{||x||_2^2} = \max_y\frac{||\Lambda y||_2^2 }{||y||_2^2} = \max \{\lambda_i\},

bo \displaystyle ||Qx||_2 = ||y||_2.

Ćwiczenie

Dla wektora \displaystyle  x=(x_j)_{j=1}^n\inR^n, niech \displaystyle rd_\nu( x)=(rd_\nu(x_j))_{j=1}^n. Pokazać, że

\displaystyle \| x-rd_\nu( x)\|_p\,\le\,\nu\,\| x\|_p

dla \displaystyle 1\le p\le\infty.

Rozwiązanie

Pokażemy dla \displaystyle p < +\infty, dla \displaystyle p=+\infty jest jeszcze łatwiej. dowodzi się analogicznie. Ponieważ \displaystyle |x_i - rd_\nu( x_i)| \leq \nu |x_i|, to

\displaystyle \| x-rd_\nu( x)\|_p^p = \sum_i |x_i - rd_\nu( x_i)|^p \le \sum_i \nu^p\,| x_i|_p^p = \nu^p \|x\|_p^p.

Ćwiczenie

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

\displaystyle \|A-rd_\nu(A)\|_p\,\le\,\nu\,\|A\|_p,

dla \displaystyle p=1,\infty, oraz

\displaystyle \|A-rd_\nu(A)\|_2\,\le\,\|A-rd_\nu(A)\|_E\,\le\,\nu\,\|A\|_E     \,\le\,\sqrt{n}\,\nu\,\|A\|_2.

Wskazówka

To zadanie robi się podobnie jak zadanie poprzednie.

Ćwiczenie

Czy algorytm eliminacji Gaussa dla \displaystyle Ax=b, gdzie macierz \displaystyle A jest symetryczna i dodatnio określona zawsze da wynik \displaystyle \widetilde{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 \displaystyle \rho_N \leq 2, zatem algorytm eliminacji Gaussa jest numerycznie poprawny. Ale nie znaczy to, że da wynik \displaystyle \widetilde{x} taki, że

\displaystyle \frac{||x-\widetilde{x}||}{||x||} \approx \nu.

Ponieważ \displaystyle \widetilde{x} jest dokładnym rozwiązaniem równania z macierzą zaburzoną, \displaystyle \widetilde{A}\widetilde{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

\displaystyle \frac{||x-\widetilde{x}||}{||x||} \approx K\cdot   \mbox{cond} (A)\cdot \nu,

a więc błąd będzie mały tylko wtedy, gdy uwarunkowanie \displaystyle 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 \displaystyle N algorytm eliminacji Gaussa daje wyniki obarczone stuprocentowym błędem! Potwierdź to eksperymentalnie!

Ćwiczenie: Numeryczne kryterium "numerycznej poprawności"

Jeśli

\displaystyle    (A+E) z\,=\, b,

gdzie \displaystyle \|E\|_p\le K\nu\|A\|_p, to oczywiście dla residuum \displaystyle  r= b-A z mamy

\displaystyle    \| r\|_p\,\le\,K\nu\|A\|_p\| z\|_p.

Pokazać, że dla \displaystyle p=1,2,\infty zachodzi też twierdzenie odwrotne, tzn. jeśli spełniony jest powyższy warunek dla residuum, to istnieje macierz pozornych zaburzeń \displaystyle E taka, że \displaystyle \|E\|_p\le K\nu\|A\|_p oraz spełniona jest równość \displaystyle (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ć

\displaystyle E= r( \mbox{sgn} \,z_i)_{1\le i\le n}^T/\| z\|_1 dla \displaystyle p=1, \displaystyle E= r z^T/\| z\|_2^2 dla \displaystyle p=2, oraz \displaystyle E= r( \mbox{sgn} \,z_k) e_k^T/\| z\|_\infty dla \displaystyle p=\infty,

gdzie \displaystyle k jest indeksem dla którego \displaystyle |z_k|=\| z\|_\infty.