Trefethen & Bau lecture notes in MATLAB

TB-Lecture-01.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Lecture 1. Matrix-Vector Multiplication"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Matrix times vector"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "A matrix right-multiplied by a column vector---that is, $\\mathbf{A}\\mathbf{x}$---is a linear combination of the columns of $\\mathbf{A}$, with coefficients of the combination given by the entries of $\\mathbf{x}$. For example,"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "A =\n",
      "\n",
      "     8     1     6\n",
      "     3     5     7\n",
      "     4     9     2\n",
      "\n",
      "\n",
      "x =\n",
      "\n",
      "    -1\n",
      "     2\n",
      "     1\n"
     ]
    }
   ],
   "source": [
    "A = magic(3), x = [-1;2;1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "A*x"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "x(1)*A(:,1) + x(2)*A(:,2) + x(3)*A(:,3)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "In this context it's clear why the number of entries in $\\mathbf{x}$ has to be the same as the number of columns in $\\mathbf{A}$."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "If you left-multiply a matrix by a vector, it should be a row vector. I'll be using column vectors exclusively, so we have to transpose (or conjugate transpose) to get the row shape. Transposition of the product also makes the interpretation clear:\n",
    "\n",
    "$$\n",
    "\\mathbf{y}^* \\mathbf{A} = \\bigl( \\mathbf{A}^* \\mathbf{y}\\bigr)^*,\n",
    "$$\n",
    "\n",
    "which is the (conjugate) transpose of the columns of $\\mathbf{A}^*$, i.e., the rows of $\\mathbf{A}$."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Linear algebra, including abstract linear algebra, is built in large part on linear combinations. The vectors that one combines need not be ordinary vectors in $\\mathbb{C}^n$. For instance, a polynomial is a linear combination of monomials. We can encompasss this fact too by generalizing the notion of a \"matrix\":\n",
    "\n",
    "$$\n",
    "c_0 + c_1 t + \\cdots c_n t^n = \\begin{bmatrix} 1 & t & \\cdots & t^n \\end{bmatrix} \\begin{bmatrix}c_0 \\\\ c_1 \\\\ \\vdots \\\\ c_n \\end{bmatrix}.\n",
    "$$\n",
    "\n",
    "The \"matrix\" here is sometimes called a *quasimatrix*. From here it's a small step to imagine choosing many values of $t$ in an interval and converting the quasimatrix into a proper matrix. This is easy to carry out in MATLAB."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "V = zeros(51,4);  % not strictly necessary\n",
    "t = linspace(0,1,51)'; \n",
    "for j = 0:3, V(:,j+1) = t.^j; end\n",
    "plot(t,V)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Matrix times matrix"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "It's often useful to think of a matrix-matrix product as a collection of matrix-vector products. For example,"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "C =\n",
      "\n",
      "    16    18    21\n",
      "     5    16    26\n",
      "     9    16    22\n",
      "     4    18    33\n"
     ]
    }
   ],
   "source": [
    "A = magic(4); B = triu(ones(4,3)); \n",
    "C = A*B"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "ans =\n",
      "\n",
      "    16    18    21\n",
      "     5    16    26\n",
      "     9    16    22\n",
      "     4    18    33\n"
     ]
    }
   ],
   "source": [
    "[ A*B(:,1), A*B(:,2), A*B(:,3) ]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Hence the number of rows in $\\mathbf{B}$ has to be the same as the number of columns in $\\mathbf{A}$. In the special case where that number is 1, then $\\mathbf{A}$ is a column vector and $\\mathbf{B}$ is a row vector, and the result is called a **vector outer product**. "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "ans =\n",
      "\n",
      "     4     1\n",
      "\n",
      "\n",
      "ans =\n",
      "\n",
      "     1     3\n"
     ]
    }
   ],
   "source": [
    "u = [ 1; 2; 3; 4 ];  v = [ 1i -1i 1 ];\n",
    "size(u), size(v)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "ans =\n",
      "\n",
      "  Columns 1 through 2\n",
      "\n",
      "   0.0000e+00 + 1.0000e+00i   0.0000e+00 - 1.0000e+00i\n",
      "   0.0000e+00 + 2.0000e+00i   0.0000e+00 - 2.0000e+00i\n",
      "   0.0000e+00 + 3.0000e+00i   0.0000e+00 - 3.0000e+00i\n",
      "   0.0000e+00 + 4.0000e+00i   0.0000e+00 - 4.0000e+00i\n",
      "\n",
      "  Column 3\n",
      "\n",
      "   1.0000e+00 + 0.0000e+00i\n",
      "   2.0000e+00 + 0.0000e+00i\n",
      "   3.0000e+00 + 0.0000e+00i\n",
      "   4.0000e+00 + 0.0000e+00i\n"
     ]
    }
   ],
   "source": [
    "u*v"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Rank and inverse"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The rank and inverse of a matrix are of critical importance in linear algebra. It's important to be aware, however, that they are not robust to perturbations. For example, it should be clear that this matrix is singular and of rank 1."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "A =\n",
      "\n",
      "     0     1\n",
      "     0     0\n",
      "\n",
      "\n",
      "ans =\n",
      "\n",
      "     1\n"
     ]
    }
   ],
   "source": [
    "A = [ 0 1; 0 0 ]\n",
    "rank(A)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "However, any perturbation of the second row, no matter how small, mathematically changes the rank to 2 and thus makes the matrix invertible."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "B =\n",
      "\n",
      "            0   1.0000e+00\n",
      "   1.0000e-12            0\n",
      "\n",
      "\n",
      "ans =\n",
      "\n",
      "     2\n"
     ]
    }
   ],
   "source": [
    "format short e\n",
    "B = A + [0 0; 1e-12 0 ]\n",
    "rank(B)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "In numerical computation, representation of and arithmetic with real numbers cannot be exact. Therefore, the notions of rank and invertibility will have to be carefully reconsidered. In fact, it's questionable as to whether you should ever compute a matrix rank in finite precision.  "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Change of basis"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "In linear algebra one learns that a matrix is the expression of a linear transformation relative to a particular basis. Unless stated otherwise, when we write out the numerical values of a matrix, we have chosen the standard basis, whose elements are the columns of an identity matrix. \n",
    "\n",
    "Say we have a basis whose elements, when expressed in the standard basis, are the columns of a square matrix $\\mathbf{A}$. Let a vector $\\mathbf{v}$ be given as coordinates $x_1,x_2,\\ldots$ in that basis. Then we can convert the coordinates of $\\mathbf{v}$ to standard by matrix--vector multiplication:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "A = magic(3);  x = [ -1; 1; 2 ];\n",
    "v_standard = A*x"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Consequently, we can convert a vector from standard coordinates to the \"$\\mathbf{A}$-basis\" through multiplication by $\\mathbf{A}^{-1}$. "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "v_Abasis = A^(-1) * v_standard"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Note that while `A^(-1)*` works in MATLAB, *it is not recommended*, for reasons we will go into later. A mathematically equivalent but computationally preferable syntax is to use `A\\` instead."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "v_Abasis = A \\ v_standard"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Matlab",
   "language": "matlab",
   "name": "matlab"
  },
  "language_info": {
   "codemirror_mode": "octave",
   "file_extension": ".m",
   "help_links": [
    {
     "text": "MetaKernel Magics",
     "url": "https://github.com/calysto/metakernel/blob/master/metakernel/magics/README.md"
    }
   ],
   "mimetype": "text/x-octave",
   "name": "matlab",
   "version": "0.11.0"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 0
}

TB-Lecture-02.ipynb

TB-Lecture-03.ipynb

TB-Lecture-04.ipynb

TB-Lecture-05.ipynb

TB-Lecture-06.ipynb

TB-Lecture-07.ipynb

TB-Lecture-08.ipynb

TB-Lecture-09.ipynb

TB-Lecture-10.ipynb

TB-Lecture-11.ipynb

TB-Lecture-12.ipynb