homework_plus_coding_assignments/Lab_Project.ipynb

{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "# Student name: \n",
    "# Student ID:"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "This Lab Project should be completed ON YOUR OWN. You may discuss the problems with your classmates but the final version must be your own work. We will not hesitate to give zero points for an assignment if it is not your own work.\n",
    "\n",
    "Upload the notebook to the [Math105LA Assign_LabProject Dropbox](https://eee.uci.edu/toolbox/dropbox/) by the deadline indicated in the Dropbox. No late submissions will be accepted."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Relaxation for fixed-point iteration\n",
    "\n",
    "We may find the fixed-point of the function\n",
    "\n",
    "$$g(x) = \\cos^2(x),$$\n",
    "\n",
    "using the following iteration,\n",
    "\n",
    "$$ x_{k+1} = g_w(x_k) = wg(x_k) + (1-w)x_k,$$\n",
    "\n",
    "obtained by averaging the current iterate, $x_k$, and the value the next iterate would have  in ordinary fixed-point iteration, $g(x_k)$.\n",
    "\n",
    "If $p$ is the fixed point, we'd like to choose $w$ so that $g'_w(p) = 0$ so that we get quadratic convergence, but $p$ is not known. One way to deal with this is to choose $w$ such that \n",
    "$g_w'(x_{k}) = 0$ before computing $x_{k+1}$ (the relaxation parameter $w$ does not need to be the same at each iteration). \n",
    "\n",
    "### Problem \n",
    "\n",
    "Implement this method to compute the fixed point of $g(x)$. Show either numerically or analytically that this method converges quadratically.\n",
    "\n",
    "### Solution"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "# your code here "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# The inverse power method\n",
    "\n",
    "Assume the eigenvalues of an $n \\times n$ matrix $A$ satisfy\n",
    "\n",
    "$$|\\lambda_1| \\geq |\\lambda_2| \\geq \\cdots \\geq |\\lambda_{n-1}| > |\\lambda_n| > 0.$$\n",
    "\n",
    "The [inverse power method](https://en.wikipedia.org/wiki/Inverse_iteration) can be used to compute $\\lambda_n$, the smallest eigenvalue of $A$ in modulus. The basic idea is to use the standard power method to compute the largest eigenvalue of $A^{-1}$, which turns out to be the reciprocal of the smallest eigenvalue of $A$. \n",
    "\n",
    "### Problem \n",
    "\n",
    "Write a function\n",
    "`InvPower(A,Nmax,TOL)`\n",
    "that performs the following:\n",
    "\n",
    "* Compute a $PA=LU$ factorization of $A$ using partial pivoting.\n",
    "\n",
    "* Choose a vector $x^{(0)}$, with unit length.\n",
    "\n",
    "* For $k = 1,2,\\ldots,Nmax$ do \n",
    "    * Compute $y^{(k)} = A^{-1} x^{(k-1)}$ using the $PA=LU$ factorization, forward and backward substitution. \n",
    "\n",
    "    * Set $\\lambda^{(k)} = [(y^{(k)})^Tx^{(k-1)}]^{-1}$.\n",
    "\n",
    "    * Set $x^{(k)} = y^{(k)}/\\|y\\|_2$.\n",
    "\n",
    "    * If $|\\lambda^{(k)} - \\lambda^{(k-1)}| < TOL$ then return $\\lambda^{(k)}$.\n",
    "    \n",
    "    \n",
    "* If $k = Nmax$ return an appropriate error message.\n",
    "\n",
    "### Solution\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "# your code here"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Problem \n",
    "\n",
    "Use your function to compute the smallest (in modulus) eigenvalue of the following matrix. Report the number of iterations to convergence. Compute the same eigenvalue using the numpy library and check that it agrees with your answer. "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[[-2.  1.  0.  0.  0.]\n",
      " [ 1. -2.  1.  0.  0.]\n",
      " [ 0.  1. -2.  1.  0.]\n",
      " [ 0.  0.  1. -2.  1.]\n",
      " [ 0.  0.  0.  1. -2.]]\n"
     ]
    }
   ],
   "source": [
    "A = np.array([[-2,1,0,0,0],\n",
    "              [1,-2,1,0,0],\n",
    "              [0,1,-2,1,0],\n",
    "              [0,0,1,-2,1],\n",
    "              [0,0,0,1,-2]], dtype=float)\n",
    "print A"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Solution"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "# your code here"
   ]
  }
 ],
 "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.1"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}