\documentclass[12pt,a4paper]{article}
\usepackage{ngerman}
\usepackage{amsmath}
\renewcommand{\labelenumi}{(\emph{\alph{enumi}})}
\renewcommand{\labelenumii}{\arabic{enumii}.}

\begin{document}
\noindent\textbf{First name:} Christoph\\
\textbf{Last Name:} Oberauer\\
\textbf{Email:} coberau@cosy.sbg.ac.at\\
\textbf{Date:} 18.01.2003\\
\textbf{Homework number:} 6\\
\textbf{Homework Title:} Exercise 7.5


\paragraph{Problem description:\\}
\begin{enumerate}
\item
Determine the polynomial interpolant to the data
$$
\begin{tabular}{ccccc}
t&1&2&3&4\\
y&11&29&65&125
\end{tabular}
$$
using monomial basis.
\item
Determine the Lagrange polynomial interpolant to the same data and show that the resulting polynomial is equivalent to that obtained in part $a$.
\item
Compute the Newton polynomial interpolant to the same data using each of the three methods given in the text (triangular matrix, incremental interpolation, divided differences) and show that each produces the same result as the previous two methods.
\end{enumerate}


\paragraph{Problem solution:}
\begin{enumerate}
\item
Solve linear system
$$Ax=\left[\begin{array}{cccc}1&1&1&1\\1&2&4&8\\1&3&9&27\\1&4&16&64\end{array}\right]\left[\begin{array}{c}x_1\\x_2\\x_3\\x_4\end{array}\right]=\left[\begin{array}{c}11\\29\\65\\125\end{array}\right]$$
\item
Use definition for Lagrange polynomial of degree 3
\item
Newton polynomials\\
Triangular matrix:\\
$$\left[\begin{array}{cccc}1&0&0&0\\1&1&0&0\\1&2&2&0\\1&3&6&6\end{array}\right]\left[\begin{array}{c}x_1\\x_2\\x_3\\x_4\end{array}\right]=\left[\begin{array}{c}11\\29\\65\\125\end{array}\right]$$
Incremental interpolation:\\
\begin{align*}
    p_1(t)&=y_1\\
p_{j+1}(t)&=p_j(t)+x_{j+1}\pi_{j+1}(t)\\
   x_{j+1}&=\frac{y_{j+1}-p_j(t_{j+1})}{\pi_{j+1}(t_{j+1})}
\end{align*}
Divided differences: applying data in this definition yields coefficients for basis functions:\\
$$f[t_1, t_2, \dots , t_k]=\frac{f[t_2, t_3, \dots , t_k]-f[t_1, t_2, \dots , t_{k-1}]}{t_k-t_1}$$
$$x_j=f[t_1, t_2, \dots , t_j]$$
\end{enumerate}


\paragraph{Results:}
\begin{enumerate}
\item
$$(x_1,x_2,x_3,x_4)=(5,2,3,1)$$
$$p(t)=t^3+3t^2+2t+5$$
\item
\begin{align*}
p(t)=&11\frac{(t-2)(t-3)(t-4)}{(-1)(-2)(-3)}+29\frac{(t-1)(t-3)(t-4)}{(1)(-1)(-2)}+\\
     &+65\frac{(t-1)(t-2)(t-4)}{(2)(1)(-1)}+125\frac{(t-1)(t-2)(t-3)}{(3)(2)(1)}
\end{align*}
Simplified
$$p(t)=t^3+3t^2+2t+5$$
\item
Newton polynomials\\
Triangular matrix:\\
Using forward substitution $x_1=11, x_2=18, x_3=9, x_4=1$, so
\begin{align*}
p(t)&=11+18(t-1)+9(t-1)(t-2)+(t-1)(t-2)(t-3)\\
    &=t^3+3t^2+2t+5
\end{align*}
Incremental interpolation:\\
\begin{align*}
p_1(t)&=11\\
   x_2&=\frac{29-11}{(2-1)}=18\\
p_2(t)&=11+18t-18=18t-7\\
   x_3&=\frac{65-47}{(3-1)(3-2)}=9\\
p_3(t)&=18t-7+9(t-1)(t-2)=9t^2-9t+11\\
   x_4&=\frac{125-119}{6}=1\\
p_4(t)&=9t^2-9t+11+(t-1)(t-2)(t-3)\\
      &=t^3+3t^2+2t+5
\end{align*}
Divided differences:\\
After doing some recursive calculations: $x_1=11, x_2=18, x_3=9, x_4=1$, which are the same coefficients as in the triangular matrix method, so $p(t)=t^3+3t^2+2t+5$.
\end{enumerate}


\paragraph{Discussion and Comments:}
\end{document}