High-Order Iterative Methods Repeating Roots a Constructive Recapitulation

Isaac Fried

Department of Mathematics, Boston University, Boston, MA, USA.

DOI: 10.4236/am.2022.132011                

Abstract

This paper considers practical, high-order methods for the iterative location of the roots of nonlinear equations, one at a time. Special attention is being paid to algorithms also applicable to multiple roots of initially known and unknown multiplicity. Efficient methods are presented in this note for the evaluation of the multiplicity index of the root being sought. Also reviewed here are super-linear and super-cubic methods that converge contrarily or alternatingly, enabling us, not only to approach the root briskly and confidently but also to actually bound and bracket it as we progress.

Keywords

Roots of Nonlinear Equations, Multiple Roots, Multiplicity Index of a Root, Estimation of the Multiplicity Index of a Root, High-Order Iterative Methods, Root Bracketing, Alternatingly Converging Methods, Contrarily Converging Methods

1. Introduction

This note is mainly concerned with the numerical approximations of function roots by various iterative methods [1] - [8]. A multiplicity greater than one of a function root may greatly impede the convergence method used to iteratively locate it. The multiplicity index m of the sought root is often unknown before hand. It may well be a latent property of the root, not cursorily revealed, nor readily available. In this note, we examine and assess computational procedures to evaluate the multiplicity index m of the iteratively approached root. We further constructively review the iterative methods [9] [10] [11] for approaching a root of a known or unknown multiplicity. Then we suggest several other useful, alternatingly converging and contrarily converging iterative methods to bound the sought root.

2. The Taylor Representation of an Osculating Function

Approximation by polynomials is fundamental to numerical analysis. Taylor’s theorem plays in a crucial role.

The monomial power function

$f\left(x\right)=x^n\mathrm{,}n\ge 1$ (1)

is ever smaller, as n is ever bigger, near $x=0$ . Function $f\left(x\right)$ in Equation (1) is actually such that

$f\left(0\right)=f^{\prime }\left(0\right)=f^{″}\left(0\right)=\cdots =f^{\left(n-1\right)}\left(0\right)=0,f^{\left(n\right)}\left(0\right)\ne 0.$ (2)

Such function is said to be osculating of degree n.

In its most concise form, Taylor’s theorem generalizes this claim to any differential function. It asserts that if Equation (2) holds true for any other differential function $f\left(x\right)$ , then this function is expressible as

$f\left(x\right)=\frac{1}{n!}{x}^n{f}^{\left(n\right)}\left(\xi \right)\text{or}f\left(x\right)=\left(\frac{1}{n!}{f}^{\left(n\right)}\left(\xi \right)\right)x^n,0<\xi <x$ (3)

for x to the right of zero. Equation (3) is said to be the Taylor form of osculating function $f\left(x\right)$ of Equation (2). Power n is said to be the degree of osculation of $f\left(x\right)$ at, here, $x=0$ .

We take in Equation (3)

$f\left(x\right)=A{x}^n+B{x}^{n+1}\mathrm{,}A\ne 0$ (4)

and obtain from it the asymptotic form of intermediate value $\xi$

$\xi =\frac{x}{n+1}$ (5)

forx close to zero.

If the point of osculation of function $f\left(x\right)$ is generally a, then

$\underset{x\to a^{+}}{\lim }\frac{\xi -a}{x-a}=\frac{1}{n+1}\mathrm{.}$ (6)

See also [12] [13].

To observe a higher order approximation to $\xi$ we start with

$f\left(x\right)=x\left(P+Qx+R{x}^2+S{x}^3\right)=x{f}^{\prime }\left(\xi \right)=x\left(P+2Q\xi +3R{\xi }^2+4S{\xi }^3\right).$ (7)

We presume that

$\xi =Ax+B{x}^2$ (8)

and readily have from Equation (7) that

$\xi =\frac{1}{2}x+\frac{1}{8}\frac{R}{Q}{x}^2.$ (9)

3. Repeated Taylor Expansion Examples

Example one. We start with

$r\left(x\right)={\text{e}}^x-\left(c_0+c_{1}x+c_2{x}^2\right)$ (10)

and fix parameters $c_0\mathrm{,}{c}_1\mathrm{,}{c}_2$ so as to have the osculation

$r\left(0\right)=0,r^{\prime }\left(0\right)=0,r^{″}\left(0\right)=0,r^{‴}\left(0\right)={\text{e}}^0=1\ne 0$ (11)

and then

${\text{e}}^x=1+x+\frac{1}{2}{x}^2+r\left(x\right)\mathrm{.}$ (12)

In view of Equation (11) the Taylor form of $r\left(x\right)$ is here

$r\left(x\right)=\frac{1}{3!}{x}^3{r}^{‴}\left(\xi \right)\text{or}r\left(x\right)=\frac{1}{3!}{x}^3{\text{e}}^{\xi },0<\xi <x$ (13)

or further, in view of Equation (11), approximately, if x is small

$r\left(x\right)=\frac{1}{6}{x}^3\left(1+\xi +\frac{1}{2}{\xi }^2\right)\text{for}{\text{e}}^{\xi }=1+\xi +\frac{1}{2}{\xi }^2.$ (14)

Here

$\xi =\frac{1}{4}x$ (15)

Nearly. We assemble Equations (12), (13) and (14) to gain the better polynomial approximation

${\text{e}}^x=1+x+\frac{1}{2}{x}^2+\frac{1}{6}{x}^3\left(1+\xi +\frac{1}{2}{\xi }^2\right)$ (16)

becoming with $\xi$ of Equation (15)

${\text{e}}^x=1+x+\frac{1}{2}{x}^2+\frac{1}{6}{x}^3+\frac{1}{24}{x}^4+\frac{1}{192}{x}^5+r\left(x\right),r\left(x\sim 0\right)=\frac{1}{320}{x}^5.$ (17)

Example two. We write

$r\left(x\right)=\ln \left(1+x\right)-\left(c_0+c_{1}x\right)$ (18)

and fix parameters $c_0\mathrm{,}{c}_1$ so that

$r\left(0\right)=0,r^{\prime }\left(0\right)=0,r^{″}\left(0\right)=-1\ne 0$ (19)

and have the osculating remainder or residual

$r\left(x\right)=\ln \left(1+x\right)-x\mathrm{.}$ (20)

The Taylor form of this osculating residual $r\left(x\right)$ is then

$r\left(x\right)=\frac{1}{2}{x}^2{r}^{″}\left(\xi \right)\text{or}r\left(x\right)=-\frac{1}{2}{x}^2{\left(1+\xi \right)}^{-2}.$ (21)

Here $\xi =x/3$ , nearly, with which we have

$\ln \left(1+x\right)=x-\frac{9}{2}{\left(\frac{x}{3+x}\right)}^2+r\left(x\right),r\left(x\sim 0\right)=-\frac{1}{12}{x}^4.$ (22)

Example three. We start with

$r\left(x\right)=\sqrt{1+x}-\left(c_0+c_{1}x\right)$ (23)

and fix parameters $c_0$ and $c_1$ so as to have both $r\left(0\right)=0$ and $r^{\prime }\left(0\right)=0$ ,

$r\left(x\right)=\sqrt{1+x}-1-\frac{1}{2}x,r\left(0\right)=0,r^{\prime }\left(0\right)=0,r^{″}\left(0\right)=-\frac{1}{4}\ne 0.$ (24)

The Taylor form of osculating function $r\left(x\right)$ in the above Equation (24) is

$r\left(x\right)=\frac{1}{2}{x}^2{r}^{″}\left(\xi \right),0<\xi <x$ (25)

and we write

$\begin{array}{c}\sqrt{1+x}=1+\frac{1}{2}x+r\left(x\right)=1+\frac{1}{2}x-\frac{1}{8}{x}^2{\left(1+\xi \right)}^{-\frac{3}{2}}\\ =1+\frac{1}{2}x-\frac{1}{8}{x}^2{\left(1+\xi \right)}^{-2}\sqrt{1+\xi }.\end{array}$ (26)

Returning to the approximation

$\sqrt{1+\xi }=1+\frac{1}{2}\xi ,\xi =\frac{1}{3}x$ (27)

we finally reach

$\sqrt{1+x}=1+\frac{1}{2}x-\frac{3}{16}{x}^2\frac{6+x}{{\left(3+x\right)}^2}+r\left(x\right),r\left(x\sim 0\right)=-\frac{13}{1152}{x}^4.$ (28)

Example four. The osculating-approximating function need not be a polynomial. Indeed, we write

$r\left(x\right)={\text{e}}^x-\left(c_1\cos x+c_2\sin x\right)$ (29)

and fix parameters $c_1\mathrm{,}{c}_2$ so as to have $r\left(0\right)=0$ , $r^{\prime }\left(0\right)=0$ , $r^{″}\left(0\right)=2\ne 0$ . The Taylor form of function $r\left(x\right)$ is here

$r\left(x\right)=\frac{1}{2}{x}^2{r}^{″}\left(\xi \right)=\frac{1}{2}{x}^2\left({\text{e}}^{\xi }+\cos \xi +\sin \xi \right),\xi =\frac{1}{3}x$ (30)

and

${\text{e}}^x=\cos x+\sin x+r\left(x\right),r\left(x\sim 0\right)=x^2.$ (31)

4. Estimation of the Root Multiplicity Index

Assuming that the power series expansion of function $f\left(x\right)$ , whose root a we are seeking to iteratively locate, is of the form

$f\left(x\right)={\left(x-a\right)}^m\left(A+B\left(x-a\right)+C{\left(x-a\right)}^2+\cdots \right),m\ge 1$ (32)

we obtain from it the first-order estimate for the root multiplicity index m

$u^{\prime }={\left(\frac{f}{f^{\prime }}\right)}^{\prime }=\frac{{f^{\prime }}^2-f{f}^{″}}{{f^{\prime }}^2}=\frac{1}{m}-\frac{2}{m^2}\frac{B}{A}\left(x-a\right)+O\left({\left(x-a\right)}^2\right),u=f/f^{\prime }$ (33)

and

$-\frac{1}{2}\frac{u^{″}}{{u^{\prime }}^2}=\frac{B}{A}+O\left(x-a\right)\mathrm{,}u=f/f^{\prime }\mathrm{.}$ (34)

Then, the second-order estimation

${u^{\prime }}^2-2u{u}^{″}=\frac{1}{m^2}+\frac{6}{m^4}-\frac{B^2\left(1+m\right)+2ACm}{A^2}{\left(x-a\right)}^2+O\left({\left(x-a\right)}^3\right),u=f/f^{\prime }.$ (35)

For example, for $f=x^2+x^3,m=2$ , we compute, at $x=0.1$ , the first-order and second-order approximations

$m=2.18\text{and}m=2.03$ (36)

respectively. For $x=0.1$ and $x=0.01$ we compute from the above Equation (34)

$\frac{B}{A}=0.78\text{and}\frac{B}{A}=0.9753$ (37)

respectively, both for $B/A=1$ .

We have also that, whatever k

$\frac{f\left(x_0-k{u}_0\right)}{f\left(x_0\right)}={\left(1-\frac{k}{m}\right)}^m+O\left(x_0-a\right)$ (38)

from which we have for $k=1$

$\ln r=m\ln \left(1-\frac{1}{m}\right),r=\frac{f\left(x_0-k{u}_0\right)}{f\left(x_0\right)}.$ (39)

By the Padé rational approximation

$\ln \left(1+x\right)=x\frac{x+6}{4x+6}+r\left(x\right),r\left(x\sim 0\right)=-\frac{1}{36}{x}^4$ (40)

we have the first-order estimate

$m=\frac{1}{6}\frac{1+4\ln r}{1+\ln r},r=\frac{f\left(x_0-u_0\right)}{f\left(x_0\right)},u_0=\frac{f_0}{{f^{\prime }}_0}.$ (41)

For example, for $f\left(x\right)=x^3+x^4$ we obtain from the above Equation (41), for $x=\left\{\mathrm{1.0,0.5,0.1}\right\}$ the corresponding root multiplicity index approximations: $m=\left\{\mathrm{3.72,3.51,3.14}\right\}$ for the exact $m=3$ .

We notice that, whatever m, root a of $u=f/f^{\prime }$ is isolated, namely always of multiplicity $m=1$ . Indeed

$u=\frac{f}{f^{\prime }}=\frac{1}{m}\left(x-a\right)-\frac{1}{m^2}\frac{B}{A}{\left(x-a\right)}^2+O\left({\left(x-a\right)}^3\right).$ (42)

5. Second Order Iterative Methods

Our prevailing task is, at first, to stepwise and steadily, approach isolated root a of function $f\left(x\right)$ , $f\left(a\right)=0$ , $f^{\prime }\left(a\right)\ne 0$ . Being at point $x=x_0$ , $f\left(x_0\right)\ne 0$ , we write the Taylor expansion

$f\left(x_0+\delta x\right)=f\left(x_0\right)+\delta x{f}^{\prime }\left(\xi \right),x_0<\xi <x_0+\delta x$ (43)

and readily obtain from it, by the linearization $f\left(x_0+\delta x\right)=0$ , $\xi =x_0$ , the eminent Newton method

$x_1=x_0+\delta x=x_0-u_0,\delta x=-u_0,u_0=\frac{f_0}{{f^{\prime }}_0},f_0=f\left(x_0\right),{f^{\prime }}_0=f^{\prime }\left(x_0\right).$ (44)

The Newton method is a quadratic iterative method to an isolated root

$x_1-a=\left(\frac{1}{2}\frac{f^{″}}{f^{\prime }}\right){\left(x_0-a\right)}^2+O\left({\left(x_0-a\right)}^3\right)$ (45)

where $f^{\prime }=f^{\prime }\left(a\right)\ne 0,f^{″}=f^{″}\left(a\right)<\infty$ .

6. Rectification for a Multiple Root by Undetermined Coefficients

We recast Newton’s method in the open-ended form

$x_1=x-P{u}_0,u_0=\frac{f_0}{{f^{\prime }}_0}$ (46)

with the undetermined coefficient P, and have by Equation (32) that at a root of multiplicity $m\ge 1$

$x_1-a=\left(1-\frac{P}{m}\right)\left(x_0-a\right)+\frac{P}{m^2}\frac{B}{A}{\left(x_0-a\right)}^2+O\left({\left(x_0-a\right)}^3\right)\mathrm{.}$ (47)

Quadratic convergence is restored to the method, as is well known, with $P=m$ . In the equation above, A and B are the coefficients in the power series expansion of $f\left(x\right)$ in Equation (32). But, for this, we need to know in advance the multiplicity index m of root a.

To have a quadratic method not needing the a-priori knowledge of multiplicity index m of the searched root we take the m approximation of Equation (33) and obtain, the quadratic for any m, method

$x_1=x_0-\frac{{f^{\prime }}_0}{{f^{\prime }}_0^2-f_0{f^{″}}_0}{f}_0$ (48)

Method (48) is also obtained by applying Newton’s method to $u=f/f^{\prime }$ . See Equation (42).

The advantage of method (48) is that it is quadratic; its drawback is that it requires $f^{″}$ .

For example, for $f(\; x\; )$

$f=x^m\left(A+Bx\right)$ (49)

we have by method (48) that

$x_1=-\frac{AB}{A^{2}m+2ABm{x}_0+B^2{x}_0^2\left(1+m\right)}{x}_0^2$ (50)

for root $a=0$ of any multiplicity index m.

7. Two-Step Method

To avoid the computation of $f^{″}$ in the modified Newton method (48), we suggest the two-step method

$x_1=x_0-m_0{u}_0,u_0=\frac{f_0}{{f^{\prime }}_0},u_1=\frac{f_1}{{f^{\prime }}_1},m_1=\frac{x_1-x_0}{u_1-u_0}=m_0\frac{u_0}{u_0-u_1},x_2=x_1-m_1{u}_1.$ (51)

To observe its working we apply the method to the trial function $f\left(x\right)$ of Equation (49) and have for the two-step method (51)

$m_1=m+\frac{B}{A}\frac{2m-m_0}{m}{x}_0+O\left(x_0^2\right)$ (52)

and then

$x_2=\frac{B}{A}\frac{m_0-m}{m^2}{x}_0^2+O\left(x_0^3\right).$ (53)

8. Super-Linear Method

With $P=m\left(1-k\right),k<0$ the modified Newton’s method of Equation (46) becomes super-linear and ultimately of alternating convergence [8]. For example, for $f\left(x\right)=x^2+x^3$ , $m=2$ , $k=-1/8$ , we generate, starting with $x_0=1$ the sequence

$x_1=\left\{1,1.0\times {10}^{-1},-7.6\times {10}^{-3},9.8\times {10}^{-4},-1.2\times {10}^{-4},1.5\times {10}^{-5},-1.9\times {10}^{-6}\right\}.$ (54)

9. Third Order Iterative Methods-and Higher

We propose to replace now $\xi =x_0$ in Newton’s method by the better

$\xi =\frac{x_0+x_1}{2}=x_0+\frac{1}{2}\delta x,\delta x=-u_0=-\frac{f_0}{{f^{\prime }}_0}$ (55)

to have the mid-point method

$x_2=x_0-\frac{f\left(x_0\right)}{f^{\prime }\left(x_0+\frac{1}{2}\delta x\right)},\delta x=-u_0=-\frac{f_0}{{f^{\prime }}_0}$ (56)

which now rises in order to become cubic

$x_2-a=\left(\frac{1}{24}\frac{f{f^{″}}^2-f^{\prime }{f}^{‴}}{{f^{\prime }}^2}\right){\left(x_0-a\right)}^3+O\left({\left(x_0-a\right)}^4\right)$ (57)

still with no need for $f^{″}\left(x_0\right)$ . See also Traub [1] page 164 Equations (8-12).

The linearization

$f^{\prime }\left(x_0+\frac{1}{2}\delta x\right)=f^{\prime }\left(x_0\right)+\frac{1}{2}\delta x{f}^{″}\left(\xi \right),\xi =x_0,\delta x=-u_0=-\frac{f\left(x_0\right)}{f^{\prime }\left(x_0\right)}=-\frac{f_0}{{f^{\prime }}_0}$ (58)

reproduces out of Equation (56) the classical method of Halley

$x_1=x_0+\frac{\det \left[\begin{array}{cc}-1& f_0\\ 0& 2{f^{\prime }}_0\end{array}\right]}{\det \left[\begin{array}{cc}{f^{\prime }}_0& f_0\\ {f^{″}}_0& 2{f^{\prime }}_0\end{array}\right]}{f}_0=x_0-\frac{2{f^{\prime }}_0}{2{f^{\prime }}_0^2-f_0{f^{″}}_0}{f}_0=x_0-\frac{1}{1-\frac{1}{2}\left({f^{″}}_0/{f^{\prime }}_0\right)u_0}{u}_0$ (59)

which is likewise cubic

$x_1-a=\left(\frac{1}{12}\frac{3{f^{″}}^2-2f^{\prime }{f}^{‴}}{{f^{\prime }}^2}\right){\left(x_0-a\right)}^3+O\left({\left(x_0-a\right)}^4\right)$ (60)

but requires the, possibly costly, second derivative $f^{″}\left(x\right)$ of $f\left(x\right)$ .

Power series expansion turns the rational Halley’s method into a polynomial in $u_0$ method

$x_1=x_0-u_0-\frac{{f^{″}}_0}{2{f^{\prime }}_0}{u}_0^2,u_0=\frac{f_0}{{f^{\prime }}_0}$ (61)

which is still cubic

$x_1-a=\frac{3{f^{″}}^2-f^{\prime }{f}^{‴}}{6{f^{\prime }}^2}{\left(x_0-a\right)}^3+O\left({\left(x_0-a\right)}^4\right)$ (62)

provided that $f^{\prime }=f^{\prime }\left(a\right)\ne 0$ .

Moreover,

$x_1=x_0-u_0-\frac{{f^{″}}_0}{2{f^{\prime }}_0}{u}_0^2-\frac{{f^{‴}}_0}{3{f^{\prime }}_0}{u}_0^3,u_0=\frac{f_0}{{f^{\prime }}_0}$ (63)

is quartic

$x_1-a=\frac{-{f^{″}}^3+2f^{\prime }{f}^{″}{f}^{‴}+{f^{\prime }}^2{{{f^{\prime }}^{\prime }}^{\prime }}^{\prime }}{8{f^{\prime }}^3}{\left(x_0-a\right)}^4+O\left({\left(x_0-a\right)}^5\right)$

provided that $f^{\prime }\left(a\right)\ne 0$ .

We generalize the method in Equation (63) as

$x_1=x_0-P{u}_0-Q\frac{{f^{″}}_0}{2{f^{\prime }}_0}{u}_0^2-R\frac{{f^{‴}}_0}{3{f^{\prime }}_0}{u}_0^3,u_0=\frac{f_0}{{f^{\prime }}_0}$ (65)

and recover a one-sided cubic convergence method to a root, even of multiplicity m, for

$P=\frac{1}{3}m\left(4-m^2\right),Q=m^3,R=-\frac{1}{2}{m}^3,$ (66)

$x_1-a=\frac{2}{m^2}{\left(\frac{B}{A}\right)}^2{\left(x_0-a\right)}^3+O\left({\left(x_0-a\right)}^4\right).$ (67)

10. Correction of Halley’s Method for Multiple Roots

We rewrite Halley’s method of Equation (59) with the open coefficients P and Q as

$x_1=x_0-\frac{P{f^{\prime }}_0}{Q{f^{\prime }}_0^2-f_0{f^{″}}_0}{f}_0$ (68)

and determine by power series expansion that if (See also [11] )

$P=2,Q=1+\frac{1}{m}$ (69)

then convergence remains cubic for a root of any known multiplicity $m\ge 1$

$x_1-a=\frac{\left(m+1\right)B^2-2mAC}{2m^2{A}^2}{\left(x_0-a\right)}^3+O\left({\left(x_0-a\right)}^4\right)\mathrm{.}$ (70)

11. A Third-Order, One-Sided, Chord Method

Having secured

$x_0,f_0=f\left(x_0\right),{f^{\prime }}_0=f^{\prime }\left(x_0\right),x_1=x_0-u_0,u_0=\frac{f_0}{{f^{\prime }}_0},f_1=f\left(x_1\right)$ (71)

we pass through the two points $\left(x_0\mathrm{,}{f}_0\right)\mathrm{,}\left(x_1\mathrm{,}{f}_1\right)$ the chord, or secant, line

$g\left(x\right)=Px+Q,P=\frac{f_1-f_0}{x_1-x_0},Q=\frac{x_1{f}_0-x_0{f}_1}{x_1-x_0}.$ (72)

We take the root of $g\left(x\right)=0$ , as the next $x_2$ , and have

$x_2=x_0-\frac{1}{1-r}{u}_0\text{or}{x}_2=x_0-\left(1+r\right)u_0\text{or}{x}_2=x_0-\left(1+r+r^2\right)u_0,r=\frac{f_1}{f_0}$ (73)

which are, all three, cubic,

$x_2-a=\frac{1}{4}{\left(\frac{f^{″}}{f^{\prime }}\right)}^2{\left(x_0-a\right)}^3,x_2-a=\frac{1}{2}{\left(\frac{f^{″}}{f^{\prime }}\right)}^2{\left(x_0-a\right)}^3,$

$x_2-a=\frac{1}{4}{\left(\frac{f^{″}}{f^{\prime }}\right)}^2{\left(x_0-a\right)}^3+O\left({\left(x_0-a\right)}^3\right)$ (74)

respectively. See also Traub [1] page 180 Equations (8-55).

Convergence of this method is one sided, namely, if $x_0-a>0$ , then also $x_2-a>0$ , and if $x_0-a<0$ , then also $x_2-a<0$ .

For example, for $f\left(x\right)=x+x^2$ we obtain by the method of the first Equation (73) the two oppositely converging sequences

$x_2=\left\{-\frac{1}{6},-\frac{1}{126},-\frac{1}{1953126}\right\}\text{and}{x}_2=\left\{\frac{1}{4},\frac{1}{28},\frac{1}{1953124}\right\}$ (75)

by which root $a=0$ is bounded, or bracketed, as

$\frac{-1}{1953126}<a<\frac{1}{1953124}.$ (76)

12. Quartic and Quintic Methods

Once $x_2$ is computed by Equation (73), just one additional computation of $f\left(x\right)$ makes the pseudo-Newton’s method

$x_3=x_2-\frac{f\left(x_2\right)}{g^{\prime }\left(x_2\right)}=x_2-\frac{f\left(x_2\right)}{A},A=\frac{f_1-f_0}{x_1-x_0}=\left(1-r\right){f^{\prime }}_0,r=\frac{f_1}{f_0}$ (77)

for $g\left(x\right)$ in Equation (72), quartic

$x_3-a=\frac{1}{4}{\left(\frac{f^{″}}{f^{\prime }}\right)}^3{\left(x_0-a\right)}^4+O\left({\left(x_0-a\right)}^5\right)\mathrm{.}$ (78)

From a parabola passing through the data $\left(x_0\mathrm{,}{f}_0\mathrm{,}{f^{\prime }}_0\right)$ and $\left(x_1\mathrm{,}{f}_1\right)$ we obtain a better approximation for $f^{\prime }\left(x_2\right)$ , and with it the method

$x_3=x_2-\frac{f\left(x_2\right)}{2A-{f^{\prime }}_0}=x_2-\frac{1}{1-2r}\frac{f_2}{{f^{\prime }}_0},r=\frac{f_1}{f_0}$ (79)

which we verify to be quintic

$x_3-a=\left(\frac{1}{12}\frac{{f^{″}}^2\left(3{f^{″}}^2-f^{\prime }{f}^{‴}\right)}{{f^{\prime }}^4}\right){\left(x_0-a\right)}^5+O\left({\left(x_0-a\right)}^6\right)\mathrm{.}$ (80)

13. Fourth-Order, Parabolic Interpolant Method

We can do still better with a parabolic interpolation that includes, the already evaluated, ${f^{\prime }}_0$ . We pass through the data $\left(x_0\mathrm{,}{f}_0\mathrm{,}{f^{\prime }}_0\right)$ and $\left(x_1\mathrm{,}{f}_1\right)$

$x_0,f_0=f\left(x_0\right),{f^{\prime }}_0=f^{\prime }\left(x_0\right),x_1=x_0-u_0,u_0=\frac{f_0}{{f^{\prime }}_0},f_1=f\left(x_1\right)$ (81)

the parabola

$q\left(x\right)=A{x}^2+Bx+C,A=r\frac{{f^{\prime }}_0^2}{f_0},B={f^{\prime }}_0-2r\frac{{f^{\prime }}_0^2}{f_0}{x}_0,C=f_0-{f^{\prime }}_0{x}_0+r\frac{{f^{\prime }}_0^2}{f_0}{x}_0^2$ (82)

where $x_1=x_0-u_0,f_1=f\left(x_1\right),r=f_1/f_0$ , and

$r=\frac{f_1}{f_0}=\left(\frac{1}{2}\frac{f^{″}}{f^{\prime }}\right)\left(x_0-a\right)+O\left({\left(x_0-a\right)}^2\right).$ (83)

We take the nearest root of $q\left(x\right)=0$ , as $x_2$ and have, by expansion in powers of r, the ultimate quartic method

$x_2=-\frac{B+\sqrt{B^2-4AC}}{2A}\text{or}{x}_2=x_0-\left(1+r+2r^2\right)u_0,u_0=\frac{f_0}{{f^{\prime }}_0},$ (84)

$x_2-a=\frac{1}{24}\frac{f^{″}}{{f^{\prime }}^3}\left(15{f^{″}}^2-2f^{\prime }{f}^{‴}\right){\left(x_0-a\right)}^4+O\left({\left(x_0-a\right)}^5\right).$ (85)

Method (84) is the expanded and ultimately truncated form of several published fourth-order chord methods, among them the rational method of Ostrowski [3], appendix G.

$x_2=x_0-\frac{1-r}{1-2r}{u}_0=x_0-\left(1+r+2r^2+4r^3+\cdots \right)u_0,f_1=f\left(x_0-u_0\right),r=\frac{f_1}{f_0}$ (86)

$x_2-a=\left(\frac{1}{24}\frac{f^{″}\left(3{f^{″}}^2-2f^{\prime }{f}^{‴}\right)}{{f^{\prime }}^3}\right){\left(x_0-a\right)}^4+O\left({\left(x_0-a\right)}^5\right).$ (87)

See in particular Traub [1] page 184 Equations (8-78).

14. From a Cubic to a Quartic Method

We write the second order, $n=2$ , version of the Taylor-Lagrange formula

$f\left(x\right)=f\left(x_0\right)+\delta x{f}^{\prime }\left(x_0\right)+\frac{1}{2}\delta x^2{f}^{″}\left(\xi \right),\delta x=x-x_0$ (88)

and take $f\left(x\right)=0,\xi =x_0$ to have the iterative method

$x_1=x_0+\delta x,0=f\left(x_0\right)+\delta x{f}^{\prime }\left(x_0\right)+\frac{1}{2}\delta x^2{f}^{″}\left(x_0\right).$ (89)

We approximate the solution of the increment equation

$f_0+\delta x{f^{\prime }}_0+\frac{1}{2}\delta x^2{f^{″}}_0=0$ (90)

by the power series

$\delta x=\left(P+Q{f}_0+R{f}_0^2+S{f}_0^3+T{f}_0^4+\cdots \right)f_0$ (91)

and have, by substitution and collection that

$\begin{array}{l}\left(1+P{f^{\prime }}_0\right)+\left(Q{f^{\prime }}_0+\frac{1}{2}{P}^2{f^{″}}_0\right)f_0+\left(R{f^{\prime }}_0+PQ{f^{″}}_0\right)f_0^2\\ +\left(S{f^{\prime }}_0+\frac{1}{2}{Q}^2{f^{″}}_0+PR{f^{″}}_0\right)f_0^3+\cdots =0\end{array}$ (92)

from which we have, with $s_0={f^{″}}_0/{f^{\prime }}_0$ , that

$P=-\frac{1}{{f^{\prime }}_0},Q=-\frac{1}{2}{P}^2{s}_0,R=-PQ{s}_0,S=-\left(\frac{1}{2}{Q}^2+PR\right)s_0,T=-\left(QR+PS\right)s_0$ (93)

and so on.

The methods

$x_1=x_0+P{f}_0+Q{f}_0^2\text{and}{x}_2=x_0+P{f}_0+Q{f}_0^2+R{f}_0^3$ (94)

or

$x_1=x_0-\left(1+\frac{1}{2}{v}_0\right)u_0,x_2=x_0-\left(1+\frac{1}{2}{v}_0+\frac{1}{2}{v}_0^2\right)u_0,u=\frac{f}{f^{\prime }},s=\frac{f^{″}}{f^{\prime }},v=us$ (95)

are both (the first is a Chebyshev method) cubic

$\begin{array}{l}{x}_1-a=\frac{1}{6}\frac{3{f^{″}}^2-f^{\prime }{f}^{‴}}{{f^{\prime }}^2}{\left(x_0-a\right)}^3+O\left({\left(x_0-a\right)}^4\right),\\ x_2-a=\left(-\frac{1}{3}\frac{f^{‴}}{f^{\prime }}\right){\left(x-a_0\right)}^3+O\left({\left(x_0-a\right)}^4\right),\end{array}$ (96)

respectively, provided that $f^{\prime }\left(a\right)\ne 0$ .

The method

$x_1=x_0-\left(P+Q{v}_0\right)u_0,u_0=\frac{f_0}{{f^{\prime }}_0},v_0=\frac{f_0{f^{″}}_0}{{f^{\prime }}_0^2},P=\frac{m\left(3-m\right)}{2},Q=\frac{1}{2}{m}^2$ (97)

converges cubically to a root of any known multiplicity $m\ge 1$

$x_1-a=\frac{\left(3+m\right)B^2-2mAC}{2A^2{m}^2}{\left(x_0-a\right)}^3+O\left({\left(x_0-a\right)}^4\right)\mathrm{.}$ (98)

Since here $n=2$ we propose to try

$\xi =\frac{2}{3}{x}_0+\frac{1}{3}{x}_1\mathrm{.}$ (99)

We recalculate $f^{″}\left(\xi \right)$ , and verify that the second method in Equation (94) above, rises by this choice of $\xi$ to a quartic

$x_1-a=\frac{1}{72}\left(\frac{45{f^{″}}^3}{{f^{\prime }}^3}+\frac{{{{f^{\prime }}^{\prime }}^{\prime }}^{\prime }}{f^{\prime }}\right){\left(x_0-a\right)}^4+O\left({\left(x_0-a\right)}^5\right).$ (100)

15. Oppositely Converging Super-Quadratic Methods

We start here with

$x_2=x_0-\left(1+Pr\right)u_0\mathrm{,}{u}_0=\frac{f_0}{{f^{\prime }}_0}\mathrm{,}r=\frac{f_1}{f_0}\mathrm{,}{f}_1=f\left(x_1\right)\mathrm{,}{x}_1=x_0-u_0$ (101)

for undetermined coefficient P, and have

$x_2-a=\frac{1}{2}\frac{f^{″}}{f^{\prime }}\left(1-P\right){\left(x_0-a\right)}^2+O\left({\left(x_0-a\right)}^3\right)\mathrm{.}$ (102)

We ask that

$\frac{f^{″}}{f^{\prime }}\left(1-P\right)=2k{\left(\frac{f^{″}}{f^{\prime }}\right)}^2$ (103)

for parameter k, or, in view of Equation (38), that

$P=1-4k\frac{r}{u_0}$ (104)

by which the iterative method in Equation (101) turns into

$x_2=x_0-\left(1+r\right)u_0+4k{r}^2$ (105)

for any k, and

$x_2-a=k{\left(\frac{f^{″}}{f^{\prime }}\right)}^2{\left(x_0-a\right)}^2+O\left({\left(x_0-a\right)}^3\right)\mathrm{.}$ (106)

This super-quadratic method converges from above if $k>0$ , and from below if $k<0$ .

The interest in the method

$x_2=x_0-2\frac{f_0}{f_0-f_1}{u}_0,x_1=x_0-2u_0,f_1=f\left(x_1\right),u_0=\frac{f_0}{{f^{\prime }}_0}$ (107)

is that it ultimately converges oppositely to Newton’s method,

$x_2-a=-\frac{1}{2}\frac{f^{″}}{f^{\prime }}{\left(x_0-a\right)}^2+O\left({\left(x_0-a\right)}^3\right)$ (108)

as seen by comparing Equation (108) with Equation (45).

For example, for $f\left(x\right)=x+x^2$ we compute, starting at $x_0=1/2$ , from Newton’s method and from method (107), respectively,

$x_1=\left\{\frac{1}{2}\mathrm{,}\frac{1}{8}\mathrm{,}\frac{1}{80}\mathrm{,}\frac{1}{6560}\mathrm{,}\frac{1}{43046720}\right\}\mathrm{,}$

$x_2=\left\{\frac{1}{2}\mathrm{,}-\frac{1}{10}\mathrm{,}-\frac{1}{82}\mathrm{,}-\frac{1}{6562}\mathrm{,}-\frac{1}{43046722}\right\}$

$\frac{1}{2}\left(x_1+x_2\right)=\frac{1}{2}\left\{\frac{1}{1}\mathrm{,}\frac{1}{40}\mathrm{,}\frac{1}{3280}\mathrm{,}\frac{1}{21523360}\mathrm{,}\frac{1}{926510094425920}\right\}$ (109)

and root a is bounded, or bracketed, thereby as

$\frac{-1}{43046722}<a<\frac{1}{43046720}.$ (110)

The average of Newton’s method and the method of Equation (107) is cubic,

$\frac{1}{2}\left(x_1+x_2\right)-a=\left(\frac{1}{6}\frac{f^{‴}}{f^{\prime }}\right){\left(x_0-a\right)}^3+O\left({\left(x_0-a\right)}^4\right).$ (111)

16. Alternatingly Converging Super-Linear and Super-Cubic Methods

We start by modifying Newton’s method into

$x_1=x_0-\left(1+k\right)\frac{f_0}{{f^{\prime }}_0}$ (112)

for anyk, and for which

$x_1-a=-k\left(x_0-a\right)+O\left({\left(x_0-a\right)}^2\right)$ (113)

indicating that, invariably, the method converges, at least asymptotically, alternatingly, if $k>0$ .

For example, for $f\left(x\right)=x+x^2$ , $k=1/8$ , $x_0=1$ , we compute by method (112) the super-linearly converging sequence

$x_1=\left\{\mathrm{1,2.5}\times {10}^{-1}\mathrm{,1.6}\times {10}^{-2}\mathrm{,}-1.7\times {10}^{-3}\mathrm{,2.1}\times {10}^{-4}\mathrm{,}-2.7\times {10}^{-5}\right\}$ (114)

and root $a=0$ is bracketed as

$-2.6706\times {10}^{-5}<a<2.1406\times {10}^{-4}.$ (115)

For a higher order method we start with, the originally quartic

$x_2=x_0-\left(1+r+Q{r}^2\right)u_0,u_0=\frac{f_0}{{f^{\prime }}_0},r=\frac{f_1}{f_0},f_1=f\left(x_0-u_0\right)$ (116)

of Equation (63), and have that

$x_2-a=-k{\left(\frac{f^{″}}{f^{\prime }}\right)}^2{\left(x_0-a\right)}^3+O\left({\left(x_0-a\right)}^4\right),k=\frac{1}{4}\left(Q-2\right)$ (117)

indicating that this super cubic method converges alternatingly if parameter $k>0$ .

For example, for $f\left(x\right)=x+x^2$ we generate by method (116) with $k=1$ the alternating sequence

$x_2=\left\{1,-0.012,8.34\times {10}^{-6},-2.32\times {10}^{-15}\right\}$ (118)

and root $a=0$ is bracketed as

$-2.32\times {10}^{-15}<a<8.34\times {10}^{-6}.$ (119)

17. Still Higher Order Methods

Starting with

$f\left(x\right)=f_0+\delta x{f^{\prime }}_0+\frac{1}{2}\delta x^2{f^{″}}_0+\frac{1}{6}\delta x^3{f}^{‴}\left(\xi \right)$ (120)

we have the suggested iterative method

$x_1=x_0+\delta x,f_0+\delta x{f^{\prime }}_0+\frac{1}{2}\delta x^2{f^{″}}_0+\frac{1}{6}\delta x^3{f^{‴}}_0=0$ (121)

and we take

$\delta x=\left(P+Q{f}_0+R{f}_0^2+S{f}_0^3+\cdots \right)f_0$ (122)

with

$\begin{array}{l}P=-\frac{1}{f^{\prime }},Q=\frac{1}{2}{P}^3{f}^{″},R=P^2\left(Q{f}^{″}+\frac{1}{6}{P}^2{f}^{‴}\right),\\ S=P\left(\frac{1}{2}{Q}^2{f}^{″}+PR{f}^{″}+\frac{1}{2}{P}^{2}Q{f}^{‴}\right).\end{array}$ (123)

The resulting methods

$x_1=x_0+\left(P+Q{f}_0+R{f}_0^2\right)f_0\text{and}{x}_2=x_0+\left(P+Q{f}_0+R{f}_0^2+S{f}_0^3\right)f_0$ (124)

are both quartic

$x_2-a=\left(\frac{1}{24}\frac{{{{f^{\prime }}^{\prime }}^{\prime }}^{\prime }}{f^{\prime }}\right){\left(x_0-a\right)}^4+O\left({\left(x_0-a\right)}^5\right)$ (125)

provided that $f^{\prime }\left(a\right)\ne 0$ .

Recalculating $f^{‴}\left(\xi \right)$ at

$\xi =\frac{3}{4}{x}_0+\frac{1}{4}{x}_1$ (126)

the method rises to quintic

$\begin{array}{c}{x}_2-a=\frac{1}{960{f^{\prime }}^4}\left(840{f^{″}}^4-840f^{\prime }{f}^{″}{f}^{‴}+80f^{\prime }{f}^{‴}-3f{f^{\prime }}^3{f}^{\left(5\right)}\right){\left(x_0-a\right)}^5\\ +O\left({\left(x_0-a\right)}^6\right)\mathrm{.}\end{array}$ (127)

18. Higher-Order Methods, Multiple Root

We reconsider the typical third-order method in Equation (61), but with the arbitrary coefficients P and Q

$x_1=x_0-P{u}_0-Q\frac{{f^{″}}_0}{{f^{\prime }}_0}{u}_0^2,u_0=\frac{f_0}{{f^{\prime }}_0}.$ (128)

By power series expansion we have that

$\begin{array}{c}{x}_1-a=\frac{1}{m^2}\left(m^2-mP+Q-mQ\right)\left(x_0-a\right)\\ +\frac{B}{A{m}^3}\left(mP-3Q+mQ\right){\left(x_0-a\right)}^2+O\left({\left(x_0-a\right)}^3\right)\end{array}$ (129)

and cubic convergence is maintained with

$P=\frac{1}{2}m\left(3-m\right),Q=\frac{1}{2}{m}^2.$ (130)

See also Petković [9], Osada [10], Traub [1], Changbum Chun [11], and in particular Osada, who suggested the simpler remarkable cubic method

$x_1=x_0-\frac{1}{2}m\left(m+1\right)\frac{f_0}{{f^{\prime }}_0}+\frac{1}{2}{\left(m-1\right)}^2\frac{{f^{\prime }}_0}{{f^{″}}_0},m>1.$ (131)

A still higher order method is

$x_1=x_0+P{f}_0+Q\left(m-1\right){f^{\prime }}_0+R\left(m-1\right)\left(m-2\right){f^{″}}_0,m>2.$ (132)

For $m=3$ , for example, we determine that

$R=-\frac{1}{{f^{\prime }}_0},Q=\frac{{f^{″}}_0}{6f_0^{/prime2}},P=-\frac{2{f^{″}}_0^2}{3{f^{\prime }}_0^3}+\frac{5{f^{‴}}_0}{9{f^{\prime }}_0^2}$ (133)

makes the method quartic

$x_1-a=\frac{-8B^3+20ABC-15A^{2}D}{3A^3}{\left(x_0-a\right)}^4+O\left({\left(x_0-a\right)}^5\right).$ (134)

To have a cubic method that does not require an a-priori knowledge of the root multiplicity, we replace f by u to have

$x_1=x_0-v_0-\frac{1}{2}\frac{{u^{″}}_0}{{u^{\prime }}_0}{v}_0^2,v=\frac{u}{u^{\prime }},u=\frac{f}{f^{\prime }}$ (135)

for which

$x_1-a=\frac{\left(1-m\right)B^2+2mAC}{A^2{m}^2}{\left(x_0-a\right)}^3+O\left({\left(x_0-a\right)}^4\right)\mathrm{.}$ (136)

Still higher order methods are readily thus generated. See also [14] [15] [16] and [17].

19. Conclusions

We have demonstrated in this paper the usefulness of a number of practical, high order methods for the iterative location of the roots of single-variable nonlinear equations. We have presented here algorithms to estimate the multiplicity of a considered root. Special attention was given here to algorithms thriftily applicable to multiple roots of initially known and unknown multiplicity.

We have further demonstrated here the advantage of super-linear and super-cubic methods that converge contrarily or alternatingly, enabling us, not only to confidently approach the root, but to also actually bound and bracket it as we progress.

Conflicts of Interest

The authors declare no conflicts of interest regarding the publication of this paper.

References

[1]	Traub, J.F. (1977) Iterative Methods for the Solution of Equations. Chelsea Publishing Company, New York.
[2]	Sharma, J.R. (2005) A Composite Third Order Newton-Steffenson Method for Solving Nonlinear Equations. Applied Mathematics and Computation, 169, 242-246. https://doi.org/10.1016/j.amc.2004.10.040
[3]	Ostrowski, A. (1960) Solution of Equations and Systems of Equations. Academic Press, New York.
[4]	Petković, M. (2009) On Optimal Multipoint Methods for Solving Nonlinear Equations. Novi Sad Journal of Mathematics, 39, 123-130.
[5]	Neta, B. (1979) A Sixth-Order Family of Methods for Nonlinear Equations. International Journal of Computer Mathematics, 7, 157-161. https://doi.org/10.1080/00207167908803166
[6]	Khattri, S.K. and Argyros, I.K. (2010) How to Develop Fourth and Seventh Order Iterative Methods. Novi Sad Journal of Mathematics, 40, 61-67.
[7]	Bi, W.H., Ren, H.M. and Wu, Q.B. (2009) Three-Step Iterative Methods with Eighth-Order Convergence for Solving Nonlinear Equations. Journal of Computational and Applied Mathematics, 225, 105-112. https://doi.org/10.1016/j.cam.2008.07.004
[8]	Fried, I. (2013, May) High-Order Iterative Bracketing Methods. International Journal for Numerical Methods in Engineering, 94, 708-714. https://doi.org/10.1002/nme.4467
[9]	Petković, M.S., Petković, L.D. and Džunić, J. (2010) Accelerating Generators of Iterative Methods for Finding Multiple Roots of Nonlinear Equations. Computers and Mathematics with Applications, 59, 2784-2793. https://doi.org/10.1016/j.camwa.2010.01.048
[10]	Osada, N. (1994) An Optimal Multiple Root-Finding Method of Order Three. Journal of Computational and Applied Mathematics, 51, 131-133. https://doi.org/10.1016/0377-0427(94)00044-1
[11]	Chun, C., Bae, H.J. and Neta, B. (2009) New Families of Nonlinear Third-Order Solvers for Finding Multiple Roots. Computers and Mathematics with Applications, 57, 1574-1582. https://doi.org/10.1016/j.camwa.2008.10.070
[12]	Beesack, P.R. (1966) A General Form of the Remainder in Taylor’s Theorem. The American Mathematical Monthly, 73, 131-133. https://doi.org/10.2307/2313928
[13]	Poffald, E.I. (1990) The Remainder in Taylor’s Formula. The American Mathematical Monthly, 97, 205-213. https://doi.org/10.1080/00029890.1990.11995575
[14]	Fried, I. (2014) Effective High-Order Iterative Methods via the Asymptotic Form of the Taylor-Lagrange Remainder. Journal of Applied Mathematics, Article ID: 108976. https://doi.org/10.1155/2014/108976
[15]	Fried, I. (2014) The Systematic Formation of High-Order Iterative Methods. Journal of Applied and computational Mathematics, 3, 1000165. https://doi.org/10.4172/2168-9679.1000165
[16]	Liu, X. and Pan, Y. (2020) The Numerical Solutions of Systems of Nonlinear Integral Equations with the Spline Functions. Journal of Applied Mathematics and Physics, 8, 470-480. https://doi.org/10.4236/jamp.2020.83037
[17]	Lin, G., Gao, Y. and Sun, Y. (2017) On Local Existence and Blow-Up of Solutions for Nonlinear Wave Equations of Higher-Order Kirchhoff Type with Strong Dissipation. International Journal of Modern Nonlinear Theory and Application, 6, 11-25. https://doi.org/10.4236/ijmnta.2017.61002