diff options
Diffstat (limited to 'tutorials/module_3/3_system_of_equations.md')
| -rw-r--r-- | tutorials/module_3/3_system_of_equations.md | 354 |
1 files changed, 334 insertions, 20 deletions
diff --git a/tutorials/module_3/3_system_of_equations.md b/tutorials/module_3/3_system_of_equations.md index 3e6fad9..b30ce78 100644 --- a/tutorials/module_3/3_system_of_equations.md +++ b/tutorials/module_3/3_system_of_equations.md @@ -1,7 +1,7 @@ # Linear Equations Let's consider an linear equation $$ -ax=b +y = m x + b $$ where $a$ and $b$ are two known constants we can solve for $x$ easily. @@ -9,45 +9,284 @@ where $a$ and $b$ are two known constants we can solve for $x$ easily. [] # Linear Algebra -Although this isn't a course in linear algebra we are going to use some fundamental concepts from linear algebra to solve systems of equations. - -If you haven't taken linear algebra before, it is the study of linear equations. These equations can be represented in the form of matrices. Let's say we have a system of equation +Although this isn't a course in linear algebra we are going to use some fundamental concepts from linear algebra to solve systems of equations. If you haven't taken linear algebra before, it is the study of linear equations. These equations can be represented in the form of matrices. Matrices are rectangular arrays of numbers arranged in rows and columns. They are widely used in both engineering and computer science. Let's say we have the following system of equation. $$ \begin{cases} a_{11} x_1 + a_{12} x_2 + a_{13} x_3 = b_1 \\ a_{21} x_1 + a_{22} x_2 + a_{23} x_3 = b_2 \\ a_{31} x_1 + a_{32} x_2 + a_{33} x_3 = b_3 \end{cases} +\tag{1} $$ -We can re-write this into matrix form by creating an $A$ matrix of all $a_{nn}$ values and a $b$ vector as follows - +Where both the $a_{nn}$ coefficients and the $b_n$ variables are all known. We can re-write this system into a matrix form by creating an $A$ matrix of all $a_{nn}$ values and a vector in the form of: $$ - A = \left[ {\begin{array}{cc} a_{11} & a_{12} & a_{13}\\ a_{21} & a_{22} & a_{23}\\ a_{31} & a_{32} & a_{33}\\ \end{array} } \right] + \left[ {\begin{array}{cc} + x_{1}\\ + x_{2}\\ + x_{3}\\ + \end{array} } \right] += + \left[ {\begin{array}{cc} + b_{1}\\ + b_{2}\\ + b_{3}\\ + \end{array} } \right] + \tag{2} $$ -and +where $$ - b = + \left[ {\begin{array}{cc} + a_{11} & a_{12} & a_{13}\\ + a_{21} & a_{22} & a_{23}\\ + a_{31} & a_{32} & a_{33}\\ + \end{array} } \right] + = A, \left[ {\begin{array}{cc} b_{1}\\ b_{2}\\ b_{3}\\ \end{array} } \right] + = b $$ -to get, +we can also write the equation in it's simplified form $$ Ax=b +\tag{3} $$ -How does this work? Matrix Math. The +Take a close look at equation 1 and 2 and look at their similarity and differences. Notice how the pattern of the $A$ matrix and $b$ vector and follow the same patterns as however the elements of the $x$ vector ($x_1$,$x_2$,$x_3$) are flipped vertically. This is because of how we multiple matrices + +## Matrix operations in python + +- Matrices of the same size can be added or subtracted element-wise: +- Multiply a matrix by a scalaryields a new matrix where every element is multiplied by the scalar. +- The determinant of a matrix is +- **Identity Matrix $I$**: Square matrix with 1’s on the diagonal and 0’s elsewhere. +- **Inverse Matrix $A^{-1}$**: Satisfies $AA^{-1} = I$. (Only square, non-singular matrices have inverses.) +### Matrix Multiplication + +If $A$ is $m \times n$ and $B$ is $n \times p$, their product $C = AB$ is an $m \times p$ matrix: + +cij=∑k=1naikbkjc_{ij} = \sum_{k=1}^n a_{ik} b_{kj} + +**Example:** +$$ +[1234][5678]=[1⋅5+2⋅71⋅6+2⋅83⋅5+4⋅73⋅6+4⋅8]=[19224350]\begin{bmatrix} 1 & 2 \\ 3 & 4 \end{bmatrix} \begin{bmatrix} 5 & 6 \\ 7 & 8 \end{bmatrix} = \begin{bmatrix} 1 \cdot 5 + 2 \cdot 7 & 1 \cdot 6 + 2 \cdot 8 \\ 3 \cdot 5 + 4 \cdot 7 & 3 \cdot 6 + 4 \cdot 8 \end{bmatrix} = \begin{bmatrix} 19 & 22 \\ 43 & 50 \end{bmatrix} +$$ + + +## 1) Matrix Math in Python +```python +import numpy as np +np.set_printoptions(suppress=True) # nicer printing +``` + +--- + + + +Let's +```python +A = np.array([[1, 3], + [2, 4]]) # 2x2 +B = np.array([[5, 6], + [7, 8]]) # 2x2 +A.shape, B.shape + +b = np.array([3, 5]) +b.shape + +# Addition and Subtraction of same shapes +A + B +A - B + +# Scalar Multiplication +3*A + +5*B + +# Matrix Multiplication +mat_mult = A @ B -Matrix definition +# Transpose +B.T + +# Identity and Inverse matrix + +I = np.eye(2) +A_inv = np.linalg.inv(A) + +A @ A_inv, A_inv @ A + +# Determinants + +detA = np.linalg.det(A) +detB = np.linalg.det(B) +detA, detB + + + +``` + + + +--- + +## 7) Determinant + +For $2\times2$, + +$\det\begin{bmatrix}a&b\\ c&d\end{bmatrix}=ad-bc$. + +```python +detA = np.linalg.det(A) +detB = np.linalg.det(B) +detA, detB +``` + + +## 8) Solve Linear Systems $Ax=b$ + +```python +A = np.array([[3., 2., -1.], + [2., -2., 4.], + [-1., 0.5, -1.]]) +b = np.array([1., -2., 0.]) + +x = np.linalg.solve(A, b) # preferred over inv(A)@b +x, np.allclose(A @ x, b) +``` + +--- + +## 9) Eigenvalues & Eigenvectors + +Solve $A\mathbf{v}=\lambda \mathbf{v}$ (square $A$). + +```python +A = np.array([[4., 2.], + [1., 3.]]) +eigvals, eigvecs = np.linalg.eig(A) +eigvals, eigvecs # columns of eigvecs are eigenvectors +``` + +**Verify one pair $(\lambda, v)$** + +```python +lam, v = eigvals[0], eigvecs[:,0] +np.allclose(A @ v, lam * v) +``` + +--- + +## 10) Norms (size/length measures) + +```python +x = np.array([3., -4., 12.]) +vec_L2 = np.linalg.norm(x, ord=2) # Euclidean +vec_L1 = np.linalg.norm(x, ord=1) +vec_Linf= np.linalg.norm(x, ord=np.inf) + +M = np.array([[1., 2.], + [3., 4.]]) +fro = np.linalg.norm(M, 'fro') # Frobenius (matrix) +vec_L2, vec_L1, vec_Linf, fro +``` + +--- + +## 11) Orthogonality & Projections (quick demo) + +```python +u = np.array([1., 2., -2.]) +v = np.array([2., -1., 0.]) + +dot = u @ v +is_orthogonal = np.isclose(dot, 0.0) + +# projection of u onto v +proj_u_on_v = (u @ v) / (v @ v) * v +dot, is_orthogonal, proj_u_on_v +``` + +--- + +## 12) Example Mini-Lab + +1. Compute $2A - B$ for + + +A=[1324],B=[5678].A=\begin{bmatrix}1&3\\2&4\end{bmatrix},\quad B=\begin{bmatrix}5&6\\7&8\end{bmatrix}. + +```python +A = np.array([[1,3],[2,4]]) +B = np.array([[5,6],[7,8]]) +result = 2*A - B +result +``` + +2. Verify $A(A^{-1})\approx I$ and report the determinant of $A$. + + +```python +A_inv = np.linalg.inv(A) +check = np.allclose(A @ A_inv, np.eye(2)) +detA = np.linalg.det(A) +check, detA +``` + +3. Solve the system $Ax=b$ with + + +A=[4123],b=[10].A=\begin{bmatrix}4&1\\2&3\end{bmatrix},\quad b=\begin{bmatrix}1\\0\end{bmatrix}. + +```python +A = np.array([[4.,1.], + [2.,3.]]) +b = np.array([1.,0.]) +x = np.linalg.solve(A,b) +x, A @ x +``` + +--- + +### Tips for Students + +- Prefer `np.linalg.solve(A,b)` over `np.linalg.inv(A) @ b` for **speed and numerical stability**. +- Watch out for **singular** or **ill-conditioned** matrices (determinant near 0). +- Use `np.allclose` when comparing float results. +--- + + + +### Problem 1 +Re-write the following systems of equation in matrix form to normal algebraic equations. + +$$ + \left[ {\begin{array}{cc} + 3 & 5 & 7\\ + 2 & 1 & 3\\ + 2 & 3 & 6\\ + \end{array} } \right] + \left[ {\begin{array}{cc} + x_{1}\\ + x_{2}\\ + x_{3}\\ + \end{array} } \right] += + \left[ {\begin{array}{cc} + 24\\ + 52\\ + 12\\ + \end{array} } \right] +$$ ## Problem 1 ```python @@ -68,27 +307,102 @@ print(x) -# Systems of Equations +# Systems of Linear Equations + +## Techniques to solve Systems of Equations +In this section our goals is to learn some algorithms that help solve system of equations in python. + + +Matrix Determinate -## Working with Systems of Equations -Matrix Determinates Cramer's Rule - -Elimination + +Now let's try to solve a problem think about how we solve a system of two linear equations by hand. +[example problem] + +You've probably learned to use one of the following methods - substitution, graphical or elimination. Is there a way to think about this algorithmically. + +Step 1 - Subtract the two +$$ +\begin{cases} +a_{11} x_1 + a_{12} x_2 = b_1 \\ +a_{21} x_1 + a_{22} x_2 = b_2 +\end{cases} +$$ +$$ +a_{11} x_1 + a_{12} x_2 + a_{13} x_3 = b_1 \\ +a_{21} x_1 + a_{22} x_2 + a_{23} x_3 = b_2 +$$ + + +<img + style="display: block; + margin-left: auto; + margin-right: auto; + width: 60%;" + src="fw_elim_bw_sub.png" + alt="Forward Elimination then Backwards Substitution"> + ### Forward Elimination + ### Back Substitution + ### Naive Gauss Elimination +```python +def gaussian_elimination_naive(A, b): + A = A.astype(float).copy() + b = b.astype(float).copy() + n = len(b) + # Forward elimination + for k in range(n-1): + if np.isclose(A[k,k], 0.0): + raise ZeroDivisionError("Zero pivot encountered (naïve). Use pivoting.") + for i in range(k+1, n): + m = A[i,k]/A[k,k] + A[i, k:] -= m * A[k, k:] + b[i] -= m * b[k] + # Back substitution + x = np.zeros(n) + for i in range(n-1, -1, -1): + s = A[i, i+1:] @ x[i+1:] + x[i] = (b[i]-s)/A[i,i] + return x +``` ### Gauss Elimination - -### LU Decomposition +```python +def gaussian_elimination_pp(A, b): + A = A.astype(float).copy() + b = b.astype(float).copy() + n = len(b) + # Forward elimination with partial pivoting + for k in range(n-1): + piv = k + np.argmax(np.abs(A[k:, k])) + if np.isclose(A[piv, k], 0.0): + raise np.linalg.LinAlgError("Matrix is singular or nearly singular.") + if piv != k: # row swap + A[[k, piv]] = A[[piv, k]] + b[[k, piv]] = b[[piv, k]] + for i in range(k+1, n): + m = A[i,k]/A[k,k] + A[i, k:] -= m * A[k, k:] + b[i] -= m * b[k] + # Back substitution + x = np.zeros(n) + for i in range(n-1, -1, -1): + s = A[i, i+1:] @ x[i+1:] + x[i] = (b[i]-s)/A[i,i] + return x +``` ## Problem 1 -## Problem 2 +### Problem 2 + + # LU Decomposition -## ## Problem 1 |