05_Iteration_Ex.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 5. Iterative Computation: Exercise\n",
    "\n",
    "Name: "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "$$ % Latex macros\n",
    "\\newcommand{\\mat}[1]{\\begin{pmatrix} #1 \\end{pmatrix}}\n",
    "\\newcommand{\\p}[2]{\\frac{\\partial #1}{\\partial #2}}\n",
    "\\newcommand{\\b}[1]{\\boldsymbol{#1}}\n",
    "\\newcommand{\\w}{\\boldsymbol{w}}\n",
    "\\newcommand{\\x}{\\boldsymbol{x}}\n",
    "\\newcommand{\\y}{\\boldsymbol{y}}\n",
    "$$"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "scrolled": true
   },
   "outputs": [],
   "source": [
    "import numpy as np\n",
    "import matplotlib.pyplot as plt\n",
    "%matplotlib inline"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 1. Newton's method in n dimension\n",
    "Newton's method can be generalized for $n$ dimensional vector $x \\in \\Re^n$ and $n$ dimensional function $f(x)={\\bf0} \\in \\Re^n$ as\n",
    "$$ x_{k+1} = x_k - J(x_k)^{-1}f(x_k) $$\n",
    "where $J(x)$ is the *Jacobian matrix*\n",
    "$$ J(x) = \\mat{\\p{f_1}{x_1} & \\cdots & \\p{f_1}{x_n}\\\\\n",
    "    \\vdots & & \\vdots\\\\\n",
    "    \\p{f_n}{x_1} & \\cdots & \\p{f_n}{x_n}} $$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "1) Define a function that computes\n",
    "$$ f(x) = \n",
    "    \\left(\\begin{array}{c} a_0 + a_1 x_1^2 + a_2 x_2^2\\\\\n",
    "    b_0 + b_1 x_1 + b_2 x_2\\end{array}\\right)\n",
    "$$\n",
    "and its Jacobian."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def f(x, a, b, deriv=True):\n",
    "    \"\"\"y[0] = a[0] + a[1]*x[0]**2 + a[2]*x[1]**2\\\\\n",
    "    y[1] = b[0] + b[1]*x[0] + b[2]*x[1]\n",
    "    also return the Jacobian if derive==True\"\"\"\n",
    "    y0 = \n",
    "    y1 = \n",
    "    if deriv:\n",
    "        J = \n",
    "        \n",
    "        return np.array([y0, y1]), np.array(J)\n",
    "    else:\n",
    "        return np.array([y0, y1])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "a = [-1, 1, 1]\n",
    "b = [-1, 1, 2]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "f([1,1],a,b)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "2) Consider the case of $a = [-1, 1, 1]$ and $b = [-1, 1, 2]$ and visualize parabollic and linear surfaces."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "%matplotlib notebook"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "x = np.linspace(-2, 2, 25)\n",
    "y = np.linspace(-2, 2, 25)\n",
    "X, Y = np.meshgrid(x, y)\n",
    "XY = np.array([X,Y])  # (2,25,25) array\n",
    "Z = \n",
    "ax = plt.figure(figsize=(8,8)).add_subplot(projection='3d')\n",
    "ax.plot_surface(X, Y, Z[0])\n",
    "\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "3) Implement Newton's method for vectors."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def newton(f, x0, *args, target=1e-6, maxstep=20):\n",
    "    \"\"\"Newton's method. \n",
    "        f: should also return Jacobian matrix\n",
    "        x0: initial guess\n",
    "        *args: parameter for f(x,*args)\n",
    "        target: accuracy target\"\"\"\n",
    "    n = len(x0)  # dimension\n",
    "    x = np.zeros((maxstep+1, n))\n",
    "    y = np.zeros((maxstep, n))\n",
    "    x[0] = x0\n",
    "    for i in range(maxstep):\n",
    "        y[i], J = f(x[i], *args)\n",
    "        if   < target:\n",
    "            break  # converged!\n",
    "        x[i+1] = \n",
    "    else:\n",
    "        print('did not coverge in', maxstep, 'steps.')\n",
    "    return x[:i+1], y[:i+1]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "4) Test how it works from different initial guesses."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "newton(f, [0,1], a, b)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "newton(f, [1,1], a, b)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    " "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 2. Bifurcation and Chaos\n",
    "A value of $x_k$ that stays unchanged after applying a map $f$ to it (i.e. $x_k = f(x_k) = x_{k+1}$) is called a \"fixed point\" of $f$. \n",
    "\n",
    "Let us consider the logistic map\n",
    "$$ x_{k+1} = a x_k(1 - x_k) $$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "1) Plot $x_{k+1}=ax_k(1-x_k)$ along with $x_{k+1}=x_k$ for $a=0.5, 2, 3.3$.\n",
    "\n",
    "What are the fixed points of these maps?"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "2) A fixed point is said to be \"stable\" when nearby values of $x_k$ also converge to the fixed point after applying $f$ many times; it's said to be \"unstable\" when nearby values of $x_k$ diverge from it. \n",
    "\n",
    "Draw \"cobweb plots\" on top of each of the previous plots to visualize trajectories. \n",
    "Try several different initial values of $x_k$.\n",
    "\n",
    "Are the fixed points you found stable or unstable?\n",
    "\n",
    "How is the stability related to the slope (derivative) of $f(x_k)=ax_k(1-x_k)$ at the fixed point?"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "3: optional) A *bifurcation diagram* is a plot of trajectories versus a parameter.  \n",
    "draw the bifurcation diagram for parameter $a$ $(1 \\le a \\le 4)$, like below:  \n",
    "![bifurcation](figures/bifurcation.png)\n",
    "\n",
    "Hint:\n",
    "* Use the `logistic()` and `iterate()` functions from the previous lecture.\n",
    "* For each value of $a$, show the trajectory (i.e., the values that $x_k$ took over some iterations) of the map after an initial transient. \n",
    "* Since $x_k$ is 1D, you can plot the trajectory on the y axis. For example, take 200 points in $1 \\le a \\le 4$, run 1000 step iterations for each $a$, and plot $x$ after skipping first 100 steps."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 3. Recursive call and fractal\n",
    "\n",
    "Draw the Sherpinski gasket as below.\n",
    "\n",
    "![shelpinski](figures/shelpinski.png)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3 (ipykernel)",
   "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.16"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 1
}