Gram_Schmidt.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {
    "collapsed": false
   },
   "source": [
    "Name: "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "collapsed": false
   },
   "source": [
    "Suppose $\\left\\{\\mathbf{v}_1, \\mathbf{v}_2,\\ldots , \\mathbf{v}_n \\right\\}$ is a basis for $\\mathbb{R}^n$. The Gram-Schmidt process is a means of taking such a basis and converting it to an orthogonal basis, $\\left\\{\\mathbf{u}_1, \\mathbf{u}_2,\\ldots , \\mathbf{u}_n \\right\\}$. It requires\n",
    "making repeated use of the orthogonal projection of one vector onto another. If $\\mathbf{u}$ and $\\mathbf{v}$, are vectors in $\\mathbb{R}^n$, we write $\\mbox{proj}_{\\mathbf{v}} \\mathbf{u}$ as the the vector projection of $\\mathbf{u}$ onto $\\mathbf{v}$. Note that the\n",
    "this projection and the projection of $\\mathbf{v}$ onto $\\mathbf{u}$ are different.\n",
    "\n",
    "Below is a function for computing $\\mbox{proj}_{\\mathbf{v}} \\mathbf{u}$.\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 39,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
   ],
   "source": [
    "def proj(u,v):\n",
    "    w=u.dot_product(v)/v.norm()^2*v\n",
    "    return w"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "collapsed": false
   },
   "source": [
    "We will work with three vectors $\\mathbf{v}_1$, $\\mathbf{v}_2$ and $\\mathbf{v}_3$ in $\\mathbb{R}^3$, which are entered below. By creating a matrix, $A$, whose columns are the three vectors, one could easily use the Invertible Matrix Theorem to show $\\mathbf{v}_1$, $\\mathbf{v}_2$ and $\\mathbf{v}_3$ form a basis $\\mathbb{R}^3$. It's easy to see, from computing their dot products, that the vectors are not orthogonal"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 40,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
   ],
   "source": [
    "v1=vector([2,3,1])\n",
    "v2=vector([1,1,1])\n",
    "v3=vector([0,1,0])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "collapsed": false
   },
   "source": [
    "At the first step of the orthogonal basis construction, we simply define $\\mathbf{u}_1=\\mathbf{v}_1$."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 41,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "(2, 3, 1)"
      ]
     },
     "execution_count": 41,
     "metadata": {
     },
     "output_type": "execute_result"
    }
   ],
   "source": [
    "u1=v1\n",
    "u1"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "collapsed": false
   },
   "source": [
    "We now compute the vector projection of $\\mathbf{v}_2$ onto $\\mathbf{u}_1$, $\\mbox{proj}_{\\mathbf{u}_1} \\mathbf{v}_2$, and we set\n",
    "set $\\mathbf{u}_2=\\mathbf{v}_2-\\mbox{proj}_{\\mathbf{u}_1} \\mathbf{v}_2$, which we know is orthogonal to $\\mathbf{u}_1$."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 42,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "(1/7, -2/7, 4/7)"
      ]
     },
     "execution_count": 42,
     "metadata": {
     },
     "output_type": "execute_result"
    }
   ],
   "source": [
    "u2=v2-proj(v2,u1)\n",
    "u2"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "collapsed": false
   },
   "source": [
    "A check that $\\mathbf{u}_1$ and $\\mathbf{u}_2$ are orthogonal by computing their dot product"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 43,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "0"
      ]
     },
     "execution_count": 43,
     "metadata": {
     },
     "output_type": "execute_result"
    }
   ],
   "source": [
    "u1.dot_product(u2)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "collapsed": false
   },
   "source": [
    "We repeat this process. Now $\\mathbf{u}_3=\\mathbf{v}_3-\\mbox{proj}_{\\mathbf{u}_1} \\mathbf{v}_3-\\mbox{proj}_{\\mathbf{u}_2} \\mathbf{v}_3$"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 44,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "(-1/3, 1/6, 1/6)"
      ]
     },
     "execution_count": 44,
     "metadata": {
     },
     "output_type": "execute_result"
    }
   ],
   "source": [
    "u3=v3-proj(v3,u1)-proj(v3,u2)\n",
    "u3"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "collapsed": false
   },
   "source": [
    "A check that $\\mathbf{u}_3$ and $\\mathbf{u}_2$ are orthogonal as are $\\mathbf{u}_3$ and $\\mathbf{u}_1$"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 45,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "0"
      ]
     },
     "execution_count": 45,
     "metadata": {
     },
     "output_type": "execute_result"
    }
   ],
   "source": [
    "u3.dot_product(u2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 46,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "0"
      ]
     },
     "execution_count": 46,
     "metadata": {
     },
     "output_type": "execute_result"
    }
   ],
   "source": [
    "u3.dot_product(u1)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "collapsed": false
   },
   "source": [
    "For the general case, we start with a basis $\\left\\{\\mathbf{v}_1, \\mathbf{v}_2,\\ldots , \\mathbf{v}_n \\right\\}$ is a basis for $\\mathbb{R}^n$. The To construct orthogonal basis, $\\left\\{\\mathbf{u}_1, \\mathbf{u}_2,\\ldots , \\mathbf{u}_n \\right\\}$, we proceed as follows:\n",
    "\n",
    "1. $\\mathbf{u}_1=\\mathbf{v}_1$.\n",
    "2. $\\mathbf{u}_k=\\mathbf{v}_k-\\sum_{j=1}^{k-1} \\mbox{proj}_{\\mathbf{u}_k} \\mathbf{v}_k$.\n",
    "\n",
    "Now consider the five vectors in $\\mathbb{R}^5$ given as follows:\n",
    "\n",
    "$\\mathbf{v}_1=\\begin{bmatrix} 3 \\\\ -5 \\\\ -4 \\\\ 4 \\\\ -3 \\end{bmatrix}$\n",
    "$\\mathbf{v}_2=\\begin{bmatrix} 0 \\\\ 4 \\\\ 0 \\\\ 0 \\\\ 5 \\end{bmatrix}$\n",
    "$\\mathbf{v}_3=\\begin{bmatrix} 2 \\\\ -4 \\\\ 3 \\\\ -5 \\\\ -1 \\end{bmatrix}$\n",
    "$\\mathbf{v}_4=\\begin{bmatrix} -3 \\\\ 4 \\\\ 3 \\\\ 5 \\\\ 0 \\end{bmatrix}$\n",
    "$\\mathbf{v}_5=\\begin{bmatrix} -3 \\\\ -3 \\\\ -1 \\\\ 4 \\\\ -5 \\end{bmatrix}$\n",
    "\n",
    "These vectors form a basis for $\\mathbb{R}^5$. In the lines below, enter the vectors by modifying the code from above. \n",
    "Then construct an orthogonal\n",
    "basis of $\\mathbb{R}^5$, $\\left\\{\\mathbf{u}_1, \\mathbf{u}_2,\\mathbf{u}_3,\\mathbf{u}_4,\\mathbf{u}_5 \\right\\}$, using these vectors."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 0,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
   ],
   "source": [
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "SageMath (stable)",
   "language": "sagemath",
   "metadata": {
    "cocalc": {
     "description": "Open-source mathematical software system",
     "priority": 10,
     "url": "https://www.sagemath.org/"
    }
   },
   "name": "sagemath"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 2
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython2",
   "version": "2.7.15"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 0
}