Chapter 11, Problem 1P

Perform the same calculations as in (a) Example 11.1, and (b) Example 11.3, but for the tridiagonal system,

$\left[\begin{array}{ccc}0.8& -0.4& \\ -0.4& 0.8& -0.4\\ & -0.4& 0.8\end{array}\right]\left\{\begin{array}{c}{x}_1\\ x_2\\ x_3\end{array}\right\}=\left\{\begin{array}{c}41\\ 25\\ 105\end{array}\right\}$

To determine

To calculate: The solution of following tridiagonal system with Thomas Algorithm:

$\begin{array}{ccc}0.8& -0.4& \\ -0.4& 0.8& -0.4\\ & -0.4& 0.8\end{array}\left\{\begin{array}{l}{x}_1\\ x_2\\ x_3\end{array}\right\}=\left\{\begin{array}{l}41\\ 25\\ 105\end{array}\right\}$

Answer to Problem 1P

Solution:

The solution is $x_1=173.8123,x_2=245.1247\text{and}{x}_3=253.9371$

Explanation of Solution

Given:

A tridiagonal system:

$\begin{array}{ccc}0.8& -0.4& 0\\ -0.4& 0.8& -0.4\\ 0& -0.4& 0.8\end{array}\left\{\begin{array}{l}{x}_1\\ x_2\\ x_3\end{array}\right\}=\left\{\begin{array}{l}41\\ 25\\ 105\end{array}\right\}$

Formula used:

(a) The decomposition is implemented as:

$e_k=\frac{e_k}{f_{k-1}}$

$f_k=f_k-e_k\cdot g_{k-1}$

(2) Forward substitution is implemented as:

$r_k=r_k-e_k\cdot r_{k-1}$

(3) Back substitution is implemented as:

$x_n=\frac{r_n}{f_n}$,

For $k\le n-1$

$x_k=\frac{r_k-g_k\cdot x_{k+1}}{f_k}$

Calculation:

Consider the system of equation:

$\begin{array}{ccc}0.8& -0.4& 0\\ -0.4& 0.8& -0.4\\ 0& -0.4& 0.8\end{array}\left\{\begin{array}{l}{x}_1\\ x_2\\ x_3\end{array}\right\}=\left\{\begin{array}{l}41\\ 25\\ 105\end{array}\right\}$

Where,

$\left[A\right]=\begin{array}{ccc}0.8& -0.4& 0\\ -0.4& 0.8& -0.4\\ 0& -0.4& 0.8\end{array}$

$f_1=0.8,f_2=0.8,f_3=0.8$

$g_1=-0.4,g_2=-0.4$

$e_2=-0.4,e_3=-0.4$

$r_1=41,r_2=25,r_3=105$

First the decomposition is implemented as:

$\begin{array}{c}{e}_2=\frac{e_2}{f_1}\\ =\frac{-0.4}{0.8}\\ =-0.5\end{array}$

Now,

$\begin{array}{c}{f}_2=f_2-e_2.g_1\\ =0.8-\left(-0.5\right)\left(-0.4\right)\\ =0.8-0.2\\ =0.6\end{array}$

And,

$\begin{array}{c}{e}_3=\frac{e_3}{f_2}\\ =\frac{-0.4}{0.6}\\ =-0.667\end{array}$

And,

$\begin{array}{c}{f}_3=f_3-e_3.g_2\\ =0.8-\left(-0.667\right)\left(-0.4\right)\\ =0.533\end{array}$

Thus, the matrix [A] is transformed to,

$\begin{array}{ccc}0.8& -0.4& 0\\ -0.5& 0.6& -0.4\\ 0& -0.667& 0.533\end{array}$

Now, the LU decomposition of the above matrix is,

$\begin{array}{c}\left[A\right]=\left[L\right]\left[U\right]\\ =\begin{array}{ccc}1& 0& 0\\ -0.5& 1& 0\\ 0& -0.667& 1\end{array}\begin{array}{ccc}0.8& -0.4& 0\\ 0& 0.6& -0.4\\ 0& 0& 0.533\end{array}\end{array}$

The forward substitution is implemented as:

$\begin{array}{c}{r}_2=r_2-e_2.r_1\\ =25-\left(-0.5\right)\left(41\right)\\ =25+20.5\\ =45.5\end{array}$

And,

$\begin{array}{c}{r}_3=r_3-e_3.r_2\\ =105-\left(-0.667\right)\left(45.5\right)\\ =135.3485\end{array}$

Thus, the right-hand-side vector is modified to,

$\left\{\begin{array}{l}41\\ 45.5\\ 135.3485\end{array}\right\}$

The right-hand-side vector can be used in conjunction with the [U] matrix to perform back substitution and obtain the solution as:

$\begin{array}{c}{x}_3=\frac{r_3}{f_3}\\ =\frac{135.3485}{0.533}\\ =253.9371\end{array}$

Also,

$$ $\begin{array}{c}{x}_2=\frac{r_2-g_2.x_3}{f_2}\\ =\frac{45.5-\left(-0.4\right)\left(253.9371\right)}{0.6}\\ =245.1247\end{array}$

And,

$\begin{array}{c}{x}_1=\frac{r_1-g_1.x_2}{f_1}\\ =\frac{41-\left(-0.4\right)\left(245.1247\right)}{0.8}\\ =173.8123\end{array}$

Thus, the solution of the given system of equation is $x_1=173.8123$, $x_2=245.1247$ and $x_3=253.9371$.

To determine

To calculate: The solution of following tridiagonal system of equation with Gauss-Seidel method:

$\begin{array}{ccc}0.8& -0.4& 0\\ -0.4& 0.8& -0.4\\ 0& -0.4& 0.8\end{array}\left\{\begin{array}{l}{x}_1\\ x_2\\ x_3\end{array}\right\}=\left\{\begin{array}{l}41\\ 25\\ 105\end{array}\right\}$

Answer to Problem 1P

Solution:

Using Gauss-Seidel method four iteration are performed to get $x_1=150.234375,x_2=221.484375\text{and}{x}_3=241.9921875$.

Explanation of Solution

Given:

A system of equation:

$\begin{array}{ccc}0.8& -0.4& 0\\ -0.4& 0.8& -0.4\\ 0& -0.4& 0.8\end{array}\left\{\begin{array}{l}{x}_1\\ x_2\\ x_3\end{array}\right\}=\left\{\begin{array}{l}41\\ 25\\ 105\end{array}\right\}$

Formula used:

(1) The values of $x_1,x_2\text{and}{x}_3$ are given by the formula:

$x_1=\frac{b_1-a_{12}{x}_2-a_{13}{x}_3}{a_{11}}$ ,

$x_2=\frac{b_2-a_{21}{x}_1-a_{23}{x}_3}{a_{22}}$,

$x_3=\frac{b_3-a_{31}{x}_1-a_{32}{x}_2}{a_{33}}$

(2) True percent relative error is given by,

${\epsilon }_t=\frac{\text{true value}-\text{approximation}}{\text{true value}}\times 100\mathbf{\text{\%}}$

(3) Convergence can be checked using the criterion

$\left|{\epsilon }_{a,i}\right|=\left|\frac{x_i{}^j-x_i{}^{j-1}}{x_i{}^j}\right|100\mathbf{\text{\%<}}{\epsilon }_s$

For all i, where j and j- 1 are the present and previous iterations.

Calculation:

The true solution is $x_1=173.8123$, $x_2=245.1247$ and $x_3=253.9371$.

Consider the system of equation:

$\begin{array}{ccc}0.8& -0.4& 0\\ -0.4& 0.8& -0.4\\ 0& -0.4& 0.8\end{array}\left\{\begin{array}{l}{x}_1\\ x_2\\ x_3\end{array}\right\}=\left\{\begin{array}{l}41\\ 25\\ 105\end{array}\right\}$

Where,

$\left[A\right]=\begin{array}{ccc}0.8& -0.4& 0\\ -0.4& 0.8& -0.4\\ 0& -0.4& 0.8\end{array}$

$\left\{X\right\}=\left\{\begin{array}{l}{x}_1\\ x_2\\ x_3\end{array}\right\}$

$\left\{B\right\}=\left\{\begin{array}{l}41\\ 25\\ 105\end{array}\right\}$

First, solve each of the equations for its unknown on the diagonal

$x_1=\frac{41-\left(-0.4\right)x_2-\left(0\right)x_3}{0.8}$ ...... (1)

$x_2=\frac{25-\left(-0.4\right)x_1-\left(-0.4\right)x_3}{0.8}$ ...... (2)

$x_3=\frac{105-\left(0\right)x_1-\left(-0.4\right)x_2}{0.8}$ ...... (3)

For initial guess, assume $x_2=0$ and $x_3=0$.

Thus, equation (1) becomes,

$\begin{array}{c}{x}_1=\frac{41-\left(-0.4\right)x_2-\left(0\right)x_3}{0.8}\\ =\frac{41-\left(-0.4\right)\left(0\right)-\left(0\right)\left(0\right)}{0.8}\\ =\frac{41}{0.8}\\ =51.25\end{array}$

This value, along with the assumed value of $x_3=0$, can be substituted in equation (2) to calculate,

$\begin{array}{c}{x}_2=\frac{25-\left(-0.4\right)x_1-\left(-0.4\right)x_3}{0.8}\\ =\frac{25-\left(-0.4\right)\left(51.25\right)-\left(-0.4\right)\left(0\right)}{0.8}\\ =\frac{45.5}{0.8}\\ =56.875\end{array}$

Now, substitute the calculated values of $x_1=51.25$ and $x_2=56.875$ into equation (3) to calculate,

$\begin{array}{c}{x}_3=\frac{105-\left(0\right)x_1-\left(-0.4\right)x_2}{0.8}\\ =\frac{105-\left(0\right)\left(51.25\right)-\left(-0.4\right)\left(56.875\right)}{0.8}\\ =\frac{127.75}{0.8}\\ =159.6875\end{array}$

For the second iteration, the same process is repeated with $x_2=56.875$ and $x_3=159.6875$ to compute,

$\begin{array}{c}{x}_1=\frac{41-\left(-0.4\right)x_2-\left(0\right)x_3}{0.8}\\ =\frac{41-\left(-0.4\right)\left(56.875\right)-\left(0\right)\left(159.6875\right)}{0.8}\\ =\frac{63.75}{0.8}\\ =79.6875\end{array}$

The true percent relative error is ${\epsilon }_t=\frac{\text{true value}-\text{approximation}}{\text{true value}}100\mathbf{\text{\%}}$

Thus,

$\begin{array}{c}\left|{\epsilon }_t\right|=\left|\frac{173.8123-\text{79}\text{.6875}}{173.8123}\right|\times 100\mathbf{\text{\%}}\\ \mathbf{\text{=0}}\mathbf{\text{.5415}}\times 100\mathbf{\text{\%}}\\ \mathbf{\text{=54}}\mathbf{\text{.15\%}}\end{array}$

The value of $x_1=79.6875$, along with the calculated value of $x_3=159.6875$, can be used to get,

$\begin{array}{c}{x}_2=\frac{25-\left(-0.4\right)x_1-\left(-0.4\right)x_3}{0.8}\\ =\frac{25-\left(-0.4\right)\left(79.6875\right)-\left(-0.4\right)\left(159.6875\right)}{0.8}\\ =\frac{120.75}{0.8}\\ =150.9375\end{array}$

Thus,

$\begin{array}{c}\left|{\epsilon }_t\right|=\left|\frac{245.1247-150.9375}{245.1247}\right|\times 100\mathbf{\text{\%}}\\ \mathbf{\text{=0}}\mathbf{\text{.3842}}\times 100\mathbf{\text{\%}}\\ \mathbf{\text{=38}}\mathbf{\text{.42\%}}\end{array}$

Now, substitute the calculated values of $x_1=79.6875$ and $x_2=150.9375$ to calculate,

$\begin{array}{c}{x}_3=\frac{105-\left(0\right)x_1-\left(-0.4\right)x_2}{0.8}\\ =\frac{105-\left(0\right)\left(79.6875\right)-\left(-0.4\right)\left(150.9375\right)}{0.8}\\ =\frac{165.375}{0.8}\\ =206.71875\end{array}$

Thus,

$\begin{array}{c}\left|{\epsilon }_t\right|=\left|\frac{253.9371-150.9375}{253.9371}\right|\times 100\mathbf{\text{\%}}\\ \mathbf{\text{=0}}\mathbf{\text{.4056}}\times 100\mathbf{\text{\%}}\\ \mathbf{\text{=40}}\mathbf{\text{.56\%}}\end{array}$

For the third iteration, the same process is repeated with $x_2=150.9375$ and $x_3=206.71875$ to compute

$\begin{array}{c}{x}_1=\frac{41-\left(-0.4\right)x_2-\left(0\right)x_3}{0.8}\\ =\frac{41-\left(-0.4\right)\left(150.9375\right)-\left(0\right)\left(206.71875\right)}{0.8}\\ =126.71875\end{array}$

The true percent relative error is ${\epsilon }_t=\frac{\text{true value}-\text{approximation}}{\text{true value}}100\mathbf{\text{\%}}$

Thus,

$\begin{array}{c}\left|{\epsilon }_t\right|=\left|\frac{173.8123-\text{126}\text{.71875}}{173.8123}\right|\times 100\mathbf{\text{\%}}\\ \mathbf{\text{=0}}\mathbf{\text{.2709}}\times 100\mathbf{\text{\%}}\\ \mathbf{\text{=27}}\mathbf{\text{.09\%}}\end{array}$

The value of $x_1=126.71875$, along with the calculated value of $x_3=206.71875$, can be used to get,

$\begin{array}{c}{x}_2=\frac{25-\left(-0.4\right)x_1-\left(-0.4\right)x_3}{0.8}\\ =\frac{25-\left(-0.4\right)\left(126.71875\right)-\left(-0.4\right)\left(206.71875\right)}{0.8}\\ =197.96875\end{array}$

Thus,

$\begin{array}{c}\left|{\epsilon }_t\right|=\left|\frac{245.1247-197.96875}{245.1247}\right|\times 100\mathbf{\text{\%}}\\ \mathbf{\text{=0}}\mathbf{\text{.1923}}\times 100\mathbf{\text{\%}}\\ \mathbf{\text{=19}}\mathbf{\text{.23\%}}\end{array}$

Now, substitute the calculated values of $x_1=126.71875$ and $x_2=197.96875$ to calculate,

$\begin{array}{c}{x}_3=\frac{105-\left(0\right)x_1-\left(-0.4\right)x_2}{0.8}\\ =\frac{105-\left(0\right)\left(126.71875\right)-\left(-0.4\right)\left(197.96875\right)}{0.8}\\ =230.234375\end{array}$

Thus,

$\begin{array}{c}\left|{\epsilon }_t\right|=\left|\frac{253.9371-230.234375}{253.9371}\right|\times 100\mathbf{\text{\%}}\\ \mathbf{\text{=0}}\mathbf{\text{.0933}}\times 100\mathbf{\text{\%}}\\ \mathbf{\text{=9}}\mathbf{\text{.33\%}}\end{array}$

For the fourth iteration, the same process is repeated with $x_2=197.96875$ and $x_3=230.234375$ to compute

$\begin{array}{c}{x}_1=\frac{41-\left(-0.4\right)x_2-\left(0\right)x_3}{0.8}\\ =\frac{41-\left(-0.4\right)\left(197.96875\right)-\left(0\right)\left(230.234375\right)}{0.8}\\ =150.234375\end{array}$

The true percent relative error is ${\epsilon }_t=\frac{\text{true value}-\text{approximation}}{\text{true value}}100\mathbf{\text{\%}}$

Thus,

$\begin{array}{c}\left|{\epsilon }_t\right|=\left|\frac{173.8123-\text{150}\text{.234375}}{173.8123}\right|\times 100\mathbf{\text{\%}}\\ \mathbf{\text{=0}}\mathbf{\text{.1356}}\times 100\mathbf{\text{\%}}\\ \mathbf{\text{=13}}\mathbf{\text{.56\%}}\end{array}$

The value of $x_1=150.234375$, along with the calculated value of $x_3=230.234375$, can be used to get,

$\begin{array}{c}{x}_2=\frac{25-\left(-0.4\right)x_1-\left(-0.4\right)x_3}{0.8}\\ =\frac{25-\left(-0.4\right)\left(150.234375\right)-\left(-0.4\right)\left(230.234375\right)}{0.8}\\ =221.484375\end{array}$

Thus,

$\begin{array}{c}\left|{\epsilon }_t\right|=\left|\frac{245.1247-221.484375}{245.1247}\right|\times 100\mathbf{\text{\%}}\\ \mathbf{\text{=0}}\mathbf{\text{.0964}}\times 100\mathbf{\text{\%}}\\ \mathbf{\text{=9}}\mathbf{\text{.64\%}}\end{array}$

Now, substitute the calculated values of $x_1=150.234375$ and $x_2=221.484375$ to calculate,

$\begin{array}{c}{x}_3=\frac{105-\left(0\right)x_1-\left(-0.4\right)x_2}{0.8}\\ =\frac{105-\left(0\right)\left(150.234375\right)-\left(-0.4\right)\left(221.484375\right)}{0.8}\\ =241.9921875\end{array}$

Thus,

$\begin{array}{c}\left|{\epsilon }_t\right|=\left|\frac{253.9371-241.9921875}{253.9371}\right|\times 100\mathbf{\text{\%}}\\ \mathbf{\text{=0}}\mathbf{\text{.0470}}\times 100\mathbf{\text{\%}}\\ \mathbf{\text{=4}}\mathbf{\text{.70\%}}\end{array}$

The method is thus converging on the true solution.

Now, estimate the error:

$\begin{array}{c}\left|{\epsilon }_{a,1}\right|=\left|\frac{150.234375-126.71875}{150.234375}\right|\times 100\mathbf{\text{\%}}\\ \mathbf{\text{=0}}\mathbf{\text{.1565}}\times 100\mathbf{\text{\%}}\\ =15.65\mathbf{\text{\%}}\end{array}$

$\begin{array}{c}\left|{\epsilon }_{a,2}\right|=\left|\frac{221.484375-197.96875}{221.484375}\right|\times 100\mathbf{\text{\%}}\\ \mathbf{\text{=0}}\mathbf{\text{.1061}}\times 100\mathbf{\text{\%}}\\ =10.61\mathbf{\text{\%}}\end{array}$

$\begin{array}{c}\left|{\epsilon }_{a,3}\right|=\left|\frac{241.9921875-230.234375}{241.9921875}\right|\times 100\mathbf{\text{\%}}\\ \mathbf{\text{=0}}\mathbf{\text{.0485}}\times 100\mathbf{\text{\%}}\\ =4.85\mathbf{\text{\%}}\end{array}$