Chapter 7
Least-Squares Approximation
Rendered from the uploaded full LaTeX source with KaTeX. No PDF, no PDF.js, no image extraction, and no raw LaTeX displayed.
After completing this chapter, the reader should be able to:
formulate overdetermined, underdetermined, full-rank, and rank-deficient least-squares problems;
prove the projection theorem and derive the normal equations;
explain why normal equations square the condition number;
solve least-squares problems using QR factorization and the SVD;
characterize all minimizers in the rank-deficient case;
compute the minimum-norm solution using the Moore–Penrose pseudoinverse;
understand residual geometry and a posteriori optimality conditions;
analyze perturbation and conditioning of least-squares solutions;
derive weighted, constrained, and regularized least-squares formulations;
explain Tikhonov regularization, truncated SVD, and filter factors;
connect linear least squares with nonlinear least squares, Gauss–Newton, Levenberg–Marquardt, LSQR, and randomized algorithms;
solve basic, advanced, and research-level least-squares exercises.
The Least-Squares Problem
Let A\in\mathbb R^{m\times n}, \qquad b\in\mathbb R^m. The least-squares problem is \min_{x\in\mathbb R^n}\|Ax-b\|_2. It is especially important when m>n, because the system Ax=b is usually overdetermined and may have no exact solution.
Least squares replaces an inconsistent system by the closest consistent one in the range of A. Geometrically, Ax_\ast is the orthogonal projection of b onto \mathcal R(A), the column space of A.
The residual associated with a candidate x is r=b-Ax. A least-squares minimizer x_\ast satisfies \|r_\ast\|_2 = \min_x\|b-Ax\|_2.
Projection Geometry
The range or column space of A is \mathcal R(A)=\{Ax:x\in\mathbb R^n\}. The least-squares problem asks for the point in \mathcal R(A) closest to b.
Let S be a subspace of \mathbb R^m. For every b\in\mathbb R^m, there exists a unique vector p\in S such that \|b-p\|_2=\min_{y\in S}\|b-y\|_2. Moreover, b-p\perp S.
Choose an orthonormal basis q_1,\ldots,q_k of S. Define p=\sum_{j=1}^k(q_j^Tb)q_j. Then for any y\in S, write y=\sum_{j=1}^k\alpha_jq_j. Since b-p\perp S, we have b-y=(b-p)+(p-y), with b-p\perp p-y. Therefore, by the Pythagorean theorem, \|b-y\|_2^2 = \|b-p\|_2^2+\|p-y\|_2^2 \ge \|b-p\|_2^2. Thus p is a minimizer. If p_1,p_2\in S are both minimizers, then the strict convexity of the Euclidean norm squared on the affine line segment between them forces p_1=p_2. Equivalently, both residuals are orthogonal to S, so p_1-p_2\in S is orthogonal to itself, hence zero.
□
Normal Equations
The objective function is \phi(x)=\frac12\|Ax-b\|_2^2. Expanding, \phi(x) = \frac12(Ax-b)^T(Ax-b) = \frac12x^TA^TAx-x^TA^Tb+\frac12b^Tb.
A vector x_\ast is a least-squares minimizer if and only if A^T(Ax_\ast-b)=0. Equivalently, A^TAx_\ast=A^Tb.
The function \phi(x)=\frac12\|Ax-b\|_2^2 is convex and differentiable. Its gradient is \nabla\phi(x)=A^T(Ax-b). A point x_\ast minimizes \phi if and only if \nabla\phi(x_\ast)=0. Therefore A^T(Ax_\ast-b)=0, which is equivalent to A^TAx_\ast=A^Tb.
□
If x_\ast solves the least-squares problem, then r_\ast=b-Ax_\ast satisfies A^Tr_\ast=0. Thus r_\ast\perp \mathcal R(A).
The normal equations give A^T(Ax_\ast-b)=0. Since r_\ast=b-Ax_\ast, this becomes A^Tr_\ast=0. The columns of A span \mathcal R(A), so A^Tr_\ast=0 means r_\ast is orthogonal to every column of A, hence to \mathcal R(A).
□
Existence and Uniqueness
Least-squares minimizers always exist, but they need not be unique.
For every A\in\mathbb R^{m\times n} and b\in\mathbb R^m, the problem \min_x\|Ax-b\|_2 has at least one minimizer.
The set \mathcal R(A) is a finite-dimensional subspace of \mathbb R^m, hence closed. By the projection theorem, there exists a unique point p\in\mathcal R(A) closest to b. Since p\in\mathcal R(A), there exists x_\ast such that Ax_\ast=p. Thus x_\ast is a least-squares minimizer.
□
The least-squares minimizer is unique if and only if A has full column rank: \operatorname{rank}(A)=n.
If A has full column rank, then A^TA is symmetric positive definite: x^TA^TAx=\|Ax\|_2^2>0 \qquad \text{for }x\ne0. Thus the normal equations have the unique solution x_\ast=(A^TA)^{-1}A^Tb.
Conversely, if A does not have full column rank, then there exists a nonzero vector z such that Az=0. If x_\ast is a minimizer, then for every scalar \alpha, A(x_\ast+\alpha z)=Ax_\ast. Thus all vectors x_\ast+\alpha z are minimizers, so uniqueness fails.
□
Conditioning of Least Squares
The normal equations involve A^TA. This is mathematically valid but can be numerically dangerous.
If A has full column rank, then \kappa_2(A^TA)=\kappa_2(A)^2.
Let the singular values of A be \sigma_1\ge\sigma_2\ge\cdots\ge\sigma_n>0. The eigenvalues of A^TA are \sigma_1^2,\ldots,\sigma_n^2. Therefore \kappa_2(A^TA) = \frac{\sigma_1^2}{\sigma_n^2} = \left(\frac{\sigma_1}{\sigma_n}\right)^2 = \kappa_2(A)^2.
□
The normal equations are attractive because they reduce least squares to a symmetric positive definite system. But they square the condition number. If A is ill-conditioned, this may destroy significant digits.
Solving Least Squares by QR Factorization
Assume A\in\mathbb R^{m\times n}, m\ge n, and A has full column rank. Let A=QR, where Q\in\mathbb R^{m\times n}, \qquad Q^TQ=I, and R\in\mathbb R^{n\times n} is upper triangular and nonsingular. Then \|Ax-b\|_2 = \|QRx-b\|_2. Complete Q to an orthogonal matrix \widehat Q=[Q\ Q_\perp]. Since orthogonal transformations preserve the Euclidean norm, \|QRx-b\|_2 = \left\| \widehat Q^T(QRx-b) \right\|_2 = \left\| \begin{pmatrix} Rx-Q^Tb\\ -Q_\perp^Tb \end{pmatrix} \right\|_2. Thus the minimizer satisfies Rx=Q^Tb.
Let A=QR be a thin QR factorization with A full column rank. Then the unique least-squares solution is obtained from Rx=Q^Tb.
Using the orthogonal decomposition above, \|Ax-b\|_2^2 = \|Rx-Q^Tb\|_2^2+\|Q_\perp^Tb\|_2^2. The second term is independent of x. Therefore the minimum is attained exactly when Rx-Q^Tb=0. Since R is nonsingular, this determines a unique x.
□
Caption.
Least squares by Householder QR
A\in\mathbb R^{m\times n}, m\ge n, b\in\mathbb R^m
Compute Householder QR factorization A=QR
Compute c=Q^Tb using the stored Householder reflectors
Solve Rx=c_1, where c_1 contains the first n components of c
Return x
Normal equations use A^TA, whose condition number is \kappa_2(A)^2. QR factorization works directly with A and is the standard stable method for full-rank dense least-squares problems.
Rank-Deficient Least Squares and the SVD
Let the singular value decomposition of A be A=U\Sigma V^T, where \Sigma= \operatorname{diag}(\sigma_1,\ldots,\sigma_r,0,\ldots,0), \qquad \sigma_1\ge\cdots\ge\sigma_r>0. The Moore–Penrose pseudoinverse is A^\dagger=V\Sigma^\dagger U^T, where \Sigma^\dagger= \operatorname{diag} \left( \frac1{\sigma_1},\ldots,\frac1{\sigma_r},0,\ldots,0 \right).
The vector x^\dagger=A^\dagger b is a least-squares minimizer. Among all least-squares minimizers, it has minimum Euclidean norm.
Let A=U\Sigma V^T. Since U and V are orthogonal, \|Ax-b\|_2 = \|\Sigma y-U^Tb\|_2, \qquad y=V^Tx. Let c=U^Tb. The minimization separates into scalar problems: \min_y \sum_{i=1}^r(\sigma_i y_i-c_i)^2 + \sum_{i=r+1}^m c_i^2. The minimum is attained when y_i=\frac{c_i}{\sigma_i}, \qquad i=1,\ldots,r. For i>r, the variables do not affect the residual. The minimum-norm choice is y_i=0, \qquad i>r. Thus x=Vy=A^\dagger b.
□
Caption.
Least squares by SVD
A, b, numerical rank tolerance \tau
Compute A=U\Sigma V^T
Set c=U^Tb
For each singular value \sigma_i:
If \sigma_i>\tau\sigma_1:
y_i\gets c_i/\sigma_i
Else:
y_i\gets0
x\gets Vy
Return x
Residual Norm and Orthogonal Projectors
The orthogonal projector onto \mathcal R(A) is P_A=AA^\dagger. Thus Ax^\dagger=P_Ab and r_\ast=b-P_Ab=(I-P_A)b.
Let A=U\Sigma V^T have rank r, and let c=U^Tb. Then \min_x\|Ax-b\|_2^2 = \sum_{i=r+1}^{m}c_i^2.
As in the proof of the referenced result, \|Ax-b\|_2^2 = \sum_{i=1}^r(\sigma_i y_i-c_i)^2 + \sum_{i=r+1}^{m}c_i^2. The first sum can be made zero by choosing y_i=c_i/\sigma_i. The second sum is independent of x. Therefore the minimum residual norm squared is \sum_{i=r+1}^{m}c_i^2.
□
Perturbation and Conditioning
Least-squares problems can be sensitive when A is ill-conditioned or nearly rank deficient. In the full column rank case, the solution is x=(A^TA)^{-1}A^Tb. Perturbations in b satisfy \Delta x=A^\dagger \Delta b. Therefore \|\Delta x\|_2\le \|A^\dagger\|_2\|\Delta b\|_2 = \frac{\|\Delta b\|_2}{\sigma_{\min}(A)}.
Assume A has full column rank and only b is perturbed. Then \Delta x=A^\dagger\Delta b, and \|\Delta x\|_2 \le \frac{1}{\sigma_{\min}(A)} \|\Delta b\|_2.
The least-squares solution is x=A^\dagger b. For b+\Delta b, the solution is x+\Delta x=A^\dagger(b+\Delta b). Subtracting gives \Delta x=A^\dagger\Delta b. Taking norms, \|\Delta x\|_2 \le \|A^\dagger\|_2\|\Delta b\|_2 = \frac{1}{\sigma_{\min}(A)}\|\Delta b\|_2.
□
Weighted Least Squares
In weighted least squares, residual components have different importance: \min_x\|W^{1/2}(Ax-b)\|_2, where W=W^T>0. The normal equations become A^TW(Ax-b)=0, or A^TWAx=A^TWb.
If W=W^T>0, then x_\ast minimizes \|W^{1/2}(Ax-b)\|_2 if and only if A^TWAx_\ast=A^TWb.
Define \phi(x)=\frac12(Ax-b)^TW(Ax-b). Then \nabla\phi(x)=A^TW(Ax-b). Setting the gradient equal to zero gives A^TWAx=A^TWb. Since W is positive definite, \phi is convex, so the first-order condition is sufficient.
□
Constrained Least Squares
A linearly constrained least-squares problem has the form \min_x\|Ax-b\|_2 \qquad \text{subject to} \qquad Cx=d. Using Lagrange multipliers, one obtains the saddle-point system \begin{pmatrix} A^TA & C^T\\ C & 0 \end{pmatrix} \begin{pmatrix} x\\ \lambda \end{pmatrix} = \begin{pmatrix} A^Tb\\ d \end{pmatrix}.
A constrained minimizer satisfies A^T(Ax-b)+C^T\lambda=0, \qquad Cx=d.
Consider the Lagrangian \mathcal L(x,\lambda) = \frac12\|Ax-b\|_2^2+\lambda^T(Cx-d). Stationarity with respect to x gives A^T(Ax-b)+C^T\lambda=0. Stationarity with respect to \lambda gives the constraint Cx=d.
□
Tikhonov Regularization
Ill-posed or ill-conditioned least-squares problems require stabilization. Tikhonov regularization solves \min_x \left( \|Ax-b\|_2^2+\lambda\|x\|_2^2 \right), \qquad \lambda>0. The normal equations are (A^TA+\lambda I)x_\lambda=A^Tb.
The unique minimizer of \|Ax-b\|_2^2+\lambda\|x\|_2^2, \qquad \lambda>0, satisfies (A^TA+\lambda I)x_\lambda=A^Tb.
Define \phi_\lambda(x)=\|Ax-b\|_2^2+\lambda\|x\|_2^2. Then \nabla\phi_\lambda(x) = 2A^T(Ax-b)+2\lambda x. Setting the gradient to zero gives (A^TA+\lambda I)x=A^Tb. Since A^TA+\lambda I is symmetric positive definite for \lambda>0, the minimizer is unique.
□
Caption.
Tikhonov regularized least squares
A, b, regularization parameter \lambda>0
Form or apply A^TA+\lambda I
Solve (A^TA+\lambda I)x_\lambda=A^Tb
Return x_\lambda
Filter Factors and Truncated SVD
Using the SVD, A=U\Sigma V^T, the Tikhonov solution is x_\lambda = \sum_{i=1}^r \frac{\sigma_i}{\sigma_i^2+\lambda} (u_i^Tb)v_i. The factors f_i(\lambda)=\frac{\sigma_i^2}{\sigma_i^2+\lambda} are called filter factors.
Truncated SVD keeps only singular values above a threshold: x_k = \sum_{i=1}^k \frac{u_i^Tb}{\sigma_i}v_i.
Choosing the Regularization Parameter
The parameter \lambda balances data fit and solution size: \|Ax_\lambda-b\|_2 \qquad \text{versus} \qquad \|x_\lambda\|_2. Common selection principles include: \text{discrepancy principle}, \qquad \text{L-curve}, \qquad \text{generalized cross-validation}.
Polynomial Least Squares
Given data (t_i,y_i), \qquad i=1,\ldots,m, polynomial least squares fits p(t)=c_0+c_1t+\cdots+c_nt^n by minimizing \sum_{i=1}^m |p(t_i)-y_i|^2. This leads to a Vandermonde-type matrix A_{ij}=t_i^{j-1}. The monomial basis can be ill-conditioned for high degree. Orthogonal polynomial bases or QR factorization improve stability.
Statistical Interpretation
If b=Ax_{\mathrm{true}}+\varepsilon, where \varepsilon is Gaussian noise with mean zero and covariance \sigma^2I, then the least-squares estimator is the maximum likelihood estimator. Its covariance in the full column rank case is \operatorname{Cov}(x_\ast)=\sigma^2(A^TA)^{-1}.
Nonlinear Least Squares
A nonlinear least-squares problem has the form \min_x \frac12\|F(x)\|_2^2, where F:\mathbb R^n\to\mathbb R^m. The Jacobian is J(x)=DF(x). Gauss–Newton linearizes F(x+s)\approx F(x)+J(x)s and solves \min_s\|J(x)s+F(x)\|_2.
Caption.
Gauss–Newton method
initial point x_0
For k=0,1,2,\ldots:
Evaluate F_k=F(x_k) and J_k=J(x_k)
Solve \min_s\|J_ks+F_k\|_2
x_{k+1}\gets x_k+s_k
If \|s_k\| and \|F_k\| are small enough:
Return x_{k+1}
Levenberg–Marquardt stabilizes Gauss–Newton by solving (J^TJ+\lambda I)s=-J^TF.
Large-Scale Least Squares: CGLS and LSQR
For large sparse problems, one avoids forming A^TA. CGLS applies conjugate gradients formally to A^TAx=A^Tb, but uses only products with A and A^T. LSQR is based on Golub–Kahan bidiagonalization and is numerically preferable to explicitly forming normal equations.
Caption.
Conceptual CGLS iteration
A, b, initial x_0
r_0\gets b-Ax_0
s_0\gets A^Tr_0
p_0\gets s_0
For k=0,1,2,\ldots:
q_k\gets Ap_k
\alpha_k\gets (s_k^Ts_k)/(q_k^Tq_k)
x_{k+1}\gets x_k+\alpha_kp_k
r_{k+1}\gets r_k-\alpha_kq_k
s_{k+1}\gets A^Tr_{k+1}
\beta_k\gets (s_{k+1}^Ts_{k+1})/(s_k^Ts_k)
p_{k+1}\gets s_{k+1}+\beta_kp_k
Randomized Least Squares
Randomized algorithms reduce the size of a large least-squares problem by sketching: \min_x\|SAx-Sb\|_2, where S\in\mathbb R^{s\times m}, \qquad s\ll m. If S is a subspace embedding for \mathcal R(A), then the sketched problem approximates the original least-squares problem.
Practical Comparison of Least-Squares Methods
- Normal equations.
-
Simple and fast for well-conditioned problems, but they square the condition number.
- Householder QR.
-
The standard stable method for dense full-rank least-squares problems.
- Modified Gram–Schmidt.
-
Useful pedagogically and in some iterative contexts, but less stable than Householder QR for difficult dense problems.
- SVD.
-
Most reliable for rank-deficient or nearly rank-deficient problems. More expensive than QR but gives rank, conditioning, and minimum-norm solutions.
- Tikhonov regularization.
-
Stabilizes ill-conditioned problems by damping small singular-value components.
- Truncated SVD.
-
A spectral regularization method that removes components associated with small singular values.
- Weighted least squares.
-
Appropriate when residual components have different variances or importance.
- Constrained least squares.
-
Used when the solution must satisfy exact linear side constraints.
- Gauss–Newton.
-
Natural method for nonlinear least squares when residuals are moderately small and the Jacobian has good rank.
- Levenberg–Marquardt.
-
More robust nonlinear least-squares method, blending Gauss–Newton and regularization.
- LSQR/CGLS.
-
Preferred for very large sparse least-squares problems when only products with A and A^T are feasible.
- Randomized least squares.
-
Effective for massive overdetermined problems when sketching preserves the geometry of the column space.
Exercises
The following exercise bank is intentionally large. Basic problems test definitions, computations, and essential facts. Starred exercises require proofs, careful derivations, stability analysis, or advanced approximation theory. Problems marked \star, \star\star, and \star\star\star are progressively harder.
Basic problems
State the least-squares problem for A\in\mathbb R^{m\times n} and b\in\mathbb R^m.
Define the least-squares residual and explain its geometric meaning.
Derive the normal equations by differentiating \|Ax-b\|_2^2.
Show that the least-squares residual is orthogonal to every column of A.
Explain why full column rank of A guarantees uniqueness of the least-squares solution.
Solve \min_x \left\| \begin{pmatrix} 1\\ 1\\ 1 \end{pmatrix}x - \begin{pmatrix} 1\\ 2\\ 4 \end{pmatrix} \right\|_2.
Write the least-squares system for fitting a line y=c_0+c_1t to data (t_i,y_i), i=1,\ldots,m.
If A=QR is a thin QR factorization, state the triangular system that gives the least-squares solution.
If \kappa_2(A)=10^5, compute \kappa_2(A^TA).
State the SVD formula for the minimum-norm least-squares solution.
Compute the Moore–Penrose pseudoinverse of \operatorname{diag}(4,2,0).
Explain why rank deficiency can lead to infinitely many least-squares minimizers.
Derive the normal equations for \min_x\left(\|Ax-b\|_2^2+\lambda\|x\|_2^2\right).
State the weighted least-squares problem and its normal equations.
Write the KKT equations for least squares subject to Cx=d.
Construct the matrix for least-squares fitting a quadratic polynomial to data (t_i,y_i).
State a nonlinear least-squares problem and define its Jacobian.
Derive the linear least-squares subproblem solved in one Gauss–Newton step.
Why are products with both A and A^T needed in LSQR-type methods?
What is the idea of sketching in randomized least squares?
Intermediate problems \star
Prove the referenced result.
Prove the referenced result.
Prove the referenced result.
Prove the referenced result.
Prove the referenced result.
Prove the referenced result.
Prove the referenced result.
Prove the referenced result.
Prove the referenced result.
Prove the referenced result.
Prove the referenced result.
Prove the referenced result.
Prove the referenced result.
Derive x_\lambda = \sum_{i=1}^r \frac{\sigma_i}{\sigma_i^2+\lambda}(u_i^Tb)v_i.
Derive the Tikhonov filter factors and explain their behavior as \sigma_i\to0.
Derive the truncated SVD solution and compare it with Tikhonov regularization.
Derive the least-squares system for polynomial fitting in a monomial basis.
Explain why an orthogonal polynomial basis improves least-squares fitting.
Derive the Gauss–Newton normal equations J^TJs=-J^TF.
Derive the Levenberg–Marquardt step (J^TJ+\lambda I)s=-J^TF.
Advanced problems \star\star
Develop a first-order perturbation theory for the least-squares solution under perturbations in both A and b.
Derive a relative condition-number estimate for the full-rank least-squares problem and identify the role of the residual norm.
Explain why Householder QR gives a backward stable least-squares solver.
Analyze modified Gram–Schmidt for least squares and compare it with Householder QR.
Show that solving normal equations by Cholesky can be backward stable for the normal equations but still forward inaccurate for the original least-squares problem.
Explain rank-revealing QR and compare it with the SVD for numerical rank detection.
Study the complete orthogonal decomposition for rank-deficient least squares.
Prove the four Moore–Penrose pseudoinverse identities.
Show that A^\dagger b is orthogonal to the null space of A.
Derive the total least-squares problem and show how it is related to the SVD of [A\ b].
Analyze the bias-variance tradeoff in Tikhonov regularization using the SVD.
Derive Morozov’s discrepancy principle for choosing the regularization parameter.
Derive the generalized cross-validation function for Tikhonov regularization.
Derive a formula for the curvature of the L-curve and explain how it identifies a regularization parameter.
Analyze \min_x\left(\|Ax-b\|_2^2+\lambda\|Lx\|_2^2\right) for a general regularization matrix L.
Show that weighted least squares is maximum likelihood when the noise covariance is known and nonspherical.
Solve equality-constrained least squares by parametrizing the constraint Cx=d.
Derive a QR-based method for equality-constrained least squares.
Analyze CGLS as CG applied to A^TAx=A^Tb, without forming A^TA.
Derive the Golub–Kahan bidiagonalization relation underlying LSQR.
State local convergence conditions for Gauss–Newton.
Compare least squares with robust regression based on L^1, Huber, or Tukey loss functions.
Derive recursive least squares using the Sherman–Morrison formula.
Explain how QR factorization can be updated when a new row is added to A.
Discuss the numerical difficulties of QR downdating.
Research-level problems \star\star\star
Study strong rank-revealing QR and compare its theoretical guarantees with those of the SVD.
Prove a subspace-embedding theorem sufficient for randomized least-squares accuracy.
Study randomized preconditioned least-squares solvers such as Blendenpik.
Define statistical leverage scores and explain their role in randomized row sampling.
Analyze early stopping of CGLS as a form of regularization.
Study hybrid LSQR methods that combine Krylov projection and Tikhonov regularization.
Use the generalized SVD to solve general-form Tikhonov regularization.
Interpret Tikhonov regularization as a Bayesian MAP estimator.
Study discrete Picard conditions and their role in ill-posed least-squares problems.
Analyze sensitivity of the total least-squares solution.
Study least-squares problems with Toeplitz, Hankel, or Vandermonde structure.
Compare QR, normal equations, and iterative methods for large sparse least-squares problems.
Study the LASSO problem \min_x\frac12\|Ax-b\|_2^2+\lambda\|x\|_1. Compare it with Tikhonov regularization.
Explain how least squares, sparsity, and restricted isometry interact in compressed sensing.
Design a distributed least-squares algorithm and analyze communication costs.
Analyze mixed-precision QR or LSQR methods with iterative refinement.
Develop an interval-arithmetic certificate for a least-squares solution and residual.
Formulate a nonlinear inverse problem as regularized nonlinear least squares and derive a Gauss–Newton–Tikhonov method.
Study least-squares parameter estimation constrained by a PDE model.
Discuss reproducibility and deterministic reductions in large-scale least-squares computations.
Exercise solutions
The solutions below are converted from the uploaded LaTeX solution file. Open an accordion to view the full solution.
This chapter gives detailed worked solutions for the exercises in Chapter 7. Each solution includes the problem formulation, the method, the mathematical derivation, the conclusion, and a diagnostic comment.
Exercise 7.1
Problem formulation.
State the least-squares problem for A\in\mathbb R^{m\times n} and b\in\mathbb R^m.
Method.
Use orthogonal projection, normal equations, QR/SVD least squares, regularization formulas, and residual orthogonality.
Detailed solution and justification.
The least-squares solution is characterized by residual orthogonality: r=b-Ax,\qquad A^Tr=0. Equivalently, A^TAx=A^Tb. For numerical stability, QR or SVD is preferred over explicitly forming A^TA because \kappa(A^TA)=\kappa(A)^2. Regularization replaces the problem by \min_x \|Ax-b\|_2^2+\lambda\|x\|_2^2, giving (A^TA+\lambda I)x=A^Tb.
Conclusion.
The displayed derivation gives the requested formula, proof, or computation. The final expression should be checked against the assumptions and notation of the corresponding chapter.
Diagnostic comment.
The formula should be verified by substitution into the defining equation and, when possible, by a small numerical test.
Exercise 7.2
Problem formulation.
Define the least-squares residual and explain its geometric meaning.
Method.
Use orthogonal projection, normal equations, QR/SVD least squares, regularization formulas, and residual orthogonality.
Detailed solution and justification.
The least-squares solution is characterized by residual orthogonality: r=b-Ax,\qquad A^Tr=0. Equivalently, A^TAx=A^Tb. For numerical stability, QR or SVD is preferred over explicitly forming A^TA because \kappa(A^TA)=\kappa(A)^2. Regularization replaces the problem by \min_x \|Ax-b\|_2^2+\lambda\|x\|_2^2, giving (A^TA+\lambda I)x=A^Tb.
Conclusion.
The displayed derivation gives the requested formula, proof, or computation. The final expression should be checked against the assumptions and notation of the corresponding chapter.
Diagnostic comment.
The formula should be verified by substitution into the defining equation and, when possible, by a small numerical test.
Exercise 7.3
Problem formulation.
Derive the normal equations by differentiating \|Ax-b\|_2^2.
Method.
Use orthogonal projection, normal equations, QR/SVD least squares, regularization formulas, and residual orthogonality.
Detailed solution and justification.
Minimize \phi(x)=\frac12\|Ax-b\|_2^2. Then \phi(x)=\frac12(Ax-b)^T(Ax-b). Differentiating, \nabla\phi(x)=A^T(Ax-b). At a minimizer, A^T(Ax-b)=0. Therefore A^TAx=A^Tb. These are the normal equations. They express the orthogonality condition b-Ax\perp \operatorname{range}(A).
Conclusion.
The displayed derivation gives the requested formula, proof, or computation. The final expression should be checked against the assumptions and notation of the corresponding chapter.
Diagnostic comment.
The formula should be verified by substitution into the defining equation and, when possible, by a small numerical test.
Exercise 7.4
Problem formulation.
Show that the least-squares residual is orthogonal to every column of A.
Method.
Use orthogonal projection, normal equations, QR/SVD least squares, regularization formulas, and residual orthogonality.
Detailed solution and justification.
The least-squares solution is characterized by residual orthogonality: r=b-Ax,\qquad A^Tr=0. Equivalently, A^TAx=A^Tb. For numerical stability, QR or SVD is preferred over explicitly forming A^TA because \kappa(A^TA)=\kappa(A)^2. Regularization replaces the problem by \min_x \|Ax-b\|_2^2+\lambda\|x\|_2^2, giving (A^TA+\lambda I)x=A^Tb.
Conclusion.
The displayed derivation gives the requested formula, proof, or computation. The final expression should be checked against the assumptions and notation of the corresponding chapter.
Diagnostic comment.
The formula should be verified by substitution into the defining equation and, when possible, by a small numerical test.
Exercise 7.5
Problem formulation.
Explain why full column rank of A guarantees uniqueness of the least-squares solution.
Method.
Use orthogonal projection, normal equations, QR/SVD least squares, regularization formulas, and residual orthogonality.
Detailed solution and justification.
The least-squares solution is characterized by residual orthogonality: r=b-Ax,\qquad A^Tr=0. Equivalently, A^TAx=A^Tb. For numerical stability, QR or SVD is preferred over explicitly forming A^TA because \kappa(A^TA)=\kappa(A)^2. Regularization replaces the problem by \min_x \|Ax-b\|_2^2+\lambda\|x\|_2^2, giving (A^TA+\lambda I)x=A^Tb.
Conclusion.
The displayed derivation gives the requested formula, proof, or computation. The final expression should be checked against the assumptions and notation of the corresponding chapter.
Diagnostic comment.
The formula should be verified by substitution into the defining equation and, when possible, by a small numerical test.
Exercise 7.6
Problem formulation.
Solve \min_x \left\| \begin{pmatrix} 1\\ 1\\ 1 \end{pmatrix}x - \begin{pmatrix} 1\\ 2\\ 4 \end{pmatrix} \right\|_2.
Method.
Use orthogonal projection, normal equations, QR/SVD least squares, regularization formulas, and residual orthogonality.
Detailed solution and justification.
The least-squares solution is characterized by residual orthogonality: r=b-Ax,\qquad A^Tr=0. Equivalently, A^TAx=A^Tb. For numerical stability, QR or SVD is preferred over explicitly forming A^TA because \kappa(A^TA)=\kappa(A)^2. Regularization replaces the problem by \min_x \|Ax-b\|_2^2+\lambda\|x\|_2^2, giving (A^TA+\lambda I)x=A^Tb.
Conclusion.
The displayed derivation gives the requested formula, proof, or computation. The final expression should be checked against the assumptions and notation of the corresponding chapter.
Diagnostic comment.
The formula should be verified by substitution into the defining equation and, when possible, by a small numerical test.
Exercise 7.7
Problem formulation.
Write the least-squares system for fitting a line y=c_0+c_1t to data (t_i,y_i), i=1,\ldots,m.
Method.
Use orthogonal projection, normal equations, QR/SVD least squares, regularization formulas, and residual orthogonality.
Detailed solution and justification.
The least-squares solution is characterized by residual orthogonality: r=b-Ax,\qquad A^Tr=0. Equivalently, A^TAx=A^Tb. For numerical stability, QR or SVD is preferred over explicitly forming A^TA because \kappa(A^TA)=\kappa(A)^2. Regularization replaces the problem by \min_x \|Ax-b\|_2^2+\lambda\|x\|_2^2, giving (A^TA+\lambda I)x=A^Tb.
Conclusion.
The displayed derivation gives the requested formula, proof, or computation. The final expression should be checked against the assumptions and notation of the corresponding chapter.
Diagnostic comment.
The formula should be verified by substitution into the defining equation and, when possible, by a small numerical test.
Exercise 7.8
Problem formulation.
If A=QR is a thin QR factorization, state the triangular system that gives the least-squares solution.
Method.
Use orthogonal projection, normal equations, QR/SVD least squares, regularization formulas, and residual orthogonality.
Detailed solution and justification.
Let A=QR, where Q has orthonormal columns. Then \|Ax-b\|_2=\|QRx-b\|_2. Decompose b=QQ^Tb+(I-QQ^T)b. Since the two parts are orthogonal, \|QRx-b\|_2^2 = \|Rx-Q^Tb\|_2^2+\|(I-QQ^T)b\|_2^2. The second term is independent of x. Hence the least-squares minimizer satisfies Rx=Q^Tb.
Conclusion.
The displayed derivation gives the requested formula, proof, or computation. The final expression should be checked against the assumptions and notation of the corresponding chapter.
Diagnostic comment.
The formula should be verified by substitution into the defining equation and, when possible, by a small numerical test.
Exercise 7.9
Problem formulation.
If \kappa_2(A)=10^5, compute \kappa_2(A^TA).
Method.
Use orthogonal projection, normal equations, QR/SVD least squares, regularization formulas, and residual orthogonality.
Detailed solution and justification.
Minimize \phi(x)=\frac12\|Ax-b\|_2^2. Then \phi(x)=\frac12(Ax-b)^T(Ax-b). Differentiating, \nabla\phi(x)=A^T(Ax-b). At a minimizer, A^T(Ax-b)=0. Therefore A^TAx=A^Tb. These are the normal equations. They express the orthogonality condition b-Ax\perp \operatorname{range}(A).
Conclusion.
The displayed derivation gives the requested formula, proof, or computation. The final expression should be checked against the assumptions and notation of the corresponding chapter.
Diagnostic comment.
Distinguish forward error from backward error; a small residual does not imply a small forward error when the problem is ill-conditioned.
Exercise 7.10
Problem formulation.
State the SVD formula for the minimum-norm least-squares solution.
Method.
Use orthogonal projection, normal equations, QR/SVD least squares, regularization formulas, and residual orthogonality.
Detailed solution and justification.
Let A=U\Sigma V^T. The least-squares problem becomes \min_x\|\Sigma V^Tx-U^Tb\|_2. Set z=V^Tx. Then solve \min_z\|\Sigma z-U^Tb\|_2. The minimum-norm solution is z_i= \begin{cases} (u_i^Tb)/\sigma_i, & \sigma_i>0,\\ 0, & \sigma_i=0. \end{cases} Therefore x=A^\dagger b=V\Sigma^\dagger U^Tb.
Conclusion.
The displayed derivation gives the requested formula, proof, or computation. The final expression should be checked against the assumptions and notation of the corresponding chapter.
Diagnostic comment.
The formula should be verified by substitution into the defining equation and, when possible, by a small numerical test.
Exercise 7.11
Problem formulation.
Compute the Moore–Penrose pseudoinverse of \operatorname{diag}(4,2,0).
Method.
Use orthogonal projection, normal equations, QR/SVD least squares, regularization formulas, and residual orthogonality.
Detailed solution and justification.
The least-squares solution is characterized by residual orthogonality: r=b-Ax,\qquad A^Tr=0. Equivalently, A^TAx=A^Tb. For numerical stability, QR or SVD is preferred over explicitly forming A^TA because \kappa(A^TA)=\kappa(A)^2. Regularization replaces the problem by \min_x \|Ax-b\|_2^2+\lambda\|x\|_2^2, giving (A^TA+\lambda I)x=A^Tb.
Conclusion.
The displayed derivation gives the requested formula, proof, or computation. The final expression should be checked against the assumptions and notation of the corresponding chapter.
Diagnostic comment.
The formula should be verified by substitution into the defining equation and, when possible, by a small numerical test.
Exercise 7.12
Problem formulation.
Explain why rank deficiency can lead to infinitely many least-squares minimizers.
Method.
Use orthogonal projection, normal equations, QR/SVD least squares, regularization formulas, and residual orthogonality.
Detailed solution and justification.
The least-squares solution is characterized by residual orthogonality: r=b-Ax,\qquad A^Tr=0. Equivalently, A^TAx=A^Tb. For numerical stability, QR or SVD is preferred over explicitly forming A^TA because \kappa(A^TA)=\kappa(A)^2. Regularization replaces the problem by \min_x \|Ax-b\|_2^2+\lambda\|x\|_2^2, giving (A^TA+\lambda I)x=A^Tb.
Conclusion.
The displayed derivation gives the requested formula, proof, or computation. The final expression should be checked against the assumptions and notation of the corresponding chapter.
Diagnostic comment.
The formula should be verified by substitution into the defining equation and, when possible, by a small numerical test.
Exercise 7.13
Problem formulation.
Derive the normal equations for \min_x\left(\|Ax-b\|_2^2+\lambda\|x\|_2^2\right).
Method.
Use orthogonal projection, normal equations, QR/SVD least squares, regularization formulas, and residual orthogonality.
Detailed solution and justification.
Minimize \phi(x)=\frac12\|Ax-b\|_2^2. Then \phi(x)=\frac12(Ax-b)^T(Ax-b). Differentiating, \nabla\phi(x)=A^T(Ax-b). At a minimizer, A^T(Ax-b)=0. Therefore A^TAx=A^Tb. These are the normal equations. They express the orthogonality condition b-Ax\perp \operatorname{range}(A).
Conclusion.
The displayed derivation gives the requested formula, proof, or computation. The final expression should be checked against the assumptions and notation of the corresponding chapter.
Diagnostic comment.
The formula should be verified by substitution into the defining equation and, when possible, by a small numerical test.
Exercise 7.14
Problem formulation.
State the weighted least-squares problem and its normal equations.
Method.
Use orthogonal projection, normal equations, QR/SVD least squares, regularization formulas, and residual orthogonality.
Detailed solution and justification.
Minimize \phi(x)=\frac12\|Ax-b\|_2^2. Then \phi(x)=\frac12(Ax-b)^T(Ax-b). Differentiating, \nabla\phi(x)=A^T(Ax-b). At a minimizer, A^T(Ax-b)=0. Therefore A^TAx=A^Tb. These are the normal equations. They express the orthogonality condition b-Ax\perp \operatorname{range}(A).
Conclusion.
The displayed derivation gives the requested formula, proof, or computation. The final expression should be checked against the assumptions and notation of the corresponding chapter.
Diagnostic comment.
The formula should be verified by substitution into the defining equation and, when possible, by a small numerical test.
Exercise 7.15
Problem formulation.
Write the KKT equations for least squares subject to Cx=d.
Method.
Use orthogonal projection, normal equations, QR/SVD least squares, regularization formulas, and residual orthogonality.
Detailed solution and justification.
The least-squares solution is characterized by residual orthogonality: r=b-Ax,\qquad A^Tr=0. Equivalently, A^TAx=A^Tb. For numerical stability, QR or SVD is preferred over explicitly forming A^TA because \kappa(A^TA)=\kappa(A)^2. Regularization replaces the problem by \min_x \|Ax-b\|_2^2+\lambda\|x\|_2^2, giving (A^TA+\lambda I)x=A^Tb.
Conclusion.
The displayed derivation gives the requested formula, proof, or computation. The final expression should be checked against the assumptions and notation of the corresponding chapter.
Diagnostic comment.
Verify the stationarity residual, feasibility residual, and descent or curvature condition, not only the final numerical value.
Exercise 7.16
Problem formulation.
Construct the matrix for least-squares fitting a quadratic polynomial to data (t_i,y_i).
Method.
Use orthogonal projection, normal equations, QR/SVD least squares, regularization formulas, and residual orthogonality.
Detailed solution and justification.
The least-squares solution is characterized by residual orthogonality: r=b-Ax,\qquad A^Tr=0. Equivalently, A^TAx=A^Tb. For numerical stability, QR or SVD is preferred over explicitly forming A^TA because \kappa(A^TA)=\kappa(A)^2. Regularization replaces the problem by \min_x \|Ax-b\|_2^2+\lambda\|x\|_2^2, giving (A^TA+\lambda I)x=A^Tb.
Conclusion.
The displayed derivation gives the requested formula, proof, or computation. The final expression should be checked against the assumptions and notation of the corresponding chapter.
Diagnostic comment.
The formula should be verified by substitution into the defining equation and, when possible, by a small numerical test.
Exercise 7.17
Problem formulation.
State a nonlinear least-squares problem and define its Jacobian.
Method.
Use orthogonal projection, normal equations, QR/SVD least squares, regularization formulas, and residual orthogonality.
Detailed solution and justification.
The least-squares solution is characterized by residual orthogonality: r=b-Ax,\qquad A^Tr=0. Equivalently, A^TAx=A^Tb. For numerical stability, QR or SVD is preferred over explicitly forming A^TA because \kappa(A^TA)=\kappa(A)^2. Regularization replaces the problem by \min_x \|Ax-b\|_2^2+\lambda\|x\|_2^2, giving (A^TA+\lambda I)x=A^Tb.
Conclusion.
The displayed derivation gives the requested formula, proof, or computation. The final expression should be checked against the assumptions and notation of the corresponding chapter.
Diagnostic comment.
The formula should be verified by substitution into the defining equation and, when possible, by a small numerical test.
Exercise 7.18
Problem formulation.
Derive the linear least-squares subproblem solved in one Gauss–Newton step.
Method.
Use orthogonal projection, normal equations, QR/SVD least squares, regularization formulas, and residual orthogonality.
Detailed solution and justification.
The least-squares solution is characterized by residual orthogonality: r=b-Ax,\qquad A^Tr=0. Equivalently, A^TAx=A^Tb. For numerical stability, QR or SVD is preferred over explicitly forming A^TA because \kappa(A^TA)=\kappa(A)^2. Regularization replaces the problem by \min_x \|Ax-b\|_2^2+\lambda\|x\|_2^2, giving (A^TA+\lambda I)x=A^Tb.
Conclusion.
The displayed derivation gives the requested formula, proof, or computation. The final expression should be checked against the assumptions and notation of the corresponding chapter.
Diagnostic comment.
Verify the stationarity residual, feasibility residual, and descent or curvature condition, not only the final numerical value.
Exercise 7.19
Problem formulation.
Why are products with both A and A^T needed in LSQR-type methods?
Method.
Use orthogonal projection, normal equations, QR/SVD least squares, regularization formulas, and residual orthogonality.
Detailed solution and justification.
Let A=QR, where Q has orthonormal columns. Then \|Ax-b\|_2=\|QRx-b\|_2. Decompose b=QQ^Tb+(I-QQ^T)b. Since the two parts are orthogonal, \|QRx-b\|_2^2 = \|Rx-Q^Tb\|_2^2+\|(I-QQ^T)b\|_2^2. The second term is independent of x. Hence the least-squares minimizer satisfies Rx=Q^Tb.
Conclusion.
The displayed derivation gives the requested formula, proof, or computation. The final expression should be checked against the assumptions and notation of the corresponding chapter.
Diagnostic comment.
The formula should be verified by substitution into the defining equation and, when possible, by a small numerical test.
Exercise 7.20
Problem formulation.
What is the idea of sketching in randomized least squares?
Method.
Use orthogonal projection, normal equations, QR/SVD least squares, regularization formulas, and residual orthogonality.
Detailed solution and justification.
The least-squares solution is characterized by residual orthogonality: r=b-Ax,\qquad A^Tr=0. Equivalently, A^TAx=A^Tb. For numerical stability, QR or SVD is preferred over explicitly forming A^TA because \kappa(A^TA)=\kappa(A)^2. Regularization replaces the problem by \min_x \|Ax-b\|_2^2+\lambda\|x\|_2^2, giving (A^TA+\lambda I)x=A^Tb.
Conclusion.
The displayed derivation gives the requested formula, proof, or computation. The final expression should be checked against the assumptions and notation of the corresponding chapter.
Diagnostic comment.
The formula should be verified by substitution into the defining equation and, when possible, by a small numerical test.
Exercise 7.21
Problem formulation.
Prove the referenced result.
Method.
Use orthogonal projection, normal equations, QR/SVD least squares, regularization formulas, and residual orthogonality.
Detailed solution and justification.
The least-squares solution is characterized by residual orthogonality: r=b-Ax,\qquad A^Tr=0. Equivalently, A^TAx=A^Tb. For numerical stability, QR or SVD is preferred over explicitly forming A^TA because \kappa(A^TA)=\kappa(A)^2. Regularization replaces the problem by \min_x \|Ax-b\|_2^2+\lambda\|x\|_2^2, giving (A^TA+\lambda I)x=A^Tb.
Conclusion.
The displayed derivation gives the requested formula, proof, or computation. The final expression should be checked against the assumptions and notation of the corresponding chapter.
Diagnostic comment.
The formula should be verified by substitution into the defining equation and, when possible, by a small numerical test.
Exercise 7.22
Problem formulation.
Prove the referenced result.
Method.
Use orthogonal projection, normal equations, QR/SVD least squares, regularization formulas, and residual orthogonality.
Detailed solution and justification.
Minimize \phi(x)=\frac12\|Ax-b\|_2^2. Then \phi(x)=\frac12(Ax-b)^T(Ax-b). Differentiating, \nabla\phi(x)=A^T(Ax-b). At a minimizer, A^T(Ax-b)=0. Therefore A^TAx=A^Tb. These are the normal equations. They express the orthogonality condition b-Ax\perp \operatorname{range}(A).
Conclusion.
The displayed derivation gives the requested formula, proof, or computation. The final expression should be checked against the assumptions and notation of the corresponding chapter.
Diagnostic comment.
The formula should be verified by substitution into the defining equation and, when possible, by a small numerical test.
Exercise 7.23
Problem formulation.
Prove the referenced result.
Method.
Use orthogonal projection, normal equations, QR/SVD least squares, regularization formulas, and residual orthogonality.
Detailed solution and justification.
The least-squares solution is characterized by residual orthogonality: r=b-Ax,\qquad A^Tr=0. Equivalently, A^TAx=A^Tb. For numerical stability, QR or SVD is preferred over explicitly forming A^TA because \kappa(A^TA)=\kappa(A)^2. Regularization replaces the problem by \min_x \|Ax-b\|_2^2+\lambda\|x\|_2^2, giving (A^TA+\lambda I)x=A^Tb.
Conclusion.
The displayed derivation gives the requested formula, proof, or computation. The final expression should be checked against the assumptions and notation of the corresponding chapter.
Diagnostic comment.
The formula should be verified by substitution into the defining equation and, when possible, by a small numerical test.
Exercise 7.24
Problem formulation.
Prove the referenced result.
Method.
Use orthogonal projection, normal equations, QR/SVD least squares, regularization formulas, and residual orthogonality.
Detailed solution and justification.
The least-squares solution is characterized by residual orthogonality: r=b-Ax,\qquad A^Tr=0. Equivalently, A^TAx=A^Tb. For numerical stability, QR or SVD is preferred over explicitly forming A^TA because \kappa(A^TA)=\kappa(A)^2. Regularization replaces the problem by \min_x \|Ax-b\|_2^2+\lambda\|x\|_2^2, giving (A^TA+\lambda I)x=A^Tb.
Conclusion.
The displayed derivation gives the requested formula, proof, or computation. The final expression should be checked against the assumptions and notation of the corresponding chapter.
Diagnostic comment.
The formula should be verified by substitution into the defining equation and, when possible, by a small numerical test.
Exercise 7.25
Problem formulation.
Prove the referenced result.
Method.
Use orthogonal projection, normal equations, QR/SVD least squares, regularization formulas, and residual orthogonality.
Detailed solution and justification.
The least-squares solution is characterized by residual orthogonality: r=b-Ax,\qquad A^Tr=0. Equivalently, A^TAx=A^Tb. For numerical stability, QR or SVD is preferred over explicitly forming A^TA because \kappa(A^TA)=\kappa(A)^2. Regularization replaces the problem by \min_x \|Ax-b\|_2^2+\lambda\|x\|_2^2, giving (A^TA+\lambda I)x=A^Tb.
Conclusion.
The displayed derivation gives the requested formula, proof, or computation. The final expression should be checked against the assumptions and notation of the corresponding chapter.
Diagnostic comment.
The formula should be verified by substitution into the defining equation and, when possible, by a small numerical test.
Exercise 7.26
Problem formulation.
Prove the referenced result.
Method.
Use orthogonal projection, normal equations, QR/SVD least squares, regularization formulas, and residual orthogonality.
Detailed solution and justification.
Minimize \phi(x)=\frac12\|Ax-b\|_2^2. Then \phi(x)=\frac12(Ax-b)^T(Ax-b). Differentiating, \nabla\phi(x)=A^T(Ax-b). At a minimizer, A^T(Ax-b)=0. Therefore A^TAx=A^Tb. These are the normal equations. They express the orthogonality condition b-Ax\perp \operatorname{range}(A).
Conclusion.
The displayed derivation gives the requested formula, proof, or computation. The final expression should be checked against the assumptions and notation of the corresponding chapter.
Diagnostic comment.
Distinguish forward error from backward error; a small residual does not imply a small forward error when the problem is ill-conditioned.
Exercise 7.27
Problem formulation.
Prove the referenced result.
Method.
Use orthogonal projection, normal equations, QR/SVD least squares, regularization formulas, and residual orthogonality.
Detailed solution and justification.
Let A=QR, where Q has orthonormal columns. Then \|Ax-b\|_2=\|QRx-b\|_2. Decompose b=QQ^Tb+(I-QQ^T)b. Since the two parts are orthogonal, \|QRx-b\|_2^2 = \|Rx-Q^Tb\|_2^2+\|(I-QQ^T)b\|_2^2. The second term is independent of x. Hence the least-squares minimizer satisfies Rx=Q^Tb.
Conclusion.
The displayed derivation gives the requested formula, proof, or computation. The final expression should be checked against the assumptions and notation of the corresponding chapter.
Diagnostic comment.
The formula should be verified by substitution into the defining equation and, when possible, by a small numerical test.
Exercise 7.28
Problem formulation.
Prove the referenced result.
Method.
Use orthogonal projection, normal equations, QR/SVD least squares, regularization formulas, and residual orthogonality.
Detailed solution and justification.
Let A=U\Sigma V^T. The least-squares problem becomes \min_x\|\Sigma V^Tx-U^Tb\|_2. Set z=V^Tx. Then solve \min_z\|\Sigma z-U^Tb\|_2. The minimum-norm solution is z_i= \begin{cases} (u_i^Tb)/\sigma_i, & \sigma_i>0,\\ 0, & \sigma_i=0. \end{cases} Therefore x=A^\dagger b=V\Sigma^\dagger U^Tb.
Conclusion.
The displayed derivation gives the requested formula, proof, or computation. The final expression should be checked against the assumptions and notation of the corresponding chapter.
Diagnostic comment.
The formula should be verified by substitution into the defining equation and, when possible, by a small numerical test.
Exercise 7.29
Problem formulation.
Prove the referenced result.
Method.
Use orthogonal projection, normal equations, QR/SVD least squares, regularization formulas, and residual orthogonality.
Detailed solution and justification.
Let A=U\Sigma V^T. The least-squares problem becomes \min_x\|\Sigma V^Tx-U^Tb\|_2. Set z=V^Tx. Then solve \min_z\|\Sigma z-U^Tb\|_2. The minimum-norm solution is z_i= \begin{cases} (u_i^Tb)/\sigma_i, & \sigma_i>0,\\ 0, & \sigma_i=0. \end{cases} Therefore x=A^\dagger b=V\Sigma^\dagger U^Tb.
Conclusion.
The displayed derivation gives the requested formula, proof, or computation. The final expression should be checked against the assumptions and notation of the corresponding chapter.
Diagnostic comment.
The formula should be verified by substitution into the defining equation and, when possible, by a small numerical test.
Exercise 7.30
Problem formulation.
Prove the referenced result.
Method.
Use orthogonal projection, normal equations, QR/SVD least squares, regularization formulas, and residual orthogonality.
Detailed solution and justification.
The least-squares solution is characterized by residual orthogonality: r=b-Ax,\qquad A^Tr=0. Equivalently, A^TAx=A^Tb. For numerical stability, QR or SVD is preferred over explicitly forming A^TA because \kappa(A^TA)=\kappa(A)^2. Regularization replaces the problem by \min_x \|Ax-b\|_2^2+\lambda\|x\|_2^2, giving (A^TA+\lambda I)x=A^Tb.
Conclusion.
The displayed derivation gives the requested formula, proof, or computation. The final expression should be checked against the assumptions and notation of the corresponding chapter.
Diagnostic comment.
The formula should be verified by substitution into the defining equation and, when possible, by a small numerical test.
Exercise 7.31
Problem formulation.
Prove the referenced result.
Method.
Use orthogonal projection, normal equations, QR/SVD least squares, regularization formulas, and residual orthogonality.
Detailed solution and justification.
Minimize \phi(x)=\frac12\|Ax-b\|_2^2. Then \phi(x)=\frac12(Ax-b)^T(Ax-b). Differentiating, \nabla\phi(x)=A^T(Ax-b). At a minimizer, A^T(Ax-b)=0. Therefore A^TAx=A^Tb. These are the normal equations. They express the orthogonality condition b-Ax\perp \operatorname{range}(A).
Conclusion.
The displayed derivation gives the requested formula, proof, or computation. The final expression should be checked against the assumptions and notation of the corresponding chapter.
Diagnostic comment.
The formula should be verified by substitution into the defining equation and, when possible, by a small numerical test.
Exercise 7.32
Problem formulation.
Prove the referenced result.
Method.
Use orthogonal projection, normal equations, QR/SVD least squares, regularization formulas, and residual orthogonality.
Detailed solution and justification.
The least-squares solution is characterized by residual orthogonality: r=b-Ax,\qquad A^Tr=0. Equivalently, A^TAx=A^Tb. For numerical stability, QR or SVD is preferred over explicitly forming A^TA because \kappa(A^TA)=\kappa(A)^2. Regularization replaces the problem by \min_x \|Ax-b\|_2^2+\lambda\|x\|_2^2, giving (A^TA+\lambda I)x=A^Tb.
Conclusion.
The displayed derivation gives the requested formula, proof, or computation. The final expression should be checked against the assumptions and notation of the corresponding chapter.
Diagnostic comment.
Verify the stationarity residual, feasibility residual, and descent or curvature condition, not only the final numerical value.
Exercise 7.33
Problem formulation.
Prove the referenced result.
Method.
Use orthogonal projection, normal equations, QR/SVD least squares, regularization formulas, and residual orthogonality.
Detailed solution and justification.
Minimize \phi(x)=\frac12\|Ax-b\|_2^2. Then \phi(x)=\frac12(Ax-b)^T(Ax-b). Differentiating, \nabla\phi(x)=A^T(Ax-b). At a minimizer, A^T(Ax-b)=0. Therefore A^TAx=A^Tb. These are the normal equations. They express the orthogonality condition b-Ax\perp \operatorname{range}(A).
Conclusion.
The displayed derivation gives the requested formula, proof, or computation. The final expression should be checked against the assumptions and notation of the corresponding chapter.
Diagnostic comment.
The formula should be verified by substitution into the defining equation and, when possible, by a small numerical test.
Exercise 7.34
Problem formulation.
Derive x_\lambda = \sum_{i=1}^r \frac{\sigma_i}{\sigma_i^2+\lambda}(u_i^Tb)v_i.
Method.
Use orthogonal projection, normal equations, QR/SVD least squares, regularization formulas, and residual orthogonality.
Detailed solution and justification.
Let A=U\Sigma V^T. The least-squares problem becomes \min_x\|\Sigma V^Tx-U^Tb\|_2. Set z=V^Tx. Then solve \min_z\|\Sigma z-U^Tb\|_2. The minimum-norm solution is z_i= \begin{cases} (u_i^Tb)/\sigma_i, & \sigma_i>0,\\ 0, & \sigma_i=0. \end{cases} Therefore x=A^\dagger b=V\Sigma^\dagger U^Tb.
Conclusion.
The displayed derivation gives the requested formula, proof, or computation. The final expression should be checked against the assumptions and notation of the corresponding chapter.
Diagnostic comment.
The formula should be verified by substitution into the defining equation and, when possible, by a small numerical test.
Exercise 7.35
Problem formulation.
Derive the Tikhonov filter factors and explain their behavior as \sigma_i\to0.
Method.
Use orthogonal projection, normal equations, QR/SVD least squares, regularization formulas, and residual orthogonality.
Detailed solution and justification.
The least-squares solution is characterized by residual orthogonality: r=b-Ax,\qquad A^Tr=0. Equivalently, A^TAx=A^Tb. For numerical stability, QR or SVD is preferred over explicitly forming A^TA because \kappa(A^TA)=\kappa(A)^2. Regularization replaces the problem by \min_x \|Ax-b\|_2^2+\lambda\|x\|_2^2, giving (A^TA+\lambda I)x=A^Tb.
Conclusion.
The displayed derivation gives the requested formula, proof, or computation. The final expression should be checked against the assumptions and notation of the corresponding chapter.
Diagnostic comment.
The formula should be verified by substitution into the defining equation and, when possible, by a small numerical test.
Exercise 7.36
Problem formulation.
Derive the truncated SVD solution and compare it with Tikhonov regularization.
Method.
Use orthogonal projection, normal equations, QR/SVD least squares, regularization formulas, and residual orthogonality.
Detailed solution and justification.
Let A=U\Sigma V^T. The least-squares problem becomes \min_x\|\Sigma V^Tx-U^Tb\|_2. Set z=V^Tx. Then solve \min_z\|\Sigma z-U^Tb\|_2. The minimum-norm solution is z_i= \begin{cases} (u_i^Tb)/\sigma_i, & \sigma_i>0,\\ 0, & \sigma_i=0. \end{cases} Therefore x=A^\dagger b=V\Sigma^\dagger U^Tb.
Conclusion.
The displayed derivation gives the requested formula, proof, or computation. The final expression should be checked against the assumptions and notation of the corresponding chapter.
Diagnostic comment.
The formula should be verified by substitution into the defining equation and, when possible, by a small numerical test.
Exercise 7.37
Problem formulation.
Derive the least-squares system for polynomial fitting in a monomial basis.
Method.
Use orthogonal projection, normal equations, QR/SVD least squares, regularization formulas, and residual orthogonality.
Detailed solution and justification.
The least-squares solution is characterized by residual orthogonality: r=b-Ax,\qquad A^Tr=0. Equivalently, A^TAx=A^Tb. For numerical stability, QR or SVD is preferred over explicitly forming A^TA because \kappa(A^TA)=\kappa(A)^2. Regularization replaces the problem by \min_x \|Ax-b\|_2^2+\lambda\|x\|_2^2, giving (A^TA+\lambda I)x=A^Tb.
Conclusion.
The displayed derivation gives the requested formula, proof, or computation. The final expression should be checked against the assumptions and notation of the corresponding chapter.
Diagnostic comment.
The formula should be verified by substitution into the defining equation and, when possible, by a small numerical test.
Exercise 7.38
Problem formulation.
Explain why an orthogonal polynomial basis improves least-squares fitting.
Method.
Use orthogonal projection, normal equations, QR/SVD least squares, regularization formulas, and residual orthogonality.
Detailed solution and justification.
The least-squares solution is characterized by residual orthogonality: r=b-Ax,\qquad A^Tr=0. Equivalently, A^TAx=A^Tb. For numerical stability, QR or SVD is preferred over explicitly forming A^TA because \kappa(A^TA)=\kappa(A)^2. Regularization replaces the problem by \min_x \|Ax-b\|_2^2+\lambda\|x\|_2^2, giving (A^TA+\lambda I)x=A^Tb.
Conclusion.
The displayed derivation gives the requested formula, proof, or computation. The final expression should be checked against the assumptions and notation of the corresponding chapter.
Diagnostic comment.
The formula should be verified by substitution into the defining equation and, when possible, by a small numerical test.
Exercise 7.39
Problem formulation.
Derive the Gauss–Newton normal equations J^TJs=-J^TF.
Method.
Use orthogonal projection, normal equations, QR/SVD least squares, regularization formulas, and residual orthogonality.
Detailed solution and justification.
Minimize \phi(x)=\frac12\|Ax-b\|_2^2. Then \phi(x)=\frac12(Ax-b)^T(Ax-b). Differentiating, \nabla\phi(x)=A^T(Ax-b). At a minimizer, A^T(Ax-b)=0. Therefore A^TAx=A^Tb. These are the normal equations. They express the orthogonality condition b-Ax\perp \operatorname{range}(A).
Conclusion.
The displayed derivation gives the requested formula, proof, or computation. The final expression should be checked against the assumptions and notation of the corresponding chapter.
Diagnostic comment.
Verify the stationarity residual, feasibility residual, and descent or curvature condition, not only the final numerical value.
Exercise 7.40
Problem formulation.
Derive the Levenberg–Marquardt step (J^TJ+\lambda I)s=-J^TF.
Method.
Use orthogonal projection, normal equations, QR/SVD least squares, regularization formulas, and residual orthogonality.
Detailed solution and justification.
The least-squares solution is characterized by residual orthogonality: r=b-Ax,\qquad A^Tr=0. Equivalently, A^TAx=A^Tb. For numerical stability, QR or SVD is preferred over explicitly forming A^TA because \kappa(A^TA)=\kappa(A)^2. Regularization replaces the problem by \min_x \|Ax-b\|_2^2+\lambda\|x\|_2^2, giving (A^TA+\lambda I)x=A^Tb.
Conclusion.
The displayed derivation gives the requested formula, proof, or computation. The final expression should be checked against the assumptions and notation of the corresponding chapter.
Diagnostic comment.
The formula should be verified by substitution into the defining equation and, when possible, by a small numerical test.
Exercise 7.41
Problem formulation.
Develop a first-order perturbation theory for the least-squares solution under perturbations in both A and b.
Method.
Use orthogonal projection, normal equations, QR/SVD least squares, regularization formulas, and residual orthogonality.
Detailed solution and justification.
The least-squares solution is characterized by residual orthogonality: r=b-Ax,\qquad A^Tr=0. Equivalently, A^TAx=A^Tb. For numerical stability, QR or SVD is preferred over explicitly forming A^TA because \kappa(A^TA)=\kappa(A)^2. Regularization replaces the problem by \min_x \|Ax-b\|_2^2+\lambda\|x\|_2^2, giving (A^TA+\lambda I)x=A^Tb.
Conclusion.
The displayed derivation gives the requested formula, proof, or computation. The final expression should be checked against the assumptions and notation of the corresponding chapter.
Diagnostic comment.
The order claim should be confirmed by a Taylor expansion or a log-log refinement table using a problem with a known exact solution.
Exercise 7.42
Problem formulation.
Derive a relative condition-number estimate for the full-rank least-squares problem and identify the role of the residual norm.
Method.
Use orthogonal projection, normal equations, QR/SVD least squares, regularization formulas, and residual orthogonality.
Detailed solution and justification.
The least-squares solution is characterized by residual orthogonality: r=b-Ax,\qquad A^Tr=0. Equivalently, A^TAx=A^Tb. For numerical stability, QR or SVD is preferred over explicitly forming A^TA because \kappa(A^TA)=\kappa(A)^2. Regularization replaces the problem by \min_x \|Ax-b\|_2^2+\lambda\|x\|_2^2, giving (A^TA+\lambda I)x=A^Tb.
Conclusion.
The displayed derivation gives the requested formula, proof, or computation. The final expression should be checked against the assumptions and notation of the corresponding chapter.
Diagnostic comment.
Distinguish forward error from backward error; a small residual does not imply a small forward error when the problem is ill-conditioned.
Exercise 7.43
Problem formulation.
Explain why Householder QR gives a backward stable least-squares solver.
Method.
Use orthogonal projection, normal equations, QR/SVD least squares, regularization formulas, and residual orthogonality.
Detailed solution and justification.
Let A=QR, where Q has orthonormal columns. Then \|Ax-b\|_2=\|QRx-b\|_2. Decompose b=QQ^Tb+(I-QQ^T)b. Since the two parts are orthogonal, \|QRx-b\|_2^2 = \|Rx-Q^Tb\|_2^2+\|(I-QQ^T)b\|_2^2. The second term is independent of x. Hence the least-squares minimizer satisfies Rx=Q^Tb.
Conclusion.
The displayed derivation gives the requested formula, proof, or computation. The final expression should be checked against the assumptions and notation of the corresponding chapter.
Diagnostic comment.
Always test the result on the scalar model equation or Fourier mode and verify the amplification factor satisfies the stated stability bound.
Exercise 7.44
Problem formulation.
Analyze modified Gram–Schmidt for least squares and compare it with Householder QR.
Method.
Use orthogonal projection, normal equations, QR/SVD least squares, regularization formulas, and residual orthogonality.
Detailed solution and justification.
Let A=QR, where Q has orthonormal columns. Then \|Ax-b\|_2=\|QRx-b\|_2. Decompose b=QQ^Tb+(I-QQ^T)b. Since the two parts are orthogonal, \|QRx-b\|_2^2 = \|Rx-Q^Tb\|_2^2+\|(I-QQ^T)b\|_2^2. The second term is independent of x. Hence the least-squares minimizer satisfies Rx=Q^Tb.
Conclusion.
The displayed derivation gives the requested formula, proof, or computation. The final expression should be checked against the assumptions and notation of the corresponding chapter.
Diagnostic comment.
The formula should be verified by substitution into the defining equation and, when possible, by a small numerical test.
Exercise 7.45
Problem formulation.
Show that solving normal equations by Cholesky can be backward stable for the normal equations but still forward inaccurate for the original least-squares problem.
Method.
Use orthogonal projection, normal equations, QR/SVD least squares, regularization formulas, and residual orthogonality.
Detailed solution and justification.
Minimize \phi(x)=\frac12\|Ax-b\|_2^2. Then \phi(x)=\frac12(Ax-b)^T(Ax-b). Differentiating, \nabla\phi(x)=A^T(Ax-b). At a minimizer, A^T(Ax-b)=0. Therefore A^TAx=A^Tb. These are the normal equations. They express the orthogonality condition b-Ax\perp \operatorname{range}(A).
Conclusion.
The displayed derivation gives the requested formula, proof, or computation. The final expression should be checked against the assumptions and notation of the corresponding chapter.
Diagnostic comment.
The order claim should be confirmed by a Taylor expansion or a log-log refinement table using a problem with a known exact solution.
Exercise 7.46
Problem formulation.
Explain rank-revealing QR and compare it with the SVD for numerical rank detection.
Method.
Use orthogonal projection, normal equations, QR/SVD least squares, regularization formulas, and residual orthogonality.
Detailed solution and justification.
Let A=QR, where Q has orthonormal columns. Then \|Ax-b\|_2=\|QRx-b\|_2. Decompose b=QQ^Tb+(I-QQ^T)b. Since the two parts are orthogonal, \|QRx-b\|_2^2 = \|Rx-Q^Tb\|_2^2+\|(I-QQ^T)b\|_2^2. The second term is independent of x. Hence the least-squares minimizer satisfies Rx=Q^Tb.
Conclusion.
The displayed derivation gives the requested formula, proof, or computation. The final expression should be checked against the assumptions and notation of the corresponding chapter.
Diagnostic comment.
The formula should be verified by substitution into the defining equation and, when possible, by a small numerical test.
Exercise 7.47
Problem formulation.
Study the complete orthogonal decomposition for rank-deficient least squares.
Method.
Use orthogonal projection, normal equations, QR/SVD least squares, regularization formulas, and residual orthogonality.
Detailed solution and justification.
The least-squares solution is characterized by residual orthogonality: r=b-Ax,\qquad A^Tr=0. Equivalently, A^TAx=A^Tb. For numerical stability, QR or SVD is preferred over explicitly forming A^TA because \kappa(A^TA)=\kappa(A)^2. Regularization replaces the problem by \min_x \|Ax-b\|_2^2+\lambda\|x\|_2^2, giving (A^TA+\lambda I)x=A^Tb.
Conclusion.
The displayed derivation gives the requested formula, proof, or computation. The final expression should be checked against the assumptions and notation of the corresponding chapter.
Diagnostic comment.
The formula should be verified by substitution into the defining equation and, when possible, by a small numerical test.
Exercise 7.48
Problem formulation.
Prove the four Moore–Penrose pseudoinverse identities.
Method.
Use orthogonal projection, normal equations, QR/SVD least squares, regularization formulas, and residual orthogonality.
Detailed solution and justification.
The least-squares solution is characterized by residual orthogonality: r=b-Ax,\qquad A^Tr=0. Equivalently, A^TAx=A^Tb. For numerical stability, QR or SVD is preferred over explicitly forming A^TA because \kappa(A^TA)=\kappa(A)^2. Regularization replaces the problem by \min_x \|Ax-b\|_2^2+\lambda\|x\|_2^2, giving (A^TA+\lambda I)x=A^Tb.
Conclusion.
The displayed derivation gives the requested formula, proof, or computation. The final expression should be checked against the assumptions and notation of the corresponding chapter.
Diagnostic comment.
The formula should be verified by substitution into the defining equation and, when possible, by a small numerical test.
Exercise 7.49
Problem formulation.
Show that A^\dagger b is orthogonal to the null space of A.
Method.
Use orthogonal projection, normal equations, QR/SVD least squares, regularization formulas, and residual orthogonality.
Detailed solution and justification.
The least-squares solution is characterized by residual orthogonality: r=b-Ax,\qquad A^Tr=0. Equivalently, A^TAx=A^Tb. For numerical stability, QR or SVD is preferred over explicitly forming A^TA because \kappa(A^TA)=\kappa(A)^2. Regularization replaces the problem by \min_x \|Ax-b\|_2^2+\lambda\|x\|_2^2, giving (A^TA+\lambda I)x=A^Tb.
Conclusion.
The displayed derivation gives the requested formula, proof, or computation. The final expression should be checked against the assumptions and notation of the corresponding chapter.
Diagnostic comment.
The formula should be verified by substitution into the defining equation and, when possible, by a small numerical test.
Exercise 7.50
Problem formulation.
Derive the total least-squares problem and show how it is related to the SVD of [A\ b].
Method.
Use orthogonal projection, normal equations, QR/SVD least squares, regularization formulas, and residual orthogonality.
Detailed solution and justification.
Let A=U\Sigma V^T. The least-squares problem becomes \min_x\|\Sigma V^Tx-U^Tb\|_2. Set z=V^Tx. Then solve \min_z\|\Sigma z-U^Tb\|_2. The minimum-norm solution is z_i= \begin{cases} (u_i^Tb)/\sigma_i, & \sigma_i>0,\\ 0, & \sigma_i=0. \end{cases} Therefore x=A^\dagger b=V\Sigma^\dagger U^Tb.
Conclusion.
The displayed derivation gives the requested formula, proof, or computation. The final expression should be checked against the assumptions and notation of the corresponding chapter.
Diagnostic comment.
The formula should be verified by substitution into the defining equation and, when possible, by a small numerical test.
Exercise 7.51
Problem formulation.
Analyze the bias-variance tradeoff in Tikhonov regularization using the SVD.
Method.
Use orthogonal projection, normal equations, QR/SVD least squares, regularization formulas, and residual orthogonality.
Detailed solution and justification.
Let A=U\Sigma V^T. The least-squares problem becomes \min_x\|\Sigma V^Tx-U^Tb\|_2. Set z=V^Tx. Then solve \min_z\|\Sigma z-U^Tb\|_2. The minimum-norm solution is z_i= \begin{cases} (u_i^Tb)/\sigma_i, & \sigma_i>0,\\ 0, & \sigma_i=0. \end{cases} Therefore x=A^\dagger b=V\Sigma^\dagger U^Tb.
Conclusion.
The displayed derivation gives the requested formula, proof, or computation. The final expression should be checked against the assumptions and notation of the corresponding chapter.
Diagnostic comment.
The formula should be verified by substitution into the defining equation and, when possible, by a small numerical test.
Exercise 7.52
Problem formulation.
Derive Morozov’s discrepancy principle for choosing the regularization parameter.
Method.
Use orthogonal projection, normal equations, QR/SVD least squares, regularization formulas, and residual orthogonality.
Detailed solution and justification.
The least-squares solution is characterized by residual orthogonality: r=b-Ax,\qquad A^Tr=0. Equivalently, A^TAx=A^Tb. For numerical stability, QR or SVD is preferred over explicitly forming A^TA because \kappa(A^TA)=\kappa(A)^2. Regularization replaces the problem by \min_x \|Ax-b\|_2^2+\lambda\|x\|_2^2, giving (A^TA+\lambda I)x=A^Tb.
Conclusion.
The displayed derivation gives the requested formula, proof, or computation. The final expression should be checked against the assumptions and notation of the corresponding chapter.
Diagnostic comment.
The formula should be verified by substitution into the defining equation and, when possible, by a small numerical test.
Exercise 7.53
Problem formulation.
Derive the generalized cross-validation function for Tikhonov regularization.
Method.
Use orthogonal projection, normal equations, QR/SVD least squares, regularization formulas, and residual orthogonality.
Detailed solution and justification.
The least-squares solution is characterized by residual orthogonality: r=b-Ax,\qquad A^Tr=0. Equivalently, A^TAx=A^Tb. For numerical stability, QR or SVD is preferred over explicitly forming A^TA because \kappa(A^TA)=\kappa(A)^2. Regularization replaces the problem by \min_x \|Ax-b\|_2^2+\lambda\|x\|_2^2, giving (A^TA+\lambda I)x=A^Tb.
Conclusion.
The displayed derivation gives the requested formula, proof, or computation. The final expression should be checked against the assumptions and notation of the corresponding chapter.
Diagnostic comment.
The formula should be verified by substitution into the defining equation and, when possible, by a small numerical test.
Exercise 7.54
Problem formulation.
Derive a formula for the curvature of the L-curve and explain how it identifies a regularization parameter.
Method.
Use orthogonal projection, normal equations, QR/SVD least squares, regularization formulas, and residual orthogonality.
Detailed solution and justification.
The least-squares solution is characterized by residual orthogonality: r=b-Ax,\qquad A^Tr=0. Equivalently, A^TAx=A^Tb. For numerical stability, QR or SVD is preferred over explicitly forming A^TA because \kappa(A^TA)=\kappa(A)^2. Regularization replaces the problem by \min_x \|Ax-b\|_2^2+\lambda\|x\|_2^2, giving (A^TA+\lambda I)x=A^Tb.
Conclusion.
The displayed derivation gives the requested formula, proof, or computation. The final expression should be checked against the assumptions and notation of the corresponding chapter.
Diagnostic comment.
The formula should be verified by substitution into the defining equation and, when possible, by a small numerical test.
Exercise 7.55
Problem formulation.
Analyze \min_x\left(\|Ax-b\|_2^2+\lambda\|Lx\|_2^2\right) for a general regularization matrix L.
Method.
Use orthogonal projection, normal equations, QR/SVD least squares, regularization formulas, and residual orthogonality.
Detailed solution and justification.
The least-squares solution is characterized by residual orthogonality: r=b-Ax,\qquad A^Tr=0. Equivalently, A^TAx=A^Tb. For numerical stability, QR or SVD is preferred over explicitly forming A^TA because \kappa(A^TA)=\kappa(A)^2. Regularization replaces the problem by \min_x \|Ax-b\|_2^2+\lambda\|x\|_2^2, giving (A^TA+\lambda I)x=A^Tb.
Conclusion.
The displayed derivation gives the requested formula, proof, or computation. The final expression should be checked against the assumptions and notation of the corresponding chapter.
Diagnostic comment.
The formula should be verified by substitution into the defining equation and, when possible, by a small numerical test.
Exercise 7.56
Problem formulation.
Show that weighted least squares is maximum likelihood when the noise covariance is known and nonspherical.
Method.
Use orthogonal projection, normal equations, QR/SVD least squares, regularization formulas, and residual orthogonality.
Detailed solution and justification.
The least-squares solution is characterized by residual orthogonality: r=b-Ax,\qquad A^Tr=0. Equivalently, A^TAx=A^Tb. For numerical stability, QR or SVD is preferred over explicitly forming A^TA because \kappa(A^TA)=\kappa(A)^2. Regularization replaces the problem by \min_x \|Ax-b\|_2^2+\lambda\|x\|_2^2, giving (A^TA+\lambda I)x=A^Tb.
Conclusion.
The displayed derivation gives the requested formula, proof, or computation. The final expression should be checked against the assumptions and notation of the corresponding chapter.
Diagnostic comment.
The formula should be verified by substitution into the defining equation and, when possible, by a small numerical test.
Exercise 7.57
Problem formulation.
Solve equality-constrained least squares by parametrizing the constraint Cx=d.
Method.
Use orthogonal projection, normal equations, QR/SVD least squares, regularization formulas, and residual orthogonality.
Detailed solution and justification.
The least-squares solution is characterized by residual orthogonality: r=b-Ax,\qquad A^Tr=0. Equivalently, A^TAx=A^Tb. For numerical stability, QR or SVD is preferred over explicitly forming A^TA because \kappa(A^TA)=\kappa(A)^2. Regularization replaces the problem by \min_x \|Ax-b\|_2^2+\lambda\|x\|_2^2, giving (A^TA+\lambda I)x=A^Tb.
Conclusion.
The displayed derivation gives the requested formula, proof, or computation. The final expression should be checked against the assumptions and notation of the corresponding chapter.
Diagnostic comment.
The formula should be verified by substitution into the defining equation and, when possible, by a small numerical test.
Exercise 7.58
Problem formulation.
Derive a QR-based method for equality-constrained least squares.
Method.
Use orthogonal projection, normal equations, QR/SVD least squares, regularization formulas, and residual orthogonality.
Detailed solution and justification.
Let A=QR, where Q has orthonormal columns. Then \|Ax-b\|_2=\|QRx-b\|_2. Decompose b=QQ^Tb+(I-QQ^T)b. Since the two parts are orthogonal, \|QRx-b\|_2^2 = \|Rx-Q^Tb\|_2^2+\|(I-QQ^T)b\|_2^2. The second term is independent of x. Hence the least-squares minimizer satisfies Rx=Q^Tb.
Conclusion.
The displayed derivation gives the requested formula, proof, or computation. The final expression should be checked against the assumptions and notation of the corresponding chapter.
Diagnostic comment.
The formula should be verified by substitution into the defining equation and, when possible, by a small numerical test.
Exercise 7.59
Problem formulation.
Analyze CGLS as CG applied to A^TAx=A^Tb, without forming A^TA.
Method.
Use orthogonal projection, normal equations, QR/SVD least squares, regularization formulas, and residual orthogonality.
Detailed solution and justification.
The least-squares solution is characterized by residual orthogonality: r=b-Ax,\qquad A^Tr=0. Equivalently, A^TAx=A^Tb. For numerical stability, QR or SVD is preferred over explicitly forming A^TA because \kappa(A^TA)=\kappa(A)^2. Regularization replaces the problem by \min_x \|Ax-b\|_2^2+\lambda\|x\|_2^2, giving (A^TA+\lambda I)x=A^Tb.
Conclusion.
The displayed derivation gives the requested formula, proof, or computation. The final expression should be checked against the assumptions and notation of the corresponding chapter.
Diagnostic comment.
The order claim should be confirmed by a Taylor expansion or a log-log refinement table using a problem with a known exact solution.
Exercise 7.60
Problem formulation.
Derive the Golub–Kahan bidiagonalization relation underlying LSQR.
Method.
Use orthogonal projection, normal equations, QR/SVD least squares, regularization formulas, and residual orthogonality.
Detailed solution and justification.
Let A=QR, where Q has orthonormal columns. Then \|Ax-b\|_2=\|QRx-b\|_2. Decompose b=QQ^Tb+(I-QQ^T)b. Since the two parts are orthogonal, \|QRx-b\|_2^2 = \|Rx-Q^Tb\|_2^2+\|(I-QQ^T)b\|_2^2. The second term is independent of x. Hence the least-squares minimizer satisfies Rx=Q^Tb.
Conclusion.
The displayed derivation gives the requested formula, proof, or computation. The final expression should be checked against the assumptions and notation of the corresponding chapter.
Diagnostic comment.
The formula should be verified by substitution into the defining equation and, when possible, by a small numerical test.
Exercise 7.61
Problem formulation.
State local convergence conditions for Gauss–Newton.
Method.
Use orthogonal projection, normal equations, QR/SVD least squares, regularization formulas, and residual orthogonality.
Detailed solution and justification.
The least-squares solution is characterized by residual orthogonality: r=b-Ax,\qquad A^Tr=0. Equivalently, A^TAx=A^Tb. For numerical stability, QR or SVD is preferred over explicitly forming A^TA because \kappa(A^TA)=\kappa(A)^2. Regularization replaces the problem by \min_x \|Ax-b\|_2^2+\lambda\|x\|_2^2, giving (A^TA+\lambda I)x=A^Tb.
Conclusion.
The displayed derivation gives the requested formula, proof, or computation. The final expression should be checked against the assumptions and notation of the corresponding chapter.
Diagnostic comment.
The order claim should be confirmed by a Taylor expansion or a log-log refinement table using a problem with a known exact solution.
Exercise 7.62
Problem formulation.
Compare least squares with robust regression based on L^1, Huber, or Tukey loss functions.
Method.
Use orthogonal projection, normal equations, QR/SVD least squares, regularization formulas, and residual orthogonality.
Detailed solution and justification.
The least-squares solution is characterized by residual orthogonality: r=b-Ax,\qquad A^Tr=0. Equivalently, A^TAx=A^Tb. For numerical stability, QR or SVD is preferred over explicitly forming A^TA because \kappa(A^TA)=\kappa(A)^2. Regularization replaces the problem by \min_x \|Ax-b\|_2^2+\lambda\|x\|_2^2, giving (A^TA+\lambda I)x=A^Tb.
Conclusion.
The displayed derivation gives the requested formula, proof, or computation. The final expression should be checked against the assumptions and notation of the corresponding chapter.
Diagnostic comment.
The formula should be verified by substitution into the defining equation and, when possible, by a small numerical test.
Exercise 7.63
Problem formulation.
Derive recursive least squares using the Sherman–Morrison formula.
Method.
Use orthogonal projection, normal equations, QR/SVD least squares, regularization formulas, and residual orthogonality.
Detailed solution and justification.
The least-squares solution is characterized by residual orthogonality: r=b-Ax,\qquad A^Tr=0. Equivalently, A^TAx=A^Tb. For numerical stability, QR or SVD is preferred over explicitly forming A^TA because \kappa(A^TA)=\kappa(A)^2. Regularization replaces the problem by \min_x \|Ax-b\|_2^2+\lambda\|x\|_2^2, giving (A^TA+\lambda I)x=A^Tb.
Conclusion.
The displayed derivation gives the requested formula, proof, or computation. The final expression should be checked against the assumptions and notation of the corresponding chapter.
Diagnostic comment.
The formula should be verified by substitution into the defining equation and, when possible, by a small numerical test.
Exercise 7.64
Problem formulation.
Explain how QR factorization can be updated when a new row is added to A.
Method.
Use orthogonal projection, normal equations, QR/SVD least squares, regularization formulas, and residual orthogonality.
Detailed solution and justification.
Let A=QR, where Q has orthonormal columns. Then \|Ax-b\|_2=\|QRx-b\|_2. Decompose b=QQ^Tb+(I-QQ^T)b. Since the two parts are orthogonal, \|QRx-b\|_2^2 = \|Rx-Q^Tb\|_2^2+\|(I-QQ^T)b\|_2^2. The second term is independent of x. Hence the least-squares minimizer satisfies Rx=Q^Tb.
Conclusion.
The displayed derivation gives the requested formula, proof, or computation. The final expression should be checked against the assumptions and notation of the corresponding chapter.
Diagnostic comment.
The formula should be verified by substitution into the defining equation and, when possible, by a small numerical test.
Exercise 7.65
Problem formulation.
Discuss the numerical difficulties of QR downdating.
Method.
Use orthogonal projection, normal equations, QR/SVD least squares, regularization formulas, and residual orthogonality.
Detailed solution and justification.
Let A=QR, where Q has orthonormal columns. Then \|Ax-b\|_2=\|QRx-b\|_2. Decompose b=QQ^Tb+(I-QQ^T)b. Since the two parts are orthogonal, \|QRx-b\|_2^2 = \|Rx-Q^Tb\|_2^2+\|(I-QQ^T)b\|_2^2. The second term is independent of x. Hence the least-squares minimizer satisfies Rx=Q^Tb.
Conclusion.
The displayed derivation gives the requested formula, proof, or computation. The final expression should be checked against the assumptions and notation of the corresponding chapter.
Diagnostic comment.
The formula should be verified by substitution into the defining equation and, when possible, by a small numerical test.
Exercise 7.66
Problem formulation.
Study strong rank-revealing QR and compare its theoretical guarantees with those of the SVD.
Method.
Use orthogonal projection, normal equations, QR/SVD least squares, regularization formulas, and residual orthogonality.
Detailed solution and justification.
Let A=QR, where Q has orthonormal columns. Then \|Ax-b\|_2=\|QRx-b\|_2. Decompose b=QQ^Tb+(I-QQ^T)b. Since the two parts are orthogonal, \|QRx-b\|_2^2 = \|Rx-Q^Tb\|_2^2+\|(I-QQ^T)b\|_2^2. The second term is independent of x. Hence the least-squares minimizer satisfies Rx=Q^Tb.
Conclusion.
The displayed derivation gives the requested formula, proof, or computation. The final expression should be checked against the assumptions and notation of the corresponding chapter.
Diagnostic comment.
The formula should be verified by substitution into the defining equation and, when possible, by a small numerical test.
Exercise 7.67
Problem formulation.
Prove a subspace-embedding theorem sufficient for randomized least-squares accuracy.
Method.
Use orthogonal projection, normal equations, QR/SVD least squares, regularization formulas, and residual orthogonality.
Detailed solution and justification.
The least-squares solution is characterized by residual orthogonality: r=b-Ax,\qquad A^Tr=0. Equivalently, A^TAx=A^Tb. For numerical stability, QR or SVD is preferred over explicitly forming A^TA because \kappa(A^TA)=\kappa(A)^2. Regularization replaces the problem by \min_x \|Ax-b\|_2^2+\lambda\|x\|_2^2, giving (A^TA+\lambda I)x=A^Tb.
Conclusion.
The displayed derivation gives the requested formula, proof, or computation. The final expression should be checked against the assumptions and notation of the corresponding chapter.
Diagnostic comment.
The formula should be verified by substitution into the defining equation and, when possible, by a small numerical test.
Exercise 7.68
Problem formulation.
Study randomized preconditioned least-squares solvers such as Blendenpik.
Method.
Use orthogonal projection, normal equations, QR/SVD least squares, regularization formulas, and residual orthogonality.
Detailed solution and justification.
The least-squares solution is characterized by residual orthogonality: r=b-Ax,\qquad A^Tr=0. Equivalently, A^TAx=A^Tb. For numerical stability, QR or SVD is preferred over explicitly forming A^TA because \kappa(A^TA)=\kappa(A)^2. Regularization replaces the problem by \min_x \|Ax-b\|_2^2+\lambda\|x\|_2^2, giving (A^TA+\lambda I)x=A^Tb.
Conclusion.
The displayed derivation gives the requested formula, proof, or computation. The final expression should be checked against the assumptions and notation of the corresponding chapter.
Diagnostic comment.
Distinguish forward error from backward error; a small residual does not imply a small forward error when the problem is ill-conditioned.
Exercise 7.69
Problem formulation.
Define statistical leverage scores and explain their role in randomized row sampling.
Method.
Use orthogonal projection, normal equations, QR/SVD least squares, regularization formulas, and residual orthogonality.
Detailed solution and justification.
The least-squares solution is characterized by residual orthogonality: r=b-Ax,\qquad A^Tr=0. Equivalently, A^TAx=A^Tb. For numerical stability, QR or SVD is preferred over explicitly forming A^TA because \kappa(A^TA)=\kappa(A)^2. Regularization replaces the problem by \min_x \|Ax-b\|_2^2+\lambda\|x\|_2^2, giving (A^TA+\lambda I)x=A^Tb.
Conclusion.
The displayed derivation gives the requested formula, proof, or computation. The final expression should be checked against the assumptions and notation of the corresponding chapter.
Diagnostic comment.
The formula should be verified by substitution into the defining equation and, when possible, by a small numerical test.
Exercise 7.70
Problem formulation.
Analyze early stopping of CGLS as a form of regularization.
Method.
Use orthogonal projection, normal equations, QR/SVD least squares, regularization formulas, and residual orthogonality.
Detailed solution and justification.
The least-squares solution is characterized by residual orthogonality: r=b-Ax,\qquad A^Tr=0. Equivalently, A^TAx=A^Tb. For numerical stability, QR or SVD is preferred over explicitly forming A^TA because \kappa(A^TA)=\kappa(A)^2. Regularization replaces the problem by \min_x \|Ax-b\|_2^2+\lambda\|x\|_2^2, giving (A^TA+\lambda I)x=A^Tb.
Conclusion.
The displayed derivation gives the requested formula, proof, or computation. The final expression should be checked against the assumptions and notation of the corresponding chapter.
Diagnostic comment.
The formula should be verified by substitution into the defining equation and, when possible, by a small numerical test.
Exercise 7.71
Problem formulation.
Study hybrid LSQR methods that combine Krylov projection and Tikhonov regularization.
Method.
Use orthogonal projection, normal equations, QR/SVD least squares, regularization formulas, and residual orthogonality.
Detailed solution and justification.
Let A=QR, where Q has orthonormal columns. Then \|Ax-b\|_2=\|QRx-b\|_2. Decompose b=QQ^Tb+(I-QQ^T)b. Since the two parts are orthogonal, \|QRx-b\|_2^2 = \|Rx-Q^Tb\|_2^2+\|(I-QQ^T)b\|_2^2. The second term is independent of x. Hence the least-squares minimizer satisfies Rx=Q^Tb.
Conclusion.
The displayed derivation gives the requested formula, proof, or computation. The final expression should be checked against the assumptions and notation of the corresponding chapter.
Diagnostic comment.
The formula should be verified by substitution into the defining equation and, when possible, by a small numerical test.
Exercise 7.72
Problem formulation.
Use the generalized SVD to solve general-form Tikhonov regularization.
Method.
Use orthogonal projection, normal equations, QR/SVD least squares, regularization formulas, and residual orthogonality.
Detailed solution and justification.
Let A=U\Sigma V^T. The least-squares problem becomes \min_x\|\Sigma V^Tx-U^Tb\|_2. Set z=V^Tx. Then solve \min_z\|\Sigma z-U^Tb\|_2. The minimum-norm solution is z_i= \begin{cases} (u_i^Tb)/\sigma_i, & \sigma_i>0,\\ 0, & \sigma_i=0. \end{cases} Therefore x=A^\dagger b=V\Sigma^\dagger U^Tb.
Conclusion.
The displayed derivation gives the requested formula, proof, or computation. The final expression should be checked against the assumptions and notation of the corresponding chapter.
Diagnostic comment.
The formula should be verified by substitution into the defining equation and, when possible, by a small numerical test.
Exercise 7.73
Problem formulation.
Interpret Tikhonov regularization as a Bayesian MAP estimator.
Method.
Use orthogonal projection, normal equations, QR/SVD least squares, regularization formulas, and residual orthogonality.
Detailed solution and justification.
The least-squares solution is characterized by residual orthogonality: r=b-Ax,\qquad A^Tr=0. Equivalently, A^TAx=A^Tb. For numerical stability, QR or SVD is preferred over explicitly forming A^TA because \kappa(A^TA)=\kappa(A)^2. Regularization replaces the problem by \min_x \|Ax-b\|_2^2+\lambda\|x\|_2^2, giving (A^TA+\lambda I)x=A^Tb.
Conclusion.
The displayed derivation gives the requested formula, proof, or computation. The final expression should be checked against the assumptions and notation of the corresponding chapter.
Diagnostic comment.
The formula should be verified by substitution into the defining equation and, when possible, by a small numerical test.
Exercise 7.74
Problem formulation.
Study discrete Picard conditions and their role in ill-posed least-squares problems.
Method.
Use orthogonal projection, normal equations, QR/SVD least squares, regularization formulas, and residual orthogonality.
Detailed solution and justification.
The least-squares solution is characterized by residual orthogonality: r=b-Ax,\qquad A^Tr=0. Equivalently, A^TAx=A^Tb. For numerical stability, QR or SVD is preferred over explicitly forming A^TA because \kappa(A^TA)=\kappa(A)^2. Regularization replaces the problem by \min_x \|Ax-b\|_2^2+\lambda\|x\|_2^2, giving (A^TA+\lambda I)x=A^Tb.
Conclusion.
The displayed derivation gives the requested formula, proof, or computation. The final expression should be checked against the assumptions and notation of the corresponding chapter.
Diagnostic comment.
Distinguish forward error from backward error; a small residual does not imply a small forward error when the problem is ill-conditioned.
Exercise 7.75
Problem formulation.
Analyze sensitivity of the total least-squares solution.
Method.
Use orthogonal projection, normal equations, QR/SVD least squares, regularization formulas, and residual orthogonality.
Detailed solution and justification.
The least-squares solution is characterized by residual orthogonality: r=b-Ax,\qquad A^Tr=0. Equivalently, A^TAx=A^Tb. For numerical stability, QR or SVD is preferred over explicitly forming A^TA because \kappa(A^TA)=\kappa(A)^2. Regularization replaces the problem by \min_x \|Ax-b\|_2^2+\lambda\|x\|_2^2, giving (A^TA+\lambda I)x=A^Tb.
Conclusion.
The displayed derivation gives the requested formula, proof, or computation. The final expression should be checked against the assumptions and notation of the corresponding chapter.
Diagnostic comment.
The formula should be verified by substitution into the defining equation and, when possible, by a small numerical test.
Exercise 7.76
Problem formulation.
Study least-squares problems with Toeplitz, Hankel, or Vandermonde structure.
Method.
Use orthogonal projection, normal equations, QR/SVD least squares, regularization formulas, and residual orthogonality.
Detailed solution and justification.
The least-squares solution is characterized by residual orthogonality: r=b-Ax,\qquad A^Tr=0. Equivalently, A^TAx=A^Tb. For numerical stability, QR or SVD is preferred over explicitly forming A^TA because \kappa(A^TA)=\kappa(A)^2. Regularization replaces the problem by \min_x \|Ax-b\|_2^2+\lambda\|x\|_2^2, giving (A^TA+\lambda I)x=A^Tb.
Conclusion.
The displayed derivation gives the requested formula, proof, or computation. The final expression should be checked against the assumptions and notation of the corresponding chapter.
Diagnostic comment.
The formula should be verified by substitution into the defining equation and, when possible, by a small numerical test.
Exercise 7.77
Problem formulation.
Compare QR, normal equations, and iterative methods for large sparse least-squares problems.
Method.
Use orthogonal projection, normal equations, QR/SVD least squares, regularization formulas, and residual orthogonality.
Detailed solution and justification.
Minimize \phi(x)=\frac12\|Ax-b\|_2^2. Then \phi(x)=\frac12(Ax-b)^T(Ax-b). Differentiating, \nabla\phi(x)=A^T(Ax-b). At a minimizer, A^T(Ax-b)=0. Therefore A^TAx=A^Tb. These are the normal equations. They express the orthogonality condition b-Ax\perp \operatorname{range}(A).
Conclusion.
The displayed derivation gives the requested formula, proof, or computation. The final expression should be checked against the assumptions and notation of the corresponding chapter.
Diagnostic comment.
The formula should be verified by substitution into the defining equation and, when possible, by a small numerical test.
Exercise 7.78
Problem formulation.
Study the LASSO problem \min_x\frac12\|Ax-b\|_2^2+\lambda\|x\|_1. Compare it with Tikhonov regularization.
Method.
Use orthogonal projection, normal equations, QR/SVD least squares, regularization formulas, and residual orthogonality.
Detailed solution and justification.
The least-squares solution is characterized by residual orthogonality: r=b-Ax,\qquad A^Tr=0. Equivalently, A^TAx=A^Tb. For numerical stability, QR or SVD is preferred over explicitly forming A^TA because \kappa(A^TA)=\kappa(A)^2. Regularization replaces the problem by \min_x \|Ax-b\|_2^2+\lambda\|x\|_2^2, giving (A^TA+\lambda I)x=A^Tb.
Conclusion.
The displayed derivation gives the requested formula, proof, or computation. The final expression should be checked against the assumptions and notation of the corresponding chapter.
Diagnostic comment.
The formula should be verified by substitution into the defining equation and, when possible, by a small numerical test.
Exercise 7.79
Problem formulation.
Explain how least squares, sparsity, and restricted isometry interact in compressed sensing.
Method.
Use orthogonal projection, normal equations, QR/SVD least squares, regularization formulas, and residual orthogonality.
Detailed solution and justification.
The least-squares solution is characterized by residual orthogonality: r=b-Ax,\qquad A^Tr=0. Equivalently, A^TAx=A^Tb. For numerical stability, QR or SVD is preferred over explicitly forming A^TA because \kappa(A^TA)=\kappa(A)^2. Regularization replaces the problem by \min_x \|Ax-b\|_2^2+\lambda\|x\|_2^2, giving (A^TA+\lambda I)x=A^Tb.
Conclusion.
The displayed derivation gives the requested formula, proof, or computation. The final expression should be checked against the assumptions and notation of the corresponding chapter.
Diagnostic comment.
The formula should be verified by substitution into the defining equation and, when possible, by a small numerical test.
Exercise 7.80
Problem formulation.
Design a distributed least-squares algorithm and analyze communication costs.
Method.
Use orthogonal projection, normal equations, QR/SVD least squares, regularization formulas, and residual orthogonality.
Detailed solution and justification.
The least-squares solution is characterized by residual orthogonality: r=b-Ax,\qquad A^Tr=0. Equivalently, A^TAx=A^Tb. For numerical stability, QR or SVD is preferred over explicitly forming A^TA because \kappa(A^TA)=\kappa(A)^2. Regularization replaces the problem by \min_x \|Ax-b\|_2^2+\lambda\|x\|_2^2, giving (A^TA+\lambda I)x=A^Tb.
Conclusion.
The displayed derivation gives the requested formula, proof, or computation. The final expression should be checked against the assumptions and notation of the corresponding chapter.
Diagnostic comment.
The formula should be verified by substitution into the defining equation and, when possible, by a small numerical test.
Exercise 7.81
Problem formulation.
Analyze mixed-precision QR or LSQR methods with iterative refinement.
Method.
Use orthogonal projection, normal equations, QR/SVD least squares, regularization formulas, and residual orthogonality.
Detailed solution and justification.
Let A=QR, where Q has orthonormal columns. Then \|Ax-b\|_2=\|QRx-b\|_2. Decompose b=QQ^Tb+(I-QQ^T)b. Since the two parts are orthogonal, \|QRx-b\|_2^2 = \|Rx-Q^Tb\|_2^2+\|(I-QQ^T)b\|_2^2. The second term is independent of x. Hence the least-squares minimizer satisfies Rx=Q^Tb.
Conclusion.
The displayed derivation gives the requested formula, proof, or computation. The final expression should be checked against the assumptions and notation of the corresponding chapter.
Diagnostic comment.
The formula should be verified by substitution into the defining equation and, when possible, by a small numerical test.
Exercise 7.82
Problem formulation.
Develop an interval-arithmetic certificate for a least-squares solution and residual.
Method.
Use orthogonal projection, normal equations, QR/SVD least squares, regularization formulas, and residual orthogonality.
Detailed solution and justification.
The least-squares solution is characterized by residual orthogonality: r=b-Ax,\qquad A^Tr=0. Equivalently, A^TAx=A^Tb. For numerical stability, QR or SVD is preferred over explicitly forming A^TA because \kappa(A^TA)=\kappa(A)^2. Regularization replaces the problem by \min_x \|Ax-b\|_2^2+\lambda\|x\|_2^2, giving (A^TA+\lambda I)x=A^Tb.
Conclusion.
The displayed derivation gives the requested formula, proof, or computation. The final expression should be checked against the assumptions and notation of the corresponding chapter.
Diagnostic comment.
The formula should be verified by substitution into the defining equation and, when possible, by a small numerical test.
Exercise 7.83
Problem formulation.
Formulate a nonlinear inverse problem as regularized nonlinear least squares and derive a Gauss–Newton–Tikhonov method.
Method.
Use orthogonal projection, normal equations, QR/SVD least squares, regularization formulas, and residual orthogonality.
Detailed solution and justification.
The least-squares solution is characterized by residual orthogonality: r=b-Ax,\qquad A^Tr=0. Equivalently, A^TAx=A^Tb. For numerical stability, QR or SVD is preferred over explicitly forming A^TA because \kappa(A^TA)=\kappa(A)^2. Regularization replaces the problem by \min_x \|Ax-b\|_2^2+\lambda\|x\|_2^2, giving (A^TA+\lambda I)x=A^Tb.
Conclusion.
The displayed derivation gives the requested formula, proof, or computation. The final expression should be checked against the assumptions and notation of the corresponding chapter.
Diagnostic comment.
Verify the stationarity residual, feasibility residual, and descent or curvature condition, not only the final numerical value.
Exercise 7.84
Problem formulation.
Study least-squares parameter estimation constrained by a PDE model.
Method.
Use orthogonal projection, normal equations, QR/SVD least squares, regularization formulas, and residual orthogonality.
Detailed solution and justification.
The least-squares solution is characterized by residual orthogonality: r=b-Ax,\qquad A^Tr=0. Equivalently, A^TAx=A^Tb. For numerical stability, QR or SVD is preferred over explicitly forming A^TA because \kappa(A^TA)=\kappa(A)^2. Regularization replaces the problem by \min_x \|Ax-b\|_2^2+\lambda\|x\|_2^2, giving (A^TA+\lambda I)x=A^Tb.
Conclusion.
The displayed derivation gives the requested formula, proof, or computation. The final expression should be checked against the assumptions and notation of the corresponding chapter.
Diagnostic comment.
The formula should be verified by substitution into the defining equation and, when possible, by a small numerical test.
Exercise 7.85
Problem formulation.
Discuss reproducibility and deterministic reductions in large-scale least-squares computations.
Method.
Use orthogonal projection, normal equations, QR/SVD least squares, regularization formulas, and residual orthogonality.
Detailed solution and justification.
The least-squares solution is characterized by residual orthogonality: r=b-Ax,\qquad A^Tr=0. Equivalently, A^TAx=A^Tb. For numerical stability, QR or SVD is preferred over explicitly forming A^TA because \kappa(A^TA)=\kappa(A)^2. Regularization replaces the problem by \min_x \|Ax-b\|_2^2+\lambda\|x\|_2^2, giving (A^TA+\lambda I)x=A^Tb.
Conclusion.
The displayed derivation gives the requested formula, proof, or computation. The final expression should be checked against the assumptions and notation of the corresponding chapter.
Diagnostic comment.
The formula should be verified by substitution into the defining equation and, when possible, by a small numerical test.
Interactive tools
The theory and solutions come first. These tools are for review, laboratories, games, memory cards, and randomized assessment.