[proofplan]
We derive the error recurrence by subtracting the fixed-point equation $x^* = Hx^* + v$ from the iteration $x^{(k+1)} = Hx^{(k)} + v$. The constant vector $v$ cancels, yielding $e^{(k+1)} = He^{(k)}$, which iterates to $e^{(k)} = H^k e^{(0)}$. The equivalence between convergence $x^{(k)} \to x^*$ and $H^k e^{(0)} \to 0$ then follows from the identity $x^{(k)} - x^* = e^{(k)}$.
[/proofplan]
[step:Derive the error recurrence $e^{(k)} = H^k e^{(0)}$ by subtracting the fixed-point equation]
Define the error at iteration $k$ as
\begin{align*}
e^{(k)} := x^{(k)} - x^* \in \mathbb{R}^n.
\end{align*}
The iteration gives $x^{(k+1)} = Hx^{(k)} + v$, and the fixed point satisfies $x^* = Hx^* + v$. Subtracting:
\begin{align*}
e^{(k+1)} = x^{(k+1)} - x^* = Hx^{(k)} + v - Hx^* - v = H(x^{(k)} - x^*) = He^{(k)}.
\end{align*}
Iterating this recurrence from $k = 0$:
\begin{align*}
e^{(k)} = He^{(k-1)} = H^2 e^{(k-2)} = \cdots = H^k e^{(0)}.
\end{align*}
[guided]
The key observation is that the constant vector $v$ cancels upon subtraction. This is the defining feature of a *stationary linear* iteration: the error evolves according to a homogeneous linear recurrence $e^{(k+1)} = He^{(k)}$, regardless of the right-hand side $v$. The matrix $H$ is called the **iteration matrix** and completely determines the convergence behaviour.
Starting from $e^{(0)} = x^{(0)} - x^*$, we apply $H$ repeatedly:
\begin{align*}
e^{(1)} = He^{(0)}, \quad e^{(2)} = He^{(1)} = H^2e^{(0)}, \quad \ldots, \quad e^{(k)} = H^k e^{(0)}.
\end{align*}
This is a simple induction: if $e^{(k)} = H^k e^{(0)}$, then $e^{(k+1)} = He^{(k)} = H \cdot H^k e^{(0)} = H^{k+1} e^{(0)}$.
[/guided]
[/step]
[step:Establish the equivalence between convergence and $H^k e^{(0)} \to 0$]
**Forward direction.** Suppose $H^k e^{(0)} \to 0$ for every $e^{(0)} \in \mathbb{R}^n$. For any starting point $x^{(0)} \in \mathbb{R}^n$, the initial error is $e^{(0)} = x^{(0)} - x^*$. By the error identity from the previous step:
\begin{align*}
\|x^{(k)} - x^*\| = \|e^{(k)}\| = \|H^k e^{(0)}\| \to 0 \quad \text{as } k \to \infty.
\end{align*}
Hence $x^{(k)} \to x^*$.
**Converse direction.** Suppose the method is convergent, i.e., $x^{(k)} \to x^*$ for every starting point $x^{(0)} \in \mathbb{R}^n$. Let $e^{(0)} \in \mathbb{R}^n$ be arbitrary. Choose $x^{(0)} = x^* + e^{(0)}$. Then $e^{(0)} = x^{(0)} - x^*$ and by convergence:
\begin{align*}
H^k e^{(0)} = e^{(k)} = x^{(k)} - x^* \to 0 \quad \text{as } k \to \infty.
\end{align*}
Since $e^{(0)}$ was arbitrary, $H^k e^{(0)} \to 0$ for every $e^{(0)} \in \mathbb{R}^n$.
[guided]
The equivalence rests on the bijection between starting points $x^{(0)} \in \mathbb{R}^n$ and initial errors $e^{(0)} = x^{(0)} - x^* \in \mathbb{R}^n$: given any $e^{(0)}$, we can construct a starting point $x^{(0)} = x^* + e^{(0)}$ that realises it. This is why convergence "for every starting point" is the same as $H^k e^{(0)} \to 0$ "for every initial error."
**Forward direction.** Suppose $H^k z \to 0$ for all $z \in \mathbb{R}^n$. Given any $x^{(0)}$, the initial error $e^{(0)} = x^{(0)} - x^*$ is a particular element of $\mathbb{R}^n$. Therefore:
\begin{align*}
\|x^{(k)} - x^*\| = \|H^k e^{(0)}\| \to 0,
\end{align*}
and the iteration converges.
**Converse direction.** Suppose $x^{(k)} \to x^*$ for every $x^{(0)} \in \mathbb{R}^n$. Let $e^{(0)} \in \mathbb{R}^n$ be any vector. We need to show $H^k e^{(0)} \to 0$. Set $x^{(0)} := x^* + e^{(0)}$, so the initial error is exactly $e^{(0)}$. By hypothesis, $x^{(k)} \to x^*$, so:
\begin{align*}
H^k e^{(0)} = x^{(k)} - x^* \to 0.
\end{align*}
Since $e^{(0)}$ was arbitrary, $H^k$ sends every vector to zero as $k \to \infty$.
[/guided]
[/step]
