Chapter 10, Problem 3P

(a) Solve the following system of equations by LU decomposition without pivoting

$\begin{array}{l}8x_1+4x_2-x_3=11\\ -2x_1+5x_2+x_3=4\\ 2x_1-x_2+6x_3=7\end{array}$

(b) Determine the matrix inverse. Check your results by verifying that $\left[A\right]{\left[A\right]}^{-1}=\left[l\right]$.

To determine

To calculate: The solution of the system of equations given below by LU decomposition without pivoting.

$\begin{array}{c}8x_1+4x_2-x_3=11\\ -2x_1+5x_2+x_3=4\\ 2x_1-x_2+6x_3=7\end{array}$

Answer to Problem 3P

Solution:

The solution of the system of equations is $x_1=1,x_2=1\text{and}{x}_3=1$.

Explanation of Solution

Given:

The system of equations,

$\begin{array}{c}8x_1+4x_2-x_3=11\\ -2x_1+5x_2+x_3=4\\ 2x_1-x_2+6x_3=7\end{array}$

Formula used:

(1) The forward substitution equations for L can be expressed as,

$\left[L\right]\left[D\right]=\left[B\right]$

(2) The backward substitution equation for U can be expressed as,

$\left[U\right]\left[X\right]=\left[D\right]$

Calculation:

Consider the system of equations,

$8x_1+4x_2-x_3=11$…… (1)

$-2x_1+5x_2+x_3=4$…… (2)

$2x_1-x_2+6x_3=7$ …… (3)

The coefficient $a_{21}$ is eliminated by multiplying equation (1) by $f_{21}=\frac{a_{21}}{a_{11}}$,

$f_{21}=\frac{-2}{8}$

And subtracting the result from equation (2).

Thus, multiply equation (1) by $\left(\frac{-2}{8}\right)$,

$\begin{array}{c}8\left(\frac{-2}{8}\right)x_1+4\left(\frac{-2}{8}\right)x_2-\left(\frac{-2}{8}\right)x_3=11\left(\frac{-2}{8}\right)\\ -2x_1-x_2+0.25x_3=-\frac{22}{8}\end{array}$

Now subtract this equation from equation (2),

$\begin{array}{c}-2x_1+5x_2+x_3+2x_1+x_2-0.25x_3=4-\frac{22}{8}\\ 6x_2+0.75x_3=1.25\end{array}$ …… (4)

The coefficient $a_{31}$ is eliminated by multiplying equation (1) by $f_{31}=\frac{a_{31}}{a_{11}}$,

$f_{31}=\frac{2}{8}$

And subtracting the result from equation (3).

Thus, multiply equation (1) by $\left(\frac{2}{8}\right)$,

$\begin{array}{c}8\left(\frac{2}{8}\right)x_1+4\left(\frac{2}{8}\right)x_2-\left(\frac{2}{8}\right)x_3=11\left(\frac{2}{8}\right)\\ 2x_1+x_2-0.25x_3=\frac{22}{8}\end{array}$

Now subtract this equation from equation (3),

$\begin{array}{c}2x_1-x_2+6x_3-2x_1-x_2+0.25x_3=7-\frac{22}{8}\\ -2x_2+6.25x_3=4.25\end{array}$ …… (5)

Now the set of equations is,

$\begin{array}{c}8x_1+4x_2-x_3=11\\ 6x_2+0.75x_3=1.25\\ -2x_2+6.25x_3=4.25\end{array}$

The factors $f_{21}$ and $f_{31}$ can be stored in $a_{21}$ and $a_{31}$.

$\left[\begin{array}{ccc}8& 4& -1\\ -0.25& 6& 0.75\\ 0.25& -2& 6.25\end{array}\right]$

The coefficient $a_{32}$ is eliminated by multiplying equation (4) by $f_{32}=\frac{{a^{\prime }}_{32}}{{a^{\prime }}_{22}}$,

$\begin{array}{c}{f}_{32}=\frac{-2}{6}\\ =-0.33333\end{array}$

And subtracting the result from equation (5). Thus, multiply equation (4) by $\left(\frac{-2}{6}\right)$,

$\begin{array}{c}6\left(\frac{-2}{6}\right)x_2+0.75\left(\frac{-2}{6}\right)x_3=1.25\left(\frac{-2}{6}\right)\\ -2x_2-0.25x_3=-0.41666\end{array}$

Now, subtract this equation from equation (5),

$\begin{array}{c}-2x_2+6.25x_3+2x_2+0.25x_3=4.25+0.41666\\ 6.5x_3=4.6666\end{array}$ …… (6)

The factor $f_{32}$ can be stored in $a_{32}$. Thus, the matrix obtained is:

$\left[\begin{array}{ccc}8& 4& -1\\ -0.25& 6& 0.75\\ 0.25& -0.33333& 6.5\end{array}\right]$

Therefore, the LU decomposition is

$\left[L\right]=\left[\begin{array}{ccc}1& 0& 0\\ -0.25& 1& 0\\ 0.25& -0.33333& 1\end{array}\right]\left[U\right]=\left[\begin{array}{ccc}8& 4& -1\\ 0& 6& 0.75\\ 0& 0& 6.5\end{array}\right]$

Now, to find the solution of the given system:

The forward substitution equations for L can be expressed as,

$\left[L\right]\left[D\right]=\left[B\right]$

$\left[\begin{array}{ccc}1& 0& 0\\ -0.25& 1& 0\\ 0.25& -0.33333& 1\end{array}\right]\left\{\begin{array}{l}{d}_1\\ d_2\\ d_3\end{array}\right\}=\left\{\begin{array}{l}11\\ 4\\ 7\end{array}\right\}$

Solve for $d_1$,

$d_1=11$

Solve for $d_2$,

$\begin{array}{c}-0.25d_1+d_2=4\\ d_2=4+0.25d_1\\ d_2=4+0.25\left(11\right)\\ d_2=6.75\end{array}$

Solve for $d_3$,

$\begin{array}{c}0.25d_1-0.33333d_2+d_3=7\\ d_3=7-0.25d_1+0.33333d_2\\ d_3=7-0.25\left(11\right)+0.33333\left(6.75\right)\\ d_3=6.5\end{array}$

Thus, $d_1=11,d_2=6.75\text{and}{d}_3=6.5$. That is, ${\left[D\right]}^T=\left[\begin{array}{ccc}11& 6.75& 6.5\end{array}\right]$.

Now, perform backward substitution:

$\begin{array}{l}\left[U\right]\left[X\right]=\left[D\right]\\ \left[\begin{array}{ccc}8& 4& -1\\ 0& 6& 0.75\\ 0& 0& 6.5\end{array}\right]\left[\begin{array}{l}{x}_1\\ x_2\\ x_3\end{array}\right]=\left[\begin{array}{l}11\\ 6.75\\ 6.5\end{array}\right]\end{array}$

Solve for $x_3$,

$\begin{array}{c}6.5x_3=6.5\\ x_3=\frac{6.5}{6.5}\\ x_3=1\end{array}$

Solve for $x_2$,

$\begin{array}{c}6x_2+0.75x_3=6.75\\ 6x_2=6.75-0.75\left(1\right)\\ x_2=\frac{6}{6}\\ x_2=1\end{array}$

Solve for $x_1$,

$\begin{array}{c}8x_1+4x_2-x_3=11\\ 8x_1=11-4\left(1\right)+\left(1\right)\\ x_1=\frac{8}{8}\\ x_1=1\end{array}$

Thus, $x_1=1,x_2=1\text{and}{x}_3=1$.

To determine

To calculate: The matrix inverse for given system of equations and check the result by verifying that $\left[A\right]{\left[A\right]}^{-1}=\left[I\right]$.

$\begin{array}{c}8x_1+4x_2-x_3=11\\ -2x_1+5x_2+x_3=4\\ 2x_1-x_2+6x_3=7\end{array}$

Answer to Problem 3P

Solution:

The matrix inverse is $A^{-1}=\left[\begin{array}{ccc}0.099359& -0.073718& 0.028846\\ 0.044872& 0.160256& -0.01923\\ 0.025641& 0.051282& 0.153846\end{array}\right]$.

Explanation of Solution

Given:

The system of equations,

$\begin{array}{c}8x_1+4x_2-x_3=11\\ -2x_1+5x_2+x_3=4\\ 2x_1-x_2+6x_3=7\end{array}$

And the LU decomposition is

$\left[L\right]=\left[\begin{array}{ccc}1& 0& 0\\ -0.25& 1& 0\\ 0.25& -0.33333& 1\end{array}\right]\left[U\right]=\left[\begin{array}{ccc}8& 4& -1\\ 0& 6& 0.75\\ 0& 0& 6.5\end{array}\right]$

Formula used:

(1) The forward substitution equations for L can be expressed as,

$\left[L\right]\left[D\right]=\left[B\right]$

(2) The backward substitution equation for U can be expressed as,

$\left[U\right]\left[X\right]=\left[D\right]$

Calculation:

Consider the given system of equations:

$\begin{array}{c}8x_1+4x_2-x_3=11\\ -2x_1+5x_2+x_3=4\\ 2x_1-x_2+6x_3=7\end{array}$

The matrix [A] is:

$\left[A\right]=\left[\begin{array}{ccc}8& 4& -1\\ -2& 5& 1\\ 2& -1& 6\end{array}\right]$

The lower and upper triangular matrix after decomposition are given as:

$\begin{array}{l}\left[A\right]=\left[L\right]\left[U\right]\\ =\left[\begin{array}{ccc}1& 0& 0\\ -0.25& 1& 0\\ 0.25& -0.33333& 1\end{array}\right]\left[\begin{array}{ccc}8& 4& -1\\ 0& 6& 0.75\\ 0& 0& 6.5\end{array}\right]\end{array}$

The first column of the inverse matrix can be determined by performing the forward substitution solution with a unit vector (with 1 in the first row) of right-hand-side vector.

The forward substitution equations for L can be expressed as,

$\left[L\right]\left[D\right]=\left[B\right]$

Where,

$\left[B\right]=\left[\begin{array}{c}1\\ 0\\ 0\end{array}\right]$

Determine D by substituting L and B as shown below,

$\left[\begin{array}{ccc}1& 0& 0\\ -0.25& 1& 0\\ 0.25& -0.33333& 1\end{array}\right]\left[\begin{array}{c}d1\\ d2\\ d3\end{array}\right]=\left[\begin{array}{c}1\\ 0\\ 0\end{array}\right]$

Solve for $d_1$,

$d_1=1$

Solve for $d_2$,

$\begin{array}{c}-0.25d_1+d_2=0\\ d_2=0.25d_1\\ d_2=0.25\left(1\right)\\ d_2=0.25\end{array}$

Solve for $d_3$,

$\begin{array}{c}0.25d_1-0.33333d_2+d_3=0\\ d_3=-0.25d_1+0.33333d_2\\ d_3=-0.25\left(1\right)+0.33333\left(0.25\right)\\ d_3=-0.16667\end{array}$

Hence, the values obtained are $d_1=1,d_2=0.25,\text{and}{d}_3=-0.16667$.

Solve with forward substitution of $D^T=\left[\begin{array}{ccc}1& 0.25& -0.16667\end{array}\right]$,

This vector can be used as right-hand side vector of equation,

$\begin{array}{c}\left[U\right]\left[X\right]=\left[D\right]\\ \left[\begin{array}{ccc}8& 4& -1\\ 0& 6& 0.75\\ 0& 0& 6.5\end{array}\right]\left[\begin{array}{c}{x}_1\\ x_2\\ x_3\end{array}\right]=\left[\begin{array}{c}1\\ 0.25\\ -0.16667\end{array}\right]\end{array}$

Solve the above matrix by back substitution, which gives the first column of the inverse matrix as:

$\left[X\right]=\left[\begin{array}{c}0.099359\\ 0.044872\\ 0.025641\end{array}\right]$

Similarly, the second column of the inverse matrix can be determined by performing the forward substitution solution with a unit vector (with 1 in the second row) of right-hand-side vector.

The forward substitution equations for L can be expressed as,

$\left[L\right]\left[D\right]=\left[B\right]$

Where,

$\left[B\right]=\left[\begin{array}{c}0\\ 1\\ 0\end{array}\right]$

Determine D by substituting L and B as shown below,

$\left[\begin{array}{ccc}1& 0& 0\\ -0.25& 1& 0\\ 0.25& -0.33333& 1\end{array}\right]\left[\begin{array}{c}d1\\ d2\\ d3\end{array}\right]=\left[\begin{array}{c}0\\ 1\\ 0\end{array}\right]$

Solve for $d_1$,

$d_1=0$

Solve for $d_2$,

$\begin{array}{c}-0.25d_1+d_2=1\\ d_2=1+0.25d_1\\ d_2=1+0.25\left(0\right)\\ d_2=1\end{array}$

Solve for $d_3$,

$\begin{array}{c}0.25d_1-0.33333d_2+d_3=0\\ d_3=-0.25d_1+0.33333d_2\\ d_3=-0.25\left(0\right)+0.33333\left(1\right)\\ d_3=0.33333\end{array}$

Hence, the values obtained are $d_1=0,d_2=1,\text{and}{d}_3=0.33333$.

Solve with forward substitution of $D^T=\left[\begin{array}{ccc}0& 1& 0.33333\end{array}\right]$,

This vector can be used as right-hand side vector of equation,

$\begin{array}{c}\left[U\right]\left[X\right]=\left[D\right]\\ \left[\begin{array}{ccc}8& 4& -1\\ 0& 6& 0.75\\ 0& 0& 6.5\end{array}\right]\left[\begin{array}{c}{x}_1\\ x_2\\ x_3\end{array}\right]=\left[\begin{array}{c}0\\ 1\\ 0.33333\end{array}\right]\end{array}$

Solve the above matrix by back substitution, which gives the second column of the inverse matrix as:

$\left[X\right]=\left[\begin{array}{c}-0.073718\\ 0.160256\\ 0.051282\end{array}\right]$

Similarly, the third column of the inverse matrix can be determined by performing the forward substitution solution with a unit vector (with 1 in the third row) of right-hand-side vector.

The forward substitution equations for L can be expressed as,

$\left[L\right]\left[D\right]=\left[B\right]$

Where,

$\left[B\right]=\left[\begin{array}{c}0\\ 0\\ 1\end{array}\right]$

Determine D by substituting L and B as shown below,

$\left[\begin{array}{ccc}1& 0& 0\\ -0.25& 1& 0\\ 0.25& -0.33333& 1\end{array}\right]\left[\begin{array}{c}d1\\ d2\\ d3\end{array}\right]=\left[\begin{array}{c}0\\ 0\\ 1\end{array}\right]$

Solve for $d_1$,

$d_1=0$

Solve for $d_2$,

$\begin{array}{c}-0.25d_1+d_2=0\\ d_2=0+0.25d_1\\ d_2=0+0.25\left(0\right)\\ d_2=0\end{array}$

Solve for $d_3$,

$\begin{array}{c}0.25d_1-0.33333d_2+d_3=1\\ d_3=1-0.25d_1+0.33333d_2\\ d_3=1-0.25\left(0\right)+0.33333\left(0\right)\\ d_3=1\end{array}$

Hence, the values obtained are $d_1=0,d_2=0\text{and}{d}_3=1$.

Solve with forward substitution of $D^T=\left[\begin{array}{ccc}0& 0& 1\end{array}\right]$,

This vector can be used as right-hand side vector of equation,

$\begin{array}{c}\left[U\right]\left[X\right]=\left[D\right]\\ \left[\begin{array}{ccc}8& 4& -1\\ 0& 6& 0.75\\ 0& 0& 6.5\end{array}\right]\left[\begin{array}{c}{x}_1\\ x_2\\ x_3\end{array}\right]=\left[\begin{array}{c}0\\ 0\\ 1\end{array}\right]\end{array}$

Solve the above matrix by back substitution, which gives the third column of the inverse matrix as:

$\left[X\right]=\left[\begin{array}{c}0.028846\\ -0.01923\\ 0.153846\end{array}\right]$

Thus, the inverse matrix is:

$A^{-1}=\left[\begin{array}{ccc}0.099359& -0.073718& 0.028846\\ 0.044872& 0.160256& -0.01923\\ 0.025641& 0.051282& 0.153846\end{array}\right]$

Now, check the result obtained.

$\begin{array}{c}\left[A\right]{\left[A\right]}^{-1}=\left[\begin{array}{ccc}8& 4& -1\\ -2& 5& 1\\ 2& -1& 6\end{array}\right]\left[\begin{array}{ccc}0.099359& -0.073718& 0.028846\\ 0.044872& 0.160256& -0.01923\\ 0.025641& 0.051282& 0.153846\end{array}\right]\\ =\left[\begin{array}{ccc}1.0000& -0.0000& -0.0000\\ 0.0000& 1.0000& -0.0000\\ 0& 0& 1.0000\end{array}\right]\\ =\left[\begin{array}{ccc}1& 0& 0\\ 0& 1& 0\\ 0& 0& 1\end{array}\right]\\ =\left[I\right]\end{array}$

Hence, verified.