Heath - Scientific Computing (523150), страница 18
Текст из файла (страница 18)
The 1-norm orthe ∞-norm is usually used in analyzing the sensitivity of solutions to linear systems. Wewill also use the 2-norm later on in other contexts. The differences among these norms areillustrated in Fig. 2.1, which shows the unit sphere, {x: kxk = 1}, in two dimensions foreach norm.1.5(−1.6, 1.2)........................ ........................................................................................................................................................................... ................ .......
....... ....................... ........................................................................... ................. ........... ................ .......... .... ........ ............. ................ ..... ...................... ...... .............. ......
................. ................. ......... ............. ........ ................................... ..... ........ .............. ....... ............ ............. ... ........ ........... .... ............. ..... ............. ....... ............. ............................................................................. ....... ...... ..................................................................................................................................................................................∞21−2.02.0−1.5Figure 2.1: The unit sphere in various vector norms.The norm of a vector is simply the factor by which the corresponding unit sphere mustbe expanded or shrunk to encompass the vector. For example, the norms have the followingvalues for the vector shown in Fig. 2.1: −1.6 = 2.8, −1.6 = 2.0, −1.6 = 1.6.
1.2 1.2 1.2 12∞In general, for any vector x in Rn , we havekxk1 ≥ kxk2 ≥ kxk∞ .On the other hand, we also have√√kxk1 ≤ n kxk2 , kxk2 ≤ n kxk∞ ,and kxk1 ≤ n kxk∞ .Thus, for a given n, any two of the norms differ by at most a constant, so they are allequivalent in the sense that if one is small, they must all be proportionally small. Hence,we can choose whichever norm is most convenient in a given context. In the remainder ofthis book, an appropriate subscript will be used to indicate a specific norm, when necessary,but the subscript will be omitted when it does not matter which particular norm is used.For any vector norm, the following important properties hold, where x and y are anyvectors:56CHAPTER 2.
SYSTEMS OF LINEAR EQUATIONS1. kxk > 0 if x 6= o.2. kγxk = |γ| · kxk for any scalar γ.3. kx + yk ≤ kxk + kyk (triangle inequality).In a more general treatment, these three properties can be taken as the definition of a vectornorm. A useful variation on the triangle inequality iskx − yk ≥ kxk − kyk.2.3.2Matrix NormsWe also need some way to measure the size or magnitude of matrices. Again, a more generaldefinition is possible, but all of the matrix norms we will use are defined in terms of anunderlying vector norm. Specifically, given a vector norm, we define the correspondingmatrix norm of a matrix A as follows:kAk = maxx6=0kAxk.kxkSuch a matrix norm is said to be subordinate to the vector norm. Intuitively, the norm ofa matrix measures the maximum stretching the matrix does to any vector, as measured inthe given vector norm.Some matrix norms are much easier to compute than others.
For example, the matrixnorm corresponding to the vector 1-norm is simply the maximum absolute column sum ofthe matrix,nXkAk1 = max|aij |,ji=1and the matrix norm corresponding to the vector ∞-norm is simply the maximum absoluterow sum of the matrix,nXkAk∞ = max|aij |.ij=1A handy way to remember these is that the matrix norms agree with the correspondingvector norms for an n × 1 matrix. Unfortunately, the matrix norm corresponding to thevector 2-norm is not so simple to compute; it turns out to be equal to the square root of thelargest eigenvalue of the matrix AT A, or, as we shall see later, the largest singular value ofA (see Section 4.5.2).The matrix norms we have defined satisfy the following important properties, where Aand B are any matrices:1.2.3.4.5.kAk > 0 if A 6= O.kγAk = |γ| · kAk for any scalar γ.kA + Bk ≤ kAk + kBk.kABk ≤ kAk · kBk.kAxk ≤ kAk · kxk for any vector x.2.3.
NORMS AND CONDITION NUMBERS57In a more general treatment, the first three properties can be taken as the definition ofa matrix norm. The remaining two properties, known as submultiplicative or consistencyconditions, may or may not hold for these more general matrix norms, but they always holdfor the matrix norms subordinate to the vector p-norms.2.3.3Condition Number of a MatrixThe condition number of a square nonsingular matrix A with respect to a given norm isdefined ascond(A) = kAk · kA−1 k.By convention, cond(A) = ∞ if A is singular. SincekAk · kA−1k=kAxkmaxx6=0 kxk kAxk −1· min,x6=0 kxkthe condition number of a matrix measures the ratio of the maximum stretching that thematrix does to any nonzero vector to the maximum shrinking.
We will see in Section 2.4.2that this concept is consistent with the general notion of condition number defined inSection 1.2.5: the condition number of the matrix bounds the ratio of the relative changein the solution of a linear system to a given relative change in the input data.The condition number is a measure of how close a matrix is to being singular: a matrixwith a large condition number (which we will quantify in Section 2.4.2) is nearly singular,whereas a matrix with a condition number close to 1 is far from being singular. Note thatthe determinant of a matrix is not a good indicator of near singularity: although a matrixA is singular if det(A) = 0, the magnitude of a nonzero determinant, large or small, givesno information on how close to singular the matrix may be. For example, det(αIn ) = αn ,which can be arbitrarily small for |α| < 1, yet the matrix is perfectly well-conditioned forany nonzero α, with a condition number of 1.Some important properties of the condition number are1.2.3.4.5.ForForForForForany matrix A, cond(A) ≥ 1.the identity matrix, cond(I) = 1.any permutation matrix P , cond(P ) = 1.any matrix A and nonzero scalar γ, cond(γA) = cond(A).any diagonal matrix D = diag(di ), cond(D) = (max |di |)/(min |di |).As we will see shortly, the usefulness of the condition number is in assessing the accuracyof solutions to linear systems.
Since the definition of the condition number involves theinverse of the matrix, computing its value is obviously a nontrivial task. In fact, to computethe condition number literally would require substantially more work than solving the linearsystem whose accuracy is to be assessed using the condition number. In practice, therefore,the condition number is merely estimated, to perhaps within an order of magnitude, as arelatively inexpensive byproduct of the solution process.The matrix norm kAk is easily computed as the maximum absolute column sum (orrow sum, depending on the norm used). It is estimating kA−1 k at low cost that presents a58CHAPTER 2.
SYSTEMS OF LINEAR EQUATIONSchallenge. From the properties of norms, we know that if z is the solution to Az = y, thenkzk≤ kA−1 k,kykand the bound is achieved for some optimally chosen vector y. We thus wish to pick avector y so that the ratio kzk/kyk is as large as possible and therefore is a reasonableestimate for kA−1 k. Finding the optimal y would be prohibitively expensive, but a usefulapproximation can be obtained much more cheaply.
One heuristic is to choose y as thesolution to the system AT y = c, where c is a vector whose components are ±1, with thesigns chosen successively to make the resulting y as large as possible.The motivation for this approach may not be obvious now, but it is essentially equivalent to one step of inverse iteration for computing the singular vector corresponding tothe smallest singular value of A (see Chapter 4). An alternative approach to conditionestimation is to treat it as a convex optimization problem that can be solved very efficientlyin practice using a heuristic algorithm. Most good modern software packages for solvinglinear systems provide an efficient and reliable condition estimator, based on a sophisticatedimplementation of one of the methods outlined here.2.42.4.1Accuracy of SolutionsResidual of a SolutionIntuitively, the most obvious way to check the validity of a solution is to substitute it intothe equation to see how closely the two sides match.
The residual vector of an approximatesolution x̂ to the n × n linear system Ax = b is defined asr = b − Ax̂.In theory, if A is nonsingular, then the error kx̂ − xk = 0 if and only if krk = 0. In practice,however, these quantities are not necessarily small simultaneously. If the computed solutionx̂ exactly satisfies(A + E)x̂ = b,thenkrk = kb − Ax̂k = kE x̂k ≤ kEk · kx̂k,so that we have the inequalitykEkkrk≤kAk · kx̂kkAkrelating the relative residual to the relative change in the matrix.
Thus, a large relativeresidual implies a large backward error in the matrix, which means that the algorithm usedto compute the solution is unstable.But how large is kEk likely to be in practice? Wilkinson [273] showed that for LUfactorization by Gaussian elimination, a bound of the formkEk≤ ρ n machkAk2.4. ACCURACY OF SOLUTIONS59holds, where ρ, called the growth factor , is the ratio of the largest entry of U to the largestentry of A.
Without pivoting, ρ can be arbitrarily large, and hence Gaussian eliminationwithout pivoting is unstable, as we have already seen. With partial pivoting, the growthfactor can still be as large as 2n−1 (since in the worst case the size of the entries can doubleat each stage of elimination), but such behavior is extremely rare. In practice, there is littleor no growth in the size of the entries, so thatkEk≈ n mach .kAkThis relation means that solving a linear system by Gaussian elimination with partial pivoting followed by back-substitution almost always yields a very small relative residual,regardless of how ill-conditioned the system may be. Thus, a small relative residual is notnecessarily a good indicator that a computed solution is close to the “true” solution unlessthe system is well-conditioned.Complete pivoting yields an even smaller growth factor, in both theory and practice,but the additional margin of stability it provides is usually not worth the extra expense.Example 2.10 Small Residual.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
