week_9_self_check_solutions.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Week 9 Self Check Questions"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "1.) Let $f$ be a function defined on the interval $[a,b]$. Let $x_k\\in [a,b]$, $k=0,\\dots,n$ with $x_i \\neq x_j$ for all $i\\neq j$. Write down the Lagrange interpolation polynomial $p$ of degree $n$ that interpolates $f$ in the points $x_k$."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution: \n",
    "\n",
    "We define\n",
    "$$\n",
    "L_k(x)=\\prod_{j=0,\\dots, n, j\\neq k} \\frac{(x-x_j)}{(x_k-x_j)}.\n",
    "$$\n",
    "Then\n",
    "$$\n",
    "p(x)=\\sum_{k=0,\\dots,n} f(x_k)L_k(x).\n",
    "$$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "2.) State the general form of Newton-Cotes quadrature rules."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution:\n",
    "\n",
    "For a general Newton-Cotes formula consider the interpolation points $x_j=a+jh$, $j=0,\\dots,n$ with $h=(b-a)/n$.\n",
    "Let $p_n$ be the corresponding Lagrange polynomial\n",
    "$$\n",
    "p_n(x)=\\sum_{j=0}^nf(x_j)L_j(x)\n",
    "$$\n",
    "for interpolating $f$ at these points. Then the Newton-Cotes formula takes the form\n",
    "$$\n",
    "I(f)\\approx \\sum_{j=0}^nf(x_j)\\omega_j,~\\omega_j=\\int_a^bL_j(x).\n",
    "$$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "3.) Explain the Runge phenomenon and state how it can be prevented."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution: \n",
    "\n",
    "Let $p_n(x)$ be the Lagrange interpolation polynomial of a continuous function $f$ in the interval $[-1,1]$. The Runge phenomenon states that as $n\\rightarrow\\infty$ the error $\\max_{x\\in[-1,1]}|f(x)-p_n(x)|$ may diverge to infinity for certain functions. The problem can be solved by using Chebychev points in $[-1,1]$ instead of equispaced points."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "4.) Explain why Newton-Cotes rules of increasing order will in general not converge to the exact integral of a function."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution:\n",
    "\n",
    "Since Newton-Cotes quadrature is based on interpolation in equispaced points the Runge phenomenon applies as well, preventing convergence as the order is increased."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "5.) A quadrature formula on the interval $[-1,1]$ uses the quadrature points\\\\\n",
    "$x_0=-\\alpha$, $x_1=\\alpha$, where $0<\\alpha\\leq 1$.\n",
    "$$\n",
    "\\int_{-1}^1f(x)dx\\approx w_0f(-\\alpha)+w_1f(\\alpha).\n",
    "$$\n",
    "The formula is required to be exact whenever $f$ is a polynomial of degree $1$. Show that $w_0=w_1=1$, independent of the value of $\\alpha$. Show also that there is one particular value of $\\alpha$, such that the formula is exact also for all polynomials of degree $2$. Find this $\\alpha$, and show that, for this value, the formula is also exact for all polynomials of degree $3$.\n",
    "\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution: In order to integrate constant functions exactly we require\n",
    "$$\n",
    "\\int_{-1}^11dx = 2 = w_0+w_1.\n",
    "$$\n",
    "To integrate the linear function $x$ exactly we require\n",
    "$$\n",
    "\\int_{-1}^1xdx = 0 = -\\alpha w_0+\\alpha w_1.\n",
    "$$\n",
    "Hence, $w_0=w_1$ and since $w_0+w_1=2$ we have $w_0=w_1=1$ independently of $\\alpha$. For quadratic functions we need\n",
    "$$\n",
    "\\int_{-1}^1x^2dx = \\frac{2}{3}= 2\\alpha^2,\n",
    "$$\n",
    "and therefore $\\alpha=\\frac{1}{\\sqrt{3}}$.\n",
    "For $x^3$ we have\n",
    "$$\n",
    "0 = \\int_{-1}^1x^3dx = -\\alpha^3+\\alpha^3.\n",
    "$$\n",
    "Hence, also cubic functions are integrated exactly by this quadrature rule.\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "6.) Consider the integral $I(f):=\\int_a^bf(x)dx$. Assume that we want to approximate $I(f)$ by a Newton-Cotes quadrature rule of the form $I_2(f):=\\omega_0f(a)+\\omega_1f((a+b)/2)+\\omega_2f(b)$. Derive the corresponding weights $\\omega_0$, $\\omega_1$, and $\\omega_2$."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution: \n",
    "\n",
    "Let $x_0 = a$, $x_1 = \\frac{a+b}{2}$, $x_2 = b$.\n",
    "We have\n",
    "\\begin{eqnarray}\n",
    "\\omega_0 & = & \\int_a^b\\frac{(x-x_1)(x-x_2)}{(x_0-x_1)(x_0-x_2)}dx\\nonumber\\\\\n",
    "& = & \\int_{-1}^1\\frac{t(t-1)}{2}\\frac{b-a}{2}dt\\nonumber\\\\\n",
    "& = & \\frac{b-a}{6}.\n",
    "\\end{eqnarray}\n",
    "We now use the symmetry of Newton-Cotes rules to derive that $\\omega_2 = \\omega_0 = \\frac{b-a}{6}$. Since the sum of all weights must be $(b-a)$ we obtain $\\omega_1 = \\frac{4(b-a)}{6}$."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python [conda env:dev]",
   "language": "python",
   "name": "conda-env-dev-py"
  },
  "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.8.6"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}