{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Compute fixedpoint of $f(x) = x^{0.5}$\n",
    "\n",
    "**Randall Romero Aguilar, PhD**\n",
    "\n",
    "This demo is based on the original Matlab demo accompanying the  <a href=\"https://mitpress.mit.edu/books/applied-computational-economics-and-finance\">Computational Economics and Finance</a> 2001 textbook by Mario Miranda and Paul Fackler.\n",
    "\n",
    "Original (Matlab) CompEcon file: **demslv03.m**\n",
    "\n",
    "Running this file requires the Python version of CompEcon. This can be installed with pip by running\n",
    "\n",
    "    !pip install compecon --upgrade\n",
    "\n",
    "<i>Last updated: 2022-Sept-04</i>\n",
    "<hr>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## About\n",
    "\n",
    "Compute fixedpoint of $f(x) = x^{0.5}$ using Newton, Broyden, and function iteration methods.\n",
    "\n",
    "Initial values generated randomly. Some alrorithms may fail to converge, depending on the initial value. \n",
    "\n",
    "True fixedpoint is $x=1$."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "import numpy as np\n",
    "import pandas as pd\n",
    "from compecon import tic, toc, NLP"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Randomly generate starting point"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "xinit = np.random.rand(1) + 0.5"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Set up the problem"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def g(x):\n",
    "    return np.sqrt(x)\n",
    "\n",
    "problem_as_fixpoint = NLP(g, xinit)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Equivalent Rootfinding Formulation"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def f(x):\n",
    "    fval = x - np.sqrt(x)\n",
    "    fjac = 1-0.5 / np.sqrt(x)\n",
    "    return fval, fjac\n",
    "\n",
    "problem_as_zero = NLP(f, xinit)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Compute fixed-point using Newton method"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "t0 = tic()\n",
    "x1 = problem_as_zero.newton()\n",
    "t1 = 100 * toc(t0)\n",
    "n1 = problem_as_zero.fnorm"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Compute fixed-point using Broyden method"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "t0 = tic()\n",
    "x2 = problem_as_zero.broyden()\n",
    "t2 = 100 * toc(t0)\n",
    "n2 = problem_as_zero.fnorm"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Compute fixed-point using function iteration"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "t0 = tic()\n",
    "x3 = problem_as_fixpoint.fixpoint()\n",
    "t3 = 100 * toc(t0)\n",
    "n3 = np.linalg.norm(problem_as_fixpoint.fx - x3)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Print results"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Hundredths of seconds required to compute fixed-point of g(x)=sqrt(x)\n",
      "using Newton, Broyden, and function iteration methods, starting at\n",
      "x = 1.09\n",
      "\n"
     ]
    },
    {
     "data": {
      "text/html": [
       "<div>\n",
       "<style scoped>\n",
       "    .dataframe tbody tr th:only-of-type {\n",
       "        vertical-align: middle;\n",
       "    }\n",
       "\n",
       "    .dataframe tbody tr th {\n",
       "        vertical-align: top;\n",
       "    }\n",
       "\n",
       "    .dataframe thead th {\n",
       "        text-align: right;\n",
       "    }\n",
       "</style>\n",
       "<table border=\"1\" class=\"dataframe\">\n",
       "  <thead>\n",
       "    <tr style=\"text-align: right;\">\n",
       "      <th></th>\n",
       "      <th>Time</th>\n",
       "      <th>Norm of f</th>\n",
       "      <th>x</th>\n",
       "    </tr>\n",
       "  </thead>\n",
       "  <tbody>\n",
       "    <tr>\n",
       "      <th>Newton</th>\n",
       "      <td>0.100112</td>\n",
       "      <td>7.083223e-14</td>\n",
       "      <td>1.0</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>Broyden</th>\n",
       "      <td>0.899744</td>\n",
       "      <td>7.837671e-09</td>\n",
       "      <td>1.0</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>Function</th>\n",
       "      <td>0.199771</td>\n",
       "      <td>5.071073e-09</td>\n",
       "      <td>1.0</td>\n",
       "    </tr>\n",
       "  </tbody>\n",
       "</table>\n",
       "</div>"
      ],
      "text/plain": [
       "              Time     Norm of f    x\n",
       "Newton    0.100112  7.083223e-14  1.0\n",
       "Broyden   0.899744  7.837671e-09  1.0\n",
       "Function  0.199771  5.071073e-09  1.0"
      ]
     },
     "execution_count": 8,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "print('Hundredths of seconds required to compute fixed-point of g(x)=sqrt(x)')\n",
    "print('using Newton, Broyden, and function iteration methods, starting at')\n",
    "print('x = %4.2f\\n' % xinit)\n",
    "\n",
    "pd.DataFrame({\n",
    "    'Time': [t1, t2, t3],\n",
    "    'Norm of f': [n1, n2, n3],\n",
    "    'x': [x1, x2, x3]},\n",
    "    index=['Newton', 'Broyden', 'Function']\n",
    ")"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3.9.7 ('base')",
   "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.9.7"
  },
  "vscode": {
   "interpreter": {
    "hash": "ad2bdc8ecc057115af97d19610ffacc2b4e99fae6737bb82f5d7fb13d2f2c186"
   }
  }
 },
 "nbformat": 4,
 "nbformat_minor": 0
}