{ "cells": [ { "cell_type": "markdown", "metadata": {}, "source": [ "

Numerical Analysis


Exercise Session 2: Polynomial interpolation

\n" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "The general interpolation problem can be summarized as follows. We consider a set of pairs $(x_i, y_i)$, $i=0, \\ldots, n$ as a well as a basis for the polynomial space, $\\phi_0(x), \\phi_1(x), \\ldots, \\phi_n(x)$. The result of the interpolation can then be written as a linear combination of the basis vectors\n", "\\begin{align*}\n", "f(x) = \\sum_{k=0}^n a_k\\phi(x)\n", "\\end{align*}\n", "\n", "We want the interpolation to pass through the pairs $(x_i, y_i)$ so that $f(x_i) = y_i$. In other words, we want to determine $a_k$ such that \n", "\\begin{align*}\n", "f(x_i) = \\sum_{k=0}^n a_k \\phi_k(x_i) = y_i, \\quad i=0, 1, \\ldots, n\n", "\\end{align*}\n", "which is a system of $n+1$ equations with $n+1$ unknowns. Using matrices, the problem can be written as \n", "\\begin{align*}\n", "\\mathbf{A} = \\left[\\begin{array}{ccc}\n", "\\phi_0(x_0)& \\ldots & \\phi_n(x_0)\\\\\n", "\\phi_0(x_1)& \\ldots & \\phi_n(x_1)\\\\\n", "\\vdots & & \\\\\n", "\\phi_0(x_n)& \\ldots & \\phi_n(x_n)\n", "\\end{array}\\right] \\left[\\begin{array}{c}\n", "a_0\\\\\n", "a_1\\\\\n", "\\vdots \\\\\n", "a_n\n", "\\end{array}\\right] = \\left[\\begin{array}{c}\n", "y_0\\\\\n", "y_1\\\\\n", "\\vdots\\\\\n", "y_n\n", "\\end{array}\\right]\n", "\\end{align*}\n", "\n", "There exist several choices for the basis, including \n", " \n", " - The monomial basis $\\displaystyle \\phi_k(x) = x^k$ \n", " - The Lagrange basis $\\displaystyle \\phi_k(x) = \\prod_{\\substack{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} \\left(x - x_j\\right)$\n", "\n", "where $k=0, \\ldots, n$\n", "\n", "In the case of the monomial basis, the matrix of the basis (which is known as the Vandermonde matrix) is given by\n", "\n", "\\begin{align*}\n", "\\left[\\begin{array}{ccccc}\n", "1& x_0 & x_0^2 & \\ldots & x_0^n\\\\\n", "1& x_1 & x_1^2 & \\ldots & x_1^n\\\\\n", "\\vdots & & & & \\\\\n", "1& x_n & x_n^2 & & x_n^n\n", "\\end{array}\\right]\n", "\\end{align*}\n", "\n", "In the case of the Lagrange basis, the matrix $\\mathbf{A}$ turns into\n", "\\begin{align*}\n", "\\left[\\begin{array}{cccc}\n", "\\ell_0(x_0)& \\ell_1(x_0)& \\ldots & \\ell_n(x_0)\\\\\n", "\\ell_0(x_1)& \\ell_1(x_1)& & \\ell_n(x_1)\\\\\n", "\\vdots & & & \\\\\n", "\\ell_0(x_n)& \\ell_1(x_n)& & \\ell_n(x_n)\n", "\\end{array}\\right]\n", "\\end{align*}\n", "\n", "which, from the definition of the Lagrange polynomials, $\\ell_k(x_k)=1$ and $\\ell_n(x_i) = 0$ for all $i\\neq k$ reduces to \n", "\\begin{align*}\n", "\\left[\\begin{array}{cccc}\n", "1& 0 &\\ldots & 0\\\\\n", "0 & 1 & & \\\\\n", "\\vdots & & \\ddots & \\\\\n", "0 & & & 1\n", "\\end{array}\\right]\n", "\\end{align*}\n", "\n", "and the corresponding system reduces to $a_k = y_k$ for all $k$." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "#### Exercise 1\n", "Find the interpolating polynomial using the monomial basis (use the Gaussian elimination implementation '\\\\' of Julia) and for the Lagrange basis (manually) for the data $(-1,-6),(1,0),(2,6)$" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [] }, { "cell_type": "markdown", "metadata": {}, "source": [ "#### Exercise 2. \n", "\n", "Prove that $\\sum_{k=0}^n \\ell_k(x) = 1$ for all $x$ where $\\ell_k$ are the Lagrange polynomials for $n+1$ points. (Hint verify the identity for $n=1$ for any data points). For the general case, think about what special function's interpolation polynomial in Lagrange form is $\\sum_{k=0}^n \\ell_k(x)$" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [] }, { "cell_type": "markdown", "metadata": {}, "source": [ "#### Exercise 3\n", "\n", "Construct the Lagrange interpolation polynomial $p_1$ of degree $1$ for a continuous function $f$ defined on the interval $[-1,1]$, using the interpolation points $x_0 = -1$, $x_1 = 1$. Show that if the second derivative of $f$ exists and is continuous on $[0,1]$, then \n", "\\begin{align*}\n", "\\left|f(x) - p_1(x)\\right|\\leq \\frac{M_2}{2}(1-x^2)\\leq \\frac{M_2}{2}, \\quad x\\in [-1,1]\n", "\\end{align*}\n", "where $M_2 = \\max_{x\\in [-1,1]} |f''(x)|$\n" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [] }, { "cell_type": "markdown", "metadata": {}, "source": [ "#### Exercise 4\n", "\n", "__a)__ Write down the Lagrange interpolation polynomial of degree $1$ for the function $f\\;:\\; x\\mapsto x^3$, using the points $x_0 = 0$, $x_1 = a$\n", "Verify the bound below and prove that in this case, the $\\xi$ is unique and satisfies $\\xi = \\frac{1}{3}(x+a)$\n", "\n", "\\begin{align*}\n", "f(x) - p_n(x) = \\frac{f^{(n+1)}(\\xi)}{(n+1)!} \\pi_{n+1}(x) \n", "\\end{align*}" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [] }, { "cell_type": "markdown", "metadata": {}, "source": [ "#### Exercise 5\n", "\n", "Write down the Lagrange interpolation polynomial of degree $n$ for the given functions and nodes. Using Pyplot, plot the function, nodes and corresponding polynomial\n", "\n", " - $f(x) = \\sin(x)$, $n=2, x_0 = 0, x_1 = \\pi/2$\n", " - $f(x) = \\sin(x)$, $n=2$, $x_0=0, x_1 = \\pi/6, x_2 = \\pi/2$,\n", " - $f(x) = \\cos(x)$, $n=2$, $x_0 = 0, x_1 = \\pi/3, x_2 = \\pi/2$\n", " - $f(x) = \\tanh(x)$, $n=2$, $x_0 = 0, x_1 = \\pi/3, x_2 = \\pi/2$\n" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [] }, { "cell_type": "markdown", "metadata": {}, "source": [ "#### Exercise 6\n", "\n", "For each case below, plot the Lagrange polynomial on the interval $[x_0,x_n]$, over the interpolation points\n", "\n", " - $n=2$, $x_0 = -1, x_1 = -0.2, x_2 = 0$, $\\ell_2(x)$\n", " - $n=4$, $x_0 = 0, x_1 = 1, x_2 = 1.5, x_3 = 2.5, x_4 = 3$, $\\ell_3(x)$\n", " - $n = 20$, $x_i=i/n$ for $i=0,\\ldots n$, $\\ell_{10}(x)$" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [] }, { "cell_type": "markdown", "metadata": {}, "source": [ "#### Exercise 7\n", "\n", "For each function below, generate equispaced points on the $[0,1]$ interval. Then build the Lagrange interpolation polynomials of degree $2$, $3$ and $4$\n", "\n", " - $\\sin(10x) + \\cos(9x) - x^2 +2$ \n", " - $\\log(5x +1 + \\sin(10*x)) + x^3+2x^2 +1 + \\cos(9x)$" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [] }, { "cell_type": "markdown", "metadata": {}, "source": [ "#### Exercise 8\n", "\n", "We consider the function $f(x) = \\frac{1}{1+16x^2}$. Generate 15 equispaced points on the [-1,1] interval and plot the resulting Lagrange interpolation polynomial on top of the function and the sample. What do you notice ? How can we explain this phenomenon?" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [] }, { "cell_type": "markdown", "metadata": {}, "source": [ "#### Exercise 9\n", "\n", "The Newton basis for polynomials up to degree $n$ is given by \n", "\\begin{align*}\n", "\\pi_k(x) = \\prod_{j=0}^{k-1} (x-x_j), \\quad k=0,1,\\ldots, n\n", "\\end{align*}\n", "the polynomial $\\pi_0(x) = \\prod_{j=0}^{-1} (x-x_j)$ is interpreted as the constant polynomial $1$. \n", "\n", "From this, one can decompose a polynomial of degree $n$ as \n", "\n", "\\begin{align*}\n", "p_n(x) &= a_0\\pi_0(x) + a_1\\pi_1(x) + \\ldots +a_n\\pi_n(x)\\\\\n", "& = a_0 + a_1(x-x_0) + a_2(x-x_0)(x-x_1) + \\ldots + a_n(x-x_0)\\ldots (x-x_{n-1})\n", "\\end{align*}\n", "\n", "The coefficients of this decomposition can then be obtained as\n", "\n", "\\begin{align*}\n", "p_n(x_i) = a_0 + a_1(x_i - x_0) + \\ldots + a_n(x_i - x_0)\\ldots (x_i - x_{n-1}) = y_i\n", "\\end{align*}\n", "\n", "Or similarly\n", "\n", "\n", "\\begin{align*}\n", "\\left[\\begin{array}{ccccc}\n", "1& 0 & 0 & \\ldots & 0\\\\\n", "1& (x_1 - x_0)& 0 & & 0\\\\\n", "1& (x_1 - x_0) & (x_2 - x_0) (x_2 - x_1)& & 0\\\\\n", "\\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{array}\\right]\\left[\\begin{array}{c}\n", "a_0\\\\\n", "a_1\\\\\n", "\\vdots \\\\\n", "a_n\n", "\\end{array}\\right] = \\left[\\begin{array}{c}\n", "y_0\\\\\n", "y_1\\\\\n", "\\vdots \\\\\n", "y_n\n", "\\end{array}\\right]\n", "\\end{align*}\n" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "#### Exercise 9a\n", "\n", "Find the interpolating polynomial using the Newton basis for the data $(-1,-6), (1,0)$ and $(2,6)$. Plot this polynomial on top of the samples." ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [] }, { "cell_type": "markdown", "metadata": {}, "source": [ "#### Exercise 9b\n", "\n", "Compute by hand, the interpolating polynomial to the data $(-1,0), (0.5,1), (1, 0)$ using the monomial, Lagrange and Newton basis functions. verify that the three polynomials are identical.\n" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [] }, { "cell_type": "markdown", "metadata": {}, "source": [ "#### Exercise 10\n", "\n", "" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "__Exercise 10a__\n", "\n", "We want to predict the risk of wild fish use as food for fish farming. \n", "\n", "\n", "\n", "The tables below encode the evolution of Wild fish used as fishmeal and oil and the Aquaculture (fish farm) production. As a first approximation, use the data and learn interpolating polynomials to predict the evolution of those two quantities until 2030\n", "\n", "\\begin{align*}\n", "\\begin{array}{|l|lllll|}\\hline\n", " &1975&1985&1995&2005&2015\\\\ \\hline\n", " \\text{Wild fish used as animal feed} &13.68&21.91&24.88&24.34&14.60 \\\\\n", " \\text{Aquaculture production} &5.22&11.35&31.23&57.82&106\\\\\n", " \\hline\n", " \\end{array}\n", " \\end{align*}" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [] }, { "cell_type": "markdown", "metadata": {}, "source": [ "__Exercise 10b__\n", "\n", "In 2006, a first study by Worm et al. predicted that by the year 2048, the ocean will be devoid of fish (as shown in the Fig below)\n", "\n", "\n", "\n", "In a subsequent study, following some uproar from the community, rather than relying on reported data on fish catch, the same authors built a database on global fish stocks (i.e not the amount of fish being caught, but the abundance of fish in each population). Such a database can be done through a combination of sonar acoustic methods (which lets scientist build a picture of the number and density of fish) and fishing (which lets them identify specific species in the ecosystem).\n", "\n", "The difference can be illstrated through the population of Tuna in the Atlantic ocean (see table below). Using this table, learn a polynomial model and predict the evolution of Tunas in the Atlantic ocean by 2048. \n", "\n", "\n", "The data below corresponds to the biomass of a fish stock divided by the biomass at its maximum sustainable\n", "yield (The level at which we can catch the maximum amount of fish without a decline in fish\n", "populations. A value of one maximises fish catch without decreasing fish populations)\n", "\n", "\\begin{align*}\n", "\\begin{array}{|l|lllll|}\\hline\n", " &1975&1985&1995&2005&2015\\\\ \\hline\n", " \\text{Wild Atlantic Tuna} &1.61&1.34&1.04&0.80& 1.14 \\\\\n", " \\hline\n", " \\end{array}\n", " \\end{align*}" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [] } ], "metadata": { "kernelspec": { "display_name": "Julia 1.6.3", "language": "julia", "name": "julia-1.6" }, "language_info": { "file_extension": ".jl", "mimetype": "application/julia", "name": "julia", "version": "1.6.3" } }, "nbformat": 4, "nbformat_minor": 4 }