3.Solving_a_system_of_Equations.ipynb

{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "outputs": [],
   "source": [
    "%pylab inline\n",
    "import numpy as np\n",
    "from scipy import *"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Solving a system of linear equations"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "hide_input": true,
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "## Finding a line passing through 2 points\n",
    "\n",
    "We are given two points in $R^2$: $[-1,2]$ and $[1,1]$, and we want to find the line passing through these points."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "hide_input": false,
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "outputs": [],
   "source": [
    "\n",
    "figure(figsize=[8,6])\n",
    "p=np.array([[-1,2],[1,1]])\n",
    "plot(p[:,0],p[:,1],'ro')\n",
    "xlim([-1.1,1.1])\n",
    "ylim([0,2.1])\n",
    "grid()\n",
    "title('we are looking for a line going through these 2 points');"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "Any line (other than vertical) can be expressed as $y=w_0+w_1x$ where $[x,y]$ are points along the line $w_0$ y-axis intercept and $w_1$ is the slope."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "To identify the line that passes through the two points we need to find $w_0,w_1$ that satisfy two constraints:\n",
    "\n",
    "* The point $[x,y]=[-1,2]$ implies the constraint $w_0-w_1=2$\n",
    "* The point $[x,y]=[1,1]$ implies the constraint $w_0+w_1=1$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "### Writing equations in matrix form\n",
    "There are many ways to solve the equations, i.e. find $w_x,w_y$ that satisfy both constraints. \n",
    "\n",
    "Here we show two ways to find the solution using `numpy`"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "We can write the two equations in matrix form as follows:\n",
    "$$\n",
    "\\begin{equation}\n",
    "\\begin{bmatrix} 1 & -1 \\\\\n",
    "\t   1 & 1\t\n",
    "\\end{bmatrix}\n",
    "\\begin{bmatrix} w_0 \\\\ w_1\t\n",
    "\\end{bmatrix}\n",
    "=\n",
    "\\begin{bmatrix} 2 \\\\ 1\t\n",
    "\\end{bmatrix}\n",
    "\\end{equation}\n",
    "$$\n",
    "Which we can write succinctly as ${\\bf A w = b}$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "* The coefficients matrix ${\\bf A} = \\begin{equation}\n",
    "\\begin{bmatrix} 1 & -1 \\\\\n",
    "\t   1 & 1\t\n",
    "\\end{bmatrix}\n",
    "\\end{equation} $\n",
    "* The *ordinate* or *dependent variable* vector: ${\\bf b}=\\begin{bmatrix} 2 \\\\ 1\t\\end{bmatrix}$\n",
    "* The parameter vector ${\\bf w} = \\begin{bmatrix} w_0 \\\\ w_1\t\\end{bmatrix}$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "**Goal:** Find ${\\bf w}$ such that  ${\\bf A w = b}$\n",
    "\n",
    "As ${\\bf A}$ is invertible we can multiply both sides by ${\\bf A^{-1}}$ and get:\n",
    "\n",
    "${\\bf w =  A^{-1} A w = A^{-1} b }$\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "### Solving using `numpy`"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "hide_input": true,
    "scrolled": true,
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "outputs": [],
   "source": [
    "A = np.array([[1,-1], [1,1]])\n",
    "print('A =\\n',A)\n",
    "b = np.array([[2],[1]])\n",
    "print('b =\\n',b)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "hide_input": true,
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "outputs": [],
   "source": [
    "from numpy.linalg import inv\n",
    "print(\"find the solution using inv(A)\")\n",
    "Ainv=inv(A)\n",
    "print('inv(A) = \\n',Ainv)\n",
    "print('check the Ainv is indeed the inverse of A')\n",
    "print('A * inv(A)=\\n',A.dot(Ainv)) # \n",
    "w=inv(A).dot(b)\n",
    "print('Solution: w= inv(A)*b = \\n',w)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "hide_input": true,
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "outputs": [],
   "source": [
    "print(\"alternatively, you can use 'solve()'\")\n",
    "from numpy.linalg import solve\n",
    "w = solve(A, b)\n",
    "print('solution: w =\\n',w)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "outputs": [],
   "source": [
    "def F(x,w):\n",
    "    return w[0]+w[1]*x\n",
    "print('F(-1)=',F(-1,w))\n",
    "print('F(1)=',F(1,w))    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "hide_input": true,
    "scrolled": false,
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "outputs": [],
   "source": [
    "figure(figsize=[8,6])\n",
    "plot(p[:,0],p[:,1],'ro')\n",
    "_xlim=[-1.1,1.1]\n",
    "xlim(_xlim)\n",
    "ylim([0,2.1])\n",
    "plot(_xlim,[F(_xlim[0],w),F(_xlim[1],w)])\n",
    "grid()\n",
    "title('plotting the line going through the two points');\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "## More than 2 points\n",
    "\n",
    "Suppose we have three points, rather than two.\n",
    "\n",
    "There is usually no straight line going through these points."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "hide_input": true,
    "scrolled": false,
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "outputs": [],
   "source": [
    "figure(figsize=[8,6])\n",
    "p=np.array([[-1,2],[1,1],[0,1.25]])\n",
    "plot(p[:,0],p[:,1],'ro')\n",
    "xlim([-1.1,1.1])\n",
    "ylim([0,2.1])\n",
    "grid()\n",
    "title('No straight line goes through these three points');"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "## next video: minimizing square error\n",
    "When the number of points is larger than the number of dimensions we say that the \n",
    "system is **over-determined**. \n",
    "\n",
    "In this case we want to find a line that passes **close to** the points."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "source": [
    "### When can you use `numpy.linlag.solve` ?\n",
    "The function `numpy.linlag.solve` can be used to solve a set of $n$ linear equations with $n$ unknowns.\n",
    "\n",
    "You simply express the set of equation in a matrix format ${\\bf Ax=b}$ and call `solve` using `x=solve(A,b)` the returned value is a vector with the solution for ${\\bf x}$.\n",
    "\n",
    "However the number of equations and the number of unknowns must be equal. \n",
    "* If the number of equations is **smaller** that the number of unknowns we say that the system is **underdetermined** or **singular**. It means that we don't have enough information to specify a unique solution. In data analysis this would rarely be the case.\n",
    "* If the number of equations is **larger** than the number of unknowns we say that the system if **overdetermined**. It means that there is no solution that satisfies all of the constraints. In data analysis this is a very common occurance, and we will discuss it in the next notebook."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "source": [
    "### Example\n",
    "Find the solution for the following set of 3 equations:\n",
    "$$\n",
    "x+y-z=5 \\\\\n",
    "z+2y=3 \\\\\n",
    "y-x=4\n",
    "$$"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "outputs": [],
   "source": [
    "# Solution\n",
    "A=np.array([[1,1,-1],[0,2,1],[-1,1,0]])\n",
    "b=np.array([5,3,4])\n",
    "solve(A,b)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "source": [
    "Which means that the solution is $x=-1,y=3,z=-3$\n",
    "\n",
    "Check that the solution is correct, i.e. that it satisfies the three constraints."
   ]
  }
 ],
 "metadata": {
  "celltoolbar": "Slideshow",
  "kernelspec": {
   "display_name": "Python [default]",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.6.2"
  },
  "toc": {
   "base_numbering": 1,
   "nav_menu": {
    "height": "122px",
    "width": "252px"
   },
   "number_sections": true,
   "sideBar": true,
   "skip_h1_title": false,
   "title_cell": "Table of Contents",
   "title_sidebar": "Contents",
   "toc_cell": false,
   "toc_position": {},
   "toc_section_display": "block",
   "toc_window_display": false
  },
  "varInspector": {
   "cols": {
    "lenName": 16,
    "lenType": 16,
    "lenVar": 40
   },
   "kernels_config": {
    "python": {
     "delete_cmd_postfix": "",
     "delete_cmd_prefix": "del ",
     "library": "var_list.py",
     "varRefreshCmd": "print(var_dic_list())"
    },
    "r": {
     "delete_cmd_postfix": ") ",
     "delete_cmd_prefix": "rm(",
     "library": "var_list.r",
     "varRefreshCmd": "cat(var_dic_list()) "
    }
   },
   "types_to_exclude": [
    "module",
    "function",
    "builtin_function_or_method",
    "instance",
    "_Feature"
   ],
   "window_display": false
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}