What is the benefit of using forward difference approximation in newton's method of root finding?

Question

I am trying to think of when using forward difference approximation to $$f'(x) = \frac{f(x+\delta) - f(x)}{\delta}$$ in Newton's root finding method of $$f(x_{n+1})=x_n-\frac{f(x_n)}{f'(x_n)}$$ is beneficial.

Substituting gives $$f(x_{n+1})=x_n-\frac{\delta}{f(x_n+\delta) - f(x_n)}f(x_n).$$ My initial thought is that this will work better for functions that have steep derivatives, so it will limit $f'(x)$ from blowing up.

Another follow up question is that why setting $\delta=\epsilon_M^{1/2}$ is a sensible thing to do? Is it because this guarantees that errors will dampen at each iteration.

Could someone please nudge me in the right direction.

Answer 1

You want $\delta$ to be small in order for the approximation to $f'$ be better. On the other hand, the subtraction $f(x+\delta)-f(\delta)$ kills precision, which means that we want $|f(x+\delta)-f(x)|\gg\epsilon$. With the choice $\delta=\sqrt{\epsilon}$, we have $|f(x+\delta)-f(x)|\approx \sqrt\epsilon|f'(x)|$. Without knowning more about $f$, we should assume that both $f(x)$ and $f'(x)$ are both of "reasonable" order of magnitude. Hence $|f(x+\delta)-f(x)|\approx\sqrt\epsilon|f(x)|$, which means that we lose only about half of the available precision.

Answer 2

The fixed-point iteration $x_+=x-af(x)$ converges if $|1-af'(x)|<1$ inside some interval containing the simple root $x_*$. Thus $a\approx f'(x)^{-1}$ has a rather large margin for approximations. It does not matter much what approximation of the derivative you use.

---

To get something approximating the second order convergence rate you want that the last step of the numerical iteration reduces the error from $x-x_*=O(\sqrtϵ)$ to $x_+-x_*=O(ϵ)$. Now \begin{align} f'(x_*)(x_+-x)&\approx f(x_+)=f(x)-f'(x)af(x)+\frac12f''(x)a^2f(x)^2+...\\ &=(1-af'(x))(f'(x_*)(x-x_*)+...)~+~\frac12f''(x)a^2(f'(x_*)(x-x'*)+..)^2~+...\\[.8em] \implies x_+-x_* &\approx (1-af'(x))(x-x_*)~+~\frac12f''(x)a^2f'(x_*)(x-x'*)^2 \end{align} The second term already has the required magnitude, thus the goal is achieved if in the first term $1-af'(x)=O(\sqrtϵ)$ or equivalently $a^{-1}=f'(x)(1+O(\sqrtϵ))$.

---

On the other hand, the error of the numerical evaluation of the divided difference $\frac{f(x+h)-f(x)}{h}$ has two components, the theoretical discretization error in the difference to $f'(x)$ of $O(h)$ and the floating point error from the evaluations of $f$ which in the quotient gives an error of size $O(\frac{ϵ}h)$. The overall error is minimal if these two contributions balance, which happens at $h=O(\sqrtϵ)$ with an error also of $O(\sqrtϵ)$. Which fits the requirement for the Newton method.

---

Note that for instance the central difference quotient $\frac{f(x+h)-f(x-h)}{2h}$ has discretization error $O(h^2)$ and floating point error again of $O(\frac{ϵ}h)$, so that balance is achieved at $h=δ=O(\sqrt[3]ϵ)$ for an error $O(ϵ^{2/3})$. Which is smaller than required. A method that requires again only 2 function evaluations per step is $$x_+=x-\frac{δ(f(x+δ)+f(x-δ))}{f(x+δ)-f(x-δ)}$$