Skip to main content

Numerical Methods · Linear systems, least squares, and eigenproblems

Two conjugate-gradient steps close an SPD two-by-two residual

Problem

Numerical Methods practice problem

LetA=(4113),b=(12),A=\begin{pmatrix}4&1\\1&3\end{pmatrix},\qquad b=\begin{pmatrix}1\\2\end{pmatrix},and consider the linear system Ax=bAx=b in exact arithmetic. The conjugate-gradient iteration from x0=0x_0=0 isr0=b−Ax0,p0=r0,αk=rk⊤rkpk⊤Apk,xk+1=xk+αkpk,rk+1=rk−αkApk,βk+1=rk+1⊤rk+1rk⊤rk,pk+1=rk+1+βk+1pk,\begin{align*} r_0&=b-Ax_0,\qquad p_0=r_0,\\ \alpha_k&=\frac{r_k^\top r_k}{p_k^\top Ap_k},\qquad x_{k+1}=x_k+\alpha_k p_k,\qquad r_{k+1}=r_k-\alpha_k Ap_k,\\ \beta_{k+1}&=\frac{r_{k+1}^\top r_{k+1}}{r_k^\top r_k},\qquad p_{k+1}=r_{k+1}+\beta_{k+1}p_k, \end{align*}stopping when rk=0r_{k}=0.

1. Prove that AA is symmetric positive definite by leading minors (or by eigenvalues). Compute those eigenvalues as (7±5)/2(7\pm\sqrt{5})/2.

2. Starting from x0=0x_0=0, compute r0r_0, p0p_0, α0\alpha_0, x1x_1, r1r_1, β1\beta_1, p1p_1, α1\alpha_1, x2x_2, and r2r_2 as exact rationals. Verify Ax2=bAx_2=b.

3. Verify the two identities r1⊤r0=0r_1^\top r_0=0 and p0⊤Ap1=0p_0^\top Ap_1=0. Then use the stated exact-arithmetic CG orthogonality theorem to explain why a general SPD n×nn\times n problem terminates with rn=0r_n=0 after at most nn steps.

4. Audit both sentences: (i) "CG is just steepest descent, so the next search direction is p1=r1p_1=r_1 and β1\beta_1 may be ignored"; (ii) "the residuals are AA-orthogonal, while the search directions are Euclidean-orthogonal." Compute the rejected steepest-descent vector r1r_1 and show that it is not AA-orthogonal to p0p_0.

Do not factor AA by Gaussian elimination, and do not replace the iteration by a nonlinear Newton update.

Hint

Hint

The leading minors of AA are 44 and det⁡A=11\det A=11. The residual r0r_0 is bb itself because x0=0x_0=0.

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

Back to Numerical Methods

An original ProofAnvil practice problem, written for this course. ProofAnvil is a practice course, not a homework-answer service.