{
 "metadata": {
  "name": "",
  "signature": "sha256:cf300856c89b59eb8cd9c42b9e7ccabf6030b17cf2bb5158b23034e0388df05b"
 },
 "nbformat": 3,
 "nbformat_minor": 0,
 "worksheets": [
  {
   "cells": [
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "# Sistemas sobredeterminados e o MMQ\n",
      "Vamos considerar um sistema linear na forma matricial:\n",
      "$$ \\begin{pmatrix} a_{11} & \\cdots & a_{1n} \\\\ \\vdots & \\vdots & \\vdots \\\\ a_{k1} & \\cdots & a_{kn}\n",
      "\\end{pmatrix}\\begin{pmatrix}x_1 \\\\ \\vdots \\\\ x_n  \\end{pmatrix}=\\begin{pmatrix}y_1 \\\\ \\vdots \\\\ y_k \\end{pmatrix}$$ com $k>n$.\n",
      "\n",
      "O posto m\u00e1ximo da matriz $A$ \u00e9 ent\u00e3o $n$. Quer dizer a imagem da matriz $A$ \u00e9 gerada pelas colunas\n",
      "de $A$. Observe que podemos escrever o produto acima como:\n",
      "$$\n",
      "x_1 \\begin{pmatrix}a_{11} \\\\ a_{21} \\\\ \\vdots \\\\ a_{k1} \\end{pmatrix} + \\cdots +x_n\\begin{pmatrix} a_{1n} \\\\ a_{2n} \\\\ \\vdots \\\\ a_{kn}\\end{pmatrix} = \\begin{pmatrix}y_1 \\\\ y_2 \\\\ \\vdots \\\\ y_k \\end{pmatrix}\n",
      "$$\n",
      "ent\u00e3o variando os n\u00fameros $x_1,\\dots, x_n$ obtemos, no m\u00e1ximo, um subespa\u00e7o de dimens\u00e3o $n$ em $\\mathbb{R}^k$. A \u00fanica forma de encontrarmos uma solu\u00e7\u00e3o do sistema \u00e9 se o vetor $\\mathbf{y}$ est\u00e1 no subespa\u00e7o de dimens\u00e3o $n$ mencionado. E se as colunas da matriz $A$ forem linearmente independentes a solu\u00e7\u00e3o ser\u00e1 \u00fanica!"
     ]
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "## Exemplo\n",
      "Seja $A = \\begin{pmatrix} 1 & 1 \\\\ 1 & 0 \\\\ 0 & 1 \\end{pmatrix}$ o sistema \n",
      "$$ A\\begin{pmatrix} x \\\\ y \\end{pmatrix} = \\begin{pmatrix} 1 \\\\ 2 \\\\ -1 \\end{pmatrix}$$ tem uma \u00fanica solu\u00e7\u00e3o $(x,y)=(2,-1)$. enquanto o sistema \n",
      "$$ A\\begin{pmatrix} x \\\\ y \\end{pmatrix} = \\begin{pmatrix} 1 \\\\ 2 \\\\ 0 \\end{pmatrix}$$ n\u00e3o tem solu\u00e7\u00e3o."
     ]
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "## Rela\u00e7\u00e3o com MMQ\n",
      "Podemos aumentar o conceito de solu\u00e7\u00e3o do sistema sobredeterminado, de forma a incluir o caso em que ele tem uma solu\u00e7\u00e3o expl\u00edcita. Dizemos que $\\mathbf{x}\\in \\mathbb{R}^n$ \u00e9 solu\u00e7\u00e3o do sistema sobredeterminado, $A\\mathbf{x}=\\mathbf{y}$, se $A\\mathbf{x}$ for o elemento do espa\u00e7o vetorial gerado pelas colunas de $A$ que esteja mais pr\u00f3ximo de $\\mathbf{y}$. E para medir a dist\u00e2ncia usamos:\n",
      "$$\\|A\\mathbf{x} -\\mathbf{y}\\|^2 = \\langle A\\mathbf{x} -\\mathbf{y},A\\mathbf{x} -\\mathbf{y}\\rangle $$\n",
      "Para facilitar a nota\u00e7\u00e3o, vamos denotar as colunas da matriz $A$ como $\\mathbf{a}_i$, com $i\\in \\{1,\\dots,n\\}$. A solu\u00e7\u00e3o do sistema sobredeterminada \u00e9 a proje\u00e7\u00e3o ortogonal de $\\mathbf{y}$ no\n",
      "na imagem de $A$, e portanto se escreve $x_1\\mathbf{a}_1+ \\cdots + x_n\\mathbf{a}_n =\\sum_{i=1}^n x_i\\mathbf{a}_i$.\n",
      "\n",
      "Por ser proje\u00e7\u00e3o ortogonal devemos ter que $\\mathbf{y}-\\sum_{i=1}^nx_i\\mathbf{a}_i$ \u00e9 ortogonal a cada $\\mathbf{a}_j$ para $j$ de $1$ a $n$. Assim devem estar satisfeitas as seguintes equa\u00e7\u00f5es:\n",
      "$$ \\langle \\mathbf{y}-\\sum_{i=1}^nx_i\\mathbf{a}_i, \\mathbf{a}_j \\rangle =0 $$\n",
      "e usando a bilinearidade do produto escalar temos:\n",
      "$$ \\sum_{i=1}^n x_i \\langle, \\mathbf{a}_i,\\mathbf{a}_j\\rangle = \\langle \\mathbf{y},\\mathbf{a}_j \\rangle $$\n",
      "Este sistema linear \u00e9 conhecido como o sistema normal do sistema sobredeterminado, e assim vemos a rela\u00e7\u00e3o com o M\u00e9todo dos m\u00ednimos quadrados.\n"
     ]
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "**Exemplo:** vamos encontrar o sistema normal dos sistemas do exemplo anterior.\n",
      "Como a matriz $A$ nos dois casos \u00e9 $A = \\begin{pmatrix} 1 & 1 \\\\ 1 & 0 \\\\ 0 & 1 \\end{pmatrix}$, temos que a matriz de coeficientes do sistema normal \u00e9:\n",
      "$$ N = \\begin{pmatrix}2 & 1 \\\\ 1 & 2 \\end{pmatrix} $$\n",
      "No primeiro caso o sistema normal \u00e9\n",
      "$$\\begin{pmatrix}2 & 1 \\\\ 1 & 2 \\end{pmatrix}\\begin{pmatrix}x_1 \\\\ x_2 \\end{pmatrix}=\\begin{pmatrix} 3 \\\\ 0 \\end{pmatrix}$$\n",
      "e no segundo caso:\n",
      "$$\\begin{pmatrix}2 & 1 \\\\ 1 & 2 \\end{pmatrix}\\begin{pmatrix}x_1 \\\\ x_2 \\end{pmatrix}=\\begin{pmatrix} 3 \\\\ 1 \\end{pmatrix}$$"
     ]
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "import numpy as np\n",
      "def SistemaNormal(A,y):\n",
      "    '''Retorna os parametros do sistema normal de um sistema sobredeterminado.'''\n",
      "    k,n = np.shape(A)\n",
      "    N = np.array([[sum(A.T[i]*A.T[j]) for j in range(n)] for i in range(n)])\n",
      "    b = np.array([sum(A.T[i]*y) for i in range(n)])\n",
      "    return N,b"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [],
     "prompt_number": 1
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "#teste\n",
      "A=np.array([[1,2,3,4,5],[2,3,4,5,6],[3,4,5,0,0]]).T\n",
      "y=np.array([1,0,1,0,1])"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [],
     "prompt_number": 2
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "N,u = SistemaNormal(A,y)"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [],
     "prompt_number": 3
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "N"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "metadata": {},
       "output_type": "pyout",
       "prompt_number": 4,
       "text": [
        "array([[55, 70, 26],\n",
        "       [70, 90, 38],\n",
        "       [26, 38, 50]])"
       ]
      }
     ],
     "prompt_number": 4
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "u"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "metadata": {},
       "output_type": "pyout",
       "prompt_number": 5,
       "text": [
        "array([ 9, 12,  8])"
       ]
      }
     ],
     "prompt_number": 5
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [],
     "language": "python",
     "metadata": {},
     "outputs": []
    }
   ],
   "metadata": {}
  }
 ]
}