Conte, de Boor - Elementary Numerical Analysis. An Algorithmic Approach (523140), страница 30
Текст из файла (страница 30)
A norm retains certain properties of the absolute valuefor numbers. Specifically, a norm assigns to each n-vector a a real numbercalled the norm of a, subject to the following reasonable restrictions:(4.33)The first restriction forces all n-vectors but the zero vector to havepositive “length.” The second restriction states, for example, that a and itsnegative -a have the same “length” and that the length of 3a is threetimes the length of a. The third restriction is the triangle inequality, socalled since it states that the sum of the lengths of two sides of a triangle isnever smaller than the length of the third side.The student is presumably familiar with the euclidean length or norm,of the n-vector a = (ai ), at least for the case n = 2 or n = 3.
But, for areason made clear below, we prefer to use, in the numerical examplesbelow, the maximum norm (4.31) as a way to measure the size or length ofthe n-vector a. It is not difficult to verify that (4.31) defines a norm, i.e.,thatsatisfies the three properties of a norm listed in (4.33). Asto (i),is the maximum of nonnegative quantities, hence nonnegative;also,if and only if, for all i, |ai | = 0, which is the same as sayingthat a = 0.
Further, ifis any scalar, then172MATRICES AND SYSTEMS OF LINEAR EQUATIONSproving (ii). Finally,proving (iii).Other vector norms in frequent use include the 1-normand various instances of the weighted p-normwhere p is some number between 1 andand the numbers w1, . . . , wnare fixed positive quantities. The case p = 2, wi = 1 (all i ) leads to thefamiliar euclidean norm.Once a vector norm is chosen, we then measure the corresponding sizeof an n × n matrix A by comparing the size of Ax with the size of x.Precisely, we define the corresponding matrix norm of A by(4.34)where the maximum is taken over all (nonzero) n-vectors x.
It can beshown that this maximum exists for every n × n matrix A (and any choiceof the vector norm). The matrix norm ||A|| is characterized by the following two facts:and(4.35)Of course, (4.35) implies at once that ||Ax|| = ||A|| ||x|| for any x with||Ax|| > ||A|| ||x||. Further, the following properties can be shown to holdfor the matrix norm (4.34):(4.36)so that the term “norm” for the number ||A|| is justified.In addition,(4.37)4.5ERROR AND RESIDUAL OF AN APPROXIMATE SOLUTION; NORMS173Finally, if the matrix A is invertible, then x = A-1(Ax); hence ||x|| <||A || ||Ax||. Combining this with (4.35), one gets-1(4.38)and both inequalities are sharp; i.e., each can be made an equality by anappropriate choice of a (nonzero) x.As it turns out, the matrix normbased on the euclidean vector norm, is usually quite difficult to calculate,while the matrix normbased on the maximum norm, can be calculated quite easily, it being thenumber(4.39)To prove this, we have to show that the numbersatisfies the two statements in (4.35), i.e., thatFor all n-vectors x,andFor some nonzero x,But for an arbitrary x,which proves the first statement.
As to the second statement, let i0 be aninteger between 1 and n so thatand let x be an n-vector of max-norm 1 such that174MATRICES AND SYSTEMS OF LINEAR EQUATIONSe.g., takeThen, for this clearly nonzero vector x,andwhich proves the second statement.Example 4.5a For the coefficient matrix A of Example 4.5, one readily findsWe have seen thatHenceThereforeConsequently,= max{|25.25| + | - 24.75|, | - 24.75| + |25.25|} = 50.For this example, then, (4.38) states thatFor all 2-vectors x,Choosingwe getand the secondinequality becomes equality.
Choosingand the first inequality is an equality for this choice.We now return to our discussion of the relationship between the errorin the approximate solution of Ax = b and the residualWe haveHence e = A-1 r. Therefore, remembering that (A-1 )-1 = A, we get from(4.38)(4.40)This gives an upper and a lower bound on the relative error ||e||/||x|| in4.5ERROR AND RESIDUAL OF AN APPROXIMATE SOLUTION; NORMS175terms of the relative residual ||r||/||b||, namely(4.41)Here, one can estimate ||x|| from a computed solution for the systemAx = b. Else, use (4.40) in the special casei.e.,to conclude from (4.41) that(4.42)The bounds (4.41) and (4.42) are sharp in the following sense.Whatever A andmight be, there are nonzero choices for e or r forwhich one or the other of the inequalities in (4.41) becomes an equality.
Ifone wants equality in one of the inequalities in (4.42), one would have tochoose a particular x as well, but such choices are always possible.Because of their importance, we state (4.41) and (4.42) in words: Therelative error in an approximate solution for the linear system Ax = b canbe as large as ||A|| ||A-1|| times, or, more precisely, as large as||A-1|| ||b||/||x|| times, its relative residual, but it can also be as small as1/(||A|| ||A-1||) times, or, more precisely, as small as ||b||/(||A|| ||x||) timesits relative residual.
Hence, ifthen the relative error andrelative residual are always of the same size, and the relative residual canthen be safely used as an estimate for the relative error. But the larger||A|| ||A-1|| is, the less information about the relative error can be obtainedfrom the relative residual.The number ||A|| ||A-1|| is called the condition number of A and is attimes abbreviatedNote that the condition number cond(A) for A depends on the matrixnorm used and can, for some matrices, vary considerably as the matrixnorm is changed. On the other hand, the condition number is always atleast 1, since for the identity matrix I, ||I|| = max||x||/||x|| = 1, and by(4.37), ||I|| = ||AA-1 || < ||A|| ||A-1 ||.Example 4.6 We find from earlier calculations that,Example 4.5,that indeed the relative error of an approximate solutionrelative residual, but can also be justof its relativefor the coefficient matrix A ofFurther, we saw in Example 4.5can be as large as 100 times itsresidual.The bounds (4.41) and (4.42) require the number ||A-1|| which is notreadily available.
But, in typical situations, a good estimate for ||e|| is the176MATRICES AND SYSTEMS OF LINEAR EQUATIONSnumberwith the computed solution of the linear system Ae = r.Sinceis usually obtained by Gauss elimination, a factorization for A isavailable and can therefore be obtained (by SUBST) with much lesscomputational effort than was needed to obtainThis presupposes that ris calculated in double precision. The vectorso obtained is the firstiterate in iterative improvement (Algorithm 4.5) discussed in the nextsection.EXERCISES4.5-1 Verify thatdefines a norm for all n-vectors a.4.5-2 Prove that the matrix norm ||A||1 associated with the vector norm ||a||1 of Exercise 4.5-1can be calculated by4.5-3 If we interpret a 2-vector a as a point in the plane with coordinates {a1, a2}, then its2-norm ||a||2 is the euclidean distance of this point from the origin. Further, the set of allvectors of euclidean norm 1 forms a circle around the origin of radius 1.
Draw the “circle ofradius 1 around the origin” when the distance of the “point” a is measured by (a) the 1-norm||a||1, (b) the norm ||a||3/2, (c) the euclidean norm ||a||2, (d) the norm ||a||4, (e) the max-norm4.5-4 With the same interpretation of 2-vectors as points in the plane as used in Exercise4.5-3, show that, for any two 2-vectors a and b, the three “points” 0, a, and a + b are thevertices of a triangle with sides of (euclidean) length ||a||2, ||b||2, and ||a + b||2, and explain theterm “triangle inequality” for property (iii) of norms [Eq.
(4.33)].4.5-5 Show that, for any 2-vectors a and b and any particular vector norm,4.5-6 Show that, for any 2-vectors a and b, and any numberbetween 0 and 1,4.5-7 Show that the matrix norm ||A|| = max(||Ax||/||x||) can also be calculated as4.5-8 Prove all the statements in (4.36) regarding matrix norms.4.5-9 Use Exercise 4.5-7 to calculate ||A||2, where(Hint: A 2-vector x has 2-norm ||x||2 = 1 if and only if4.5-10 Use Exercise 4.4-2 to calculate the condition number of the coefficient matrixsystem of Exercise 4.2-8; then discuss relative error and relative residuals of thecalculated in Exercises 4.2-8 and 4.3-4 in terms of this condition number.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
