Conte, de Boor - Elementary Numerical Analysis. An Algorithmic Approach (523140), страница 25
Текст из файла (страница 25)
, n.144MATRICES AND SYSTEMS OF LINEAR EQUATIONS(iii) If A is an n × m matrix, then PTA is the n × m matrix whose ithrow equals the pi th row of A, i = 1, . . . , n.Example The matrixis the permutation matrix corresponding to the permutation p T = [2 3 l] sincePi1 - i2, Pi2 = i3, and Pi3 = i1. One hasHence PTi1 = i3, PT i2 = i1, PT i3 = i2, illustrating (i) of Theorem 4.5. Further, onecalculates, for example, thatHence column 2 of AP is column 3 = p2 of A, illustrating (ii) of Theorem 4.5.The Numerical Solution of Linear SystemsWe will consider only linear systemswhich have one and only one solution for every right-side b. By Theorems4.2 and 4.3, we must therefore restrict attention to those systems whichhave exactly as many equations as unknowns, i.e., for which the coefficientmatrix A is square. For such systems, Theorem 4.4 tells us that A should beinvertible in order that the system have exactly one solution for everyright-side b.
We will therefore assume that all linear systems under discussion have an invertible coefficient matrix.A frequently quoted test for invertibility of a matrix is based on theconcept of the determinant. The relevant theorem states that the matrix Ais invertible if and only if detIf detthen it is evenpossible to express the solution of Ax = b in terms of determinants, by theso-called Cramer’s rule. Nevertheless, determinants are not of practicalinterest for the solution of linear systems since the calculation of onedeterminant is, in general, of the same order of difficulty as solving thelinear system. For this reason, we make no use of determinants in solvinglinear systems, nor do we attempt to define a determinant here. However,in Sec.
4.7, we do present a method for evaluating determinants (based ona direct method for solving linear systems) for use in another context.Numerical methods for solving linear systems may be divided into twotypes, direct and iterative. Direct methods are those which, in the absenceof round-off or other errors, will yield the exact solution in a finite number4.1PROPERTIES OF MATRICES145of elementary arithmetic operations. In practice, because a computerworks with a finite word length, direct methods do not lead to exactsolutions. Indeed, errors arising from roundoff, instability, and loss ofsignificance may lead to extremely poor or even useless results. A largepart of numerical analysis is concerned with why and how these errorsarise, and with the search for methods which minimize the totality of sucherrors.
The fundamental method used for direct solutions is Gauss elimination, but even within this class there are various choices of methods andthese vary in computational efficiency and accuracy. Some of thesemethods will be examined in the next sections.Iterative methods are those which start with an initial approximationand which, by applying a suitably chosen algorithm, lead to successivelybetter approximations. Even if the process converges, we can only hope toobtain an approximate solution by iterative methods.
Iterative methodsvary with the algorithm chosen and in their rates of convergence. Someiterative methods may actually diverge; others may converge so slowly thatthey are computationally useless. The important advantages of iterativemethods are the simplicity and uniformity of the operations to be performed, which make them well suited for use on computers, and theirrelative insensitivity to the growth of round-off errors.Matrices associated with linear systems are also classified as dense orsparse. Dense matrices have very few zero elements, and the order of suchmatrices tends to be relatively small—perhaps of order 100 or less. It isusually most efficient to handle problems involving such matrices by directmethods. Sparse matrices have very few nonzero elements. They usuallyarise from attempts to solve differential equations by finite-differencemethods. The order of such matrices may be very large, and they areideally suited to solution by iterative methods which take advantage of thesparse nature of the matrix involved.
Iterative methods for solving linearand nonlinear systems will be discussed in Chap 5.EXERCISES4.1-1 Let(a)(b)(c)(d)Compute AB and BA and show thatFind (A + B) + C and A + (B + C).Show that A(BC) = (AB)C.Verify that (AB)T = BT AT .4.1-2 Show that the following matrix A is not invertible (see Theorem 4.4):146MATRICES AND SYSTEMS OF LINEAR EQUATIONS4.1-3 For the matrix A given below, find a permutation matrix P such that(a) Postmultiplication of A by P interchanges the fourth and the first columns of A(b) Premultiplication of A by P interchanges the third row and the first row of A4.14 In the matrix A in Exercise 4.1-3 find a sequence of permutation matrices which willtransform A into the form4.1-5 Write the following system in matrix form and identify the matrix A and the vector b4.1-6 Convince yourself that the notion of invertibility makes sense for square matrices onlyby proving the following: Let A be an m × n matrix; if B and C are n × m matrices suchthat AB = Im and CA = In then B = C = A-1; in particular, then m = n.
[Hint: Prove firstthat B = C. Then show that m = trace (AB) = trace (BA) = n, where the trace of a squarematrix is defined as the sum of its diagonal entries.]4.1-7 Make use of Theorem 4.4 to prove that a permutation matrix is invertible.4.1-8 Make use of Theorem 4.4 to prove that, if A and B are square matrices such that theirproduct is invertible, then both A and B must be invertible.4.1-9 Do the vectorsform a basis?4.1-10 Prove that the three vectorsform a linearly independent set. Do they form a basis?4.1-11 For each of the three operations with matrices, namely, addition of two matrices,multiplication of two matrices, and multiplication of a scalar with a matrix, write a FORTRAN subroutine which carries out the operation on appropriate input and returns theresulting matrix.4.1-12 If p(x) = c 0 + c 1 x + c 2 x 2 + · · · + c k x k is a given polynomial and A is a givenn × n matrix, then the matrix p(A) is defined byHere A0 = I, A1 = A, and for j > 1, Aj = A(Aj-1 ).
Write an efficient FORTRAN subroutine with arguments N. KP1, A, C, PA, where N is the order of the matrix A, and PA is to4.2THE SOLUTION OF LINEAR SYSTEMS BY ELIMINATION147contain, on return, the matrix p(A), with C a one-dimensional array containing C(i) = Ci-1i = 1, . . . , KP1.
Do not use any arrays in the subroutine other than the arrays A, C, and PA.(Hint: Remember Algorithm 2.1.)4.1-13 Suppose there exists, for a given matrix A of order n, a polynomial p(x) such thatwhile p(A) is the null matrix. Prove that A must be invertible.4.1-14 Verify the rules stated in (4.11).4.1-15 The Vandermonde matrix for the points x0, . . . , xn is, by definition, the matrix oforder n + 1 given byThe matrix plays a prominent role in some treatments ofpolynomial interpolation because it is the coefficient matrix in the linear systemfor the power coefficients of the interpolating polynomial. Use the Lagrange polynomials(2.6) to construct the inverse for V in case n = 3.
What is the relationship between the powerform of the Lagrange polynomials for x0, . . . , xn and the entries of the inverse of V?4.2 THE SOLUTION OF LINEAR SYSTEMS BYELIMINATIONLet A be a given square matrix of order n, b a given n-vector. We wish tosolve the linear systemAx = b(4.14)for the unknown n-vector x. The solution vector x can be obtained withoutdifficulty in case A is upper-triangular with all diagonal entries nonzero.For then the system (4.14) has the form(4.15)In particular, the last equation involves only xn; hence, sincemust haveweSince we now know xn, the second last equationinvolves only one unknown, namely, xn-1 . Asit follows that148MATRICES AND SYSTEMS OF LINEAR EQUATIONSWith xn and xn-1 now determined, the third last equationcontains only one true unknown, namely, xn-2 .
Once again, since a n-2 ,we can solve for xn-2 ,n-2In general, with xk+1, xk+2, . . . , xn already computed, the k th equationcan be uniquely solved for xk, sinceto giveThis process of determining the solution of (4.15) is called backsubstitution.Algorithm 4.1: Back-substitution Given the upper-triangular n × nmatrix A with none of the diagonal entries equal to zero, and then-vector b. The entries xn, xn-1, . . . , x1 of the solution x of Ax = bcan then be obtained (in that order) byHere, two remarks are in order: When k = n, then the summationwhich is interpreted as the sum over no terms andgives, by convention, the value 0. Also, we note the following consequence,almost evident from our description of back-substitution.Theorem 4.6 An upper-triangular matrix A is invertible if and only ifall its diagonal entries are different from zero.Indeed, back-substitution shows that the linear system Ax = b has atmost one solution for given b, in case all diagonal entries of A are nonzero;hence, by Theorem 4.4, A must be invertible.
On the other hand, for eachj = 1, . . . , n, there exist x1, . . . , xj not all zero so that4.2 THE SOLUTION OF LINEAR SYSTEMS BY ELIMINATION 149by Theorem 4.2. But then, if ajj = 0, the vector y = [x1 · · · xj0 · · · 0]T isnot the zero vector, yet satisfies Ay = 0, showing, by Theorem 4.4, that Ais not invertible.We are therefore justified in calling the vector x calculated by Algorithm 4.1 the solution of (4.15).Example 4.1 Consider the following linear system:(4.16)From the last equation, x3 = b3/a33 == 3.
With this, from the second (last) equation,x 2 = (b 2 - a 2 3 x 3 )/a 2 2 = (-7 + 3)/(-2) = 2. Hence, from the first equation, x 1 =(b1 - a12x2 - a13x3)/a11 = (5 - 3.2 + 3)/2 = 1.If now the coefficient matrix A of the system Ax = b is not uppertriangular, we subject the system first to the method of elimination due toGauss. This method is probably familiar to the student, from elementaryalgebra.
Its objective is the transformation of the given system into anequivalent system with upper-triangular coefficient matrix. The latter system can then be solved by back-substitution.We say that the two linear systems Ax = b andare equivalentprovided any solution of one is a solution of the other.Theorem 4.7 Let Ax = b be a given linear system, and suppose wesubject this system to a sequence of operations of the following kind:(i) Multiplication of one equation by a nonzero constant(ii) Addition of a multiple of one equation to another equation(iii) Interchange of two equationsIf this sequence of operations produces the new systemthenthe systems Ax = b andare equivalent.
In particular, then, Ais invertible if and only ifis invertible.See Exercise 4.2-11 for a proof.Elimination is based on this theorem and the following observation: IfAx = b is a linear system and if, for some k and j,then we caneliminate the unknown xj from any equationby adding -(a i j /a k j )times equation k to equation i. The resulting systemis equivalentto the original system.In its simplest form, Gauss elimination derives from a given linearsystem Ax = b of order n a sequence of equivalent systems A(k)x = b( k ) ,k = 0, . . . , n - 1. Here A(0) x = b(0) is just the original system.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
