{"worksheets": [{"cells": [{"cell_type": "markdown", "metadata": {}, "source": ["# Orthogonal Iteration"]}, {"collapsed": false, "metadata": {}, "input": ["import numpy as np\n", "import numpy.linalg as la"], "cell_type": "code", "prompt_number": 62, "outputs": [], "language": "python"}, {"cell_type": "markdown", "metadata": {}, "source": ["Let's make a matrix with given eigenvalues:"]}, {"collapsed": false, "metadata": {}, "input": ["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": "code", "prompt_number": 3, "outputs": [{"text": ["[-1.3657822  -0.78460489 -0.08829521  0.30824369  0.52110266]\n"], "output_type": "stream", "stream": "stdout"}], "language": "python"}, {"cell_type": "markdown", "metadata": {}, "source": ["Let's make an array of iteration vectors:"]}, {"collapsed": false, "metadata": {}, "input": ["X = np.random.randn(n, n)"], "cell_type": "code", "prompt_number": 4, "outputs": [], "language": "python"}, {"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."]}, {"collapsed": false, "metadata": {}, "input": ["Q, R = la.qr(X)\n", "X = np.dot(A, Q)\n", "print(Q)"], "cell_type": "code", "prompt_number": 64, "outputs": [{"text": ["[[-0.36366705 -0.24462159  0.39052837  0.06435026 -0.8070026 ]\n", " [-0.42943052 -0.63956476  0.08336455 -0.49910706  0.3879289 ]\n", " [-0.040959   -0.42224061 -0.83670032  0.25124759 -0.23841653]\n", " [ 0.80079022 -0.35639657  0.08781549 -0.40630442 -0.24273785]\n", " [-0.20098031  0.47519633 -0.36436102 -0.72009898 -0.28721745]]\n"], "output_type": "stream", "stream": "stdout"}], "language": "python"}, {"cell_type": "markdown", "metadata": {}, "source": ["Now check that the (hopefully) converged $Q$ actually led to Schur form:"]}, {"collapsed": false, "metadata": {}, "input": ["la.norm(\n", "    np.dot(np.dot(Q, R), Q.T)\n", "    - A)"], "cell_type": "code", "prompt_number": 67, "outputs": [{"text": ["5.2990176465002692e-10"], "output_type": "pyout", "metadata": {}, "prompt_number": 67}], "language": "python"}, {"cell_type": "markdown", "metadata": {}, "source": ["Do the eigenvalues match?"]}, {"collapsed": false, "metadata": {}, "input": ["R"], "cell_type": "code", "prompt_number": 68, "outputs": [{"text": ["array([[-1.3657822 ,  0.08740819,  3.037871  , -0.26244477, -0.29760524],\n", "       [ 0.        , -0.78460489, -0.45833238, -1.38868012,  0.24515348],\n", "       [ 0.        ,  0.        ,  0.52110266, -0.15202445,  0.07378812],\n", "       [-0.        ,  0.        , -0.        ,  0.30824369,  0.17685701],\n", "       [ 0.        , -0.        ,  0.        ,  0.        , -0.08829521]])"], "output_type": "pyout", "metadata": {}, "prompt_number": 68}], "language": "python"}, {"cell_type": "markdown", "metadata": {}, "source": ["What are possible flaws in this plan?\n", "\n", "* Will this always converge?\n", "* What about complex eigenvalues?"]}], "metadata": {}}], "nbformat_minor": 0, "nbformat": 3, "metadata": {"name": "", "signature": "sha256:5020a1d3a2256e2233ea5a3c2be335ab80586e6e2c92aaaafe2eb93af2473cb4"}}