Repeat Exercise 1 using the Gauss-Seidel method

Find the first two iterations ofthe Jacobi method for the following linear systems, using x (0) = 0: 3. 4. 5. 6. 7. 8. 9. a. c. 3xi X2-\- X3 I, b. 3a:i + 6x2 + 2x3 ::= 0- 3xi + 3x2 + 7x3 = 4. 10x1+ 5x2 =6, d. 5xi + 10X2 4X3 =25, 4x2 + 8x3 X4 = I I, X3 + 5X4 11- 10xi X2 =9, X] + 10x2 2x3 = 7, 2X2 + 10x3 = 6. 4xi + X2 + X3 + X5 = 6, X] 3x2 + X3 + X4 =6, 2xi + X2 + 5x3 X4 X5 = 6, X| X2 X3 + 4X4 6, 2x2 -ra + X4 + 4x5 = 6.

Find the first two iterations ofthe Jacobi method for the following linear systems, using x (0) = 0: a. c. 4xi + X2 X3 = 5, X| + 3x2 + +a ~ 4, 2xi + 2x2 + 5x3 = 1- 4xi + X2 X3 + X4 = 2, XI + 4x2 X3 X4 = I, X| X2 + 5x3 + X4 = 0, X| X2 + X3 + 3X4 = 1 b. 2xi+ X2 + ^X3 4, X| -2X2 - 5 X 3 = -4. X2 + 2x3 = 0. d. 4X| X2 =0, X| + 4x2 x-i =5, X2 + 4X3 - 0, + 4X4 - +5 =6, - X4 +4X5- *6 = -2,

Repeat Exercise 1 using the Gauss-Seidel method.

Repeat Exercise 2 using the Gauss-Seidel method

Use the Jacobi method to solve the linear systems in Exercise 1, with TOL 10-3 in the Ioq norm.

Use the Jacobi method to solve the linear systems in Exercise 2, with TOL = 10-3 in the 1^ norm

Use the Gauss-Seidel method to solve the linear systems in Exercise 1, with TOL = I0~3 in the norm

Use the Gauss-Seidel method to solve the linear systems in Exercise 2, with TOL = 10-3 in the /-o norm.

The linear system 2X| - X2 + X3 = -1, 2xi + 2x2 T 2x3 = 4, X| - X2 + 2x3 = -5, has the solution (1, 2, I)'. a. Show that p(7}) = ^ > I. b. Show that the Jacobi method with x 1 " 1 = 0 fails to give a good approximation after 25 iterations.c. Show that p(TK) T. d. Use the Gauss-Seidel method with x ,0) = 0 to approximate the solution to the linear system to within 10-5 in the Zoo norm.

The linear system xi + 2X2 - 2X3 = 7, X] + X2+ X3 = 2, 2xi + 2x2 + X3 = 5 has the solution (1, 2, 1)'. a. Show that p(Tj) 0. Use the Jacobi method with x <0) = 0 to approximate the solution to the linear system to within ID-5 in the 1^ norm. Show that p(Tg) = 2. Show thatthe Gauss-Seidel method applied as in part (b) fails to give a good approximation in b. c. d. 11. 25 iterations.

The linear system X| r 1 -*i X2 2 X2 *3 = 1 4 X3 = *3 = 0.2, -1.425, 2, has the solution (0.9, -0.8, 0.7)'. a. is the coefficient matrix A = 0 1 i '2 1 -k -1 1 strictly diagonally dominant? b. Compute the spectral radius ofthe Gauss-Seidel matrix Tg. c. Use the Gauss-Seidel iterative method to approximate the solution to the linear system with a tolerance of 10-2 and a maximum of 300 iterations. d. What happens in part (c) when the system is changed to the following? *i xt 2X3 X2 I*2 + r x 3 -T3 = 0.2, = -1.425, = 2

Repeat Exercise 11 using the Jacobi method

Use (a) the Jacobi and (b) the Gauss-Seidel methods to solve the linear system Ax = b to within I0"5 in the /-o norm, where the entries of A are a iJ = when j = i and / = 1,2,... , 80, + 2 and / = 1,2,... ,78, 2 and i = 3,4,... , 80, + 4 and i 1,2,... ,76, 4 and i 5.6 80, 2i, J = 0.5/, when J = 7 = 0.25i, when 7 = 0, otherwise, and those of b are b-, = n, for each i = 1,2,... ,80.

Suppose that an object can be at any one ofn+1 equally spaced points xq, . ,xn. When an object is at location x,-, it is equally likely to move to either x,_i or x/+i and cannot directly move to any other location. Consider the probabilities that an object starting at location x,- will reach the left endpoint xq before reaching the right endpoint x. Clearly, Pq = 1 and P,, = 0. Since the object can move to x, only from x,_i or x/+i and does so with probability ^ for each ofthese locations, Pi -P(_i + -Pi+i, for each i 1,2,... , n 1. a. Show that 1 -T Q., () Pi r 1 ' 2 Pi 0 . Pn-l . . 0 _ ; .22 6 -0 -i 1 . b. Solve this system using n = 10, 50, and 100. c. Change the probabilities to a and 1 a for movement to the left and right, respectively, and derive the linear system similar to the one in part (a). d. Repeat part (b) with cr = j.

The forces on the bridge truss described in the opening to this chapter satisfy the equations in the following table: Joint Horizontal Component Vertical Component 16. (D -Pl + 4fl+f2 = 0 is I II o -f/l + #/4 = 0 -f/l-/3-^/4 = 0 -/2 + /5=0 /3 - 10.000 = 0 -f/4-/5=0 1/4 - Ej = 0 This linear system can be placed in the matrix form -1 0 0 72 2 1 0 0 0 0 -1 0 72 2 0 0 0 0 0 0 -1 0 0 0 1 2 0 0 0 0 72 2 0 -1 1 2 0 0 0 0 0 -1 0 0 1 0 0 0 0 0 1 0 0 0 0 0 72 2 0 0 73 2 0 0 0 0 0 0 0 73 2 -1 " Fi ' 0 Pi 0 Fi 0 A 0 fi 0 h 10,000 A 0 . A . 0 a. b. Explain why the system of equations was reordered. Approximate the solution of the resulting linear system to within 10-2 in the lx norm using as initial approximation the vector ail of whose entries are Is with (i) the Jacobi method and (ii) the Gauss-Seidel method.

A coaxial able is made up of a 0.1-inch-square inner conductor and 0.5-inch-square outer conductor. The potential at a point in the cross section ofthe cable is described by Laplace's equation.Suppose the inner conductor is kept at 0 volts and the outer conductor is kept at 110 volts. Approximating the potential between the two conductorsrequires solving the following linearsystem. (See Exercise 5 of Section 12.1.) 4 -1 0 0 -1 0 0 0 0 0 0 0 -1 4 -1 0 0 0 0 0 0 0 0 0 0 -1 4 -1 0 0 0 0 0 0 0 0 0 0 -1 4 0 -1 0 0 0 0 0 0 -1 0 0 0 4 0 -1 0 0 0 0 0 0 0 0 -1 0 4 0 -1 0 0 0 0 0 0 0 0 -1 0 4 0 -1 0 0 0 0 0 0 0 0 -1 0 4 0 0 0 -1 0 0 0 0 0 0 -1 0 4 -1 0 0 0 0 0 0 0 0 0 0 -1 4 -1 0 0 0 0 0 0 0 0 0 0 -1 4 -1 0 0 0 0 0 -1 0 0 0 0 -1 4 ' Wl ' 220 ' VV'2 110 VI' 3 110 H'4 220 Ws 110 VV'6 no Wl no w's no Wg 220 VV|0 no wn no . w n . . 220 . a. Is the matrix strictly diagonally dominant? b. Solve the linear system using the Jacobi method with x (0) = 0 and TOL = 10-2 . c. Repeat part (b) using the Gauss-Seidel method.

Show that if A is strictly diagonally dominant, then ||7}| 18. a. Prove that 19. < 1

a. Prove that 19. < 1. |x(i) - x|| < Ix'01 - Xll and |x( - Xll < II7" 11' 1 - II7" || Ixd) _ x (0)| where T is an n x n matrix with ||r|| < 1 and x<*) = TV*-1 ' + c, k 1,2,... , with x <0) arbitrary, c M", and x = Tx + c. b. Apply the bounds to Exercise I, when possible, using the norm

Suppose that A is a positive definite. a. Show that we can write A = D L L', where D is diagonal with da > 0 for each 1 < / < and L is lower triangular. Further, show that Z) L is nonsingular. Let Tg (D L)_1L' and P A - T'gATg. Show that P is symmetric. Show that Tg can also be written as Tg I (D L)~i A. Let Q = (D - L)-1 A. Show that rg = / - g and P = g'lAg-1 - A + (g')-1 AJg. Show that P Q' DQ and P is positive definite. Let X be an eigenvalue of Tg with eigenvector x ^ 0. Use part (b) to show that x' Px > 0 implies that |A| < 1. Show that Tg is convergent and prove that the Gauss-Seidel method converges.

The GMRES method is an iterative method used for solutions of large sparse nonsymmetric linear systems. Compare that method to the iterative methods discussed in this section.

Are direct methods such as Gaussian elimination or LU factorization more efficient than indirect methods such as Gauss-Seidel or Jacobi when the size ofthe system increases significantly?