MN04LAB

Ćwiczenie

Aby obliczyć $S(a,b)=a^2-b^2$ można zastosować dwa algorytmy: ${\mathbf{𝐀}\mathbf{𝐋}\mathbf{𝐆}}_1(a,b)=a*a-b*b$ oraz ${\mathbf{𝐀}\mathbf{𝐋}\mathbf{𝐆}}_2(a,b)=(a+b)*(a-b)$. Pokazać, że oba algorytmy są numerycznie poprawne, ale drugi z nich wywołuje mniejszy błąd względny wyniku w przypadku, gdy $r{d}_{\nu }(a)=a$ i $r{d}_{\nu }(b)=b$.

Ćwiczenie

Pokazać, że naturalny algorytm obliczania cosinusa kąta między dwoma wektorami Parser nie mógł rozpoznać (nieznana funkcja „\inR”): {\displaystyle \displaystyle a, b\inR^n} ,

$\cos (a,b)=\frac{\sum _{j=1}^n{a}_j{b}_j}{\sqrt{\left(\sum _{j=1}^n{a}_j^2\right)\left(\sum _{j=1}^n{b}_j^2\right)}},$

jest numerycznie poprawny. Oszacować błąd względny wyniku w $f{l}_{\nu }$.

Ćwiczenie

Pokazać, że naturalny algorytm obliczania $\Vert Ax{\Vert }_2$ dla danej macierzy Parser nie mógł rozpoznać (nieznana funkcja „\inR”): {\displaystyle \displaystyle A\inR^{n\times n}} i wektora Parser nie mógł rozpoznać (nieznana funkcja „\inR”): {\displaystyle \displaystyle x\inR^n} jest numerycznie poprawny. Dokładniej,

$f{l}_{\nu }(\Vert Ax{\Vert }_2)=(A+E)x,$

gdzie $\Vert E{\Vert }_2\le 2(n+2)\sqrt{n}\nu \Vert A{\Vert }_2$. Ponadto, jeśli $A$ jest nieosobliwa to

$|f{l}_{\nu }(\Vert Ax{\Vert }_2)-\Vert Ax{\Vert }_2|\le 2(n+2)\sqrt{n}\nu (\Vert A{\Vert }_2\Vert A^{-1}{\Vert }_2)\Vert Ax{\Vert }_2.$

Ćwiczenie

Niech $\mathbf{𝐀}\mathbf{𝐋}\mathbf{𝐆}$ będzie algorytmem numerycznie poprawnym w zbiorze danych $f\in F_0$, przy czym dla małych $\nu$, $f{l}_{\nu }(\mathbf{𝐀}\mathbf{𝐋}\mathbf{𝐆}(f))=\phi (y_{\nu })$, gdzie $\Vert y_{\nu }-y\Vert \le K\nu \Vert y\Vert$ i $K$ nie zależy od $\nu$ i $f$ ($y=N(f)$). Pokazać, że w ogólności $\mathbf{𝐀}\mathbf{𝐋}\mathbf{𝐆}$ nie musi być "numerycznie poprawny po współrzędnych", tzn. w ogólności nie istnieje bezwzględna stała $K_1$ taka, że dla małych $\nu$ i dla dowolnej $f\in F_0$

$|y_{\nu ,j}-y_j|\le K_1\nu |y_j|,1\le j\le n,$

gdzie $y=(y_1,\dots ,y_n)$.

Ćwiczenie

Podaj przykład funkcji $f$, której miejsce zerowe $x^{*}$ ma wspólczynnik uwarunkowania

• mały
• duży

Rozwiązanie

Ponieważ nasze zadanie to wyznaczenie $x^{*}=f^{-1}(0)$, to

${\text{cond}}_{abs}(f^{-1},0)=\frac{1}{f^{\prime }(x^{*})}.$

Znaczy to, że im bardziej płaska jest $f$ w otoczeniu pierwiastka $x^{*}$, tym bardziej nawet małe zaburzenia $f$ mogą spowodować duże przemieszczenie jej miejsca zerowego.

Zauważ, że dla wielokrotnych miejsc zerowych, ${\text{cond}}_{abs}(f^{-1},0)=\mathrm{\infty }$, co zgadza się z intuicją, bo może być, że nawet minimalne zaburzenie $f$ spowoduje, iż miejsc zerowych po prostu nie będzie...