TheoremStatement: Literature-sourcedProof: AI-adaptedPipeline-generatedprecheck pass

How statement and proof provenance work

The first chip identifies the source of the statement or construction; the second identifies the source of its local proof or verification.

Literature-sourced: the exact statement appears in a cited source; only wording and notation differ.
AI-adapted: a semantically identical restatement of literature-sourced material, modulo indexing, notation, and boundary cases adopted by the library.
AI-generated: a genuinely novel statement formulated by AI, with no source for the claim itself.

These labels describe origin, not correctness: citations and verification chips remain separate evidence.

Exact implicit Arnoldi restart applies its shift polynomial and preserves an Arnoldi residual identity

Statement

Let $A \in C^{n \times n}$ , and suppose an exact $m$ -step Arnoldi factorization without breakdown is $A V_{m} = V_{m} H_{m} + β_{m} v_{m + 1} e_{m}^{*}, V_{m}^{*} V_{m} = I_{m},$ where $H_{m}$ is upper Hessenberg and $β_{m} > 0$ . Let $1 \leq r < m$ , $p = m - r$ , and let $H_{j - 1} - μ_{j} I = Q_{j} R_{j}$ be exact shifted QR factorizations using the ordered top-down adjacent-row Givens eliminations on pairs $(1, 2), (2, 3), \dots, (m - 1, m)$ , with $R_{j}$ upper triangular. Put $Q = Q_{1} \dots Q_{p}, H^{+} = Q^{*} H_{m} Q, q (z) = \prod_{j = 1}^{p} (z - μ_{j}) .$ Assume $q (A) v_{1} \neq 0$ , the exact filtered Krylov space $K_{r} (A, q (A) v_{1})$ has dimension $r$ , and $ρ \neq 0$ in the factorization $q (H_{m}) = Q R$ with $R$ upper triangular. Then $range (V_{m} Q (:, 1 : r)) = K_{r} (A, q (A) v_{1}) .$ Writing $H_{r}^{+} = H^{+} (1 : r, 1 : r)$ , $h^{+} = H_{r + 1, r}^{+}$ , and $g = h^{+} V_{m} Q e_{r + 1} + β_{m} (e_{m}^{*} Q e_{r}) v_{m + 1},$ the truncated restart has the exact residual identity $A V_{m} Q (:, 1 : r) = V_{m} Q (:, 1 : r) H_{r}^{+} + g e_{r}^{*} .$ If $g \neq 0$ , then $v_{r + 1}^{+} = g / ∥ g ∥_{2}$ is orthogonal to the retained columns and the new Arnoldi residual coefficient is $β_{r}^{+} = ∥ g ∥_{2}$ ; if $g = 0$ , the retained subspace is exactly invariant.

Facts & Assumptions

Given: The no-breakdown Arnoldi factorization, dimensions and shifts in the Statement, with the stated nonannihilation and filtered-dimension hypotheses.

[F1]

Before breakdown, Arnoldi produces an orthonormal Krylov basis and a rectangular upper-Hessenberg factorization: before breakdown, $A Q_{m} = Q_{m + 1} {\overset{ˉ}{H}}_{m}$ , the Arnoldi vectors are orthonormal, and $H_{m}$ is upper Hessenberg; the present item writes this basis as $V_{m}$ .

[F2]

Unshifted QR iteration, shifted QR iteration, deflation, and the Wilkinson shift: a shifted QR step factors $H - μ I = Q R$ with $Q$ unitary and $R$ upper triangular, then sets $H_{+} = R Q + μ I = Q^{*} H Q$ .

[F3]

Shifted QR iteration preserves upper Hessenberg form: an exact shifted QR step built from adjacent-row Givens eliminations preserves upper Hessenberg form.

[F4]

Upper Hessenberg matrices and real symmetric tridiagonal matrices: upper Hessenberg means $H_{i j} = 0$ whenever $i > j + 1$ .

[F5]

Real Givens rotations and complex Givens transformations and Full, reduced, and column-pivoted computational QR factorisations: the QR factorization in the Statement is formed by successive adjacent-row Givens rotations, with the unitary factor given by their ordered product.

Proof

technique · direct

1.1F1F4algebra

For $0 \leq j \leq m - 1$ , $A^{j} v_{1} = V_{m} H_{m}^{j} e_{1}$ : the claim holds at $j = 0$ , and if it holds at $j < m - 1$ , [F1] gives $A^{j + 1} v_{1} = V_{m} H_{m}^{j + 1} e_{1} + β_{m} v_{m + 1} e_{m}^{*} H_{m}^{j} e_{1}$ . By [F4], $H_{m}^{j} e_{1}$ is supported in rows $1$ through $j + 1$ , so $e_{m}^{*} H_{m}^{j} e_{1} = 0$ when $j < m - 1$ ; induction proves the identity through degree $m - 1$ .

2.1givenF2step 1.1algebra

Since $\deg q = p < m$ , step 1.1 gives $q (A) v_{1} = V_{m} q (H_{m}) e_{1}$ . Put $P_{j} = Q_{1} \dots Q_{j}$ and $P_{0} = I$ ; the cumulative similarities give $H_{j - 1} = P_{j - 1}^{*} H_{m} P_{j - 1}$ . Thus $H_{m} - μ_{j} I = P_{j - 1} (H_{j - 1} - μ_{j} I) P_{j - 1}^{*} = P_{j - 1} Q_{j} R_{j} P_{j - 1}^{*} = P_{j} R_{j} P_{j - 1}^{*}$ . Because scalar factors commute, order the product as $q (H_{m}) = (H_{m} - μ_{p} I) \dots (H_{m} - μ_{1} I)$ ; substituting these factorizations cancels every adjacent $P_{j - 1}^{*} P_{j - 1}$ and gives $q (H_{m}) = P_{p} (R_{p} \dots R_{1}) = Q R$ . The product $R_{p} \dots R_{1}$ is upper triangular, and $R e_{1} = ρ e_{1}$ , so $q (A) v_{1} = ρ V_{m} Q e_{1}$ .

3.1givenF3step 1.1step 2.1algebra

For $0 \leq j < r$ , $p + j \leq m - 1$ , so applying step 1.1 to each monomial of $z^{j} q (z)$ gives $A^{j} q (A) v_{1} = V_{m} H_{m}^{j} q (H_{m}) e_{1} = ρ V_{m} Q (H^{+})^{j} e_{1}$ . By [F3], $H^{+}$ is upper Hessenberg, so $(H^{+})^{j} e_{1}$ is supported in its first $j + 1$ coordinates and the resulting vector lies in $range (V_{m} Q (:, 1 : r))$ . Thus $K_{r} (A, q (A) v_{1})$ is contained in the retained range; both have dimension $r$ , the former by hypothesis and the latter because $V_{m} Q$ has orthonormal columns, so they are equal.

3.2F1F3F4F5step 2.1algebra

In each shifted QR step the top-down left eliminations use row pairs $(1, 2), (2, 3), \dots, (m - 1, m)$ ; by [F5] the unitary factor is the ordered product of their adjoints. In $Q_{i} e_{j}$ , rotations with index greater than $j$ act first and fix $e_{j}$ , rotation $j$ adds at most row $j + 1$ , and rotations with smaller indices add only rows less than $j$ ; by [F4], each $Q_{i}$ is upper Hessenberg. If $C$ has lower bandwidth $a$ and $D$ lower bandwidth $b$ , a nonzero term in $(C D)_{i j} = \sum_{k} C_{i k} D_{k j}$ requires $k \geq i - a$ and $k \leq j + b$ , so $C D$ has lower bandwidth at most $a + b$ . Hence $Q = Q_{1} \dots Q_{p}$ has lower bandwidth $p$ and $e_{m}^{*} Q e_{j} = 0$ for $j < m - p = r$ . Multiplying the Arnoldi factorization in [F1] by $Q$ yields $A V_{m} Q = V_{m} Q H^{+} + β_{m} v_{m + 1} e_{m}^{*} Q$ ; since $H^{+}$ is upper Hessenberg, restricting to columns 1 through $r$ gives $A V_{m} Q (:, 1 : r) = V_{m} Q (:, 1 : r) H_{r}^{+} + (h^{+} V_{m} Q e_{r + 1} + β_{m} (e_{m}^{*} Q e_{r}) v_{m + 1}) e_{r}^{*}$ , the stated identity with residual vector $g$ .

4.1F1step 3.2algebra∎

The vector $V_{m} Q e_{r + 1}$ is orthogonal to the first $r$ columns of $V_{m} Q$ , and [F1] makes $v_{m + 1}$ orthogonal to the range of $V_{m}$ ; hence $g$ is orthogonal to the retained columns. If $g \neq 0$ , normalization gives the next Arnoldi residual direction with coefficient $∥ g ∥_{2}$ ; if $g = 0$ , step 3.2 says $A$ maps the retained range into itself.

Depends on

Used by

A shift near the wanted eigenvalue suppresses its component under repeated implicit restarts Example

Dependency tree · two levels

19 results within two dependency steps of this one, each drawn at its shortest distance from it. An arrow runs from a result to what uses it, so the chart reads left to right and ends at this result, which carries a heavier outline. Every node is a link to that result. Click elsewhere on the chart to enlarge it.

Sources

Yousef Saad, Numerical Methods for Large Eigenvalue Problems, second edition, §7.3 (standard reference, not scraped)
Peter Arbenz, Lecture Notes on Solving Large Scale Eigenvalue Problems, §11.2 (standard reference, not scraped)