m |
|||
(One intermediate revision by the same user not shown) | |||
Line 17: | Line 17: | ||
The coefficients of the unknowns form a [[Matrix]] - a rectangular array of numbers: | The coefficients of the unknowns form a [[Matrix]] - a rectangular array of numbers: | ||
− | * | + | * <math>A = \begin{bmatrix} |
a_{11} & a_{12} & ... & a_{1n}\\ | a_{11} & a_{12} & ... & a_{1n}\\ | ||
a_{21} & a_{22} & ... & a_{2n}\\ | a_{21} & a_{22} & ... & a_{2n}\\ | ||
\vdots & \vdots & \vdots & \vdots \\ | \vdots & \vdots & \vdots & \vdots \\ | ||
a_{m1} & a_{m2} & ... & a_{mn} | a_{m1} & a_{m2} & ... & a_{mn} | ||
− | \end{bmatrix} | + | \end{bmatrix}</math> |
* We call this matrix $A$, it's $m \times n$ matrix: with $m$ rows and $n$ columns | * We call this matrix $A$, it's $m \times n$ matrix: with $m$ rows and $n$ columns | ||
The unknowns themselves form a column vector $\mathbf{x}$, and the ... form a column vector $b$ | The unknowns themselves form a column vector $\mathbf{x}$, and the ... form a column vector $b$ | ||
− | * | + | * <math>\mathbf{x} = \begin{bmatrix} |
x_1 \\ | x_1 \\ | ||
x_2 \\ | x_2 \\ | ||
\vdots \\ | \vdots \\ | ||
x_n \\ | x_n \\ | ||
− | \end{bmatrix} | + | \end{bmatrix}</math>, <math>\mathbf{b} = \begin{bmatrix} |
b_1 \\ | b_1 \\ | ||
b_2 \\ | b_2 \\ | ||
\vdots \\ | \vdots \\ | ||
b_m \\ | b_m \\ | ||
− | \end{bmatrix} | + | \end{bmatrix}</math>, |
* they're both column vectors, $\mathbf{x}$ has size $n$, and $\mathbf{b}$ has size $m$ | * they're both column vectors, $\mathbf{x}$ has size $n$, and $\mathbf{b}$ has size $m$ | ||
* can write them as rows using the transposition notation: $\mathbf{x} = [x_1, x_2, ..., x_n]^T$ (but they still remain column vectors) | * can write them as rows using the transposition notation: $\mathbf{x} = [x_1, x_2, ..., x_n]^T$ (but they still remain column vectors) | ||
Line 55: | Line 55: | ||
Matrix form: | Matrix form: | ||
− | * | + | * <math>\begin{bmatrix} |
2 & -1 \\ | 2 & -1 \\ | ||
-1 & 2 | -1 & 2 | ||
Line 63: | Line 63: | ||
0 \\ | 0 \\ | ||
3 | 3 | ||
− | \end{bmatrix} | + | \end{bmatrix}</math> |
We can see this in two possible ways: | We can see this in two possible ways: | ||
Line 86: | Line 86: | ||
=== Column Picture === | === Column Picture === | ||
We have two vectors: | We have two vectors: | ||
− | * | + | * <math>x \begin{bmatrix} |
2 \\ | 2 \\ | ||
-1 | -1 | ||
Line 95: | Line 95: | ||
0 \\ | 0 \\ | ||
3 | 3 | ||
− | \end{bmatrix} | + | \end{bmatrix}</math> |
− | We need to combine first two vectors | + | We need to combine first two vectors <math>v = \begin{bmatrix} |
2 \\ | 2 \\ | ||
-1 | -1 | ||
− | \end{bmatrix} | + | \end{bmatrix}</math> and <math>u = \begin{bmatrix} |
-1 \\ | -1 \\ | ||
2 | 2 | ||
− | \end{bmatrix} | + | \end{bmatrix}</math> so they form <math>\begin{bmatrix} |
0 \\ | 0 \\ | ||
3 | 3 | ||
− | \end{bmatrix} | + | \end{bmatrix}</math> |
Line 198: | Line 198: | ||
* so we can the solution as the Nullspace $C(A)$ but shifted away from the origin by $x_p$ | * so we can the solution as the Nullspace $C(A)$ but shifted away from the origin by $x_p$ | ||
* note that this solution doesn't form a subspace | * note that this solution doesn't form a subspace | ||
+ | |||
Line 221: | Line 222: | ||
Solution to $A \mathbf x = \mathbf b$: | Solution to $A \mathbf x = \mathbf b$: | ||
* if the solution exists (i.e. $\mathbf b \in C(A)$) then this solution is unique | * if the solution exists (i.e. $\mathbf b \in C(A)$) then this solution is unique | ||
− | * so we have either 0 solutions or 1 | + | * so we have either 0 solutions or 1 |
− | * No solution? Can approximate it with [[Normal Equation]] | + | |
+ | |||
+ | === [[Gaussian Elimination]] and [[LU Decomposition]] === | ||
+ | Solving $A\mathbf x = \mathbf b$ | ||
+ | * As metioned earlier - need to reduce it to RREF | ||
+ | * Can do that with Gaussian Elimination via LU Decomposition | ||
+ | * Let $LU = A$ | ||
+ | * then $A \mathbf x = \mathbf b$ becomes $LU \mathbf x = \mathbf b$ | ||
+ | * Now let $U \mathbf x = \mathbf y$ and $L \mathbf y = \mathbf x$ | ||
+ | * With this substitution we need to solve two equations now, but they are simple because $L$ is lower-diagonal and $U$ is upper-diagonal | ||
+ | |||
+ | |||
+ | |||
+ | === No Solution === | ||
+ | No solution? | ||
+ | * Can approximate it with [[Normal Equation]] | ||
+ | * That would be the [[Ordinary Least Squares|Least Squares]] solution | ||
The fundamental problem of Linear Algebra is solving a system of Linear Equations.
Suppose we have a system with $m$ equations and $n$ unknowns:
$\left\{\begin{matrix} a_{11} x_1 + a_{12} x_2 + \ ... \ + a_{1n} x_n = b_1\\ a_{21} x_1 + a_{22} x_2 + \ ... \ + a_{2n} x_n = b_2\\ \vdots \\ a_{m1} x_1 + a_{22} x_2 + \ ... \ + a_{mn} x_n = b_m\\ \end{matrix}\right.$
The coefficients of the unknowns form a Matrix - a rectangular array of numbers:
The unknowns themselves form a column vector $\mathbf{x}$, and the ... form a column vector $b$
So the system of linear equations can be expressed in a matrix form as $A\mathbf{x} = \mathbf{b}$
Suppose we have the following system of linear equations:
$\left\{\begin{matrix} 2x - y = 0\\ -x + 2y = 3 \end{matrix}\right.$
Matrix form:
We can see this in two possible ways:
We have two lines:
The solution is $[x, y]^T = [1, 2]^T$
For 3 and more dimensions, we have (hyper)planes instead of lines.
We have two vectors:
We need to combine first two vectors [math]v = \begin{bmatrix} 2 \\ -1 \end{bmatrix}[/math] and [math]u = \begin{bmatrix} -1 \\ 2 \end{bmatrix}[/math] so they form [math]\begin{bmatrix} 0 \\ 3 \end{bmatrix}[/math]
I.e. we want to find a Linear Combination of these columns.
import matplotlib.pylab as plt import numpy as np class Line: def __init__(self, slope, intercept): self.slope = slope self.intercept = intercept def calculate(self, x1): x2 = x1 * self.slope + self.intercept return x2 line1 = Line(2, 0) line2 = Line(0.5, 1.5) a = np.array([-6, 6]) plt.plot(a, line1.calculate(a), color='red', marker='') plt.plot(a, line2.calculate(a), color='blue', marker='') plt.scatter([1], [2]) plt.grid() plt.axis('equal') plt.ylim([-1, 3]) plt.xlim([-1, 3])
import matplotlib.pylab as plt plt.axis('equal') plt.quiver([0, 0, 0], [0, 0, 0], [-1, 2, 0], [2, -1, 3], color=['red', 'blue', 'black'], angles='xy', scale_units='xy', scale=1) plt.quiver([2], [-1], [-2], [4], color='red', width=0.005, scale=1, angles='xy', scale_units='xy') plt.grid() plt.ylim([-2, 5]) plt.xlim([-4, 4]) plt.show()
How we can solve the system $A \mathbf x = \mathbf b$?
Vector Solution: the solution found with the column picture
Matrix Solution
Such systems are called homogeneous - see Homogeneous Systems of Linear Equations
Let $A$ be $n \times m$ matrix of rank $r$
Steps:
Let $A$ be $m \times n$ matrix of rank $r$
Full rank = $r$ is as big as it can be
Nullspace $N(A)$?
Solution to $A \mathbf x = \mathbf b$:
Solving $A\mathbf x = \mathbf b$
No solution?
for which $\mathbf b$ we can solve $A \mathbf x = \mathbf b$?
Zero or $\infty$ solutions