nrla_QR_zerlegung.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# QR Zerlegung\n",
    "\n",
    "- Gegeben: Matrix $A \\in M(m \\times n)$\n",
    "- Gesucht: Orthogonale Matrix $Q$ und obere Dreiecksmatrix $R$, sodass $A = Q \\cdot R$"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "# input:\n",
    "A = matrix([\n",
    "    [1, 1, 1],\n",
    "    [2, -4, 1],\n",
    "    [-2, 1, -3]\n",
    "])\n",
    "#"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Orthonormalisieren der Spaltenvektor von $A$ mittels Gram-Schmidt Verfahren:\n",
    "\n",
    "$$ w_1 = \\frac{1}{\\| v_1 \\|} v_1 $$\n",
    "$$ u_i = v_i - \\sum_{k=1}^{i-1} \\langle v_i, w_k \\rangle w_k $$\n",
    "$$ w_i = \\frac{1}{\\| u_i \\|} u_i $$"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/html": [
       "<html><script type=\"math/tex; mode=display\">\\newcommand{\\Bold}[1]{\\mathbf{#1}}v_0 = \\left(1,\\,2,\\,-2\\right)</script></html>"
      ],
      "text/plain": [
       "v_0 = (1, 2, -2)"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    },
    {
     "data": {
      "text/html": [
       "<html><script type=\"math/tex; mode=display\">\\newcommand{\\Bold}[1]{\\mathbf{#1}}w_0 = \\left(\\frac{1}{3},\\,\\frac{2}{3},\\,-\\frac{2}{3}\\right)</script></html>"
      ],
      "text/plain": [
       "w_0 = (1/3, 2/3, -2/3)"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    },
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "\n"
     ]
    },
    {
     "data": {
      "text/html": [
       "<html><script type=\"math/tex; mode=display\">\\newcommand{\\Bold}[1]{\\mathbf{#1}}v_1 = \\left(1,\\,-4,\\,1\\right)</script></html>"
      ],
      "text/plain": [
       "v_1 = (1, -4, 1)"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    },
    {
     "data": {
      "text/html": [
       "<html><script type=\"math/tex; mode=display\">\\newcommand{\\Bold}[1]{\\mathbf{#1}}u_1 = \\left(2,\\,-2,\\,-1\\right)</script></html>"
      ],
      "text/plain": [
       "u_1 = (2, -2, -1)"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    },
    {
     "data": {
      "text/html": [
       "<html><script type=\"math/tex; mode=display\">\\newcommand{\\Bold}[1]{\\mathbf{#1}}w_1 = \\left(\\frac{2}{3},\\,-\\frac{2}{3},\\,-\\frac{1}{3}\\right)</script></html>"
      ],
      "text/plain": [
       "w_1 = (2/3, -2/3, -1/3)"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    },
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "\n"
     ]
    },
    {
     "data": {
      "text/html": [
       "<html><script type=\"math/tex; mode=display\">\\newcommand{\\Bold}[1]{\\mathbf{#1}}v_2 = \\left(1,\\,1,\\,-3\\right)</script></html>"
      ],
      "text/plain": [
       "v_2 = (1, 1, -3)"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    },
    {
     "data": {
      "text/html": [
       "<html><script type=\"math/tex; mode=display\">\\newcommand{\\Bold}[1]{\\mathbf{#1}}u_2 = \\left(-\\frac{2}{3},\\,-\\frac{1}{3},\\,-\\frac{2}{3}\\right)</script></html>"
      ],
      "text/plain": [
       "u_2 = (-2/3, -1/3, -2/3)"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    },
    {
     "data": {
      "text/html": [
       "<html><script type=\"math/tex; mode=display\">\\newcommand{\\Bold}[1]{\\mathbf{#1}}w_2 = \\left(-\\frac{2}{3},\\,-\\frac{1}{3},\\,-\\frac{2}{3}\\right)</script></html>"
      ],
      "text/plain": [
       "w_2 = (-2/3, -1/3, -2/3)"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    },
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "\n"
     ]
    }
   ],
   "source": [
    "V = [vector(v for v in col) for col in A.T]\n",
    "W = []\n",
    "U = []\n",
    "W.append((1/(V[0].norm())) * V[0])\n",
    "show(LatexExpr(\"v_0 =\"), V[0])\n",
    "show(LatexExpr(\"w_0 =\"), W[0])\n",
    "print\n",
    "for i, v in enumerate(V[1:]):\n",
    "    show(LatexExpr(\"v_{} =\".format(i+1)), v)\n",
    "    s = sum([(v.dot_product(w) * w) for w in W])\n",
    "    u = v - s\n",
    "    show(LatexExpr(\"u_{} =\".format(i+1)), u)\n",
    "    U.append(u)\n",
    "    w = (1/u.norm()) * u\n",
    "    show(LatexExpr(\"w_{} =\".format(i+1)), w)\n",
    "    W.append(w)\n",
    "    print"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Orthonormalisierte Spaltenvektoren bilden die Spaltenvektoren von $Q$"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/html": [
       "<html><script type=\"math/tex; mode=display\">\\newcommand{\\Bold}[1]{\\mathbf{#1}}\\left(\\begin{array}{rrr}\n",
       "\\frac{1}{3} & \\frac{2}{3} & -\\frac{2}{3} \\\\\n",
       "\\frac{2}{3} & -\\frac{2}{3} & -\\frac{1}{3} \\\\\n",
       "-\\frac{2}{3} & -\\frac{1}{3} & -\\frac{2}{3}\n",
       "\\end{array}\\right)</script></html>"
      ],
      "text/plain": [
       "[ 1/3  2/3 -2/3]\n",
       "[ 2/3 -2/3 -1/3]\n",
       "[-2/3 -1/3 -2/3]"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "Q = matrix(W).T\n",
    "show(Q)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Berechnen von $$R = Q^T A$$"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/html": [
       "<html><script type=\"math/tex; mode=display\">\\newcommand{\\Bold}[1]{\\mathbf{#1}}\\left(\\begin{array}{rrr}\n",
       "3 & -3 & 3 \\\\\n",
       "0 & 3 & 1 \\\\\n",
       "0 & 0 & 1\n",
       "\\end{array}\\right)</script></html>"
      ],
      "text/plain": [
       "[ 3 -3  3]\n",
       "[ 0  3  1]\n",
       "[ 0  0  1]"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "R = Q.T * A\n",
    "show(R)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/html": [
       "<html><script type=\"math/tex; mode=display\">\\newcommand{\\Bold}[1]{\\mathbf{#1}}\\left(\\begin{array}{rrr}\n",
       "1 & 1 & 1 \\\\\n",
       "2 & -4 & 1 \\\\\n",
       "-2 & 1 & -3\n",
       "\\end{array}\\right)</script></html>"
      ],
      "text/plain": [
       "[ 1  1  1]\n",
       "[ 2 -4  1]\n",
       "[-2  1 -3]"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    },
    {
     "data": {
      "text/html": [
       "<html><script type=\"math/tex; mode=display\">\\newcommand{\\Bold}[1]{\\mathbf{#1}}\\mathrm{True}</script></html>"
      ],
      "text/plain": [
       "True"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "show(Q*R)\n",
    "show(Q*R == A)"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "SageMath 7.0",
   "language": "",
   "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.11"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 0
}