2

My Question:

Derive a new iteration method for solving $f(x)=0$ by solving the quadratic equation $$f(x_k)+f'(x_k)(x-x_k)+\frac{1}{2}f''(x_k)(x-x_k)^2=0$$ Complete your algorithm by specifying which root to choose, and prove cubic convergence under appropriate assumptions on $f,x$ and the starting value $x_0$.

My thoughts:

Since you are solving the equation to find a new technique, let's say the roots of the equation is the new technique. Then I can get that, $$f(x_k) +f'(x_k)(x_{k+1}-x_k)+\frac{1}{2}f''(x_k)(x_{k+1}-x_k)^2 = 0$$ If that's the case, I can subtract it from the third level of taylor expansion. $$f(x_k) + f'(x_k) * (x-x_k)+\frac{1}{2}f^{\prime\prime}(x_k) (x-x_k)^2+\frac{1}{6}f'''(x_k)(x-x_k)^3=0$$ After I did the subtraction, I think I am pretty close, but now the issue becomes I have to prove that

$$\frac{f''(x_k)(x-x_{k+1})(x-2x_k+x_{k+1})}{2f'(x_k)(x-x_{k+1})^3}$$ is going to converge to some constant as $k \to \infty$? But I don't think that's gonna happen because if I use L'hospital's rule multiple times, since the numerators has higher order, if $x_k$ converges to $x$, the equation is likely to become infinity.

Edit: I really don't know how to start with this, if I'm even understanding this question correctly.

user312492
  • 21
  • @Winther Ok I see. But, now what does it mean "which root to choose"? – user312492 Feb 11 '16 at 01:37
  • When you solve the quadratic equation you get two roots. You need to choose the right root to get convergence. For example if $f'(x) > 0$ then you need to choose the positive root (the two terms in $-b \pm \sqrt{b^2 - 4ac}$ should almost cancel when close to the root). – Winther Feb 11 '16 at 01:52
  • @Winther Still don't understand what you mean... Although I get what you're saying, but how does this help me to solve my problem. – user312492 Feb 11 '16 at 03:25
  • 1
    See Halley method, today without square root, Halley originally used the square root. Also the Laguerre method is equivalent up to $O(f(x_k)^3)$ differences, but not easy to motivate. – Lutz Lehmann Feb 11 '16 at 07:57

1 Answers1

0

This is not exactly new, this is the original version of Halley's method from the middle of the 19th century.

As nothing about $f''(x_k)$ is certain, but $x_k$ is not already a root, complete the square from the left. To facilitate that multiply with $4f(x_k)$ to get $$ 0=(2f(x_k)+f'(x_k)(x-x_k))^2-(f'(x_k)^2-2f(x_k)f''(x_k))(x-x_k)^2\\ -2f(x_k)=\Bigl[f'(x_k)\pm\sqrt{f'(x_k)^2-2f(x_k)f''(x_k)}\Bigr](x-x_k) $$ For the next iterate $x_{k+1}=x$ the sign gets chosen so that $|x-x_k|$ is the smaller of the two possible values. Close to the root this means that the sign of the root is the same as the sign of $f'(x_k)$.

The limit is possibly about the cubic convergence, with $x$ the closest root of the equation. The expectation is that $\frac{x_{k+1}-r}{(x_k-x)^3}$ converges to a non-zero constant, but the claim is not compatible with that.

Lutz Lehmann
  • 126,666