A Proof of the Forsythe Conjecture for the Two-Step Restarted Conjugate Gradient Method

Abstract

Forsythe conjectured in 1968 that the normalized residual directions of restarted conjugate gradients approach a two-cycle. We prove the conjecture for restart length two: unless the method terminates, its even and odd normalized residuals converge separately.

24 pages, 1 figure