Differences

This shows you the differences between two versions of the page.

--- lecture_5 [2015/02/04 12:00] – rupert
+++ lecture_5 [2017/02/07 10:11] (current) – [Gaussian elimination] rupert
@@ Line 21: / Line 21: @@
   - $x_2$ and $x_5$ are free, so set $x_2=s$ where $s\in \mathbb{R}$ and $x_5=t$ where $t\in \mathbb{R}$
   - Working from the bottom: $$ x_4+3x_5=4\implies x_4=4-3x_5=4-3t$$ $$ x_3+x_4+x_5=5\implies x_3=5-x_4-x_5=5-(4-3t)-t=1+2t$$ $$ x_1+2x_2+3x_3=8\implies x_1=8-2x_2-3x_3=8-2s-3(1+2t)=5-2s-6t.$$
+So \begin{align*} x_1&=5-2s-6t\\x_2&=s\\x_3&=1+2t\\x_4&=4-3t\\x_5&=t\end{align*}
+where $s$ and $t$ are free parameters, i.e. $s,t\in \mathbb{R}$.
 Writing this solution in vector form gives:
@@ Line 28: / Line 31: @@
 Note that the solution set is a subset of $\mathbb{R}^5$, which is $5$-dimensional space; and the solution set is $2$-dimensional, because there are $2$ free parameters.
+==== Gaussian elimination ====
+We've seen that putting a matrix into REF (or even better, in RREF) makes it easier to solve equations.
+{{page>gaussian elimination algorithm}}
+=== Example ===
+Use Gaussian elimination to solve the linear system
+\begin{align*} 2x+y+3z+4w&=27\\ x+2y+3z+2w&=30\\x+y+3z+w&=25\end{align*}
+== Solution 1 ==
+We put the augmented matrix into REF:
+\begin{align*}
+\def\go#1#2#3{\begin{bmatrix}#1\\#2\\#3\end{bmatrix}}
+\def\ar#1{\\[6pt]\xrightarrow{#1}&}
+&\go{2&1&3&4&27}{1&2&3&2&30}{1&1&3&1&25}
+\ar{\text{reorder rows (to avoid division)}}
+\go{1&1&3&1&25}{1&2&3&2&30}{2&1&3&4&27}
+\ar{R2\to R2-R1\text{ and }R3\to R3-2R2}
+\go{1&1&3&1&25}{0&1&0&1&5}{0&-1&-3&2&-23}
+\ar{R3\to R3+R2}
+\go{1&1&3&1&25}{0&1&0&1&5}{0&0&-3&3&-18}
+\ar{R3\to-\tfrac13R3}
+\go{1&1&3&1&25}{0&1&0&1&5}{0&0&1&-1&6}
+\end{align*}
+This is in REF. There are leading entries in the columns for $x,y,z$ but not for $w$, so $w=t$ is a free variable (where $t\in\mathbb{R}$). Now
+$$ z-w=6\implies z=6+w=6+t$$
+$$ y+w=5\implies y=5-w=5-t$$
+$$ x+y+3z+w=25\implies x=25-y-3z-w=25-(5-t)-3(6+t)-t=2-3t.$$
+So
+$$ \begin{bmatrix}x\\y\\z\\w\end{bmatrix}=\begin{bmatrix} 2\\5\\6\\0\end{bmatrix}+t\begin{bmatrix}-3\\-1\\1\\1\end{bmatrix},\quad t\in\mathbb{R}.$$
+== Solution 2 ==
+We put the augmented matrix into RREF.
+\begin{align*}
+\def\go#1#2#3{\begin{bmatrix}#1\\#2\\#3\end{bmatrix}}
+\def\ar#1{\\[6pt]\xrightarrow{#1}&}
+&\go{2&1&3&4&27}{1&2&3&2&30}{1&1&3&1&25}
+\ar{\text{do everything as above}}
+\go{1&1&3&1&25}{0&1&0&1&5}{0&0&1&-1&6}
+\ar{R1\to R1-3R3}
+\go{1&1&0&4&7}{0&1&0&1&5}{0&0&1&-1&6}
+\ar{R1\to R1-R2}
+\go{1&0&0&3&2}{0&1&0&1&5}{0&0&1&-1&6}
+\end{align*}
+This is in RREF. There are leading entries in the columns for $x,y,z$ but not for $w$, so $w=t$ is a free variable (where $t\in\mathbb{R}$). Now
+$$ z-w=6\implies z=6+w=6+t$$
+$$ y+w=5\implies y=5-w=5-t$$
+$$ x+3w=2\implies x=2-3w=2-3t$$
+So
+$$ \begin{bmatrix}x\\y\\z\\w\end{bmatrix}=\begin{bmatrix} 2\\5\\6\\0\end{bmatrix}+t\begin{bmatrix}-3\\-1\\1\\1\end{bmatrix},\quad t\in\mathbb{R}.$$