The [[Fixed Point|Fixed Point]] Method is an iterative method to find the [[Fixed Point|fixed point]] of a function $f$. $\huge f: p \mapsto p $ The fixed point method is to simply keep applying the function. $\huge x_{n+1} = f(x_{n}) $ >[!info] Restriction to guarentee this method works >$\huge f\in \mathcal C^{1}[a,b] $ >$\huge >\forall x\in [a,b]: |f'(x)| <1 >$ ### Asymtopic Behavior Solve for $p$ such that $f(p)=p$. $\forall x, \let \hat{x} = x - p$. $\huge \begin{align} x_{n+1} &= f(x_{n}) \end{align}$ [[Taylor Series]] at $x=p$ $\large \begin{align} f(x) &= f(p) +f'(p)(x-p)+ \frac{1}{2} f''(p)(x-p)^{2} + \cdots \\ &= p + f'(p) \hat{x} + \frac{1}{2} f''(p) \hat{x}^{2} + \cdots \end{align}$ $\huge \begin{align} x_{n+1} &= p + f'(p) \hat{x}_{n} + \frac{1}{2} + \mathcal O(\hat{x}_{n}^{2}) \\ \end{align}$ The [[Numerical Analysis Error Bounds|Error Bound]] will be: $\huge \epsilon_{n} = \left| \hat{x}_{n} \right| $ $\huge \begin{align} \hat{x}_{n+1} &= x_{n+1} - p \\ &= f'(p) \hat{x}_{n} + \mathcal O( \hat{x}_{n}^{2}) \end{align}$ As $n\to \infty$, $\hat{x}_{n}\to 0$, so we discard the negligent $\mathcal O$: $\huge \hat{x}_{n+1} \approx f'(p) \hat{x}_{n} $ Because $f'(p)$ is constant, this means that the error of the fixed point method has an [[Order of Convergence]] $\alpha=1$. ### Approximation using [[Aitken's Delta Squared]] Let $p$ be such that $f(p) =p$. The taylor series of $f$ around $x=p$ is: $\large f(x) = p + f'(p)(x-p)+ \frac{1}{2}f''(x)(x-p)^{2} + \mathcal O((x-p)^{3}) $ $\huge \let \hat{x} = x-p $ $\large \begin{align} f(x) &= p + f'(p)\hat{x}+ \frac{1}{2}f''(p) \hat{x}^{2} + \mathcal O(\hat{x}^{3})\\ \end{align} $ $\huge \begin{align} f(x) &= p + f'(p)\hat{xi_{i}}+ \frac{1}{2}f''(p) \hat{x_{i}}^{2} + \mathcal O(\hat{x_{i}}^{3})\\ \hat{x}_{i+1} &= x_{i+1}-p \\ &= f'_{p} \hat{x}_{i} + \frac{1}{2}f_{p}''\hat{x}_{i}^{2} + \mathcal O(\hat{x}_{i}^{3}) \\ \Delta \hat{x}_{i} &= x_{i+1} - \hat{x}_{i}\\ &= (f_{p}'-1) \hat{x}_{i} + \frac{1}{2}f_{p}'' \hat{x}_{i}^{2} + \mathcal O( \hat{x}_{i}^{3}) \\ \Delta^{2} \hat{x}_{i} &= (f_{p}' - 1)^{2} \hat{x}_{i} + \frac{1}{2}\pa{ f_{p}'^{2} + {f'}_{p}^{1} - 2 } \hat{x}_{i}^{2} + \mathcal O (\hat{x}^{3}) \\ &= \hat{x}_{i} - 2. \frac{f_{p}'}{f_{p}'-1} f_{p}'' \hat{x}_{i}^{2} + \mathcal O(\hat{x}_{i}^{3}) \end{align} $ $\huge x_{i} - \frac{\Delta x_{i}^{2}}{\Delta^{2} x_{i}} = p + 2 \frac{f_{p}'}{f_{p}'-1} f_{p}'' \hat{x}_{i}^{2} + \mathcal O(\hat{x}_{i}^{3}) $