Chapter 4
Direct Methods for Linear Systems
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 linear systems as algebraic and operator problems;
distinguish existence, uniqueness, conditioning, residuals, and errors;
derive Gaussian elimination and LU factorization;
understand pivoting, growth factors, and numerical stability;
prove fundamental perturbation and backward-error estimates;
derive Cholesky, LDL^T, QR, Householder, and Givens direct methods;
understand least-squares systems and the danger of normal equations;
use Schur complements, block elimination, sparse elimination, and banded solvers;
analyze iterative refinement and mixed-precision correction;
solve basic, advanced, and research-level exercises on direct solvers.
The Linear System Problem
A linear system has the form Ax=b, \qquad A\in\mathbb R^{n\times n}, \qquad b\in\mathbb R^n. When A is nonsingular, the exact solution is x=A^{-1}b. In numerical computation, however, one rarely computes A^{-1} explicitly. Instead one computes a factorization of A and solves simpler triangular or orthogonal subproblems.
Direct methods solve a linear system in a finite number of arithmetic operations in exact arithmetic. In floating-point arithmetic, the decisive questions are stability, conditioning, pivoting, and the propagation of rounding errors.
Let \widehat{x} be an approximation to the exact solution x. The error is e=x-\widehat{x}, and the residual is r=b-A\widehat{x}. They are related by Ae=r.
Let A be nonsingular. If Ax=b and r=b-A\widehat{x}, then x-\widehat{x}=A^{-1}r. Consequently, \frac{\|x-\widehat{x}\|}{\|x\|} \le \kappa(A) \frac{\|r\|}{\|b\|}, \qquad \kappa(A)=\|A\|\,\|A^{-1}\|.
Since Ax=b, r=b-A\widehat{x}=Ax-A\widehat{x}=A(x-\widehat{x}). Multiplying by A^{-1} gives x-\widehat{x}=A^{-1}r. Therefore \|x-\widehat{x}\|\le \|A^{-1}\|\,\|r\|. Also \|b\|=\|Ax\|\le \|A\|\,\|x\|. Thus \frac{1}{\|x\|}\le \frac{\|A\|}{\|b\|}. Combining the two inequalities yields \frac{\|x-\widehat{x}\|}{\|x\|} \le \|A^{-1}\|\,\|r\|\,\frac{\|A\|}{\|b\|} = \kappa(A)\frac{\|r\|}{\|b\|}.
□
The residual is a backward-error object. If A is ill-conditioned, a very small residual may still correspond to a large forward error.
Matrix Norms and Conditioning
A matrix norm is subordinate to a vector norm if \|A\|=\max_{x\ne0}\frac{\|Ax\|}{\|x\|}. Important examples are \|A\|_1=\max_j\sum_i |a_{ij}|, \|A\|_\infty=\max_i\sum_j |a_{ij}|, and \|A\|_2=\sigma_{\max}(A).
For nonsingular A, the condition number is \kappa(A)=\|A\|\,\|A^{-1}\|. In the spectral norm, \kappa_2(A)=\frac{\sigma_{\max}(A)}{\sigma_{\min}(A)}.
Let Ax=b and A(x+\Delta x)=b+\Delta b. Then \frac{\|\Delta x\|}{\|x\|} \le \kappa(A)\frac{\|\Delta b\|}{\|b\|}.
The proof is the same as the residual-error argument with r=\Delta b: A\Delta x=\Delta b, \qquad \Delta x=A^{-1}\Delta b. Then \|\Delta x\|\le \|A^{-1}\|\,\|\Delta b\|, \qquad \|b\|\le \|A\|\,\|x\|. Combining gives the estimate.
□
Let A be nonsingular, and suppose (A+\Delta A)(x+\Delta x)=b, \qquad Ax=b. If \|A^{-1}\Delta A\|<1, then A+\Delta A is nonsingular and \frac{\|\Delta x\|}{\|x\|} \le \frac{\kappa(A)\,\|\Delta A\|/\|A\|} {1-\kappa(A)\,\|\Delta A\|/\|A\|}.
From (A+\Delta A)(x+\Delta x)=Ax we obtain A\Delta x=-\Delta A(x+\Delta x). Thus \Delta x=-A^{-1}\Delta A(x+\Delta x). Taking norms, \|\Delta x\| \le \|A^{-1}\|\,\|\Delta A\|\left(\|x\|+\|\Delta x\|\right). Rearranging, \left(1-\|A^{-1}\|\,\|\Delta A\|\right)\|\Delta x\| \le \|A^{-1}\|\,\|\Delta A\|\,\|x\|. Dividing by \|x\|, and writing \|A^{-1}\|\,\|\Delta A\| = \kappa(A)\frac{\|\Delta A\|}{\|A\|}, gives the result. The nonsingularity follows from the Neumann-series argument: A+\Delta A=A(I+A^{-1}\Delta A), and I+A^{-1}\Delta A is invertible if \|A^{-1}\Delta A\|<1.
□
Triangular Systems
Triangular systems are the fundamental subproblems in direct methods.
Forward Substitution
For a lower triangular system Lx=b, with nonzero diagonal entries, forward substitution computes x_i = \frac{1}{\ell_{ii}} \left( b_i-\sum_{j=1}^{i-1}\ell_{ij}x_j \right), \qquad i=1,\ldots,n.
Caption.
Forward substitution
lower triangular L, right-hand side b
For i=1,\ldots,n:
s\gets b_i
For j=1,\ldots,i-1:
s\gets s-\ell_{ij}x_j
x_i\gets s/\ell_{ii}
Return x
Back Substitution
For an upper triangular system Ux=b, back substitution computes x_i = \frac{1}{u_{ii}} \left( b_i-\sum_{j=i+1}^{n}u_{ij}x_j \right), \qquad i=n,n-1,\ldots,1.
Caption.
Back substitution
upper triangular U, right-hand side b
For i=n,n-1,\ldots,1:
s\gets b_i
For j=i+1,\ldots,n:
s\gets s-u_{ij}x_j
x_i\gets s/u_{ii}
Return x
Solving a dense triangular n\times n system by forward or backward substitution requires \frac{n(n-1)}{2} multiplications, the same number of additions/subtractions, and n divisions. Thus the cost is O(n^2).
For row i in forward substitution, the inner sum has i-1 terms. Therefore the number of multiplication-subtraction pairs is \sum_{i=1}^n(i-1)=\frac{n(n-1)}2. There is one division per row.
□
Let \widehat{x} be computed by floating-point triangular substitution for Tx=b, where T is triangular. Under the standard model and no overflow or underflow, there exists a triangular perturbation \Delta T such that (T+\Delta T)\widehat{x}=b, and componentwise |\Delta T|\le \gamma_n |T|, up to harmless row-dependent constants.
Each computed row equation has the form \widehat{s}_i = b_i-\sum_j t_{ij}\widehat{x}_j with the dot-product summation affected by a componentwise relative perturbation bounded by a \gamma-factor. Therefore the computed equality can be written as b_i=\sum_j (t_{ij}+\Delta t_{ij})\widehat{x}_j with |\Delta t_{ij}|\le \gamma_n |t_{ij}|. Assembling these row equations gives (T+\Delta T)\widehat{x}=b. The perturbation has the same triangular sparsity pattern because only entries present in the triangular solve participate in the row equations.
□
Gaussian Elimination
Gaussian elimination transforms A into an upper triangular matrix by eliminating entries below the diagonal. At step k, for i>k, \ell_{ik}=\frac{a_{ik}^{(k)}}{a_{kk}^{(k)}}, and the row update is a_{ij}^{(k+1)} = a_{ij}^{(k)}-\ell_{ik}a_{kj}^{(k)}, \qquad j=k,\ldots,n.
Caption.
Gaussian elimination without pivoting
A\in\mathbb R^{n\times n}, b\in\mathbb R^n
For k=1,\ldots,n-1:
For i=k+1,\ldots,n:
\ell_{ik}\gets a_{ik}/a_{kk}
For j=k,\ldots,n:
a_{ij}\gets a_{ij}-\ell_{ik}a_{kj}
b_i\gets b_i-\ell_{ik}b_k
Solve the resulting upper triangular system by back substitution
Suppose Gaussian elimination can be performed without encountering a zero pivot. Then A=LU, where L is unit lower triangular and U is upper triangular.
Each elimination step subtracts multiples of the pivot row from lower rows. This is equivalent to left multiplication by a unit lower triangular elimination matrix E_k. After n-1 steps, E_{n-1}\cdots E_1A=U. Therefore A=E_1^{-1}\cdots E_{n-1}^{-1}U. The product L=E_1^{-1}\cdots E_{n-1}^{-1} is unit lower triangular, with entries equal to the elimination multipliers.
□
Dense Gaussian elimination requires \frac{2}{3}n^3+O(n^2) floating-point operations. The subsequent triangular solve costs O(n^2).
At step k, the trailing update has approximately (n-k)^2 multiplication-subtraction pairs. Counting each pair as two floating-point operations, the leading cost is 2\sum_{k=1}^{n-1}(n-k)^2 = 2\sum_{m=1}^{n-1}m^2 = 2\frac{(n-1)n(2n-1)}{6} = \frac{2}{3}n^3+O(n^2).
□
LU Factorization and Solving
Once A=LU, the system Ax=b is solved by two triangular systems: Ly=b, \qquad Ux=y.
Caption.
Solve by LU factorization
factorization A=LU, right-hand side b
Solve Ly=b by forward substitution
Solve Ux=y by back substitution
Return x
If the same matrix A is used with many right-hand sides b^{(1)},\ldots,b^{(m)}, the factorization is computed once. Each new solve then costs only O(n^2), not O(n^3).
Pivoting
Gaussian elimination without pivoting can fail or be unstable. Pivoting exchanges rows and/or columns to choose better pivots.
Partial Pivoting
Partial pivoting chooses the largest entry in the current pivot column: |a_{pk}^{(k)}| = \max_{i\ge k}|a_{ik}^{(k)}|. Rows p and k are interchanged. The resulting factorization is PA=LU, where P is a permutation matrix.
Caption.
Gaussian elimination with partial pivoting
A\in\mathbb R^{n\times n}
P\gets I
For k=1,\ldots,n-1:
p\gets \arg\max_{i=k,\ldots,n}|a_{ik}|
If a_{pk}=0:
stop: matrix is singular
Swap rows k and p in A, P, and previous columns of L
For i=k+1,\ldots,n:
\ell_{ik}\gets a_{ik}/a_{kk}
For j=k+1,\ldots,n:
a_{ij}\gets a_{ij}-\ell_{ik}a_{kj}
Return P,L,U
In Gaussian elimination with partial pivoting, |\ell_{ik}|\le 1 for every multiplier.
At step k, partial pivoting chooses a pivot satisfying |a_{kk}^{(k)}|=\max_{i\ge k}|a_{ik}^{(k)}|. For i>k, \ell_{ik}=\frac{a_{ik}^{(k)}}{a_{kk}^{(k)}}. Therefore |\ell_{ik}|\le1.
□
Growth Factor
The element growth factor for Gaussian elimination is \rho_n = \frac{\max_{i,j,k}|a_{ij}^{(k)}|} {\max_{i,j}|a_{ij}|}. It measures the largest intermediate element relative to the largest original element.
Partial pivoting keeps multipliers bounded by one, but it does not prevent all element growth. Large growth factors can cause large backward-error constants.
Let \widehat{x} be the computed solution obtained by Gaussian elimination with partial pivoting. Under the standard floating-point model, the computed solution is the exact solution of a nearby system (A+\Delta A)\widehat{x}=b, where, in normwise form, \frac{\|\Delta A\|}{\|A\|} \le C_n\,\rho_n\,u+O(u^2), with C_n a modest polynomial in n and \rho_n the growth factor.
Each elimination update has the form a_{ij}\leftarrow a_{ij}-\ell_{ik}a_{kj}. In floating-point arithmetic, each multiply-subtract introduces local relative errors. Accumulating these errors over the elimination process yields a perturbation whose size is proportional to the largest intermediate element. That largest element is measured by \rho_n\|A\|. After collecting all local perturbations into a single matrix perturbation, one obtains (A+\Delta A)=\widehat{L}\widehat{U} up to the row permutation, and \|\Delta A\| \le C_n\rho_n u\|A\|+O(u^2). The triangular solve contributes additional terms of the same first-order type.
□
Complete Pivoting, Rook Pivoting, and Scaling
Complete pivoting searches the full trailing submatrix: |a_{pq}^{(k)}| = \max_{i,j\ge k}|a_{ij}^{(k)}|. It produces PAQ=LU. Complete pivoting controls growth more aggressively than partial pivoting, but costs more comparisons and changes both row and column ordering.
Rook pivoting alternates row and column searches until the selected pivot is largest in both its row and column. It is often used in symmetric indefinite factorizations.
Equilibration or scaling seeks diagonal matrices D_r,D_c such that D_rAD_c has better row and column scaling. Scaling can reduce element growth and improve componentwise accuracy, although it does not change the exact solution problem in a trivial way.
Cholesky Factorization
If A is symmetric positive definite, one can write A=LL^T, where L is lower triangular with positive diagonal entries.
If A\in\mathbb R^{n\times n} is symmetric positive definite, then there exists a unique lower triangular matrix L with positive diagonal entries such that A=LL^T.
We prove by induction. For n=1, A=[a_{11}] with a_{11}>0, so L=[\sqrt{a_{11}}].
Partition A= \begin{pmatrix} \alpha & r^T\\ r & B \end{pmatrix}, \qquad \alpha>0. Set \ell_{11}=\sqrt{\alpha}, \qquad \ell=\frac{r}{\ell_{11}}. Then the Schur complement is S=B-\ell\ell^T = B-\frac{rr^T}{\alpha}. Since A is positive definite, S is positive definite. By induction, S=\widetilde{L}\widetilde{L}^T. Therefore L= \begin{pmatrix} \ell_{11} & 0\\ \ell & \widetilde{L} \end{pmatrix} satisfies A=LL^T. Positivity of the diagonal gives uniqueness from the recursive construction.
□
Caption.
Cholesky factorization
symmetric positive definite matrix A
For j=1,\ldots,n:
\ell_{jj}\gets \sqrt{a_{jj}-\sum_{k=1}^{j-1}\ell_{jk}^2}
For i=j+1,\ldots,n:
\ell_{ij}\gets \left(a_{ij}-\sum_{k=1}^{j-1}\ell_{ik}\ell_{jk}\right)/\ell_{jj}
Return L
Dense Cholesky factorization costs \frac13 n^3+O(n^2) floating-point operations, approximately half the leading cost of Gaussian elimination.
Cholesky updates only one triangular half of the matrix and uses symmetry. Counting the inner products in the lower triangular part gives the leading sum \sum_{j=1}^n (n-j)^2 = \frac13n^3+O(n^2).
□
If Cholesky factorization is computed in floating-point arithmetic for a symmetric positive definite matrix A, then the computed factor \widehat{L} satisfies \widehat{L}\widehat{L}^T=A+\Delta A, where \|\Delta A\|\le C_nu\|A\|+O(u^2) for a modest dimension-dependent constant C_n.
Each computed inner product in the Cholesky recursion is backward stable, and the square-root operation is correctly rounded under the standard model. The local rounding errors can be collected into perturbations of the entries of A. Since the algorithm updates symmetric Schur complements and no pivot growth analogous to general Gaussian elimination occurs for positive definite matrices, the accumulated perturbation satisfies a normwise bound of the stated form.
□
LDL^T Factorization
For symmetric matrices, one often uses A=LDL^T, where L is unit lower triangular and D is diagonal or block diagonal. For symmetric positive definite matrices, D is diagonal with positive entries. For symmetric indefinite matrices, stable factorization may require pivoting and 1\times1 or 2\times2 diagonal blocks.
The LDL^T form avoids square roots and is natural for symmetric indefinite problems. With appropriate pivoting, it is the foundation of robust symmetric direct solvers.
Schur Complements and Block Elimination
Partition A= \begin{pmatrix} A_{11} & A_{12}\\ A_{21} & A_{22} \end{pmatrix}, where A_{11} is nonsingular. The Schur complement of A_{11} in A is S=A_{22}-A_{21}A_{11}^{-1}A_{12}.
If A_{11} is nonsingular, then A = \begin{pmatrix} I & 0\\ A_{21}A_{11}^{-1} & I \end{pmatrix} \begin{pmatrix} A_{11} & A_{12}\\ 0 & S \end{pmatrix}, where S=A_{22}-A_{21}A_{11}^{-1}A_{12}.
Multiplying the two block matrices gives \begin{pmatrix} A_{11} & A_{12}\\ A_{21} & A_{21}A_{11}^{-1}A_{12}+S \end{pmatrix}. Substituting the definition of S yields A.
□
Let A= \begin{pmatrix} A_{11} & A_{12}\\ A_{12}^T & A_{22} \end{pmatrix} be symmetric with A_{11} symmetric positive definite. Then A is symmetric positive definite if and only if the Schur complement S=A_{22}-A_{12}^TA_{11}^{-1}A_{12} is symmetric positive definite.
Using the block factorization, A = \begin{pmatrix} I & 0\\ A_{12}^TA_{11}^{-1} & I \end{pmatrix} \begin{pmatrix} A_{11} & 0\\ 0 & S \end{pmatrix} \begin{pmatrix} I & A_{11}^{-1}A_{12}\\ 0 & I \end{pmatrix}. The outer factors are nonsingular and transpose to each other. Therefore the quadratic form associated with A is positive for all nonzero vectors if and only if the block diagonal matrix with blocks A_{11} and S is positive definite. Since A_{11} is positive definite, this is equivalent to S being positive definite.
□
QR Factorization
A QR factorization has the form A=QR, where Q has orthonormal columns and R is upper triangular. For square nonsingular A, Q\in\mathbb R^{n\times n} is orthogonal.
Householder QR
A Householder reflector has the form H=I-2vv^T, \qquad \|v\|_2=1. It is orthogonal and symmetric: H^T=H, \qquad H^TH=I.
Let H=I-2vv^T, where \|v\|_2=1. Then H is symmetric, orthogonal, and reflects vectors across the hyperplane orthogonal to v.
Symmetry is immediate: H^T=I-2vv^T=H. Also, H^TH=H^2=(I-2vv^T)^2=I-4vv^T+4v(v^Tv)v^T=I. Thus H is orthogonal. Finally, Hv=v-2v(v^Tv)=-v, while if w^Tv=0, then Hw=w. Hence H reflects in the hyperplane orthogonal to v.
□
Caption.
Householder QR factorization
A\in\mathbb R^{m\times n}, m\ge n
For k=1,\ldots,n:
Choose Householder vector v_k to zero entries k+1,\ldots,m in column k
Apply H_k=I-2v_kv_k^T to the trailing matrix
Return Q=H_1H_2\cdots H_n, R=Q^TA
Householder QR factorization is backward stable. The computed factors \widehat{Q} and \widehat{R} satisfy A+\Delta A=\widehat{Q}\widehat{R}, where \|\Delta A\|\le C_{m,n}u\|A\|+O(u^2), and \widehat{Q} is nearly orthogonal.
Each Householder transformation is applied by stable inner products and axpy-type updates. Since Householder reflectors are orthogonal, they do not amplify the norm of the transformed matrix in exact arithmetic. The local rounding errors from each orthogonal transformation can be collected into a backward perturbation of the input matrix. Accumulating over n reflectors yields the stated normwise perturbation bound.
□
Givens Rotations
A Givens rotation acts on two coordinates: G= \begin{pmatrix} c & s\\ -s & c \end{pmatrix}, \qquad c^2+s^2=1. It is used to zero selected entries and is especially useful for sparse matrices.
Least-Squares Problems
For A\in\mathbb R^{m\times n}, m\ge n, the least-squares problem is \min_x \|Ax-b\|_2. The normal equations are A^TAx=A^Tb.
A vector x_\ast solves \min_x \|Ax-b\|_2 if and only if A^T(Ax_\ast-b)=0. Equivalently, A^TAx_\ast=A^Tb.
Let \phi(x)=\frac12\|Ax-b\|_2^2. Then \nabla \phi(x)=A^T(Ax-b). At a minimizer, the gradient vanishes, giving A^T(Ax_\ast-b)=0. Conversely, since \phi is convex quadratic, any stationary point is a global minimizer.
□
If A has full column rank, then \kappa_2(A^TA)=\kappa_2(A)^2. Thus solving least-squares problems through normal equations can lose significant accuracy when A is ill-conditioned.
If A has full column rank, then \kappa_2(A^TA)=\kappa_2(A)^2.
The singular values of A^TA are the squares of the singular values of A. Hence \kappa_2(A^TA) = \frac{\sigma_{\max}(A)^2}{\sigma_{\min}(A)^2} = \left(\frac{\sigma_{\max}(A)}{\sigma_{\min}(A)}\right)^2 = \kappa_2(A)^2.
□
Rank-Revealing Factorizations and the SVD
If A is rank deficient or nearly rank deficient, ordinary LU or QR may hide the numerical rank. The singular value decomposition is A=U\Sigma V^T. The best rank-k approximation in the spectral norm is obtained by truncating the SVD.
Let A=U\Sigma V^T be the singular value decomposition, with singular values \sigma_1\ge\sigma_2\ge\cdots\ge0. Then the best rank-k approximation to A in the spectral norm is A_k=U_k\Sigma_kV_k^T, and \|A-A_k\|_2=\sigma_{k+1}.
The truncated SVD satisfies A-A_k=\sum_{j>k}\sigma_j u_jv_j^T, so \|A-A_k\|_2=\sigma_{k+1}. For any rank-k matrix B, there exists a unit vector z in the span of the first k+1 right singular vectors of A such that Bz=0. Hence \|A-B\|_2\ge \|(A-B)z\|_2=\|Az\|_2\ge \sigma_{k+1}. Thus no rank-k matrix can do better.
□
Banded and Sparse Direct Methods
A matrix is banded with lower bandwidth p and upper bandwidth q if a_{ij}=0 \qquad \text{whenever } i-j>p \text{ or } j-i>q. Banded Gaussian elimination preserves bandwidth under suitable pivoting restrictions and can reduce cost dramatically.
Sparse direct methods exploit zeros. However, elimination can create new nonzero entries, called fill-in.
The numerical factorization is only half the problem. The symbolic phase chooses an ordering that reduces fill-in. Good ordering can be the difference between a feasible and an impossible computation.
Common orderings include: \text{minimum degree},\qquad \text{nested dissection},\qquad \text{approximate minimum degree}.
Rank-One Updates: Sherman–Morrison and Woodbury
If a factorization or inverse information for A is known, one may want to solve a modified system involving a low-rank update.
Let A be nonsingular and let u,v\in\mathbb R^n. If 1+v^TA^{-1}u\ne0, then (A+uv^T)^{-1} = A^{-1} - \frac{A^{-1}uv^TA^{-1}}{1+v^TA^{-1}u}.
Let B=A^{-1} - \frac{A^{-1}uv^TA^{-1}}{1+v^TA^{-1}u}. Then (A+uv^T)B = I+uv^TA^{-1} - \frac{u v^TA^{-1}}{1+v^TA^{-1}u} - \frac{u(v^TA^{-1}u)v^TA^{-1}}{1+v^TA^{-1}u}. The last two terms combine as -\frac{u v^TA^{-1}(1+v^TA^{-1}u)}{1+v^TA^{-1}u} = -u v^TA^{-1}. Thus (A+uv^T)B=I.
□
Let A and C be nonsingular. Then (A+UCV^T)^{-1} = A^{-1} - A^{-1}U \left(C^{-1}+V^TA^{-1}U\right)^{-1} V^TA^{-1}, provided the middle inverse exists.
The result follows by multiplying the proposed inverse by A+UCV^T and simplifying, or by applying block Gaussian elimination to an augmented block matrix.
□
Iterative Refinement
Given an approximate solution x_k, compute the residual r_k=b-Ax_k, solve the correction equation Ad_k=r_k, and update x_{k+1}=x_k+d_k.
Caption.
Iterative refinement
factorization of A, initial solution x_0
For k=0,1,2,\ldots:
Compute residual r_k=b-Ax_k, preferably in higher precision
Solve Ad_k=r_k using the existing factors
x_{k+1}\gets x_k+d_k
If \|r_k\| and \|d_k\| are sufficiently small:
Return x_{k+1}
Assume the correction solve applies an approximate inverse A^{-1}+\Delta, \qquad \|\Delta\|\le C u_\ell\|A^{-1}\|, and that residuals are computed in a higher precision with unit roundoff u_h. Then the error e_k=x-x_k satisfies a model recurrence \|e_{k+1}\| \le C u_\ell\kappa(A)\|e_k\| + O(u_h)\|x\|. Thus refinement converges if C u_\ell\kappa(A)<1.
In exact arithmetic, r_k=b-Ax_k=A(x-x_k)=Ae_k, and the exact correction is d_k=e_k. If the correction solve uses A^{-1}+\Delta, then d_k=(A^{-1}+\Delta)r_k = e_k+\Delta A e_k. The update gives e_{k+1}=x-(x_k+d_k) = -\Delta A e_k, plus residual-computation error of size O(u_h)\|x\|. Therefore \|e_{k+1}\| \le \|\Delta\|\,\|A\|\,\|e_k\|+O(u_h)\|x\| \le C u_\ell\kappa(A)\|e_k\|+O(u_h)\|x\|.
□
Componentwise Backward Error
Normwise backward error may hide scaling information. For a computed solution \widehat{x}, define the componentwise backward error \omega(\widehat{x}) = \max_i \frac{|r_i|} {(|A|\,|\widehat{x}|+|b|)_i}, \qquad r=b-A\widehat{x}. This is the smallest relative componentwise perturbation size, in a natural sense, that makes \widehat{x} the exact solution of a nearby system.
Normwise bounds are elegant and general. Componentwise bounds are often more informative for scaled, sparse, or structured problems. Modern direct solvers often report both residual norms and componentwise backward errors.
Practical Comparison of Direct Methods
- General dense A.
-
Use LU factorization with partial pivoting: PA=LU. This is the standard dense direct solver for general nonsingular matrices.
- Symmetric positive definite A.
-
Use Cholesky: A=LL^T. It is faster than LU, needs about half the storage, and is backward stable.
- Symmetric indefinite A.
-
Use pivoted LDL^T factorization with 1\times1 and 2\times2 pivots.
- Least-squares problem.
-
Prefer Householder QR or SVD. Avoid normal equations when \kappa(A) is large, because A^TA squares the condition number.
- Rank-deficient or nearly rank-deficient problem.
-
Use SVD or a rank-revealing QR factorization.
- Banded matrix.
-
Use a banded factorization that preserves bandwidth.
- Sparse matrix.
-
Use sparse direct solvers with symbolic reordering to reduce fill-in.
- Many right-hand sides.
-
Compute a factorization once and reuse it for triangular solves.
- Low precision factorization.
-
Use iterative refinement, preferably with residuals computed in higher precision.
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 linear algebra. Problems marked \star, \star\star, and \star\star\star are progressively harder.
Basic problems
Let Ax=b be nonsingular and let r=b-A\widehat{x}. Prove that x-\widehat{x}=A^{-1}r.
Compute \kappa_2(A) for A=\begin{pmatrix}1&0\\0&\varepsilon\end{pmatrix}, \qquad 0<\varepsilon<1.
Compute \|A\|_1, \|A\|_\infty, and \|A\|_2 for A=\begin{pmatrix}1&2\\0&3\end{pmatrix}.
Solve \begin{pmatrix} 2&0&0\\ 1&1&0\\ -1&2&1 \end{pmatrix} x= \begin{pmatrix} 2\\3\\4 \end{pmatrix} by forward substitution.
Solve \begin{pmatrix} 1&2&1\\ 0&3&-1\\ 0&0&2 \end{pmatrix} x= \begin{pmatrix} 4\\5\\6 \end{pmatrix} by back substitution.
Find an LU factorization without pivoting for A=\begin{pmatrix} 2&1\\ 4&5 \end{pmatrix}.
Given L=\begin{pmatrix}1&0\\2&1\end{pmatrix}, \qquad U=\begin{pmatrix}3&1\\0&4\end{pmatrix}, solve LUx=b for b=(1,2)^T.
Explain why Gaussian elimination without pivoting fails for A=\begin{pmatrix} 0&1\\ 1&1 \end{pmatrix}.
Perform one step of partial pivoting for A=\begin{pmatrix} 10^{-6}&1\\ 1&1 \end{pmatrix}.
Compute the Cholesky factorization of A=\begin{pmatrix} 4&2\\ 2&3 \end{pmatrix}.
Use leading principal minors to determine whether A=\begin{pmatrix} 2&-1\\ -1&2 \end{pmatrix} is symmetric positive definite.
Compute a QR factorization of A=\begin{pmatrix} 1&1\\ 0&1\\ 0&0 \end{pmatrix} using classical Gram–Schmidt.
Let v=(1,0)^T. Compute H=I-2vv^T. Show that H is orthogonal.
Find c and s such that \begin{pmatrix}c&s\\-s&c\end{pmatrix} \begin{pmatrix}3\\4\end{pmatrix} = \begin{pmatrix}5\\0\end{pmatrix}.
Derive the normal equations for \min_x\|Ax-b\|_2.
If \kappa_2(A)=10^4, what is \kappa_2(A^TA)?
Compute the Schur complement of A_{11} in A=\begin{pmatrix} 2&1\\ 3&5 \end{pmatrix}.
State the Sherman–Morrison formula and explain when it is valid.
Describe one step of iterative refinement for Ax=b.
Explain what fill-in means in sparse Gaussian elimination.
Intermediate problems \star
Prove the relative residual-error bound in the referenced result.
Prove the referenced result.
Prove the referenced result.
Fill in the details of the referenced result.
Prove the referenced result.
Assume A=LU=\widetilde{L}\widetilde{U}, where L,\widetilde{L} are unit lower triangular and U,\widetilde{U} are upper triangular. Prove uniqueness when the factorization exists.
Show that LU factorization without pivoting exists if all leading principal minors of A are nonzero.
Prove the referenced result.
Prove that partial pivoting gives |\ell_{ik}|\le1.
Show that permutation matrices are orthogonal: P^TP=I.
Construct a small matrix for which Gaussian elimination without pivoting produces large intermediate entries.
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.
Advanced problems \star\star
Give a detailed derivation of the referenced result, carefully tracking the role of the growth factor.
Construct the classical Wilkinson-type matrix for which partial pivoting exhibits growth factor 2^{n-1}.
Compare partial pivoting and complete pivoting. Prove that complete pivoting controls the pivot choice more strongly and discuss its additional cost.
Describe rook pivoting and explain why it is useful in symmetric indefinite factorization.
Derive the componentwise backward error formula \omega(\widehat{x}) = \max_i \frac{|r_i|} {(|A|\,|\widehat{x}|+|b|)_i}.
Give a detailed proof of backward stability for Cholesky factorization.
Give an example of a symmetric matrix that is not positive definite and explain why Cholesky factorization breaks down.
Explain why 2\times2 pivots are needed in stable symmetric indefinite factorization.
Prove the referenced result in more detail.
Compare classical and modified Gram–Schmidt. Explain why modified Gram–Schmidt is usually more stable.
Compare the forward accuracy of solving least-squares problems by Householder QR and by normal equations.
Derive the least-squares solution using the singular value decomposition.
Prove the referenced result.
Explain the purpose of rank-revealing QR factorization and compare it with the SVD.
Derive block Gaussian elimination and express it in terms of Schur complements.
Prove the Woodbury formula.
Estimate the cost of LU factorization for a matrix with fixed lower and upper bandwidth.
Explain fill-in using the graph of a sparse symmetric matrix.
Describe nested dissection ordering and explain why it reduces fill-in for grid-like problems.
Analyze iterative refinement when the factorization is computed in low precision and the residual in high precision.
Discuss diagonal scaling D_rAD_c. Give an example where scaling improves componentwise behavior.
Show how to compute \det(A) from PA=LU, including the sign of the permutation.
Explain how to compute A^{-1} using an LU factorization. Why is solving systems usually preferable to forming A^{-1}?
Design a practical error estimator for Ax=b based on the residual, an estimate of \|A^{-1}\|, and componentwise backward error.
Investigate how row scaling can affect pivot choices and growth factors in partial pivoting.
Research-level problems \star\star\star
State and prove a rigorous Wilkinson backward-error theorem for Gaussian elimination with partial pivoting.
Study why large growth factors are rare in practice for random matrices, despite exponential worst-case examples.
State a strong rank-revealing QR theorem and compare its guarantees with those of the SVD.
Study communication-avoiding LU factorization. Explain how reducing communication can be as important as reducing arithmetic.
Derive a blocked LU or Cholesky algorithm and explain why matrix-matrix updates are preferred on modern architectures.
Define the elimination tree of a sparse Cholesky factorization and explain how it organizes parallel computation.
Study the multifrontal method for sparse direct factorization and explain the role of frontal matrices.
Explain supernodal sparse factorization and why dense linear algebra kernels improve performance.
Analyze the tradeoff between sparsity preservation and numerical stability in sparse pivoting strategies.
Study direct solvers for Toeplitz, Hankel, Cauchy, or Vandermonde matrices. Compare fast algorithms with stability issues.
Investigate hierarchical low-rank direct solvers such as HSS or HODLR methods. Explain when off-diagonal low rank appears.
Explain how Sherman–Morrison–Woodbury formulas arise in quasi-Newton optimization and constrained least-squares problems.
Design an interval-arithmetic verification procedure for certifying that a computed \widehat{x} encloses the exact solution of Ax=b.
Develop a componentwise perturbation theory for Ax=b and compare it with normwise condition-number bounds.
Study smoothed analysis results explaining why Gaussian elimination with partial pivoting is reliable in practice.
Analyze the use of FP16, BF16, TF32, FP32, and FP64 in mixed-precision direct solvers with iterative refinement.
Discuss reproducibility issues in parallel direct solvers and propose strategies for bitwise reproducible factorizations.
Compare numerical pivoting with fraction-free Gaussian elimination over exact arithmetic domains.
Study block direct solvers for saddle-point systems \begin{pmatrix} A & B^T\\ B & 0 \end{pmatrix} \begin{pmatrix} x\\y \end{pmatrix} = \begin{pmatrix} f\\g \end{pmatrix}. Analyze Schur complement strategies.
Explain how sparse Cholesky or multifrontal solvers are used in finite element discretizations of elliptic PDEs. Analyze fill-in and ordering.
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 4. Each solution includes the problem formulation, the method, the mathematical derivation, the conclusion, and a diagnostic comment.
Exercise 4.1
Problem formulation.
Let Ax=b be nonsingular and let r=b-A\widehat{x}. Prove that x-\widehat{x}=A^{-1}r.
Method.
Use matrix factorization, triangular substitution, pivoting, Schur complements, QR/SVD, and backward-error analysis.
Detailed solution and justification.
The computation is based on rewriting the linear system in a form that can be solved by triangular substitutions or orthogonal transformations. If a factorization A=LU,\quad A=QR,\quad \text{or}\quad A=LL^T is available, the original problem is reduced to simpler subproblems. The residual of a computed solution \widetilde x is r=b-A\widetilde x. A small backward error means that \widetilde x solves a nearby problem. The forward error is bounded in terms of the condition number: \frac{\|x-\widetilde x\|}{\|x\|} \lesssim \kappa(A)\frac{\|r\|}{\|b\|}.
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 4.2
Problem formulation.
Compute \kappa_2(A) for A=\begin{pmatrix}1&0\\0&\varepsilon\end{pmatrix}, \qquad 0<\varepsilon<1.
Method.
Use matrix factorization, triangular substitution, pivoting, Schur complements, QR/SVD, and backward-error analysis.
Detailed solution and justification.
The computation is based on rewriting the linear system in a form that can be solved by triangular substitutions or orthogonal transformations. If a factorization A=LU,\quad A=QR,\quad \text{or}\quad A=LL^T is available, the original problem is reduced to simpler subproblems. The residual of a computed solution \widetilde x is r=b-A\widetilde x. A small backward error means that \widetilde x solves a nearby problem. The forward error is bounded in terms of the condition number: \frac{\|x-\widetilde x\|}{\|x\|} \lesssim \kappa(A)\frac{\|r\|}{\|b\|}.
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 4.3
Problem formulation.
Compute \|A\|_1, \|A\|_\infty, and \|A\|_2 for A=\begin{pmatrix}1&2\\0&3\end{pmatrix}.
Method.
Use matrix factorization, triangular substitution, pivoting, Schur complements, QR/SVD, and backward-error analysis.
Detailed solution and justification.
The computation is based on rewriting the linear system in a form that can be solved by triangular substitutions or orthogonal transformations. If a factorization A=LU,\quad A=QR,\quad \text{or}\quad A=LL^T is available, the original problem is reduced to simpler subproblems. The residual of a computed solution \widetilde x is r=b-A\widetilde x. A small backward error means that \widetilde x solves a nearby problem. The forward error is bounded in terms of the condition number: \frac{\|x-\widetilde x\|}{\|x\|} \lesssim \kappa(A)\frac{\|r\|}{\|b\|}.
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 4.4
Problem formulation.
Solve \begin{pmatrix} 2&0&0\\ 1&1&0\\ -1&2&1 \end{pmatrix} x= \begin{pmatrix} 2\\3\\4 \end{pmatrix} by forward substitution.
Method.
Use matrix factorization, triangular substitution, pivoting, Schur complements, QR/SVD, and backward-error analysis.
Detailed solution and justification.
The computation is based on rewriting the linear system in a form that can be solved by triangular substitutions or orthogonal transformations. If a factorization A=LU,\quad A=QR,\quad \text{or}\quad A=LL^T is available, the original problem is reduced to simpler subproblems. The residual of a computed solution \widetilde x is r=b-A\widetilde x. A small backward error means that \widetilde x solves a nearby problem. The forward error is bounded in terms of the condition number: \frac{\|x-\widetilde x\|}{\|x\|} \lesssim \kappa(A)\frac{\|r\|}{\|b\|}.
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 4.5
Problem formulation.
Solve \begin{pmatrix} 1&2&1\\ 0&3&-1\\ 0&0&2 \end{pmatrix} x= \begin{pmatrix} 4\\5\\6 \end{pmatrix} by back substitution.
Method.
Use matrix factorization, triangular substitution, pivoting, Schur complements, QR/SVD, and backward-error analysis.
Detailed solution and justification.
The computation is based on rewriting the linear system in a form that can be solved by triangular substitutions or orthogonal transformations. If a factorization A=LU,\quad A=QR,\quad \text{or}\quad A=LL^T is available, the original problem is reduced to simpler subproblems. The residual of a computed solution \widetilde x is r=b-A\widetilde x. A small backward error means that \widetilde x solves a nearby problem. The forward error is bounded in terms of the condition number: \frac{\|x-\widetilde x\|}{\|x\|} \lesssim \kappa(A)\frac{\|r\|}{\|b\|}.
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 4.6
Problem formulation.
Find an LU factorization without pivoting for A=\begin{pmatrix} 2&1\\ 4&5 \end{pmatrix}.
Method.
Use matrix factorization, triangular substitution, pivoting, Schur complements, QR/SVD, and backward-error analysis.
Detailed solution and justification.
Assume A=LU, where L is lower triangular and U is upper triangular. To solve Ax=b, write LUx=b. Set Ux=y. Then solve the two triangular systems Ly=b, \qquad Ux=y. Forward substitution computes y, and backward substitution computes x. If pivoting is required, use PA=LU, so the first system becomes Ly=Pb.
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 4.7
Problem formulation.
Given L=\begin{pmatrix}1&0\\2&1\end{pmatrix}, \qquad U=\begin{pmatrix}3&1\\0&4\end{pmatrix}, solve LUx=b for b=(1,2)^T.
Method.
Use matrix factorization, triangular substitution, pivoting, Schur complements, QR/SVD, and backward-error analysis.
Detailed solution and justification.
Assume A=LU, where L is lower triangular and U is upper triangular. To solve Ax=b, write LUx=b. Set Ux=y. Then solve the two triangular systems Ly=b, \qquad Ux=y. Forward substitution computes y, and backward substitution computes x. If pivoting is required, use PA=LU, so the first system becomes Ly=Pb.
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 4.8
Problem formulation.
Explain why Gaussian elimination without pivoting fails for A=\begin{pmatrix} 0&1\\ 1&1 \end{pmatrix}.
Method.
Use matrix factorization, triangular substitution, pivoting, Schur complements, QR/SVD, and backward-error analysis.
Detailed solution and justification.
The computation is based on rewriting the linear system in a form that can be solved by triangular substitutions or orthogonal transformations. If a factorization A=LU,\quad A=QR,\quad \text{or}\quad A=LL^T is available, the original problem is reduced to simpler subproblems. The residual of a computed solution \widetilde x is r=b-A\widetilde x. A small backward error means that \widetilde x solves a nearby problem. The forward error is bounded in terms of the condition number: \frac{\|x-\widetilde x\|}{\|x\|} \lesssim \kappa(A)\frac{\|r\|}{\|b\|}.
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 4.9
Problem formulation.
Perform one step of partial pivoting for A=\begin{pmatrix} 10^{-6}&1\\ 1&1 \end{pmatrix}.
Method.
Use matrix factorization, triangular substitution, pivoting, Schur complements, QR/SVD, and backward-error analysis.
Detailed solution and justification.
The computation is based on rewriting the linear system in a form that can be solved by triangular substitutions or orthogonal transformations. If a factorization A=LU,\quad A=QR,\quad \text{or}\quad A=LL^T is available, the original problem is reduced to simpler subproblems. The residual of a computed solution \widetilde x is r=b-A\widetilde x. A small backward error means that \widetilde x solves a nearby problem. The forward error is bounded in terms of the condition number: \frac{\|x-\widetilde x\|}{\|x\|} \lesssim \kappa(A)\frac{\|r\|}{\|b\|}.
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 4.10
Problem formulation.
Compute the Cholesky factorization of A=\begin{pmatrix} 4&2\\ 2&3 \end{pmatrix}.
Method.
Use matrix factorization, triangular substitution, pivoting, Schur complements, QR/SVD, and backward-error analysis.
Detailed solution and justification.
For a symmetric positive definite matrix A, Cholesky factorization writes A=LL^T, with L lower triangular and positive diagonal. The entries are computed from \ell_{ii}= \left( a_{ii}-\sum_{k=1}^{i-1}\ell_{ik}^2 \right)^{1/2}, and for j>i, \ell_{ji}= \frac{1}{\ell_{ii}} \left( a_{ji}-\sum_{k=1}^{i-1}\ell_{jk}\ell_{ik} \right). Positive definiteness guarantees that the square roots are real and positive.
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 4.11
Problem formulation.
Use leading principal minors to determine whether A=\begin{pmatrix} 2&-1\\ -1&2 \end{pmatrix} is symmetric positive definite.
Method.
Use matrix factorization, triangular substitution, pivoting, Schur complements, QR/SVD, and backward-error analysis.
Detailed solution and justification.
The computation is based on rewriting the linear system in a form that can be solved by triangular substitutions or orthogonal transformations. If a factorization A=LU,\quad A=QR,\quad \text{or}\quad A=LL^T is available, the original problem is reduced to simpler subproblems. The residual of a computed solution \widetilde x is r=b-A\widetilde x. A small backward error means that \widetilde x solves a nearby problem. The forward error is bounded in terms of the condition number: \frac{\|x-\widetilde x\|}{\|x\|} \lesssim \kappa(A)\frac{\|r\|}{\|b\|}.
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 4.12
Problem formulation.
Compute a QR factorization of A=\begin{pmatrix} 1&1\\ 0&1\\ 0&0 \end{pmatrix} using classical Gram–Schmidt.
Method.
Use matrix factorization, triangular substitution, pivoting, Schur complements, QR/SVD, and backward-error analysis.
Detailed solution and justification.
The computation is based on rewriting the linear system in a form that can be solved by triangular substitutions or orthogonal transformations. If a factorization A=LU,\quad A=QR,\quad \text{or}\quad A=LL^T is available, the original problem is reduced to simpler subproblems. The residual of a computed solution \widetilde x is r=b-A\widetilde x. A small backward error means that \widetilde x solves a nearby problem. The forward error is bounded in terms of the condition number: \frac{\|x-\widetilde x\|}{\|x\|} \lesssim \kappa(A)\frac{\|r\|}{\|b\|}.
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 4.13
Problem formulation.
Let v=(1,0)^T. Compute H=I-2vv^T. Show that H is orthogonal.
Method.
Use matrix factorization, triangular substitution, pivoting, Schur complements, QR/SVD, and backward-error analysis.
Detailed solution and justification.
The computation is based on rewriting the linear system in a form that can be solved by triangular substitutions or orthogonal transformations. If a factorization A=LU,\quad A=QR,\quad \text{or}\quad A=LL^T is available, the original problem is reduced to simpler subproblems. The residual of a computed solution \widetilde x is r=b-A\widetilde x. A small backward error means that \widetilde x solves a nearby problem. The forward error is bounded in terms of the condition number: \frac{\|x-\widetilde x\|}{\|x\|} \lesssim \kappa(A)\frac{\|r\|}{\|b\|}.
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 4.14
Problem formulation.
Find c and s such that \begin{pmatrix}c&s\\-s&c\end{pmatrix} \begin{pmatrix}3\\4\end{pmatrix} = \begin{pmatrix}5\\0\end{pmatrix}.
Method.
Use matrix factorization, triangular substitution, pivoting, Schur complements, QR/SVD, and backward-error analysis.
Detailed solution and justification.
The computation is based on rewriting the linear system in a form that can be solved by triangular substitutions or orthogonal transformations. If a factorization A=LU,\quad A=QR,\quad \text{or}\quad A=LL^T is available, the original problem is reduced to simpler subproblems. The residual of a computed solution \widetilde x is r=b-A\widetilde x. A small backward error means that \widetilde x solves a nearby problem. The forward error is bounded in terms of the condition number: \frac{\|x-\widetilde x\|}{\|x\|} \lesssim \kappa(A)\frac{\|r\|}{\|b\|}.
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 4.15
Problem formulation.
Derive the normal equations for \min_x\|Ax-b\|_2.
Method.
Use matrix factorization, triangular substitution, pivoting, Schur complements, QR/SVD, and backward-error analysis.
Detailed solution and justification.
The computation is based on rewriting the linear system in a form that can be solved by triangular substitutions or orthogonal transformations. If a factorization A=LU,\quad A=QR,\quad \text{or}\quad A=LL^T is available, the original problem is reduced to simpler subproblems. The residual of a computed solution \widetilde x is r=b-A\widetilde x. A small backward error means that \widetilde x solves a nearby problem. The forward error is bounded in terms of the condition number: \frac{\|x-\widetilde x\|}{\|x\|} \lesssim \kappa(A)\frac{\|r\|}{\|b\|}.
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 4.16
Problem formulation.
If \kappa_2(A)=10^4, what is \kappa_2(A^TA)?
Method.
Use matrix factorization, triangular substitution, pivoting, Schur complements, QR/SVD, and backward-error analysis.
Detailed solution and justification.
The computation is based on rewriting the linear system in a form that can be solved by triangular substitutions or orthogonal transformations. If a factorization A=LU,\quad A=QR,\quad \text{or}\quad A=LL^T is available, the original problem is reduced to simpler subproblems. The residual of a computed solution \widetilde x is r=b-A\widetilde x. A small backward error means that \widetilde x solves a nearby problem. The forward error is bounded in terms of the condition number: \frac{\|x-\widetilde x\|}{\|x\|} \lesssim \kappa(A)\frac{\|r\|}{\|b\|}.
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 4.17
Problem formulation.
Compute the Schur complement of A_{11} in A=\begin{pmatrix} 2&1\\ 3&5 \end{pmatrix}.
Method.
Use matrix factorization, triangular substitution, pivoting, Schur complements, QR/SVD, and backward-error analysis.
Detailed solution and justification.
The computation is based on rewriting the linear system in a form that can be solved by triangular substitutions or orthogonal transformations. If a factorization A=LU,\quad A=QR,\quad \text{or}\quad A=LL^T is available, the original problem is reduced to simpler subproblems. The residual of a computed solution \widetilde x is r=b-A\widetilde x. A small backward error means that \widetilde x solves a nearby problem. The forward error is bounded in terms of the condition number: \frac{\|x-\widetilde x\|}{\|x\|} \lesssim \kappa(A)\frac{\|r\|}{\|b\|}.
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 4.18
Problem formulation.
State the Sherman–Morrison formula and explain when it is valid.
Method.
Use matrix factorization, triangular substitution, pivoting, Schur complements, QR/SVD, and backward-error analysis.
Detailed solution and justification.
For a rank-one update A+uv^T, the Sherman–Morrison formula is (A+uv^T)^{-1} = A^{-1}- \frac{A^{-1}uv^TA^{-1}}{1+v^TA^{-1}u}, provided 1+v^TA^{-1}u\ne0. The Woodbury formula generalizes this to low-rank updates: (A+UCV)^{-1} = A^{-1}-A^{-1}U(C^{-1}+VA^{-1}U)^{-1}VA^{-1}. These formulas are useful when A^{-1} or a factorization of A is already available.
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 4.19
Problem formulation.
Describe one step of iterative refinement for Ax=b.
Method.
Use matrix factorization, triangular substitution, pivoting, Schur complements, QR/SVD, and backward-error analysis.
Detailed solution and justification.
The computation is based on rewriting the linear system in a form that can be solved by triangular substitutions or orthogonal transformations. If a factorization A=LU,\quad A=QR,\quad \text{or}\quad A=LL^T is available, the original problem is reduced to simpler subproblems. The residual of a computed solution \widetilde x is r=b-A\widetilde x. A small backward error means that \widetilde x solves a nearby problem. The forward error is bounded in terms of the condition number: \frac{\|x-\widetilde x\|}{\|x\|} \lesssim \kappa(A)\frac{\|r\|}{\|b\|}.
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 4.20
Problem formulation.
Explain what fill-in means in sparse Gaussian elimination.
Method.
Use matrix factorization, triangular substitution, pivoting, Schur complements, QR/SVD, and backward-error analysis.
Detailed solution and justification.
The computation is based on rewriting the linear system in a form that can be solved by triangular substitutions or orthogonal transformations. If a factorization A=LU,\quad A=QR,\quad \text{or}\quad A=LL^T is available, the original problem is reduced to simpler subproblems. The residual of a computed solution \widetilde x is r=b-A\widetilde x. A small backward error means that \widetilde x solves a nearby problem. The forward error is bounded in terms of the condition number: \frac{\|x-\widetilde x\|}{\|x\|} \lesssim \kappa(A)\frac{\|r\|}{\|b\|}.
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 4.21
Problem formulation.
Prove the relative residual-error bound in the referenced result.
Method.
Use matrix factorization, triangular substitution, pivoting, Schur complements, QR/SVD, and backward-error analysis.
Detailed solution and justification.
The computation is based on rewriting the linear system in a form that can be solved by triangular substitutions or orthogonal transformations. If a factorization A=LU,\quad A=QR,\quad \text{or}\quad A=LL^T is available, the original problem is reduced to simpler subproblems. The residual of a computed solution \widetilde x is r=b-A\widetilde x. A small backward error means that \widetilde x solves a nearby problem. The forward error is bounded in terms of the condition number: \frac{\|x-\widetilde x\|}{\|x\|} \lesssim \kappa(A)\frac{\|r\|}{\|b\|}.
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 4.22
Problem formulation.
Prove the referenced result.
Method.
Use matrix factorization, triangular substitution, pivoting, Schur complements, QR/SVD, and backward-error analysis.
Detailed solution and justification.
The computation is based on rewriting the linear system in a form that can be solved by triangular substitutions or orthogonal transformations. If a factorization A=LU,\quad A=QR,\quad \text{or}\quad A=LL^T is available, the original problem is reduced to simpler subproblems. The residual of a computed solution \widetilde x is r=b-A\widetilde x. A small backward error means that \widetilde x solves a nearby problem. The forward error is bounded in terms of the condition number: \frac{\|x-\widetilde x\|}{\|x\|} \lesssim \kappa(A)\frac{\|r\|}{\|b\|}.
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 4.23
Problem formulation.
Prove the referenced result.
Method.
Use matrix factorization, triangular substitution, pivoting, Schur complements, QR/SVD, and backward-error analysis.
Detailed solution and justification.
The computation is based on rewriting the linear system in a form that can be solved by triangular substitutions or orthogonal transformations. If a factorization A=LU,\quad A=QR,\quad \text{or}\quad A=LL^T is available, the original problem is reduced to simpler subproblems. The residual of a computed solution \widetilde x is r=b-A\widetilde x. A small backward error means that \widetilde x solves a nearby problem. The forward error is bounded in terms of the condition number: \frac{\|x-\widetilde x\|}{\|x\|} \lesssim \kappa(A)\frac{\|r\|}{\|b\|}.
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 4.24
Problem formulation.
Fill in the details of the referenced result.
Method.
Use matrix factorization, triangular substitution, pivoting, Schur complements, QR/SVD, and backward-error analysis.
Detailed solution and justification.
The computation is based on rewriting the linear system in a form that can be solved by triangular substitutions or orthogonal transformations. If a factorization A=LU,\quad A=QR,\quad \text{or}\quad A=LL^T is available, the original problem is reduced to simpler subproblems. The residual of a computed solution \widetilde x is r=b-A\widetilde x. A small backward error means that \widetilde x solves a nearby problem. The forward error is bounded in terms of the condition number: \frac{\|x-\widetilde x\|}{\|x\|} \lesssim \kappa(A)\frac{\|r\|}{\|b\|}.
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 4.25
Problem formulation.
Prove the referenced result.
Method.
Use matrix factorization, triangular substitution, pivoting, Schur complements, QR/SVD, and backward-error analysis.
Detailed solution and justification.
Assume A=LU, where L is lower triangular and U is upper triangular. To solve Ax=b, write LUx=b. Set Ux=y. Then solve the two triangular systems Ly=b, \qquad Ux=y. Forward substitution computes y, and backward substitution computes x. If pivoting is required, use PA=LU, so the first system becomes Ly=Pb.
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 4.26
Problem formulation.
Assume A=LU=\widetilde{L}\widetilde{U}, where L,\widetilde{L} are unit lower triangular and U,\widetilde{U} are upper triangular. Prove uniqueness when the factorization exists.
Method.
Use matrix factorization, triangular substitution, pivoting, Schur complements, QR/SVD, and backward-error analysis.
Detailed solution and justification.
Assume A=LU, where L is lower triangular and U is upper triangular. To solve Ax=b, write LUx=b. Set Ux=y. Then solve the two triangular systems Ly=b, \qquad Ux=y. Forward substitution computes y, and backward substitution computes x. If pivoting is required, use PA=LU, so the first system becomes Ly=Pb.
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 4.27
Problem formulation.
Show that LU factorization without pivoting exists if all leading principal minors of A are nonzero.
Method.
Use matrix factorization, triangular substitution, pivoting, Schur complements, QR/SVD, and backward-error analysis.
Detailed solution and justification.
Assume A=LU, where L is lower triangular and U is upper triangular. To solve Ax=b, write LUx=b. Set Ux=y. Then solve the two triangular systems Ly=b, \qquad Ux=y. Forward substitution computes y, and backward substitution computes x. If pivoting is required, use PA=LU, so the first system becomes Ly=Pb.
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 4.28
Problem formulation.
Prove the referenced result.
Method.
Use matrix factorization, triangular substitution, pivoting, Schur complements, QR/SVD, and backward-error analysis.
Detailed solution and justification.
The computation is based on rewriting the linear system in a form that can be solved by triangular substitutions or orthogonal transformations. If a factorization A=LU,\quad A=QR,\quad \text{or}\quad A=LL^T is available, the original problem is reduced to simpler subproblems. The residual of a computed solution \widetilde x is r=b-A\widetilde x. A small backward error means that \widetilde x solves a nearby problem. The forward error is bounded in terms of the condition number: \frac{\|x-\widetilde x\|}{\|x\|} \lesssim \kappa(A)\frac{\|r\|}{\|b\|}.
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 4.29
Problem formulation.
Prove that partial pivoting gives |\ell_{ik}|\le1.
Method.
Use matrix factorization, triangular substitution, pivoting, Schur complements, QR/SVD, and backward-error analysis.
Detailed solution and justification.
The computation is based on rewriting the linear system in a form that can be solved by triangular substitutions or orthogonal transformations. If a factorization A=LU,\quad A=QR,\quad \text{or}\quad A=LL^T is available, the original problem is reduced to simpler subproblems. The residual of a computed solution \widetilde x is r=b-A\widetilde x. A small backward error means that \widetilde x solves a nearby problem. The forward error is bounded in terms of the condition number: \frac{\|x-\widetilde x\|}{\|x\|} \lesssim \kappa(A)\frac{\|r\|}{\|b\|}.
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 4.30
Problem formulation.
Show that permutation matrices are orthogonal: P^TP=I.
Method.
Use matrix factorization, triangular substitution, pivoting, Schur complements, QR/SVD, and backward-error analysis.
Detailed solution and justification.
The computation is based on rewriting the linear system in a form that can be solved by triangular substitutions or orthogonal transformations. If a factorization A=LU,\quad A=QR,\quad \text{or}\quad A=LL^T is available, the original problem is reduced to simpler subproblems. The residual of a computed solution \widetilde x is r=b-A\widetilde x. A small backward error means that \widetilde x solves a nearby problem. The forward error is bounded in terms of the condition number: \frac{\|x-\widetilde x\|}{\|x\|} \lesssim \kappa(A)\frac{\|r\|}{\|b\|}.
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 4.31
Problem formulation.
Construct a small matrix for which Gaussian elimination without pivoting produces large intermediate entries.
Method.
Use matrix factorization, triangular substitution, pivoting, Schur complements, QR/SVD, and backward-error analysis.
Detailed solution and justification.
The computation is based on rewriting the linear system in a form that can be solved by triangular substitutions or orthogonal transformations. If a factorization A=LU,\quad A=QR,\quad \text{or}\quad A=LL^T is available, the original problem is reduced to simpler subproblems. The residual of a computed solution \widetilde x is r=b-A\widetilde x. A small backward error means that \widetilde x solves a nearby problem. The forward error is bounded in terms of the condition number: \frac{\|x-\widetilde x\|}{\|x\|} \lesssim \kappa(A)\frac{\|r\|}{\|b\|}.
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 4.32
Problem formulation.
Prove the referenced result.
Method.
Use matrix factorization, triangular substitution, pivoting, Schur complements, QR/SVD, and backward-error analysis.
Detailed solution and justification.
For a symmetric positive definite matrix A, Cholesky factorization writes A=LL^T, with L lower triangular and positive diagonal. The entries are computed from \ell_{ii}= \left( a_{ii}-\sum_{k=1}^{i-1}\ell_{ik}^2 \right)^{1/2}, and for j>i, \ell_{ji}= \frac{1}{\ell_{ii}} \left( a_{ji}-\sum_{k=1}^{i-1}\ell_{jk}\ell_{ik} \right). Positive definiteness guarantees that the square roots are real and positive.
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 4.33
Problem formulation.
Prove the referenced result.
Method.
Use matrix factorization, triangular substitution, pivoting, Schur complements, QR/SVD, and backward-error analysis.
Detailed solution and justification.
For a symmetric positive definite matrix A, Cholesky factorization writes A=LL^T, with L lower triangular and positive diagonal. The entries are computed from \ell_{ii}= \left( a_{ii}-\sum_{k=1}^{i-1}\ell_{ik}^2 \right)^{1/2}, and for j>i, \ell_{ji}= \frac{1}{\ell_{ii}} \left( a_{ji}-\sum_{k=1}^{i-1}\ell_{jk}\ell_{ik} \right). Positive definiteness guarantees that the square roots are real and positive.
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 4.34
Problem formulation.
Prove the referenced result.
Method.
Use matrix factorization, triangular substitution, pivoting, Schur complements, QR/SVD, and backward-error analysis.
Detailed solution and justification.
The computation is based on rewriting the linear system in a form that can be solved by triangular substitutions or orthogonal transformations. If a factorization A=LU,\quad A=QR,\quad \text{or}\quad A=LL^T is available, the original problem is reduced to simpler subproblems. The residual of a computed solution \widetilde x is r=b-A\widetilde x. A small backward error means that \widetilde x solves a nearby problem. The forward error is bounded in terms of the condition number: \frac{\|x-\widetilde x\|}{\|x\|} \lesssim \kappa(A)\frac{\|r\|}{\|b\|}.
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 4.35
Problem formulation.
Prove the referenced result.
Method.
Use matrix factorization, triangular substitution, pivoting, Schur complements, QR/SVD, and backward-error analysis.
Detailed solution and justification.
The computation is based on rewriting the linear system in a form that can be solved by triangular substitutions or orthogonal transformations. If a factorization A=LU,\quad A=QR,\quad \text{or}\quad A=LL^T is available, the original problem is reduced to simpler subproblems. The residual of a computed solution \widetilde x is r=b-A\widetilde x. A small backward error means that \widetilde x solves a nearby problem. The forward error is bounded in terms of the condition number: \frac{\|x-\widetilde x\|}{\|x\|} \lesssim \kappa(A)\frac{\|r\|}{\|b\|}.
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 4.36
Problem formulation.
Prove the referenced result.
Method.
Use matrix factorization, triangular substitution, pivoting, Schur complements, QR/SVD, and backward-error analysis.
Detailed solution and justification.
The computation is based on rewriting the linear system in a form that can be solved by triangular substitutions or orthogonal transformations. If a factorization A=LU,\quad A=QR,\quad \text{or}\quad A=LL^T is available, the original problem is reduced to simpler subproblems. The residual of a computed solution \widetilde x is r=b-A\widetilde x. A small backward error means that \widetilde x solves a nearby problem. The forward error is bounded in terms of the condition number: \frac{\|x-\widetilde x\|}{\|x\|} \lesssim \kappa(A)\frac{\|r\|}{\|b\|}.
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 4.37
Problem formulation.
Prove the referenced result.
Method.
Use matrix factorization, triangular substitution, pivoting, Schur complements, QR/SVD, and backward-error analysis.
Detailed solution and justification.
The computation is based on rewriting the linear system in a form that can be solved by triangular substitutions or orthogonal transformations. If a factorization A=LU,\quad A=QR,\quad \text{or}\quad A=LL^T is available, the original problem is reduced to simpler subproblems. The residual of a computed solution \widetilde x is r=b-A\widetilde x. A small backward error means that \widetilde x solves a nearby problem. The forward error is bounded in terms of the condition number: \frac{\|x-\widetilde x\|}{\|x\|} \lesssim \kappa(A)\frac{\|r\|}{\|b\|}.
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 4.38
Problem formulation.
Prove the referenced result.
Method.
Use matrix factorization, triangular substitution, pivoting, Schur complements, QR/SVD, and backward-error analysis.
Detailed solution and justification.
The computation is based on rewriting the linear system in a form that can be solved by triangular substitutions or orthogonal transformations. If a factorization A=LU,\quad A=QR,\quad \text{or}\quad A=LL^T is available, the original problem is reduced to simpler subproblems. The residual of a computed solution \widetilde x is r=b-A\widetilde x. A small backward error means that \widetilde x solves a nearby problem. The forward error is bounded in terms of the condition number: \frac{\|x-\widetilde x\|}{\|x\|} \lesssim \kappa(A)\frac{\|r\|}{\|b\|}.
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 4.39
Problem formulation.
Prove the referenced result.
Method.
Use matrix factorization, triangular substitution, pivoting, Schur complements, QR/SVD, and backward-error analysis.
Detailed solution and justification.
For a rank-one update A+uv^T, the Sherman–Morrison formula is (A+uv^T)^{-1} = A^{-1}- \frac{A^{-1}uv^TA^{-1}}{1+v^TA^{-1}u}, provided 1+v^TA^{-1}u\ne0. The Woodbury formula generalizes this to low-rank updates: (A+UCV)^{-1} = A^{-1}-A^{-1}U(C^{-1}+VA^{-1}U)^{-1}VA^{-1}. These formulas are useful when A^{-1} or a factorization of A is already available.
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 4.40
Problem formulation.
Prove the referenced result.
Method.
Use matrix factorization, triangular substitution, pivoting, Schur complements, QR/SVD, and backward-error analysis.
Detailed solution and justification.
The computation is based on rewriting the linear system in a form that can be solved by triangular substitutions or orthogonal transformations. If a factorization A=LU,\quad A=QR,\quad \text{or}\quad A=LL^T is available, the original problem is reduced to simpler subproblems. The residual of a computed solution \widetilde x is r=b-A\widetilde x. A small backward error means that \widetilde x solves a nearby problem. The forward error is bounded in terms of the condition number: \frac{\|x-\widetilde x\|}{\|x\|} \lesssim \kappa(A)\frac{\|r\|}{\|b\|}.
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 4.41
Problem formulation.
Give a detailed derivation of the referenced result, carefully tracking the role of the growth factor.
Method.
Use matrix factorization, triangular substitution, pivoting, Schur complements, QR/SVD, and backward-error analysis.
Detailed solution and justification.
The computation is based on rewriting the linear system in a form that can be solved by triangular substitutions or orthogonal transformations. If a factorization A=LU,\quad A=QR,\quad \text{or}\quad A=LL^T is available, the original problem is reduced to simpler subproblems. The residual of a computed solution \widetilde x is r=b-A\widetilde x. A small backward error means that \widetilde x solves a nearby problem. The forward error is bounded in terms of the condition number: \frac{\|x-\widetilde x\|}{\|x\|} \lesssim \kappa(A)\frac{\|r\|}{\|b\|}.
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 4.42
Problem formulation.
Construct the classical Wilkinson-type matrix for which partial pivoting exhibits growth factor 2^{n-1}.
Method.
Use matrix factorization, triangular substitution, pivoting, Schur complements, QR/SVD, and backward-error analysis.
Detailed solution and justification.
The computation is based on rewriting the linear system in a form that can be solved by triangular substitutions or orthogonal transformations. If a factorization A=LU,\quad A=QR,\quad \text{or}\quad A=LL^T is available, the original problem is reduced to simpler subproblems. The residual of a computed solution \widetilde x is r=b-A\widetilde x. A small backward error means that \widetilde x solves a nearby problem. The forward error is bounded in terms of the condition number: \frac{\|x-\widetilde x\|}{\|x\|} \lesssim \kappa(A)\frac{\|r\|}{\|b\|}.
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 4.43
Problem formulation.
Compare partial pivoting and complete pivoting. Prove that complete pivoting controls the pivot choice more strongly and discuss its additional cost.
Method.
Use matrix factorization, triangular substitution, pivoting, Schur complements, QR/SVD, and backward-error analysis.
Detailed solution and justification.
The computation is based on rewriting the linear system in a form that can be solved by triangular substitutions or orthogonal transformations. If a factorization A=LU,\quad A=QR,\quad \text{or}\quad A=LL^T is available, the original problem is reduced to simpler subproblems. The residual of a computed solution \widetilde x is r=b-A\widetilde x. A small backward error means that \widetilde x solves a nearby problem. The forward error is bounded in terms of the condition number: \frac{\|x-\widetilde x\|}{\|x\|} \lesssim \kappa(A)\frac{\|r\|}{\|b\|}.
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 4.44
Problem formulation.
Describe rook pivoting and explain why it is useful in symmetric indefinite factorization.
Method.
Use matrix factorization, triangular substitution, pivoting, Schur complements, QR/SVD, and backward-error analysis.
Detailed solution and justification.
The computation is based on rewriting the linear system in a form that can be solved by triangular substitutions or orthogonal transformations. If a factorization A=LU,\quad A=QR,\quad \text{or}\quad A=LL^T is available, the original problem is reduced to simpler subproblems. The residual of a computed solution \widetilde x is r=b-A\widetilde x. A small backward error means that \widetilde x solves a nearby problem. The forward error is bounded in terms of the condition number: \frac{\|x-\widetilde x\|}{\|x\|} \lesssim \kappa(A)\frac{\|r\|}{\|b\|}.
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 4.45
Problem formulation.
Derive the componentwise backward error formula \omega(\widehat{x}) = \max_i \frac{|r_i|} {(|A|\,|\widehat{x}|+|b|)_i}.
Method.
Use matrix factorization, triangular substitution, pivoting, Schur complements, QR/SVD, and backward-error analysis.
Detailed solution and justification.
The computation is based on rewriting the linear system in a form that can be solved by triangular substitutions or orthogonal transformations. If a factorization A=LU,\quad A=QR,\quad \text{or}\quad A=LL^T is available, the original problem is reduced to simpler subproblems. The residual of a computed solution \widetilde x is r=b-A\widetilde x. A small backward error means that \widetilde x solves a nearby problem. The forward error is bounded in terms of the condition number: \frac{\|x-\widetilde x\|}{\|x\|} \lesssim \kappa(A)\frac{\|r\|}{\|b\|}.
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 4.46
Problem formulation.
Give a detailed proof of backward stability for Cholesky factorization.
Method.
Use matrix factorization, triangular substitution, pivoting, Schur complements, QR/SVD, and backward-error analysis.
Detailed solution and justification.
For a symmetric positive definite matrix A, Cholesky factorization writes A=LL^T, with L lower triangular and positive diagonal. The entries are computed from \ell_{ii}= \left( a_{ii}-\sum_{k=1}^{i-1}\ell_{ik}^2 \right)^{1/2}, and for j>i, \ell_{ji}= \frac{1}{\ell_{ii}} \left( a_{ji}-\sum_{k=1}^{i-1}\ell_{jk}\ell_{ik} \right). Positive definiteness guarantees that the square roots are real and positive.
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 4.47
Problem formulation.
Give an example of a symmetric matrix that is not positive definite and explain why Cholesky factorization breaks down.
Method.
Use matrix factorization, triangular substitution, pivoting, Schur complements, QR/SVD, and backward-error analysis.
Detailed solution and justification.
Assume A=LU, where L is lower triangular and U is upper triangular. To solve Ax=b, write LUx=b. Set Ux=y. Then solve the two triangular systems Ly=b, \qquad Ux=y. Forward substitution computes y, and backward substitution computes x. If pivoting is required, use PA=LU, so the first system becomes Ly=Pb.
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 4.48
Problem formulation.
Explain why 2\times2 pivots are needed in stable symmetric indefinite factorization.
Method.
Use matrix factorization, triangular substitution, pivoting, Schur complements, QR/SVD, and backward-error analysis.
Detailed solution and justification.
The computation is based on rewriting the linear system in a form that can be solved by triangular substitutions or orthogonal transformations. If a factorization A=LU,\quad A=QR,\quad \text{or}\quad A=LL^T is available, the original problem is reduced to simpler subproblems. The residual of a computed solution \widetilde x is r=b-A\widetilde x. A small backward error means that \widetilde x solves a nearby problem. The forward error is bounded in terms of the condition number: \frac{\|x-\widetilde x\|}{\|x\|} \lesssim \kappa(A)\frac{\|r\|}{\|b\|}.
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 4.49
Problem formulation.
Prove the referenced result in more detail.
Method.
Use matrix factorization, triangular substitution, pivoting, Schur complements, QR/SVD, and backward-error analysis.
Detailed solution and justification.
The computation is based on rewriting the linear system in a form that can be solved by triangular substitutions or orthogonal transformations. If a factorization A=LU,\quad A=QR,\quad \text{or}\quad A=LL^T is available, the original problem is reduced to simpler subproblems. The residual of a computed solution \widetilde x is r=b-A\widetilde x. A small backward error means that \widetilde x solves a nearby problem. The forward error is bounded in terms of the condition number: \frac{\|x-\widetilde x\|}{\|x\|} \lesssim \kappa(A)\frac{\|r\|}{\|b\|}.
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 4.50
Problem formulation.
Compare classical and modified Gram–Schmidt. Explain why modified Gram–Schmidt is usually more stable.
Method.
Use matrix factorization, triangular substitution, pivoting, Schur complements, QR/SVD, and backward-error analysis.
Detailed solution and justification.
The computation is based on rewriting the linear system in a form that can be solved by triangular substitutions or orthogonal transformations. If a factorization A=LU,\quad A=QR,\quad \text{or}\quad A=LL^T is available, the original problem is reduced to simpler subproblems. The residual of a computed solution \widetilde x is r=b-A\widetilde x. A small backward error means that \widetilde x solves a nearby problem. The forward error is bounded in terms of the condition number: \frac{\|x-\widetilde x\|}{\|x\|} \lesssim \kappa(A)\frac{\|r\|}{\|b\|}.
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 4.51
Problem formulation.
Compare the forward accuracy of solving least-squares problems by Householder QR and by normal equations.
Method.
Use matrix factorization, triangular substitution, pivoting, Schur complements, QR/SVD, and backward-error analysis.
Detailed solution and justification.
The computation is based on rewriting the linear system in a form that can be solved by triangular substitutions or orthogonal transformations. If a factorization A=LU,\quad A=QR,\quad \text{or}\quad A=LL^T is available, the original problem is reduced to simpler subproblems. The residual of a computed solution \widetilde x is r=b-A\widetilde x. A small backward error means that \widetilde x solves a nearby problem. The forward error is bounded in terms of the condition number: \frac{\|x-\widetilde x\|}{\|x\|} \lesssim \kappa(A)\frac{\|r\|}{\|b\|}.
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 4.52
Problem formulation.
Derive the least-squares solution using the singular value decomposition.
Method.
Use matrix factorization, triangular substitution, pivoting, Schur complements, QR/SVD, and backward-error analysis.
Detailed solution and justification.
Assume A=LU, where L is lower triangular and U is upper triangular. To solve Ax=b, write LUx=b. Set Ux=y. Then solve the two triangular systems Ly=b, \qquad Ux=y. Forward substitution computes y, and backward substitution computes x. If pivoting is required, use PA=LU, so the first system becomes Ly=Pb.
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 4.53
Problem formulation.
Prove the referenced result.
Method.
Use matrix factorization, triangular substitution, pivoting, Schur complements, QR/SVD, and backward-error analysis.
Detailed solution and justification.
The computation is based on rewriting the linear system in a form that can be solved by triangular substitutions or orthogonal transformations. If a factorization A=LU,\quad A=QR,\quad \text{or}\quad A=LL^T is available, the original problem is reduced to simpler subproblems. The residual of a computed solution \widetilde x is r=b-A\widetilde x. A small backward error means that \widetilde x solves a nearby problem. The forward error is bounded in terms of the condition number: \frac{\|x-\widetilde x\|}{\|x\|} \lesssim \kappa(A)\frac{\|r\|}{\|b\|}.
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 4.54
Problem formulation.
Explain the purpose of rank-revealing QR factorization and compare it with the SVD.
Method.
Use matrix factorization, triangular substitution, pivoting, Schur complements, QR/SVD, and backward-error analysis.
Detailed solution and justification.
The computation is based on rewriting the linear system in a form that can be solved by triangular substitutions or orthogonal transformations. If a factorization A=LU,\quad A=QR,\quad \text{or}\quad A=LL^T is available, the original problem is reduced to simpler subproblems. The residual of a computed solution \widetilde x is r=b-A\widetilde x. A small backward error means that \widetilde x solves a nearby problem. The forward error is bounded in terms of the condition number: \frac{\|x-\widetilde x\|}{\|x\|} \lesssim \kappa(A)\frac{\|r\|}{\|b\|}.
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 4.55
Problem formulation.
Derive block Gaussian elimination and express it in terms of Schur complements.
Method.
Use matrix factorization, triangular substitution, pivoting, Schur complements, QR/SVD, and backward-error analysis.
Detailed solution and justification.
The computation is based on rewriting the linear system in a form that can be solved by triangular substitutions or orthogonal transformations. If a factorization A=LU,\quad A=QR,\quad \text{or}\quad A=LL^T is available, the original problem is reduced to simpler subproblems. The residual of a computed solution \widetilde x is r=b-A\widetilde x. A small backward error means that \widetilde x solves a nearby problem. The forward error is bounded in terms of the condition number: \frac{\|x-\widetilde x\|}{\|x\|} \lesssim \kappa(A)\frac{\|r\|}{\|b\|}.
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 4.56
Problem formulation.
Prove the Woodbury formula.
Method.
Use matrix factorization, triangular substitution, pivoting, Schur complements, QR/SVD, and backward-error analysis.
Detailed solution and justification.
For a rank-one update A+uv^T, the Sherman–Morrison formula is (A+uv^T)^{-1} = A^{-1}- \frac{A^{-1}uv^TA^{-1}}{1+v^TA^{-1}u}, provided 1+v^TA^{-1}u\ne0. The Woodbury formula generalizes this to low-rank updates: (A+UCV)^{-1} = A^{-1}-A^{-1}U(C^{-1}+VA^{-1}U)^{-1}VA^{-1}. These formulas are useful when A^{-1} or a factorization of A is already available.
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 4.57
Problem formulation.
Estimate the cost of LU factorization for a matrix with fixed lower and upper bandwidth.
Method.
Use matrix factorization, triangular substitution, pivoting, Schur complements, QR/SVD, and backward-error analysis.
Detailed solution and justification.
Assume A=LU, where L is lower triangular and U is upper triangular. To solve Ax=b, write LUx=b. Set Ux=y. Then solve the two triangular systems Ly=b, \qquad Ux=y. Forward substitution computes y, and backward substitution computes x. If pivoting is required, use PA=LU, so the first system becomes Ly=Pb.
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 4.58
Problem formulation.
Explain fill-in using the graph of a sparse symmetric matrix.
Method.
Use matrix factorization, triangular substitution, pivoting, Schur complements, QR/SVD, and backward-error analysis.
Detailed solution and justification.
The computation is based on rewriting the linear system in a form that can be solved by triangular substitutions or orthogonal transformations. If a factorization A=LU,\quad A=QR,\quad \text{or}\quad A=LL^T is available, the original problem is reduced to simpler subproblems. The residual of a computed solution \widetilde x is r=b-A\widetilde x. A small backward error means that \widetilde x solves a nearby problem. The forward error is bounded in terms of the condition number: \frac{\|x-\widetilde x\|}{\|x\|} \lesssim \kappa(A)\frac{\|r\|}{\|b\|}.
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 4.59
Problem formulation.
Describe nested dissection ordering and explain why it reduces fill-in for grid-like problems.
Method.
Use matrix factorization, triangular substitution, pivoting, Schur complements, QR/SVD, and backward-error analysis.
Detailed solution and justification.
The computation is based on rewriting the linear system in a form that can be solved by triangular substitutions or orthogonal transformations. If a factorization A=LU,\quad A=QR,\quad \text{or}\quad A=LL^T is available, the original problem is reduced to simpler subproblems. The residual of a computed solution \widetilde x is r=b-A\widetilde x. A small backward error means that \widetilde x solves a nearby problem. The forward error is bounded in terms of the condition number: \frac{\|x-\widetilde x\|}{\|x\|} \lesssim \kappa(A)\frac{\|r\|}{\|b\|}.
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 4.60
Problem formulation.
Analyze iterative refinement when the factorization is computed in low precision and the residual in high precision.
Method.
Use matrix factorization, triangular substitution, pivoting, Schur complements, QR/SVD, and backward-error analysis.
Detailed solution and justification.
The computation is based on rewriting the linear system in a form that can be solved by triangular substitutions or orthogonal transformations. If a factorization A=LU,\quad A=QR,\quad \text{or}\quad A=LL^T is available, the original problem is reduced to simpler subproblems. The residual of a computed solution \widetilde x is r=b-A\widetilde x. A small backward error means that \widetilde x solves a nearby problem. The forward error is bounded in terms of the condition number: \frac{\|x-\widetilde x\|}{\|x\|} \lesssim \kappa(A)\frac{\|r\|}{\|b\|}.
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 4.61
Problem formulation.
Discuss diagonal scaling D_rAD_c. Give an example where scaling improves componentwise behavior.
Method.
Use matrix factorization, triangular substitution, pivoting, Schur complements, QR/SVD, and backward-error analysis.
Detailed solution and justification.
The computation is based on rewriting the linear system in a form that can be solved by triangular substitutions or orthogonal transformations. If a factorization A=LU,\quad A=QR,\quad \text{or}\quad A=LL^T is available, the original problem is reduced to simpler subproblems. The residual of a computed solution \widetilde x is r=b-A\widetilde x. A small backward error means that \widetilde x solves a nearby problem. The forward error is bounded in terms of the condition number: \frac{\|x-\widetilde x\|}{\|x\|} \lesssim \kappa(A)\frac{\|r\|}{\|b\|}.
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 4.62
Problem formulation.
Show how to compute \det(A) from PA=LU, including the sign of the permutation.
Method.
Use matrix factorization, triangular substitution, pivoting, Schur complements, QR/SVD, and backward-error analysis.
Detailed solution and justification.
Assume A=LU, where L is lower triangular and U is upper triangular. To solve Ax=b, write LUx=b. Set Ux=y. Then solve the two triangular systems Ly=b, \qquad Ux=y. Forward substitution computes y, and backward substitution computes x. If pivoting is required, use PA=LU, so the first system becomes Ly=Pb.
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 4.63
Problem formulation.
Explain how to compute A^{-1} using an LU factorization. Why is solving systems usually preferable to forming A^{-1}?
Method.
Use matrix factorization, triangular substitution, pivoting, Schur complements, QR/SVD, and backward-error analysis.
Detailed solution and justification.
Assume A=LU, where L is lower triangular and U is upper triangular. To solve Ax=b, write LUx=b. Set Ux=y. Then solve the two triangular systems Ly=b, \qquad Ux=y. Forward substitution computes y, and backward substitution computes x. If pivoting is required, use PA=LU, so the first system becomes Ly=Pb.
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 4.64
Problem formulation.
Design a practical error estimator for Ax=b based on the residual, an estimate of \|A^{-1}\|, and componentwise backward error.
Method.
Use matrix factorization, triangular substitution, pivoting, Schur complements, QR/SVD, and backward-error analysis.
Detailed solution and justification.
The computation is based on rewriting the linear system in a form that can be solved by triangular substitutions or orthogonal transformations. If a factorization A=LU,\quad A=QR,\quad \text{or}\quad A=LL^T is available, the original problem is reduced to simpler subproblems. The residual of a computed solution \widetilde x is r=b-A\widetilde x. A small backward error means that \widetilde x solves a nearby problem. The forward error is bounded in terms of the condition number: \frac{\|x-\widetilde x\|}{\|x\|} \lesssim \kappa(A)\frac{\|r\|}{\|b\|}.
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 4.65
Problem formulation.
Investigate how row scaling can affect pivot choices and growth factors in partial pivoting.
Method.
Use matrix factorization, triangular substitution, pivoting, Schur complements, QR/SVD, and backward-error analysis.
Detailed solution and justification.
The computation is based on rewriting the linear system in a form that can be solved by triangular substitutions or orthogonal transformations. If a factorization A=LU,\quad A=QR,\quad \text{or}\quad A=LL^T is available, the original problem is reduced to simpler subproblems. The residual of a computed solution \widetilde x is r=b-A\widetilde x. A small backward error means that \widetilde x solves a nearby problem. The forward error is bounded in terms of the condition number: \frac{\|x-\widetilde x\|}{\|x\|} \lesssim \kappa(A)\frac{\|r\|}{\|b\|}.
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 4.66
Problem formulation.
State and prove a rigorous Wilkinson backward-error theorem for Gaussian elimination with partial pivoting.
Method.
Use matrix factorization, triangular substitution, pivoting, Schur complements, QR/SVD, and backward-error analysis.
Detailed solution and justification.
The computation is based on rewriting the linear system in a form that can be solved by triangular substitutions or orthogonal transformations. If a factorization A=LU,\quad A=QR,\quad \text{or}\quad A=LL^T is available, the original problem is reduced to simpler subproblems. The residual of a computed solution \widetilde x is r=b-A\widetilde x. A small backward error means that \widetilde x solves a nearby problem. The forward error is bounded in terms of the condition number: \frac{\|x-\widetilde x\|}{\|x\|} \lesssim \kappa(A)\frac{\|r\|}{\|b\|}.
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 4.67
Problem formulation.
Study why large growth factors are rare in practice for random matrices, despite exponential worst-case examples.
Method.
Use matrix factorization, triangular substitution, pivoting, Schur complements, QR/SVD, and backward-error analysis.
Detailed solution and justification.
The computation is based on rewriting the linear system in a form that can be solved by triangular substitutions or orthogonal transformations. If a factorization A=LU,\quad A=QR,\quad \text{or}\quad A=LL^T is available, the original problem is reduced to simpler subproblems. The residual of a computed solution \widetilde x is r=b-A\widetilde x. A small backward error means that \widetilde x solves a nearby problem. The forward error is bounded in terms of the condition number: \frac{\|x-\widetilde x\|}{\|x\|} \lesssim \kappa(A)\frac{\|r\|}{\|b\|}.
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 4.68
Problem formulation.
State a strong rank-revealing QR theorem and compare its guarantees with those of the SVD.
Method.
Use matrix factorization, triangular substitution, pivoting, Schur complements, QR/SVD, and backward-error analysis.
Detailed solution and justification.
The computation is based on rewriting the linear system in a form that can be solved by triangular substitutions or orthogonal transformations. If a factorization A=LU,\quad A=QR,\quad \text{or}\quad A=LL^T is available, the original problem is reduced to simpler subproblems. The residual of a computed solution \widetilde x is r=b-A\widetilde x. A small backward error means that \widetilde x solves a nearby problem. The forward error is bounded in terms of the condition number: \frac{\|x-\widetilde x\|}{\|x\|} \lesssim \kappa(A)\frac{\|r\|}{\|b\|}.
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 4.69
Problem formulation.
Study communication-avoiding LU factorization. Explain how reducing communication can be as important as reducing arithmetic.
Method.
Use matrix factorization, triangular substitution, pivoting, Schur complements, QR/SVD, and backward-error analysis.
Detailed solution and justification.
Assume A=LU, where L is lower triangular and U is upper triangular. To solve Ax=b, write LUx=b. Set Ux=y. Then solve the two triangular systems Ly=b, \qquad Ux=y. Forward substitution computes y, and backward substitution computes x. If pivoting is required, use PA=LU, so the first system becomes Ly=Pb.
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 4.70
Problem formulation.
Derive a blocked LU or Cholesky algorithm and explain why matrix-matrix updates are preferred on modern architectures.
Method.
Use matrix factorization, triangular substitution, pivoting, Schur complements, QR/SVD, and backward-error analysis.
Detailed solution and justification.
Assume A=LU, where L is lower triangular and U is upper triangular. To solve Ax=b, write LUx=b. Set Ux=y. Then solve the two triangular systems Ly=b, \qquad Ux=y. Forward substitution computes y, and backward substitution computes x. If pivoting is required, use PA=LU, so the first system becomes Ly=Pb.
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 4.71
Problem formulation.
Define the elimination tree of a sparse Cholesky factorization and explain how it organizes parallel computation.
Method.
Use matrix factorization, triangular substitution, pivoting, Schur complements, QR/SVD, and backward-error analysis.
Detailed solution and justification.
For a symmetric positive definite matrix A, Cholesky factorization writes A=LL^T, with L lower triangular and positive diagonal. The entries are computed from \ell_{ii}= \left( a_{ii}-\sum_{k=1}^{i-1}\ell_{ik}^2 \right)^{1/2}, and for j>i, \ell_{ji}= \frac{1}{\ell_{ii}} \left( a_{ji}-\sum_{k=1}^{i-1}\ell_{jk}\ell_{ik} \right). Positive definiteness guarantees that the square roots are real and positive.
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 4.72
Problem formulation.
Study the multifrontal method for sparse direct factorization and explain the role of frontal matrices.
Method.
Use matrix factorization, triangular substitution, pivoting, Schur complements, QR/SVD, and backward-error analysis.
Detailed solution and justification.
The computation is based on rewriting the linear system in a form that can be solved by triangular substitutions or orthogonal transformations. If a factorization A=LU,\quad A=QR,\quad \text{or}\quad A=LL^T is available, the original problem is reduced to simpler subproblems. The residual of a computed solution \widetilde x is r=b-A\widetilde x. A small backward error means that \widetilde x solves a nearby problem. The forward error is bounded in terms of the condition number: \frac{\|x-\widetilde x\|}{\|x\|} \lesssim \kappa(A)\frac{\|r\|}{\|b\|}.
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 4.73
Problem formulation.
Explain supernodal sparse factorization and why dense linear algebra kernels improve performance.
Method.
Use matrix factorization, triangular substitution, pivoting, Schur complements, QR/SVD, and backward-error analysis.
Detailed solution and justification.
The computation is based on rewriting the linear system in a form that can be solved by triangular substitutions or orthogonal transformations. If a factorization A=LU,\quad A=QR,\quad \text{or}\quad A=LL^T is available, the original problem is reduced to simpler subproblems. The residual of a computed solution \widetilde x is r=b-A\widetilde x. A small backward error means that \widetilde x solves a nearby problem. The forward error is bounded in terms of the condition number: \frac{\|x-\widetilde x\|}{\|x\|} \lesssim \kappa(A)\frac{\|r\|}{\|b\|}.
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 4.74
Problem formulation.
Analyze the tradeoff between sparsity preservation and numerical stability in sparse pivoting strategies.
Method.
Use matrix factorization, triangular substitution, pivoting, Schur complements, QR/SVD, and backward-error analysis.
Detailed solution and justification.
The computation is based on rewriting the linear system in a form that can be solved by triangular substitutions or orthogonal transformations. If a factorization A=LU,\quad A=QR,\quad \text{or}\quad A=LL^T is available, the original problem is reduced to simpler subproblems. The residual of a computed solution \widetilde x is r=b-A\widetilde x. A small backward error means that \widetilde x solves a nearby problem. The forward error is bounded in terms of the condition number: \frac{\|x-\widetilde x\|}{\|x\|} \lesssim \kappa(A)\frac{\|r\|}{\|b\|}.
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 4.75
Problem formulation.
Study direct solvers for Toeplitz, Hankel, Cauchy, or Vandermonde matrices. Compare fast algorithms with stability issues.
Method.
Use matrix factorization, triangular substitution, pivoting, Schur complements, QR/SVD, and backward-error analysis.
Detailed solution and justification.
The computation is based on rewriting the linear system in a form that can be solved by triangular substitutions or orthogonal transformations. If a factorization A=LU,\quad A=QR,\quad \text{or}\quad A=LL^T is available, the original problem is reduced to simpler subproblems. The residual of a computed solution \widetilde x is r=b-A\widetilde x. A small backward error means that \widetilde x solves a nearby problem. The forward error is bounded in terms of the condition number: \frac{\|x-\widetilde x\|}{\|x\|} \lesssim \kappa(A)\frac{\|r\|}{\|b\|}.
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 4.76
Problem formulation.
Investigate hierarchical low-rank direct solvers such as HSS or HODLR methods. Explain when off-diagonal low rank appears.
Method.
Use matrix factorization, triangular substitution, pivoting, Schur complements, QR/SVD, and backward-error analysis.
Detailed solution and justification.
The computation is based on rewriting the linear system in a form that can be solved by triangular substitutions or orthogonal transformations. If a factorization A=LU,\quad A=QR,\quad \text{or}\quad A=LL^T is available, the original problem is reduced to simpler subproblems. The residual of a computed solution \widetilde x is r=b-A\widetilde x. A small backward error means that \widetilde x solves a nearby problem. The forward error is bounded in terms of the condition number: \frac{\|x-\widetilde x\|}{\|x\|} \lesssim \kappa(A)\frac{\|r\|}{\|b\|}.
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 4.77
Problem formulation.
Explain how Sherman–Morrison–Woodbury formulas arise in quasi-Newton optimization and constrained least-squares problems.
Method.
Use matrix factorization, triangular substitution, pivoting, Schur complements, QR/SVD, and backward-error analysis.
Detailed solution and justification.
For a rank-one update A+uv^T, the Sherman–Morrison formula is (A+uv^T)^{-1} = A^{-1}- \frac{A^{-1}uv^TA^{-1}}{1+v^TA^{-1}u}, provided 1+v^TA^{-1}u\ne0. The Woodbury formula generalizes this to low-rank updates: (A+UCV)^{-1} = A^{-1}-A^{-1}U(C^{-1}+VA^{-1}U)^{-1}VA^{-1}. These formulas are useful when A^{-1} or a factorization of A is already available.
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 4.78
Problem formulation.
Design an interval-arithmetic verification procedure for certifying that a computed \widehat{x} encloses the exact solution of Ax=b.
Method.
Use matrix factorization, triangular substitution, pivoting, Schur complements, QR/SVD, and backward-error analysis.
Detailed solution and justification.
Assume A=LU, where L is lower triangular and U is upper triangular. To solve Ax=b, write LUx=b. Set Ux=y. Then solve the two triangular systems Ly=b, \qquad Ux=y. Forward substitution computes y, and backward substitution computes x. If pivoting is required, use PA=LU, so the first system becomes Ly=Pb.
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 4.79
Problem formulation.
Develop a componentwise perturbation theory for Ax=b and compare it with normwise condition-number bounds.
Method.
Use matrix factorization, triangular substitution, pivoting, Schur complements, QR/SVD, and backward-error analysis.
Detailed solution and justification.
The computation is based on rewriting the linear system in a form that can be solved by triangular substitutions or orthogonal transformations. If a factorization A=LU,\quad A=QR,\quad \text{or}\quad A=LL^T is available, the original problem is reduced to simpler subproblems. The residual of a computed solution \widetilde x is r=b-A\widetilde x. A small backward error means that \widetilde x solves a nearby problem. The forward error is bounded in terms of the condition number: \frac{\|x-\widetilde x\|}{\|x\|} \lesssim \kappa(A)\frac{\|r\|}{\|b\|}.
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 4.80
Problem formulation.
Study smoothed analysis results explaining why Gaussian elimination with partial pivoting is reliable in practice.
Method.
Use matrix factorization, triangular substitution, pivoting, Schur complements, QR/SVD, and backward-error analysis.
Detailed solution and justification.
The computation is based on rewriting the linear system in a form that can be solved by triangular substitutions or orthogonal transformations. If a factorization A=LU,\quad A=QR,\quad \text{or}\quad A=LL^T is available, the original problem is reduced to simpler subproblems. The residual of a computed solution \widetilde x is r=b-A\widetilde x. A small backward error means that \widetilde x solves a nearby problem. The forward error is bounded in terms of the condition number: \frac{\|x-\widetilde x\|}{\|x\|} \lesssim \kappa(A)\frac{\|r\|}{\|b\|}.
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 4.81
Problem formulation.
Analyze the use of FP16, BF16, TF32, FP32, and FP64 in mixed-precision direct solvers with iterative refinement.
Method.
Use matrix factorization, triangular substitution, pivoting, Schur complements, QR/SVD, and backward-error analysis.
Detailed solution and justification.
The computation is based on rewriting the linear system in a form that can be solved by triangular substitutions or orthogonal transformations. If a factorization A=LU,\quad A=QR,\quad \text{or}\quad A=LL^T is available, the original problem is reduced to simpler subproblems. The residual of a computed solution \widetilde x is r=b-A\widetilde x. A small backward error means that \widetilde x solves a nearby problem. The forward error is bounded in terms of the condition number: \frac{\|x-\widetilde x\|}{\|x\|} \lesssim \kappa(A)\frac{\|r\|}{\|b\|}.
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 4.82
Problem formulation.
Discuss reproducibility issues in parallel direct solvers and propose strategies for bitwise reproducible factorizations.
Method.
Use matrix factorization, triangular substitution, pivoting, Schur complements, QR/SVD, and backward-error analysis.
Detailed solution and justification.
The computation is based on rewriting the linear system in a form that can be solved by triangular substitutions or orthogonal transformations. If a factorization A=LU,\quad A=QR,\quad \text{or}\quad A=LL^T is available, the original problem is reduced to simpler subproblems. The residual of a computed solution \widetilde x is r=b-A\widetilde x. A small backward error means that \widetilde x solves a nearby problem. The forward error is bounded in terms of the condition number: \frac{\|x-\widetilde x\|}{\|x\|} \lesssim \kappa(A)\frac{\|r\|}{\|b\|}.
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 4.83
Problem formulation.
Compare numerical pivoting with fraction-free Gaussian elimination over exact arithmetic domains.
Method.
Use matrix factorization, triangular substitution, pivoting, Schur complements, QR/SVD, and backward-error analysis.
Detailed solution and justification.
The computation is based on rewriting the linear system in a form that can be solved by triangular substitutions or orthogonal transformations. If a factorization A=LU,\quad A=QR,\quad \text{or}\quad A=LL^T is available, the original problem is reduced to simpler subproblems. The residual of a computed solution \widetilde x is r=b-A\widetilde x. A small backward error means that \widetilde x solves a nearby problem. The forward error is bounded in terms of the condition number: \frac{\|x-\widetilde x\|}{\|x\|} \lesssim \kappa(A)\frac{\|r\|}{\|b\|}.
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 4.84
Problem formulation.
Study block direct solvers for saddle-point systems \begin{pmatrix} A & B^T\\ B & 0 \end{pmatrix} \begin{pmatrix} x\\y \end{pmatrix} = \begin{pmatrix} f\\g \end{pmatrix}. Analyze Schur complement strategies.
Method.
Use matrix factorization, triangular substitution, pivoting, Schur complements, QR/SVD, and backward-error analysis.
Detailed solution and justification.
The computation is based on rewriting the linear system in a form that can be solved by triangular substitutions or orthogonal transformations. If a factorization A=LU,\quad A=QR,\quad \text{or}\quad A=LL^T is available, the original problem is reduced to simpler subproblems. The residual of a computed solution \widetilde x is r=b-A\widetilde x. A small backward error means that \widetilde x solves a nearby problem. The forward error is bounded in terms of the condition number: \frac{\|x-\widetilde x\|}{\|x\|} \lesssim \kappa(A)\frac{\|r\|}{\|b\|}.
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 4.85
Problem formulation.
Explain how sparse Cholesky or multifrontal solvers are used in finite element discretizations of elliptic PDEs. Analyze fill-in and ordering.
Method.
Use matrix factorization, triangular substitution, pivoting, Schur complements, QR/SVD, and backward-error analysis.
Detailed solution and justification.
For a symmetric positive definite matrix A, Cholesky factorization writes A=LL^T, with L lower triangular and positive diagonal. The entries are computed from \ell_{ii}= \left( a_{ii}-\sum_{k=1}^{i-1}\ell_{ik}^2 \right)^{1/2}, and for j>i, \ell_{ji}= \frac{1}{\ell_{ii}} \left( a_{ji}-\sum_{k=1}^{i-1}\ell_{jk}\ell_{ik} \right). Positive definiteness guarantees that the square roots are real and positive.
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.
Interactive tools
The theory and solutions come first. These tools are for review, laboratories, games, memory cards, and randomized assessment.