week_3_self_check_solutions.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Week 3 Self Check Questions - Solutions"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Question 1:\n",
    "\n",
    "Let $A\\in\\mathbb{R}^{n\\times n}$. Proof that the LU decomposition exists with nonsingular $L$ and $U$ if and only if the determinant of all minors is nonzero.\n",
    "(Note: The minors are the submatrices $A[:m, :m]$).\n",
    "\n",
    "Does the LU decomposition exist for the following matrix? Justify your answer. \n",
    "$$\n",
    "\\begin{bmatrix}\n",
    "0.5 &   -2 &   2 \\\\\n",
    "-1 & 4 & -5\\\\\n",
    "9&  -5& 8 \n",
    "\\end{bmatrix}\n",
    "$$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution:\n",
    "\n",
    "First assume that the LU Decomposition exists. We then have $A = LU$ with nonsingular $L$ and $U$ and hence, for each minor $A[:m, :m] = L[:m, :m]\\times U[:m, :m]$.\n",
    "Since $L$ and $U$ are nonsingular it follows that also the minors are nonsingular and therefore have nonzero determinant.\n",
    "\n",
    "Now assume that all minors have nonzero determinant. We proceed by induction. Let the statement be true for all matrices have dimension $n-1$. We now partition $A\\in\\mathbb{R}^{n\\times n}$ as\n",
    "\n",
    "$$\n",
    "A = \\begin{bmatrix}\\hat{A} & b\\\\\n",
    "                   c^T & \\gamma\n",
    "    \\end{bmatrix}\n",
    "=\n",
    "\\begin{bmatrix}\\hat{L} & 0\\\\\n",
    "               \\ell^T & 1\n",
    "\\end{bmatrix}\n",
    "\\begin{bmatrix}\\hat{U} & r\\\\\n",
    "               0   & \\delta\n",
    "\\end{bmatrix}\n",
    "$$\n",
    "with $b,c, \\ell, r\\in\\mathbb{R}^{n-1}$, $\\gamma, \\delta\\in\\mathbb{R}$, $\\hat{L}, \\hat{U}\\in\\mathbb{R}^{n-1\\times n-1}$. Here $\\hat{A} = \\hat{L}\\times\\hat{U}$ is a nonsingular LU decomposition of\n",
    "$\\hat{A}$, which exists by induction hypothesis. To construct an LU decomposition of dimension $n$ we need to find $\\ell$, $r$ and a nonzero $\\delta$ such that the above decomposition is valid.\n",
    "\n",
    "By inspection we obtain $r=\\hat{L}^{-1}\\hat{b}$ and $\\ell^T = c^T\\hat{U}^{-1}$, which exists since $\\hat{L}$ and $\\hat{U}$ are nonsingular. For $\\delta$ we have the expression\n",
    "$$\n",
    "\\delta = \\gamma - l^Tr = \\gamma - c^T\\hat{A}^{-1}b.\n",
    "$$\n",
    "Since $\\hat{A}$ is nonsingular $\\delta$ exists. It is left to show that $\\delta\\neq 0$. However, this follows from\n",
    "$$\n",
    "\\det A = \\delta \\det\\hat{L}\\det{\\hat{U}} = \\delta\\det\\hat{A}\n",
    "$$\n",
    "and that $\\det A$ and $\\det\\hat{A}$ are nonzero by induction hypothesis.\n",
    "\n",
    "\n",
    "For the matrix \n",
    "$$\n",
    "\\begin{bmatrix}\n",
    "0.5 &   -2 &   2 \\\\\n",
    "-1 & 4 & -5\\\\\n",
    "9&  -5& 8 \n",
    "\\end{bmatrix}\n",
    "$$\n",
    "the first $2\\times 2$ subblock is singular. Hence, its determinant is zero and therefore the LU decomposition does not exist.\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Question 2:\n",
    "    \n",
    "Let $A\\in\\mathbb{R}^{n\\times n}$ be tridiagonal, that is only the main diagonal and the first upper and lower off-diagonals can be nonzero.\n",
    "    Assume that an LU decomposition exists. Show that it can be computed in $\\mathcal{O}(n)$ operations.\n",
    "    \n",
    "    "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution:\n",
    "\n",
    "In each outer loop of the Gaussian elimination only one off-diagonal element needs to be reduced. Hence, the cost for each outer loop is constant and independent of $n$, leading to a total cost of $\\mathcal{O}(n)$."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Question 3:\n",
    "    \n",
    "Proof the Sherman-Morrison formula\n",
    "$$\n",
    "        (A+uv^T)^{-1} = A^{-1} - \\frac{A^{-1}uv^TA^{-1}}{1+v^TA^{-1}u}\n",
    "        $$\n",
    "if $1+v^TA^{-1}u\\neq 0$."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We have\n",
    "        \\begin{align}\n",
    "            (A+uv^T) \\left[A^{-1} - \\frac{A^{-1}uv^TA^{-1}}{1+v^TA^{-1}u}\\right] &= \\nonumber\\\\\n",
    "            I - \\frac{uv^TA^{-1}}{1+v^TA^{-1}u} + uv^TA^{-1} - uv^T\\frac{A^{-1}uv^TA^{-1}}{1+v^TA^{-1}u} &=\\nonumber \\\\\n",
    "            I - \\left[\\frac{uv^TA^{-1} + uv^TA^{-1}uv^TA^{-1}}{1+v^TA^{-1}u} - uv^TA^{-1}\\right] &= \\nonumber\\\\\n",
    "            I - u\\left[\\frac{1+v^TA^{-1}u}{1+v^TA^{-1}u} -1\\right]v^TA^{-1}&=\\nonumber\\\\\n",
    "            I\\nonumber\n",
    "        \\end{align}\n",
    "Similarly, we show that\n",
    "        \\begin{align}\n",
    "            \\left[A^{-1} - \\frac{A^{-1}uv^TA^{-1}}{1+v^TA^{-1}u}\\right](A+uv^T) &= \\nonumber\\\\\n",
    "            I - A^{-1}u\\left[\\frac{1 + v^TA^{-1}u}{1+v^TA^{-1}u} - 1\\right]v^T &= \\nonumber\\\\\n",
    "            I\\nonumber\n",
    "        \\end{align}\n",
    "Hence, the formula holds."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Question 4:\n",
    "    \n",
    "Explain why the LU Decomposition without pivoting is not backward stable and why the backward error result from the notes for the LU\n",
    "Decomposition does not imply backward stability.\n",
    "\n",
    "Solution:\n",
    "\n",
    "Refer to the lecture notes and the example of the matrix\n",
    "\n",
    "$$\n",
    "\\begin{bmatrix}\\epsilon & 1\\\\\n",
    "               1         & 1\n",
    "\\end{bmatrix}\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
}