Example:
| \[\begin{array}{ccccccccl}x_1&+&4x_2&+&x_3&\quad=\quad&1&(i)\\ 5x_1&+&4x_2&-&x_3&\quad=\quad&2&(ii)& x_1,x_2,x_3=?\\ 2x_1&+&x_2&+&x_3&\quad=\quad&0&(iii)\end{array}\] |
| \[ \begin{array}{cccccc} (i)+(ii)&\Rightarrow&6x_1+8x_2=3&|&\cdot5\\ & & & & &-\\ (ii)+(iii)&\Rightarrow&\underline{7x_1+5x_2=2}&|&\cdot8\\ &&-26x_1=-1\\ \rightarrow&x_1=\frac{1}{26}\\ \rightarrow&x_2=\frac{9}{26}\\ \rightarrow&x_3=-\frac{11}{26} \end{array}\] |
now in matrix notation:
| \[\left(\begin{array}{ccc}1&4&1\\ 5&4&-1\\ 2&1&1\end{array}\right)\left(\begin{array}{c}x_1\\x_2\\x_3\end{array}\right)=\left(\begin{array}{c}1\\2\\0\end{array}\right)\] |
solution:
| \[\left(\begin{array}{c}x_1\\x_2\\x_3\end{array}\right)=\underbrace{\left(\begin{array}{ccc}1&4&1\\ 5&4&-1\\ 2&1&1\end{array}\right)^{-1}}_{\mbox{Problem, inverse of coefficient matrix $\tilde A$}}\left(\begin{array}{c}1\\2\\0\end{array}\right)\] |
\begin{eqnarray*} \det(\tilde A)&=&-26\\\\ \tilde{A}^{-1}&=&-\frac{1}{26}\left(\begin{array}{ccc}5&-7&-3\\ -3&-1&7\\ -8&6&-16\end{array}\right)^\top=-\frac{1}{26}\left(\begin{array}{ccc}5&-3&-8\\-7&-1&6\\-3&7&-16\end{array}\right)\\ \Rightarrow\;\left(\begin{array}{c}x_1\\x_2\\x_3\end{array}\right)&=&-\frac{1}{26}\left(\begin{array}{ccc}5&-3&-8\\-7&-1&+6\\-3&+7&-16\end{array}\right)\left(\begin{array}{c}1\\2\\0\end{array}\right)=-\frac{1}{26}\vect{-1\\-9\\11}=\vect{\frac{1}{26}\\\\\frac{9}{26}\\\\\frac{-11}{26}}\end{eqnarray*}
In general: system of \(M\) linear equations with \(N\) variables \(x_1,\ldots,x_N\).
| \[\begin{array}{ccccccccc} a_{11}x_1&\;+\;&a_{12}x_2&\;+\;&\cdots&\;+\;&a_{1N}x_N&\;=\;&b_1\\ a_{21}x_1&\;+\;&a_{22}x_2&\;+\;&\cdots&\;+\;&a_{2N}x_N&\;=\;&b_2\\ \vdots&\;+\;&\vdots&\;+\;&\cdots&\;+\;&\vdots&\;=\;&\vdots\vdots\\ a_{M1}x_1&\;+\;&a_{M2}x_2&\;+\;&\cdots&\;+\;&a_{MN}x_N&\;=\;&b_M \end{array}\] |
Matrix-Notation: \(\qquad\tilde{A}\vec{x}=\vec{b}\)
| \[\tilde{A}\left(a_{jk}\right)\;M \times N,\quad\vec{x}=\vect{x_1\\\vdots\\x_N}\;N\times1,\quad\vec{b}=\vect{b_1\\\vdots\\b_M}\;M\times1\] |
different cases:
\(M=N\) and \(\det(\tilde A)\neq0\) then: solution given by \(\vec{x}=\tilde{A}^{-1}b\) (see above)
\(M=N\) and \(\det(\tilde{A})=0\)
\(\rightarrow\) in general no solution if \(\vec{b}\neq\vec{0}\)
\(\rightarrow\)
\(\vec{x}=\vec{0}\) trivial solution if \(\vec{b}=\vec{0}\) (homogeneous system) and further for
any non-trivial solution \(\vec{x}\) the vector \(\alpha\vec{x}\) is another solution. If \(\vec{x}^{(1)},\ldots,\vec{x}^{(k)}\) are \(k\) linear independent solutions than \(\vec{x}=k_1\vec{x}^{(1)}+\ldots+k_k\vec{x}^{(k)}\)
with arbitrary \(k_1,\ldots,k_k\) is another solution.
\(M \gt N\): more equations than variables\(\rightarrow\;\) in
general no solution
solutions only if equations are trivially dependent on each other
| \[\left.\begin{array}{l}x_1+x_2=0\\\\x_1+2x_2=1\\\\2x_1+2x_2=0\end{array}\right\}\Rightarrow\;M=3,\;N=2\mbox{ but effectively }M=N=2\] |
\(M \lt N\): more variables than system of equations ”over-determined
”\(\Rightarrow\;\) in general \(N-M\) variables free
or parameters
Example:
| \[\begin{array}{lclr}x_1+3x_2+3x_3+4x_4&=&1&(i)\\\\ -2x_1+3x_2-4x_3+x_4&=&2&(ii)\end{array} M=2,\;N=4\] |
| \[\begin{array}{cclcl} (i)-(ii)&\;\Rightarrow\;&3x_1+7x_3-3x_4=-1&\;\Rightarrow\;&x_1=-\frac{7}{3}x_3+x_4-\frac{1}{3}\\\\ 2(i)+(ii)&\;\Rightarrow\;&9x_2+2x_3+9x_4=4&\;\Rightarrow\;&x_2=-\frac{2}{9}x_3-x_4+\frac{4}{9}\end{array}\] |
\(x_3,x_4\) are free parameters.
Important Case: \(M=N\)
Cramer-Rule:
| \[\begin{array}{c}a_{11}x_1+\ldots+a_{1N}x_N=b_1\\\cdots\\a_{N1}x_1+\ldots+a_{NN}x_N=b_N\end{array}\] |
If \(\det(\tilde{A})\neq0\) then the solution is given by
| \[x_1=\frac{\det(\tilde{A_1})}{\det(\tilde{A})},\quad x_2=\frac{\det(\tilde{A_2})}{\det(\tilde{A})},\ldots,x_N=\frac{\det(\tilde{A_N})}{\det(\tilde{A})}\] |
where
| \[\begin{array}{cccl}\tilde{A}_j=\left(\begin{array}{cc}a_{11}&a_{12}\\a_{21}&a_{22}\\\vdots&\vdots\\a_{N1}&a_{N2}\end{array}\right.&\begin{array}{c}b_1\\b_2\\\vdots\\b_N\end{array} &\left.\begin{array}{cc}\cdots&a_{1N}\\\cdots&a_{2N}\\ &\vdots\\\cdots&a_{NN}\end{array}\right)&\mbox{thus not very efficient for larger systems!!}\\ &\uparrow& \end{array}\] |
i.e. in the \(j\)-th column the vector \(\vect{b_{1}\\\vdots\\b_{N}}\)
is placed instead of \(\vect{a_{jj}\\\vdots\\a_{Nj}}\)
Example
as before:
\begin{eqnarray*}x_1+4x_2+x_3&=&1\\5x_1+4x_2-x_3&=&2\\2x_1+x_2+x_3&=&0\end{eqnarray*}
| \[\begin{array}{ll}\det(\tilde{A}) = -26\neq0 & \det(\tilde{A}_1)=\left|\begin{array}{ccc}1&4&1\\2&4&-1\\0&1&1\end{array}\right|=-1\\\\ \det(\tilde{A}_2)=\left|\begin{array}{ccc}1&1&1\\5&2&-1\\2&0&1\end{array}\right|=-9 \qquad & \det(\tilde{A}_2)=\left|\begin{array}{ccc}1&4&1\\5&4&2\\2&1&0\end{array}\right|=11 \end{array}\] |
| \[\Rightarrow \qquad x_1=\frac{1}{26},\quad x_2=\frac{9}{26},\quad x_3=-\frac{11}{26}\] |
There are efficient algorithms for large systems with numerically and analytically (Gauß Algorithm etc.) They all rely on the transformations of the matrix \(\tilde A\) with respect to \(\vec{b}\).
|
|
|
|
© J. Carstensen (Math for MS)