Heath - Scientific Computing (523150), страница 30
Текст из файла (страница 30)
The input typicallyrequired includes a two-dimensional array containing the matrix A, a one-dimensional arraycontaining the right-hand-side vector b (or a two-dimensional array for multiple right-handside vectors), the number of rows m and number of columns n in the matrix, the leadingdimension of the array containing A (so that the subroutine can interpret subscripts properly in the array), and possibly some work space and a flag indicating the particular taskto be performed. The user may also need to supply the relevant tolerance if column pivoting or other means of rank determination is performed.
On return, the solution x usuallyoverwrites the storage for b, and the matrix factorization overwrites the storage for A.In MATLAB, the backslash operator used for solving square linear systems is extended toinclude rectangular systems as well. Thus, the least squares solution to the overdeterminedsystem Ax ≈ b is given by x = A \ b. Internally, the solution is computed by QR factorization, but the user need not be aware of this. The QR factorization can be computedexplicitly, if desired, by the MATLAB qr function, [Q, R] = qr(A).In addition to mathematical software libraries such as those listed in the table, manystatistical packages have extensive software for solving least squares problems in variouscontexts, and they often include many diagnostic features for assessing the quality of theresults. Well-known packages in this category include BMDP, Minitab, Omnitab, S, SAS, andSPSS.
There is also a statistics toolbox available for MATLAB. Additional software is available3.7. HISTORICAL NOTES AND FURTHER READING105for data fitting using criteria other than least squares, particularly for the 1-norm and the∞-norm, which are preferable in some contexts.3.7Historical Notes and Further ReadingThe normal equations method for least squares problems, due to Gauss, dates from around1800, and Gram-Schmidt orthogonalization from around 1900. The orthogonalization methods of Householder and Givens date from the late 1950s, and the numerically stable modifiedform of Gram-Schmidt orthogonalization dates from the 1960s.
The use of orthogonalization, particularly the Householder method, for solving least squares problems was popularized by Golub [101]. A tutorial introduction to Householder transformations (treating onlysquare systems) can be found in [28]. Comprehensive references on least squares computations include [19, 76, 163]. The books on matrix computations cited in Chapter 2 alsodiscuss linear least squares problems in some detail. For a statistical perspective on leastsquares computations, see [148, 254].We have discussed only the simplest type of least squares problems, in which the modelfunction is linear, only the values yi of the dependent variable are subject to random error(i.e., the values ti of the independent variable t are taken as exact), and all of the datapoints are weighted equally.
We will discuss nonlinear least squares problems in Section 6.4.Incorporating varying weights for the data points or more general cross-correlations amongthe variables is relatively straightforward within the framework we have discussed. Allowingvarying weights for the data points, for example, simply involves multiplying both sides ofthe least squares system by a diagonal matrix. When all of the variables are subject torandom error, so that the entries of the matrix A as well as those of the right-hand-sidevector b are uncertain, then minimizing the vertical distances between the data points andthe fitted curve may no longer be appropriate.
Minimizing the orthogonal distances betweenthe data points and the curve is a reasonable alternative. It yields a more complicatedcomputational problem, but one that is still tractable using the singular value decomposition(see Section 4.5.2). For a thorough discussion of this approach, called total least squares,see [259].Review Questions3.1 True or false: If you are given four ormore data points, then fitting a straight lineto the data is a linear least squares problem,whereas fitting a quadratic polynomial to thedata is a nonlinear least squares problem.3.2 True or false: At the solution to a linearleast squares problem Ax ≈ b, the residualvector r = b − Ax is orthogonal to the columnspace of A.3.3 True or false: An overdetermined linear least squares problem Ax ≈ b always hasa unique solution x that minimizes the Euclidean norm of the residual vector r = b−Ax.3.4 True or false: In solving a linear leastsquares problem Ax ≈ b, if the vector b liesin the column space of the matrix A, then theresidual is o.3.5 True or false: In solving a linear leastsquares problem Ax ≈ b, if the residual is o,then the solution x must be unique.3.6 True or false: The product of a Householder transformation and a Givens rotation isalways an orthogonal matrix.3.7 True or false: If the n × n matrix Q is aHouseholder transformation, and x is an arbi-106trary n-vector, then the last k components ofthe vector Qx are zero for some k < n.3.8 True or false: Methods based on orthogonal factorization are generally more expensive computationally than methods based onthe normal equations for solving linear leastsquares problems.3.9 (a) In a data-fitting problem in whichm data points (ti , yi ) are fit by a model function f (t, x), where t is the independent variable and x is an n-vector of parameters to bedetermined, what does it mean for the functionf to be linear in the components of x?(b) Give an example of a model functionf (t, x) that is linear in this sense.(c) Give an example of a model functionf (t, x) that is nonlinear.3.10 In a linear least squares problem Ax ≈b, where A is an m×n matrix, if rank(A) < n,then which of the following situations are possible?(a) There is no solution.(b) There is a unique solution.(c) There is a solution, but it is not unique.3.11 In solving an overdetermined leastsquares problem Ax ≈ b, which would be amore serious difficulty: that the rows of A arelinearly dependent, or that the columns of Aare linearly dependent? Explain.3.12 In an overdetermined linear least squaresproblem with model function f (t, x) =x1 φ1 (t) + x2 φ2 (t) + x3 φ3 (t), what will be therank of the resulting least squares matrix A ifwe take φ1 (t) = 1, φ2 (t) = t, and φ3 (t) = 1−t?3.13 What is the system of normal equationsfor the linear least squares problem Ax ≈ b?3.14 List two ways in which use of the normalequations for solving linear least squares problems may suffer loss of numerical accuracy.3.15 Let A be an m × n matrix.
Under whatconditions on the matrix A will the matrixAT A be(a) Symmetric?(b) Nonsingular?(c) Positive definite?CHAPTER 3. LINEAR LEAST SQUARES3.16 Which of the following properties of anm×n matrix A, with m > n, indicate that theminimum residual solution of the least squaresproblem Ax ≈ b is not unique?(a) The columns of A are linearly dependent.(b) The rows of A are linearly dependent.(c) The matrix AT A is singular.3.17 (a) Can Gaussian elimination with pivoting be used to compute an LU factorizationof a rectangular m×n matrix A, where L is anm × k matrix whose entries above its main diagonal are all zero, U is a k × n matrix whoseentries below its main diagonal are all zero,and k = min{m, n}?(b) If this were possible, would it provide away to solve an overdetermined least squaresproblem Ax ≈ b, where m > n? Why?3.18 (a) What is meant by two vectors x andy being orthogonal to each other?(b) Prove that if two nonzero vectors are orthogonal to each other, then they must also belinearly independent.(c) Give an example of two nonzero vectors inthe plane that are orthogonal to each other.(d ) Give an example of two nonzero vectorsin the plane that are not orthogonal to eachother.(e) List two ways in which orthogonality is important in the context of linear least squaresproblems.3.19 In Euclidean n-space, is orthogonality atransitive relation? That is, if x is orthogonalto y, and y is orthogonal to z, is x necessarilyorthogonal to z?3.20 (a) Why are orthogonal transformations, such as Householder or Givens, oftenused to solve least squares problems?(b) Why are such methods not often used tosolve square linear systems?(c) Do orthogonal transformations have anyadvantage over Gaussian elimination for solving square linear systems? If so, state one.REVIEW QUESTIONS3.21 Which of the following matrices are orthogonal?0 1(a)1 010(b)0 −12 0(c)0 21√ √√2/2 √2/2(d )− 2/22/23.22 Which of the following properties doesan n × n orthogonal matrix necessarily have?(a) It is nonsingular.(b) It preserves the Euclidean vector normwhen multiplied times a vector.(c) Its transpose is its inverse.(d ) Its columns are orthonormal.(e) It is symmetric.(f ) It is diagonal.(g) Its Euclidean matrix norm is 1.(h) Its condition number in the Euclideannorm is 1.3.23 Which of the following types of matricesare necessarily orthogonal?(a) Permutation(b) Symmetric positive definite(c) Householder transformation(d ) Givens rotation(e) Nonsingular(f ) Diagonal3.24 Show that multiplication by an orthogonal matrix Q preserves the Euclidean norm ofa vector x.3.25 What condition must a nonzero n-vectorw satisfy to ensure that the matrix H =I − 2wwT is orthogonal?3.26 If Q is a 2 × 2 orthogonal matrix suchthat 1αQ=,10what must the value of α be?1073.27 How many scalar multiplications are required to multiply an arbitrary n-vector byan n × n Householder transformation matrixH = I − 2wwT , where w is an n-vector withkwk2 = 1?3.28 Given a vector a, in designing a Householder transformation H such that Ha =αe1 , we know that α = ±kak2 .
On what basisshould the sign be chosen?3.29 List one advantage and one disadvantageof Givens rotations for QR factorization compared with Householder transformations.3.30 When used to annihilate the secondcomponent of a 2-vector, does a Householdertransformation always give the same result asa Givens rotation?3.31 In addition to the input array containing the matrix A, which can be overwritten,how much additional auxiliary array storage isrequired to compute and store the following?(a) The LU factorization of A by Gaussianelimination with partial pivoting, where A isn×n(b) The QR factorization of A by Householdertransformations, where A is m × n3.32 In solving a linear least squares problemAx ≈ b, where A is an m × n matrix withm ≥ n and rank(A) < n, at what point willthe least squares solution process break down(assuming exact arithmetic)?(a) Using Cholesky factorization to solve thenormal equations(b) Using QR factorization by Householdertransformations3.33 Compared to the classical GramSchmidt procedure, which of the following areadvantages of modified Gram-Schmidt orthogonalization?(a) Requires less storage(b) Requires less work(c) Is more stable numerically3.34 For computing the QR factorization ofan m×n matrix, with m ≥ n, how large must nbe before there is a difference between the classical and modified Gram-Schmidt procedures?108CHAPTER 3.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
