Midterm1-StudyGuide.ipynb

{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "%matplotlib inline\n",
    "import numpy as np\n",
    "import matplotlib.pyplot as plt\n",
    "plt.style.use('seaborn')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Midterm 1 Study Guide\n",
    "\n",
    "So far in this class, we have worked with the following topics.\n",
    "\n",
    "* Rootfinding\n",
    "  * Midpoint Methods\n",
    "  * Newton and Secant Methods\n",
    "  * Convergence classes of iterative methods (q-linear and q-quadratic)\n",
    "* Conditioning of problems\n",
    "* Stability of algorithms\n",
    "* Numerical Linear Algebra\n",
    "  * Thinking abstractly about vectors\n",
    "  * Inner products and norms\n",
    "  * Projectors $P = I - v v^T$ where $\\lVert v \\rVert = 1$\n",
    "  * Reflectors $F = I - 2 v v^T$ where $\\lVert v \\rVert = 1$\n",
    "  * Gram-Schmidt algorithm for QR factorization\n",
    "  * Householder algorithm for QR factorization\n",
    "  * Leading order cost of algorithms (like big-$O$, but we quantify the leading coefficient)\n",
    "  * Solution of linear equations and linear least squares problems\n",
    "  \n",
    "I recommend reviewing the class notebooks, in-class activities, and homeworks.  Below, I'll give some discussion of the sort of questions that I could ask.\n",
    "\n",
    "## Rootfinding\n",
    "\n",
    "All rootfinding methods attempt to find $x$ such that $f(x) = 0$, but they require different information about $f$ and/or where to look.\n",
    "If we know $f'(x) < 0$, which methods can be used?  What if we also know that $f(a) > 0 > f(b)$?  Does any method guarantee that we find a unique solution?"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "image/png": "iVBORw0KGgoAAAANSUhEUgAAAX4AAAD4CAYAAADrRI2NAAAABHNCSVQICAgIfAhkiAAAAAlwSFlzAAALEgAACxIB0t1+/AAAADl0RVh0U29mdHdhcmUAbWF0cGxvdGxpYiB2ZXJzaW9uIDMuMC4yLCBodHRwOi8vbWF0cGxvdGxpYi5vcmcvOIA7rQAAEudJREFUeJzt3X+s3Xddx/FnvQVm590o7aWsP6BDmne2LLgZXFk0MH5MqmssEjDr1MxsUUmY0cQ/RDCMmJDOqOjIFlBGUxZlsyBi42qGWcTyx7JUwCiseYfaDHrW2l7qJSurYsauf5x7x+3tOfd+z+/vj+cjITvnw/nx+fBlr3Pu9/u6n7tmfn4eSVJz/MikJyBJGi+DX5IaxuCXpIYx+CWpYQx+SWqYtZOewEpmZ8/3XTlav34dc3MXhjmdiavbmuq2Hqjfmuq2HqjfmjqtZ2Zmes1Kz6ntN/61a6cmPYWhq9ua6rYeqN+a6rYeqN+a+llPbYNfktSZwS9JDWPwS1LDGPyS1DAGvyQ1TKnrnP148qkzPPrE05w6d4HNG9Zx603b2XntpklPS5JKo1bB/+RTZ/iLQ9948X5r9rkX7xv+ktRWq1M9jz7xdJfxb411HpJUZrUK/lPf6fzbeKfPPTfmmUhSedUq+DdvXNdx/KoNl495JpJUXrU6x3/rTdsvOsf/w/HXdHz8ixeCv3OBzRu9ECypGWoV/Iuh/egT3+L0uee4asPl3HrTazqGuReCJTVVrYIf2qG989pNzMxMMzt7vuvjVroQbPBLqrNanePvhReCJTVVY4PfC8GSmqqxwX/rTdu7jHe+ECxJdVG7c/xF9XIhWJLqpLHBDz+8ECxJTdLYUz2S1FSN/sZflL/oJalODP5V+ItekurGUz2rcMdPSXUztm/8EfFa4IPAlZn57nG976D8RS9JdVPoG39E7I+IsxHx9WXjuyIiI+J4RLx/pdfIzBOZedcgk50Ef9FLUt0U/cZ/ALgfeGhxICKmgAeAW4AWcDQiDgFTwL5lz78zM88OPNsJ6HXHT0kqu0LBn5lHImL7suEbgeOZeQIgIh4B9mTmPmD3MCa3fv061q6d6vv5MzPTA89h95unueKKy/js49/k5JnzbNs0zXvetoM33bC14+OPfK3FZx//Jt8+c55Xr/LYfgxjTWVSt/VA/dZUt/VA/dbU63oGOce/BTi55H4L2NntwRGxAfgIcENE/P7CB8SK5uY6n18vYrXdOXtxzdYr+dAdb7horNNrL28APX36Wf74r77Cs8/+71AaQMNcUxnUbT1QvzXVbT1QvzV1Ws9qHwSDBP+aDmPz3R6cmeeA9w7wfqXnVs+SqmCQOmcL2Lbk/lbg1GDTqTYbQJKqYJBv/EeBHRFxNfAMcBtw+1BmVVGbN66jNXtpyNsAklQmReucDwNPtG9GKyLuyszngbuBx4BjwMHMvLT+0iBu9SypCoq2evZ2GT8MHB7qjCrMrZ4lVYF79QxZ0a2e3fhN0qQY/BPgxm+SJslN2ibAjd8kTZLBPwHWPiVNksE/AW78JmmSDP4JsPYpaZK8uDsB1j4lTZLBPyFFa5+wpPp57gKbN1j9lDQYg7/krH5KGjbP8Zec1U9Jw2bwl5zVT0nDZvCXnNVPScNm8Jec1U9Jw+bF3ZKz+ilp2Az+Clisfq72t0Ld8VNSEQZ/TVj7lFSU5/hrwtqnpKIM/pqw9impKIO/Jqx9SirK4K8Ja5+SivLibk30Wvu0ASQ1l8FfI738oXcbQFJzeaqngWwASc1m8DeQDSCp2Qz+BrIBJDWbwd9ANoCkZvPibgO58ZvUbAZ/Q/XSALL2KdWLwa+urH1K9TTW4I+IdwK3Aq8EHsjML47z/dWblWqfBr9UXYWDPyL2A7uBs5l53ZLxXcB9wBTwYGbe2+01MvMLwBciYj3wJ4DBX2LWPqV66uUb/wHgfuChxYGImAIeAG4BWsDRiDhE+0Ng37Ln35mZZxdu/8HC81RimzeuozV7achb+5SqrXDwZ+aRiNi+bPhG4HhmngCIiEeAPZm5j/ZPBxeJiDXAvcA/ZuZX+561xuLWm7ZfdI7/h+PWPqUqG/Qc/xbg5JL7LWDnCo//LeDtwJUR8brM/MRKL75+/TrWrp3qe3IzM9N9P7esxrmm3W+e5oorLuOzj3+Tk2fOs23TNO952w7edMPWob2Hx6j86rYeqN+ael3PoMG/psPYfLcHZ+bHgI8VffG5uc7nmItY7e/TVtEk1nTN1iv50B1vuGis2xx6rX56jMqvbuuB+q2p03pW+yAYNPhbwLYl97cCpwZ8TVWQ1U+pOgbdsuEosCMiro6IlwK3AYcGn5aqxh0/peooHPwR8TDwRPtmtCLirsx8HrgbeAw4BhzMzEuvBqr2rH5K1dFLq2dvl/HDwOGhzUiVZPVTqg5359RQuOOnVB3u1aOhcMdPqToMfg1Nzzt+nrvA5g3u+CmNm8GvsbL2KU2e5/g1VtY+pckz+DVW1j6lyTP4NVb+oXdp8gx+jZW1T2nyvLirsbL2KU2ewa+xW6x9Ftkl0T/2Lg2fwa/SsvopjYbn+FVaVj+l0TD4VVpWP6XRMPhVWlY/pdEw+FVaVj+l0fDirkrL6qc0Gga/Sq3nHT+tfUqrMvhVedY+pd54jl+VZ+1T6o3Br8qz9in1xuBX5Vn7lHpj8KvyrH1KvfHirirP2qfUG4NftVC09glWPyWDX41i9VPyHL8axuqnZPCrYax+Sga/Gsbqp2Twq2Gsfkpe3FXD9FL9tP2juhpb8EfENcBvAxuBxzPz4+N6b2mpItVP2z+qs0LBHxH7gd3A2cy8bsn4LuA+YAp4MDPv7fYamXkMeG9E/AjwyYFmLY3YSu0fg19VV/Qb/wHgfuChxYGImAIeAG4BWsDRiDhE+0Ng37Ln35mZZyPiF4D3L7yWVFq2f1RnhYI/M49ExPZlwzcCxzPzBEBEPALsycx9tH866PQ6h4BDEfEo8JnV3nf9+nWsXTtVZIodzcxM9/3csqrbmsq6nle/apqnTz97yfi2TdOrzrmsa+pX3dYD9VtTr+sZ5Bz/FuDkkvstYGe3B0fEzcC7gJcBh4u8wdxc529dRczMTDM7e77v55dR3dZU5vW846e2XXSOf+n4SnMu85r6Ubf1QP3W1Gk9q30QDBL8azqMzXd7cGZ+CfjSAO8njY0bv6nOBgn+FrBtyf2twKnBpiOVR18bv527wOYNVj9VboME/1FgR0RcDTwD3AbcPpRZSRVi9VNVU+g3dyPiYeCJ9s1oRcRdmfk8cDfwGHAMOJiZl54UlWrOjd9UNUVbPXu7jB+m4IVaqa6sfqpq3KtHGpAbv6lqDH5pQG78pqpxkzZpQFY/VTUGvzQEi9XP1X45yB0/VQYGvzQm1j5VFp7jl8bE2qfKwuCXxsTap8rC4JfGxNqnysLgl8bE2qfKwou70phY+1RZGPzSGPW146fVTw2ZwS+VkNVPjZLn+KUSsvqpUTL4pRKy+qlRMvilErL6qVEy+KUSsvqpUfLirlRCVj81Sga/VFJFq5/WPtUrg1+qMGuf6ofn+KUKs/apfhj8UoVZ+1Q/DH6pwqx9qh8Gv1Rh1j7VDy/uShVm7VP9MPilinPHT/XK4JcawuqnFnmOX2oIq59aZPBLDWH1U4sMfqkhrH5qkcEvNYTVTy0a68XdiLgcOALck5n/MM73lpqul+rni+2fcxfYvMH2T90UCv6I2A/sBs5m5nVLxncB9wFTwIOZee8qL/V7wME+5yppQEWqn7Z/6q/oN/4DwP3AQ4sDETEFPADcArSAoxFxiPaHwL5lz78TeD3wFHDZYFOWNEortX8M/nooFPyZeSQiti8bvhE4npknACLiEWBPZu6j/dPBRSLiLcDlwLXA/0TE4cx8YaX3Xb9+HWvXThWZYkczM9N9P7es6ramuq0Hqr+mU+e6t3+qvrZFdVnHol7XM8g5/i3AySX3W8DObg/OzA8CRMSvAd9ZLfQB5uY6/x+wiJmZaWZnz/f9/DKq25rqth6ox5o2b1hHa/bSiudVGy6v/NqgHsdoqU7rWe2DYJBWz5oOY/OrPSkzD3hhVyov2z/1N8g3/hawbcn9rcCpwaYjadLc+K3+Bgn+o8COiLgaeAa4Dbh9KLOSNFGL7Z8ip0Xc+K16Cp3qiYiHgSfaN6MVEXdl5vPA3cBjwDHgYGZ+Y6XXkVQvi9XP1uxzvDA//2L188mnzkx6alpB0VbP3i7jh4HDQ52RpMqw+llNbtkgqW9u/FZNBr+kvrnxWzUZ/JL6ZvWzmvwLXJL6ZvWzmgx+SQMp+jd/rX2Wh8EvaeTc8bNcPMcvaeT8e7/lYvBLGjlrn+Vi8EsaOWuf5WLwSxo5a5/l4sVdSSNn7bNcDH5JY1G09glWP0fN4JdUKlY/R89z/JJKxern6Bn8kkrF6ufoGfySSsXq5+gZ/JJKxern6HlxV1KpWP0cPYNfUum44+doGfySKsnaZ/88xy+pkqx99s/gl1RJ1j77Z/BLqiRrn/0z+CVVkrXP/nlxV1IlWfvsn8EvqbL62vHz3AU2b2h29dPgl1R7Vj8v5jl+SbVn9fNiBr+k2rP6eTGDX1LtWf282NiCPyJujogvR8QnIuLmcb2vJFn9vFihi7sRsR/YDZzNzOuWjO8C7gOmgAcz894VXmYe+B5wGdDqe8aS1KNeqp9N2PitaKvnAHA/8NDiQERMAQ8At9AO8qMRcYj2h8C+Zc+/E/hyZv5LRGwCPgr88mBTl6TiFqufMzPTzM6e7/iYprR/CgV/Zh6JiO3Lhm8EjmfmCYCIeATYk5n7aP900M0c8LIi77t+/TrWrp0q8tCOZmam+35uWdVtTXVbD9RvTXVbD3Rf02NH/7XL+El2v/l1o5zSQHo9RoP0+LcAJ5fcbwE7uz04It4FvAN4Oe2fHlY1N9f5SnwRK32qV1Xd1lS39UD91lS39cDKa/r2f3UeP3nmfGn/d+i0ntU+CAYJ/jUdxua7PTgzPw98foD3k6SR2rxxHa3ZSyuedWv/DNLqaQHbltzfCpwabDqSNDlNaf8M8o3/KLAjIq4GngFuA24fyqwkaQKasvFb0Trnw8DNwMaIaAH3ZOanIuJu4DHaTZ79mfmNFV5Gkkqvr43fKlb9LNrq2dtl/DBweKgzkqQKqHL10y0bJKkPVd74zeCXpD5UeeM3g1+S+lDljd8MfknqQ5Wrn/4FLknqQ5Wrnwa/JPWpaPWzbLVPg1+SRqiMtU/P8UvSCJWx9mnwS9IIlbH2afBL0giVsfZp8EvSCJWx9unFXUkaoTLWPg1+SRqxstU+DX5JKoFx1j49xy9JJTDO2qfBL0klMM7ap8EvSSUwztqnwS9JJTDO2qcXdyWpBMZZ+zT4JakkevlD74PwVI8kNYzBL0kNY/BLUsMY/JLUMAa/JDXMmvn5+UnPQZI0Rn7jl6SGMfglqWEMfklqGINfkhrG4JekhjH4JalhDH5Japha7s4ZEbuA+4Ap4MHMvHfCUxpIRDwNnAd+ADyfmW+Y6IT6EBH7gd3A2cy8bmHsFcDfANuBp4Ffysy5Sc2xF13W82Hg14HZhYd9IDMPT2aGvYmIbcBDwKuAF4C/zMz7Kn6Muq3pw1TwOEXEZcAR4GW0s/tzmXlPRFwNPAK8Avgq8KuZ+X8rvVbtvvFHxBTwAPBzwLXA3oi4drKzGoq3ZOb1VQz9BQeAXcvG3g88npk7gMcX7lfFAS5dD8CfLRyn66sQJks8D/xuZl4DvBF438K/N1U+Rt3WBNU8Tt8H3pqZPwFcD+yKiDcCf0R7PTuAOeCu1V6odsEP3Agcz8wTC596jwB7JjynxsvMI8B/LxveA3x64fangXeOdVID6LKeysrM05n51YXb54FjwBaqfYy6ramSMnM+M7+3cPclC/+ZB94KfG5hvNAxqmPwbwFOLrnfosIHe8E88MWI+EpE/MakJzNEmzLzNLT/JQVeOeH5DMPdEfHvEbE/ItZPejL9iIjtwA3Ak9TkGC1bE1T0OEXEVET8G3AW+CfgP4HvZubzCw8plHd1DP41HcaqviHRT2fmT9I+ffW+iHjTpCekjj4O/DjtH8NPA3862en0LiJ+DPhb4Hcy89lJz2cYOqypsscpM3+QmdcDW2mf3bimw8NWzbs6Bn8L2Lbk/lbg1ITmMhSZeWrhn2eBv6N9wOvgTERcBbDwz7MTns9AMvPMwr+YLwCfpGLHKSJeQjsg/zozP78wXOlj1GlNVT9OAJn5XeBLtK9dvDwiFos6hfKujsF/FNgREVdHxEuB24BDE55T3yLi8oiYXrwN/Czw9cnOamgOAXcs3L4D+PsJzmVgiwG54Bep0HGKiDXAp4BjmfnRJf9VZY9RtzVV9ThFxExEvHzh9o8Cb6d93eKfgXcvPKzQMarltswR8fPAn9Ouc+7PzI9MeEp9i4jX0v6WD+0K12equJ6IeBi4GdgInAHuAb4AHAReDXwbeE9mVuKCaZf13Ez79ME87erjby6eHy+7iPgZ4MvAf9CuPgJ8gPY58aoeo25r2ksFj1NEvJ72xdsp2l/aD2bmHy5kxGKd82vAr2Tm91d6rVoGvySpuzqe6pEkrcDgl6SGMfglqWEMfklqGINfkhrG4JekhjH4Jalh/h9EvqT8pjQJ/gAAAABJRU5ErkJggg==\n",
      "text/plain": [
       "<Figure size 432x288 with 1 Axes>"
      ]
     },
     "metadata": {
      "needs_background": "light"
     },
     "output_type": "display_data"
    }
   ],
   "source": [
    "def iterate(f, x0, n):\n",
    "    \"\"\"Apply n iterations of x_{i+1} = f(x_i),\n",
    "    return resulting history as an array.\n",
    "    \"\"\"\n",
    "    hist = [x0]\n",
    "    for i in range(n):\n",
    "        hist.append(f(hist[i]))\n",
    "    return np.array(hist)\n",
    "\n",
    "def f1(x):\n",
    "    return np.cos(x)\n",
    "\n",
    "hist1 = iterate(f1, 1, 80)\n",
    "x_star = hist1[-1] # Suppose the last estimate is best\n",
    "plt.semilogy(np.abs(hist1[:30] - x_star), 'o');"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "What convergence class is the above figure evidence of?"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "image/png": "iVBORw0KGgoAAAANSUhEUgAAAYEAAAD4CAYAAAAKA1qZAAAABHNCSVQICAgIfAhkiAAAAAlwSFlzAAALEgAACxIB0t1+/AAAADl0RVh0U29mdHdhcmUAbWF0cGxvdGxpYiB2ZXJzaW9uIDMuMC4yLCBodHRwOi8vbWF0cGxvdGxpYi5vcmcvOIA7rQAAFHlJREFUeJzt3X+MXWd+1/G3dwaljHfY9dq33vgHGaeyvqwVUYKqTN0KWEGtdXFIqtUKxVmgql2hoKZdEBUkRKJB1TKRFi1EOFq2DakbWMVEaSSs2pBWkdLsH4M17ZbS2ta3hNSpr23siTt0XU+rrLvDH/dOdjqeOz/uPXPvmXneLynyPc/c89xPrGQ+97nn3HO2zM3NIUkq00cGHUCSNDiWgCQVzBKQpIJZApJUMEtAkgo2POgAazE9favrU5m2bRthZma2yjiVM2Pv6p4P6p+x7vnAjGvVaIxu6fSzYlYCw8NDg46wIjP2ru75oP4Z654PzFilYkpAknQ3S0CSCmYJSFLBLAFJKpglIEkF21CniHbj3IXrnJm8xNWbs+zaPsKRg2OMH9g56FiSVAubugTOXbjOV0+f/3C7OX37w22LQJI2+cdBZyYvdRh/r685JKmuNnUJXH1/6W/rXbt5u89JJKmeNnUJ7NoxsuT4vdu39jmJJNXTpi6BIwfHOozf198gklRTAz0wHBH3A88AH8vMz1U9//zB3zOT73Ht5m3u3b6VIwfv86CwJLV1XQIR8RLwMHAjMx9YMH4YeB4YAl7MzOc6zZGZ7wLHI+K1bnOsZPzATsYP7KTRGGV6+tZ6vYwkbUi9rAROAieAl+cHImIIeAE4BDSBqYg4TasQJhbtfywzb/Tw+pKkHnVdApn5dkSMLRp+CHin/Q6fiDgFPJqZE7RWDT3Ztm2kp8uzNhqjvUZYd2bsXd3zQf0z1j0fmLEqVR8T2A1cXrDdBMY7PTkitgNfBB6MiKfbZdFRLzdo2AgfB5mxd3XPB/XPWPd8YMa1Wq6Mqi6Bpe5e0/FuYJl5E3ii4gySpFWq+hTRJrB3wfYe4GrFryFJqkjVK4EpYH9E7AOuAI8Bj1f8GpKkinS9EoiIV4DJ1sNoRsTxzLwDPAm8AVwEXs3M88vNI0kanF7ODjraYfwscLbrRJKkvtnUl42QJC3PEpCkglkCklQwS0CSCrapby+5Xj68b/H7s+za4X2LJW1clsAaed9iSZuJHwetkfctlrSZWAJr5H2LJW0mlsAaed9iSZuJJbBG3rdY0mbigeE18r7FkjYTS6AL8/ctlqSNzo+DJKlgloAkFcwSkKSCWQKSVDBLQJIKZglIUsEsAUkq2EC/JxARnwK+AOwA3szMrwwyjySVpusSiIiXgIeBG5n5wILxw8DzwBDwYmY+12mOzLwIPBERHwF+vtsskqTu9LISOAmcAF6eH4iIIeAF4BDQBKYi4jStQphYtP+xzLwREY8AT7XnkiT10Za5ubmud46IMeCX51cCEXEQeDYzP9PefhogMxcXwFJzncnMI8s9586dP50bHh7qOq8kFWpLpx9UfUxgN3B5wXYTGO/05Ij4NPBZ4B7g7EqTz8wsfS3/1Wg0RpmevtX1/v1gxt7VPR/UP2Pd84EZ16rRGO34s6pLYKm26bjUyMy3gLcqziBJWqWqTxFtAnsXbO8Brlb8GpKkilS9EpgC9kfEPuAK8BjweMWvIUmqSNcrgYh4BZhsPYxmRBzPzDvAk8AbwEXg1cw8X01USVLVul4JZObRDuNnWcVBXknS4HnZCEkqmCUgSQWzBCSpYJaAJBXMEpCkglkCklQwS0CSCmYJSFLBLAFJKpglIEkFswQkqWCWgCQVrOpLSasL5y5c58zkJa7enGXX9hGOHBxj/MDOQceSVABLYMDOXbjOV09/52rbzenbH25bBJLWmx8HDdiZyUsdxt/raw5JZbIEBuzq+7NLjl+7ebvPSSSVyBIYsF07RpYcv3f71j4nkVQiS2DAjhwc6zB+X3+DSCqSB4YHbP7g75nJ97h28zb3bt/KkYP3eVBYUl8MtAQi4tPAzwLngVOZ+dYg8wzK+IGdjB/YSaMxyvT0rUHHkVSQrksgIl4CHgZuZOYDC8YPA88DQ8CLmfncMtPMAX8EfBfQ7DaLJKk7vawETgIngJfnByJiCHgBOETrl/pURJymVQgTi/Y/Bnw9M38tInYCXwY+30MeSdIadV0Cmfl2RIwtGn4IeCcz3wWIiFPAo5k5QWvV0MkMcM9Kr7lt2wjDw0NdJoZGY7TrffvFjL2rez6of8a65wMzVqXqYwK7gcsLtpvAeKcnR8Rngc8AH6e1qljWzMzS59Svxkb4vN2Mvat7Pqh/xrrnAzOu1XJlVHUJbFlibK7TkzPzdeD1ijNIklap6u8JNIG9C7b3AFcrfg1JUkWqXglMAfsjYh9wBXgMeLzi15AkVaTrlUBEvAJMth5GMyKOZ+Yd4EngDeAi8Gpmnl9uHknS4PRydtDRDuNngbNdJ5Ik9Y3XDpKkglkCklQwS0CSCmYJSFLBLAFJKpglIEkFswQkqWCWgCQVzBKQpIJZApJUMEtAkgpmCUhSwSwBSSqYJSBJBbMEJKlgloAkFcwSkKSCWQKSVLCqbzS/JhHx14DPt3McyMwfGGQeSSpN1yUQES8BDwM3MvOBBeOHgeeBIeDFzHyu0xyZ+XXg6xHxI8BUt1kkSd3pZSVwEjgBvDw/EBFDwAvAIaAJTEXEaVqFMLFo/2OZeaP9+HHgx3vIIknqQtclkJlvR8TYouGHgHcy812AiDgFPJqZE7RWDXeJiL8I/GFmfrPbLJKk7lR9TGA3cHnBdhMYX2Gf48AvrGbybdtGGB4e6jIaNBqjXe/bL2bsXd3zQf0z1j0fmLEqVZfAliXG5pbbITN/ZrWTz8zMrjnQvEZjlOnpW13v3w9m7F3d80H9M9Y9H5hxrZYro6pPEW0Cexds7wGuVvwakqSKVL0SmAL2R8Q+4ArwGK2DvpKkGup6JRARrwCTrYfRjIjjmXkHeBJ4A7gIvJqZ56uJKkmqWi9nBx3tMH4WONt1IklS33jZCEkqmCUgSQWzBCSpYJaAJBXMEpCkglkCklQwS0CSCmYJSFLBLAFJKpglIEkFswQkqWCWgCQVzBKQpIJZApJUMEtAkgpmCUhSwSwBSSqYJSBJBbMEJKlgXd9juAoRcQB4FrgJvJmZrw0yjySVpuuVQES8FBE3IuJ3Fo0fjoiMiHci4qkVpvlh4N9n5j8C/kG3WSRJ3ellJXASOAG8PD8QEUPAC8AhoAlMRcRpYAiYWLT/MeA/AT8TEY8A23vIIknqQtclkJlvR8TYouGHgHcy812AiDgFPJqZE8DDHab6iXZ5vN5tFklSd6o+JrAbuLxguwmMd3pyu0T+BbAV+NJKk2/bNsLw8FDX4RqN0a737Rcz9q7u+aD+GeueD8xYlapLYMsSY3OdnpyZl4B/uNrJZ2Zmu4jU0miMMj19q+v9+8GMvat7Pqh/xrrnAzOu1XJlVPUpok1g74LtPcDVil9DklSRqlcCU8D+iNgHXAEeAx6v+DUkSRXp5RTRV4DJ1sNoRsTxzLwDPAm8AVwEXs3M89VElSRVrZezg452GD8LnO06kSSpb7xshCQVzBKQpIIN9NpBWh/nLlznzOQlrr4/y64dIxw5OMb4gZ2DjiWphiyBTebchet89fR3jsU3p29/uG0RSFrMj4M2mTOTlzqMv9fXHJI2Bktgk7n6/tLfqr5283afk0jaCCyBTWbXjpElx+/dvrXPSSRtBJbAJnPk4FiH8fv6G0TShuCB4U1m/uDvmcn3uHbzNvdu38qRg/d5UFjSkiyBTWj8wE5/6UtaFT8OkqSCWQKSVDBLQJIKZglIUsEsAUkqmCUgSQWzBCSpYJaAJBXMEpCkgvXtG8MRcT/wDPCxzPxcpzFJUv+saiUQES9FxI2I+J1F44cjIiPinYh4ark5MvPdzDy+0pgkqX9WuxI4CZwAXp4fiIgh4AXgENAEpiLiNDAETCza/1hm3ug5rSSpUqsqgcx8OyLGFg0/BLyTme8CRMQp4NHMnAAerjRl27ZtIwwPD3W9f6MxWmGa9WHG3tU9H9Q/Y93zgRmr0ssxgd3A5QXbTWC805MjYjvwReDBiHg6MyeWGlvuBWdmlr5r1mo0GqNMT9/qev9+MGPv6p4P6p+x7vnAjGu1XBn1UgJblhib6/TkzLwJPLHSmCSpf3o5RbQJ7F2wvQe42lscSVI/9bISmAL2R8Q+4ArwGPB4JakkSX2x2lNEXwEmWw+jGRHHM/MO8CTwBnAReDUzz69fVElS1VZ7dtDRDuNngbOVJpIk9Y2XjZCkglkCklQwS0CSCmYJSFLBLAFJKpglIEkFswQkqWCWgCQVzBKQpIJZApJUMEtAkgpmCUhSwSwBSSqYJSBJBbMEJKlgloAkFcwSkKSCWQKSVDBLQJIKtqp7DFchIu4HngE+lpmfa499CvgCsAN4MzO/0q88kqRVlkBEvAQ8DNzIzAcWjB8GngeGgBcz87lOc2Tmu8DxiHhtwdhF4ImI+Ajw8939K0iSurXalcBJ4ATw8vxARAwBLwCHgCYwFRGnaRXCxKL9j2XmjaUmjohHgKfa80uS+mjL3Nzcqp4YEWPAL8+vBCLiIPBsZn6mvf00QGYuLoDF87w2/3HQovEzmXlkuX3v3PnTueHhoVXllSR9aEunH/RyTGA3cHnBdhMY7/TkiNgOfBF4MCKezsyJiPg08FngHuDsSi84MzPbddhGY5Tp6Vtd798PZuxd3fNB/TPWPR+Yca0ajdGOP+ulBJZqlo7Lisy8CTyxaOwt4K0eMkiSetDLKaJNYO+C7T3A1d7iSJL6qZeVwBSwPyL2AVeAx4DHK0klSeqLVa0EIuIVYLL1MJoRcTwz7wBPAm8AF4FXM/P8+kWVJFVtVSuBzDzaYfwsqzigK0mqJy8bIUkFswQkqWCWgCQVzBKQpIJZApJUMEtAkgpmCUhSwSwBSSqYJSBJBevb7SW1sZ27cJ0zk5e4enOWXdtHOHJwjPEDO3uf7/1Zdu2ocL6K8m2EjHXPtxEyVp1vo2RcaOjZZ5+tbLL1Njv7wbPd7rt16z3Mzn5QYZrq1TXjuQvX+erp83xz9lvMzcE3Z7/Fb+Q0n/zECHsaH+1tPiqer4J8GyFj3fNthIxV56tzxq1b7/lXnX7mx0Fa0ZnJSx3G39uU863HnKXNtx5z1n2+9ZhzPTIuZgloRVffX/qObtdu3t6U863HnKXNtx5z1n2+9ZhzPTIuZgloRbt2jCw5fu/2rZtyvvWYs7T51mPOus+3HnOuR8bFLAGt6MjBsQ7j923K+dZjztLmW4856z7fesy5HhkX88BwjdQ1457GR/nkJ0a4/gd/zO0/+Ra7d3yUoz+0v+szFOo+30bIWPf5NkLGkv6dlzswvGVuruO94WtnevpW12EbjVGmp29VGadyZuxd3fNB/TPWPR+Yca0ajdEtnX7mx0GSVDBLQJIK1rdvDEfE/cAzwMcy83PtsU8DPwucB05l5lv9yiNJWmUJRMRLwMPAjcx8YMH4YeB5YAh4MTOf6zRHZr4LHI+I1xYMzwF/BHwX0Fx7fElSL1a7EjgJnABenh+IiCHgBeAQrV/gUxFxmlYhTCza/1hm3lhi3q9n5q9FxE7gy8Dn1xZfktSLVZVAZr4dEWOLhh8C3mm/wyciTgGPZuYErVXDaub9dvvhDHDPSs9f7gj3ajQao73s3hdm7F3d80H9M9Y9H5ixKr0cE9gNXF6w3QTGOz05IrYDXwQejIinM3MiIj4LfAb4OK2VhiSpj3opgaXelXc8jz8zbwJPLBp7HXi9hwySpB70copoE9i7YHsPcLW3OJKkfuplJTAF7I+IfcAV4DHg8UpSSZL6YlUrgYh4BZhsPYxmRBzPzDvAk8AbwEXg1cw8v35RJUlV21DXDpIkVcvLRkhSwYq40fxavtk8CBGxl9YX8T4JfBv4ucx8frCp7tb+guCvA1cyc1XfBemniPg48CLwAK0z1Y5l5uRgU31HRPwT4MdpZftt4Mcy808GnOmuqwFExCeA/wKMAZeAv5uZMzXL+CXg7wAfAP+H1t/l/6tLvgU/+2ngS0AjM98fRL6VbPqVwIJvNv8wcAA4GhEHBpvqLneAf5qZnwK+H/iJGmYE+AKt4z919Tzw3zPzLwHfS42yRsRu4KeA72v/ohiidTLFoJ0EDi8aewp4MzP3A2+2twfpJHdn/FXggcz8y8DvAk/3O9QCJ7k73/ybu0PA7/c70Fps+hJgwTebM/MD4BTw6IAz/RmZeS0zv9F+fIvWL6/dg031Z0XEHuAIrXfatRMRfwH468B/BMjMDwb1znAZw8Cfj4hhYIQanFKdmW8Df7Bo+FHgF9uPfxH4kb6GWmSpjJn5K+2TUwD+B61T1Aeiw98hwL8F/hnLfH+qDkoogaW+2VyrX7ALtS/P8SBwbsBRFvt3tP6D/vZKTxyQ+4Fp4Bci4jcj4sWIqO5GrD3KzCvAv6H1rvAa8IeZ+SuDTdXRzsy8Bq03KMB3DzjPSo4B/23QIRaKiEdofWz6W4POspISSmBN32wepIj4KPBLwD/OzG8OOs+8iJj/vPM3Bp1lGcPAXwW+kpkPArcZ/McYH4qIbbTeYe8DdgFbI+LvDTbVxhcRz9D6OPVrg84yLyJGaF02/18OOstqlFACG+KbzRHx52gVwNfal9Ookx8EHomIS7Q+TvubEfGfB5robk2gmZnzK6jXaJVCXfwQ8HuZOZ2Z36J1uZQfGHCmTq5HxL0A7T+XugLwwEXEj9I6IPv5zKzTG7vvoVX2v9X+f2YP8I2I+OQgQ3VSwtlBtf9mc0RsofVZ9sXM/PKg8yyWmU/TPvDWvhHQT2dmrd7FZub/jYjLERGZmcDfAi4MOtcCvw98f/td4h/Tyvfrg43U0WngR4Hn2n/+18HGuVv7jL9/DvyNzJwddJ6FMvO3WfARWrsIvs+zgwZkg3yz+QeBv0/rHfb/bP/ztwcdagP6SeBrEfG/gL8C/OsB5/lQe4XyGvANWqeHfgT4uYGGYumrAdD65X8oIv43rbNbBnpKdYeMJ4BR4Ffb/7/8h5rl2zD8xrAkFWzTrwQkSZ1ZApJUMEtAkgpmCUhSwSwBSSqYJSBJBbMEJKlg/x8jAut7TOfKuQAAAABJRU5ErkJggg==\n",
      "text/plain": [
       "<Figure size 432x288 with 1 Axes>"
      ]
     },
     "metadata": {
      "needs_background": "light"
     },
     "output_type": "display_data"
    }
   ],
   "source": [
    "def f2(x):\n",
    "    return x - (np.cos(x) - x) / (-np.sin(x) - 1)\n",
    "\n",
    "hist2 = iterate(f2, 1, 15)\n",
    "plt.semilogy(np.abs(hist2 - x_star), 'o');"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "What convergence class is the above plot evidence of?\n",
    "\n",
    "What happens after the fourth iteration?\n",
    "\n",
    "Can you sketch a function such that Newton exhibits a certain behavior, such as error decreasing while residual increases?"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Conditioning\n",
    "\n",
    "You should be able to estimate (relative) condition numbers (a finite number or $\\infty$) for differentiable functions such as $\\sin x$ at a given value of $x$.  Recall that for differentiable functions, the relative condition number is\n",
    "$$ \\kappa = \\lvert f'(x) \\rvert \\frac{\\lvert x \\rvert}{\\lvert f(x) \\rvert} . $$\n",
    "You should be able to estimate condition number for a $2\\times 2$ diagonal matrix, for example.\n",
    "\n",
    "## Stability\n",
    "\n",
    "You should be able to recognize unstable algorithms, such as in the activity where we computed $\\exp(-20)$ by directly evaluating the Taylor series."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "image/png": "iVBORw0KGgoAAAANSUhEUgAAAXoAAAD4CAYAAADiry33AAAABHNCSVQICAgIfAhkiAAAAAlwSFlzAAALEgAACxIB0t1+/AAAADl0RVh0U29mdHdhcmUAbWF0cGxvdGxpYiB2ZXJzaW9uIDMuMC4yLCBodHRwOi8vbWF0cGxvdGxpYi5vcmcvOIA7rQAAIABJREFUeJzt3Xl81fWV//FX9psNEpIbEpIgiHgkghsIMhaXumFtsZ3WFqwKHduZdn46M61tx5lRRGpb22qtHbUb00K1I6W1WjtFwQ21bgUVoiwfZQ1ZICshC9nz++Pe4DUlcLPeJe/n4+HDe7/3c3PP4Sbnfu75fr7fb0x3dzciIhK9YkMdgIiIDC8VehGRKKdCLyIS5VToRUSinAq9iEiUiw91AL1VVTX0axlQZmYKdXXNwxVOyCm/yKb8Ilsk5ef1psf09VjEz+jj4+NCHcKwUn6RTflFtmjJL+ILvYiIHJ8KvYhIlFOhFxGJcir0IiJRToVeRCTKhd3yyoH4yd0b+nzsK7deNGJxiIiEI83oRUSinAq9iEiUC6p1Y2bzgfuBOGCFc+7uXo+fBPwS8AK1wHXOuVL/Y4uB2/xD73LOrRqi2EVEJAgnnNGbWRzwIHAlUAQsMrOiXsPuAX7tnDsDWA581//cccAdwBxgNnCHmWUOXfgiInIiwbRuZgM7nXO7nXNtwGrg6l5jioDn/LdfCHj8CuAZ51ytc64OeAaYP/iwRUQkWMG0bvKB/QH3S/HN0ANtAT6Nr73zKSDdzLL6eG7+8V4sMzNlSM8v4fWmD9nPCpVoyOF4lF9kU37hL5hCf6wzovU+w+TXgQfMbAnwElAGdAT53A/p75nivN704y6hrKpq6NfPCzdeb3rE53A8yi+yKb/wcbwPpGAKfSlQGHC/ACgPHOCcKwf+HsDM0oBPO+fqzawUuKjXczcEE7SIiAyNYAr9RmCqmU3GN1NfCFwbOMDMsoFa51wX8B/4VuAArAO+E7AD9nL/4yIiMkJOuDPWOdcB3ISvaG8H1jjntprZcjNb4B92EeDM7D1gPPBt/3NrgW/h+7DYCCz3bxMRkRES093drws6Dbv+XmGqp4e2Z9lttJeWHt2eUFDA5GV3DXl8Iy2SeoQDofwim/ILH1F9hSngb4o8QHtpKXuW3dbHM0RERo+oKPS9i/yJtouIjCZRUehFRKRvKvQiIlEuKgp9QkFBv7aLiIwmUVHoJy+762+KerSsuhERGayouMIUoKIuItKHqJjRi4hI31ToRUSinAq9iEiUU6EXEYlyKvQiIlFOhV5EJMqp0IuIRDkVehGRKKdCLyIS5VToRUSinAq9iEiUU6EXEYlyKvTDoKWtg+37K2lp6wh1KCIi0XP2ynDR0tbBsv99nsP5L+B54xSWfmwhGSmpoQ5LREaxoAq9mc0H7gfigBXOubt7PT4RWAVk+Mfc6pxba2aJwM+AWUAX8K/OuQ1DF374Katuorr5EImd8bSOc9y18QcsmHI5M7NncqC2hfzsVDyJ+nwVkZFzwtaNmcUBDwJXAkXAIjMr6jXsNmCNc+5sYCHwkH/7lwCcczOAy4B7zSyq20X52amMT5hIS/E8PDVFdNHBb997gls3fI/v/unPLF+1US0dERlRwUwtZwM7nXO7AcxsNXA1sC1gTDcwxn97LFDuv10EPAfgnKs0s0P4Zvd/HXzo4cmTGM/ti2dRVt1EfnYq7bTw6Lt/ZnPdWyRN3UxNzQHKqouYMmFsqEMVkVEimEKfD+wPuF8KzOk1Zhmw3sxuBlKBS/3btwBX+z8cCoGZ/v/3WegzM1OIj48LKvgeXm96v8aPhML8zKO3v5a9hH99IJualM1kdBVy5mm5JCfFc6ipmYPVLUzMHUNyUt9vRTjmN5SUX2RTfuEvmEIfc4xt3b3uLwJWOufuNbO5wMNmNh34JTAN2ATsA14Fjtu3qKtrDiKkD3i96VRVNfTrOaFw+8ILKauexYSsFBoPH6GkuYGlf/k+bQfz8bacxe2LZx2zdx8p+Q2U8otsyi98HO8DKZhCX4pvFt6jgA9aMz1uBOYDOOdeMzMPkO2cqwS+2jPIzF4F3g8u7OjiSYz/ULvGHSinsyMOOhOoqGmmrLpJ7RwRGRbB7BjdCEw1s8n+VTQLgSd7jSkBLgEws2mAB6gysxQzS/VvvwzocM5tQzi7YAqZZZfTcfAk8rJSGD8uiR+99VNeKd3IzrJD2mErIkPmhDN651yHmd0ErMO3dPKXzrmtZrYc2OScexK4BfiFmX0VX1tniXOu28xygHVm1gWUAdcPWyYRxpMYz9LFs4/utN3fVMKe+hLeP7SbrqYxpB86k+WfuzLUYYpIFIjp7u7dbg+tqqqGfgUUST20E3l7Xwk/feMx4rMrADg5bSo3z7uWxNboPeAqmt6/Y1F+kS2S8vN604+1PxXQKRDCyrS8CWTXz6Vl61zijmSzu/F9bnn6W/xm+2O8U1Kudo6IDIgO0QwjgWvwJ2R9nPcOv8eTe57i1Yo3eKVzE8lvnMayj3+W9OTkUIcqIhFEM/ow07M6JzkpgTO9p/Plopto2zsNumJpydrKdzfdR1tne6jDFJEIokIf5iZPyCSncxotxReQVHcqZ3pPJzEugZa2DnaUVqudIyInpNZNmEtOCjylwiV4EuNpaetg+aqN1Oa8gCcmhbsu/zJpHk+oQxWRMKUZfQToaef0HDlbVt3EgUP1ALS0dXKwttV/u4Nd5fWa5YvIh2hGH4Hys1PJy8igYvsccrMTyc9OpaWtg/9Y+3Ma6zx4O05j6eLZOh2yiAAq9BGp9xkyPYnxFJeU0ZpSSuKYDupaSnhpTwKXnTqLmJg+l9aKyCih1k2E6t3OOTV3PGP3X0HHwYnEJh3hj2W/48dv/5xdtSVq54iMcprRRwlPYjx3XH8+ZdVnEZ/SxNp9T/NuzQ5++PYDdFTnM67pDO64bp7aOSKjkGb0UaRnln9SxgS+cuY/8OnCRXQdSSPeW0Z94Xoe27FOa/BFRiEV+ij2dyfNILPiMtr2nE5sdzyvVr/I8td/QPnhKrVzREYRfY+PYr4zZJ5LWXURWRlxbCh/ifcP7eGB3+7kQM0RcrOSWbr4XLVzRKKcZvRRrqedk5GSxidP+RifzLuWAzVHAKhOeZtfFP+Gpvb+XdVLRCKLCv0oU+hNJy8rBejGk3mYytZyEmMTAB1wJRKt9J19lAlcg5+XNY8jXU0k+M+dc9sffk99QzteTlFLRySK6C95FAq8fm0KiQCUVB2mOWMriTmt1DWWsLFkDPNOOT2UYYrIEFHrRgCY6B3D2IqL6ajJJTatntUlq/jV1v+l4nC12jkiEU4zegH8B1x9/gLKqmfSlljNk3v+j00HN7Op4h3aKyaR3Xo6S284T+0ckQikGb0c1dPSmZY9hW/Mupkr8j5Bd0c8Cfm7qMtfz7O73iDcrjEsIiemQi/HFBsTy+VT5pJRegXt5ScTm9DGUxV/5N43H2J//QG1c0QiSFDfw81sPnA/EAescM7d3evxicAqIMM/5lbn3FozSwBWAOf4X+vXzrnvDmH8Mow8ifEsveE8yqpn4Elr5al969he+z4PPbaDg5Vd5GWlcPviWWrniIS5E87ozSwOeBC4EigCFplZUa9htwFrnHNnAwuBh/zbrwGSnHMzgJnAP5nZpCGKXUZATzsnf0wOX5xxPTdM/kcOVnYBcLBzL4+7Z2jX+XNEwlowrZvZwE7n3G7nXBuwGri615huYIz/9ligPGB7qpnFA8lAG3B40FFLyFhu7tEDrlIm7uG16peobT2kg61Ewlgw37nzgf0B90uBOb3GLAPWm9nNQCpwqX/77/F9KFQAKcBXnXO1x3uxzMwU4uPjggjrA15ver/GR5pwy+/+Wy6m5MBhssZ9lL2H9zIleyJf+9GLlDWUM35cKj/+fwtITgq+nRNu+Q015RfZoiG/YP4aj3WJot5LLxYBK51z95rZXOBhM5uO79tAJzAByAReNrNnnXO7+3qxurr+nXfF602nqqqhX8+JJOGa37iUBLpb4KTEyWzZcYDSygaSit7lUGoD922o49oZHyc1IeWEPydc8xsqyi+yRVJ+x/tACqZ1UwoUBtwv4IPWTI8bgTUAzrnXAA+QDVwLPO2ca3fOVQKvALOCjlwiQn52KnlZqbSXTSWuPZXNhzZx5+vf5/l9f+H9sjq1c0RCLJgZ/UZgqplNBsrw7Wy9tteYEuASYKWZTcNX6Kv82z9qZo/ga92cB/xoiGKXMPHB+XOmMX7c1bxe+QZr9zzLY7uepKv5BdLrzmL5567U6hyREDnhjN451wHcBKwDtuNbXbPVzJab2QL/sFuAL5nZFuBRYIlzrhvfap004F18Hxi/cs4VD0MeEmI9q3PSPB4unXghSyZ/mY6qfGKSG2jKf5mfbXmYmiN1oQ5TZFSKCbcjHauqGvoVUCT10AYiUvNraevgW6s2caClgtQpjk5PLQmx8VxccCHmmcmknAw8ifERm1+wlF9ki6T8vN70Y+1PBXSuGxkmHz4d8lW8U/sOj+9cy/qS5/jT9gbGJxZw+2LtrhEZCSr0MmwCT4c8J28mYzoK+eHT6+hqGEcFzWyvKIe0I3iI/OVrIuFM57qRETN5/DhymApAXlYKbxx6nm+s+zbv1+7TwVYiw0gzehkxge2c/OxUdh4ey5iUNH71WDkHanaRm53EbdefS0pSYqhDFYkqmtHLiOpp53gS45mePY35+VcfvVh5Terb3PPmg+ypLwlxlCLRRYVeQmpi7pij585JToGDLRXc8+YDrHx3NcUlZWrniAwBtW4kpJKTAts5F1LavJ/fuifYWPkWfy0vJvn1IpYvuIZUT1KoQxWJWJrRS8gFtnNOyZjMZwuW0La3CIihJbuY7236Ma52Z6jDFIlYKvQSdgq96eR0nkZL8TwS6ydR21bNjzf/nJ8X/5rN+/arnSPST2rdSNj58OqcS6lsOcBq9zhbqt9l88HtpL/0Ee783BU6d45IkDSjl7AU2M6ZOKaAv59wPW27p9PVnE5VeSJl1U26ULlIkDQlkohQ4E0jp/tUKrbnk5eVSn52Ks/tf4n3andzfuZlWF6uZvgifdBfhkSE3gdbJSXE4Wp2sb16N5ueySMvo1QXKhfpg1o3EjEC2zkxMTFckfP3HHn3POhMpKKmmZf3buad6m2hDlMk7Gj6IxGrwJtGblo2Fa3N5GZ5eLFqPXWlh5iWaczNvITTJxRohi+CCr1EsN7tnLr2Kaze8Tjb6xzbat7Hs+lU7rxqEenJyUPyej+5e0Ofj33l1ouG5DVEhoNaNxLRAts5eanj+UTuQtp2ngkdCbSO28F3Nv1Q7RwZ9TSjl6hS4E0jJ2YKFcVeMqbso3HcLn5avFLtHBnV9BsvUeXD7ZyPUtde86F2TvImY9nHF5LuGZp2jkgkUOtGos7x2jlHMnbgDlSEOkSREaUZvUS9wHZOdn4z0y+YCMCeulIOHe5iWt4EtXMkqgX1221m84H7gThghXPu7l6PTwRWARn+Mbc659aa2eeBbwQMPQM4xzm3eSiCFwlG79U5nsR4mlvbuO/1VXTENzL2ucu547p5KvYStU74m21mccCDwGVAKbDRzJ50zgUuZbgNWOOc+4mZFQFrgUnOud8Av/H/nBnAH1XkJRQCL1QOUF7dzJHSicSkNHCwspuy6iYm5qaSENv3n4SWUEqkCmYKMxvY6ZzbDWBmq4GrgcBC3w2M8d8eC5Qf4+csAh4deKgiQ6fAm0YOU6nY30xeVgoTslL4+TurSIxJZPbYi3XuHIkqwfwm5wP7A+6XAnN6jVkGrDezm4FU4NJj/JzP4fuAOK7MzBTi4+OCCOsDXm96v8ZHGuU3PO6/5WJKDhxmYu4YumPaad3WyrY6x9sHt5G6cToPLPkCacmDv7KV3r/IFg35BVPoY46xrff5YRcBK51z95rZXOBhM5vunOsCMLM5QLNz7t0TvVhdXXMQIX3A602nqqqhX8+JJMpveI1LSaDxsO/i5AtyruV7b/2RhML3aB63hW+u+w6Lp3+Gk8dOGvDPD3V+w035hY/jfSAFs7yyFCgMuF/A37ZmbgTWADjnXgM8QHbA4wtR20bCXIE3jZwu813Z6vBJVLdWcu+bD7Fq6xreLanQla0kYgUzo98ITDWzyUAZvqJ9ba8xJcAlwEozm4av0FcBmFkscA1wwVAFLTIcel/Zqqy5lEd3/IG/HtzEG2VbSHl1Bv/47NN/87xTV6wc+WBF+uGEM3rnXAdwE7AO2I5vdc1WM1tuZgv8w24BvmRmW/DN3Jc453raOxcApT07c0XCWeDBVlMyJvG5wi/Qtu80iOnii8co8gDvfXHJyAYp0k9BLStwzq3Ft2QycNvSgNvbgPP7eO4G4LyBhygSOoXedHI6iqgoziXG150UiTg6BYLIcfS0c/5r0fnHXJUgEglU6EVOoPfBViKRRoVeZIjsqN6NK63R6hwJOyr0IkHqa3XNqStWUn64iv/e/At+tOUB7vjtUyr2ElZ0jLdIP/RV7Ovqu+ioyicup4TG/Jf5n+J6bjjjk3iJ/KMqJfJpRi8yBKaMzyK7cRat284jrnUs2w4Xs/z1H/CUe4mdZYc0w5eQ0oxeZAgEHmyVm3UVf63cyJ92P82vNj9KZ0MGGYdmsmzRJTpRmoSEZvQiQ6RndU5qUhIXF36EGyb9E52144lLP8Th/OdZve1PtHW2hTpMGYVU6EWGyWl5eeQcnkerO4fYzmQ21r7GfW/9lCOt7ewqr1c7R0aMvkeKDBNPYjw//LcL2bLDyM5cwAtlG8hOyuauX79JRU0zuVnJLF18rto5Muw0oxcZRslJvnbO2OQUPnnKx8iLMypqmiGunboJ63lq519CHaKMAir0IiMoPzuVvKwUYpMbiU1sIy6xFYCWtg61c2TY6DujyAj6YHXONNLHfJTMlHRa2jpYvuqvVCdsJ7vDWHrDeWrnyJDSjF5khPWszslJyyQhNp6y6iaq4hwJEx11+et5ee+WUIcoUUaFXiTE8rNT8XZNpb38ZGITW3mi9LesePcRKhtr1c6RIaHvhyIh5kmMZ+kN51FWPYPY5AYe2/VH3q4s5u2K7bSVTMXbZVqdI4OiGb1IGOhp50zOLOBrM7/CpeOvpLu7m8TJ26jNeYEtZXtDHaJEMBV6kTATGxPLlVPnMbb0MjpqcolLP8Rv9v4Pj7+/lh2l1WrlSL/pu6BIGPIkxnPHdfMoqz6H+tj9/GHXkzy7fwNPVezD23w2ty+epVaOBE2/KSJh6oMrW40luWM89214jI4Dk6joaKa0qpH88R6S4z2hDlMigFo3IhFgck4m3iNnQUcieVkp1MbsZdlr32PLwe1amSMnFNSM3szmA/cDccAK59zdvR6fCKwCMvxjbnXOrfU/dgbwM2AM0AWc65xrGbIMREaBwNMg52en8mb1m3R1d/HoU6VUHqggLytF7Rzp0wln9GYWBzwIXAkUAYvMrKjXsNuANc65s4GFwEP+58YDjwBfds6dDlwEtA9Z9CKjSE8rx5MYz/kT5nDjyTdReSAOgAMt5TzhnqWzqzPEUUo4Cubjfzaw0zm3G8DMVgNXA9sCxnTjm7EDjAXK/bcvB4qdc1sAnHM1QxG0iMCknEzyslKoqGkmbfIuXq6qYu+mHXz6lE8R25JBfnaqZvgCBFfo84H9AfdLgTm9xiwD1pvZzUAqcKl/+6lAt5mtA7zAaufc9wcVsYgAH27nZIydxdp9T/P6gU386O0HaT8wiewjZ+i8OQIEV+hjjrGtu9f9RcBK59y9ZjYXeNjMpvt//keAc4Fm4Dkze9M591xfL5aZmUJ8fFxw0ft5vdF9AWblF9mGO7/C/EwATpt0I2uLz+CXb68mIW8vda0HKa4ex1Vn9p6XDS29f+EvmEJfChQG3C/gg9ZMjxuB+QDOudfMzANk+5/7onOuGsDM1gLnAH0W+rq65qCDB9+bUFXV0K/nRBLlF9lGOr8ZWaeQWX4Z1Z5iEvL2smrHSrYfKubTp3yCtMTUIX89vX/h43gfSMEU+o3AVDObDJTh29l6ba8xJcAlwEozmwZ4gCpgHfBNM0sB2oALgfv6m4CIBMd33pw5lFVPB089v9/1OH898BZbq3dwgfcyLjl5NslJCaEOU0bYCVfdOOc6gJvwFe3t+FbXbDWz5Wa2wD/sFuBLZrYFeBRY4pzrds7VAT/E92GxGXjLOffn4UhERHx6VudMGTeRr8+8iQWTP0ZTWytPVfyRZauf1Zr7USiovTT+NfFre21bGnB7G3B+H899BN8SSxEZYXGxcZySdDYtxY3EZlZSdTCJsuomJuQkkhSXRGyMjpkcDbQ7XiTK5WenkpueTcXBFPKyUpiQlcLKrY9wuK2Rq3Kv4ZTx2VqZE+X07opEud5H1cbFdZMQm0D5wVZ++NxW8rJSdVRtlNP3NpFRIPCo2oS4BC7O+gQNW88EYqioaeYJ9yy76/eFOkwZJvoIFxmF8rNTyRuXTkVNMznju3mlagN/qXqB8/PO46z0jzA5J1Mz/Ciid1JkFOrdziltPplHtv+Ov1S8xkt73ya95hyWf/bjKvZRQq0bkVEqsJ1zSsZkFhXeSHvZycQktNI04VX+p/hRGtubQh2mDAEVehEB4KScsXhbzqJ161ziWjLYdvgd7nr9Xt4of5udZYe0/j6C6XuZiAAfbufkZl3Jqwde4//2rOfXOx6lsy6HzPqZ3HHdPLVzIpBm9CJyVE87JzUpictOuojrJ32JzsOZxGVWcij7VUqrGkMdogyAPppFpE/TJxQy7pmLqKpxjEvMpsCbBkDDkSNU1rWRNiY5xBFKMFToRaRPnsR4li4+l7LqoqMXMik/XMV3Xv8xrftPIe/pafzndeeonRPm1LoRkeMKXJ0D4A6W0dXdBV2xlFY2UlatlTnhToVeRPpl7knTGVt6BZ01EyjISWNcRhzPl7xEU0sru8rrtTonDOn7loj0iycxnjuu/zvKqps487Rcfv3m73hu/0s8sfVlmt4/ndzkXJ07J8xoRi8i/dbTzklOimf+pI9y+tgz6EyqJ6noNao8W9hXWR/qECWACr2IDEpKQgr/MGMhqeXn092eREL+LtaU/oq9h0tCHZr46buViAyaJzGe5Z+9it0H5/J2w8u8euAN7tn0IBfmf4QZqXOZlJOhVk4I6V9eRIaEJzGeosIcivg05+adxSPbf8eGspd5/sibjKk9lzs/d4WKfYiodSMiQ+7UzClcO/FGOg6cRIynmYYJL/Ly3s2hDmvUUqEXkWExKSeT7KaZtG2fQ2LTBOZOnA5AS1uHlmGOMH2PEpFh8cFJ0qYdPaq2pa2D/3riURo768lqOoulN5ynds4ICOpf2MzmA/cDccAK59zdvR6fCKwCMvxjbnXOrTWzScB2wPmHvu6c+/IQxS4iYa5nGWaP/VUNNHv2EZfUwoEy31G1gY/L8DhhoTezOOBB4DKgFNhoZk8657YFDLsNWOOc+4mZFQFrgUn+x3Y5584a2rBFJBIVetPJPHgxB5uryRubQX52Ku/X7qO9KZmTx4/T7H6YBPOvOhvY6ZzbDWBmq4GrgcBC3w2M8d8eC5QPZZAiEh18J0mbc/QShk3tzdy/aQWdnTGkvziT5Z+9SsV+GASzMzYf2B9wv9S/LdAy4DozK8U3m7854LHJZva2mb1oZvMGE6yIRL7Ak6TVHOqg7WCB//KFr7DynTUc6WgJdYhRJ5iPzphjbOvudX8RsNI5d6+ZzQUeNrPpQAUw0TlXY2YzgSfM7HTn3OG+XiwzM4X4+Lhg4wfA603v1/hIo/wim/LrW9qYZHLXnU3ZtvGknrqVd+o3891N+/jCWYsY25XPxNwxJCeFdoYfDe9fMP+CpUBhwP0C/rY1cyMwH8A595qZeYBs51wl0Orf/qaZ7QJOBTb19WJ1dc3BR4/vTaiqaujXcyKJ8otsyu/E/vO6cyirNsaPm8+G8pdYt+957nn1IToqC8hqPJulN8wNWTsnkt6/430gBdO62QhMNbPJZpYILASe7DWmBLgEwMymAR6gysy8/p25mNnJwFRgd78zEJGo1dPKSfN4+PjJl3PtSV+gqzmd+JxS6vKf4dV974Q6xIh3wkLvnOsAbgLW4VsqucY5t9XMlpvZAv+wW4AvmdkW4FFgiXOuG7gAKPZv/z3wZedc7XAkIiLR4eyCKWRWXEJ72RRiE1t5bP+jrHnviVCHFdFiurt7t9tDq6qqoV8BRdJXq4FQfpFN+Q1MS1sHZdVNdHvqWbPzMc72nsHF+RceXa0zUq2cSHr/vN70Y+1PBXRkrIiEoQ8OtBrLN2fdTGtbJ99atYmK2kYyTy7l9quuISMlNdRhRgyd60ZEwlp8bDwHaluoqGkmzruflqxt/OG9p0MdVkRRoReRsJefnUpeVgqdVYV4aor41KmXA3CktR1XWqMTpJ2AWjciEvY+OEFaE/nZFx09QdrSPzxB49h3GVNzLnd+br6Oqu2DZvQiEhECj6gFKKtuor7tEDFJR2iY8BK/2foEbZ3tIY4yPKnQi0hEys9Oxds2g7btc4hrT+Otur/y3Y334ap363z3veh7johEpMDz3Xszr2R96bNs2P8KP97yU9orJpN95AyWLp6jdg6a0YtIBOtp54xJTuEzUxdwzcTr6GpNJmHCHurynuOt0p2hDjEsqNCLSNSYM3EameWX0XGwkNiURh7dt5I/73mGppbWUd3O0XcaEYkansR4lt5wHmXVM2iMK2fNzj+wft8LvLwhhsqDseRlpXD74lmjrp0zurIVkagXeFTt1HFf47W9O/jN63UAVByuZX9VA1PzM0Mb5AhT60ZEolZKQjLnnzSDvKwUiOkk9fQ3+WPF/9LRNbpaOJrRi0hU61mds/tgDX+pqyDDM4b42PijJ04byZOkhUp0Zycigq/YFxWOZ1rB9XR1d9HS1sHyVRup9hST1T6VO667IKqLvVo3IjJqxMTEEBcbR1l1E5Wd+0jI30V9wbM8s+t1wu2U7UNJhV5ERp387FRy4k6ibc/pxMTC0xVP8rPiVbxTUh6VSzCj97uKiEgfPInxLF18LmXVRXjSWln93u95p2YbxQd2kvbyOSy/ZkFUtXI0oxcmLaRgAAAHdklEQVSRUalnGWb+mByuzruWtn2nQVwHTXmv88t3VnOk40ioQxwyKvQiMuoVeNPI6Sii9d2/I64lg631xXz7jft4q3RbVBxRGz3fTUREBijwfPe5465gQ/mLPL33ee5+5b9p21NETtdpEX1ErWb0IiJ80MpJ9SRx1cmXs/CkxXQ1jqWr3ktFTTNl1U2hDnHAVOhFRI5hZuFUsqsvpbstmbysFPKzI/di5EF9DzGz+cD9QBywwjl3d6/HJwKrgAz/mFudc2t7Pb4NWOacu2eIYhcRGTaexHju+7eL2LLjwLAePfuTuzf0+dhXbr1oSF7jhDN6M4sDHgSuBIqARWZW1GvYbcAa59zZwELgoV6P3wc8NfhwRURGTnLShy9fGKmCad3MBnY653Y759qA1cDVvcZ0A2P8t8cC5T0PmNkngd3A1sGHKyIi/RXMx1Q+sD/gfikwp9eYZcB6M7sZSAUuBTCzVODfgcuArwcTUGZmCvHxccEMPcrrTe/X+Eij/CKb8otsocxvqF47mEIfc4xtvU8KsQhY6Zy718zmAg+b2XTgTuA+51yjmQUVUF1dc1Djeni96VRVNfTrOZFE+UU25RfZQp1ff177eB8KwbRuSoHCgPsFBLRm/G4E1gA4514DPEA2vpn/981sL/BvwH+a2U1Bxi0iIkMgmBn9RmCqmU0GyvDtbL2215gS4BJgpZlNw1foq5xz83oGmNkyoNE598BQBC4iIsE5YaF3znX4Z+Hr8C2d/KVzbquZLQc2OeeeBG4BfmFmX8XX1lninIvec36KiAyRoVpCeTwx4XYO5qqqhn4FFOoe2nBTfpFN+UW2SMrP600/1v5UQEfGiohEPRV6EZEop0IvIhLlVOhFRKKcCr2ISJSL7DP1iIhEgfe+uORvtp26YuWQ/XzN6EVEQuhYRf542wdChV5EJMqp0IuIRDkVehGRKKdCLyIS5VToRURCqK/VNUO56kbLK0VEQmwoi/qxaEYvIhLlVOhFRKKcCr2ISJRToRcRiXIq9CIiUS7sLiUoIiJDSzN6EZEop0IvIhLlVOhFRKKcCr2ISJRToRcRiXIq9CIiUU6FXkQkyoXt2SvNbD5wPxAHrHDO3d3HuM8AvwPOdc5tCtg+EdgGLHPO3TMCIffLYPIzszOAnwFjgC7/Yy0jEng/DDRHM0sAVgDn4Psd/bVz7rsjFHbQTpSfmS0BfgCU+Tc94Jxb4X9sMXCbf/tdzrlVIxJ0Pww0PzM7C/gJvt/PTuDbzrnfjljgQRrM++d/fAywHXjcOXfTiAQ9QGE5ozezOOBB4EqgCFhkZkXHGJcO/AvwxjF+zH3AU8MZ50ANJj8ziwceAb7snDsduAhoH4Gw+2WQ7+E1QJJzbgYwE/gnM5s07EH3Q7D5Ab91zp3l/6+nyI8D7gDmALOBO8wsc4RCD8pg8gOagRv8v5/zgR+ZWcaIBB6kQebX41vAi8Mc6pAIy0KP75d/p3Nut3OuDVgNXH2Mcd8Cvg98aDZrZp8EdgNbhzvQARpMfpcDxc65LQDOuRrnXOdwBzwAg8mxG0j1f6glA23A4WGOt7+Cze9YrgCecc7VOufqgGfwFcRwMuD8nHPvOefe998uByoB77BFOjCDef8ws5nAeGD9MMU3pMK10OcD+wPul/q3HWVmZwOFzrn/67U9Ffh34M7hDnIQBpwfcCrQbWbrzOwtM/vm8IY6YIPJ8fdAE1ABlAD3OOdqhzHWgThhfn6fNrNiM/u9mRX287mhNJj8jjKz2UAisGt4whywAednZrHAvcA3hj/MoRGuhT7mGNuOnpTH/w99H3DLMcbdCdznnGscptiGwmDyiwc+Anze//9PmdklwxHkIA0mx9n4ersTgMnALWZ28nAEOQjHzc/vT8Ak59wZwLNATx8+mOeG2mDyA8DM8oCHgS8457qGJcqBG0x+/wysdc7tJ0KE687YUiBwdlAAlAfcTwemAxvMDCAXeNLMFuDre37GzL4PZABdZtbinHtgRCIPzmDyKwVedM5VA5jZWnw7LZ8bgbj7YzA5Xgs87ZxrByrN7BVgFr52XLg4UX4452oC7v4C+F7Acy/q9dwNQx7h4Awmv54dlX8GbnPOvT6McQ7UYPKbC8wzs38G0oBEM2t0zt06jPEOSrgW+o3AVDObjG+P90J8f/wAOOfqgeye+2a2Afi6f1XKvIDty4DGMCvyMIj8zGwX8E0zS8HXu74Q38w43Awmx0uAj5rZI0AKcB7woxGMPRjHzQ98M1rnXIX/7gJ8KzQA1gHfCdgBeznwH8Mfcr8MOD8zSwQex7da6ncjF3K/DDg/59znA8YsAWaFc5GHMG3dOOc6gJvw/UFsB9Y457aa2XL/jC+iDSY//867H+L7Rd0MvOWc+/Nwx9xfg3wPH8Q3U3oXX56/cs4VD2vA/RRkfv9iZlvNbAu+lUVL/M+txbcTeqP/v+Xhtg9iMPkBnwUuAJaY2Wb/f2eNcArHNcj8Io7ORy8iEuXCckYvIiJDR4VeRCTKqdCLiEQ5FXoRkSinQi8iEuVU6EVEopwKvYhIlPv/YCWwONfYoJ4AAAAASUVORK5CYII=\n",
      "text/plain": [
       "<Figure size 432x288 with 1 Axes>"
      ]
     },
     "metadata": {
      "needs_background": "light"
     },
     "output_type": "display_data"
    }
   ],
   "source": [
    "def g1(theta):\n",
    "    return np.array([np.cos(theta), \n",
    "                     np.sin(theta)])\n",
    "\n",
    "def g2(theta):\n",
    "    return np.array([np.cos(theta),\n",
    "                    np.cos(theta - np.pi/2)])\n",
    "\n",
    "theta = np.linspace(1, 1.1)\n",
    "plt.plot(*g1(theta), '.')\n",
    "plt.plot(*g2(theta), '-.')\n",
    "plt.plot(*g1(theta + np.pi*1e14), 'o')\n",
    "plt.plot(*g2(theta + np.pi*1e14), 's');"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Can you explain the plot above?  Is there evidence that one of these functions (`g1` or `g2`) is backward stable?"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Numerical Linear Algebra\n",
    "\n",
    "If $u$ and $v$ are vectors and I propose a function $h(u, v)$, can you determine whether it is an inner product?\n",
    "\n",
    "There are two Moodle quizes about projections and matrix transformations.  If I ask a similar question, can you understand the terminology and show whether a property is true?\n",
    "\n",
    "Is an orthogonal projector an orthogonal matrix?\n",
    "\n",
    "If $Q$ has orthonormal columns, is $Q^T Q = Q Q^T$?  What if $Q$ is square?"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "3.3422138886441676e-16"
      ]
     },
     "execution_count": 5,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "def factor(A):\n",
    "    A = A.copy()\n",
    "    n = len(A)\n",
    "    for i in range(n):\n",
    "        ai = 1/A[i, i]\n",
    "        A[i+1:, i] *= ai\n",
    "        A[i+1:, i+1:] -= np.outer(A[i+1:, i], A[i, i+1:])\n",
    "    return np.tril(A, -1) + np.eye(n), np.triu(A)\n",
    "\n",
    "A = np.random.randn(4, 4)\n",
    "L, U = factor(A)\n",
    "np.linalg.norm(L @ U - A)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Which line in the above function is most expensive?\n",
    "\n",
    "How much does it cost on the first iteration?\n",
    "\n",
    "Can you write a sum of the cost over all loop iterations?\n",
    "\n",
    "Can you write a $2\\times 2$ matrix such that the above code fails?\n",
    "\n",
    "Given a collection of vectors, how can you use QR factorization to build an orthogonal basis that spans the same space and where all but one vector has mean zero?\n",
    "\n",
    "Given a matrix $A$, can you devise an elementary reflector $F = I - 2 v v^T$ such that the first column of the product $F A$ is a constant vector (all entries the same)?"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "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.7.2"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}