Solving_System_of_Linear_Equations.ipynb

{
  "cells": [
    {
      "cell_type": "markdown",
      "id": "sunset-slovenia",
      "metadata": {
        "id": "sunset-slovenia"
      },
      "source": [
        "---"
      ]
    },
    {
      "cell_type": "markdown",
      "id": "grand-excellence",
      "metadata": {
        "deletable": false,
        "editable": false,
        "id": "grand-excellence",
        "nbgrader": {
          "cell_type": "markdown",
          "checksum": "20ff09590d775ba39d375bb01f491a09",
          "grade": false,
          "grade_id": "cell-1fc84fa265289359",
          "locked": true,
          "schema_version": 3,
          "solution": false,
          "task": false
        }
      },
      "source": [
        "# Numerical Analysis\n",
        "# Solving a System of Linear Equations"
      ]
    },
    {
      "cell_type": "markdown",
      "id": "random-mainstream",
      "metadata": {
        "id": "random-mainstream"
      },
      "source": [
        "## Remember\n",
        "\n",
        "### Jacobi\n",
        "\n",
        "To solve the system of equations $Ax = b$ using Jacobi's method, you decompose $A$ into three matrices $D+L+U$ where $D$ is the diagonal matrix of $A$, $L$ is the strict lower triangular matrix of $A$ and $U$ is the strict upper triangular matrix of $A$.\n",
        "Then to find a solution, you iterate through the following formula\n",
        "$$\n",
        "x^{(k)} = D^{-1}(b - (L+U)x^{(k-1)})\n",
        "$$\n",
        "\n",
        "### Gauss-Siedel\n",
        "To solve the system of equations $Ax = b$ using Gauss-Siedel method, you decompose $A$ into three matrices $D+L+U$ where $D$ is the diagonal matrix of $A$, $L$ is the strict lower triangular matrix of $A$ and $U$ is the strict upper triangular matrix of $A$.\n",
        "Then to find a solution, you iterate through the following formula\n",
        "$$\n",
        "x^{(k)} = (D+L)^{-1}(b - Ux^{(k-1)})\n",
        "$$"
      ]
    },
    {
      "cell_type": "markdown",
      "id": "religious-newfoundland",
      "metadata": {
        "deletable": false,
        "editable": false,
        "id": "religious-newfoundland",
        "nbgrader": {
          "cell_type": "markdown",
          "checksum": "ac6ec9fab97567d0e8bdf256c5930724",
          "grade": false,
          "grade_id": "cell-86a84faa28c49163",
          "locked": true,
          "schema_version": 3,
          "solution": false,
          "task": false
        }
      },
      "source": [
        "#### TO-DO (1)\n",
        "\n",
        "Deﬁne a function `jacobi` that takes in $n\\times n$ square matrix `A`, vector `b` of size $n$, and a number of iterations `N`. Start with an initial solution $x^{(0)} = 0$ and use the Jacobi's formula to find an approximate solution to the equation `Ax = b`."
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "id": "flush-corpus",
      "metadata": {
        "deletable": false,
        "id": "flush-corpus",
        "nbgrader": {
          "cell_type": "code",
          "checksum": "1ecf43f8ae4e0676f9b32ad74bfc23ea",
          "grade": false,
          "grade_id": "cell-db97c555e129ba01",
          "locked": false,
          "schema_version": 3,
          "solution": true,
          "task": false
        }
      },
      "outputs": [],
      "source": [
        "import numpy as np\n",
        "#from numpy import linalg\n",
        "def jacobi(A, b, N):\n",
        "    # YOUR CODE HERE\n",
        "    X_0 = np.zeros_like(b)\n",
        "    D= np.diag(np.diag(A))\n",
        "    D_1= np.linalg.inv(D)\n",
        "    for i in range(N):\n",
        "      X_0 = D_1@(b-(A-D)@X_0)\n",
        "    return X_0\n",
        "    raise NotImplementedError()"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "id": "major-threshold",
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "deletable": false,
        "editable": false,
        "id": "major-threshold",
        "nbgrader": {
          "cell_type": "code",
          "checksum": "a5be424af26031a6967469824d5d3658",
          "grade": true,
          "grade_id": "cell-05aa7e9e5bf73475",
          "locked": true,
          "points": 5,
          "schema_version": 3,
          "solution": false,
          "task": false
        },
        "outputId": "465388c6-ed8b-4925-b250-a63c3c4b1abc"
      },
      "outputs": [
        {
          "name": "stdout",
          "output_type": "stream",
          "text": [
            "[0.99999999 0.99999999 0.99999999 0.99999999 0.99999999 0.99999999\n",
            " 0.99999999 0.99999999 0.99999999 0.99999999]\n"
          ]
        }
      ],
      "source": [
        "np.random.seed(42)\n",
        "A = 10 * np.eye(10)\n",
        "A = A + np.random.rand(10,10)\n",
        "b = np.sum(A, axis=1)\n",
        "s = jacobi(A,b,20)\n",
        "print(s)\n",
        "assert np.allclose(s, np.ones(10))"
      ]
    },
    {
      "cell_type": "markdown",
      "id": "hungry-hollow",
      "metadata": {
        "deletable": false,
        "editable": false,
        "id": "hungry-hollow",
        "nbgrader": {
          "cell_type": "markdown",
          "checksum": "8877bca546294f7b3b067f8e10bd307d",
          "grade": false,
          "grade_id": "cell-751b31697bf40662",
          "locked": true,
          "schema_version": 3,
          "solution": false,
          "task": false
        }
      },
      "source": [
        "#### TO-DO (2)\n",
        "\n",
        "Deﬁne a function `siedel` that takes in $n\\times n$ square matrix `A`, vector `b` of size $n$, and a number of iterations `N`. Start with an initial solution $x^{(0)} = 0$ and use the Gauss-Siedel formula to find an approximate solution to the equation `Ax = b`."
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "id": "fifteen-sunset",
      "metadata": {
        "deletable": false,
        "id": "fifteen-sunset",
        "nbgrader": {
          "cell_type": "code",
          "checksum": "0aa58bf0330093e3e926837d0429e050",
          "grade": false,
          "grade_id": "cell-1a2a21e628de402b",
          "locked": false,
          "schema_version": 3,
          "solution": true,
          "task": false
        }
      },
      "outputs": [],
      "source": [
        "import numpy as np\n",
        "from numpy.linalg import inv\n",
        "\n",
        "def siedel(A, b, N):\n",
        "    # YOUR CODE HERE\n",
        "    X_0 = np.zeros_like(b)\n",
        "    D= np.diag(np.diag(A))\n",
        "    L = np.tril(A,-1)\n",
        "    U = np.triu(A,1)\n",
        "    DL_1= np.linalg.inv(D+L)\n",
        "    for i in range(N):\n",
        "      X_0 = DL_1@(b-U@X_0)\n",
        "    print(X_0)\n",
        "    return X_0\n",
        "    raise NotImplementedError()"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "id": "furnished-ballot",
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "deletable": false,
        "editable": false,
        "id": "furnished-ballot",
        "nbgrader": {
          "cell_type": "code",
          "checksum": "73b1695475a7cd8b2b710876686e6945",
          "grade": true,
          "grade_id": "cell-590a3e49a220661b",
          "locked": true,
          "points": 5,
          "schema_version": 3,
          "solution": false,
          "task": false
        },
        "outputId": "c57b35ee-f236-4fa3-8bb1-ef2734834b4f"
      },
      "outputs": [
        {
          "name": "stdout",
          "output_type": "stream",
          "text": [
            "[1. 1. 1. 1. 1. 1. 1. 1. 1. 1.]\n"
          ]
        }
      ],
      "source": [
        "np.random.seed(42)\n",
        "A = 10 * np.eye(10)\n",
        "A = A + np.random.rand(10,10)\n",
        "b = np.sum(A, axis=1)\n",
        "s = siedel(A,b,10)\n",
        "assert np.allclose(s, np.ones(10))"
      ]
    },
    {
      "cell_type": "markdown",
      "id": "intimate-radio",
      "metadata": {
        "id": "intimate-radio"
      },
      "source": [
        "**\\[THE END\\]**"
      ]
    }
  ],
  "metadata": {
    "colab": {
      "collapsed_sections": [],
      "name": "Ahmad Mongy - 120200033 - Lab9-Solving_System_of_Linear_Equations.ipynb",
      "provenance": []
    },
    "kernelspec": {
      "display_name": "Python 3",
      "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.7.1"
    }
  },
  "nbformat": 4,
  "nbformat_minor": 5
}