{"metadata": {"name": "", "signature": "sha256:480b8d144d8d338f331afa009000efbd5b411d027849e06bfb65734a955f4132"}, "nbformat_minor": 0, "nbformat": 3, "worksheets": [{"metadata": {}, "cells": [{"cell_type": "markdown", "source": ["# Keeping track of coefficients in Gram-Schmidt"], "metadata": {}}, {"prompt_number": 38, "metadata": {}, "outputs": [], "language": "python", "input": ["import numpy as np\n", "import numpy.linalg as la"], "cell_type": "code", "collapsed": false}, {"prompt_number": 39, "metadata": {}, "outputs": [], "language": "python", "input": ["A = np.random.randn(3, 3)"], "cell_type": "code", "collapsed": false}, {"cell_type": "markdown", "source": ["Let's start from regular old (modified) Gram-Schmidt:"], "metadata": {}}, {"prompt_number": 57, "metadata": {}, "outputs": [], "language": "python", "input": ["\n", "Q = np.zeros(A.shape)\n", "\n", "q = A[:, 0]\n", "Q[:, 0] = q/la.norm(q)\n", "\n", "# -----------\n", "\n", "q = A[:, 1]\n", "coeff = np.dot(Q[:, 0], q)\n", "q = q - coeff*Q[:, 0]\n", "Q[:, 1] = q/la.norm(q)\n", "\n", "# -----------\n", "\n", "q = A[:, 2]\n", "coeff = np.dot(Q[:, 0], q)\n", "q = q - coeff*Q[:, 0]\n", "coeff = np.dot(Q[:, 1], q)\n", "q = q - coeff*Q[:, 1]\n", "Q[:, 2] = q/la.norm(q)"], "cell_type": "code", "collapsed": false}, {"prompt_number": 52, "metadata": {}, "outputs": [{"prompt_number": 52, "metadata": {}, "output_type": "pyout", "text": ["array([[  1.00000000e+00,   8.88178420e-16,   3.05311332e-16],\n", "       [  8.88178420e-16,   1.00000000e+00,   0.00000000e+00],\n", "       [  3.05311332e-16,   0.00000000e+00,   1.00000000e+00]])"]}], "language": "python", "input": ["Q.dot(Q.T)"], "cell_type": "code", "collapsed": false}, {"cell_type": "markdown", "source": ["Now we want to keep track of what vector got added to what other vector, in the style of an elimination matrix.\n", "\n", "Let's call that matrix $R$.\n", "\n", "* Would it be $A=QR$ or $A=RQ$? Why?\n", "* Where are $R$'s nonzeros?"], "metadata": {}}, {"prompt_number": 56, "metadata": {}, "outputs": [], "language": "python", "input": ["R = np.zeros((A.shape[0], A.shape[0]))"], "cell_type": "code", "collapsed": false}, {"prompt_number": 54, "metadata": {}, "outputs": [], "language": "python", "input": ["Q = np.zeros(A.shape)\n", "\n", "q = A[:, 0]\n", "Q[:, 0] = q/la.norm(q)\n", "\n", "R[0,0] = la.norm(q)\n", "\n", "# -----------\n", "\n", "q = A[:, 1]\n", "coeff = np.dot(Q[:, 0], q)\n", "R[0,1] = coeff\n", "q = q - coeff*Q[:, 0]\n", "Q[:, 1] = q/la.norm(q)\n", "\n", "R[1,1] = la.norm(q)\n", "\n", "# -----------\n", "\n", "q = A[:, 2]\n", "coeff = np.dot(Q[:, 0], q)\n", "R[0,2] = coeff\n", "q = q - coeff*Q[:, 0]\n", "coeff = np.dot(Q[:, 1], q)\n", "R[1,2] = coeff\n", "q = q- coeff*Q[:, 1]\n", "Q[:, 2] = q/la.norm(q)\n", "\n", "R[2,2] = la.norm(q)"], "cell_type": "code", "collapsed": false}, {"prompt_number": 55, "metadata": {}, "outputs": [{"prompt_number": 55, "metadata": {}, "output_type": "pyout", "text": ["array([[ 0.77134813,  0.22468956, -2.09753371],\n", "       [ 0.        ,  1.92179208,  1.24545523],\n", "       [ 0.        ,  0.        ,  0.56553203]])"]}], "language": "python", "input": ["R"], "cell_type": "code", "collapsed": false}, {"prompt_number": 48, "metadata": {}, "outputs": [{"prompt_number": 48, "metadata": {}, "output_type": "pyout", "text": ["2.7755575615628914e-17"]}], "language": "python", "input": ["la.norm(Q.dot(R) - A)"], "cell_type": "code", "collapsed": false}, {"cell_type": "markdown", "source": ["This is called [QR factorization](https://en.wikipedia.org/wiki/QR_decomposition)."], "metadata": {}}, {"cell_type": "markdown", "source": ["----------\n", "* When does it break?\n", "* Does it need something like pivoting?\n", "* Can we use it for something?"], "metadata": {}}]}]}