day 25 - conjugate gradients.ipynb

{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "import numpy as np"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## algorithm"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def conjugate_gradients(A, b):\n",
    "    x = np.zeros(A.shape[1])\n",
    "    residuals = b - A @ x\n",
    "    direction = residuals\n",
    "    error = residuals.T @ residuals\n",
    "\n",
    "    # step along conjugate directions\n",
    "    while error > 1e-8:\n",
    "        x += direction * error / (direction.T @ A @ direction)\n",
    "        residuals = b - A @ x\n",
    "        error1 = error\n",
    "        error = residuals.T @ residuals\n",
    "        direction = residuals + error / error1 * direction\n",
    "\n",
    "    return x"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## run"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "A\n",
      "[[ 0.72202644  0.70073834  0.09483571]\n",
      " [ 0.97657699  0.41447392  0.96942563]\n",
      " [ 0.35596098  0.91433461  0.52105508]\n",
      " [ 0.66857021  0.48664146  0.46385892]\n",
      " [ 0.65044125  0.98123656  0.55633599]]\n",
      "b\n",
      "[ 0.97013697  0.76971217  0.92539487  0.10820739  0.98406079]\n",
      "x\n",
      "[ 0.26730959  0.87199275 -0.04536451]\n"
     ]
    }
   ],
   "source": [
    "A = np.random.rand(5, 3)\n",
    "b = np.random.rand(5)\n",
    "\n",
    "print('A')\n",
    "print(A)\n",
    "print('b')\n",
    "print(b)\n",
    "print('x')\n",
    "\n",
    "# make system positive semidefinite\n",
    "print(conjugate_gradients(A.T @ A, A.T @ b))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": []
  }
 ],
 "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.0"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}