Deriving Newton-Raphson's extended method (sometimes known as Euler-Chebyshev method)

Question

I am trying to derive this iteration method for simple root of $f(x)=0$:

$$x_{i+1}=x_i−\frac{f(x_i)}{f′(x_i)}-\frac{1}{2}{f(x_i)}^2\frac{f''(x_i)}{f'(x_i)^3}$$

Can somebody help me out?

Answer 1

Here are some hints. To motivate the formula we Taylor expand $f(x+h)$ to second order

$$f(x+h) = f(x) + hf'(x) + \frac{h^2}{2}f''(x) + O(h^3)$$

Lets assume we have an approximate root $x$ (so $f(x)\approx 0$). We now want to find a $h$ such that $x+h$ is the root. In practice it will only be a better approxiation for the root since we use a finite order expansion in $h$. By taking $f(x+h)=0$ in the equation above and truncating at second order we get a quadratic equation for $h$,

$$f(x) + hf'(x) + \frac{h^2}{2}f''(x) = 0$$

Now solve for $h$ using the quadratic formula. Next use that $f(x) \approx 0$ is small and apply the approximation $\sqrt{1+a} \approx 1 + \frac{a}{2} + \frac{a^2}{8}$ valid for $|a|\ll 1$ to get ridd of the square root. Finally identity $x$ with $x_n$ and $x+h$ with $x_{n+1}$ to get the desired itteration formula.

Answer 2

Once you have figured out what the question is: suppose $r$ is your simple root. Then $f(x) = a_1 (x-r) + a_2 (x-r)^2 + a_3 (x-r)^3 + \ldots$.
If $x_i = r + \epsilon$, then $$\eqalign{f(x_i) &= a_1 \epsilon + a_2 \epsilon^2 + a_3 \epsilon^3 + O(\epsilon^4)\cr f'(x_i) &= a_1 + 2 a_2 \epsilon + 3 a_3 \epsilon^2 + O(\epsilon^3)\cr f''(x_i) &= 2 a_2 + 6 a_3 \epsilon + O(\epsilon^2)}$$

Plug in to your formula and expand in a series in powers of $\epsilon$. You should get $x_{i+1} = r + c \epsilon^3 + O(\epsilon^4)$ for some $c$.