 \begin{enumerate}
  \item[a)] Das Neville--Schema l\"asst sich v\"ollig analog zu den
            dividierten Differenzen in einem Schema darstellen.
\[
\begin{array}{c|ccccccc}
   &k = 0  &&  k = 1  &&  k = 2  && k=3\\ \hline
%
x_0&f_0=P_{0,0}&{\phantom{\nearrow}\atop\searrow}&\\
   &          &                       &P_{1,1}&{\phantom{\nearrow}\atop\searrow}& \\
x_1&f_1=P_{1,0}&{\nearrow\atop\searrow}&                                        &                       &P_{2,2}&{\phantom{\nearrow}\atop\searrow}\\
   &          &                       &P_{2,1}&{\nearrow\atop\searrow}&                   &        &P_{3,3}\\
x_2&f_2=P_{2,0}&{\nearrow\atop\searrow}&                                        &                       &P_{3,2}&{\nearrow\atop\searrow}&  \\
   &          &                       &P_{3,1}&{\nearrow\atop{\searrow}}&  \vdots \\
x_3&f_3=P_{3,0}&{\nearrow\atop\searrow}&  \vdots  & & \\
x_4&  \vdots  &  & & \\
 \vdots  & & & & 
\end{array}
\]
 Dabei bedeuten die Pfeile immer die Berechnung von $P_{i,k}$ aus
 $P_{i-1,k-1}$ und $P_{i,k-1}$ nach der Formel
 \item[b)] 
 Zur Berechnung von $P_{n,n}$ k\"onne wir in einem ersten Schritt die
 Formel umschreiben.
\begin{eqnarray*}
 P_{i,k}&=&\frac{(x-t_{i-k})P_{i,k-1}-(x-t_i)P_{i-1,k-1}}{t_{i}-t_{i-k}}\\
        &=&\frac{(x-t_{i-k})P_{i,k-1}-(t_{i-k}-t_i)P_{i-1,k-1}+(t_{i-k}-x)P_{i-1,k-1}}{t_{i}-t_{i-k}}\\
        &=&P_{i-1,k-1}+(P_{i,k-1}-P_{i-1,k-1})\frac{x-t_{i-k}}{t_{i}-t_{i-k}}
\end{eqnarray*}
 Wir k\"onnen die 
 St\"utzstellen $t_0,\dots,t_n$ durch $t_0:=x-t_0,\dots,t_n:=x-t_n$ ersetzen.
 Dies kostet $n+1$ \flops.
 Somit lautet unsere Formel zur Berechnung von $P_{i,k}$ jetzt
 $P_{i,k}:=\displaystyle P_{i-1,k-1}+(P_{i,k-1}-P_{i-1,k-1})\frac{t_{i-k}}{t_{i-k}-t_{i}}$.
 Das Tableau aus Teil a) zeigt uns, dass diese Formel insgesamt
 $n+(n-1)+\cdots+1=\frac{n(n+1)}{2}$ Mal angewendet werden muss.
 In jedem Schritt kostet das jetzt noch 5 \flops. Also haben wir insgesamt
 \[
\frac{(5n+2)(n+1)}{2} \flops.
\]
 Dagegen kostet laut \"Ubung \ref{numI/uebung055}, \ref{numI/uebung056} das Newton--Schema, also dividierte Differenzen
 plus Horner--artige Auswertung $\frac{3n(n+3)}{2} \flops$. D.h. die 
 Newtondarstellung mittels dividierter Differenzen ist billiger. Und das schon
 bei einer Auswertung. Schlimmer wird es, wenn man an mehreren Stellen $x$
 das Interpolationspolynom berechnen will. Hier hat man aufgrund der expliziten
 Darstellung bei den dividierten Differenzen nur $3n\flops$ w\"ahrend man
 das Neville--Schema komplett neu durchlaufen muss.
  \item[c)] 
            Nehme an, dass $t_i=h^2 4^{-i}$, $i=0,\dots,n$. 
            In diesem Fall haben wir nach Teil b)
\[
P_{i,k}=P_{i-1,k-1}+(P_{i,k-1}-P_{i-1,k-1})\frac{4^{k-i}}{4^{k-i}-4^{-i}}
       =P_{i-1,k-1}+\frac{P_{i,k-1}-P_{i-1,k-1}}{1-4^{-k}}
\]
 So umgeschrieben ist das Neville--Schema jetzt deutlich billiger.
 Der Ausdruck $1-4^{-k}$ l\"asst sich f\"ur jedes $k=1,2,\dots,n$ aufdatieren
 durch sukzessives Vierteln und anschliessender Subtraktion.
 Das kostet schon mal $2n\flops$. Der verbleibende Ausdruck kann in 
 $\frac{n(n+1)}{2}$ Schritten mit Kosten von 3\flops pro Schritt berechnet
 werden. Also insgesamt
\[
 \frac{n(3n+7)}{2}\flops.
\]
 Das ist jetzt ungef\"ahr so teuer wie die Newton--Darstellung. Es er\"ubrigt
 sich allerdings zu sagen, dass auch die Newton--Darstellung in diesem Fall
 vereinfacht werden kann.
 \end{enumerate}
