Chapter 5
Iterative 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:
derive stationary iterations from matrix splittings A=M-N;
prove the spectral-radius convergence criterion;
analyze Jacobi, Gauss–Seidel, SOR, weighted Jacobi, and Richardson iterations;
understand diagonal dominance, M-matrices, and symmetric positive definite convergence criteria;
formulate Krylov subspaces and projection methods;
derive the Arnoldi and Lanczos recurrences;
prove the main convergence estimate for the conjugate-gradient method;
understand GMRES as a residual-minimization method;
compare preconditioning strategies and their effect on spectra;
explain the smoothing principle and the structure of multigrid;
solve basic, advanced, and research-level exercises on iterative solvers.
Why Iterative Methods?
Direct methods factorize the matrix A and solve Ax=b in a finite number of arithmetic operations in exact arithmetic. For very large systems, especially sparse systems coming from partial differential equations, direct factorization may be too expensive because of fill-in, storage growth, and communication cost. Iterative methods generate a sequence x^{(0)},x^{(1)},x^{(2)},\ldots that ideally converges to the exact solution x=A^{-1}b.
Iterative methods trade exact finite termination for cheaper iterations. Their success depends on the spectrum, the conditioning, the matrix structure, and the quality of the preconditioner.
The residual and error are r^{(k)}=b-Ax^{(k)}, \qquad e^{(k)}=x-x^{(k)}. They satisfy the fundamental identity r^{(k)}=Ae^{(k)}. Thus a small residual implies a small error only when A is not too ill-conditioned.
Matrix Splittings
Let A=M-N, where M is nonsingular. Then the system Ax=b becomes Mx=Nx+b. The associated fixed-point iteration is x^{(k+1)}=M^{-1}Nx^{(k)}+M^{-1}b. Define the iteration matrix B=M^{-1}N and the constant vector c=M^{-1}b. Then x^{(k+1)}=Bx^{(k)}+c.
Let x be the exact solution of Ax=b. If x^{(k+1)}=Bx^{(k)}+c, where x=Bx+c, then e^{(k+1)}=Be^{(k)} and therefore e^{(k)}=B^ke^{(0)}.
Since x=Bx+c and x^{(k+1)}=Bx^{(k)}+c, x^{(k+1)}-x = B(x^{(k)}-x). Thus e^{(k+1)}=Be^{(k)}. Applying the same identity repeatedly gives e^{(k)}=B^ke^{(0)}.
□
A stationary iteration uses the same matrix B at every step. Its convergence is completely determined by the powers B^k. e^{(k)}=B^ke^{(0)}.
The Spectral-Radius Convergence Theorem
The spectral radius of a square matrix B is \rho(B)=\max\{|\lambda|:\lambda\in\sigma(B)\}.
The stationary iteration x^{(k+1)}=Bx^{(k)}+c converges to the unique fixed point for every initial vector x^{(0)} if and only if \rho(B)<1.
The iteration converges for every initial vector if and only if B^ke^{(0)}\to0 for every vector e^{(0)}. This is equivalent to B^k\to0.
If B^k\to0, then for every eigenpair Bv=\lambda v, B^kv=\lambda^kv\to0. Since v\ne0, this implies |\lambda|<1. Hence \rho(B)<1.
Conversely, if \rho(B)<1, then the Jordan canonical form, or equivalently the Gelfand formula \rho(B)=\lim_{k\to\infty}\|B^k\|^{1/k}, implies that B^k\to0. Therefore e^{(k)}=B^ke^{(0)}\to0 for every e^{(0)}.
□
Classical Splittings: Jacobi, Gauss–Seidel, and SOR
Write A=D-L-U, where D is the diagonal part of A, -L is the strictly lower triangular part, and -U is the strictly upper triangular part. This sign convention is standard in iterative methods.
Jacobi Method
The Jacobi splitting is M=D, \qquad N=L+U. Thus x_J^{(k+1)} = D^{-1}(L+U)x^{(k)}+D^{-1}b. Componentwise, x_i^{(k+1)} = \frac{1}{a_{ii}} \left( b_i-\sum_{j\ne i}a_{ij}x_j^{(k)} \right).
Caption.
Jacobi iteration
A, b, initial vector x^{(0)}, tolerance \tau
For k=0,1,2,\ldots:
For i=1,\ldots,n:
x_i^{(k+1)}\gets \dfrac{1}{a_{ii}}\left(b_i-\sum_{j\ne i}a_{ij}x_j^{(k)}\right)
If \|b-Ax^{(k+1)}\|\le \tau\|b\|:
Return x^{(k+1)}
Gauss–Seidel Method
The Gauss–Seidel splitting is M=D-L, \qquad N=U. Thus x_{GS}^{(k+1)} = (D-L)^{-1}Ux^{(k)}+(D-L)^{-1}b. Componentwise, x_i^{(k+1)} = \frac{1}{a_{ii}} \left( b_i-\sum_{j<i}a_{ij}x_j^{(k+1)} -\sum_{j>i}a_{ij}x_j^{(k)} \right). Gauss–Seidel uses newly computed components as soon as they become available.
Caption.
Gauss–Seidel iteration
A, b, initial vector x^{(0)}, tolerance \tau
For k=0,1,2,\ldots:
For i=1,\ldots,n:
s_1\gets \sum_{j<i}a_{ij}x_j^{(k+1)}
s_2\gets \sum_{j>i}a_{ij}x_j^{(k)}
x_i^{(k+1)}\gets (b_i-s_1-s_2)/a_{ii}
If \|b-Ax^{(k+1)}\|\le \tau\|b\|:
Return x^{(k+1)}
Successive Over-Relaxation
The SOR method introduces a relaxation parameter \omega: x_i^{(k+1)} = (1-\omega)x_i^{(k)} + \frac{\omega}{a_{ii}} \left( b_i-\sum_{j<i}a_{ij}x_j^{(k+1)} -\sum_{j>i}a_{ij}x_j^{(k)} \right). Its iteration matrix is B_\omega = (D-\omega L)^{-1}\left[(1-\omega)D+\omega U\right]. The case \omega=1 gives Gauss–Seidel.
Caption.
SOR iteration
A, b, x^{(0)}, relaxation parameter \omega, tolerance \tau
For k=0,1,2,\ldots:
For i=1,\ldots,n:
s_1\gets \sum_{j<i}a_{ij}x_j^{(k+1)}
s_2\gets \sum_{j>i}a_{ij}x_j^{(k)}
z_i\gets (b_i-s_1-s_2)/a_{ii}
x_i^{(k+1)}\gets (1-\omega)x_i^{(k)}+\omega z_i
If \|b-Ax^{(k+1)}\|\le \tau\|b\|:
Return x^{(k+1)}
Convergence Criteria for Classical Methods
A matrix A=(a_{ij}) is strictly row diagonally dominant if |a_{ii}|>\sum_{j\ne i}|a_{ij}|, \qquad i=1,\ldots,n.
If A is strictly row diagonally dominant, then the Jacobi method converges for every initial vector.
The Jacobi iteration matrix is B_J=D^{-1}(L+U). Its infinity norm is \|B_J\|_\infty = \max_i \frac{1}{|a_{ii}|} \sum_{j\ne i}|a_{ij}|. Strict diagonal dominance gives \|B_J\|_\infty<1. Therefore \rho(B_J)\le \|B_J\|_\infty<1, and the spectral-radius theorem proves convergence.
□
If A is strictly row diagonally dominant, then the Gauss–Seidel method converges for every initial vector.
Let e^{(k+1)}=B_{GS}e^{(k)}. In component form, a_{ii}e_i^{(k+1)} = -\sum_{j<i}a_{ij}e_j^{(k+1)} - \sum_{j>i}a_{ij}e_j^{(k)}. Choose an index p such that |e_p^{(k+1)}|=\|e^{(k+1)}\|_\infty. Then |a_{pp}|\|e^{(k+1)}\|_\infty \le \sum_{j<p}|a_{pj}|\|e^{(k+1)}\|_\infty + \sum_{j>p}|a_{pj}|\|e^{(k)}\|_\infty. Rearranging gives \|e^{(k+1)}\|_\infty \le q\|e^{(k)}\|_\infty with q<1, because strict diagonal dominance implies |a_{pp}|-\sum_{j<p}|a_{pj}|>\sum_{j>p}|a_{pj}|. Thus Gauss–Seidel is a contraction in the infinity norm.
□
If A is symmetric positive definite, then Gauss–Seidel converges for every initial vector.
For A=D-L-L^T, the Gauss–Seidel splitting is A=(D-L)-L^T. The error equation is (D-L)e^{(k+1)}=L^Te^{(k)}. One can show, using the A-energy norm \|v\|_A^2=v^TAv, that \|e^{(k+1)}\|_A<\|e^{(k)}\|_A unless e^{(k)}=0. The strict decrease follows from positive definiteness of A and the triangular splitting. Hence the iteration converges.
□
If the SOR method converges, then 0<\omega<2. For symmetric positive definite A, SOR converges for every initial vector whenever 0<\omega<2.
The determinant of the SOR iteration matrix is \det(B_\omega)=(1-\omega)^n. If the method converges, then all eigenvalues of B_\omega must have modulus less than one. Hence |\det(B_\omega)|<1, which implies |1-\omega|<1, and therefore 0<\omega<2.
For the SPD case, the standard energy argument for consistently relaxed triangular splittings shows that the SOR iteration matrix is a contraction in an equivalent energy norm for 0<\omega<2.
□
Richardson and Weighted Jacobi Iterations
Richardson iteration is x^{(k+1)}=x^{(k)}+\alpha r^{(k)}, \qquad r^{(k)}=b-Ax^{(k)}. The error satisfies e^{(k+1)}=(I-\alpha A)e^{(k)}. Thus convergence requires \rho(I-\alpha A)<1.
Let A be symmetric positive definite with eigenvalues in \lambda_{\min}\le \lambda \le \lambda_{\max}. The Richardson iteration converges if 0<\alpha<\frac{2}{\lambda_{\max}}. The value minimizing \max_{\lambda\in[\lambda_{\min},\lambda_{\max}]}|1-\alpha\lambda| is \alpha_\ast=\frac{2}{\lambda_{\min}+\lambda_{\max}}, and the corresponding convergence factor is \frac{\kappa_2(A)-1}{\kappa_2(A)+1}.
The eigenvalues of I-\alpha A are 1-\alpha\lambda_i. Convergence is equivalent to |1-\alpha\lambda_i|<1 for all i, which gives 0<\alpha<\frac{2}{\lambda_{\max}}. The optimal \alpha balances the endpoint magnitudes: 1-\alpha\lambda_{\min}=-(1-\alpha\lambda_{\max}). Solving gives \alpha_\ast=\frac{2}{\lambda_{\min}+\lambda_{\max}}. The maximum factor becomes \frac{\lambda_{\max}-\lambda_{\min}} {\lambda_{\max}+\lambda_{\min}} = \frac{\kappa_2(A)-1}{\kappa_2(A)+1}.
□
Weighted Jacobi is x^{(k+1)} = x^{(k)} + \omega D^{-1}(b-Ax^{(k)}). It is especially important as a smoother in multigrid methods.
Krylov Subspaces
The k-th Krylov subspace generated by A and r_0 is \mathcal K_k(A,r_0) = \operatorname{span} \{r_0,Ar_0,A^2r_0,\ldots,A^{k-1}r_0\}. Krylov methods seek approximations of the form x_k=x_0+q_{k-1}(A)r_0, where q_{k-1} is a polynomial of degree at most k-1. Therefore x_k\in x_0+\mathcal K_k(A,r_0). The residual can be written as r_k=p_k(A)r_0, where p_k is a polynomial of degree k satisfying p_k(0)=1.
Projection Principles
Let x_k\in x_0+\mathcal K_k. A projection method imposes r_k=b-Ax_k\perp \mathcal L_k, where \mathcal L_k is a chosen test space.
Important choices are: \mathcal L_k=\mathcal K_k \qquad \text{Galerkin condition}, and x_k=\arg\min_{x\in x_0+\mathcal K_k}\|b-Ax\|_2 \qquad \text{minimal residual condition}. CG uses a Galerkin principle for SPD matrices. GMRES uses a minimal-residual principle for nonsymmetric matrices.
Arnoldi Process
The Arnoldi process constructs an orthonormal basis V_k=[v_1,\ldots,v_k] for \mathcal K_k(A,r_0). It produces the relation AV_k=V_{k+1}\overline{H}_k, where \overline{H}_k is (k+1)\times k upper Hessenberg.
Caption.
Arnoldi process
A, starting vector r_0\ne0, dimension k
v_1\gets r_0/\|r_0\|_2
For j=1,\ldots,k:
w\gets Av_j
For i=1,\ldots,j:
h_{ij}\gets v_i^Tw
w\gets w-h_{ij}v_i
h_{j+1,j}\gets \|w\|_2
If h_{j+1,j}=0:
stop
v_{j+1}\gets w/h_{j+1,j}
Return V_{k+1}, \overline{H}_k
After k Arnoldi steps, AV_k=V_{k+1}\overline{H}_k. Moreover, the columns of V_{k+1} are orthonormal unless breakdown occurs.
At step j, the algorithm writes Av_j=\sum_{i=1}^{j+1}h_{ij}v_i. Stacking these identities for j=1,\ldots,k gives AV_k=V_{k+1}\overline{H}_k. The orthogonalization subtracts the projections onto previous basis vectors, and the normalization makes each new vector have unit norm. Hence the columns are orthonormal unless h_{j+1,j}=0.
□
Conjugate Gradient Method
Assume A is symmetric positive definite. CG solves Ax=b by minimizing the quadratic energy \phi(x)=\frac12x^TAx-b^Tx. The gradient is \nabla\phi(x)=Ax-b=-r.
CG generates search directions p_k that are A-conjugate: p_i^TAp_j=0, \qquad i\ne j.
Caption.
Conjugate gradient method
SPD matrix A, right-hand side b, initial vector x_0
r_0\gets b-Ax_0
p_0\gets r_0
For k=0,1,2,\ldots:
\alpha_k\gets \dfrac{r_k^Tr_k}{p_k^TAp_k}
x_{k+1}\gets x_k+\alpha_kp_k
r_{k+1}\gets r_k-\alpha_kAp_k
If \|r_{k+1}\| is small enough:
Return x_{k+1}
\beta_k\gets \dfrac{r_{k+1}^Tr_{k+1}}{r_k^Tr_k}
p_{k+1}\gets r_{k+1}+\beta_kp_k
Let A be symmetric positive definite. The k-th CG iterate satisfies x_k = \arg\min_{x\in x_0+\mathcal K_k(A,r_0)} \|x-x_\ast\|_A, where \|v\|_A=\sqrt{v^TAv}.
The quadratic satisfies \phi(x)-\phi(x_\ast) = \frac12\|x-x_\ast\|_A^2. CG constructs x_k by imposing the Galerkin condition r_k\perp \mathcal K_k(A,r_0). Since r_k=b-Ax_k=A(x_\ast-x_k), this is equivalent to x_\ast-x_k\perp_A \mathcal K_k(A,r_0). Therefore x_k is the A-orthogonal projection of x_\ast onto x_0+\mathcal K_k(A,r_0), which is precisely the minimizer in the A-norm.
□
Let A be symmetric positive definite and let \kappa=\kappa_2(A). Then the CG error satisfies \frac{\|e_k\|_A}{\|e_0\|_A} \le 2 \left( \frac{\sqrt{\kappa}-1}{\sqrt{\kappa}+1} \right)^k.
The CG minimization property implies \|e_k\|_A = \min_{\substack{p\in\mathbb P_k\\p(0)=1}} \|p(A)e_0\|_A. Using the spectral decomposition of A, this gives \frac{\|e_k\|_A}{\|e_0\|_A} \le \min_{\substack{p\in\mathbb P_k\\p(0)=1}} \max_{\lambda\in[\lambda_{\min},\lambda_{\max}]} |p(\lambda)|. The scaled Chebyshev polynomial on [\lambda_{\min},\lambda_{\max}] gives the bound 2 \left( \frac{\sqrt{\kappa}-1}{\sqrt{\kappa}+1} \right)^k.
□
Lanczos Process and Symmetric Krylov Methods
For symmetric A, Arnoldi reduces to the Lanczos process: AV_k=V_kT_k+\beta_kv_{k+1}e_k^T, where T_k is tridiagonal. This three-term recurrence is the algebraic reason why CG can be implemented with short recurrences.
For symmetric indefinite systems, MINRES uses the Lanczos relation and minimizes the residual norm over a Krylov subspace. Unlike CG, MINRES does not require positive definiteness, but it does require symmetry.
GMRES
For a general nonsymmetric matrix A, GMRES chooses x_k\in x_0+\mathcal K_k(A,r_0) to minimize \|b-Ax_k\|_2. Using Arnoldi, AV_k=V_{k+1}\overline{H}_k, and writing x_k=x_0+V_ky, the residual becomes r_k=r_0-AV_ky. If r_0=\beta v_1, \qquad \beta=\|r_0\|_2, then r_k = V_{k+1}(\beta e_1-\overline{H}_ky). Since V_{k+1} has orthonormal columns, \|r_k\|_2 = \|\beta e_1-\overline{H}_ky\|_2. Thus GMRES reduces a large least-squares problem to a small one.
Caption.
GMRES
A, b, x_0, maximum dimension m
r_0\gets b-Ax_0
\beta\gets \|r_0\|_2
v_1\gets r_0/\beta
For k=1,\ldots,m:
Perform one Arnoldi step to update V_{k+1} and \overline{H}_k
Solve y_k=\arg\min_y\|\beta e_1-\overline{H}_ky\|_2
x_k\gets x_0+V_ky_k
If \|\beta e_1-\overline{H}_ky_k\|_2 is small enough:
Return x_k
Return x_m
The k-th GMRES iterate satisfies \|r_k\|_2 = \min_{x\in x_0+\mathcal K_k(A,r_0)} \|b-Ax\|_2. Equivalently, \|r_k\|_2 = \min_{\substack{p\in\mathbb P_k\\p(0)=1}} \|p(A)r_0\|_2.
Every vector in x_0+\mathcal K_k(A,r_0) has the form x=x_0+q_{k-1}(A)r_0. Then r=b-Ax = r_0-Aq_{k-1}(A)r_0 = p_k(A)r_0, where p_k(0)=1. GMRES chooses the vector in the affine Krylov space that minimizes the residual norm, hence the polynomial characterization follows.
□
Restarted GMRES and Nonsymmetric Methods
Full GMRES stores all Arnoldi vectors, so memory and orthogonalization cost increase with k. Restarted GMRES, denoted GMRES(m), runs m steps, restarts from the current iterate, and repeats. Restarting saves storage but may slow or destroy convergence.
Other important nonsymmetric methods include: \text{BiCG},\qquad \text{CGS},\qquad \text{QMR},\qquad \text{BiCGSTAB}. BiCGSTAB is often attractive because it uses short recurrences and smoother residual behavior than BiCG, but it can break down or stagnate on difficult problems.
Preconditioning
A preconditioner is a matrix M such that M^{-1}A is easier for an iterative method than A, while applying M^{-1} is cheap.
Left preconditioning solves M^{-1}Ax=M^{-1}b. Right preconditioning solves AM^{-1}y=b, \qquad x=M^{-1}y. Split preconditioning uses M=M_LM_R and solves M_L^{-1}AM_R^{-1}y=M_L^{-1}b.
A good preconditioner should:
reduce the effective condition number or cluster eigenvalues;
be cheap to apply;
preserve important structure when possible;
be robust across a family of related problems.
Common preconditioners include: \text{Jacobi},\qquad \text{block Jacobi},\qquad \text{SSOR},\qquad \text{ILU},\qquad \text{incomplete Cholesky},\qquad \text{multigrid}.
Preconditioned Conjugate Gradient
For SPD systems, the preconditioner M should also be SPD. PCG applies CG in the M^{-1}A-geometry without forming M^{-1}A explicitly.
Caption.
Preconditioned conjugate gradient
SPD A, SPD preconditioner M, right-hand side b, initial x_0
r_0\gets b-Ax_0
Solve Mz_0=r_0
p_0\gets z_0
For k=0,1,2,\ldots:
\alpha_k\gets \dfrac{r_k^Tz_k}{p_k^TAp_k}
x_{k+1}\gets x_k+\alpha_kp_k
r_{k+1}\gets r_k-\alpha_kAp_k
If \|r_{k+1}\| is small enough:
Return x_{k+1}
Solve Mz_{k+1}=r_{k+1}
\beta_k\gets \dfrac{r_{k+1}^Tz_{k+1}}{r_k^Tz_k}
p_{k+1}\gets z_{k+1}+\beta_kp_k
Let A and M be SPD. PCG satisfies the same type of bound as CG with \kappa_2(A) replaced by \kappa_2(M^{-1/2}AM^{-1/2}). Thus \frac{\|e_k\|_A}{\|e_0\|_A} \le 2 \left( \frac{\sqrt{\kappa_M}-1}{\sqrt{\kappa_M}+1} \right)^k, where \kappa_M=\kappa_2(M^{-1/2}AM^{-1/2}).
Since M is SPD, define \widetilde{A}=M^{-1/2}AM^{-1/2}. This matrix is SPD. Applying CG theory to the transformed system \widetilde{A}y=M^{-1/2}b, \qquad x=M^{-1/2}y, gives the stated convergence estimate with \kappa_M=\kappa_2(\widetilde{A}).
□
Multigrid Methods
Multigrid methods are designed for discretized differential equations. They exploit two complementary facts:
simple iterations such as weighted Jacobi or Gauss–Seidel rapidly damp high-frequency error components;
smooth low-frequency errors on a fine grid look more oscillatory on a coarse grid and can be corrected cheaply there.
A two-grid correction has the form: \text{smooth on fine grid}, \text{restrict residual to coarse grid}, \text{solve or approximately solve coarse-grid error equation}, \text{prolongate correction to fine grid}, \text{post-smooth}.
Caption.
Multigrid V-cycle
level \ell, matrix A_\ell, right-hand side b_\ell, initial x_\ell
If \ell is the coarsest level:
Solve A_\ell x_\ell=b_\ell directly
Else:
Apply \nu_1 pre-smoothing steps to A_\ell x_\ell=b_\ell
r_\ell\gets b_\ell-A_\ell x_\ell
r_{\ell-1}\gets R_\ell r_\ell
e_{\ell-1}\gets 0
Recursively solve A_{\ell-1}e_{\ell-1}=r_{\ell-1}
x_\ell\gets x_\ell+P_\ell e_{\ell-1}
Apply \nu_2 post-smoothing steps
Return x_\ell
Stopping Criteria and Finite Precision
Common stopping criteria include: \frac{\|r^{(k)}\|}{\|b\|}\le \tau, \frac{\|x^{(k+1)}-x^{(k)}\|}{1+\|x^{(k+1)}\|}\le \tau, and componentwise backward-error tests. For Krylov methods, finite precision causes loss of orthogonality, residual gaps, delayed convergence, and possible stagnation.
In finite precision, the recursively updated residual may differ from the true residual: r_k^{\mathrm{true}}=b-Ax_k. Reliable implementations occasionally recompute the residual explicitly.
Practical Comparison of Iterative Methods
- Jacobi.
-
Very simple and parallel, but usually slow. Useful as a smoother and for teaching.
- Gauss–Seidel.
-
Often faster than Jacobi, but less parallel in its basic form.
- SOR.
-
Can be much faster if \omega is well chosen. Poor \omega can ruin convergence.
- Richardson.
-
Simple and theoretically useful. Needs spectral information or preconditioning.
- CG.
-
Best first choice for large sparse SPD systems. Requires only matrix-vector products and short recurrences.
- MINRES.
-
Appropriate for symmetric indefinite systems when residual minimization is desired.
- GMRES.
-
Robust for nonsymmetric systems, but storage and orthogonalization costs grow unless restarted.
- BiCGSTAB.
-
Short recurrences for nonsymmetric systems. Often effective, but less robust than GMRES.
- Preconditioned Krylov.
-
Usually essential for difficult large-scale systems. The preconditioner often determines success or failure.
- Multigrid.
-
Optimal or near-optimal for many PDE systems when grid hierarchy, smoothing, and coarse-grid correction are well designed.
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 A=M-N. Derive x^{(k+1)}=M^{-1}Nx^{(k)}+M^{-1}b.
Prove that if e^{(k)}=x^{(k)}-x, then e^{(k)}=B^ke^{(0)}.
Compute the spectral radius of B=\begin{pmatrix} 0&1/2\\ 1/3&0 \end{pmatrix}.
Derive the Jacobi method from the splitting A=D-L-U.
Derive the Gauss–Seidel method from the splitting A=(D-L)-U.
For A=\begin{pmatrix}4&1\\1&3\end{pmatrix}, \qquad b=\begin{pmatrix}1\\2\end{pmatrix}, perform one Jacobi step starting from x^{(0)}=0.
For the same system as in the referenced result, perform one Gauss–Seidel step starting from x^{(0)}=0.
Show that SOR with \omega=1 is Gauss–Seidel.
Show that Richardson iteration has error matrix I-\alpha A.
Let A be SPD with eigenvalues in [2,8]. For what values of \alpha does Richardson iteration converge?
Write \mathcal K_3(A,r_0) explicitly.
What matrix properties are required for the standard conjugate-gradient method?
State the minimization property of GMRES.
Explain the difference between left and right preconditioning.
What is the Jacobi preconditioner for a matrix A?
Given x^{(k)}, define the residual r^{(k)}. Explain why it is useful.
Give two common stopping criteria for iterative methods.
State the two main ideas behind multigrid methods.
Why are weighted Jacobi and Gauss–Seidel called smoothers in multigrid?
Explain the difference between a recursively updated residual and the true residual b-Ax_k.
Intermediate problems \star
Prove the referenced result.
Show that if \|B\|<1 in any subordinate norm, then the iteration x^{(k+1)}=Bx^{(k)}+c converges.
Prove the referenced result.
Prove the referenced result.
Prove the necessary condition 0<\omega<2 for SOR convergence.
Prove the referenced result.
Derive the weighted Jacobi iteration and its iteration matrix.
Use Gershgorin disks to derive a sufficient condition for Jacobi convergence.
Prove the referenced result.
Show that every Krylov iterate can be written as x_k=x_0+q_{k-1}(A)r_0.
Show that the Krylov residual has the form r_k=p_k(A)r_0, \qquad p_k(0)=1.
Derive the CG formula \alpha_k=\frac{r_k^Tr_k}{p_k^TAp_k}.
Derive the Fletcher–Reeves CG coefficient \beta_k=\frac{r_{k+1}^Tr_{k+1}}{r_k^Tr_k}.
Prove that exact-arithmetic CG residuals are mutually orthogonal.
Prove that exact-arithmetic CG search directions are A-conjugate.
Prove the referenced result.
Derive the small least-squares problem in GMRES: \min_y\|\beta e_1-\overline{H}_ky\|_2.
Prove the polynomial characterization of GMRES residuals.
Show that right preconditioning solves AM^{-1}y=b, \qquad x=M^{-1}y.
Show that PCG is equivalent to applying CG to M^{-1/2}AM^{-1/2}y=M^{-1/2}b.
Write the algebraic two-grid error-propagation operator.
For the one-dimensional Poisson matrix, explain why weighted Jacobi damps high-frequency error components.
Explain how rounding errors create a gap between recursive and true residuals.
Give two reasons why an iterative method may stagnate in finite precision.
Design a robust stopping test using both relative residual and relative update size.
Advanced problems \star\star
Prove the spectral-radius theorem using Jordan canonical form.
Prove or carefully justify the use of Gelfand’s formula \rho(B)=\lim_{k\to\infty}\|B^k\|^{1/k}.
Study convergence of Jacobi and Gauss–Seidel for nonsingular M-matrices.
Define consistently ordered matrices and derive the classical optimal SOR parameter formula in terms of \rho(B_J).
State and prove Young’s theorem for SOR convergence under standard assumptions.
Derive the SSOR preconditioner and explain why it is symmetric positive definite under suitable assumptions.
Derive Chebyshev semi-iteration for SPD systems when eigenvalue bounds are known.
Derive steepest descent for SPD linear systems and compare its convergence factor with CG.
Prove the referenced result in full detail.
Explain why CG may converge much faster than the condition-number bound when eigenvalues are clustered.
Derive the Lanczos three-term recurrence from Arnoldi for symmetric matrices.
Derive the MINRES minimization property for symmetric indefinite systems.
For normal A, bound GMRES convergence using polynomial approximation on the spectrum.
Define the field of values and explain how it can be used to estimate GMRES convergence.
Construct an example or explanation showing why restarted GMRES may stagnate.
Derive the BiCG method from coupled Krylov subspaces for A and A^T.
Explain the stabilization idea behind BiCGSTAB and compare it with BiCG.
Define ILU(0) and explain how it differs from exact LU factorization.
Describe incomplete Cholesky preconditioning for SPD systems and discuss breakdown.
Explain additive Schwarz preconditioning from a domain-decomposition perspective.
Explain the difference between geometric multigrid and algebraic multigrid.
Derive a two-grid convergence estimate from smoothing and approximation properties.
Use local Fourier analysis to study weighted Jacobi smoothing for the one-dimensional Poisson equation.
Derive the Kaczmarz method as successive orthogonal projections onto hyperplanes.
State and prove a basic expected convergence estimate for randomized Kaczmarz.
Research-level problems \star\star\star
Analyze loss of orthogonality and delayed convergence in finite-precision CG.
Study residual replacement strategies in Krylov methods and explain when they improve robustness.
Derive flexible GMRES for variable preconditioners and explain why ordinary GMRES formulas are insufficient.
Study deflated CG or GMRES and explain how removing troublesome eigencomponents accelerates convergence.
Analyze Krylov subspace recycling for sequences of slowly varying linear systems.
Design a polynomial preconditioner and analyze its effect on the residual polynomial.
Prove an optimal O(n) complexity estimate for a model multigrid method under standard smoothing and approximation assumptions.
Study strength-of-connection measures in algebraic multigrid and explain their role in coarsening.
Explain smoothed aggregation AMG and compare it with classical AMG.
Develop block preconditioners for saddle-point systems and analyze the spectra of the preconditioned operators.
Study Schur-complement preconditioners for block systems and derive spectral equivalence conditions.
State and prove a condition-number estimate for an additive Schwarz preconditioner.
Investigate communication-avoiding Krylov methods and explain the stability tradeoffs caused by enlarged bases.
Study pipelined CG or GMRES and analyze the effect of overlapping communication and computation.
Analyze mixed-precision Krylov methods with low-precision preconditioning and high-precision residual correction.
Study randomized sketching as a preconditioner for least-squares or linear systems.
Explain how Krylov methods are used inside Newton’s method for nonlinear systems. Analyze forcing terms and preconditioning.
For the finite-difference Poisson equation in two dimensions, compare Jacobi, Gauss–Seidel, CG, PCG, and multigrid in terms of asymptotic complexity.
Design stopping criteria for Krylov methods that account for conditioning, residual gaps, and backward error.
Discuss reproducibility challenges for parallel iterative solvers and propose strategies for deterministic reductions.
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 5. Each solution includes the problem formulation, the method, the mathematical derivation, the conclusion, and a diagnostic comment.
Exercise 5.1
Problem formulation.
Let A=M-N. Derive x^{(k+1)}=M^{-1}Nx^{(k)}+M^{-1}b.
Method.
Use matrix splittings, spectral-radius convergence, Krylov projection, CG/GMRES recurrences, and preconditioning arguments.
Detailed solution and justification.
An iterative method can be written as x^{(k+1)}=Gx^{(k)}+c. If x_\ast is the fixed point, then e^{(k+1)}=Ge^{(k)}. Therefore e^{(k)}=G^ke^{(0)}. The method converges for every initial guess if and only if \rho(G)<1. For Krylov methods, the approximation is selected from x_k\in x_0+\mathcal K_k(A,r_0), using an orthogonality, minimization, or projection condition.
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 5.2
Problem formulation.
Prove that if e^{(k)}=x^{(k)}-x, then e^{(k)}=B^ke^{(0)}.
Method.
Use matrix splittings, spectral-radius convergence, Krylov projection, CG/GMRES recurrences, and preconditioning arguments.
Detailed solution and justification.
An iterative method can be written as x^{(k+1)}=Gx^{(k)}+c. If x_\ast is the fixed point, then e^{(k+1)}=Ge^{(k)}. Therefore e^{(k)}=G^ke^{(0)}. The method converges for every initial guess if and only if \rho(G)<1. For Krylov methods, the approximation is selected from x_k\in x_0+\mathcal K_k(A,r_0), using an orthogonality, minimization, or projection condition.
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 5.3
Problem formulation.
Compute the spectral radius of B=\begin{pmatrix} 0&1/2\\ 1/3&0 \end{pmatrix}.
Method.
Use matrix splittings, spectral-radius convergence, Krylov projection, CG/GMRES recurrences, and preconditioning arguments.
Detailed solution and justification.
An iterative method can be written as x^{(k+1)}=Gx^{(k)}+c. If x_\ast is the fixed point, then e^{(k+1)}=Ge^{(k)}. Therefore e^{(k)}=G^ke^{(0)}. The method converges for every initial guess if and only if \rho(G)<1. For Krylov methods, the approximation is selected from x_k\in x_0+\mathcal K_k(A,r_0), using an orthogonality, minimization, or projection condition.
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 5.4
Problem formulation.
Derive the Jacobi method from the splitting A=D-L-U.
Method.
Use matrix splittings, spectral-radius convergence, Krylov projection, CG/GMRES recurrences, and preconditioning arguments.
Detailed solution and justification.
Split A=D-(L+U), where D is the diagonal part. Jacobi iteration solves the diagonal part exactly: Dx^{(k+1)}=(L+U)x^{(k)}+b. Componentwise, x_i^{(k+1)} = \frac1{a_{ii}} \left( b_i-\sum_{j\ne i}a_{ij}x_j^{(k)} \right). The iteration matrix is G_J=D^{-1}(L+U). Convergence occurs if \rho(G_J)<1.
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 5.5
Problem formulation.
Derive the Gauss–Seidel method from the splitting A=(D-L)-U.
Method.
Use matrix splittings, spectral-radius convergence, Krylov projection, CG/GMRES recurrences, and preconditioning arguments.
Detailed solution and justification.
With A=D-L-U, Gauss–Seidel uses the newest available components: (D-L)x^{(k+1)}=Ux^{(k)}+b. Componentwise, x_i^{(k+1)} = \frac1{a_{ii}} \left( b_i-\sum_{j<i}a_{ij}x_j^{(k+1)} -\sum_{j>i}a_{ij}x_j^{(k)} \right). The iteration matrix is G_{GS}=(D-L)^{-1}U. It converges whenever \rho(G_{GS})<1; in particular, convergence holds for symmetric positive definite matrices.
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 5.6
Problem formulation.
For A=\begin{pmatrix}4&1\\1&3\end{pmatrix}, \qquad b=\begin{pmatrix}1\\2\end{pmatrix}, perform one Jacobi step starting from x^{(0)}=0.
Method.
Use matrix splittings, spectral-radius convergence, Krylov projection, CG/GMRES recurrences, and preconditioning arguments.
Detailed solution and justification.
Split A=D-(L+U), where D is the diagonal part. Jacobi iteration solves the diagonal part exactly: Dx^{(k+1)}=(L+U)x^{(k)}+b. Componentwise, x_i^{(k+1)} = \frac1{a_{ii}} \left( b_i-\sum_{j\ne i}a_{ij}x_j^{(k)} \right). The iteration matrix is G_J=D^{-1}(L+U). Convergence occurs if \rho(G_J)<1.
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 5.7
Problem formulation.
For the same system as in the referenced result, perform one Gauss–Seidel step starting from x^{(0)}=0.
Method.
Use matrix splittings, spectral-radius convergence, Krylov projection, CG/GMRES recurrences, and preconditioning arguments.
Detailed solution and justification.
Split A=D-(L+U), where D is the diagonal part. Jacobi iteration solves the diagonal part exactly: Dx^{(k+1)}=(L+U)x^{(k)}+b. Componentwise, x_i^{(k+1)} = \frac1{a_{ii}} \left( b_i-\sum_{j\ne i}a_{ij}x_j^{(k)} \right). The iteration matrix is G_J=D^{-1}(L+U). Convergence occurs if \rho(G_J)<1.
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 5.8
Problem formulation.
Show that SOR with \omega=1 is Gauss–Seidel.
Method.
Use matrix splittings, spectral-radius convergence, Krylov projection, CG/GMRES recurrences, and preconditioning arguments.
Detailed solution and justification.
With A=D-L-U, Gauss–Seidel uses the newest available components: (D-L)x^{(k+1)}=Ux^{(k)}+b. Componentwise, x_i^{(k+1)} = \frac1{a_{ii}} \left( b_i-\sum_{j<i}a_{ij}x_j^{(k+1)} -\sum_{j>i}a_{ij}x_j^{(k)} \right). The iteration matrix is G_{GS}=(D-L)^{-1}U. It converges whenever \rho(G_{GS})<1; in particular, convergence holds for symmetric positive definite matrices.
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 5.9
Problem formulation.
Show that Richardson iteration has error matrix I-\alpha A.
Method.
Use matrix splittings, spectral-radius convergence, Krylov projection, CG/GMRES recurrences, and preconditioning arguments.
Detailed solution and justification.
An iterative method can be written as x^{(k+1)}=Gx^{(k)}+c. If x_\ast is the fixed point, then e^{(k+1)}=Ge^{(k)}. Therefore e^{(k)}=G^ke^{(0)}. The method converges for every initial guess if and only if \rho(G)<1. For Krylov methods, the approximation is selected from x_k\in x_0+\mathcal K_k(A,r_0), using an orthogonality, minimization, or projection condition.
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 5.10
Problem formulation.
Let A be SPD with eigenvalues in [2,8]. For what values of \alpha does Richardson iteration converge?
Method.
Use matrix splittings, spectral-radius convergence, Krylov projection, CG/GMRES recurrences, and preconditioning arguments.
Detailed solution and justification.
An iterative method can be written as x^{(k+1)}=Gx^{(k)}+c. If x_\ast is the fixed point, then e^{(k+1)}=Ge^{(k)}. Therefore e^{(k)}=G^ke^{(0)}. The method converges for every initial guess if and only if \rho(G)<1. For Krylov methods, the approximation is selected from x_k\in x_0+\mathcal K_k(A,r_0), using an orthogonality, minimization, or projection condition.
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 5.11
Problem formulation.
Write \mathcal K_3(A,r_0) explicitly.
Method.
Use matrix splittings, spectral-radius convergence, Krylov projection, CG/GMRES recurrences, and preconditioning arguments.
Detailed solution and justification.
An iterative method can be written as x^{(k+1)}=Gx^{(k)}+c. If x_\ast is the fixed point, then e^{(k+1)}=Ge^{(k)}. Therefore e^{(k)}=G^ke^{(0)}. The method converges for every initial guess if and only if \rho(G)<1. For Krylov methods, the approximation is selected from x_k\in x_0+\mathcal K_k(A,r_0), using an orthogonality, minimization, or projection condition.
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 5.12
Problem formulation.
What matrix properties are required for the standard conjugate-gradient method?
Method.
Use matrix splittings, spectral-radius convergence, Krylov projection, CG/GMRES recurrences, and preconditioning arguments.
Detailed solution and justification.
For A=A^T\succ0, CG minimizes the quadratic \phi(x)=\frac12x^TAx-b^Tx over successive Krylov spaces. The recurrences are \alpha_k=\frac{r_k^Tr_k}{p_k^TAp_k}, \qquad x_{k+1}=x_k+\alpha_kp_k, r_{k+1}=r_k-\alpha_kAp_k, \beta_k=\frac{r_{k+1}^Tr_{k+1}}{r_k^Tr_k}, \qquad p_{k+1}=r_{k+1}+\beta_kp_k. The directions satisfy p_i^TAp_j=0,\qquad i\ne j. Thus CG reaches the exact solution in at most n steps in exact arithmetic.
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 5.13
Problem formulation.
State the minimization property of GMRES.
Method.
Use matrix splittings, spectral-radius convergence, Krylov projection, CG/GMRES recurrences, and preconditioning arguments.
Detailed solution and justification.
GMRES seeks an approximation in x_k=x_0+V_ky, where V_k spans the Krylov space \mathcal K_k(A,r_0)= \operatorname{span}\{r_0,Ar_0,\ldots,A^{k-1}r_0\}. Arnoldi gives AV_k=V_{k+1}\overline H_k. The residual is r_k=b-Ax_k=r_0-AV_ky. Since r_0=\beta v_1=V_{k+1}\beta e_1, r_k=V_{k+1}(\beta e_1-\overline H_ky). Because V_{k+1} has orthonormal columns, GMRES solves y_k=\arg\min_y\|\beta e_1-\overline H_ky\|_2.
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 5.14
Problem formulation.
Explain the difference between left and right preconditioning.
Method.
Use matrix splittings, spectral-radius convergence, Krylov projection, CG/GMRES recurrences, and preconditioning arguments.
Detailed solution and justification.
An iterative method can be written as x^{(k+1)}=Gx^{(k)}+c. If x_\ast is the fixed point, then e^{(k+1)}=Ge^{(k)}. Therefore e^{(k)}=G^ke^{(0)}. The method converges for every initial guess if and only if \rho(G)<1. For Krylov methods, the approximation is selected from x_k\in x_0+\mathcal K_k(A,r_0), using an orthogonality, minimization, or projection condition.
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 5.15
Problem formulation.
What is the Jacobi preconditioner for a matrix A?
Method.
Use matrix splittings, spectral-radius convergence, Krylov projection, CG/GMRES recurrences, and preconditioning arguments.
Detailed solution and justification.
Split A=D-(L+U), where D is the diagonal part. Jacobi iteration solves the diagonal part exactly: Dx^{(k+1)}=(L+U)x^{(k)}+b. Componentwise, x_i^{(k+1)} = \frac1{a_{ii}} \left( b_i-\sum_{j\ne i}a_{ij}x_j^{(k)} \right). The iteration matrix is G_J=D^{-1}(L+U). Convergence occurs if \rho(G_J)<1.
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 5.16
Problem formulation.
Given x^{(k)}, define the residual r^{(k)}. Explain why it is useful.
Method.
Use matrix splittings, spectral-radius convergence, Krylov projection, CG/GMRES recurrences, and preconditioning arguments.
Detailed solution and justification.
An iterative method can be written as x^{(k+1)}=Gx^{(k)}+c. If x_\ast is the fixed point, then e^{(k+1)}=Ge^{(k)}. Therefore e^{(k)}=G^ke^{(0)}. The method converges for every initial guess if and only if \rho(G)<1. For Krylov methods, the approximation is selected from x_k\in x_0+\mathcal K_k(A,r_0), using an orthogonality, minimization, or projection condition.
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 5.17
Problem formulation.
Give two common stopping criteria for iterative methods.
Method.
Use matrix splittings, spectral-radius convergence, Krylov projection, CG/GMRES recurrences, and preconditioning arguments.
Detailed solution and justification.
An iterative method can be written as x^{(k+1)}=Gx^{(k)}+c. If x_\ast is the fixed point, then e^{(k+1)}=Ge^{(k)}. Therefore e^{(k)}=G^ke^{(0)}. The method converges for every initial guess if and only if \rho(G)<1. For Krylov methods, the approximation is selected from x_k\in x_0+\mathcal K_k(A,r_0), using an orthogonality, minimization, or projection condition.
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 5.18
Problem formulation.
State the two main ideas behind multigrid methods.
Method.
Use matrix splittings, spectral-radius convergence, Krylov projection, CG/GMRES recurrences, and preconditioning arguments.
Detailed solution and justification.
An iterative method can be written as x^{(k+1)}=Gx^{(k)}+c. If x_\ast is the fixed point, then e^{(k+1)}=Ge^{(k)}. Therefore e^{(k)}=G^ke^{(0)}. The method converges for every initial guess if and only if \rho(G)<1. For Krylov methods, the approximation is selected from x_k\in x_0+\mathcal K_k(A,r_0), using an orthogonality, minimization, or projection condition.
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 5.19
Problem formulation.
Why are weighted Jacobi and Gauss–Seidel called smoothers in multigrid?
Method.
Use matrix splittings, spectral-radius convergence, Krylov projection, CG/GMRES recurrences, and preconditioning arguments.
Detailed solution and justification.
Split A=D-(L+U), where D is the diagonal part. Jacobi iteration solves the diagonal part exactly: Dx^{(k+1)}=(L+U)x^{(k)}+b. Componentwise, x_i^{(k+1)} = \frac1{a_{ii}} \left( b_i-\sum_{j\ne i}a_{ij}x_j^{(k)} \right). The iteration matrix is G_J=D^{-1}(L+U). Convergence occurs if \rho(G_J)<1.
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 5.20
Problem formulation.
Explain the difference between a recursively updated residual and the true residual b-Ax_k.
Method.
Use matrix splittings, spectral-radius convergence, Krylov projection, CG/GMRES recurrences, and preconditioning arguments.
Detailed solution and justification.
An iterative method can be written as x^{(k+1)}=Gx^{(k)}+c. If x_\ast is the fixed point, then e^{(k+1)}=Ge^{(k)}. Therefore e^{(k)}=G^ke^{(0)}. The method converges for every initial guess if and only if \rho(G)<1. For Krylov methods, the approximation is selected from x_k\in x_0+\mathcal K_k(A,r_0), using an orthogonality, minimization, or projection condition.
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 5.21
Problem formulation.
Prove the referenced result.
Method.
Use matrix splittings, spectral-radius convergence, Krylov projection, CG/GMRES recurrences, and preconditioning arguments.
Detailed solution and justification.
An iterative method can be written as x^{(k+1)}=Gx^{(k)}+c. If x_\ast is the fixed point, then e^{(k+1)}=Ge^{(k)}. Therefore e^{(k)}=G^ke^{(0)}. The method converges for every initial guess if and only if \rho(G)<1. For Krylov methods, the approximation is selected from x_k\in x_0+\mathcal K_k(A,r_0), using an orthogonality, minimization, or projection condition.
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 5.22
Problem formulation.
Show that if \|B\|<1 in any subordinate norm, then the iteration x^{(k+1)}=Bx^{(k)}+c converges.
Method.
Use matrix splittings, spectral-radius convergence, Krylov projection, CG/GMRES recurrences, and preconditioning arguments.
Detailed solution and justification.
An iterative method can be written as x^{(k+1)}=Gx^{(k)}+c. If x_\ast is the fixed point, then e^{(k+1)}=Ge^{(k)}. Therefore e^{(k)}=G^ke^{(0)}. The method converges for every initial guess if and only if \rho(G)<1. For Krylov methods, the approximation is selected from x_k\in x_0+\mathcal K_k(A,r_0), using an orthogonality, minimization, or projection condition.
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 5.23
Problem formulation.
Prove the referenced result.
Method.
Use matrix splittings, spectral-radius convergence, Krylov projection, CG/GMRES recurrences, and preconditioning arguments.
Detailed solution and justification.
Split A=D-(L+U), where D is the diagonal part. Jacobi iteration solves the diagonal part exactly: Dx^{(k+1)}=(L+U)x^{(k)}+b. Componentwise, x_i^{(k+1)} = \frac1{a_{ii}} \left( b_i-\sum_{j\ne i}a_{ij}x_j^{(k)} \right). The iteration matrix is G_J=D^{-1}(L+U). Convergence occurs if \rho(G_J)<1.
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 5.24
Problem formulation.
Prove the referenced result.
Method.
Use matrix splittings, spectral-radius convergence, Krylov projection, CG/GMRES recurrences, and preconditioning arguments.
Detailed solution and justification.
With A=D-L-U, Gauss–Seidel uses the newest available components: (D-L)x^{(k+1)}=Ux^{(k)}+b. Componentwise, x_i^{(k+1)} = \frac1{a_{ii}} \left( b_i-\sum_{j<i}a_{ij}x_j^{(k+1)} -\sum_{j>i}a_{ij}x_j^{(k)} \right). The iteration matrix is G_{GS}=(D-L)^{-1}U. It converges whenever \rho(G_{GS})<1; in particular, convergence holds for symmetric positive definite matrices.
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 5.25
Problem formulation.
Prove the necessary condition 0<\omega<2 for SOR convergence.
Method.
Use matrix splittings, spectral-radius convergence, Krylov projection, CG/GMRES recurrences, and preconditioning arguments.
Detailed solution and justification.
An iterative method can be written as x^{(k+1)}=Gx^{(k)}+c. If x_\ast is the fixed point, then e^{(k+1)}=Ge^{(k)}. Therefore e^{(k)}=G^ke^{(0)}. The method converges for every initial guess if and only if \rho(G)<1. For Krylov methods, the approximation is selected from x_k\in x_0+\mathcal K_k(A,r_0), using an orthogonality, minimization, or projection condition.
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 5.26
Problem formulation.
Prove the referenced result.
Method.
Use matrix splittings, spectral-radius convergence, Krylov projection, CG/GMRES recurrences, and preconditioning arguments.
Detailed solution and justification.
An iterative method can be written as x^{(k+1)}=Gx^{(k)}+c. If x_\ast is the fixed point, then e^{(k+1)}=Ge^{(k)}. Therefore e^{(k)}=G^ke^{(0)}. The method converges for every initial guess if and only if \rho(G)<1. For Krylov methods, the approximation is selected from x_k\in x_0+\mathcal K_k(A,r_0), using an orthogonality, minimization, or projection condition.
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 5.27
Problem formulation.
Derive the weighted Jacobi iteration and its iteration matrix.
Method.
Use matrix splittings, spectral-radius convergence, Krylov projection, CG/GMRES recurrences, and preconditioning arguments.
Detailed solution and justification.
Split A=D-(L+U), where D is the diagonal part. Jacobi iteration solves the diagonal part exactly: Dx^{(k+1)}=(L+U)x^{(k)}+b. Componentwise, x_i^{(k+1)} = \frac1{a_{ii}} \left( b_i-\sum_{j\ne i}a_{ij}x_j^{(k)} \right). The iteration matrix is G_J=D^{-1}(L+U). Convergence occurs if \rho(G_J)<1.
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 5.28
Problem formulation.
Use Gershgorin disks to derive a sufficient condition for Jacobi convergence.
Method.
Use matrix splittings, spectral-radius convergence, Krylov projection, CG/GMRES recurrences, and preconditioning arguments.
Detailed solution and justification.
Split A=D-(L+U), where D is the diagonal part. Jacobi iteration solves the diagonal part exactly: Dx^{(k+1)}=(L+U)x^{(k)}+b. Componentwise, x_i^{(k+1)} = \frac1{a_{ii}} \left( b_i-\sum_{j\ne i}a_{ij}x_j^{(k)} \right). The iteration matrix is G_J=D^{-1}(L+U). Convergence occurs if \rho(G_J)<1.
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 5.29
Problem formulation.
Prove the referenced result.
Method.
Use matrix splittings, spectral-radius convergence, Krylov projection, CG/GMRES recurrences, and preconditioning arguments.
Detailed solution and justification.
An iterative method can be written as x^{(k+1)}=Gx^{(k)}+c. If x_\ast is the fixed point, then e^{(k+1)}=Ge^{(k)}. Therefore e^{(k)}=G^ke^{(0)}. The method converges for every initial guess if and only if \rho(G)<1. For Krylov methods, the approximation is selected from x_k\in x_0+\mathcal K_k(A,r_0), using an orthogonality, minimization, or projection condition.
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 5.30
Problem formulation.
Show that every Krylov iterate can be written as x_k=x_0+q_{k-1}(A)r_0.
Method.
Use matrix splittings, spectral-radius convergence, Krylov projection, CG/GMRES recurrences, and preconditioning arguments.
Detailed solution and justification.
An iterative method can be written as x^{(k+1)}=Gx^{(k)}+c. If x_\ast is the fixed point, then e^{(k+1)}=Ge^{(k)}. Therefore e^{(k)}=G^ke^{(0)}. The method converges for every initial guess if and only if \rho(G)<1. For Krylov methods, the approximation is selected from x_k\in x_0+\mathcal K_k(A,r_0), using an orthogonality, minimization, or projection condition.
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 5.31
Problem formulation.
Show that the Krylov residual has the form r_k=p_k(A)r_0, \qquad p_k(0)=1.
Method.
Use matrix splittings, spectral-radius convergence, Krylov projection, CG/GMRES recurrences, and preconditioning arguments.
Detailed solution and justification.
An iterative method can be written as x^{(k+1)}=Gx^{(k)}+c. If x_\ast is the fixed point, then e^{(k+1)}=Ge^{(k)}. Therefore e^{(k)}=G^ke^{(0)}. The method converges for every initial guess if and only if \rho(G)<1. For Krylov methods, the approximation is selected from x_k\in x_0+\mathcal K_k(A,r_0), using an orthogonality, minimization, or projection condition.
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 5.32
Problem formulation.
Derive the CG formula \alpha_k=\frac{r_k^Tr_k}{p_k^TAp_k}.
Method.
Use matrix splittings, spectral-radius convergence, Krylov projection, CG/GMRES recurrences, and preconditioning arguments.
Detailed solution and justification.
For A=A^T\succ0, CG minimizes the quadratic \phi(x)=\frac12x^TAx-b^Tx over successive Krylov spaces. The recurrences are \alpha_k=\frac{r_k^Tr_k}{p_k^TAp_k}, \qquad x_{k+1}=x_k+\alpha_kp_k, r_{k+1}=r_k-\alpha_kAp_k, \beta_k=\frac{r_{k+1}^Tr_{k+1}}{r_k^Tr_k}, \qquad p_{k+1}=r_{k+1}+\beta_kp_k. The directions satisfy p_i^TAp_j=0,\qquad i\ne j. Thus CG reaches the exact solution in at most n steps in exact arithmetic.
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 5.33
Problem formulation.
Derive the Fletcher–Reeves CG coefficient \beta_k=\frac{r_{k+1}^Tr_{k+1}}{r_k^Tr_k}.
Method.
Use matrix splittings, spectral-radius convergence, Krylov projection, CG/GMRES recurrences, and preconditioning arguments.
Detailed solution and justification.
For A=A^T\succ0, CG minimizes the quadratic \phi(x)=\frac12x^TAx-b^Tx over successive Krylov spaces. The recurrences are \alpha_k=\frac{r_k^Tr_k}{p_k^TAp_k}, \qquad x_{k+1}=x_k+\alpha_kp_k, r_{k+1}=r_k-\alpha_kAp_k, \beta_k=\frac{r_{k+1}^Tr_{k+1}}{r_k^Tr_k}, \qquad p_{k+1}=r_{k+1}+\beta_kp_k. The directions satisfy p_i^TAp_j=0,\qquad i\ne j. Thus CG reaches the exact solution in at most n steps in exact arithmetic.
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 5.34
Problem formulation.
Prove that exact-arithmetic CG residuals are mutually orthogonal.
Method.
Use matrix splittings, spectral-radius convergence, Krylov projection, CG/GMRES recurrences, and preconditioning arguments.
Detailed solution and justification.
For A=A^T\succ0, CG minimizes the quadratic \phi(x)=\frac12x^TAx-b^Tx over successive Krylov spaces. The recurrences are \alpha_k=\frac{r_k^Tr_k}{p_k^TAp_k}, \qquad x_{k+1}=x_k+\alpha_kp_k, r_{k+1}=r_k-\alpha_kAp_k, \beta_k=\frac{r_{k+1}^Tr_{k+1}}{r_k^Tr_k}, \qquad p_{k+1}=r_{k+1}+\beta_kp_k. The directions satisfy p_i^TAp_j=0,\qquad i\ne j. Thus CG reaches the exact solution in at most n steps in exact arithmetic.
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 5.35
Problem formulation.
Prove that exact-arithmetic CG search directions are A-conjugate.
Method.
Use matrix splittings, spectral-radius convergence, Krylov projection, CG/GMRES recurrences, and preconditioning arguments.
Detailed solution and justification.
For A=A^T\succ0, CG minimizes the quadratic \phi(x)=\frac12x^TAx-b^Tx over successive Krylov spaces. The recurrences are \alpha_k=\frac{r_k^Tr_k}{p_k^TAp_k}, \qquad x_{k+1}=x_k+\alpha_kp_k, r_{k+1}=r_k-\alpha_kAp_k, \beta_k=\frac{r_{k+1}^Tr_{k+1}}{r_k^Tr_k}, \qquad p_{k+1}=r_{k+1}+\beta_kp_k. The directions satisfy p_i^TAp_j=0,\qquad i\ne j. Thus CG reaches the exact solution in at most n steps in exact arithmetic.
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 5.36
Problem formulation.
Prove the referenced result.
Method.
Use matrix splittings, spectral-radius convergence, Krylov projection, CG/GMRES recurrences, and preconditioning arguments.
Detailed solution and justification.
For A=A^T\succ0, CG minimizes the quadratic \phi(x)=\frac12x^TAx-b^Tx over successive Krylov spaces. The recurrences are \alpha_k=\frac{r_k^Tr_k}{p_k^TAp_k}, \qquad x_{k+1}=x_k+\alpha_kp_k, r_{k+1}=r_k-\alpha_kAp_k, \beta_k=\frac{r_{k+1}^Tr_{k+1}}{r_k^Tr_k}, \qquad p_{k+1}=r_{k+1}+\beta_kp_k. The directions satisfy p_i^TAp_j=0,\qquad i\ne j. Thus CG reaches the exact solution in at most n steps in exact arithmetic.
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 5.37
Problem formulation.
Derive the small least-squares problem in GMRES: \min_y\|\beta e_1-\overline{H}_ky\|_2.
Method.
Use matrix splittings, spectral-radius convergence, Krylov projection, CG/GMRES recurrences, and preconditioning arguments.
Detailed solution and justification.
GMRES seeks an approximation in x_k=x_0+V_ky, where V_k spans the Krylov space \mathcal K_k(A,r_0)= \operatorname{span}\{r_0,Ar_0,\ldots,A^{k-1}r_0\}. Arnoldi gives AV_k=V_{k+1}\overline H_k. The residual is r_k=b-Ax_k=r_0-AV_ky. Since r_0=\beta v_1=V_{k+1}\beta e_1, r_k=V_{k+1}(\beta e_1-\overline H_ky). Because V_{k+1} has orthonormal columns, GMRES solves y_k=\arg\min_y\|\beta e_1-\overline H_ky\|_2.
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 5.38
Problem formulation.
Prove the polynomial characterization of GMRES residuals.
Method.
Use matrix splittings, spectral-radius convergence, Krylov projection, CG/GMRES recurrences, and preconditioning arguments.
Detailed solution and justification.
GMRES seeks an approximation in x_k=x_0+V_ky, where V_k spans the Krylov space \mathcal K_k(A,r_0)= \operatorname{span}\{r_0,Ar_0,\ldots,A^{k-1}r_0\}. Arnoldi gives AV_k=V_{k+1}\overline H_k. The residual is r_k=b-Ax_k=r_0-AV_ky. Since r_0=\beta v_1=V_{k+1}\beta e_1, r_k=V_{k+1}(\beta e_1-\overline H_ky). Because V_{k+1} has orthonormal columns, GMRES solves y_k=\arg\min_y\|\beta e_1-\overline H_ky\|_2.
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 5.39
Problem formulation.
Show that right preconditioning solves AM^{-1}y=b, \qquad x=M^{-1}y.
Method.
Use matrix splittings, spectral-radius convergence, Krylov projection, CG/GMRES recurrences, and preconditioning arguments.
Detailed solution and justification.
An iterative method can be written as x^{(k+1)}=Gx^{(k)}+c. If x_\ast is the fixed point, then e^{(k+1)}=Ge^{(k)}. Therefore e^{(k)}=G^ke^{(0)}. The method converges for every initial guess if and only if \rho(G)<1. For Krylov methods, the approximation is selected from x_k\in x_0+\mathcal K_k(A,r_0), using an orthogonality, minimization, or projection condition.
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 5.40
Problem formulation.
Show that PCG is equivalent to applying CG to M^{-1/2}AM^{-1/2}y=M^{-1/2}b.
Method.
Use matrix splittings, spectral-radius convergence, Krylov projection, CG/GMRES recurrences, and preconditioning arguments.
Detailed solution and justification.
For A=A^T\succ0, CG minimizes the quadratic \phi(x)=\frac12x^TAx-b^Tx over successive Krylov spaces. The recurrences are \alpha_k=\frac{r_k^Tr_k}{p_k^TAp_k}, \qquad x_{k+1}=x_k+\alpha_kp_k, r_{k+1}=r_k-\alpha_kAp_k, \beta_k=\frac{r_{k+1}^Tr_{k+1}}{r_k^Tr_k}, \qquad p_{k+1}=r_{k+1}+\beta_kp_k. The directions satisfy p_i^TAp_j=0,\qquad i\ne j. Thus CG reaches the exact solution in at most n steps in exact arithmetic.
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 5.41
Problem formulation.
Write the algebraic two-grid error-propagation operator.
Method.
Use matrix splittings, spectral-radius convergence, Krylov projection, CG/GMRES recurrences, and preconditioning arguments.
Detailed solution and justification.
An iterative method can be written as x^{(k+1)}=Gx^{(k)}+c. If x_\ast is the fixed point, then e^{(k+1)}=Ge^{(k)}. Therefore e^{(k)}=G^ke^{(0)}. The method converges for every initial guess if and only if \rho(G)<1. For Krylov methods, the approximation is selected from x_k\in x_0+\mathcal K_k(A,r_0), using an orthogonality, minimization, or projection condition.
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 5.42
Problem formulation.
For the one-dimensional Poisson matrix, explain why weighted Jacobi damps high-frequency error components.
Method.
Use matrix splittings, spectral-radius convergence, Krylov projection, CG/GMRES recurrences, and preconditioning arguments.
Detailed solution and justification.
Split A=D-(L+U), where D is the diagonal part. Jacobi iteration solves the diagonal part exactly: Dx^{(k+1)}=(L+U)x^{(k)}+b. Componentwise, x_i^{(k+1)} = \frac1{a_{ii}} \left( b_i-\sum_{j\ne i}a_{ij}x_j^{(k)} \right). The iteration matrix is G_J=D^{-1}(L+U). Convergence occurs if \rho(G_J)<1.
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 5.43
Problem formulation.
Explain how rounding errors create a gap between recursive and true residuals.
Method.
Use matrix splittings, spectral-radius convergence, Krylov projection, CG/GMRES recurrences, and preconditioning arguments.
Detailed solution and justification.
An iterative method can be written as x^{(k+1)}=Gx^{(k)}+c. If x_\ast is the fixed point, then e^{(k+1)}=Ge^{(k)}. Therefore e^{(k)}=G^ke^{(0)}. The method converges for every initial guess if and only if \rho(G)<1. For Krylov methods, the approximation is selected from x_k\in x_0+\mathcal K_k(A,r_0), using an orthogonality, minimization, or projection condition.
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 5.44
Problem formulation.
Give two reasons why an iterative method may stagnate in finite precision.
Method.
Use matrix splittings, spectral-radius convergence, Krylov projection, CG/GMRES recurrences, and preconditioning arguments.
Detailed solution and justification.
An iterative method can be written as x^{(k+1)}=Gx^{(k)}+c. If x_\ast is the fixed point, then e^{(k+1)}=Ge^{(k)}. Therefore e^{(k)}=G^ke^{(0)}. The method converges for every initial guess if and only if \rho(G)<1. For Krylov methods, the approximation is selected from x_k\in x_0+\mathcal K_k(A,r_0), using an orthogonality, minimization, or projection condition.
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 5.45
Problem formulation.
Design a robust stopping test using both relative residual and relative update size.
Method.
Use matrix splittings, spectral-radius convergence, Krylov projection, CG/GMRES recurrences, and preconditioning arguments.
Detailed solution and justification.
An iterative method can be written as x^{(k+1)}=Gx^{(k)}+c. If x_\ast is the fixed point, then e^{(k+1)}=Ge^{(k)}. Therefore e^{(k)}=G^ke^{(0)}. The method converges for every initial guess if and only if \rho(G)<1. For Krylov methods, the approximation is selected from x_k\in x_0+\mathcal K_k(A,r_0), using an orthogonality, minimization, or projection condition.
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 5.46
Problem formulation.
Prove the spectral-radius theorem using Jordan canonical form.
Method.
Use matrix splittings, spectral-radius convergence, Krylov projection, CG/GMRES recurrences, and preconditioning arguments.
Detailed solution and justification.
An iterative method can be written as x^{(k+1)}=Gx^{(k)}+c. If x_\ast is the fixed point, then e^{(k+1)}=Ge^{(k)}. Therefore e^{(k)}=G^ke^{(0)}. The method converges for every initial guess if and only if \rho(G)<1. For Krylov methods, the approximation is selected from x_k\in x_0+\mathcal K_k(A,r_0), using an orthogonality, minimization, or projection condition.
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 5.47
Problem formulation.
Prove or carefully justify the use of Gelfand’s formula \rho(B)=\lim_{k\to\infty}\|B^k\|^{1/k}.
Method.
Use matrix splittings, spectral-radius convergence, Krylov projection, CG/GMRES recurrences, and preconditioning arguments.
Detailed solution and justification.
An iterative method can be written as x^{(k+1)}=Gx^{(k)}+c. If x_\ast is the fixed point, then e^{(k+1)}=Ge^{(k)}. Therefore e^{(k)}=G^ke^{(0)}. The method converges for every initial guess if and only if \rho(G)<1. For Krylov methods, the approximation is selected from x_k\in x_0+\mathcal K_k(A,r_0), using an orthogonality, minimization, or projection condition.
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 5.48
Problem formulation.
Study convergence of Jacobi and Gauss–Seidel for nonsingular M-matrices.
Method.
Use matrix splittings, spectral-radius convergence, Krylov projection, CG/GMRES recurrences, and preconditioning arguments.
Detailed solution and justification.
Split A=D-(L+U), where D is the diagonal part. Jacobi iteration solves the diagonal part exactly: Dx^{(k+1)}=(L+U)x^{(k)}+b. Componentwise, x_i^{(k+1)} = \frac1{a_{ii}} \left( b_i-\sum_{j\ne i}a_{ij}x_j^{(k)} \right). The iteration matrix is G_J=D^{-1}(L+U). Convergence occurs if \rho(G_J)<1.
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 5.49
Problem formulation.
Define consistently ordered matrices and derive the classical optimal SOR parameter formula in terms of \rho(B_J).
Method.
Use matrix splittings, spectral-radius convergence, Krylov projection, CG/GMRES recurrences, and preconditioning arguments.
Detailed solution and justification.
An iterative method can be written as x^{(k+1)}=Gx^{(k)}+c. If x_\ast is the fixed point, then e^{(k+1)}=Ge^{(k)}. Therefore e^{(k)}=G^ke^{(0)}. The method converges for every initial guess if and only if \rho(G)<1. For Krylov methods, the approximation is selected from x_k\in x_0+\mathcal K_k(A,r_0), using an orthogonality, minimization, or projection condition.
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 5.50
Problem formulation.
State and prove Young’s theorem for SOR convergence under standard assumptions.
Method.
Use matrix splittings, spectral-radius convergence, Krylov projection, CG/GMRES recurrences, and preconditioning arguments.
Detailed solution and justification.
An iterative method can be written as x^{(k+1)}=Gx^{(k)}+c. If x_\ast is the fixed point, then e^{(k+1)}=Ge^{(k)}. Therefore e^{(k)}=G^ke^{(0)}. The method converges for every initial guess if and only if \rho(G)<1. For Krylov methods, the approximation is selected from x_k\in x_0+\mathcal K_k(A,r_0), using an orthogonality, minimization, or projection condition.
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 5.51
Problem formulation.
Derive the SSOR preconditioner and explain why it is symmetric positive definite under suitable assumptions.
Method.
Use matrix splittings, spectral-radius convergence, Krylov projection, CG/GMRES recurrences, and preconditioning arguments.
Detailed solution and justification.
An iterative method can be written as x^{(k+1)}=Gx^{(k)}+c. If x_\ast is the fixed point, then e^{(k+1)}=Ge^{(k)}. Therefore e^{(k)}=G^ke^{(0)}. The method converges for every initial guess if and only if \rho(G)<1. For Krylov methods, the approximation is selected from x_k\in x_0+\mathcal K_k(A,r_0), using an orthogonality, minimization, or projection condition.
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 5.52
Problem formulation.
Derive Chebyshev semi-iteration for SPD systems when eigenvalue bounds are known.
Method.
Use matrix splittings, spectral-radius convergence, Krylov projection, CG/GMRES recurrences, and preconditioning arguments.
Detailed solution and justification.
An iterative method can be written as x^{(k+1)}=Gx^{(k)}+c. If x_\ast is the fixed point, then e^{(k+1)}=Ge^{(k)}. Therefore e^{(k)}=G^ke^{(0)}. The method converges for every initial guess if and only if \rho(G)<1. For Krylov methods, the approximation is selected from x_k\in x_0+\mathcal K_k(A,r_0), using an orthogonality, minimization, or projection condition.
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 5.53
Problem formulation.
Derive steepest descent for SPD linear systems and compare its convergence factor with CG.
Method.
Use matrix splittings, spectral-radius convergence, Krylov projection, CG/GMRES recurrences, and preconditioning arguments.
Detailed solution and justification.
For A=A^T\succ0, CG minimizes the quadratic \phi(x)=\frac12x^TAx-b^Tx over successive Krylov spaces. The recurrences are \alpha_k=\frac{r_k^Tr_k}{p_k^TAp_k}, \qquad x_{k+1}=x_k+\alpha_kp_k, r_{k+1}=r_k-\alpha_kAp_k, \beta_k=\frac{r_{k+1}^Tr_{k+1}}{r_k^Tr_k}, \qquad p_{k+1}=r_{k+1}+\beta_kp_k. The directions satisfy p_i^TAp_j=0,\qquad i\ne j. Thus CG reaches the exact solution in at most n steps in exact arithmetic.
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 5.54
Problem formulation.
Prove the referenced result in full detail.
Method.
Use matrix splittings, spectral-radius convergence, Krylov projection, CG/GMRES recurrences, and preconditioning arguments.
Detailed solution and justification.
For A=A^T\succ0, CG minimizes the quadratic \phi(x)=\frac12x^TAx-b^Tx over successive Krylov spaces. The recurrences are \alpha_k=\frac{r_k^Tr_k}{p_k^TAp_k}, \qquad x_{k+1}=x_k+\alpha_kp_k, r_{k+1}=r_k-\alpha_kAp_k, \beta_k=\frac{r_{k+1}^Tr_{k+1}}{r_k^Tr_k}, \qquad p_{k+1}=r_{k+1}+\beta_kp_k. The directions satisfy p_i^TAp_j=0,\qquad i\ne j. Thus CG reaches the exact solution in at most n steps in exact arithmetic.
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 5.55
Problem formulation.
Explain why CG may converge much faster than the condition-number bound when eigenvalues are clustered.
Method.
Use matrix splittings, spectral-radius convergence, Krylov projection, CG/GMRES recurrences, and preconditioning arguments.
Detailed solution and justification.
For A=A^T\succ0, CG minimizes the quadratic \phi(x)=\frac12x^TAx-b^Tx over successive Krylov spaces. The recurrences are \alpha_k=\frac{r_k^Tr_k}{p_k^TAp_k}, \qquad x_{k+1}=x_k+\alpha_kp_k, r_{k+1}=r_k-\alpha_kAp_k, \beta_k=\frac{r_{k+1}^Tr_{k+1}}{r_k^Tr_k}, \qquad p_{k+1}=r_{k+1}+\beta_kp_k. The directions satisfy p_i^TAp_j=0,\qquad i\ne j. Thus CG reaches the exact solution in at most n steps in exact arithmetic.
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 5.56
Problem formulation.
Derive the Lanczos three-term recurrence from Arnoldi for symmetric matrices.
Method.
Use matrix splittings, spectral-radius convergence, Krylov projection, CG/GMRES recurrences, and preconditioning arguments.
Detailed solution and justification.
An iterative method can be written as x^{(k+1)}=Gx^{(k)}+c. If x_\ast is the fixed point, then e^{(k+1)}=Ge^{(k)}. Therefore e^{(k)}=G^ke^{(0)}. The method converges for every initial guess if and only if \rho(G)<1. For Krylov methods, the approximation is selected from x_k\in x_0+\mathcal K_k(A,r_0), using an orthogonality, minimization, or projection condition.
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 5.57
Problem formulation.
Derive the MINRES minimization property for symmetric indefinite systems.
Method.
Use matrix splittings, spectral-radius convergence, Krylov projection, CG/GMRES recurrences, and preconditioning arguments.
Detailed solution and justification.
An iterative method can be written as x^{(k+1)}=Gx^{(k)}+c. If x_\ast is the fixed point, then e^{(k+1)}=Ge^{(k)}. Therefore e^{(k)}=G^ke^{(0)}. The method converges for every initial guess if and only if \rho(G)<1. For Krylov methods, the approximation is selected from x_k\in x_0+\mathcal K_k(A,r_0), using an orthogonality, minimization, or projection condition.
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 5.58
Problem formulation.
For normal A, bound GMRES convergence using polynomial approximation on the spectrum.
Method.
Use matrix splittings, spectral-radius convergence, Krylov projection, CG/GMRES recurrences, and preconditioning arguments.
Detailed solution and justification.
GMRES seeks an approximation in x_k=x_0+V_ky, where V_k spans the Krylov space \mathcal K_k(A,r_0)= \operatorname{span}\{r_0,Ar_0,\ldots,A^{k-1}r_0\}. Arnoldi gives AV_k=V_{k+1}\overline H_k. The residual is r_k=b-Ax_k=r_0-AV_ky. Since r_0=\beta v_1=V_{k+1}\beta e_1, r_k=V_{k+1}(\beta e_1-\overline H_ky). Because V_{k+1} has orthonormal columns, GMRES solves y_k=\arg\min_y\|\beta e_1-\overline H_ky\|_2.
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 5.59
Problem formulation.
Define the field of values and explain how it can be used to estimate GMRES convergence.
Method.
Use matrix splittings, spectral-radius convergence, Krylov projection, CG/GMRES recurrences, and preconditioning arguments.
Detailed solution and justification.
GMRES seeks an approximation in x_k=x_0+V_ky, where V_k spans the Krylov space \mathcal K_k(A,r_0)= \operatorname{span}\{r_0,Ar_0,\ldots,A^{k-1}r_0\}. Arnoldi gives AV_k=V_{k+1}\overline H_k. The residual is r_k=b-Ax_k=r_0-AV_ky. Since r_0=\beta v_1=V_{k+1}\beta e_1, r_k=V_{k+1}(\beta e_1-\overline H_ky). Because V_{k+1} has orthonormal columns, GMRES solves y_k=\arg\min_y\|\beta e_1-\overline H_ky\|_2.
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 5.60
Problem formulation.
Construct an example or explanation showing why restarted GMRES may stagnate.
Method.
Use matrix splittings, spectral-radius convergence, Krylov projection, CG/GMRES recurrences, and preconditioning arguments.
Detailed solution and justification.
GMRES seeks an approximation in x_k=x_0+V_ky, where V_k spans the Krylov space \mathcal K_k(A,r_0)= \operatorname{span}\{r_0,Ar_0,\ldots,A^{k-1}r_0\}. Arnoldi gives AV_k=V_{k+1}\overline H_k. The residual is r_k=b-Ax_k=r_0-AV_ky. Since r_0=\beta v_1=V_{k+1}\beta e_1, r_k=V_{k+1}(\beta e_1-\overline H_ky). Because V_{k+1} has orthonormal columns, GMRES solves y_k=\arg\min_y\|\beta e_1-\overline H_ky\|_2.
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 5.61
Problem formulation.
Derive the BiCG method from coupled Krylov subspaces for A and A^T.
Method.
Use matrix splittings, spectral-radius convergence, Krylov projection, CG/GMRES recurrences, and preconditioning arguments.
Detailed solution and justification.
For A=A^T\succ0, CG minimizes the quadratic \phi(x)=\frac12x^TAx-b^Tx over successive Krylov spaces. The recurrences are \alpha_k=\frac{r_k^Tr_k}{p_k^TAp_k}, \qquad x_{k+1}=x_k+\alpha_kp_k, r_{k+1}=r_k-\alpha_kAp_k, \beta_k=\frac{r_{k+1}^Tr_{k+1}}{r_k^Tr_k}, \qquad p_{k+1}=r_{k+1}+\beta_kp_k. The directions satisfy p_i^TAp_j=0,\qquad i\ne j. Thus CG reaches the exact solution in at most n steps in exact arithmetic.
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 5.62
Problem formulation.
Explain the stabilization idea behind BiCGSTAB and compare it with BiCG.
Method.
Use matrix splittings, spectral-radius convergence, Krylov projection, CG/GMRES recurrences, and preconditioning arguments.
Detailed solution and justification.
For A=A^T\succ0, CG minimizes the quadratic \phi(x)=\frac12x^TAx-b^Tx over successive Krylov spaces. The recurrences are \alpha_k=\frac{r_k^Tr_k}{p_k^TAp_k}, \qquad x_{k+1}=x_k+\alpha_kp_k, r_{k+1}=r_k-\alpha_kAp_k, \beta_k=\frac{r_{k+1}^Tr_{k+1}}{r_k^Tr_k}, \qquad p_{k+1}=r_{k+1}+\beta_kp_k. The directions satisfy p_i^TAp_j=0,\qquad i\ne j. Thus CG reaches the exact solution in at most n steps in exact arithmetic.
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 5.63
Problem formulation.
Define ILU(0) and explain how it differs from exact LU factorization.
Method.
Use matrix splittings, spectral-radius convergence, Krylov projection, CG/GMRES recurrences, and preconditioning arguments.
Detailed solution and justification.
An iterative method can be written as x^{(k+1)}=Gx^{(k)}+c. If x_\ast is the fixed point, then e^{(k+1)}=Ge^{(k)}. Therefore e^{(k)}=G^ke^{(0)}. The method converges for every initial guess if and only if \rho(G)<1. For Krylov methods, the approximation is selected from x_k\in x_0+\mathcal K_k(A,r_0), using an orthogonality, minimization, or projection condition.
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 5.64
Problem formulation.
Describe incomplete Cholesky preconditioning for SPD systems and discuss breakdown.
Method.
Use matrix splittings, spectral-radius convergence, Krylov projection, CG/GMRES recurrences, and preconditioning arguments.
Detailed solution and justification.
An iterative method can be written as x^{(k+1)}=Gx^{(k)}+c. If x_\ast is the fixed point, then e^{(k+1)}=Ge^{(k)}. Therefore e^{(k)}=G^ke^{(0)}. The method converges for every initial guess if and only if \rho(G)<1. For Krylov methods, the approximation is selected from x_k\in x_0+\mathcal K_k(A,r_0), using an orthogonality, minimization, or projection condition.
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 5.65
Problem formulation.
Explain additive Schwarz preconditioning from a domain-decomposition perspective.
Method.
Use matrix splittings, spectral-radius convergence, Krylov projection, CG/GMRES recurrences, and preconditioning arguments.
Detailed solution and justification.
An iterative method can be written as x^{(k+1)}=Gx^{(k)}+c. If x_\ast is the fixed point, then e^{(k+1)}=Ge^{(k)}. Therefore e^{(k)}=G^ke^{(0)}. The method converges for every initial guess if and only if \rho(G)<1. For Krylov methods, the approximation is selected from x_k\in x_0+\mathcal K_k(A,r_0), using an orthogonality, minimization, or projection condition.
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 5.66
Problem formulation.
Explain the difference between geometric multigrid and algebraic multigrid.
Method.
Use matrix splittings, spectral-radius convergence, Krylov projection, CG/GMRES recurrences, and preconditioning arguments.
Detailed solution and justification.
An iterative method can be written as x^{(k+1)}=Gx^{(k)}+c. If x_\ast is the fixed point, then e^{(k+1)}=Ge^{(k)}. Therefore e^{(k)}=G^ke^{(0)}. The method converges for every initial guess if and only if \rho(G)<1. For Krylov methods, the approximation is selected from x_k\in x_0+\mathcal K_k(A,r_0), using an orthogonality, minimization, or projection condition.
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 5.67
Problem formulation.
Derive a two-grid convergence estimate from smoothing and approximation properties.
Method.
Use matrix splittings, spectral-radius convergence, Krylov projection, CG/GMRES recurrences, and preconditioning arguments.
Detailed solution and justification.
An iterative method can be written as x^{(k+1)}=Gx^{(k)}+c. If x_\ast is the fixed point, then e^{(k+1)}=Ge^{(k)}. Therefore e^{(k)}=G^ke^{(0)}. The method converges for every initial guess if and only if \rho(G)<1. For Krylov methods, the approximation is selected from x_k\in x_0+\mathcal K_k(A,r_0), using an orthogonality, minimization, or projection condition.
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 5.68
Problem formulation.
Use local Fourier analysis to study weighted Jacobi smoothing for the one-dimensional Poisson equation.
Method.
Use matrix splittings, spectral-radius convergence, Krylov projection, CG/GMRES recurrences, and preconditioning arguments.
Detailed solution and justification.
Split A=D-(L+U), where D is the diagonal part. Jacobi iteration solves the diagonal part exactly: Dx^{(k+1)}=(L+U)x^{(k)}+b. Componentwise, x_i^{(k+1)} = \frac1{a_{ii}} \left( b_i-\sum_{j\ne i}a_{ij}x_j^{(k)} \right). The iteration matrix is G_J=D^{-1}(L+U). Convergence occurs if \rho(G_J)<1.
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 5.69
Problem formulation.
Derive the Kaczmarz method as successive orthogonal projections onto hyperplanes.
Method.
Use matrix splittings, spectral-radius convergence, Krylov projection, CG/GMRES recurrences, and preconditioning arguments.
Detailed solution and justification.
An iterative method can be written as x^{(k+1)}=Gx^{(k)}+c. If x_\ast is the fixed point, then e^{(k+1)}=Ge^{(k)}. Therefore e^{(k)}=G^ke^{(0)}. The method converges for every initial guess if and only if \rho(G)<1. For Krylov methods, the approximation is selected from x_k\in x_0+\mathcal K_k(A,r_0), using an orthogonality, minimization, or projection condition.
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 5.70
Problem formulation.
State and prove a basic expected convergence estimate for randomized Kaczmarz.
Method.
Use matrix splittings, spectral-radius convergence, Krylov projection, CG/GMRES recurrences, and preconditioning arguments.
Detailed solution and justification.
An iterative method can be written as x^{(k+1)}=Gx^{(k)}+c. If x_\ast is the fixed point, then e^{(k+1)}=Ge^{(k)}. Therefore e^{(k)}=G^ke^{(0)}. The method converges for every initial guess if and only if \rho(G)<1. For Krylov methods, the approximation is selected from x_k\in x_0+\mathcal K_k(A,r_0), using an orthogonality, minimization, or projection condition.
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 5.71
Problem formulation.
Analyze loss of orthogonality and delayed convergence in finite-precision CG.
Method.
Use matrix splittings, spectral-radius convergence, Krylov projection, CG/GMRES recurrences, and preconditioning arguments.
Detailed solution and justification.
For A=A^T\succ0, CG minimizes the quadratic \phi(x)=\frac12x^TAx-b^Tx over successive Krylov spaces. The recurrences are \alpha_k=\frac{r_k^Tr_k}{p_k^TAp_k}, \qquad x_{k+1}=x_k+\alpha_kp_k, r_{k+1}=r_k-\alpha_kAp_k, \beta_k=\frac{r_{k+1}^Tr_{k+1}}{r_k^Tr_k}, \qquad p_{k+1}=r_{k+1}+\beta_kp_k. The directions satisfy p_i^TAp_j=0,\qquad i\ne j. Thus CG reaches the exact solution in at most n steps in exact arithmetic.
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 5.72
Problem formulation.
Study residual replacement strategies in Krylov methods and explain when they improve robustness.
Method.
Use matrix splittings, spectral-radius convergence, Krylov projection, CG/GMRES recurrences, and preconditioning arguments.
Detailed solution and justification.
An iterative method can be written as x^{(k+1)}=Gx^{(k)}+c. If x_\ast is the fixed point, then e^{(k+1)}=Ge^{(k)}. Therefore e^{(k)}=G^ke^{(0)}. The method converges for every initial guess if and only if \rho(G)<1. For Krylov methods, the approximation is selected from x_k\in x_0+\mathcal K_k(A,r_0), using an orthogonality, minimization, or projection condition.
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 5.73
Problem formulation.
Derive flexible GMRES for variable preconditioners and explain why ordinary GMRES formulas are insufficient.
Method.
Use matrix splittings, spectral-radius convergence, Krylov projection, CG/GMRES recurrences, and preconditioning arguments.
Detailed solution and justification.
GMRES seeks an approximation in x_k=x_0+V_ky, where V_k spans the Krylov space \mathcal K_k(A,r_0)= \operatorname{span}\{r_0,Ar_0,\ldots,A^{k-1}r_0\}. Arnoldi gives AV_k=V_{k+1}\overline H_k. The residual is r_k=b-Ax_k=r_0-AV_ky. Since r_0=\beta v_1=V_{k+1}\beta e_1, r_k=V_{k+1}(\beta e_1-\overline H_ky). Because V_{k+1} has orthonormal columns, GMRES solves y_k=\arg\min_y\|\beta e_1-\overline H_ky\|_2.
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 5.74
Problem formulation.
Study deflated CG or GMRES and explain how removing troublesome eigencomponents accelerates convergence.
Method.
Use matrix splittings, spectral-radius convergence, Krylov projection, CG/GMRES recurrences, and preconditioning arguments.
Detailed solution and justification.
For A=A^T\succ0, CG minimizes the quadratic \phi(x)=\frac12x^TAx-b^Tx over successive Krylov spaces. The recurrences are \alpha_k=\frac{r_k^Tr_k}{p_k^TAp_k}, \qquad x_{k+1}=x_k+\alpha_kp_k, r_{k+1}=r_k-\alpha_kAp_k, \beta_k=\frac{r_{k+1}^Tr_{k+1}}{r_k^Tr_k}, \qquad p_{k+1}=r_{k+1}+\beta_kp_k. The directions satisfy p_i^TAp_j=0,\qquad i\ne j. Thus CG reaches the exact solution in at most n steps in exact arithmetic.
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 5.75
Problem formulation.
Analyze Krylov subspace recycling for sequences of slowly varying linear systems.
Method.
Use matrix splittings, spectral-radius convergence, Krylov projection, CG/GMRES recurrences, and preconditioning arguments.
Detailed solution and justification.
An iterative method can be written as x^{(k+1)}=Gx^{(k)}+c. If x_\ast is the fixed point, then e^{(k+1)}=Ge^{(k)}. Therefore e^{(k)}=G^ke^{(0)}. The method converges for every initial guess if and only if \rho(G)<1. For Krylov methods, the approximation is selected from x_k\in x_0+\mathcal K_k(A,r_0), using an orthogonality, minimization, or projection condition.
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 5.76
Problem formulation.
Design a polynomial preconditioner and analyze its effect on the residual polynomial.
Method.
Use matrix splittings, spectral-radius convergence, Krylov projection, CG/GMRES recurrences, and preconditioning arguments.
Detailed solution and justification.
An iterative method can be written as x^{(k+1)}=Gx^{(k)}+c. If x_\ast is the fixed point, then e^{(k+1)}=Ge^{(k)}. Therefore e^{(k)}=G^ke^{(0)}. The method converges for every initial guess if and only if \rho(G)<1. For Krylov methods, the approximation is selected from x_k\in x_0+\mathcal K_k(A,r_0), using an orthogonality, minimization, or projection condition.
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 5.77
Problem formulation.
Prove an optimal O(n) complexity estimate for a model multigrid method under standard smoothing and approximation assumptions.
Method.
Use matrix splittings, spectral-radius convergence, Krylov projection, CG/GMRES recurrences, and preconditioning arguments.
Detailed solution and justification.
An iterative method can be written as x^{(k+1)}=Gx^{(k)}+c. If x_\ast is the fixed point, then e^{(k+1)}=Ge^{(k)}. Therefore e^{(k)}=G^ke^{(0)}. The method converges for every initial guess if and only if \rho(G)<1. For Krylov methods, the approximation is selected from x_k\in x_0+\mathcal K_k(A,r_0), using an orthogonality, minimization, or projection condition.
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 5.78
Problem formulation.
Study strength-of-connection measures in algebraic multigrid and explain their role in coarsening.
Method.
Use matrix splittings, spectral-radius convergence, Krylov projection, CG/GMRES recurrences, and preconditioning arguments.
Detailed solution and justification.
An iterative method can be written as x^{(k+1)}=Gx^{(k)}+c. If x_\ast is the fixed point, then e^{(k+1)}=Ge^{(k)}. Therefore e^{(k)}=G^ke^{(0)}. The method converges for every initial guess if and only if \rho(G)<1. For Krylov methods, the approximation is selected from x_k\in x_0+\mathcal K_k(A,r_0), using an orthogonality, minimization, or projection condition.
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 5.79
Problem formulation.
Explain smoothed aggregation AMG and compare it with classical AMG.
Method.
Use matrix splittings, spectral-radius convergence, Krylov projection, CG/GMRES recurrences, and preconditioning arguments.
Detailed solution and justification.
An iterative method can be written as x^{(k+1)}=Gx^{(k)}+c. If x_\ast is the fixed point, then e^{(k+1)}=Ge^{(k)}. Therefore e^{(k)}=G^ke^{(0)}. The method converges for every initial guess if and only if \rho(G)<1. For Krylov methods, the approximation is selected from x_k\in x_0+\mathcal K_k(A,r_0), using an orthogonality, minimization, or projection condition.
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 5.80
Problem formulation.
Develop block preconditioners for saddle-point systems and analyze the spectra of the preconditioned operators.
Method.
Use matrix splittings, spectral-radius convergence, Krylov projection, CG/GMRES recurrences, and preconditioning arguments.
Detailed solution and justification.
An iterative method can be written as x^{(k+1)}=Gx^{(k)}+c. If x_\ast is the fixed point, then e^{(k+1)}=Ge^{(k)}. Therefore e^{(k)}=G^ke^{(0)}. The method converges for every initial guess if and only if \rho(G)<1. For Krylov methods, the approximation is selected from x_k\in x_0+\mathcal K_k(A,r_0), using an orthogonality, minimization, or projection condition.
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 5.81
Problem formulation.
Study Schur-complement preconditioners for block systems and derive spectral equivalence conditions.
Method.
Use matrix splittings, spectral-radius convergence, Krylov projection, CG/GMRES recurrences, and preconditioning arguments.
Detailed solution and justification.
An iterative method can be written as x^{(k+1)}=Gx^{(k)}+c. If x_\ast is the fixed point, then e^{(k+1)}=Ge^{(k)}. Therefore e^{(k)}=G^ke^{(0)}. The method converges for every initial guess if and only if \rho(G)<1. For Krylov methods, the approximation is selected from x_k\in x_0+\mathcal K_k(A,r_0), using an orthogonality, minimization, or projection condition.
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 5.82
Problem formulation.
State and prove a condition-number estimate for an additive Schwarz preconditioner.
Method.
Use matrix splittings, spectral-radius convergence, Krylov projection, CG/GMRES recurrences, and preconditioning arguments.
Detailed solution and justification.
An iterative method can be written as x^{(k+1)}=Gx^{(k)}+c. If x_\ast is the fixed point, then e^{(k+1)}=Ge^{(k)}. Therefore e^{(k)}=G^ke^{(0)}. The method converges for every initial guess if and only if \rho(G)<1. For Krylov methods, the approximation is selected from x_k\in x_0+\mathcal K_k(A,r_0), using an orthogonality, minimization, or projection condition.
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 5.83
Problem formulation.
Investigate communication-avoiding Krylov methods and explain the stability tradeoffs caused by enlarged bases.
Method.
Use matrix splittings, spectral-radius convergence, Krylov projection, CG/GMRES recurrences, and preconditioning arguments.
Detailed solution and justification.
An iterative method can be written as x^{(k+1)}=Gx^{(k)}+c. If x_\ast is the fixed point, then e^{(k+1)}=Ge^{(k)}. Therefore e^{(k)}=G^ke^{(0)}. The method converges for every initial guess if and only if \rho(G)<1. For Krylov methods, the approximation is selected from x_k\in x_0+\mathcal K_k(A,r_0), using an orthogonality, minimization, or projection condition.
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 5.84
Problem formulation.
Study pipelined CG or GMRES and analyze the effect of overlapping communication and computation.
Method.
Use matrix splittings, spectral-radius convergence, Krylov projection, CG/GMRES recurrences, and preconditioning arguments.
Detailed solution and justification.
For A=A^T\succ0, CG minimizes the quadratic \phi(x)=\frac12x^TAx-b^Tx over successive Krylov spaces. The recurrences are \alpha_k=\frac{r_k^Tr_k}{p_k^TAp_k}, \qquad x_{k+1}=x_k+\alpha_kp_k, r_{k+1}=r_k-\alpha_kAp_k, \beta_k=\frac{r_{k+1}^Tr_{k+1}}{r_k^Tr_k}, \qquad p_{k+1}=r_{k+1}+\beta_kp_k. The directions satisfy p_i^TAp_j=0,\qquad i\ne j. Thus CG reaches the exact solution in at most n steps in exact arithmetic.
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 5.85
Problem formulation.
Analyze mixed-precision Krylov methods with low-precision preconditioning and high-precision residual correction.
Method.
Use matrix splittings, spectral-radius convergence, Krylov projection, CG/GMRES recurrences, and preconditioning arguments.
Detailed solution and justification.
An iterative method can be written as x^{(k+1)}=Gx^{(k)}+c. If x_\ast is the fixed point, then e^{(k+1)}=Ge^{(k)}. Therefore e^{(k)}=G^ke^{(0)}. The method converges for every initial guess if and only if \rho(G)<1. For Krylov methods, the approximation is selected from x_k\in x_0+\mathcal K_k(A,r_0), using an orthogonality, minimization, or projection condition.
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 5.86
Problem formulation.
Study randomized sketching as a preconditioner for least-squares or linear systems.
Method.
Use matrix splittings, spectral-radius convergence, Krylov projection, CG/GMRES recurrences, and preconditioning arguments.
Detailed solution and justification.
An iterative method can be written as x^{(k+1)}=Gx^{(k)}+c. If x_\ast is the fixed point, then e^{(k+1)}=Ge^{(k)}. Therefore e^{(k)}=G^ke^{(0)}. The method converges for every initial guess if and only if \rho(G)<1. For Krylov methods, the approximation is selected from x_k\in x_0+\mathcal K_k(A,r_0), using an orthogonality, minimization, or projection condition.
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 5.87
Problem formulation.
Explain how Krylov methods are used inside Newton’s method for nonlinear systems. Analyze forcing terms and preconditioning.
Method.
Use matrix splittings, spectral-radius convergence, Krylov projection, CG/GMRES recurrences, and preconditioning arguments.
Detailed solution and justification.
An iterative method can be written as x^{(k+1)}=Gx^{(k)}+c. If x_\ast is the fixed point, then e^{(k+1)}=Ge^{(k)}. Therefore e^{(k)}=G^ke^{(0)}. The method converges for every initial guess if and only if \rho(G)<1. For Krylov methods, the approximation is selected from x_k\in x_0+\mathcal K_k(A,r_0), using an orthogonality, minimization, or projection condition.
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 5.88
Problem formulation.
For the finite-difference Poisson equation in two dimensions, compare Jacobi, Gauss–Seidel, CG, PCG, and multigrid in terms of asymptotic complexity.
Method.
Use matrix splittings, spectral-radius convergence, Krylov projection, CG/GMRES recurrences, and preconditioning arguments.
Detailed solution and justification.
Split A=D-(L+U), where D is the diagonal part. Jacobi iteration solves the diagonal part exactly: Dx^{(k+1)}=(L+U)x^{(k)}+b. Componentwise, x_i^{(k+1)} = \frac1{a_{ii}} \left( b_i-\sum_{j\ne i}a_{ij}x_j^{(k)} \right). The iteration matrix is G_J=D^{-1}(L+U). Convergence occurs if \rho(G_J)<1.
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 5.89
Problem formulation.
Design stopping criteria for Krylov methods that account for conditioning, residual gaps, and backward error.
Method.
Use matrix splittings, spectral-radius convergence, Krylov projection, CG/GMRES recurrences, and preconditioning arguments.
Detailed solution and justification.
An iterative method can be written as x^{(k+1)}=Gx^{(k)}+c. If x_\ast is the fixed point, then e^{(k+1)}=Ge^{(k)}. Therefore e^{(k)}=G^ke^{(0)}. The method converges for every initial guess if and only if \rho(G)<1. For Krylov methods, the approximation is selected from x_k\in x_0+\mathcal K_k(A,r_0), using an orthogonality, minimization, or projection condition.
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 5.90
Problem formulation.
Discuss reproducibility challenges for parallel iterative solvers and propose strategies for deterministic reductions.
Method.
Use matrix splittings, spectral-radius convergence, Krylov projection, CG/GMRES recurrences, and preconditioning arguments.
Detailed solution and justification.
An iterative method can be written as x^{(k+1)}=Gx^{(k)}+c. If x_\ast is the fixed point, then e^{(k+1)}=Ge^{(k)}. Therefore e^{(k)}=G^ke^{(0)}. The method converges for every initial guess if and only if \rho(G)<1. For Krylov methods, the approximation is selected from x_k\in x_0+\mathcal K_k(A,r_0), using an orthogonality, minimization, or projection condition.
Conclusion.
The displayed derivation gives the requested formula, proof, or computation. The final expression should be checked against the assumptions and notation of the corresponding chapter.
Diagnostic comment.
The formula should be verified by substitution into the defining equation and, when possible, by a small numerical test.
Interactive tools
The theory and solutions come first. These tools are for review, laboratories, games, memory cards, and randomized assessment.