Lecture3-2.ipynb

Lecture3-2.ipynb

{
  "cells": [
    {
      "metadata": {
        "collapsed": true
      },
      "cell_type": "markdown",
      "source": "LU Decomposition!"
    },
    {
      "metadata": {},
      "cell_type": "markdown",
      "source": "Given the equations:\n\n$$\n\\begin{eqnarray*}\n10x_1 + 2x_2 - x_3 = 27 \\\\\n-3x_1 -6x_2 + 2x_3 = -61.5 \\\\\nx_1 + x_2 + 5x_3 = - 21.5 \\\\\n\\end{eqnarray*}\n$$\n\nChange the right-hand-sides of the linear system of equations to the following vectors:\n\nb1=(2.5,3.1,-0.3), b2=(0,-2,1.5), and b3=(1,0,1).  \n\nFor solving the linear system, apply the LU decomposition."
    },
    {
      "metadata": {
        "collapsed": true,
        "trusted": true
      },
      "cell_type": "code",
      "source": "import numpy as np\nA = np.array([[10.,2.,-1.],[-3.,-6.,2.],[1.,1.,5.]])",
      "execution_count": 1,
      "outputs": []
    },
    {
      "metadata": {
        "collapsed": false,
        "trusted": true
      },
      "cell_type": "code",
      "source": "import copy\ndef lu_decomp(A_):\n    Au = copy.deepcopy(A_)\n    Al = np.identity(len(Au))\n    for i in range(len(Au)):\n        for j in range((i+1),len(Au)):\n            B = np.identity(len(Au))\n            c = Au[j][i]/Au[i][i]\n            for k in range(len(Au)):\n                Au[j][k] -= c*Au[i][k]\n            B[j][i] = c #using elementary matrix operations\n            Al = Al.dot(B)\n    return [Au, Al]\n\ndef lu_solver(A, B):\n    Au, Al = lu_decomp(A)\n    # forward substitution\n    y = np.zeros(len(A))\n    for i in range(len(B)):\n        b_y = B[i];\n        for j in range(i):\n            b_y -= Al[i][j]*y[j]\n        y[i] = b_y/Al[i][i]\n    \n    #back substitution\n    x = np.zeros(len(A))\n    for i in reversed(range(len(B))):\n        y_x = y[i]\n        for j in reversed(range(i+1, len(B))):\n            y_x -= Au[i][j]*x[j]\n        x[i] = y_x/Au[i][i]\n    \n    return x\n    ",
      "execution_count": 2,
      "outputs": []
    },
    {
      "metadata": {
        "collapsed": false,
        "trusted": true
      },
      "cell_type": "code",
      "source": "b1 = np.array([2.5, 3.1, -0.3])\nlu_solver(A, b1)",
      "execution_count": 3,
      "outputs": [
        {
          "output_type": "execute_result",
          "data": {
            "text/plain": "array([ 0.39273356, -0.71176471,  0.00380623])"
          },
          "metadata": {},
          "execution_count": 3
        }
      ]
    },
    {
      "metadata": {
        "collapsed": false,
        "trusted": true
      },
      "cell_type": "code",
      "source": "b2 = np.array([0, -2, 1.5])\nlu_solver(A,b2)",
      "execution_count": 4,
      "outputs": [
        {
          "output_type": "execute_result",
          "data": {
            "text/plain": "array([-0.06574394,  0.44117647,  0.22491349])"
          },
          "metadata": {},
          "execution_count": 4
        }
      ]
    },
    {
      "metadata": {
        "trusted": true,
        "collapsed": false
      },
      "cell_type": "code",
      "source": "b3 = np.array([1., 0., 1.])\nlu_solver(A,b3)",
      "execution_count": 5,
      "outputs": [
        {
          "output_type": "execute_result",
          "data": {
            "text/plain": "array([ 0.11764706, -0.        ,  0.17647059])"
          },
          "metadata": {},
          "execution_count": 5
        }
      ]
    },
    {
      "metadata": {},
      "cell_type": "markdown",
      "source": "※ using Naive Gauss elimination"
    },
    {
      "metadata": {
        "trusted": true,
        "collapsed": true
      },
      "cell_type": "code",
      "source": "import copy\ndef upm(A_, B_):\n    A = copy.deepcopy(A_)\n    B = copy.deepcopy(B_)\n    for i in range(len(A)):\n        for j in range((i+1),len(A)):\n            c = A[j][i]/A[i][i]\n            for k in range(len(A)):\n                A[j][k] -= c*A[i][k]\n            B[j] -= c*B[i]\n    return [A,B]\n    \ndef naive_gauss_elimination(A_, B_):\n    A = copy.deepcopy(A_)\n    B = copy.deepcopy(B_)\n    A, B = upm(A, B)\n    ans = np.zeros(len(A))\n    for i in reversed(range(len(A))):\n        a = B[i]\n        for j in reversed(range(i+1,len(A))):\n            a -= A[i][j]*ans[j]\n        a /= A[i][i]\n        ans[i] = a\n    return ans",
      "execution_count": 6,
      "outputs": []
    },
    {
      "metadata": {
        "trusted": true,
        "collapsed": false
      },
      "cell_type": "code",
      "source": "naive_gauss_elimination(A,b1)",
      "execution_count": 7,
      "outputs": [
        {
          "output_type": "execute_result",
          "data": {
            "text/plain": "array([ 0.39273356, -0.71176471,  0.00380623])"
          },
          "metadata": {},
          "execution_count": 7
        }
      ]
    },
    {
      "metadata": {
        "trusted": true,
        "collapsed": false
      },
      "cell_type": "code",
      "source": "naive_gauss_elimination(A,b2)",
      "execution_count": 8,
      "outputs": [
        {
          "output_type": "execute_result",
          "data": {
            "text/plain": "array([-0.06574394,  0.44117647,  0.22491349])"
          },
          "metadata": {},
          "execution_count": 8
        }
      ]
    },
    {
      "metadata": {
        "trusted": true,
        "collapsed": false
      },
      "cell_type": "code",
      "source": "naive_gauss_elimination(A,b3)",
      "execution_count": 9,
      "outputs": [
        {
          "output_type": "execute_result",
          "data": {
            "text/plain": "array([ 0.11764706, -0.        ,  0.17647059])"
          },
          "metadata": {},
          "execution_count": 9
        }
      ]
    }
  ],
  "metadata": {
    "kernelspec": {
      "name": "python3",
      "display_name": "Python 3",
      "language": "python"
    },
    "language_info": {
      "name": "python",
      "version": "3.6.0",
      "mimetype": "text/x-python",
      "codemirror_mode": {
        "name": "ipython",
        "version": 3
      },
      "pygments_lexer": "ipython3",
      "nbconvert_exporter": "python",
      "file_extension": ".py"
    },
    "toc": {
      "threshold": 4,
      "number_sections": true,
      "toc_cell": false,
      "toc_window_display": false,
      "toc_section_display": "block",
      "sideBar": true,
      "navigate_menu": true,
      "moveMenuLeft": true,
      "widenNotebook": false,
      "colors": {
        "hover_highlight": "#DAA520",
        "selected_highlight": "#FFD700",
        "running_highlight": "#FF0000"
      },
      "nav_menu": {
        "height": "12px",
        "width": "252px"
      }
    },
    "varInspector": {
      "window_display": true,
      "cols": {
        "lenName": 16,
        "lenType": 16,
        "lenVar": 40
      },
      "kernels_config": {
        "python": {
          "library": "var_list.py",
          "delete_cmd_prefix": "del ",
          "delete_cmd_postfix": "",
          "varRefreshCmd": "print(var_dic_list())"
        },
        "r": {
          "library": "var_list.r",
          "delete_cmd_prefix": "rm(",
          "delete_cmd_postfix": ") ",
          "varRefreshCmd": "cat(var_dic_list()) "
        }
      },
      "types_to_exclude": [
        "module",
        "function",
        "builtin_function_or_method",
        "instance",
        "_Feature"
      ],
      "oldHeight": 122,
      "position": {
        "height": "187px",
        "left": "877px",
        "right": "20px",
        "top": "106px",
        "width": "350px"
      },
      "varInspector_section_display": "block"
    },
    "gist": {
      "id": "3846045e761422dbdc3e386e2fd94316",
      "data": {
        "description": "Lecture3-2.ipynb",
        "public": true
      }
    },
    "_draft": {
      "nbviewer_url": "https://gist.github.com/3846045e761422dbdc3e386e2fd94316"
    }
  },
  "nbformat": 4,
  "nbformat_minor": 2
}