{
  "cells": [
    {
      "cell_type": "markdown",
      "metadata": {},
      "source": [
        "# Rates of Convergence"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": 1,
      "metadata": {
        "collapsed": false
      },
      "outputs": [],
      "source": [
        "import numpy as np"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": 2,
      "metadata": {
        "collapsed": false
      },
      "outputs": [],
      "source": [
        "C = 1/2\n",
        "e0 = 0.1*np.random.rand()\n",
        "\n",
        "rate = 1"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": 3,
      "metadata": {
        "collapsed": false
      },
      "outputs": [
        {
          "name": "stdout",
          "output_type": "stream",
          "text": [
            "0.00216056864310018\n",
            "0.00108028432155009\n",
            "0.000540142160775045\n",
            "0.0002700710803875225\n",
            "0.00013503554019376126\n",
            "6.751777009688063e-05\n",
            "3.3758885048440315e-05\n",
            "1.6879442524220158e-05\n",
            "8.439721262110079e-06\n",
            "4.219860631055039e-06\n",
            "2.1099303155275197e-06\n",
            "1.0549651577637599e-06\n",
            "5.274825788818799e-07\n",
            "2.6374128944093996e-07\n",
            "1.3187064472046998e-07\n",
            "6.593532236023499e-08\n",
            "3.2967661180117495e-08\n",
            "1.6483830590058748e-08\n",
            "8.241915295029374e-09\n",
            "4.120957647514687e-09\n"
          ]
        }
      ],
      "source": [
        "e = e0\n",
        "for i in range(20):\n",
        "    print(e)\n",
        "    e = C*e**rate"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {},
      "source": [
        "* What do you observe about the number of iterations it takes to decrease the error by a factor of 10 for `rate=1,2,3`?\n",
        "* Is there a point to faster than cubic convergence?"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {},
      "source": [
        "------------------\n",
        "Now let's see if we can figure out the convergence order from the data.\n",
        "\n",
        "Here's a function that spits out some fake errors of a process that converges to $q$th order:"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": 4,
      "metadata": {
        "collapsed": false
      },
      "outputs": [],
      "source": [
        "def make_rate_q_errors(q, e0, n=10, C=0.7):\n",
        "    errors = []\n",
        "    e = e0\n",
        "    for i in range(n):\n",
        "        errors.append(e)\n",
        "        e = C*e**q\n",
        "        \n",
        "    return errors"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": 5,
      "metadata": {
        "collapsed": false
      },
      "outputs": [],
      "source": [
        "errors = make_rate_q_errors(1, e0)"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": 6,
      "metadata": {
        "collapsed": false
      },
      "outputs": [
        {
          "name": "stdout",
          "output_type": "stream",
          "text": [
            "0.00216056864310018\n",
            "0.001512398050170126\n",
            "0.0010586786351190881\n",
            "0.0007410750445833616\n",
            "0.0005187525312083531\n",
            "0.00036312677184584713\n",
            "0.00025418874029209295\n",
            "0.00017793211820446505\n",
            "0.00012455248274312553\n",
            "8.718673792018786e-05\n"
          ]
        }
      ],
      "source": [
        "for e in errors:\n",
        "    print(e)"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": 7,
      "metadata": {
        "collapsed": false
      },
      "outputs": [
        {
          "name": "stdout",
          "output_type": "stream",
          "text": [
            "0.7\n",
            "0.7\n",
            "0.7\n",
            "0.6999999999999998\n",
            "0.7\n",
            "0.6999999999999998\n",
            "0.7\n",
            "0.7\n",
            "0.7\n"
          ]
        }
      ],
      "source": [
        "for i in range(len(errors)-1):\n",
        "    print(errors[i+1]/errors[i])"
      ]
    }
  ],
  "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.5.1+"
    }
  },
  "nbformat": 4,
  "nbformat_minor": 0
}