{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Example of fixed point iteration"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Consider finding roots of\n",
    "$$\n",
    "f(x) = x^2 - a, \\qquad a > 0\n",
    "$$\n",
    "using following fixed point maps\n",
    "\\begin{eqnarray*}\n",
    "x &=& x + c(x^2 - a) \\\\\n",
    "x &=& \\frac{a}{x} \\\\\n",
    "x &=& \\frac{1}{2}\\left( x + \\frac{a}{x} \\right)\n",
    "\\end{eqnarray*}"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "     0   2.0000000000e+00   2.0000000000e+00   2.0000000000e+00\n",
      "     1   2.1000000000e+00   1.5000000000e+00   1.7500000000e+00\n",
      "     2   2.2410000000e+00   2.0000000000e+00   1.7321428571e+00\n",
      "     3   2.4432081000e+00   1.5000000000e+00   1.7320508100e+00\n",
      "     4   2.7401346820e+00   2.0000000000e+00   1.7320508076e+00\n",
      "     5   3.1909684895e+00   1.5000000000e+00   1.7320508076e+00\n",
      "     6   3.9091964797e+00   2.0000000000e+00   1.7320508076e+00\n",
      "     7   5.1373781913e+00   1.5000000000e+00   1.7320508076e+00\n",
      "     8   7.4766436594e+00   2.0000000000e+00   1.7320508076e+00\n",
      "     9   1.2766663700e+01   1.5000000000e+00   1.7320508076e+00\n",
      "    10   2.8765433904e+01   2.0000000000e+00   1.7320508076e+00\n"
     ]
    }
   ],
   "source": [
    "a = 3.0\n",
    "c = 0.1\n",
    "x1, x2, x3 = 2.0, 2.0, 2.0\n",
    "print(\"%6d %18.10e %18.10e %18.10e\" % (0,x1,x2,x3))\n",
    "for i in range(10):\n",
    "    x1 = x1 + c*(x1**2 - a)\n",
    "    x2 = a/x2\n",
    "    x3 = 0.5*(x3 + a/x3)\n",
    "    print(\"%6d %18.10e %18.10e %18.10e\" % (i+1,x1,x2,x3))\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The first iteration diverges, the second oscillates while the last (Newton method) converges."
   ]
  }
 ],
 "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.6.6"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 1
}