{
  "cells": [
    {
      "cell_type": "markdown",
      "metadata": {},
      "source": [
        "# Orthogonal Iteration"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": 46,
      "metadata": {
        "collapsed": false
      },
      "outputs": [],
      "source": [
        "import numpy as np\n",
        "import numpy.linalg as la"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {},
      "source": [
        "Let's make a matrix with given eigenvalues:"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": 47,
      "metadata": {
        "collapsed": false
      },
      "outputs": [
        {
          "name": "stdout",
          "output_type": "stream",
          "text": [
            "[-1.3657822  -0.78460489 -0.08829521  0.30824369  0.52110266]\n"
          ]
        }
      ],
      "source": [
        "n = 5\n",
        "\n",
        "np.random.seed(70)\n",
        "eigvecs = np.random.randn(n, n)\n",
        "eigvals = np.sort(np.random.randn(n))\n",
        "\n",
        "A = np.dot(la.solve(eigvecs, np.diag(eigvals)), eigvecs)\n",
        "print(eigvals)"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {},
      "source": [
        "Let's make an array of iteration vectors:"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": 48,
      "metadata": {
        "collapsed": false
      },
      "outputs": [],
      "source": [
        "X = np.random.randn(n, n)"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {},
      "source": [
        "Next, implement orthogonal iteration:\n",
        "    \n",
        "* Orthogonalize.\n",
        "* Apply A\n",
        "* Repeat\n",
        "\n",
        "Run this cell in-place (Ctrl-Enter) many times."
      ]
    },
    {
      "cell_type": "code",
      "execution_count": 90,
      "metadata": {
        "collapsed": false
      },
      "outputs": [
        {
          "name": "stdout",
          "output_type": "stream",
          "text": [
            "[[-0.36366705 -0.2446216   0.39052837  0.06435026 -0.8070026 ]\n",
            " [-0.42943052 -0.63956476  0.08336453 -0.49910706  0.3879289 ]\n",
            " [-0.040959   -0.42224059 -0.83670034  0.25124759 -0.23841653]\n",
            " [ 0.80079022 -0.35639657  0.08781548 -0.40630442 -0.24273785]\n",
            " [-0.20098031  0.47519634 -0.364361   -0.72009898 -0.28721745]]\n"
          ]
        }
      ],
      "source": [
        "Q, R = la.qr(X)\n",
        "X = A @ Q\n",
        "print(Q)"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {},
      "source": [
        "Now check that the (hopefully) converged $Q$ actually led to Schur form:"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": 91,
      "metadata": {
        "collapsed": false
      },
      "outputs": [
        {
          "data": {
            "text/plain": [
              "2.4553239646805687e-07"
            ]
          },
          "execution_count": 91,
          "metadata": {},
          "output_type": "execute_result"
        }
      ],
      "source": [
        "la.norm(\n",
        "    Q @ R @ Q.T\n",
        "    - A)"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {},
      "source": [
        "Do the eigenvalues match?"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": 92,
      "metadata": {
        "collapsed": false
      },
      "outputs": [
        {
          "data": {
            "text/plain": [
              "array([[-1.3657822 ,  0.08740833,  3.037871  , -0.26244477, -0.29760524],\n",
              "       [ 0.        , -0.78460491, -0.45833236, -1.38868012,  0.24515348],\n",
              "       [ 0.        ,  0.        ,  0.52110264, -0.1520245 ,  0.07378813],\n",
              "       [ 0.        ,  0.        ,  0.        ,  0.30824369,  0.17685701],\n",
              "       [ 0.        ,  0.        ,  0.        ,  0.        , -0.08829521]])"
            ]
          },
          "execution_count": 92,
          "metadata": {},
          "output_type": "execute_result"
        }
      ],
      "source": [
        "R"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {},
      "source": [
        "What are possible flaws in this plan?\n",
        "\n",
        "* Will this always converge?\n",
        "* What about complex eigenvalues?"
      ]
    }
  ],
  "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.5.1+"
    }
  },
  "nbformat": 4,
  "nbformat_minor": 0
}