ipynb • Lines: 840{
"cells": [
{
"cell_type": "markdown",
"metadata": {
"id": "EAt-K2qgcIou"
},
"source": [
"# Systems of Linear Equations"
]
},
{
"cell_type": "markdown",
"metadata": {
"id": "FZYK-0rin5x7"
},
"source": [
"Welcome to the first assignment of the Course 1. From the lecture videos you learned about the systems of linear equations and the approach to find their solutions using row reduction. \n",
"\n",
"**After this assignment you will be able to:**\n",
"- Use `NumPy` package to set up the arrays corresponding to the system of linear equations\n",
"- Evaluate the determinant of a matrix and find the solution of the system with `NumPy` linear algebra package\n",
"- Perform row reduction to bring matrix into row echelon form\n",
"- Find the solution for the system of linear equations using row reduced matrix"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"# Table of Contents\n",
"- [ 1 - System of Linear Equations and Corresponding `NumPy` Arrays](#1)\n",
" - [ Exercise 1](#ex01)\n",
"- [ 2 - Solution for the System of Equations with `NumPy` Linear Algebra Package](#2)\n",
" - [ Exercise 2](#ex02)\n",
"- [ 3 - Elementary Operations and Row Reduction](#3)\n",
" - [ Exercise 3](#ex03)\n",
" - [ Exercise 4](#ex04)\n",
"- [ 4 - Solution for the System of Equations using Row Reduction](#4)\n",
" - [ Exercise 5](#ex05)\n",
" - [ Exercise 6](#ex06)"
]
},
{
"cell_type": "markdown",
"metadata": {
"id": "XI8PBrk_2Z4V"
},
"source": [
"## Packages\n",
"\n",
"Run the following cell to load the packages you'll need."
]
},
{
"cell_type": "code",
"execution_count": 1,
"metadata": {
"tags": [
"graded"
]
},
"outputs": [],
"source": [
"import numpy as np"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Load the unit tests defined specifically for this notebook."
]
},
{
"cell_type": "code",
"execution_count": 2,
"metadata": {},
"outputs": [],
"source": [
"import w2_unittest"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"<a name='1'></a>\n",
"## 1 - System of Linear Equations and Corresponding `NumPy` Arrays\n",
"\n",
"Matrices can be used to solve systems of equations. But first, you need to represent the system using matrices. Given the following system of linear equations:\n",
"\n",
"$$\\begin{cases} \n",
"2x_1-x_2+x_3+x_4=6, \\\\ x_1+2x_2-x_3-x_4=3, \\\\ -x_1+2x_2+2x_3+2x_4=14, \\\\ x_1-x_2+2x_3+x_4=8, \\end{cases}\\tag{1}$$\n",
"\n",
"you will construct matrix $A$, where each row represents one equation in the system and each column represents a variable $x_1$, $x_2$, $x_3$, $x_4$. The free coefficients from the right sides of the equations you will put into vector $b$."
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"<a name='ex01'></a>\n",
"### Exercise 1\n",
"\n",
"Construct matrix $A$ and vector $b$ corresponding to the system of linear equations $(1)$."
]
},
{
"cell_type": "code",
"execution_count": 3,
"metadata": {
"id": "Je3yV0Wnn5x8",
"scrolled": true,
"tags": [
"graded"
]
},
"outputs": [],
"source": [
"### START CODE HERE ###\n",
"A = np.array([ \n",
" [2, -1, 1, 1],\n",
" [1, 2, -1, -1],\n",
" [-1, 2, 2, 2],\n",
" [1, -1, 2, 1] \n",
" ], dtype=np.dtype(float)) \n",
"b = np.array([6, 3, 14, 8], dtype=np.dtype(float))\n",
"\n",
"### END CODE HERE ###"
]
},
{
"cell_type": "code",
"execution_count": 4,
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"\u001b[92m All tests passed\n"
]
}
],
"source": [
"# Test your solution\n",
"w2_unittest.test_matrix(A, b)"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"<a name='2'></a>\n",
"## 2 - Solution for the System of Equations with `NumPy` Linear Algebra Package\n",
"\n",
"A system of four linear equations with four unknown variables has a unique solution if and only if the determinant of the corresponding matrix of coefficients is not equal to zero. `NumPy` provides quick and reliable ways to calculate the determinant of a square matrix and also to solve the system of linear equations."
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"<a name='ex02'></a>\n",
"### Exercise 2\n",
"\n",
"Find the determinant $d$ of matrix A and the solution vector $x$ for the system of linear equations $(1)$."
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"<details> \n",
"<summary>\n",
" <font size=\"3\" color=\"darkgreen\"><b>Hints</b></font>\n",
"</summary>\n",
"<p>\n",
"<ul>\n",
" <li>use np.linalg.det(...) function to calculate determinant</li>\n",
" <li>use np.linalg.solve(..., ...) function to find solution of the linear system</li>\n",
"</ul>\n",
"</p>"
]
},
{
"cell_type": "code",
"execution_count": 11,
"metadata": {
"tags": [
"graded"
]
},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"Determinant of matrix A: -17.00\n",
"Solution vector: [2. 3. 4. 1.]\n"
]
}
],
"source": [
"### START CODE HERE ###\n",
"# determinant of matrix A\n",
"d = np.linalg.det(A)\n",
"ainv = np.linalg.inv(A)\n",
"\n",
"# solution of the system of linear equations \n",
"# with the corresponding coefficients matrix A and free coefficients b\n",
"x = np.dot(ainv, b)\n",
"### END CODE HERE ###\n",
"\n",
"print(f\"Determinant of matrix A: {d:.2f}\")\n",
"\n",
"print(f\"Solution vector: {x}\")"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"##### __Expected Output__\n",
"\n",
"```Python\n",
"Determinant of matrix A: -17.00\n",
"Solution vector: [2. 3. 4. 1.]\n",
"```"
]
},
{
"cell_type": "code",
"execution_count": 12,
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"\u001b[92m All tests passed\n"
]
}
],
"source": [
"# Test your solution\n",
"w2_unittest.test_det_and_solution_scipy(d,x)"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"<a name='3'></a>\n",
"## 3 - Elementary Operations and Row Reduction\n",
"\n",
"Even though the contemporary packages allow to find the solution with one line of the code, performing required algebraic operations manually helps to build foundations which are necessary for deep understanding of the machine learning algorithms. \n",
"\n",
"Here you will solve the system of linear equations algebraically using row reduction. It involves combination of the equations using elementary operations, eliminaring as many variables as possible for each equation. There are three valid operations which can be performed to bring the system of equations to equivalent one (with the same solutions):\n",
"\n",
"- Multiply any row by non-zero number\n",
"- Add two rows and exchange one of the original rows with the result of the addition\n",
"- Swap rows"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"<a name='ex03'></a>\n",
"### Exercise 3\n",
"\n",
"Set up three functions corresponding to the discussed above elementary operations."
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"<details> \n",
"<summary>\n",
" <font size=\"3\" color=\"darkgreen\"><b>Hints</b></font>\n",
"</summary>\n",
"<p>\n",
"<ul>\n",
" <li>you can extract i-th row of a matrix M using the code M[i]</li>\n",
" <li>remember, that indexing of arrays in Python starts from zero, so to extract second row of a matrix, you need to use the following code: M[1]</li>\n",
"</ul>\n",
"</p>"
]
},
{
"cell_type": "code",
"execution_count": 13,
"metadata": {
"tags": [
"graded"
]
},
"outputs": [],
"source": [
"### START CODE HERE ###\n",
"def MultiplyRow(M, row_num, row_num_multiple):\n",
" # .copy() function is required here to keep the original matrix without any changes\n",
" M_new = M.copy() \n",
" # exchange row_num of the matrix M_new with its multiple by row_num_multiple\n",
" # Note: for simplicity, you can drop check if row_num_multiple has non-zero value, which makes the operation valid\n",
" M_new[row_num] = M_new[row_num] * row_num_multiple\n",
" return M_new\n",
" \n",
"def AddRows(M, row_num_1, row_num_2, row_num_1_multiple):\n",
" M_new = M.copy() \n",
" # multiply row_num_1 by row_num_1_multiple and add it to the row_num_2, \n",
" # exchanging row_num_2 of the matrix M_new with the result\n",
" M_new[row_num_2] = row_num_1_multiple * M_new[row_num_1] + M_new[row_num_2]\n",
" return M_new\n",
"\n",
"def SwapRows(M, row_num_1, row_num_2):\n",
" M_new = M.copy() \n",
" # exchange row_num_1 and row_num_2 of the matrix M_new\n",
" M_new[[row_num_1, row_num_2]] = M_new[[row_num_2, row_num_1]]\n",
" return M_new\n",
"### END CODE HERE ###"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Check your code using the following test cell s:"
]
},
{
"cell_type": "code",
"execution_count": 14,
"metadata": {
"tags": [
"graded"
]
},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"Original matrix:\n",
"[[ 1. -2. 3. -4.]\n",
" [-5. 6. -7. 8.]\n",
" [-4. 3. -2. 1.]\n",
" [ 8. -7. 6. -5.]]\n",
"\n",
"Original matrix after its third row is multiplied by -2:\n",
"[[ 1. -2. 3. -4.]\n",
" [-5. 6. -7. 8.]\n",
" [ 8. -6. 4. -2.]\n",
" [ 8. -7. 6. -5.]]\n",
"\n",
"Original matrix after exchange of the third row with the sum of itself and first row multiplied by 4:\n",
"[[ 1. -2. 3. -4.]\n",
" [ -5. 6. -7. 8.]\n",
" [ 0. -5. 10. -15.]\n",
" [ 8. -7. 6. -5.]]\n",
"\n",
"Original matrix after exchange of its first and third rows:\n",
"[[-4. 3. -2. 1.]\n",
" [-5. 6. -7. 8.]\n",
" [ 1. -2. 3. -4.]\n",
" [ 8. -7. 6. -5.]]\n"
]
}
],
"source": [
"A_test = np.array([\n",
" [1, -2, 3, -4],\n",
" [-5, 6, -7, 8],\n",
" [-4, 3, -2, 1], \n",
" [8, -7, 6, -5]\n",
" ], dtype=np.dtype(float))\n",
"print(\"Original matrix:\")\n",
"print(A_test)\n",
"\n",
"print(\"\\nOriginal matrix after its third row is multiplied by -2:\")\n",
"print(MultiplyRow(A_test,2,-2))\n",
"\n",
"print(\"\\nOriginal matrix after exchange of the third row with the sum of itself and first row multiplied by 4:\")\n",
"print(AddRows(A_test,0,2,4))\n",
"\n",
"print(\"\\nOriginal matrix after exchange of its first and third rows:\")\n",
"print(SwapRows(A_test,0,2))\n",
"\n"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"##### __Expected Output__\n",
"\n",
"```Python\n",
"Original matrix:\n",
"[[ 1 -2 3 -4]\n",
" [-5 6 -7 8]\n",
" [-4 3 -2 1]\n",
" [ 8 -7 6 -5]]\n",
"\n",
"Original matrix after its third row is multiplied by -2:\n",
"[[ 1 -2 3 -4]\n",
" [-5 6 -7 8]\n",
" [ 8 -6 4 -2]\n",
" [ 8 -7 6 -5]]\n",
"\n",
"Original matrix after exchange of the third row with the sum of itself and first row multiplied by 4:\n",
"[[ 1 -2 3 -4]\n",
" [ -5 6 -7 8]\n",
" [ 0 -5 10 -15]\n",
" [ 8 -7 6 -5]]\n",
"\n",
"Original matrix after exchange of its first and third rows:\n",
"[[-4 3 -2 1]\n",
" [-5 6 -7 8]\n",
" [ 1 -2 3 -4]\n",
" [ 8 -7 6 -5]]\n",
"```"
]
},
{
"cell_type": "code",
"execution_count": 15,
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"\u001b[92m All tests passed\n"
]
}
],
"source": [
"# Test your solution\n",
"w2_unittest.test_elementary_operations(MultiplyRow, AddRows, SwapRows)"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"<a name='ex04'></a>\n",
"### Exercise 4\n",
"\n",
"Apply elementary operations to the defined above matrix A, performing row reduction according to the given instructions.\n",
"\n",
"*Note:* Feel free to add a return statement between the different matrix operations in the code to check on your results while you are writing the code (commenting off the rest of the function). This way you can see, whether your matrix operations are performed correctly line by line (don't forget to remove the return statement afterwards!)."
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"<details> \n",
"<summary>\n",
" <font size=\"3\" color=\"darkgreen\"><b>Hints</b></font>\n",
"</summary>\n",
"<p>\n",
"<ul>\n",
" <li>to swap row 1 and row 2 of matrix A, use the code SwapRows(A,1,2)</li>\n",
" <li>to multiply row 1 of matrix A by 4 and add it to the row 2, use the code AddRows(A,1,2,4)</li>\n",
" <li>to multiply row 2 of matrix A by 5, use the code MultiplyRow(A,2,5)</li>\n",
"</ul>\n",
"</p>\n"
]
},
{
"cell_type": "code",
"execution_count": 35,
"metadata": {
"tags": [
"graded"
]
},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"[[ 1. 2. -1. -1. 3.]\n",
" [ 0. 1. 4. 3. 22.]\n",
" [ 0. 0. 1. 3. 7.]\n",
" [-0. -0. -0. 1. 1.]]\n"
]
}
],
"source": [
"def augmented_to_ref(A, b): \n",
" ### START CODE HERE ###\n",
" # stack horizontally matrix A and vector b, which needs to be reshaped as a vector (4, 1)\n",
" A_system = np.hstack((A, b.reshape((4, 1))))\n",
" \n",
" # swap row 0 and row 1 of matrix A_system (remember that indexing in NumPy array starts from 0)\n",
" A_ref = SwapRows(A_system, 0, 1)\n",
" \n",
" # multiply row 0 of the new matrix A_ref by -2 and add it to the row 1\n",
" A_ref = AddRows(A_ref, 0, 1, -2)\n",
" \n",
" # add row 0 of the new matrix A_ref to the row 2, replacing row 2\n",
" A_ref = AddRows(A_ref, 0, 2, 1)\n",
" \n",
" # multiply row 0 of the new matrix A_ref by -1 and add it to the row 3\n",
" A_ref = AddRows(A_ref, 0, 3, -1)\n",
" \n",
" # add row 2 of the new matrix A_ref to the row 3, replacing row 3\n",
" A_ref = A_ref = AddRows(A_ref, 2, 3, 1)\n",
" \n",
" \n",
" # swap row 1 and 3 of the new matrix A_ref\n",
" A_ref = SwapRows(A_ref, 1, 3)\n",
" \n",
" # add row 2 of the new matrix A_ref to the row 3, replacing row 3\n",
" A_ref = AddRows(A_ref, 2, 3, 1)\n",
" \n",
" # multiply row 1 of the new matrix A_ref by -4 and add it to the row 2\n",
" A_ref = AddRows(A_ref, 1, 2, -4)\n",
" \n",
" # add row 1 of the new matrix A_ref to the row 3, replacing row 3\n",
" A_ref = AddRows(A_ref, 1, 3, 1)\n",
" \n",
" # multiply row 3 of the new matrix A_ref by 2 and add it to the row 2\n",
" A_ref = AddRows(A_ref, 3, 2, 2)\n",
" \n",
" # multiply row 2 of the new matrix A_ref by -8 and add it to the row 3\n",
" A_ref = AddRows(A_ref, 2, 3, -8)\n",
" \n",
" # multiply row 3 of the new matrix A_ref by -1/17\n",
" A_ref = MultiplyRow(A_ref, 3, -1/17)\n",
" ### END CODE HERE ###\n",
" \n",
" return A_ref\n",
"\n",
"A_ref = augmented_to_ref(A, b)\n",
"\n",
"print(A_ref)"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"##### __Expected Output__\n",
"\n",
"```Python\n",
"[[ 1 2 -1 -1 3]\n",
" [ 0 1 4 3 22]\n",
" [ 0 0 1 3 7]\n",
" [ 0 0 0 1 1]]\n",
"```"
]
},
{
"cell_type": "code",
"execution_count": 36,
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"\u001b[92m All tests passed\n"
]
}
],
"source": [
"# Test your solution\n",
"w2_unittest.test_augmented_to_ref(augmented_to_ref)"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"<a name='4'></a>\n",
"## 4 - Solution for the System of Equations using Row Reduction\n",
"\n",
"The solution can be found from the reduced form manually. From the last line you can find $x_4$, then you can calculate each of the $x_3$, $x_2$ and $x_1$ taking the elements of the matrix `A_ref[i,j]` and solving the linear equations one by one."
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"<a name='ex05'></a>\n",
"### Exercise 5\n",
"\n",
"From the last line of the reduced matrix `A_ref` find $x_4$. Then you can calculate each of the $x_3$, $x_2$ and $x_1$ taking the elements of the matrix `A_ref[i,j]` and solving the linear equations one by one."
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"<details> \n",
"<summary>\n",
" <font size=\"3\" color=\"darkgreen\"><b>Hints</b></font>\n",
"</summary>\n",
"<p>\n",
"Row reduced matrix in the section above corresponds to the following system of linear equations:\n",
"$$\\begin{cases} \n",
"x_1+2x_2-x_3-x_4=3, \\\\ x_2+4x_3+3x_4=22, \\\\ x_3+3x_4=7, \\\\ x_4=1, \n",
"\\end{cases}$$\n",
"\n",
"</p>"
]
},
{
"cell_type": "code",
"execution_count": 37,
"metadata": {
"tags": [
"graded"
]
},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"2 3 4 1\n"
]
}
],
"source": [
"### START CODE HERE ###\n",
"\n",
"# find the value of x_4 from the last line of the reduced matrix A_ref\n",
"x_4 = 1\n",
"\n",
"# find the value of x_3 from the previous row of the matrix. Use value of x_4.\n",
"x_3 = 4\n",
"\n",
"# find the value of x_2 from the second row of the matrix. Use values of x_3 and x_4\n",
"x_2 = 3\n",
"\n",
"# find the value of x_1 from the first row of the matrix. Use values of x_2, x_3 and x_4\n",
"x_1 = 2\n",
"### END CODE HERE ###\n",
"\n",
"print(x_1, x_2, x_3, x_4)"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"##### __Expected Output__\n",
"\n",
"```Python\n",
"2 3 4 1\n",
"```"
]
},
{
"cell_type": "code",
"execution_count": 38,
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"\u001b[92m All tests passed\n"
]
}
],
"source": [
"# Test your solution\n",
"w2_unittest.test_solution_elimination(x_1, x_2, x_3, x_4)"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"<a name='ex06'></a>\n",
"### Exercise 6\n",
"\n",
"Using the same elementary operations as above you can reduce the matrix further to diagonal form, from which you can see the solutions easily."
]
},
{
"cell_type": "code",
"execution_count": 41,
"metadata": {
"tags": [
"graded"
]
},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"[[ 1. 0. 0. 0. 2.]\n",
" [ 0. 1. 0. 0. 3.]\n",
" [ 0. 0. 1. 0. 4.]\n",
" [-0. -0. -0. 1. 1.]]\n"
]
}
],
"source": [
"def ref_to_diagonal(A_ref): \n",
" ### START CODE HERE ###\n",
" # multiply row 3 of the matrix A_ref by -3 and add it to the row 2\n",
" A_diag = AddRows(A_ref, 3, 2, -3)\n",
" \n",
" # multiply row 3 of the new matrix A_diag by -3 and add it to the row 1\n",
" A_diag = AddRows(A_diag, 3, 1, -3)\n",
" \n",
" # add row 3 of the new matrix A_diag to the row 0, replacing row 0\n",
" A_diag = AddRows(A_diag, 3, 0, 1)\n",
" \n",
" # multiply row 2 of the new matrix A_diag by -4 and add it to the row 1\n",
" A_diag = AddRows(A_diag, 2, 1, -4)\n",
" \n",
" # add row 2 of the new matrix A_diag to the row 0, replacing row 0\n",
" A_diag = AddRows(A_diag, 2, 0, 1)\n",
" \n",
" # multiply row 1 of the new matrix A_diag by -2 and add it to the row 0\n",
" A_diag = AddRows(A_diag, 1, 0, -2)\n",
" ### END CODE HERE ###\n",
" \n",
" return A_diag\n",
" \n",
"A_diag = ref_to_diagonal(A_ref)\n",
"\n",
"print(A_diag)"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"##### __Expected Output__\n",
"\n",
"```Python\n",
"[[1 0 0 0 2]\n",
" [0 1 0 0 3]\n",
" [0 0 1 0 4]\n",
" [0 0 0 1 1]]\n",
"```"
]
},
{
"cell_type": "code",
"execution_count": 42,
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"\u001b[92m All tests passed\n"
]
}
],
"source": [
"# Test your solution\n",
"w2_unittest.test_ref_to_diagonal(ref_to_diagonal)"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Congratulations! You have finished first assignment in this Course."
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {
"tags": [
"graded"
]
},
"outputs": [],
"source": []
}
],
"metadata": {
"accelerator": "GPU",
"colab": {
"collapsed_sections": [],
"name": "C1_W1_Assignment_Solution.ipynb",
"provenance": []
},
"coursera": {
"schema_names": [
"AI4MC1-1"
]
},
"grader_version": "1",
"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.8.8"
},
"toc": {
"base_numbering": 1,
"nav_menu": {},
"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": true,
"toc_window_display": false
},
"vscode": {
"interpreter": {
"hash": "478841ab876a4250505273c8a697bbc1b6b194054b009c227dc606f17fb56272"
}
}
},
"nbformat": 4,
"nbformat_minor": 1
}