chapter4-1.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "id": "b44d3722",
   "metadata": {},
   "source": [
    "# 4.1 Polynomial interpolation"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "60ac2661",
   "metadata": {},
   "source": [
    "In polynomial interpolation, we pick polynomials as the family of functions in the interpolation problem.\n",
    "\n",
    "- Data: $(x_{i},y_{i}),i=0,1,...,n$\n",
    "- Family: Polynomials\n",
    "\n",
    "The space of polynomials up to degree $n$ is a vector space. We will consider three choices for the basis for this vector space:\n",
    "\n",
    "- Basis:\n",
    "\n",
    "    - Monomial basis: $\\phi_{k}(x)=x^{k}$\n",
    "    - Lagrange basis: $\\phi_{k}(x)=\\prod_{j=0,j\\neq k}^{n}\\left(\\frac{x-x_{j}}{x_{k}-x_{j}}\\right)$\n",
    "    - Newton basis: $\\phi_{k}(x)=\\prod_{j=0}^{k-1}(x-x_{j})$\n",
    "where $k=0,1,...,n$.\n",
    "\n",
    "Once we decide on the basis, the interpolating polynomial can be written as a linear combination of the basis functions:\n",
    "\\begin{equation*}\n",
    "p_{n}(x)=\\sum_{k=0}^{n}a_{k}\\phi_{k}(x)\n",
    "\\end{equation*}\n",
    "where $p_{n}(x_{i})=y_{i},i=0,1,...,n.$\n",
    "\n",
    "Here is an important question. How do we know that $p_{n}$, a polynomial of degree at most $n$ passing through the data points, actually exists? Or, equivalently,\n",
    "how do we know the system of equations $p_{n}(x_{i})=y_{i},i=0,1,...,n$, has a solution?\n",
    "\n",
    "The answer is given by the following theorem, which we will prove later in this section."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "7d411a6f",
   "metadata": {},
   "source": [
    "\\begin{theorem}\\label{theo:chap3_thm47}\n",
    "If points $x_{0},x_{1},...,x_{n}$\n",
    "are distinct, then for real values $y_{0},y_{1},...,y_{n},$ there\n",
    "is a unique polynomial $p_{n}$ of degree at most $n$ such that $p_{n}(x_{i})=y_{i},i=0,1,...,n.$\n",
    "\\end{theorem}"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "972ede4f",
   "metadata": {},
   "source": [
    "We mentioned three families of basis functions for polynomials. The choice of a family of basis functions affects:\n",
    "\n",
    "- The accuracy of the numerical methods to solve the system of linear equations $Aa=y$.\n",
    "- The ease at which the resulting polynomial can be evaluated, differentiated, integrated, etc.\n"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "f34a3887",
   "metadata": {},
   "source": [
    "## Monomial form of polynomial interpolation"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "029a716f",
   "metadata": {},
   "source": [
    "Given data $(x_{i},y_{i}),i=0,1,...,n$, we know from the previous theorem that there exists a polynomial $p_n(x)$ of degree at most $n$, that passes through the data points. To represent $p_n(x)$, we will use the monomial basis functions, $1,x,x^{2},...,x^{n}$, or written more succinctly,\n",
    "\\begin{equation*}\n",
    "\\phi_{k}(x)=x^{k},k=0,1,...,n.\n",
    "\\end{equation*}\n",
    "The interpolating polynomial $p_n(x)$ can be written as a linear combination of these basis functions as\n",
    "\\begin{equation*}\n",
    "p_{n}(x)=a_{0}+a_{1}x+a_{2}x^{2}+...+a_{n}x^{n}.\n",
    "\\end{equation*}\n",
    "We will determine $a_{i}$ using the fact that $p_n$ is an interpolant for the data:\n",
    "\\begin{equation*}\n",
    "p_{n}(x_{i})=a_{0}+a_{1}x_{i}+a_{2}x_{i}^{2}+...+a_{n}x_{i}^{n}=y_{i}\n",
    "\\end{equation*}\n",
    "for $i=0,1,...,n.$ Or, in matrix form, we want to solve\n",
    "\\begin{equation*}\n",
    "\\underbrace{\\begin{bmatrix}1 & x_{0} & x_{0}^{2} & ... & x_{0}^{n}\\\\\n",
    "1 & x_{1} & x_{1}^{2} & \\cdots & x_{1}^{n}\\\\\n",
    "\\vdots & \\vdots & \\vdots & \\vdots & \\vdots\\\\\n",
    "1 & x_{n} & x_{n}^{2} & \\cdots & x_{n}^{n}\n",
    "\\end{bmatrix}}_A \\underbrace{\\begin{bmatrix}a_{0}\\\\\n",
    "a_{1}\\\\\n",
    "\\vdots\\\\\n",
    "a_{n}\n",
    "\\end{bmatrix}}_a=\\underbrace{\\begin{bmatrix}y_{0}\\\\\n",
    "y_{1}\\\\\n",
    "\\vdots\\\\\n",
    "y_{n}\n",
    "\\end{bmatrix}}_y\n",
    "\\end{equation*}\n",
    "for $[a_{0},...,a_{n}]^{T}$ where $[\\cdot]^T$ stands for the transpose of the vector.\n",
    "The coefficient matrix $A$ is known as the *van der Monde matrix*. This\n",
    "is usually an ill-conditioned matrix, which means solving the system of equations\n",
    "could result in large error in the coefficients $a_{i}.$ An intuitive\n",
    "way to understand the ill-conditioning is to plot several basis monomials,\n",
    "and note how less distinguishable they are as the degree increases,\n",
    "making the columns of the matrix nearly linearly dependent."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "4d047d3a",
   "metadata": {},
   "source": [
    "![Monomial basis functions.](./images/monbasis_plot.png)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "11874266",
   "metadata": {},
   "source": [
    "Solving the matrix equation $Aa=b$ could also be expensive. Using Gaussian elimination to solve the matrix equation for a general matrix $A$ requires $O(n^3)$ operations. This means the number of operations grows like $Cn^3$, where $C$ is a positive constant. (The formal definition of the big O notation is as follows: we write $f(n)=O(g(n))$ as $n\\rightarrow \\infty$ if and only if there exists a positive constant $M$ and a positive integer $n^*$ such that $|f(n)|\\leq M g(n)$ for all $n\\geq n^*$.) However, there are some advantages to the monomial form: evaluating the polynomial is very efficient using Horner's method,\n",
    "which is the nested form discussed in Exercises 1.3-4, 1.3-5 of Chapter 1, requiring $O(n)$ operations. Differentiation and integration are also relatively efficient."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "9e8b693c",
   "metadata": {},
   "source": [
    "## Lagrange form of polynomial interpolation"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "dded8195",
   "metadata": {},
   "source": [
    "The ill-conditioning of the van der Monde matrix, as well as the high complexity of solving the resulting matrix equation in the monomial form of polynomial interpolation, motivate us to explore other basis functions for polynomials. As before, we start with data $(x_{i},y_{i}),i=0,1,...,n$, and call our interpolating polynomial of degree at most $n$, $p_n(x)$. The Lagrange basis functions up to degree $n$ (also called cardinal polynomials) are defined as\n",
    "\n",
    "\\begin{equation*}\n",
    "l_{k}(x)=\\prod_{j=0,j\\neq k}^{n}\\left(\\frac{x-x_{j}}{x_{k}-x_{j}}\\right),k=0,1,...,n.\n",
    "\\end{equation*}\n",
    "We write the interpolating polynomial $p_n(x)$ as a linear combination of these basis functions as\n",
    "\\begin{equation*}\n",
    "p_{n}(x)=a_{0}l_{0}(x)+a_{1}l_{1}(x)+\\cdots+a_{n}l_{n}(x).\n",
    "\\end{equation*}\n",
    "We will determine $a_{i}$ from\n",
    "\\begin{equation*}\n",
    "p_{n}(x_{i})=a_{0}l_{0}(x_{i})+a_{1}l_{1}(x_{i})+\\cdots+a_{n}l_{n}(x_{i})=y_{i}\n",
    "\\end{equation*}\n",
    "for $i=0,1,\\dots,n.$ Or, in matrix form, we want to solve\n",
    "\\begin{equation*}\n",
    "\\underbrace{\\begin{bmatrix}l_{0}(x_{0}) & l_{1}(x_{0}) & \\cdots & l_{n}(x_{0})\\\\\n",
    "l_{0}(x_{1}) & l_{1}(x_{1}) & \\cdots & l_{n}(x_{1})\\\\\n",
    "\\vdots & \\vdots & \\vdots & \\vdots\\\\\n",
    "l_{0}(x_{n}) & l_{1}(x_{n}) & \\cdots & l_{n}(x_{n})\n",
    "\\end{bmatrix}}_A \\underbrace{\\begin{bmatrix}a_{0}\\\\\n",
    "a_{1}\\\\\n",
    "\\vdots\\\\\n",
    "a_{n}\n",
    "\\end{bmatrix}}_a=\\underbrace{\\begin{bmatrix}y_{0}\\\\\n",
    "y_{1}\\\\\n",
    "\\vdots\\\\\n",
    "y_{n}\n",
    "\\end{bmatrix}}_y\n",
    "\\end{equation*}\n",
    "for $[a_{0},\\dots,a_{n}]^{T}.$\n",
    "\n",
    "Solving this matrix equation is trivial for the following reason.\n",
    "Observe that $l_{k}(x_{k})=1$ and $l_{k}(x_{i})=0$ for all $i\\neq k.$\n",
    "Then the coefficient matrix $A$ becomes the identity matrix, and\n",
    "\\begin{equation*}\n",
    "a_{k}=y_{k}\\text{ for }k=0,1,\\dots,n.\n",
    "\\end{equation*}\n",
    "The interpolating polynomial becomes\n",
    "\\begin{equation*}\n",
    "p_{n}(x)=y_{0}l_{0}(x)+y_{1}l_{1}(x)+\\cdots+y_{n}l_{n}(x).\n",
    "\\end{equation*}\n",
    "The main advantage of the Lagrange form of interpolation is that finding the interpolating polynomial is trivial: there is no need to solve a matrix equation. However, the evaluation, differentiation, and integration of the Lagrange form\n",
    "of a polynomial is more expensive than, for example, the monomial form.\n"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "6051e9fb",
   "metadata": {},
   "source": [
    "\\begin{example}\\label{example:chap3_exa48}\n",
    "Find the interpolating polynomial using the monomial basis and Lagrange\n",
    "basis functions for the data: $(-1,-6),(1,0),(2,6)$.\n",
    "\\end{example}"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "6f6eab1a",
   "metadata": {},
   "source": [
    "**Solution.**\n",
    "\n",
    "- Monomial basis: $p_{2}(x)=a_{0}+a_{1}x+a_{2}x^{2}$\n",
    "\\begin{equation*}\n",
    "\\underbrace{\\left[\\begin{array}{ccc}\n",
    "1 & x_{0} & x_{0}^{2}\\\\\n",
    "1 & x_{1} & x_{1}^{2}\\\\\n",
    "1 & x_{2} & x_{2}^{2}\n",
    "\\end{array}\\right]}_A \\underbrace{\\begin{bmatrix}a_{0}\\\\\n",
    "a_{1}\\\\\n",
    "a_{2}\n",
    "\\end{bmatrix}}_a=\\underbrace{\\begin{bmatrix}y_{0}\\\\\n",
    "y_{1}\\\\\n",
    "y_{2}\n",
    "\\end{bmatrix}}_y\\Rightarrow\\left[\\begin{array}{ccc}\n",
    "1 & -1 & 1\\\\\n",
    "1 & 1 & 1\\\\\n",
    "1 & 2 & 4\n",
    "\\end{array}\\right]\\begin{bmatrix}a_{0}\\\\\n",
    "a_{1}\\\\\n",
    "a_{2}\n",
    "\\end{bmatrix}=\\begin{bmatrix}-6\\\\\n",
    "0\\\\\n",
    "6\n",
    "\\end{bmatrix}\n",
    "\\end{equation*}\n",
    "We can use Gaussian elimination to solve this matrix equation, or get help from Python:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "id": "0d4c9ae2",
   "metadata": {},
   "outputs": [],
   "source": [
    "import numpy as np"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "id": "8bb489c2",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "array([[ 1, -1,  1],\n",
       "       [ 1,  1,  1],\n",
       "       [ 1,  2,  4]])"
      ]
     },
     "execution_count": 2,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "A = np.array([[1,-1,1], [1,1,1], [1,2,4]])\n",
    "A"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "id": "4fd97bdf",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "array([-6,  0,  6])"
      ]
     },
     "execution_count": 3,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "y = np.array([-6, 0, 6])\n",
    "y"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "id": "6e1569e7",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "array([-4.,  3.,  1.])"
      ]
     },
     "execution_count": 4,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "np.linalg.solve(A, y)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "c97a889c",
   "metadata": {},
   "source": [
    "Since the solution is $a=[-4,3,1]^{T},$ we obtain\n",
    "\\begin{equation*}\n",
    "p_{2}(x)=-4+3x+x^{2}.\n",
    "\\end{equation*}\n",
    "- Lagrange basis: $p_{2}(x) =y_{0}l_{0}(x)+y_{1}l_{1}(x)+y_{2}l_{2}(x)=-6l_{0}(x)+0l_{1}(x)+6l_{2}(x)$\n",
    "%\\begin{align*}\n",
    "%p_{2}(x) & =a_{0}l_{0}(x)+a_{1}l_{1}(x)+a_{2}l_{2}(x)\\\\\n",
    "% & =-27l_{0}(x)-l_{1}(x)+0l_{2}(x)\n",
    "%\\end{align*}\n",
    "where\n",
    "\\begin{align*}\n",
    "l_{0}(x) & =\\frac{(x-x_{1})(x-x_{2})}{(x_{0}-x_{1})(x_{0}-x_{2})}=\\frac{(x-1)(x-2)}{(-1-1)(-1-2)}=\\frac{(x-1)(x-2)}{6}\\\\\n",
    "l_{2}(x) & =\\frac{(x-x_{0})(x-x_{1})}{(x_{2}-x_{0})(x_{2}-x_{1})}=\\frac{(x+1)(x-1)}{(2+1)(2-1)}=\\frac{(x+1)(x-1)}{3}\n",
    "\\end{align*}\n",
    "therefore\n",
    "\\begin{align*}\n",
    "p_{2}(x) & =-6 \\frac{(x-1)(x-2)}{6} +6 \\frac{(x+1)(x-1)}{3}=-(x-1)(x-2)+2(x+1)(x-1).\n",
    "\\end{align*}\n",
    "If we multiply out and collect the like terms, we obtain $p_2(x)=-4+3x+x^{2}$, which is the polynomial we obtained from the monomial basis earlier."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "693c1485",
   "metadata": {},
   "source": [
    "**Exercise 4.1-1**\n",
    "\n",
    "Prove that $\\sum_{k=0}^{n}l_{k}(x)=1$ for all $x,$ where $l_{k}$\n",
    "are the Lagrange basis functions for $n+1$ data points. (Hint. First\n",
    "verify the identity for $n=1$ algebraically, for any two data points.\n",
    "For the general case, think about what special function's interpolating\n",
    "polynomial in Lagrange form is $\\sum_{k=0}^{n}l_{k}(x)$.)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "f66d06c9",
   "metadata": {},
   "source": [
    "## Newton's form of polynomial interpolation"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "a9aa8a15",
   "metadata": {},
   "source": [
    "The Newton basis functions up to degree $n$ are\n",
    "\\begin{equation*}\n",
    "\\pi_{k}(x)=\\prod_{j=0}^{k-1}(x-x_{j}), k=0,1,\\dots,n\n",
    "\\end{equation*}\n",
    "where $\\pi_{0}(x)=\\prod_{j=0}^{-1}(x-x_{j})$ is interpreted as 1.\n",
    "The interpolating polynomial $p_n$, written as a linear combination of Newton basis functions, is\n",
    "\\begin{align*}\n",
    "p_{n}(x) & =a_{0}\\pi_{0}(x)+a_{1}\\pi_{1}(x)+\\cdots+a_{n}\\pi_{n}(x)\\\\\n",
    " & =a_{0}+a_{1}(x-x_{0})+a_{2}(x-x_{0})(x-x_{1})+\\cdots+a_{n}(x-x_{0})\\cdots(x-x_{n-1}).\n",
    "\\end{align*}\n",
    "We will determine $a_{i}$ from\n",
    "\\begin{equation*}\n",
    "p_{n}(x_{i})=a_{0}+a_{1}(x_{i}-x_{0})+\\cdots+a_{n}(x_i-x_{0})\\cdots(x_i-x_{n-1})=y_{i},\n",
    "\\end{equation*}\n",
    "for $i=0,1,\\dots,n,$ or in matrix form\n",
    "\\begin{equation*}\n",
    "\\underbrace{\\begin{bmatrix}1 & 0 & 0 & \\ldots & 0\\\\\n",
    "1 & (x_{1}-x_{0}) & 0 & \\ldots & 0\\\\\n",
    "1 & (x_{2}-x_{0}) & (x_{2}-x_{0})(x_{2}-x_{1}) & \\ldots  & 0\\\\\n",
    "\\vdots & \\vdots & \\vdots & \\vdots & \\vdots\\\\\n",
    "1 & (x_{n}-x_{0}) & (x_{n}-x_{0})(x_{n}-x_{1}) & \\ldots & \\prod_{i=0}^{n-1}(x_{n}-x_{i})\n",
    "\\end{bmatrix}}_A \\underbrace{\\begin{bmatrix}a_{0}\\\\\n",
    "a_{1}\\\\\n",
    "\\vdots\\\\\n",
    "a_{n}\n",
    "\\end{bmatrix}}_a=\\underbrace{\\begin{bmatrix}y_{0}\\\\\n",
    "y_{1}\\\\\n",
    "\\vdots\\\\\n",
    "y_{n}\n",
    "\\end{bmatrix}}_y.\n",
    "\\end{equation*}\n",
    "Note that the coefficient matrix $A$ is\n",
    "lower-triangular, and $a$ can be solved by forward substitution, which is shown in the next example, in\n",
    "$O(n^2)$ operations."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "38ca6001",
   "metadata": {},
   "source": [
    "\\begin{example}\\label{example:chap3_exa49}\n",
    "Find the interpolating polynomial using Newton's basis for the data:\n",
    "$(-1,-6),(1,0),(2,6)$.\n",
    "\\end{example}\n",
    "\n",
    "**Solution.**\n",
    "\n",
    "We have $p_{2}(x)=a_{0}+a_{1}\\pi_{1}(x)+a_{2}\\pi_{2}(x)=a_{0}+a_{1}(x+1)+a_{2}(x+1)(x-1).$\n",
    "Find $a_{0},a_{1},a_{2}$ from\n",
    "\\begin{align*}\n",
    "p_2(-1)=-6 &\\Rightarrow a_0+a_1(-1+1)+a_2(-1+1)(-1-1)=a_0=-6\\\\\n",
    "p_2(1)=0 &\\Rightarrow a_0+a_1(1+1)+a_2(1+1)(1-1)=a_0+2a_1=0\\\\\n",
    "p_2(2)=6 &\\Rightarrow a_0+a_1(2+1)+a_2(2+1)(2-1)=a_0+3a_1+3a_2=6\n",
    "\\end{align*}\n",
    "or, in matrix form\n",
    "\\begin{equation*}\n",
    "\\begin{bmatrix}1 & 0 & 0\\\\\n",
    "1 & 2 & 0\\\\\n",
    "1 & 3 & 3\n",
    "\\end{bmatrix}\\begin{bmatrix}a_{0}\\\\\n",
    "a_{1}\\\\\n",
    "a_{2}\n",
    "\\end{bmatrix}=\\begin{bmatrix}-6\\\\\n",
    "0\\\\\n",
    "6\n",
    "\\end{bmatrix}.\n",
    "\\end{equation*}\n",
    "Forward substitution is:\n",
    "\\begin{gather*}\n",
    "a_{0}=-6\\\\\n",
    "a_{0}+2a_{1}=0\\Rightarrow-6+2a_{1}=0\\Rightarrow a_{1}=3\\\\\n",
    "a_{0}+3a_{1}+3a_{2}=6\\Rightarrow-6+9+3a_{2}=6\\Rightarrow a_{2}=1.\n",
    "\\end{gather*}\n",
    "Therefore $a=[-6,3,1]^{T}$ and\n",
    "\\begin{equation*}\n",
    "p_{2}(x)=-6+3(x+1)+(x+1)(x-1).\n",
    "\\end{equation*}\n",
    "Multiplying out and simplifying give $p_2(x)=-4+3x+x^2$, which is the polynomial discussed in Example \\ref{example:chap3_exa48}."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "68071e48",
   "metadata": {},
   "source": [
    "\n",
    "**Summary:** The interpolating polynomial $p_2(x)$ for the data, $(-1,-6),(1,0),(2,6)$, represented in three different basis functions is:\n",
    "\\begin{align*}\n",
    "\\text{Monomial: } p_{2}(x) & = -4+3x+x^{2}\\\\\n",
    "\\text{Lagrange: } p_{2}(x)= & -(x-1)(x-2)+2(x+1)(x-1)\\\\\n",
    "\\text{Newton: } p_{2}(x)= & -6+3(x+1)+(x+1)(x-1)\n",
    "\\end{align*}\n",
    "\n",
    "Similar to the monomial form, a polynomial written in Newton's form can be evaluated using the Horner's method which has $O(n)$ complexity:\n",
    "\\begin{align*}\n",
    "p_{n}(x)&=a_{0}+a_{1}(x-x_{0})+a_{2}(x-x_{0})(x-x_{1})+\\cdots+a_{n}(x-x_{0})(x-x_{1})\\cdots(x-x_{n-1})\\\\\n",
    "&=a_{0}+(x-x_{0})(a_{1}+(x-x_{1})(a_{2}+\\cdots+(x-x_{n-2})(a_{n-1}+(x-x_{n-1})(a_{n}))\\cdots))\n",
    "\\end{align*}"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "babc8ade",
   "metadata": {},
   "source": [
    "\\begin{example}\\label{example:chap3_exa50}\n",
    "Write $p_{2}(x)=-6+3(x+1)+(x+1)(x-1)$ using the nested form.\n",
    "\\end{example}"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "053003df",
   "metadata": {},
   "source": [
    "**Solution.**\n",
    "\n",
    "$-6+3(x+1)+(x+1)(x-1)=-6+(x+1)(2+x);$ note that the left-hand side has 2 multiplications,\n",
    "and the right-hand side has 1."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "d3b705ef",
   "metadata": {},
   "source": [
    "**Complexity of the three forms of polynomial interpolation:** The number of operations required in solving the corresponding matrix equation in each polynomial basis is:\n",
    "\n",
    "- Monomial $\\rightarrow O(n^3)$\n",
    "- Lagrange $\\rightarrow$ trivial\n",
    "- Newton $\\rightarrow O(n^2)$\n",
    "\n",
    "Evaluating the polynomials can be done efficiently using Horner's method for monomial and Newton forms. A modified version of Lagrange form can also be evaluated using Horner's method, but we do not discuss it here."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "d6b1df27",
   "metadata": {},
   "source": [
    "**Exercise 4.1-2**\n",
    "\n",
    "Compute, by hand, the interpolating polynomial to the data $(-1,0)$,\n",
    "$(0.5,1)$, $(1,0)$ using the monomial, Lagrange, and Newton basis\n",
    "functions. Verify the three polynomials are identical."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "204ef42b",
   "metadata": {},
   "source": [
    "It's time to discuss some theoretical results for polynomial interpolation. Let's start with proving Theorem \\ref{theo:chap3_thm47} which we stated earlier:"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "48bfdd43",
   "metadata": {},
   "source": [
    "\\begin{theorem}\n",
    "If points $x_{0},x_{1},\\dots,x_{n}$ are distinct, then for real values\n",
    "$y_{0},y_{1},\\dots,y_{n},$ there is a unique polynomial $p_{n}$ of\n",
    "degree at most $n$ such that $p_{n}(x_{i})=y_{i},i=0,1,\\dots,n$.\n",
    "\\end{theorem}"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "dad016c1",
   "metadata": {},
   "source": [
    "\\begin{proof}\n",
    "We have already established the existence of $p_{n}$ without mentioning it! The Lagrange\n",
    "form of the interpolating polynomial constructs $p_{n}$ directly:\n",
    "\\begin{equation*}\n",
    "p_{n}(x)=\\sum_{k=0}^{n}y_{k}l_{k}(x)=\\sum_{k=0}^{n}y_{k}\\prod_{j=0,j\\neq k}^{n}\\frac{x-x_{j}}{x_{k}-x_{j}}.\n",
    "\\end{equation*}\n",
    "Let's prove uniqueness. Assume $p_{n},q_{n}$ are two distinct polynomials\n",
    "satisfying the conclusion. Then $p_{n}-q_{n}$ is a polynomial of\n",
    "degree at most $n$ such that $(p_{n}-q_{n})(x_{i})=0$ for $i=0,1,\\dots,n.$\n",
    "This means the non-zero polynomial $(p_{n}-q_{n})$ of degree at most\n",
    "$n,$ has $(n+1)$ distinct roots, which is a contradiction.\n",
    "\\end{proof}"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "2984b704",
   "metadata": {},
   "source": [
    "The following theorem, which we state without proof, establishes the error of polynomial interpolation. Notice the similarities between this and Taylor's Theorem (Theorem 5 Chapter1-1)."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "85b6dce4",
   "metadata": {},
   "source": [
    "\\begin{theorem}\\label{theo:chap3_thm51}\n",
    "Let $x_{0},x_{1},\\dots,x_{n}$ be distinct\n",
    "numbers in the interval $[a,b]$ and $f\\in C^{n+1}[a,b].$ Then for\n",
    "each $x\\in[a,b],$ there is a number $\\xi$ between $x_{0},x_{1},\\dots,x_{n}$ such that\n",
    "\\begin{equation*}\n",
    "f(x)-p_{n}(x)=\\frac{f^{(n+1)}(\\xi)}{(n+1)!}(x-x_{0})(x-x_{1})\\cdots(x-x_{n}).\n",
    "\\end{equation*}\n",
    "\\end{theorem}"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "e7e84f8f",
   "metadata": {},
   "source": [
    "The following lemma is useful in finding upper bounds for $|f(x)-p_{n}(x)|$\n",
    "using Theorem \\ref{theo:chap3_thm51}, when the nodes $x_0,\\dots,x_n$ are **equally spaced**."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "d9672942",
   "metadata": {},
   "source": [
    "\\begin{lemma}\\label{lem:chap3_lem52}\n",
    "Consider the partition of $[a,b]$ as $x_0=a,x_1=a+h,\\dots,x_n=a+nh=b$. More succinctly, $x_{i}=a+ih$ for $i=0,1,\\dots,n$ and $h=\\frac{b-a}{n}.$ Then for any $x\\in[a,b]$\n",
    "\\begin{equation*}\n",
    "\\prod_{i=0}^{n}|x-x_{i}|\\leq\\frac{1}{4}h^{n+1}n!\n",
    "\\end{equation*}\n",
    "\\end{lemma}\n",
    "\n",
    "\\begin{proof}\n",
    "Since $x\\in[a,b]$, it falls into one of the subintervals: let $x\\in[x_{j},x_{j+1}].$\n",
    "Consider the product $|x-x_{j}||x-x_{j+1}|.$ Put $s=|x-x_{j}|$ and\n",
    "$t=|x-x_{j+1}|.$ The maximum of $st$ given $s+t=h,$ using calculus,\n",
    "can be found to be $h^{2}/4,$ which is attained when $x$ is the\n",
    "midpoint, and thus $s=t=h/2$. Then\n",
    "\\begin{align*}\n",
    "\\prod_{i=0}^{n}|x-x_{i}| & =|x-x_{0}|\\cdots|x-x_{j-1}||x-x_{j}||x-x_{j+1}||x-x_{j+2}|\\cdots|x-x_{n}|\\\\\n",
    " & \\leq|x-x_{0}|\\cdots|x-x_{j-1}|\\frac{h^{2}}{4}|x-x_{j+2}|\\cdots|x-x_{n}|\\\\\n",
    " & \\leq|x_{j+1}-x_{0}|\\cdots|x_{j+1}-x_{j-1}|\\frac{h^{2}}{4}|x_{j}-x_{j+2}|\\cdots|x_{j}-x_{n}|\\\\\n",
    " & =(j+1)h\\cdots2h\\left(\\frac{h^{2}}{4}\\right)(2h)\\cdots(n-j)h\\\\\n",
    " & =h^{j}(j+1)!\\frac{h^{2}}{4}(n-j)!h^{n-j-1}\\\\\n",
    " & \\leq h^{n+1}\\frac{n!}{4}.\n",
    "\\end{align*}\n",
    "\\end{proof}"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "d03e5090",
   "metadata": {},
   "source": [
    "\\begin{example}\\label{example:chap3_exa53}\n",
    "Find an upper bound for the absolute error when $f(x)=\\cos x$ is approximated by its interpolating polynomial $p_n(x)$ on $[0,\\pi/2]$. For the interpolating polynomial, use 5 equally spaced nodes ($n=4$) in $[0,\\pi/2]$, including the endpoints.\n",
    "\\end{example}\n",
    "\n",
    "\n",
    "**Solution.**\n",
    "\n",
    "From Theorem \\ref{theo:chap3_thm51},\n",
    "\\begin{equation*}\n",
    "|f(x)-p_{4}(x)|=\\frac{|f^{(5)}(\\xi)|}{5!}|(x-x_{0})\\cdots(x-x_{4})|.\n",
    "\\end{equation*}\n",
    "We have $|f^{(5)}(\\xi)|\\leq1.$ The nodes are equally spaced with\n",
    "$h=(\\pi/2-0)/4=\\pi/8.$ Then from the previous lemma,\n",
    "\\begin{equation*}\n",
    "|(x-x_{0})\\cdots(x-x_{4})|\\leq\\frac{1}{4}\\left(\\frac{\\pi}{8}\\right)^{5}4!\n",
    "\\end{equation*}\n",
    "and therefore\n",
    "\\begin{equation*}\n",
    "|f(x)-p_{4}(x)|\\leq\\frac{1}{5!}\\frac{1}{4}\\left(\\frac{\\pi}{8}\\right)^{5}4!=4.7\\times10^{-4}.\n",
    "\\end{equation*}"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "afc00b4e",
   "metadata": {},
   "source": [
    "**Exercise 4.1-3**\n",
    "\n",
    "Find an upper bound for the absolute error when $f(x)=\\ln x$ is approximated by an interpolating\n",
    "polynomial of degree five with six nodes equally spaced in the interval\n",
    "$[1,2]$."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "ac02f232",
   "metadata": {},
   "source": [
    "We now revisit Newton's form of interpolation, and learn an alternative method, known as \\textbf{divided differences}, to compute the coefficients of the interpolating polynomial. This approach is  numerically more stable than the forward substitution approach we used earlier. Let's recall the interpolation problem.\n",
    "\n",
    "- Data: $(x_{i},y_{i}),i=0,1,\\dots,n$\n",
    "- Interpolant in Newton's form:\n",
    "\\begin{equation*}\n",
    "p_{n}(x)=a_{0}+a_{1}(x-x_{0})+a_{2}(x-x_{0})(x-x_{1})+\\cdots+a_{n}(x-x_{0})\\cdots(x-x_{n-1})\n",
    "\\end{equation*}\n",
    "Determine $a_{i}$ from $p_{n}(x_{i})=y_{i},i=0,1,\\dots,n$.\n",
    "\n",
    "Let's think of the $y$-coordinates of the data, $y_{i}$, as values of an unknown function $f$ evaluated at $x_i$, i.e., $f(x_{i})=y_{i}.$ Substitute $x=x_{0}$ in the interpolant to get:\n",
    "\\begin{equation*}\n",
    "a_{0}=f(x_{0}).\n",
    "\\end{equation*}\n",
    "Substitute $x=x_{1}$ to get $a_{0}+a_{1}(x_{1}-x_{0})=f(x_{1})$\n",
    "or,\n",
    "\\begin{equation*}\n",
    "a_{1}=\\frac{f(x_{1})-f(x_{0})}{x_{1}-x_{0}}.\n",
    "\\end{equation*}\n",
    "Substitute $x=x_{2}$ to get, after some algebra\n",
    "\\begin{equation*}\n",
    "a_{2}=\\frac{\\frac{f(x_{2})-f(x_{0})}{x_{2}-x_{1}}-\\frac{f(x_{1})-f(x_{0})}{x_{1}-x_{0}}\\frac{x_{2}-x_{0}}{x_{2}-x_{1}}}{x_{2}-x_{0}}\n",
    "\\end{equation*}\n",
    "which can be further rewritten as\n",
    "\\begin{equation*}\n",
    "a_{2}=\\frac{\\frac{f(x_{2})-f(x_{1})}{x_{2}-x_{1}}-\\frac{f(x_{1})-f(x_{0})}{x_{1}-x_{0}}}{x_{2}-x_{0}}.\n",
    "\\end{equation*}\n",
    "Inspecting the formulas for $a_{0},a_{1},a_{2}$ suggests the following\n",
    "simplified new notation called **divided differences**:\n",
    "\\begin{align*}\n",
    "a_{0} & =f(x_{0})=\\color{red}{f[x_{0}]}\\longrightarrow\\text{0th divided difference}\\\\\n",
    "a_{1} & =\\frac{f(x_{1})-f(x_{0})}{x_{1}-x_{0}}=\\color{red}{f[x_{0},x_{1}]}\\longrightarrow\\text{1st divided difference}\\\\\n",
    "a_{2} & =\\frac{\\frac{f(x_{2})-f(x_{1})}{x_{2}-x_{1}}-\\frac{f(x_{1})-f(x_{0})}{x_{1}-x_{0}}}{x_{2}-x_{0}}=\\frac{f[x_{1},x_{2}]-f[x_{0},x_{1}]}{x_{2}-x_{0}} =\\color{red}{f[x_{0},x_{1},x_{2}]}\\longrightarrow\\text{2nd divided difference }\n",
    "\\end{align*}\n",
    "And in general, $a_{k}$ will be given by the $k$th divided difference:\n",
    "\\begin{equation*}\n",
    "a_{k}=\\color{red}{f[x_{0},x_{1},\\dots,x_{k}]}.\n",
    "\\end{equation*}\n",
    "With this new notation, Newton's interpolating polynomial can be written\n",
    "as\n",
    "\\begin{align*}\n",
    "p_{n}(x)&=f[x_{0}]+\\sum_{k=1}^{n}f[x_{0},x_{1},\\dots,x_{k}](x-x_{0})\\cdots(x-x_{k-1})\\\\\n",
    "&=f[x_{0}]+f[x_{0},x_{1}](x-x_{0})+f[x_{0},x_{1},x_{2}](x-x_{0})(x-x_{1})+\\cdots\\\\\n",
    "&+f[x_{0},x_{1},\\dots,x_{n}](x-x_{0})(x-x_{1})\\cdots(x-x_{n-1}).\n",
    "\\end{align*}"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "9295be27",
   "metadata": {},
   "source": [
    "Here is the formal definition of divided differences:\n",
    "\\begin{definition}\\label{def:chap3_def54}\n",
    "Given data $(x_{i},f(x_{i})),i=0,1,\\dots,n,$ the divided differences\n",
    "are defined recursively as\n",
    "\\begin{align*}\n",
    "f[x_{0}] & =f(x_{0})\\\\\n",
    "f[x_{0},x_{1},\\dots,x_{k}] & =\\frac{f[x_{1},\\dots,x_{k}]-f[x_{0},\\dots,x_{k-1}]}{x_{k}-x_{0}}\n",
    "\\end{align*}\n",
    "where $k=1,\\dots,n$.\n",
    "\\end{definition}"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "04fee330",
   "metadata": {},
   "source": [
    "##### \\begin{example}\\label{example:chap3_exa55}\n",
    "Find the interpolating polynomial for the data $(-1,-6),(1,0),(2,6)$\n",
    "using Newton's form and divided differences.\n",
    "\\end{example}\n",
    "\n",
    "**Solution.**\n",
    "\n",
    "We want to compute\n",
    "\\begin{equation*}\n",
    "p_{2}(x)=f[x_{0}]+f[x_{0},x_{1}](x-x_{0})+f[x_{0},x_{1},x_{2}](x-x_{0})(x-x_{1}).\n",
    "\\end{equation*}\n",
    "Here are the divided differences:\n",
    "\n",
    "\n",
    "\\begin{equation*}\n",
    "\\begin{array}{cccc}\n",
    "x & f[x] & \\text{First divided difference} & \\text{Second divided difference}\\\\\n",
    "\\hline\n",
    "x_{0}=-1 & f[x_{0}]=\\color{blue}{-6} &  & \\\\\n",
    " &  & f[x_{0},x_{1}]=\\frac{f[x_{1}]-f[x_{0}]}{x_{1}-x_{0}}=\\color{blue}{3} & \\\\\n",
    "x_{1}=1 & f[x_{1}]=0 &  & f[x_{0},x_{1},x_{2}]=\\frac{f[x_{1},x_{2}]-f[x_{0},x_{1}]}{x_{2}-x_{0}}=\\color{blue}{1}\\\\\n",
    " &  & f[x_{1},x_{2}]=\\frac{f[x_{2}]-f[x_{1}]}{x_{2}-x_{1}}=6 & \\\\\n",
    "x_{2}=2 & f[x_{2}]=6 &  & \\\\\n",
    "\\hline\n",
    "\\end{array}\n",
    "\\end{equation*}\n",
    "\n",
    "Therefore\n",
    "\\begin{equation*}\n",
    "p_{2}(x)=\\color{blue}{-6}+\\color{blue}{3}(x+1)+\\color{blue}{1}(x+1)(x-1),\n",
    "\\end{equation*}\n",
    "which is the same polynomial we had in Example \\ref{example:chap3_exa49}."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "9168f00e",
   "metadata": {},
   "source": [
    "\\begin{theorem}\\label{theo:chap3_thm55}\n",
    "The ordering of the data in constructing divided differences is not\n",
    "important, that is, the divided difference $f[x_{0},\\dots,x_{k}]$ is invariant\n",
    "under all permutations of the arguments $x_{0},\\dots,x_{k}$.\n",
    "\\end{theorem}"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "2679eb6a",
   "metadata": {},
   "source": [
    "\\begin{proof}\n",
    "Consider the data $(x_{0},y_{0}),(x_{1},y_{1}),\\dots,(x_{k},y_{k})$\n",
    "and let $p_{k}(x)$ be its interpolating polynomial:\n",
    "\\begin{align*}\n",
    "p_{k}(x) & =f[x_{0}]+f[x_{0},x_{1}](x-x_{0})+f[x_{0},x_{1},x_{2}](x-x_{0})(x-x_{1})+\\cdots\\\\\n",
    " & +f[x_{0},\\dots,x_{k}](x-x_{0})\\cdots(x-x_{k-1}).\n",
    "\\end{align*}\n",
    "Now let's consider a permutation of the $x_{i};$ let's label them\n",
    "as $\\tilde{x}_{0},\\tilde{x}_{1},\\dots,\\tilde{x}_{k}.$ The interpolating\n",
    "polynomial for the permuted data does not change, since the data $x_{0},x_{1},\\dots,x_{k}$\n",
    "(omitting the $y$-coordinates) is the same as $\\tilde{x}_{0},\\tilde{x}_{1},\\dots,\\tilde{x}_{k}$,\n",
    "just in different order. Therefore\n",
    "\\begin{align*}\n",
    "p_{k}(x) & =f[\\tilde{x}_{0}]+f[\\tilde{x}_{0},\\tilde{x}_{1}](x-\\tilde{x}_{0})+f[\\tilde{x}_{0},\\tilde{x}_{1},\\tilde{x}_{2}](x-\\tilde{x}_{0})(x-\\tilde{x}_{1})+\\cdots \\\\\n",
    "&+f[\\tilde{x}_{0},\\dots,\\tilde{x}_{k}](x-\\tilde{x}_{0})\\cdots(x-\\tilde{x}_{k-1}).\n",
    "\\end{align*}\n",
    "The coefficient of the polynomial $p_{k}(x)$ for the highest degree\n",
    "$x^{k}$ is $f[x_{0},\\dots,x_{k}]$ in the first equation, and $f[\\tilde{x}_{0},\\dots,\\tilde{x}_{k}]$\n",
    "in the second. Therefore they must be equal to each other.\n",
    "\\end{proof}"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "1c91ed7a",
   "metadata": {},
   "source": [
    "**Exercise 4.1-4**\n",
    "\n",
    "Find the interpolating polynomial $p_2(x)$ for the data $(1,0),(-1,-6),(2,6)$\n",
    "using Newton's form and divided differences.\n",
    "\n",
    "a. Is the polynomial the same as the interpolating polynomial found in Example \\ref{example:chap3_exa55}? Is this expected?\n",
    "\n",
    "b. Are the second divided differences of the interpolating polynomial of Example \\ref{example:chap3_exa55} and $p_2(x)$ the same? Is this expected?"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "7d4c3a73",
   "metadata": {},
   "source": [
    "**Exercise 4.1-5**\n",
    "\n",
    "Consider the function $f$ given in the following table.\n",
    "\\begin{equation*}\n",
    "\\begin{array}{ccccc}\n",
    "x & 1 & 2 & 4 & 6\\\\\n",
    "\\hline\n",
    "f(x) & 2 & 3 & 5 & 9\\\\\n",
    "\\end{array}\n",
    "\\end{equation*}\n",
    "\n",
    "a) Construct a divided difference table for $f$ by hand, and write the\n",
    "Newton form of the interpolating polynomial using the divided differences.\n",
    "\n",
    "b) Assume you are given a new data point for the function: $x=3,y=4.$\n",
    "Find the new interpolating polynomial. (Hint: Think about how to update\n",
    "the interpolating polynomial you found in part (a).)\n",
    "\n",
    "c) If you were working with the Lagrange form of the interpolating polynomial\n",
    "instead of the Newton form, and you were given an additional data\n",
    "point like in part (b), how easy would it be (compared to what you\n",
    "did in part (b)) to update your interpolating polynomial?"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "bceae884",
   "metadata": {},
   "source": [
    "\\begin{example}\\label{example:chap3_exa57}\n",
    "Before the widespread availability of computers and mathematical software, the values of some often-used mathematical functions were disseminated to researchers and engineers via tables. The following table, taken from [Abramowitz and Stegun, 1991], displays some values of the gamma function, $\\Gamma(x)=\\int_0^\\infty t^{x-1} e^{-t}dt$.\n",
    "\n",
    "\\begin{equation*}\n",
    "\\begin{array}{ccccc}\n",
    "x & 1.750 & 1.755 & 1.760 & 1.765\\\\\n",
    "\\hline\n",
    "\\Gamma (x) & 0.91906 & 0.92021 & 0.92137 & 0.92256\\\\\n",
    "\\end{array}\n",
    "\\end{equation*}\n",
    "Use polynomial interpolation to estimate $\\Gamma(1.761)$.\n",
    "\\end{example}\n",
    "\n",
    "**Solution.**\n",
    "\n",
    "The divided differences, with five-digit rounding, are:\n",
    "\n",
    "\\begin{equation*}\n",
    "\\begin{array}{cccccc}\n",
    "i & x_{i} & f[x_{i}] & f[x_{i},x_{i+1}] & f[x_{i-1},x_{i},x_{i+1}] & f[x_{0},x_{1},x_{2},x_{3}]\\\\\n",
    "\\hline\n",
    "0 & 1.750 & \\color{blue}{0.91906} &  &  & \\\\\n",
    " &  &  & \\color{blue}{0.23} &  & \\\\\n",
    "1 & 1.755 & 0.92021 &  & \\color{blue}{0.2} & \\\\\n",
    " &  &  & 0.232 &  & \\color{blue}{26.667}\\\\\n",
    "2 & 1.760 & 0.92137 &  & 0.6 & \\\\\n",
    " &  &  & 0.238&  & \\\\\n",
    "3 & 1.765 & 0.92256 &  &  & \\\\\n",
    "\\hline\n",
    "\\end{array}\n",
    "\\end{equation*}\n",
    "\n",
    "Here are various estimates for $\\Gamma(1.761)$ using interpolating polynomials\n",
    "of increasing degrees:\n",
    "\\begin{align*}\n",
    "p_{1}(x)  &=\\color{blue}{f[x_{0}]}+\\color{blue}{f[x_{0},x_{1}]}(x-x_{0})\\Rightarrow p_{1}(1.761)=\\color{blue}{0.91906+0.23}(1.761-1.750)=0.92159\\\\\n",
    "p_{2}(x)  &=f[x_{0}]+f[x_{0},x_{1}](x-x_{0})+\\color{blue}{f[x_{0},x_{1},x_{2}]}(x-x_{0})(x-x_{1})\\\\\n",
    "&\\Rightarrow  p_{2}(1.761)=0.92159+\\color{blue}{(0.2)}(1.761-1.750)(1.761-1.755)=0.92160\\\\\n",
    "p_{3}(x) & =p_{2}(x)+\\color{blue}{f[x_{0},x_{1},x_{2},x_{3}]}(x-x_{0})(x-x_{1})(x-x_{2})\\\\\n",
    "&\\Rightarrow p_{3}(1.761)=0.9216+\\color{blue}{26.667}(1.761-1.750)(1.761-1.755)(1.761-1.760)=0.92160.\n",
    "\\end{align*}\n",
    "\n",
    "Next we will change the ordering of the data and repeat the calculations. We will list the data in decreasing order of the $x$-coordinates:\n",
    "\\begin{equation*}\n",
    "\\begin{array}{cccccc}\n",
    "i & x_{i} & f[x_{i}] & f[x_{i},x_{i+1}] & f[x_{i-1},x_{i},x_{i+1}] & f[x_{0},x_{1},x_{2},x_{3}]\\\\\n",
    "\\hline\n",
    "0 & 1.765 & \\color{blue}{0.92256} &  &  & \\\\\n",
    " &  &  & \\color{blue}{0.238} &  & \\\\\n",
    "1 & 1.760 & 0.92137 &  & \\color{blue}{0.6} & \\\\\n",
    " &  &  & 0.232 &  & \\color{blue}{26.667}\\\\\n",
    "2 & 1.755 & 0.92021 &  & 0.2 & \\\\\n",
    " &  &  & 0.23 &  & \\\\\n",
    "3 & 1.750 & 0.91906 &  &  & \\\\\n",
    "\\hline\n",
    "\\end{array}\n",
    "\\end{equation*}\n",
    "\n",
    "The polynomial evaluations are:\n",
    "\\begin{align*}\n",
    "p_{1}(1.761) & =\\color{blue}{0.92256}+\\color{blue}{0.238}(1.761-1.765)=0.92161\\\\\n",
    "p_{2}(1.761) & =0.92161+\\color{blue}{0.6}(1.761-1.765)(1.761-1.760)=0.92161\\\\\n",
    "p_{3}(1.761) & =0.92161+\\color{blue}{26.667}(1.761-1.765)(1.761-1.760)(1.761-1.755)=0.92161.\n",
    "\\end{align*}"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "dc60c3eb",
   "metadata": {},
   "source": [
    "**Summary of results:**\n",
    "\n",
    "The following table displays the results for each ordering of the data, together with the correct $\\Gamma(1.761)$ to 7 digits of accuracy.\n",
    "\n",
    "\\begin{equation*}\n",
    "\\begin{array}{ccc}\n",
    "\\hline\n",
    "\\text{Ordering} & (1.75,1.755,1.76,1.765) & (1.765,1.76,1.755,1.75) \\\\\n",
    "\\hline\n",
    "p_{1}(1.761) & 0.92159 & 0.92161\\\\\n",
    "p_{2}(1.761) & 0.92160 & 0.92161\\\\\n",
    "p_{3}(1.761) & 0.92160 & 0.92161\\\\\n",
    "\\hline\n",
    "\\Gamma(1.761) & \\color{red}{0.9216103} & \\color{red}{0.9216103}\\\\\n",
    "\\hline\n",
    "\\end{array}\n",
    "\\end{equation*}"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "2f8bee15",
   "metadata": {},
   "source": [
    "**Exercise 4.1-6**\n",
    "\n",
    "Answer the following questions:\n",
    "\n",
    "a) Theorem \\ref{theo:chap3_thm55} stated that the ordering of the data in divided differences\n",
    "does not matter. But we see differences in the two tables above. Is\n",
    "this a contradiction?\n",
    "\n",
    "b) $p_{1}(1.761)$ is a better approximation to $\\Gamma(1.761)$ in the second ordering. Is this expected?\n",
    "\n",
    "c) $p_{3}(1.761)$ is different in the two orderings; however, this difference is due to rounding error. In other words, if the calculations can be done exactly, $p_{3}(1.761)$ will be the same in each ordering of the data. Why?"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "6fdbf841",
   "metadata": {},
   "source": [
    "**Exercise 4.1-7**\n",
    "\n",
    "Consider a function $f(x)$ such that $f(2)=1.5713$, $f(3)=1.5719,f(5)=1.5738,$\n",
    "and $f(6)=1.5751.$ Estimate $f(4)$ using a second degree interpolating\n",
    "polynomial (interpolating the first three data points) and a third degree interpolating polynomial (interpolating the first four data points). Round the\n",
    "final results to four decimal places. Is there any advantage here\n",
    "in using a third degree interpolating polynomial?"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "b6b8e582",
   "metadata": {},
   "source": [
    "## Python code for Newton interpolation"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "d1b21a8a",
   "metadata": {},
   "source": [
    "Consider the following divided difference table.\n",
    "\n",
    "\\begin{equation}\\label{eq:table3.1}\n",
    "\\begin{array}{cccc}\n",
    "x & f(x) & f[x_{i},x_{i+1}] & f[x_{i-1},x_{i},x_{i+1}]\\\\\n",
    "\\hline\n",
    "x_{0} & \\color{red}{y_{0}} &  & \\\\\n",
    " &  & \\color{red}{\\frac{y_{1}-y_{0}}{x_{1}-x_{0}}=f[x_{0},x_{1}]} & \\\\\n",
    "x_{1} & y_{1} &  & \\color{red}{\\frac{f[x_{1},x_{2}]-f[x_{0},x_{1}]}{x_{2}-x_{0}}=f[x_0,x_1,x_2]}\\\\\n",
    " &  & \\frac{y_{2}-y_{1}}{x_{2}-x_{1}}=f[x_{1},x_{2}] & \\\\\n",
    "x_{2} & y_{2} &  & \\\\\n",
    "\\hline\n",
    "\\end{array}\n",
    "\\end{equation}"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "47792cd3",
   "metadata": {},
   "source": [
    "There are $2+1=3$ divided differences in the table, not counting the 0th divided differences. In general, the number of divided differences to compute is $1+\\cdots+n=n(n+1)/2$. However, to construct Newton's form of the interpolating polynomial, we need only $n$ divided differences and the 0th divided difference $y_0$. These numbers are displayed in red in Table \\ref{eq:table3.1}. The important observation is, even though all the divided differences have to be computed in order to get the ones needed for Newton's form, they do not have to be all stored. The following Python code is based on an efficient algorithm that goes through the divided difference calculations recursively, and stores an array of size $m=n+1$ at any given time. In the final iteration, this array has the divided differences needed for Newton's form.\n",
    "\n",
    "Let's explain the idea of the algorithm using the simple example of Table \\ref{eq:table3.1}. The code creates an array $a=(a_0,a_1,a_2)$ of size $m=n+1$, which is three in our example, and sets\n",
    "\\begin{equation*}\n",
    "a_0=\\color{red}{y_0},a_1=y_1,a_2=y_2.\n",
    "\\end{equation*}\n",
    "\n",
    "In the first iteration (for loop, $j=1$), $a_1$ and $a_2$ are updated:\n",
    "\\begin{equation*}\n",
    "a_1:=\\frac{a_1-a_0}{x_1-x_0}=\\frac{y_1-y_0}{x_1-x_0}=\\color{red}{f[x_0,x_1]},a_2:=\\frac{a_2-a_1}{x_2-x_1}=\\frac{y_2-y_1}{x_2-x_1}.\n",
    "\\end{equation*}\n",
    "In the last iteration (for loop, $j=2$), only $a_2$ is updated:\n",
    "\\begin{equation*}\n",
    "a_2:=\\frac{a_2-a_1}{x_2-x_0}=\\frac{ \\frac{y_2-y_1}{x_2-x_1}-\\frac{y_1-y_0}{x_1-x_0} }{x_2-x_0}=\\color{red}{f[x_0,x_1,x_2]}.\n",
    "\\end{equation*}\n",
    "The final array $a$ is\n",
    "\\begin{equation*}\n",
    "a=(\\color{red}{y_0,f[x_0,x_1],f[x_0,x_1,x_2]})\n",
    "\\end{equation*}\n",
    "containing the divided differences needed to construct the Newton's form of the polynomial."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "e4ea8ab6",
   "metadata": {},
   "source": [
    "Here is the Python function **diff** that computes the divided differences. The code uses a function we have not used before: **np.flip(np.arange(j,m))**. An example illustrates what it does the best:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "id": "1e4e5163",
   "metadata": {},
   "outputs": [],
   "source": [
    "import numpy as np"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "id": "4091bf4a",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "array([5, 4, 3, 2])"
      ]
     },
     "execution_count": 7,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "np.flip(np.arange(2,6))"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "8cffb298",
   "metadata": {},
   "source": [
    " In the code **diff** the inputs are the $x$- and $y$-coordinates of the data. The numbering of the indices starts at 0."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "id": "ce79fac0",
   "metadata": {},
   "outputs": [],
   "source": [
    "def diff(x, y):\n",
    "    m = x.size # here m is the number of data points.\n",
    "    # the degree of the polynomial is m-1\n",
    "    a = np.zeros(m)\n",
    "    for i in range(m):\n",
    "        a[i] = y[i]\n",
    "    for j in range(1, m):\n",
    "        for i in np.flip(np.arange(j,m)):\n",
    "            a[i] = (a[i]-a[i-1]) / (x[i]-x[i-(j)])\n",
    "    return a"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "f4bee86b",
   "metadata": {},
   "source": [
    "Let's compute the divided differences of Example \\ref{example:chap3_exa55}:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "id": "8e490326",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "array([-6.,  3.,  1.])"
      ]
     },
     "execution_count": 9,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "diff(np.array([-1,1,2]), np.array([-6,0,6]))"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "53f22d2e",
   "metadata": {},
   "source": [
    "These are the divided differences in the second ordering of the data in Example \\ref{example:chap3_exa57}:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "id": "6cd02b2e",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "array([ 0.92256   ,  0.238     ,  0.6       , 26.66666667])"
      ]
     },
     "execution_count": 10,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "diff(np.array([1.765,1.760,1.755,1.750]),\n",
    "     np.array([0.92256,0.92137,0.92021,0.91906]))"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "5d5b3da6",
   "metadata": {},
   "source": [
    " Now let's write a code for the Newton form of polynomial interpolation. The\n",
    "inputs to the function **newton** are the $x$- and $y$-coordinates of the data, and where we want to evaluate the polynomial: $z$. The code uses the divided differences function **diff** discussed earlier to compute:\n",
    "\\begin{equation*}\n",
    "f[x_{0}]+f[x_{0},x_{1}](z-x_{0})+\\cdots\n",
    "+f[x_{0},x_{1},\\dots,x_{n}](z-x_{0})(z-x_{1})\\cdots(z-x_{n-1})\n",
    "\\end{equation*}"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "id": "564c925c",
   "metadata": {},
   "outputs": [],
   "source": [
    "def newton(x, y, z):\n",
    "    m = x.size # here m is the number of data points, not the degree\n",
    "    # of the polynomial\n",
    "    a = diff(x, y)\n",
    "    sum = a[0]\n",
    "    pr = 1.0\n",
    "    for j in range(m-1):\n",
    "        pr *= (z-x[j])\n",
    "        sum += a[j+1]*pr\n",
    "    return sum"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "5a9c95b3",
   "metadata": {},
   "source": [
    " Let's verify the code by computing $p_3(1.761)$ of Example \\ref{example:chap3_exa57}:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "id": "ff1267ce",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "0.92160496"
      ]
     },
     "execution_count": 12,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "newton(np.array([1.765,1.760,1.755,1.750]),\n",
    "       np.array([0.92256,0.92137,0.92021,0.91906]), 1.761)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "cf1f61e9",
   "metadata": {},
   "source": [
    "**Exercise 4.1-8**\n",
    "\n",
    "This problem discusses inverse interpolation\n",
    "which gives another method to find the root of a function. Let $f$ be a continuous function on $[a,b]$ with one root $p$ in the interval. Also assume $f$ has an inverse. Let $x_{0},x_{1},\\dots,x_{n}$ be $n+1$ distinct numbers\n",
    "in $[a,b]$ with $f(x_{i})=y_{i},i=0,1,\\dots,n.$ Construct an interpolating\n",
    "polynomial $P_{n}$ for $f^{-1}(x),$ by taking your data points as\n",
    "$(y_{i},x_{i}),i=0,1,\\dots,n.$ Observe that $f^{-1}(0)=p,$ the root\n",
    "we are trying to find. Then, approximate the root $p$, by evaluating\n",
    "the interpolating polynomial for $f^{-1}$ at 0, i.e., $P_{n}(0)\\approx p.$\n",
    "Using this method, and the following data, find an approximation to the solution of $\\log x=0.$\n",
    "\\begin{equation*}\n",
    "\\begin{array}{ccccc}\n",
    "x & 0.4 & 0.8 & 1.2 & 1.6\\\\\n",
    "\\hline\n",
    "\\log x & -0.92 & -0.22 & 0.18 & 0.47\\\\\n",
    "\\end{array}\n",
    "\\end{equation*}"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "67d1916a",
   "metadata": {},
   "source": [
    "**References**"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "f7c74840",
   "metadata": {},
   "source": [
    "M. Abramowitz and I.A. Stegun. Handbook of mathematical functions: with formulas, graphs, and mathematical tables. Volume 55. Courier Corporation, 1991."
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3 (ipykernel)",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.10.11"
  },
  "latex_envs": {
   "LaTeX_envs_menu_present": true,
   "autoclose": false,
   "autocomplete": true,
   "bibliofile": "biblio.bib",
   "cite_by": "apalike",
   "current_citInitial": 1,
   "eqLabelWithNumbers": true,
   "eqNumInitial": 1,
   "hotkeys": {
    "equation": "Ctrl-E",
    "itemize": "Ctrl-I"
   },
   "labels_anchors": false,
   "latex_user_defs": false,
   "report_style_numbering": false,
   "user_envs_cfg": false
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}