1
$\begingroup$

There is a numerical method for solving non-linear equations which uses the Taylor Series:

$$f(x_n+e_n)=f(x_n)+f'(x_n)e_n+\cdots+\frac{f^{(k)}(x_n)}{k!} e_n^k+\cdots+=0$$

The solution is then found through the iteration:

$$x_{n+1}=x_n+e_n$$

For $k=1$ we have:

$$e_{n1}=-\frac{f_{n}}{f'_{n}}$$

For $k=2$ we have:

$$e_{n2}=-\frac{f_{n}}{f'_{n}+\frac{f''_{n}}{2!}e_{n1}}$$

and so on...

My questions are:

  1. What is the name of that method?

  2. Solving for $k=2$ we get:

$$e_{n2}=-\frac{f_{n}}{f'_{n}+\frac{f''_{n}}{2!}e_{n2}}$$

so why we set $e_{n2}=e_{n1}$?

$\endgroup$
  • $\begingroup$ You should have a negative sign in front of the $e_{n2}$ terms. The name for $k=2$ is Halley's method. See the Wikipedia article on Halley's method for an answer to question 2. $\endgroup$ – J. Heller Feb 8 '17 at 23:36
  • $\begingroup$ @J.Heller Indeed I will correct it. $\endgroup$ – Adam Feb 8 '17 at 23:41
  • $\begingroup$ @Winther I know. What I want is the name of that general procedure. $\endgroup$ – Adam Feb 8 '17 at 23:43
  • $\begingroup$ Probably you are looking for "Householder methods". There is a wikipedia page for it, I think there or on its talk page this iterative computation is also discussed. However, the only source for the name is a website/preprint that is also scarce in published sources. $\endgroup$ – Dr. Lutz Lehmann Feb 9 '17 at 13:38
1
$\begingroup$

I will try to address the "why $e_{n1}$ instead of $e_{n2}$" issue mentioned by OP. The method you seem to start with is to Taylor expand $f$ to $k$'th order

$$T_k[f](x_n +e_n) = f(x_n) + f'(x_n)e_n + f''(x_n)\frac{e_n^2}{2!} + \ldots + \frac{f^{(k)}(x_n)}{k!}e_n^k$$

and then solve for $e_n$ such that $T_k[f](x_n+e_n) \approx f(x_n + e_n) = 0$ and use $x_{n+1} = x_n + e_n$ as an itteration to find a zero of $f$. This is a perfectly valid starting point for constructing a root-finding method, however doing it directly like this has some issues that makes it not very useful in general. To see why this is so, let's go through the first few values of $k$ and see what it gives us.

If we do this for $k=1$ then we obtain good old Newton's method

$$e_n = - \frac{f(x_n)}{f'(x_n)} \implies x_{n+1} = x_n - \frac{f(x_n)}{f'(x_n)}$$

If we do this for $k=2$ we obtain the equation $$e_n = -\frac{f(x_n)}{f'(x_n) + \frac{f''(x_n)}{2}e_n}\tag{1}$$ which can be solved for $e_n$ to give

$$e_n = \frac{-f'(x_n) \pm \sqrt{f'^2(x_n) - 4f(x_n)f''(x_n)}}{f''(x_n)}$$ Here we see a possible problem: if $f'^2(x_n) - 4f(x_n)f''(x_n) < 0$ then the iteration would break down as we will get imaginary numbers: the equation has no solution in the reals (which could happen for all even $k$). This makes this method of limited use as this would happen for quite a large range of functions. If we instead take $e_n$ on the right hand side of $(1)$ to be the result for $k=1$, i.e. $e_n = -f(x_n)/f'(x_n)$, then we obtain Halleys method

$$e_n = -\frac{f(x_n)}{f'(x_n) - \frac{f''(x_n)f(x_n)}{2f'(x_n)}}$$

which is a good method as long as $f''$ exist and it's not to hard/expensive to compute it.

For higher $k$ we run into the problem of having to solve a complicated polynomial equation. This is formally possible for $k=3$ and $k=4$, but this leads to very complicated expressions and for $k>4$ we would need a numerical solver to solve the polynomial equation for which this method looses all of it's appeal (we need a root-finder inside of a root-finder). One possible solution to this is to do it like in Householder's method which is a generalization of the procedure done above for $k=2$. This method can be though of as using the formula for $e_n$ for a lower $k$ to construct the formula for $e_n$ instead of trying to solve the polynomial equation (this is illustrated quite well in the last formula in LutzL's answer). This does not have the problems I mentioned above and as long as the higher order derivatives needed in the formula are easy/fast to compute then this is a good method.

$\endgroup$
2
$\begingroup$

The Householder (?) methods are a generalization of Newton's and Halley's method with the closed formula $$ x_{n+1} = x_n+k\frac{(1/f)^{(k-1)}(x_n)}{(1/f)^{(k)}(x_n)} \text{ i.e., } e_{n,k}=k\frac{(1/f)^{(k-1)}(x_n)}{(1/f)^{(k)}(x_n)} $$

Let the local power series of $f$ and $g=1/f$ be $f(x+e)=\sum a_ke^k$ and $g(x+e)=\sum b_ke^k$. The product of both has to be the constant $1$. If the closest singularity of $g$, i.e., the closest root of $f$ as complex function, is real (and simple, and the following limit exists etc.), then it is located at $x_+=x+e$ with $$ e=\lim_{k\to\infty}\frac{b_{k-1}}{b_k}=\lim_{k\to\infty}k\frac{g^{(k-1)}(x)}{g^{(k)}(x)} $$ Now introduce the $e_k=\frac{b_{k-1}}{b_k}$ so that for $j<k$ $$ b_j=b_ke_k…e_{j+1} $$ and for $k>1$ the Cauchy product formula reads as \begin{align} 0&=a_0b_k+a_1b_{k-1}+a_2b_{k-2}+…+a_kb_0 \\ &=a_0b_k+(a_1+a_2e_{k-1}+a_3e_{k-1}e_{k-2}+…+a_ke_{k-1}…e_1)b_{k-1} \end{align} so that $$ e_k=\frac{b_{k-1}}{b_k}=-\frac{a_0}{a_1+e_{k-1}(a_2+e_{k-2}(a_3+…))} =-\frac{f}{f'+e_{k-1}(\frac{f''}{2!}+e_{k-2}(\frac{f'''}{3!}+…(e_1\frac{f^{(k)}}{k!})))} $$

$\endgroup$
0
$\begingroup$

Halley's method is used for computing square roots or $n$th roots. If you used $e_{n2}$ in the denominator instead of $e_{n1},$ there would be a square root in each iteration, defeating the purpose of using the method. However, Halley preferred the method with $e_{n2}$ in the denominator (called Halley's irrational formula) for computing cube roots (see Halley's method). For a cube root, the "irrational formula" iteration for finding the cube root of $a$ is $$ x_{n+1} = x_n/2 + \sqrt{12ax_n - 3x_n^4}/(6x_n) $$ whereas the standard Halley's method iteration is $$ x_{n+1} = (x_n^4 + 2ax_n) / (2x_n^3 + a). $$ I have compared these methods on a computer for computing the cube root of 2 and the "irrational formula" does have a somewhat faster convergence rate. But the total time on a computer is slower because of the square root at each iteration.

$\endgroup$
  • $\begingroup$ What this answer has to do with my question? $\endgroup$ – Adam Feb 9 '17 at 0:09
  • $\begingroup$ I believe that if you used $e_{n2}$ instead of $e_{n1}$ in the denominator, the convergence would still only be cubic. So it is better to use $e_{n1}$ because you avoid the square root that way. $\endgroup$ – J. Heller Feb 9 '17 at 0:13
  • $\begingroup$ I have no problem with the convergence even if it is cubic. What I have a problem with is finding the reason why $e_{n1}=e_{n2}$. Also Winther mentioned the name of a similar method not the one I described so I still need the name. $\endgroup$ – Adam Feb 9 '17 at 2:39
  • $\begingroup$ Try the example of $f(x)=x^2-a$ using $e_{n2}$ in the denominator. The iteration you get is $x_{n+1} = \pm \sqrt{a},$ which is useless for computing the square root of $a$ (on a computer or by hand). On the other hand, the iteration you get using Halley's method (with $e_{n1}$ in the denominator) is $x_{n+1} = (x_n^3 + 3ax_n) / (3x_n^2 + a),$ which has cubic convergence, meaning it converges extremely fast. For example with $a=2$ and an initial guess of $x_0=1$, we get $x_1^2-2=-.04$, $x_2^2-2=-1.03\times 10^{-6}$, $x^2_3-2=-1.08 \times 10^{-19}.$ $\endgroup$ – J. Heller Feb 9 '17 at 3:26
  • $\begingroup$ I don't believe that I can make my questions clearer. I just want the name of the method and the reason why $e_{n1}=e_{n2}$. All those comments provide neither. I thank you for your answer and your commitment to it but it is not helpful to me. I am sorry. $\endgroup$ – Adam Feb 9 '17 at 5:47

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.