= Solution
Because $Ax^*=b$, the error $e^{(k)}=x^*-x^{(k)}$ obeys
$$
e^{(k+1)}
=((1+\beta)I-\alpha A)e^{(k)}
-\beta e^{(k-1)}.
$$
Thus the <heavy-ball error propagation matrix> is
$$
\boxed{
\begin{pmatrix}e^{(k+1)}\\ e^{(k)}\end{pmatrix}
=
M\begin{pmatrix}e^{(k)}\\e^{(k-1)}\end{pmatrix},
\qquad
M=
\begin{pmatrix}
(1+\beta)I-\alpha A&-\beta I\\
I&0
\end{pmatrix}.}
$$
If $A=\operatorname{diag}(\lambda_1,\ldots,\lambda_n)$, permute the coordinates from
$$
(e_1^{(k)},\ldots,e_n^{(k)},e_1^{(k-1)},\ldots,e_n^{(k-1)})
$$
to
$$
(e_1^{(k)},e_1^{(k-1)},\ldots,e_n^{(k)},e_n^{(k-1)}).
$$
For the corresponding <permutation matrix> $P$,
$$
\boxed{
PMP^T=\operatorname{diag}(M_1,\ldots,M_n),
\qquad
M_i=
\begin{pmatrix}
1+\beta-\alpha\lambda_i&-\beta\\
1&0
\end{pmatrix}.}
$$
Back to article page
