To implement Chebyshev acceleration cheaply, use the 3 term recurrence relation

$$T_m(x) = 2xT_{m-1}(x) - T_{m-2}(x)$$ (1)

This means we need to save and combine only 3 vectors, $y_m$, $y_{m-1}$ and $y_{m-2}$ and not all previous $x_,$.

To see how this works let

$$\mu_m \equiv \frac{1}{T_m(1/\rho )}$$ (2)

so

$$P_m(R) = \mu_mT_m\left(\frac{R}{\rho}\right )$$

and

$$\frac{1}{\mu_m} = \frac{2}{\rho\mu_{m-1}}-\frac{1}{\mu_{m-2}}$$

by the 3 term recurrence in Eqn 1. Therefore

$$\begin{eqnarray*} y_m-x &=& P_m(R)(x_0-x) \\ &=& \mu_mT_m\left(\frac{R}{\rho}\... ...ac{y_{m-1}-x}{\mu_{m-1}} - \frac{y_{m-2}-x}{\mu_{m-2}} \right] \end{eqnarray*}$$

or

$$y_m = \frac{2\mu_m}{\mu_{m-1}}\frac{R}{\rho}y_{m-1} - \frac{\mu_m}{\mu_{m-2}}y_{m-2} +dm$$

where

$$\begin{eqnarray*} dm &=& x- \frac{2\mu_m}{\mu_{m-1}}\left(\frac{R}{\rho}\right)x... ...c{2\mu_m}{\rho\mu_{m-1}}c \\ &=& \frac{2\mu_m}{\rho\mu_{m-1}}c \end{eqnarray*}$$

This yields the algorithm

ALGORITHM: Chebyshev acceleration of $x_{i+1}=Rx_i+c$.
$\mu_0=1$; $\mu_1=\rho$; $y_0=x_0$; $y_1=Rx_0+c$

for m=2,3$\ldots$

$$\begin{eqnarray*} \mu_m &=& \frac{1}{\left(\frac{2}{\rho\mu_{m-1}}-\frac{1}{\mu_... ...-\frac{\mu_m}{\mu_{m-2}}y_{m-2} + \frac{2\mu_m}{\rho\mu_{m-1}}c \end{eqnarray*}$$

end for.