show that the approximate error relationship is $\epsilon_{k+1} \approx \frac{f''(s)}{(2f'(s))}\epsilon_k \epsilon_{k-1}$

104 Views Asked by At

If the Secant Method converges to $s$, and $f'(s) \ne 0$ and $f''(s) \ne 0$, show that the approximate error relationship is $\epsilon_{k+1} \approx \frac{f''(s)}{(2f'(s))}\epsilon_k \epsilon_{k-1}$

Here are my workings below, this is my first attempt at this proof and I am wondering if it correct as I have spent sometime typing up the proper latex, thanks!

Suppose that we are solving the equation $f(x)=0$ using the secant method. Let the iterations

$$x_{k+1} = x_k - f(x_k) \frac{x_k - x_{k-1}}{f(x_k)-f(x_{k-1})}$$

be successful and approach a solution $s$, $f(s) = 0$ as $k \rightarrow \infty$.

The above equation expresses the iterate $x_{k+1}$ as a function of $x_k$ and $x_{k-1}$.

Let $x_k = s + \epsilon_k.$ Since $x_k \rightarrow s$ the sequence of errors $\epsilon _k$ approaches $0$ as $k \rightarrow \infty$. In terms of $s$ and $\epsilon _k$ the formula becomes

$$e_{k+1} = e_k - \frac{f(s +\epsilon_k)(\epsilon_k - \epsilon _{k-1})}{f(s+\epsilon_k)-f(s+\epsilon_{k-1})}$$

Assume that $f(x)$ is two times differentiable function and that $f'(s), f''(s) \ne 0$ . We write Taylors formula:

$$f(s+\epsilon) = f(s) + f'(s)\epsilon + \frac{f''(s)}{2}\epsilon ^2 + R_2(\epsilon)$$

Here $f(s) = 0$, $\epsilon$ is small, and $R_2(\epsilon)$ is the remainder term. Recall that $R_2(\epsilon)$ vanishes at $\epsilon = 0$ at a faster rate then $\epsilon ^2$. Neglecting the terms of order higher than $2$ in $\epsilon$, we have the approximation

$$f(s+\epsilon) \approx f'(s) \epsilon +\frac{f''(s)}{2}\epsilon ^2$$

Set for brevity

$$M = \frac{f''(s)}{2f'(s)}$$

and use the approximate equalities

$$f(s+\epsilon _k) \approx e_k f'(s)(1+M\epsilon _k)$$ $$f(s+ \epsilon_k) - f(s+\epsilon _{k-1}) \approx f'(s)(\epsilon_k-\epsilon_{k-1})(1+M(\epsilon_k + e_{k-1}))$$

Then to simplify our $2$nd equation I have written on this post

$$\epsilon_{k+1} \approx \epsilon _k - \frac{\epsilon_k f'(s)(1+M\epsilon_k)(\epsilon_k-\epsilon_{k-1})}{f'(s)(\epsilon _k - \epsilon _{k-1})(1+M(\epsilon _k + \epsilon _{k-1}))} \\ = \epsilon _k - \frac{\epsilon_k (1+ M \epsilon_k)}{1+ M(\epsilon _k + \epsilon_{k-1})} \\ = \frac{\epsilon _{k-1}\epsilon _k M }{1+M(\epsilon_k + \epsilon _{k-1})} \\ \approx \epsilon _{k-1}\epsilon _k M$$

Therefore we have obtained a relation for the errors,

$$\epsilon_{k+1} \approx \frac{f''(s)}{2f'(s)}\epsilon_{k-1}e_k$$ where the terms of order higher than $2$ in $\epsilon$ are neglected.