I am having difficulty understanding the Taylor expansion and solving for $f(x) = 0$

Using evaluations of $f(x_n)$, $f'(x_n)$, and $f''(x_n)$. The following remarks may be helpful in constructing the algorithm"

$\quad \quad \bullet$ Use the Taylor expansion with three terms plus a remainder term.

$\quad \quad \bullet$ Show that in the course of derivation a quadratic equation arises, and therefor two distainct schemes can be derived.

Here is the question exactly.

a. Another method for solving $f(x) = 0$ is to consider the third-order approximation of $f$ around the point $x_n$:

b. Show that the order of convergence (under the appropriate conditions ) is cubic.

From my professors notes he says,

for some point $\xi$ between $x^*$ and $x_n$. If $x_n$ is already fairly close to $x^*$, then $(x^* - x_n)^2$ will be very small, so we have

$$0 \approx f(x_k) + f'(x_k)(x^* - x_k).$$

But that was when he only had the Taylor Series Theorem at second order I believe, so I am supposed to solve it for third order.

Directly from his notes and using his logic about $(x^*-x_n)^2$ being too small so I figured that if that cancels out when squared then perhaps it does when it is cubed.

Here is my attempt at solving it applying my profs notes.

$$ f(x^*) = f(x_n) + f'(x_n)(x^* - x_n) + \frac{f''(x_n)}{2}(x^* - x_n)^2 + \frac{f'''(\xi)}{6}(x^* - x_n)^3 $$

$$0 \approx f(x_n) + f'(x_n)(x^* - x_n) + \frac{f''(x_n)}{2}(x^* - x_n)^2.$$

Right here is where the quadratic arises

Solving for $x^*$, we obtain

$$ 2 [ -f(x_n) - f'(x_n)(x^* - x_n) ] \approx f''(x_n)(x^* - x_n)^2$$

$$ 2 \frac{-f(x_n) - f'(x_n)(x^* - x_n)}{f''(x_n)} \approx (x^* - x_n)^2$$

Which is where I get stuck so I don't know how to approac the problem further. Any help would be appreciated.


You have to solve $0=a+bs+cs^2+O(s^3)$. You could apply the quadratic solution formula and obtain the original method that Halley used, or you could apply some binomial formula tricks to reduce the equation to a linear equation by multiplying with $(b-cs)$ to get $$ 0=a(b-cs)+(b^2-c^2s^2)s+O(s^3)=ab+(b^2-ac)s+O(s^3) $$ leading to the Halley method in its hyperbolic form as it is usually known today $$ (x^*-x_n)=s\approx -\frac{ab}{b^2-ac}=-\frac{f(x_n)f'(x_n)}{f'(x_n)^2-\frac12f''(x_n)f(x_n)}. $$


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.