Metodo di accelerazione di Aitken

Il metodi di accelerazione di Aitken viene utilizzato per ottenere ancora una convergenza quadratica in caso di radici multiple, questa volta senza conoscerne la molteplicità. Tutto il metodo si basa sul seguente limite:

$$\lim_{k \rightarrow + \infty} \frac{\overline{x} - x_{k+1}}{\overline{x}-x_k} = c$$

a partire da questo limite si possono ottenere le seguenti espressioni:

$$k \gg 1$$

$$\overline{x} - x_{k+1} \approx c(\overline{x} - x_k)$$ (5.1)

$$\overline{x} - x_{k} \approx c(\overline{x} - x_{k-1})$$

sottraendo tra loro queste due quantita si ricava

$$\begin{eqnarray*} x_k - x_{k+1} & \approx & c(x_k - x_{k-1})\\ c & \approx & \frac{x_k - x_{k+1}}{x_{k-1}- x_k}. \end{eqnarray*}$$

Considerando l'espressione 5.1 e sviluppando

$$\begin{eqnarray*} \overline{x}-x_k & \approx & c(\overline{x} - x_k)\\ (1-c)\... ..._{k+1} x_{k-1} - x_k^2}{x_{k+1}-2x_k + x_{k-1}} = {\hat{x}}_k. \end{eqnarray*}$$

una volta ottenute le approssimazioni $x_{k-1}$, $x_k$ e $x_{k+1}$ si può generare ${\hat{x}}_k$ tramite il metodo di Aitken. Uno schema riassuntivo dell'algoritmo è simile al seguente:

$$\begin{array}{ccccc} \left. \begin{array}{c} x_0 \\ \d... ...{array}{c} {\hat{x}}_2 \\ \vdots \end{array} \end{array}$$

Se $\{ x_k \}$ converge linearmente, allora la successione $\{ {\hat{x}}_k \}$ converge quadraticamente.