week_2_self_check_solutions.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Week 2 Self Check Questions - Solutions"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Question 1:**\n",
    "\n",
    "State the relative forward error, backward error, and condition number for the linear system of equations $Ax=b$.\n",
    "\n",
    "Let $x$ be the exact solution, and $\\tilde{x}$ the computed solution. Then the relative forward error is defined as\n",
    "\n",
    "$$\n",
    "e := \\frac{\\|x - \\tilde{x}\\|}{\\|x\\|}.\n",
    "$$\n",
    "\n",
    "The relative backward error is\n",
    "\n",
    "$$\n",
    "\\eta(\\tilde{x}) = \\frac{\\|b - A\\tilde{x}\\|}{\\|A\\| \\cdot \\|\\tilde{x}\\|}.\n",
    "$$\n",
    "\n",
    "The condition number is\n",
    "\n",
    "$$\n",
    "\\kappa(A) = \\|A\\|\\cdot \\|A^{1}\\|.\n",
    "$$\n",
    "\n",
    "**Question 2:**\n",
    "\n",
    "Assuming you are working in single precision floating point arithmetic and you have a backward stable algorithm for a problem with condition number $\\kappa = 10^{3}$. How many correct digits do you expect in your solution?\n",
    "\n",
    "\n",
    "The algorithm is backward stable. Hence, the backward error is expected to be a small multiple of machine precision. We have $\\epsilon_{mach} \\approx 6\\times 10^{-8}$. The condition number is $10^3$. Hence, the forward error is expected to be a multiple of $10^{-5}$, giving us around 3 to 4 digits of accuracy in the solution depending on the pre-factors. "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Question 3:**\n",
    "\n",
    "Compute the $1-$norm condition number of\n",
    "\n",
    "$$\n",
    "A = \\begin{bmatrix}1 & 1\\\\ 0 & \\epsilon\\end{bmatrix}\n",
    "$$\n",
    "\n",
    "in dependence of $\\epsilon$. What happens as $\\epsilon\\rightarrow 0$?\n",
    "\n",
    "We have $A^{-1} = \\begin{bmatrix}1 & -\\epsilon^{-1}\\\\ 0 & \\epsilon^{-1}\\end{bmatrix}$. Hence,\n",
    "\n",
    "$$\n",
    "\\kappa(A) = \\|A\\|_1\\cdot \\|A^{-1}\\|_1 = (1+\\epsilon) \\cdot \\frac{2}{\\epsilon}.\n",
    "$$\n",
    "\n",
    "and $\\kappa(A)\\rightarrow\\infty$ as $\\epsilon\\rightarrow 0$. The reason is simple. For $\\epsilon=0$ the matrix is not invertible and we expect the condition number to become unbounded as we reach this limit case."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Question 4**:\n",
    "\n",
    "Let $x\\in\\mathbb{R}^2$ and $f(x) = x_1 - x_2$. Compute the $\\infty$-norm condition number of $f$. Hint: Use the expression for the condition number of a differentiable function. For what inputs is the condition number large?\n",
    "\n",
    "The Jacobian of $f$ is $J = \\begin{bmatrix}1 & -1\\end{bmatrix}$. Hence, $\\|J\\|_{\\infty} = 2$. For the condition number we obtain\n",
    "\n",
    "\\begin{align}\n",
    "\\kappa &= \\frac{\\|J\\|_{\\infty}}{\\|f(x)\\|_{\\infty} / \\|x\\|_{\\infty}}\\nonumber\\\\\n",
    "       &= \\frac{2}{|x_1 - x_2| / \\max\\left\\{|x_1|, |x_2|\\right\\}}.\n",
    "\\end{align}\n",
    "\n",
    "The condition number is large if $x_1\\approx x_2$. This reflects the issue of cancellation errors. Consider two numbers $x_1$ and $x_2$ who agree to the first $5$ digits and each of them is accurate to 7 digits. Then the difference of the two numbers will only be accurate to 2 digits since the first 5 correct digits cancel each other out.\n"
   ]
  }
 ],
 "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
}