Heath - Scientific Computing (523150), страница 22
Текст из файла (страница 22)
SYSTEMS OF LINEAR EQUATIONS2.23 True or false: kAk1 = kAT k∞ .2.24 True or false: If A is any n × n nonsingular matrix, then cond(A) = cond(A−1 ).2.25 True or false: In solving a nonsingularsystem of linear equations, Gaussian elimination with partial pivoting usually yields a smallresidual even if the matrix is ill-conditioned.2.26 True or false: Since the multipliers inGaussian elimination with partial pivoting arebounded by 1 in magnitude, the elements ofthe successive reduced matrices cannot growin magnitude.2.27 Can a system of linear equations Ax = bhave exactly two distinct solutions?2.28 Can the number of solutions to a linearsystem Ax = b ever be determined solely fromthe matrix A without knowing the right-handside vector b?2.29 In solving a square system of linear equations Ax = b, which would be a more seriousdifficulty: that the rows of A are linearly dependent, or that the columns of A are linearlydependent? Explain.2.30 (a) State one defining property of a singular matrix A.(b) Suppose that the linear system Ax = bhas two distinct solutions x and y.
Use theproperty you gave in part a to prove that Amust be singular.2.31 Given a nonsingular system of linearequations Ax = b, what effect on the solution vector x results from each of the followingactions?(a) Permuting the rows of [ Ab](b) Permuting the columns of A(c) Multiplying both sides of the equation fromthe left by a nonsingular matrix M2.32 Suppose that both sides of a system oflinear equations Ax = b are multiplied by anonzero scalar α.2.33 Suppose that both sides of a system oflinear equations Ax = b are premultiplied bya nonsingular diagonal matrix.(a) Does this change the true solution x?(b) Can this affect the conditioning of the system?(c) Can this affect the choice of pivots in Gaussian elimination?2.34 With a singular matrix and the use of exact arithmetic, at what point will the solutionprocess break down in solving a linear systemby Gaussian elimination(a) With partial pivoting?(b) Without pivoting?2.35 (a) What is the difference between partial pivoting and complete pivoting in Gaussian elimination?(b) State one advantage of each type of pivoting relative to the other.2.36 Consider the following matrix A, whoseLU factorization we wish to compute usingGaussian elimination:4−81A = 657.0 −10 −3What will the initial pivot element be if(a) No pivoting is used?(b) Partial pivoting is used?(c) Complete pivoting is used?2.37 Give two reasons why pivoting is essential for a numerically stable implementation ofGaussian elimination.2.38 If A is an ill-conditioned matrix, andits LU factorization is computed by Gaussianelimination with partial pivoting, would youexpect the ill-conditioning to be reflected inL, in U , or both? Why?(b) Does this change the residual vector r =b − Ax for a given x?2.39 (a) What is the inverse of the followingmatrix?1 0 0 00 1 0 00 m1 1 00 m2 0 1(c) What conclusion can be drawn about assessing the quality of a computed solution?(b) How might such a matrix arise in computational practice?(a) Does this change the true solution x?REVIEW QUESTIONS2.40 (a) Can every nonsingular n × n matrixA be written as a product, A = LU , where Lis a lower triangular matrix and U is an uppertriangular matrix?(b) If so, what is an algorithm for accomplishing this? If not, give a counterexample to illustrate.2.41 Given an n × n nonsingular matrix Aand a second n × n matrix B, what is the bestway to compute the n × n matrix A−1 B?2.42 If A and B are n × n matrices, with Anonsingular, and c is an n-vector, how wouldyou efficiently compute the product A−1 Bc?2.43 If A is an n × n matrix and x is an nvector, which of the following computations requires less work? Explain.(a) y = (x xT ) A(b) y = x (xT A)2.44 How does the computational work insolving an n × n triangular system of linearequations compare with that for solving a general n × n system of linear equations?2.45 Assume that you have already computedthe LU factorization, A = LU , of the nonsingular matrix A.
How would you use it to solvethe linear system AT x = b?2.46 If L is a nonsingular lower triangularmatrix, P is a permutation matrix, and b isa given vector, how would you solve each ofthe following linear systems?(a) LP x = b(b) P Lx = b2.47 In the plane R2 , is it possible to have avector x 6= o such that kxk1 = kxk∞ ? If so,give an example.2.48 In the plane R2 , is it possible to havetwo vectors x and y such that kxk1 > kyk1 ,but kxk∞ < kyk∞ ? If so, give an example.2.49 In general, which matrix norm is easierto compute, kAk1 or kAk2 ? Why?2.50 (a) Is the magnitude of the determinantof a matrix a good indicator of whether thematrix is nearly singular?(b) If so, why? If not, what is a better indicator of near singularity?732.51 (a) How is the condition number of amatrix A defined for a given matrix norm?(b) How is the condition number used in estimating the accuracy of a computed solution toa linear system Ax = b?2.52 Why is computing the condition numberof a general matrix a nontrivial problem?2.53 Give an example of a 3 × 3 matrix A,other than the identity matrix I, such thatcond(A) = 1.2.54 Suppose that the n × n matrix A isperfectly well-conditioned, i.e., cond(A) = 1.Which of the following matrices would thennecessarily share this same property?(a) cA, where c is any nonzero scalar(b) DA, where D is any nonsingular diagonalmatrix(c) P A, where P is any permutation matrix(d ) BA, where B is any nonsingular matrix(e) A−1 , the inverse of A(f ) AT , the transpose of A2.55 Let A = diag( 12 ) be an n × n diagonalmatrix with all its diagonal entries equal to 12 .(a) What is the value of det(A)?(b) What is the value of cond(A)?(c) What conclusion can you draw from theseresults?2.56 Suppose that the n × n matrix A is exactly singular, but its floating-point representation, fl(A), is nonsingular.
In this case, whatwould you expect the order of magnitude of thecondition number cond(fl(A)) to be?2.57 Classify each of the following matrices aswell-conditioned or ill-conditioned: 10100(a)010−10 10100(b)01010 −10100(c)010−101 2(d )2 474CHAPTER 2. SYSTEMS OF LINEAR EQUATIONS2.58 Which of the following are good indicators that a matrix is nearly singular?(a) Its determinant is small.(b) Its norm is small.(c) Its norm is large.(d ) Its condition number is large.2.59 In a floating-point system having 10 decimal digits of precision, if Gaussian eliminationwith partial pivoting is used to solve a linearsystem whose matrix has a condition numberof 103 , and whose input data are accurate tofull machine precision, about how many digitsof accuracy would you expect in the solution?2.60 Assume that you are solving a system oflinear equations Ax = b on a computer whosefloating-point number system has 12 decimaldigits of precision, and that the problem dataare correct to full machine precision.
Abouthow large can the condition number of the matrix A be before the computed solution x willcontain no significant digits?2.61 Under what circumstances does a smallresidual vector r = b − Ax imply that x is anaccurate solution to the linear system Ax = b?2.62 Let A be an arbitrary square matrix andc an arbitrary scalar. Which of the followingstatements must necessarily hold?(a) kcAk = |c| · kAk.(b) cond(cA) = |c| · cond(A).2.63 (a) What is the main difference betweenGaussian elimination and Gauss-Jordan elimination?(b) State one advantage of each type of elimination relative to the other.2.64 Rank the following methods according tothe amount of work required for solving a general system of linear equations of order n:(a) Gauss-Jordan elimination(b) Gaussian elimination with partial pivoting(c) Cramer’s rule(d ) Explicit matrix inversion followed bymatrix-vector multiplication2.65 (a) How much storage is required tostore an n × n matrix of rank one efficiently?(b) How many arithmetic operations are required to multiply an n-vector by an n × nmatrix of rank one efficiently?2.66 In a comparison of ordinary Gaussianelimination with Gauss-Jordan elimination forsolving a linear system Ax = b,(a) Which has a more expensive factorization?(b) Which has a more expensive backsubstitution?(c) Which has a higher cost overall?2.67 For each of the following elimination algorithms for solving linear systems, is thereany pivoting strategy that can guarantee thatall of the multipliers will be at most 1 in absolute value?(a) Gaussian elimination(b) Gauss-Jordan elimination2.68 What two properties of a matrix A together imply that A has a Cholesky factorization?2.69 List three advantages of Cholesky factorization compared with LU factorization.2.70 How many square roots are required tocompute the Cholesky factorization of an n×nsymmetric positive definite matrix?2.71 Let A = {aij } be an n × n symmetricpositive definite matrix.(a) What is the (1, 1) entry of its Choleskyfactor L?(b) What is the (n, 1) entry of its Choleskyfactor L?2.72 What is the Cholesky factorization ofthe following matrix?4 22 22.73 (a) Is it possible, in general, to solve asymmetric indefinite linear system at a costsimilar to that for using Cholesky factorization to solve a symmetric positive definite linear system?(b) If so, what is an algorithm for accomplishing this? If not, why?2.74 Give two reasons why iterative improvement for solutions of linear systems is oftenimpractical to implement.EXERCISES752.75 Suppose you have already solved then × n linear system Ax = b by LU factorization and back-substitution.
What is the further cost (order of magnitude will suffice) ofsolving a new system(a) With the same matrix A but a differentright-hand-side vector?(b) With the matrix changed by adding a matrix of rank one?(c) With the matrix A changed completely?Exercises2.1 In Section 2.1.1, four defining propertiesare given for a singular matrix. Show thatthese four properties are indeed equivalent.2.2 Suppose that each of the row sums of ann × n matrix A is equal to zero. Show that Amust be singular.2.3 Suppose that A is a singular n × n matrix. Prove that if the linear system Ax = bhas at least one solution x, then it has infinitely many solutions.2.4 (a) Show that the following matrix issingular.1 1 0A = 1 2 11 3 2T(b) If b = [ 2 4 6 ] , how many solutions arethere to the system Ax = b?2.5 What is the inverse oftrix?10A = 1 −11 −2the following ma0012.6 Let A be an n × n matrix such thatA2 = 0, the zero matrix.
Show that A mustbe singular.2.7 LetA=11+.1−1(a) What is the determinant of A?(b) In floating-point arithmetic, for what rangeof values of will the computed value of thedeterminant be zero?(c) What is the LU factorization of A?(d ) In floating-point arithmetic, for whatrange of values of will the computed valueof U be singular?2.8 Let A and B be any two n × n matrices.(a) Prove that (AB)T = B T AT .(b) If A and B are both nonsingular, provethat (AB)−1 = B −1 A−1 .2.9 Let A be any nonsingular matrix.
Provethat (A−1 )T = (AT )−1 . For this reason, thenotation A−T can be used unambiguously todenote this matrix.2.10 Let P be any permutation matrix.(a) Prove that P −1 = P T .(b) Prove that P can be expressed as a product of pairwise interchanges.2.11 Write out a detailed algorithm for solving a lower triangular linear system Lx = b byforward-substitution.2.12 Verify that the dominant term in theoperation count (number of multiplications ornumber of additions) for solving a lower triangular system of order n by forward substitutionis n2 /2.2.13 How would you solve a partitioned linearsystem of the form L1 Oxb=,B L2ycwhere L1 and L2 are nonsingular lower triangular matrices, and the solution and righthand-side vectors are partitioned accordingly?Show the specific steps you would perform interms of the given submatrices and vectors.2.14 Prove each of the four properties of elementary elimination matrices enumerated inSection 2.2.2.2.15 (a) Prove that the product of two lowertriangular matrices is lower triangular.(b) Prove that the inverse of a nonsingularlower triangular matrix is lower triangular.76CHAPTER 2.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
