2

I have the following equation (from Taylor's expansion) $$ f(x_n)+f'(x_n)(x-x_n)+\frac{1}{2}f''(x_n)(x-x_n)^2=0$$

The task: Derive an algorithm for finding the approximation $x_{n+1}$ (determine which root from the quadratic equation must be taken), if $x_n$ is close enough to the solution. We can assume, that the solution has a multiplicity of one.

What I've got so far:

I'll take $A=(x-x_n)$. Solve $$f(x_n)+f'(x_n)A+\frac{1}{2}f''(x_n)A^2=0$$ for A. I get that $$A_{1,2}=\frac{-f'(x_n)\pm \sqrt{(f'(x_n))^2-4\frac{f''(x_n)}{2}f(x_n)}}{2\frac{f''(x_n)}{2}}$$ from that $$x_{n+1}=x_n+\frac{-f'(x_n)\pm \sqrt{(f'(x_n))^2-2f''(x_n)f(x_n)}}{f''(x_n)}$$ Now I must choose the root. Which one should I take and why?

We need $x_{n+1}$ as close to $x_n$ as possible. So $$\frac{-f'(x_n)\pm \sqrt{(f'(x_n))^2-2f''(x_n)f(x_n)}}{f''(x_n)}$$ needs to be as close to $0$ as possible. As $f(x_n)\approx 0$ $$-f'(x_n)\pm \sqrt{(f'(x_n))^2-2f''(x_n)f(x_n)}\approx -f'(x_n)\pm |f'(x_n)| $$ So we can see that choosing the quadratic equation solution $$\frac{-f'(x_n)+\text{sign}(f'(x_n))\sqrt{(f'(x_n))^2-2f''(x_n)f(x_n)}} {f''(x_n)}$$ guarantees that $x_{n+1}$ is as close to $x_n$ as possible.

pls_halp
  • 471

1 Answers1

2

The one with the smaller fraction. Or the one where the whole expression is closer to $x_n$. Or in the end, the root with the same sign as $f'(x_n)$ so that the denominator of the fraction almost cancels.

Better yet, apply binomial formulas to get $$ x_{n+1}=x_n-\frac{2f(x_n)}{f'(x_n)+sign(f'(x_n))\sqrt{f'(x_n)^2-2f(x_n)f''(x_n)}} $$ to avoid floating-point cancellation errors.

Look up Halley's and Laguerres method for alternative formulas with cubic convergence.

One can also apply the Taylor series of the square root wherever it appears. In the first solution form of the quadratic equation one would need to use the quadratic Taylor polynomial $\sqrt{1-a}=1-\frac a2-\frac{a^2}8+O(a^3)$ to retain a third order method, \begin{align} x_{n+1}&=x_n-\frac{f'(x)\left(1-\sqrt{1-2\frac{f(x_n)f''(x_n)}{f'(x_n)^2}}\right)}{f''(x_n)}\\ &=x_n-\frac{f(x)}{f'(x)}\left(1+\frac{f''(x_n)f(x_n)}{2f'(x_n)^2}\right)+O(f(x_n)^3) \end{align} which is also a named method, especially if (properly) applied to the vector case.

Lutz Lehmann
  • 126,666
  • Can you elaborate more on the use of binomial formulas? How did you reach the equation above? – pls_halp Mar 18 '18 at 20:44
  • 1
    It is the usual $a-b=\frac{a^2-b^2}{a+b}$. And as written above, the sign is chosen to get the smaller of the two possible increments, that is for the larger denominator close to $2f'(x_n)$. – Lutz Lehmann Mar 18 '18 at 21:31
  • What do you mean by the denominator of the fraction almost cancelling? What does that have to do with the sign of $f'(x_n)$? – pls_halp Mar 19 '18 at 07:09
  • 1
    As $f(x_n)\approx 0$ you get $\sqrt{f'(x_n)^2-2f(x_n)f''(x_n)}\approx |f'(x_n)|$. And one of $-f'(x_n)\pm|f'(x_n)|$ is zero, and we want that sign in the step update. – Lutz Lehmann Mar 19 '18 at 07:23
  • So did you mean the numerator of the fraction cancelling out? – pls_halp Mar 19 '18 at 07:29
  • No, then you would have a zero step. It is the small difference that remains that makes the third order step. One just needs an equivalent form or approximately equivalent form where that cancellation does not occur. – Lutz Lehmann Mar 19 '18 at 07:47
  • I have edited my question, to sum up this conversation. Does it make sense? – pls_halp Mar 19 '18 at 08:14
  • Yes, that is correct. I added one alternative way on how to proceed to avoid the cancellation issue. – Lutz Lehmann Mar 19 '18 at 08:25