312 SPECIAL MATRICES AND GAUSS-SEIDEL

SOFTWARE

FIGURE 11.9
Mathcad screen to determine the matrix inverse and condition numbers of a scaled 3×3 Hilbert
matrix.

PROBLEMS
⎡ ⎤
11.1 Perform the same calculations as in (a) Example 11.1, and 2.01475 −0.020875
(b) Example 11.3, but for the tridiagonal system, ⎢ −0.020875 2.01475 −0.020875 ⎥
⎢ ⎥
⎣ −0.020875 2.01475 −0.020875 ⎦
⎡ ⎤⎧ ⎫ ⎧ ⎫ −0.020875 2.01475
0.8 −0.4 ⎨ x1 ⎬ ⎨ 41 ⎬ ⎧ ⎫ ⎧ ⎫
⎣ −0.4 0.8 −0.4 ⎦ x2 = 25 ⎪ T1 ⎪ ⎪ 4.175 ⎪
⎩ ⎭ ⎩ ⎭ ⎪
⎨T ⎪ ⎬ ⎪ ⎨ 0 ⎪ ⎬
−0.4 0.8 x3 105 2
× =
⎪
⎪ T ⎪ ⎪ 0 ⎪
⎩ 3⎪ ⎭ ⎪ ⎩ ⎪
⎭
11.2 Determine the matrix inverse for Example 11.1 based on the T4 2.0875
LU decomposition and unit vectors. Use the Thomas algorithm to obtain a solution.
11.3 The following tridiagonal system must be solved as part of a 11.4 Confirm the validity of the Cholesky decomposition of Ex-
larger algorithm (Crank-Nicolson) for solving partial differential ample 11.2 by substituting the results into Eq. (11.2) to see if the
equations: product of [L] and [L]T yields [A].
cha01064_ch11.qxd 3/20/09 12:13 PM Page 313

PROBLEMS 313

11.5 Perform the same calculations as in Example 11.2, but for the 11.13 Use the Gauss-Seidel method (a) without relaxation and (b)
symmetric system, with relaxation (λ = 1.2) to solve the following system to a toler-
⎡ ⎤⎧ ⎫ ⎧ ⎫ ance of εs = 5%. If necessary, rearrange the equations to achieve
6 15 55 ⎨ a0 ⎬ ⎨ 152.6 ⎬ convergence.
⎣ 15 55 225 ⎦ a1 = 585.6
⎩ ⎭ ⎩ ⎭ 2x1 − 6x2 − x3 = −38
55 225 979 a2 2488.8
−3x1 − x2 + 7x3 = −34
In addition to solving for the Cholesky decomposition, employ it to
solve for the a’s. −8x1 + x2 − 2x3 = −20
11.6 Perform a Cholesky decomposition of the following symmet- 11.14 Redraw Fig. 11.5 for the case where the slopes of the equa-
ric system by hand, tions are 1 and –1. What is the result of applying Gauss-Seidel to
⎡ ⎤⎧ ⎫ ⎧ ⎫ such a system?
8 20 15 ⎨ x1 ⎬ ⎨ 100 ⎬
11.15 Of the following three sets of linear equations, identify the
⎣ 20 80 50 ⎦ x2 = 250
⎩ ⎭ ⎩ ⎭ set(s) that you could not solve using an iterative method such as
15 50 60 x3 100 Gauss-Seidel. Show using any number of iterations that is neces-
11.7 Compute the Cholesky decomposition of sary that your solution does not converge. Clearly state your con-
⎡ ⎤ vergence criteria (how you know it is not converging).
9 0 0
[A] = ⎣ 0 25 0 ⎦
Set One Set Two Set Three
0 0 4
9x + 3y + z = 13 x + y + 6z = 8 −3x + 4y + 5z = 6
Do your results make sense in terms of Eqs. (11.3) and (11.4)?
−6x + 8z = 2 x + 5y − z = 5 −2x + 2y − 4z = −3
11.8 Use the Gauss-Seidel method to solve the tridiagonal system
from Prob.11.1 (εs = 5%). Use overrelaxation with λ = 1.2. 2x + 5y − z = 6 4x + 2y − 2z = 4 2y − z = 1
11.9 Recall from Prob. 10.8, that the following system of equa-
tions is designed to determine concentrations (the c’s in g/m3) in a 11.16 Use the software package of your choice to obtain a solution,
series of coupled reactors as a function of amount of mass input to calculate the inverse, and determine the condition number (without
each reactor (the right-hand sides in g/d), scaling) based on the row-sum norm for
15c1 − 3c2 − c3 = 3300 (a)
⎡ ⎤⎧ ⎫ ⎧ ⎫
−3c1 + 18c2 − 6c3 = 1200 1 4 9 ⎨ x1 ⎬ ⎨ 14 ⎬
⎣ 4 9 16 ⎦ x2 = 29
−4c1 − c2 + 12c3 = 2400 ⎩ ⎭ ⎩ ⎭
9 16 25 x3 50
Solve this problem with the Gauss-Seidel method to εs = 5%.
11.10 Repeat Prob. 11.9, but use Jacobi iteration. (b)
11.11 Use the Gauss-Seidel method to solve the following system ⎡ ⎤⎧ ⎫ ⎧ ⎫
1 4 9 16 ⎪ x1 ⎪ ⎪ 30 ⎪
until the percent relative error falls below εs = 5%, ⎪
⎨ ⎬ ⎨⎪ ⎪ ⎪
⎬
⎢ 4 9 16 25 ⎥
⎢ ⎥ x2 = 54
10x1 + 2x2 − x3 = 27 ⎣ 9 16 25 ⎦
36 ⎪ ⎪ x3 ⎪ ⎪ 86 ⎪
⎩ ⎪ ⎭ ⎪
⎩ ⎪
⎭
16 25 36 49 x4 126
−3x1 − 6x2 + 2x3 = −61.5
x1 + x2 + 5x3 = −21.5 In both cases, the answers for all the x’s should be 1.
11.17 Given the pair of nonlinear simultaneous equations:
11.12 Use the Gauss-Seidel method (a) without relaxation and (b)
with relaxation (λ = 0.95) to solve the following system to a toler- f(x, y) = 4 − y − 2x 2
ance of εs = 5%. If necessary, rearrange the equations to achieve g(x, y) = 8 − y 2 − 4x
convergence.
−3x1 + x2 + 12x3 = 50 (a) Use the Excel Solver to determine the two pairs of values of x
and y that satisfy these equations.
6x1 − x2 − x3 = 3 (b) Using a range of initial guesses (x = −6 to 6 and y = −6 to 6),
6x1 + 9x2 + x3 = 40 determine which initial guesses yield each of the solutions.
cha01064_ch11.qxd 3/20/09 12:13 PM Page 314

314 SPECIAL MATRICES AND GAUSS-SEIDEL

11.18 An electronics company produces transistors, resistors, and 11.24 Develop a user-friendly program in either a high-level or
computer chips. Each transistor requires four units of copper, one macro language of your choice to obtain a solution for a tridiagonal
unit of zinc, and two units of glass. Each resistor requires three, system with the Thomas algorithm (Fig. 11.2). Test your program
three, and one units of the three materials, respectively, and each by duplicating the results of Example 11.1.
computer chip requires two, one, and three units of these materials, 11.25 Develop a user-friendly program in either a high-level or
respectively. Putting this information into table form, we get: macro language of your choice for Cholesky decomposition based
on Fig. 11.3. Test your program by duplicating the results of
Example 11.2.
Component Copper Zinc Glass 11.26 Develop a user-friendly program in either a high-level or
macro language of your choice for the Gauss-Seidel method based
Transistors 4 1 2
on Fig. 11.6. Test your program by duplicating the results of
Resistors 3 3 1
Computer chips 2 1 3
Example 11.3.
11.27 As described in Sec. PT3.1.2, linear algebraic equations can
arise in the solution of differential equations. For example, the
Supplies of these materials vary from week to week, so the com- following differential equation results from a steady-state mass
pany needs to determine a different production run each week. For balance for a chemical in a one-dimensional canal,
example, one week the total amounts of materials available are d 2c dc
960 units of copper, 510 units of zinc, and 610 units of glass. Set up 0 = D 2 −U − kc
dx dx
the system of equations modeling the production run, and use
where c = concentration, t = time, x = distance, D = diffusion
Excel, MATLAB, or Mathcad, to solve for the number of transis-
coefficient, U = fluid velocity, and k = a first-order decay rate.
tors, resistors, and computer chips to be manufactured this week.
Convert this differential equation to an equivalent system of
11.19 Use MATLAB or Mathcad software to determine the spectral
simultaneous algebraic equations. Given D = 2, U = 1, k = 0.2,
condition number for a 10-dimensional Hilbert matrix. How many
c(0) = 80 and c(10) = 20, solve these equations from x = 0 to 10
digits of precision are expected to be lost due to ill-conditioning?
and develop a plot of concentration versus distance.
Determine the solution for this system for the case where each
11.28 A pentadiagonal system with a bandwidth of five can be ex-
element of the right-hand-side vector {b} consists of the summation
pressed generally as
of the coefficients in its row. In other words, solve for the case where
⎡ ⎤⎧ ⎫ ⎧ ⎫
all the unknowns should be exactly one. Compare the resulting
⎪ 1⎪
⎪ ⎪ ⎪ ⎪ 1⎪
f 1 g1 h 1 x r ⎪
errors with those expected based on the condition number. ⎢ e2 f 2 g2 h 2 ⎥⎪⎪ x2 ⎪
⎪ ⎪ ⎪
⎪ ⎪ r2 ⎪
⎪ ⎪
⎪
⎢ ⎥⎪ ⎪
⎪ ⎪ ⎪
⎪
11.20 Repeat Prob. 11.19, but for the case of a six-dimensional ⎢ d3 e3 f 3 g3 ⎥⎪⎪ ⎪ ⎪
⎪ ⎪
⎢ h ⎥⎪⎪ x 3⎪ ⎪ 3⎪
⎪ ⎪ r ⎪
3
⎥ ⎪ ⎪
⎬ ⎪ ⎪
Vandermonde matrix (see Prob. 10.17) where x1 = 4, x2 = 2, x3 = 7, ⎢
⎢ · · · ⎥
⎨ · ⎨ · ⎬
x4 = 10, x5 = 3, and x6 = 5. ⎢ ⎥ =
⎢ · · · ⎥⎪ · ⎪ ⎪ · ⎪
⎢ ⎥⎪⎪ ⎪ ⎪ ⎪
⎪ ⎪ ⎪ ⎪
⎪ ⎪ · ⎪
11.21 Given a square matrix [A], write a single line MATLAB ⎢ ⎥⎪ ⎪ ⎪ ⎪
⎢ · · · ⎥⎪⎪ · ⎪
⎪ ⎪
⎪ ⎪
⎪
command that will create a new matrix [Aug] that consists of the ⎪
⎪xn−1⎪ ⎪
⎪ ⎪ ⎪rn−1⎪
⎪ ⎪
⎣ dn−1 en−1 f n−1 gn−1 ⎦ ⎪ ⎪
original matrix [A] augmented by an identity matrix [I]. ⎩ ⎭ ⎩ ⎪
⎪ ⎪ ⎪ ⎭
11.22 Write the following set of equations in matrix form: dn en fn xn rn

50 = 5x3 − 7x2 Develop a program to efficiently solve such systems without pivot-
ing in a similar fashion to the algorithm used for tridiagonal matri-
4x2 + 7x3 + 30 = 0
ces in Sec. 11.1.1. Test it for the following case:
x1 − 7x3 = 40 − 3x2 + 5x1 ⎡ ⎤⎧ ⎫ ⎧ ⎫
8 −2 −1 0 0 ⎪ x1 ⎪ ⎪ 5 ⎪
⎪
⎪ ⎪ ⎪ ⎪
Use Excel, MATLAB, or Mathcad to solve for the unknowns. In ⎢ −2 9 −4 −1 0⎥ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪
addition, compute the transpose and the inverse of the coefficient ⎢ ⎥ ⎨ x2 ⎬ ⎨ 2 ⎬
⎢ −1 −3 7 −1 −2 ⎥ x3 = 1
⎢ ⎥
matrix. ⎣ 0 −4 −2 12 −5 ⎦ ⎪ ⎪
⎪
⎪
⎪ ⎪ ⎪1⎪ ⎪
11.23 In Sec. 9.2.1, we determined the number of operations re- ⎪ x4 ⎪
⎩ ⎪ ⎪
⎭ ⎪ ⎪
⎩ ⎪
⎭
quired for Gauss elimination without partial pivoting. Make a sim- 0 0 −7 −3 15 x5 5
ilar determination for the Thomas algorithm (Fig. 11.2). Develop a
plot of operations versus n (from 2 to 20) for both techniques.