\documentclass[10pt,a4paper]{article}

%% Polonizacja
\usepackage[T1]{fontenc}
\usepackage[latin2]{inputenc}
\usepackage{polski}
\usepackage{indentfirst}

%% Wzorki matematyczne
\usepackage{amsmath,amsfonts}

\begin{document}

\newcounter{seria}
\setcounter{seria}{1}
\newcommand*{\preparedby}{Jakub Narębski}
\input{naglowek.tex}

\section{Dokładność numeryczna}

Liczby rzeczywiste są przechowywane w~komputerze ze skończoną
dokładnością.  Skończony jest także zakres tych liczb.  W~związku
z~tym przy obliczeniach na liczbach rzeczywistych pojawiają się błędy
numeryczne.  Musimy zatem z~różnych poprawnych matematycznie
algorytmów wybrać taki, który powoduje najmniejszy błąd związany
z~prowadzeniem obliczeń na komputerze.

Przy pomocy prostych przykładów chcielibyśmy zilustrować, że
nie każdy poprawny matematycznie algorytm obliczania danego 
wzoru jest poprawny numerycznie. Często użycie złego algorytmu
prowadzi do znacznego błędu.
 

\subsection{Reprezentacja liczb rzeczywistych (zmiennoprzecinkowych)}

Każdą liczbę $x$, $x \neq 0$ można reprezentować jednoznacznie
w~postaci wykładniczej \(x = s \cdot m \cdot 2^c\), gdzie $s \in
\{-1,1\}$ jest znakiem liczby, $m \in [\frac{1}{2}, 1)$ nazywamy
\textbf{mantysą}, a $c \in \mathbb{Z}$ nazywamy \textbf{cechą}.
W~komputerze $m$ i~$c$ są reprezentowane za pomocą skończonej ilości
bitów.  W~związku ze skończonym zakresem wartości przyjmowanych przez
cechę \(c_{\text{min}} \leq c \leq c_{\text{max}}\) w~reprezentacji
zmiennoprzecinkowej można reprezentować tylko liczby ze skończonego
zakresu
\begin{math}
  \frac{1}{2} 2^{c_{\text{min}}} \leq 
  \lvert x \rvert <
  2^{c_{\text{max}}}
\end{math}
oraz 0.  W~związku ze skończoną ilością $t$ bitów mantysy
reprezentacja zmiennoprzecinkowa może różnić się od wartości ścisłej:
\(\tilde{x}_t = rd(x) = x(1 + \epsilon)\), gdzie \(\lvert \epsilon
\rvert \leq 2^{-t}\).

Możliwe źródła błędów numerycznych
\begin{itemize}
\item Błędy danych wejściowych, czy to związane z~pomiarem, czy to
  powstałe w~wyniku obcięcia przy przejściu do reprezentacji
  zmiennoprzecinkowej. 

\item Błędy obcięcia powstałe przez zastąpienie granicy (np. sumy
  nieskończonej) przez $n$--ty wyraz ciągu (sumę częściową).

\item Błędy zaokrągleń wynikające z~prowadzenia obliczeń na liczbach
  zmiennoprzecinkowych: 
  \begin{equation*}
    \mathit{fl}(a \Box b) = (a \Box b)(1 + \epsilon(a, b, \Box))
  \end{equation*}
  Przykładowo przy dodawaniu (odejmowaniu) dwu liczb
  zmiennoprzecinkowych najpierw sprowadza się je przeskalowywując do
  wspólnej cechy, dodaje mantysy a~następnie odrzuca bity poza
  zakresem.
\end{itemize}

\noindent
\textbf{Zadanie 1.} Znaleźć najmniejsze takie $a \neq 0$, że
w~obliczeniach zmiennoprzecinkowych $\mathit{fl}(1 + a) = 1$.  Znaleźć
taką liczbę $a$, że $\mathit{fl}(1/a \ast a) \neq 1$.  \emph{Uwaga:}
w~razie potrzeby zastosować zmienne pomocnicze (volatile) aby uniknąć
optymalizacji kompilatora.



\subsection{Unikanie nadmiaru i niedomiaru (w obliczeniach pośrednich)}

Chcemy obliczyć wartość bezwzględną liczby zespolonej $z = a +
\mathrm{i} b \neq 0$ lub długość przeciwprostokątnej trójkąta o
przyprostokątnych $a$ i $b$, czy też odległość euklidesową między
dwoma punktami na płaszczyźnie.

Klasyczny algorytm $\lvert z \rvert = \sqrt{a^2 + b^2}$ może prowadzić
do nadmiaru lub niedomiaru w obliczeniach pośrenich, podczas gdy wynik
jest reprezentowalny w arytmetyce zmiennoprzecinkowej.

Lepszy algorytm wygląda następująco
\begin{tabbing}
aaa\=\kill\\
\textbf{if} ($\lvert a \rvert > \lvert b \rvert$) \textbf{then}\\
\>z = $\lvert a \rvert \sqrt{1 + \left(\frac{\lvert b \rvert}{\lvert a \rvert}\right)^2}$\\
\textbf{else}\\
\>z = $\lvert b \rvert \sqrt{1 + \left(\frac{\lvert a \rvert}{\lvert b \rvert}\right)^2}$\\
\end{tabbing}


\textbf{Zadanie 2.} Zaimplementować oba te algorytmy.  Porównać ich
dokładność oraz dokładność funkcji bibliotecznej \texttt{hypot} (z
\texttt{math.h}).  Dla jakich $a$ i~$b$ metoda klasyczna nie działa, 
a druga metoda daje poprawne wyniki (do tego nie trzeba użyć
komputera)? 



\subsection{Redukcja cyfr znaczących przy odejmowaniu bliskich sobie liczb}


\subsubsection{Szacowanie błędu algorytmu na przykładzie wzoru $a^2-b^2$}

Istnieją dwa algorytmy obliczania wzoru $a^2-b^2$.
\begin{eqnarray}
&& a^2-b^2 \nonumber \\
&& (a-b)(a+b)
\end{eqnarray}

Każde działanie numeryczne generuje pewien błąd w porównaniu do rzeczywistej
wartości wyniku dzialania:
\begin{eqnarray}
fl(a+b) = (a+b)(1+\epsilon) \nonumber \\
fl(a*b) = (a*b)(1+\epsilon)  \\
fl(\sqrt{a}) = \sqrt{s}(1+\epsilon), \nonumber
\end{eqnarray}
gdzie poprzez $fl(a\Box b)$ oznaczamy wynik numerycznego dzialania $\Box$.

Oszacujmy błędy otrzymane w obu algorytmach:
\begin{eqnarray}
fl(a^2-b^2) &=& (a*a(1+\epsilon_1)-b*b(1+\epsilon_2))(1+\epsilon_3)\nonumber \\
&=& (a^2-b^2)\left(1+\frac{a^2\epsilon_1-b^2\epsilon_2}{a^2-b^2}\right)(1+\epsilon_3) \\
&=& (a^2-b^2)(1+\delta) \nonumber, 
\end{eqnarray}
gdzie $\delta = \frac{a^2\epsilon_1-b^2\epsilon_2}{a^2-b^2}(1 -
\epsilon_3) + \epsilon_3$. Jeżeli $a^2$ jest odpowiednio bliskie $b^2$, 
a $\epsilon_1$ i $\epsilon_2$ maja przeciwne znaki, to błąd względny 
$\delta$ wyniku otrzymanego pierwszym algorytmem może być dowolnie duży. 


Nie jest to prawda w przypadku drugiego algorytmu:
\begin{equation}
  \begin{split}
    fl((a-b)(a+b)) &= ((a-b)(1+\epsilon_1)(a+b)(1+\epsilon_2))(1+\epsilon_3) \\
                   &= (a^2-b^2)(1+\delta), 
  \end{split}
\end{equation}
gdzie $\delta \leq |\epsilon_1|+|\epsilon_2|+|\epsilon_3|$.


\subsubsection{Obliczanie zer równania kwadratowego}

\begin{equation}
  x^2 - 2px + q = 0
\end{equation}

W szkole stosuje się algorytm:
\begin{subequations}
  \begin{align}
    x_1 &= p+\sqrt{p\cdot p-q} \\
    x_2 &= p-\sqrt{p\cdot p-q}
  \end{align}
\end{subequations}

Poprawny algorytm wygląda następująco: obliczamy ten pierwiastek dla
którego mamy we wzorze dodawanie, a~drugi obliczamy na podstawie wzoru
Verleta $x_1 \cdot x_2 = q$.  Zapis tego algorytmu poniżej

\bigskip

\begingroup\ttfamily
\noindent
if $p\ge 0$ then
\begin{eqnarray}
x_1 &=& p+\sqrt{p\cdot p-q} \\
x_2 &=& q/x_1 \nonumber
\end{eqnarray}
if $p<0$ then
\begin{eqnarray}
x_2 &=& p-\sqrt{p\cdot p-q} \\
x_1 &=& q/x_2 \nonumber
\end{eqnarray}
\endgroup

Kiedy algorytm 'szkolny' jest niepoprawny? Może on generować znaczny
błąd w chwili gdy np. $p\cdot p\gg q$.  

\textbf{Zadanie 3.} Zaimplementować oba te algorytmy.  Poszukać takich
wartości $p$ i $q$, dla których algorytmy dają różne wyniki.  Który
algorytm jest dokładniejszy?
%%
\input{podpis.tex}

\end{document}

