CG00.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# An Introduction to the Conjugate Gradient Method Without the Agonizing Pain"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "[Jonathan Richard Shewchuk](https://people.eecs.berkeley.edu/~jrs/), <br>\n",
    "August 4, 1994 <br>\n",
    "School of Computer Science <br>\n",
    "Carnegie Mellon University <br>\n",
    "Pittsburgh, PA 15213\n",
    "\n",
    "Supported in part by the Natural Sciences and Engineering Research Council of Canada under a 1967 Science and Engineering Scholarship and by the National Science Foundation under Grant ASC-9318163. The views and conclusions contained in this document are those of the author and should not be interpreted as representing the official policies, either express or implied, of NSERC, NSF, or the U.S. Government."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<html>\n",
    "<hr style=\"height:2px;border:none;color:#228;background-color:#228;\" />\n",
    "<span style=\"color:#228\">\n",
    "\n",
    "<p>Converted to a notebook by André van Schaik in June 2017. It strikes me as if this paper was always meant to be in notebook format. You can now zoom images and rotate 3D images, and I've added a few interactive figures with sliders to play with.\n",
    "\n",
    "<p>André van Schaik<br>\n",
    "<a href='http://westernsydney.edu.au/icns'>International Centre for Neuromorphic Systems</a><br>\n",
    "<a href='http://westernsydney.edu.au/marcs'>The MARCS Institute for Brain, Behaviour, and Development</a><br>\n",
    "<a href='http://westernsydney.edu.au'>Western Sydney University</a>\n",
    "</span>\n",
    "<hr style=\"height:2px;border:none;color:#228;background-color:#228;\" />\n",
    "</html>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Abstract"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The Conjugate Gradient Method is the most prominent iterative method for solving sparse systems of linear equations. Unfortunately, many textbook treatments of the topic are written with neither illustrations nor intuition, and their victims can be found to this day babbling senselessly in the corners of dusty libraries. For this reason, a deep, geometric understanding of the method has been reserved for the elite brilliant few who have painstakingly decoded the mumblings of their forebears. Nevertheless, the Conjugate Gradient Method is a composite of simple, elegant ideas that almost anyone can understand. Of course, a reader as intelligent as yourself will learn them almost effortlessly.\n",
    "\n",
    "The idea of quadratic forms is introduced and used to derive the methods of Steepest Descent, Conjugate Directions, and Conjugate Gradients. Eigenvectors are explained and used to examine the convergence of the Jacobi Method, Steepest Descent, and Conjugate Gradients. Other topics include preconditioning and the nonlinear Conjugate Gradient Method. I have taken pains to make this article easy to read. Sixty-six illustrations are provided. Dense prose is avoided. Concepts are explained in several different ways. Most equations are coupled with an intuitive interpretation."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Contents"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "1. [Introduction](CG01.ipynb)\n",
    "\n",
    "2. [Notation](CG02.ipynb)\n",
    "\n",
    "3. [The Quadratic Form](CG03.ipynb)\n",
    "\n",
    "4. [The Method of Steepest Descent](CG04.ipynb)\n",
    "\n",
    "5. [Thinking with Eigenvectors and Eigenvalues](CG05.ipynb)<br>\n",
    " 5.1. [Eigen do it if I try](CG05.ipynb#5.1)<br>\n",
    " 5.2. [Jacobi iterations](CG05.ipynb#5.2)<br>\n",
    " 5.3. [A Concrete Example](CG05.ipynb#5.3)<br>\n",
    "\n",
    "6. [Convergence Analysis of Steepest Descent](CG06.ipynb)<br>\n",
    " 6.1. [Instant Results](CG06.ipynb#6.1)<br>\n",
    " 6.2. [General Convergence](CG06.ipynb#6.2)\n",
    "\n",
    "7. [The Method of Conjugate Directions](CG07.ipynb)<br>\n",
    " 7.1. [Conjugacy](CG07.ipynb#7.1)<br>\n",
    " 7.2. [Gram-Schmidt Conjugation](CG07.ipynb#7.2)<br>\n",
    " 7.3. [Optimality of the Error Term](CG07.ipynb#7.3)\n",
    "\n",
    "8. [The Method of Conjugate Gradients](CG08.ipynb)\n",
    "\n",
    "9. [Convergence Analysis of Conjugate Gradients](CG09.ipynb)<br>\n",
    " 9.1. [Picking Perfect Polynomials](CG09.ipynb#9.1)<br>\n",
    " 9.2. [Chebyshev Polynomials](CG09.ipynb#9.2)\n",
    "\n",
    "10. [Complexity](CG10.ipynb)\n",
    "\n",
    "11. [Starting and Stopping](CG11.ipynb)<br>\n",
    " 11.1. [Starting](CG11.ipynb#11.1)<br>\n",
    " 11.2. [Stopping](CG11.ipynb#11.2)\n",
    "\n",
    "12. [Preconditioning](CG12.ipynb#12)\n",
    "\n",
    "13. [Conjugate Gradients on the Normal Equations](CG13.ipynb#13)\n",
    "\n",
    "14. [The Nonlinear Conjugate Gradient Method](CG14.ipynb)<br>\n",
    " 14.1. [Outline of the Nonlinear Conjugate Gradient Method](CG14.ipynb#14.1)<br>\n",
    " 14.2. [General Line Search](CG14.ipynb#14.2)<br>\n",
    " 14.3. [Preconditioning](CG14.ipynb#14.3)\n",
    "\n",
    "A [Notes and References](CGA.ipynb)\n",
    "\n",
    "B [Canned Algorithms](CGB.ipynb)<br>\n",
    " 1. [Steepest Descent](CGB.ipynb#B.1)<br>\n",
    " 2. [Conjugate Gradients](CGB.ipynb#B.2)<br>\n",
    " 3. [Preconditioned Conjugate Gradients](CGB.ipynb#B.3)<br>\n",
    " 4. [Nonlinear Conjugate Gradients with Newton-Raphson and Fletcher-Reeves](CGB.ipynb#B.4)<br>\n",
    " 5. [Preconditioned Nonlinear Conjugate Gradients with Secant and Polak-Ribière](CGB.ipynb#B.5)\n",
    "\n",
    "C [Ugly Proofs](CGC.ipynb)<br>\n",
    " 1. [The Solution to $Ax = b$ Minimizes the Quadratic Form](CGC.ipynb#C.1)<br>\n",
    " 2. [A Symmetric Matrix Has $n$ Orthogonal Eigenvectors](CGC.ipynb#C.2)<br>\n",
    " 3. [Optimality of Chebyshev Polynomials](CGC.ipynb#C.3)\n",
    "\n",
    "D [Homework](CGD.ipynb)\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Next: [1. Introduction](CG01.ipynb)"
   ]
  }
 ],
 "metadata": {
  "anaconda-cloud": {},
  "hide_input": false,
  "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.7.9"
  },
  "latex_envs": {
   "bibliofile": "biblio.bib",
   "cite_by": "apalike",
   "current_citInitial": 1,
   "eqLabelWithNumbers": true,
   "eqNumInitial": 0
  },
  "widgets": {
   "state": {},
   "version": "1.1.2"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}