Global Convergence of Hessenberg Shifted QR I: Dynamics

The paper proves a deterministic shifting strategy Sh_{k,B} for Hessenberg shifted QR that, for diagonalizable H0 with κV(H0) ≤ B, guarantees rapid decoupling with decδ(H0) ≤ 4 log(1/δ) (Theorem 1.3) and gives an explicit per-iteration cost bound incorporating TAppRitz and a nonnormality overhead TNN(k,B) . The proof does not rely on a uniform contraction of the GMRES-type quantity μ_k; instead it introduces a potential ψk(H) (the geometric mean of the last k subdiagonals), an approximate functional calculus (Lemma 2.4), a procedure find to obtain an α-promising Ritz value (Lemma 2.7), and an exceptional-shift net exc that ensures potential reduction when the promising shift stagnates (Lemma 2.8 and Lemma 2.9). This yields a per-iteration constant-factor decrease of ψk and hence O(log(1/δ)) decoupling time; see the algorithm Shk,B and the potential-reduction framework in Section 2 . Key technical steps include Lemma 2.3 (which bounds ψk after an implicit QR step via τp(H) = ||e_n^* p(H)^{-1}||^{-1/k}) together with the approximate functional calculus to link these observables to moments of a measure Z_H associated with H . The candidate model’s claim that the result was likely open and would require a uniform contraction of μ_k conflicts with the paper’s different potential-based method and the exceptional-shift mechanism; the paper provides a complete, exact-arithmetic proof of the stated bounds including the explicit TNN(k,B) term .