Numerical Methods · Linear systems, least squares, and eigenproblems
Two conjugate-gradient steps close an SPD two-by-two residual
Problem
Numerical Methods practice problemLetand consider the linear system in exact arithmetic. The conjugate-gradient iteration from isstopping when .
1. Prove that is symmetric positive definite by leading minors (or by eigenvalues). Compute those eigenvalues as .
2. Starting from , compute , , , , , , , , , and as exact rationals. Verify .
3. Verify the two identities and . Then use the stated exact-arithmetic CG orthogonality theorem to explain why a general SPD problem terminates with after at most steps.
4. Audit both sentences: (i) "CG is just steepest descent, so the next search direction is and may be ignored"; (ii) "the residuals are -orthogonal, while the search directions are Euclidean-orthogonal." Compute the rejected steepest-descent vector and show that it is not -orthogonal to .
Do not factor by Gaussian elimination, and do not replace the iteration by a nonlinear Newton update.
Hint
HintThe leading minors of are and . The residual is itself because .
Check your work
Work the problem yourself first. Then open it in Training to check your answer and read the full worked solution.
The answer check and full solution for this problem come with ProofAnvil Practice membership ($19 USD monthly). See membership. Or start with the free Numerical Methods sample problem: Try the free sample problem.
More Numerical Methods practice problems
- A decimal floating-point system uses base β = 10, precision t = 4, and exponent range…Floating-point arithmetic, conditioning, and stability
- In four-digit decimal floating-point arithmetic with rounding to nearest, compute…Floating-point arithmetic, conditioning, and stability
- Let g be continuously differentiable on an open interval containing a fixed point…Root finding and nonlinear systems
- Let A ∈ ℝ^(n×n) be strictly row-diagonally dominant, and let G_J=D⁻¹(L+U) be the Jacobi…Linear systems, least squares, and eigenproblems
- The values f(1.0)=2.7183, f(1.1)=3.0042, f(1.2)=3.3201, and f(1.3)=3.6693 are given…Interpolation and approximation
- A fixed-point rearrangement is useless unless it contracts on an invariant intervalRoot finding and nonlinear systems
- Matching values and derivatives needs repeated-node divided differencesInterpolation and approximation
- Two Gauss nodes integrate cubics exactly and miss a concrete quarticNumerical differentiation and quadrature
- Linear shooting hits the far boundary in one sensitivity stepNumerical ODE and introductory PDE methods