Heath - Scientific Computing (523150), страница 23
Текст из файла (страница 23)
SYSTEMS OF LINEAR EQUATIONS2.16 (a) What is the LU factorization of thefollowing matrix?1 ac b2.22 Verify that the dominant term in theoperation count (number of multiplications ornumber of additions) for LU factorization of amatrix of order n by Gaussian elimination isn3 /3.(b) Under what condition is this matrix singular?2.23 Verify that the dominant term in theoperation count (number of multiplications ornumber of additions) for computing the inverseof a matrix of order n by Gaussian eliminationis n3 .2.17 Write out the LU factorization of the following matrix (show both the L and U matrices explicitly):1 −10 −12 −1 .0 −112.18 Prove that the matrix0 1A=1 0has no LU factorization, i.e., no lower triangular matrix L and upper triangular matrix Uexist such that A = LU .2.19 Let A be an n × n nonsingular matrix.Consider the following algorithm:2.24 Verify that the dominant term in theoperation count (number of multiplications ornumber of additions) for Gauss-Jordan elimination for a matrix of order n is n3 /2.2.25 (a) If u and v are nonzero n-vectors,prove that the n×n outer product matrix uv Thas rank one.(b) If A is an n×n matrix such that rank(A) =1, prove that there exist nonzero n-vectors uand v such that A = uv T .2.26 An n × n matrix A is said to be elementary if it differs from the identity matrix by amatrix of rank one, i.e., if A = I − uv T forsome n-vectors u and v.(a) If A is elementary, what condition on uand v ensures that A is nonsingular?1.
Scan columns 1 through n of A in succession, and permute rows, if necessary, sothat the diagonal entry is the largest entry in magnitude on or below the diagonalin each column. The result is P A for somepermutation matrix P .2. Now carry out Gaussian elimination without pivoting to compute the LU factorization of P A.(b) If A is elementary and nonsingular, provethat A−1 is also elementary by showing thatA−1 = I − σuv T for some scalar σ. What isthe specific value for σ, in terms of u and v?(a) Is this algorithm numerically stable?(b) If so, explain why. If not, give a counterexample to illustrate.2.27 Prove that the Sherman-Morrison formula(A − uv T )−1 =2.20 Prove that if Gaussian elimination withpartial pivoting is applied to a matrix A thatis diagonally dominant by columns, then norow interchanges will occur.2.21 If A, B, and C are n × n matrices, withB and C nonsingular, and b is an n-vector,how would you implement the formulax = B −1 (2A + I)(C −1 + A)bwithout computing any matrix inverses?(c) Is an elementary elimination matrix, as defined in Section 2.2.2, elementary? If so, whatare u, v, and σ in this case?A−1 + A−1 u(1 − v T A−1 u)−1 v T A−1given in Section 2.2.8 is correct.
(Hint: Multiply both sides by A − uv T .)2.28 Prove that the Woodbury formula(A − U V T )−1 =A−1 + A−1 U (1 − V T A−1 U )−1 V T A−1given in Section 2.2.8 is correct. (Hint: Multiply both sides by A − U V T .)EXERCISES772.29 Prove that the vector p-norms satisfy theproperties given in Section 2.3.1 for p = 1, 2,and ∞.2.30 Prove that the matrix p-norms satisfythe properties given in Section 2.3.2 for p = 1and ∞.2.31 Let A be a symmetric positive definitematrix. Show that the functionkxkA = (xT Ax)1/2satisfies the three properties of a vector normgiven in Section 2.3.1.
This vector norm is saidto be induced by the matrix A.2.32 Show that the following functions satisfy the first three properties of a matrix normgiven in Section 2.3.2 and hence are matrixnorms in the more general sense mentionedthere.(a)kAkmax = max |aij |i,jNote that this is simply the ∞-norm of A con2sidered as a vector in Rn .(b)kAkF = Xi,j1/2|aij |2 Note that this is simply the 2-norm of A con2sidered as a vector in Rn .
It is called theFrobenius norm.2.33 Prove or give a counterexample: If A isa nonsingular matrix, then kA−1 k = kAk−1 .2.34 Suppose that A is a positive definite matrix.2.37 Suppose that the symmetric matrixαB=aaTAof order n + 1 is positive definite.(a) Show that the scalar α must be positiveand the n × n matrix A must be positive definite.(b) What is the Cholesky factorization of B interms of α, a, and the Cholesky factorizationof A?2.38 Suppose that the symmetric matrixB=AaTaαof order n + 1 is positive definite.(a) Show that the scalar α must be positiveand the n × n matrix A must be positive definite.(b) What is the Cholesky factorization of B interms of the constituent submatrices?2.39 Verify that the dominant term in theoperation count (number of multiplications ornumber of additions) for Cholesky factorization of a symmetric positive definite matrix oforder n is n3 /6.2.40 Let A be a band matrix with bandwidth β, and suppose that the LU factorization P A = LU is computed using Gaussianelimination with partial pivoting.
Show thatthe bandwidth of the upper triangular factorU is at most 2β.(a) Show that A must be nonsingular.2.41 Let A be a nonsingular tridiagonal matrix.(b) Show that A−1 must be positive definite.(a) Show that in general A−1 is dense.2.35 Suppose that the matrix A has a factorization of the form A = BB T , with B nonsingular. Show that A must be symmetric andpositive definite.(b) Compare the work and storage required inthis case to solve the linear system Ax = bby Gaussian elimination and back-substitutionwith those required to solve the system by explicit matrix inversion.2.36 Derive an algorithm for computing theCholesky factorization LLT of an n × n symmetric positive definite matrix A by equatingthe corresponding entries of A and LLT .This example illustrates yet another reasonwhy explicit matrix inversion is usually a badidea.78CHAPTER 2. SYSTEMS OF LINEAR EQUATIONS2.42 (a) Devise an algorithm for computingthe inverse of a nonsingular n × n triangularmatrix in place, i.e., with no additional arraystorage.(b) Is it possible to compute the inverse of ageneral nonsingular n × n matrix in place? Ifso, sketch an algorithm for doing so, and if not,explain why.
For purposes of this exercise, youmay assume that pivoting is not required.2.43 Suppose you need to solve the linear system Cz = d, where C is a complex n × n ma-trix and d and z are complex n-vectors, butyour linear equation solver handles only realsystems. Let C = A + iB and d = b √+ ic,where A, B, b, and c are real and i = −1.Show that the solution z = x + iy is given bythe 2n × 2n real linear systemAB−BA xb=.ycIs this a good way to solve this problem? Why?Computer Problems2.1 (a) Show that the matrix0.1 0.2 0.3A = 0.4 0.5 0.6 0.7 0.8 0.9is singular. Describe the set of solutions to thesystem Ax = b if0.1b = 0.3 .0.5(b) If we were to use Gaussian elimination withpartial pivoting to solve this system using exact arithmetic, at what point would the process fail?(c) Since some of the entries of A are not exactly representable in a binary floating-pointsystem, the matrix is no longer exactly singular when entered into a computer; thus, solving the system by Gaussian elimination willnot necessarily fail.
Solve this system on acomputer using a library routine for Gaussianelimination. Compare the computed solutionwith your description of the solution set in parta. If your software includes a condition estimator, what is the estimated value for cond(A)?How many digits of accuracy in the solutionwould this lead you to expect?2.2 (a) Use a library routine for Gaussianelimination to solve the system Ax = b, where 24 −22A= 49 −3 , b = 8 .−2 −1710(b) Use the LU factorization of A already computed to solve the system Ay = c, where4c = 8,−6without refactoring the matrix.(c) If the matrix A changes so that a1,2 = 2,use the Sherman-Morrison updating techniqueto compute the new solution x without refactoring the matrix, using the original righthand-side vector b.2.3 The following diagram depicts a planetruss having 13 members (the numbered lines)connected by 10 joints (the numbered circles).The indicated loads, in tons, are applied atjoints 2, 5, and 6, and we wish to determine theresulting force on each member of the truss.....................................
3 .....................4....................... 7 ........................... 4 .....................8........................................... .... .......... ... ............................................... 12..........1.............5...... 3..11.. 7 ................................. 9...................... . .............................................................................................................................................................................................................................................................1.......2.......5.......6.....
8 ..................................106213 ....................................................101520For the truss to be in static equilibrium, theremust be no net force, horizontally or vertically,at any joint. Thus, we can determine the member forces by equating the horizontal forces tothe left and right at each joint, and similarlyequating the vertical forces upward and downward at each joint. For the eight joints, thiswould give 16 equations, which is more thanCOMPUTER PROBLEMSthe 13 unknown forces to be determined. Forthe truss to be statically determinate, that is,for there to be a unique solution, we assumethat joint 1 is rigidly fixed both horizontallyand vertically, and that joint 8 is fixed vertically.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
