We present ever higher order single-point iterative methods for the numerical solution of the nonlinear equation . Then we show that for these methods are optimal in the sense of Pell’s equation (see     ), namely, that if the initial guess satisfies the diophantine Pell’s equation , for some integer k, then the iterated value , obtained by a method of order n, satisfies the Pell equation .
Using a generalization of the recursive solution to Pell’s equation we generate super-linear and super-quadratic methods that converge alternatingly and oppositely to provide upper and lower bounds on the targeted root (see    ).
2. Pell’s Equation
Let N be a positive integer which is not a square. The pair of natural numbers p, q satisfying the general Pell’s equation (see     ):
are such that
nearly, if . If k > 0, then p/q is an overestimate of , and if k < 0, then p/q is an underestimate of .
We verify (see  , Chapter 32) that a new solution pair to the optimal, or minimal ( ), Pell’s equation is obtained from a known solution pair by the expansion of
where variable n is taken odd for .
For example, if we take in Equation (3) n = 2, then (see   , and also   )
which is Newton’s method, preferably written as
3. Super-Linear Iterative Method
We start with the general power series expansion around
and ask that , or that is a fixed-point of iteration function . Now we pass from the general to the specific
for parameters , and we ask, here specifically, that
or, again, that is a fixed-point of the rational iteration function in Equation (9). To satisfy Equation (10) we take , and are left with
in which in the second denominator is written for .
Writing and , the iterative method assumes the form
for parameters A and C. Referring to Equation (12) we have
Lemma 1. If are such that , and , then are such that .
Proof. We verify that
and the result follows.
For instance, if and , then
Observe that the iterative method (11) converges linearly for any , since then
4. Alternating Convergence
If in Equation (11), , then and are of the same sign, but if , they are of opposite signs. Also, the smaller , the faster the convergence.
The method of Equation (11), as well as higher order methods, can be derived directly, in reverse, from the generalized Equation (3)
with n = 1 and m = 1. Indeed, expansion of Equation (16) brings it to the form
which elicits the pair of equations
with A = p and C = q in Equation (11).
For example, taking in Equation (11) , , , , , we obtain from it the alternating sequence of convergents:
5. The Method of Newton and Its Opposites
Taking in Equation (9) , or and , the linear method rises to become the quadratic method of Newton, otherwise directly obtainable from Equation (3) with n = 2 (see Equations (5)-(7)).
Here, for Newton’s method
nearly, if is close to .
is such that
if is close to . Here, convergence is quadratic and from below. Compare Equations ((21) and (24)).
The average of methods (5) and (22)
For example, for N = 2 and we obtain from method (6) , from method (22) , and for their average , and
The biased average method
produces an oppositely converging quartic method such that, asymptotically
Compare Equations ((26) and (30)).
The biased average method
is a quintic method and such that
implying that the convergence of method (31) is alternating. Indeed, starting with we obtain from method (31)
6. More Convergence from Below
The noteworthy method
converges to quadratically and from below,
We write and and have for Equation (34) that
7. Super-Linear Alternating Methods
We put in Equation (11)
nearly, if is close to and , the super-linear method
A small negative causes method (39) to ultimately oscillate, or alternate.
method (39) becomes cubic and of alternating convergence
8. Stacked Methods
we have the stacked method
It is such that if
nearly, if both epsilons are small compared with .
If , then , and if , then . For example, for N = 2 we obtain from the stacked method of Equation (44) the alternatingly converging sequence
9. Halley’s Third-Order Method
Halley’s cubic iterative method
becomes for and
and is verified to be such that
implying that if is an underestimate (k < 0), then so is , and if is an overestimate (k > 0), then so is .
nearly, if is close to .
10. Fourth-Order Method
The quartic method (see   for higher order methods):
becomes for and
observed to be a repeated second order method and such that
if is close to . Convergence here is from above.
11. Fifth-Order Method
The quintic method
becomes for and
and happens to be such that
if is close to .
12. A Rational Quadratic Method
is merely in disguise. Replacement of by the good rational approximation p/q turns the scheme into
and for the specific , it becomes
Starting with we obtain , . Starting with we obtain , . Then
obtained from Equation (62) with , we compute
13. The General Rational Super-Quadratic Method
We start by writing
To have a factor in the numerator of the right-hand side of Equation (69), we ask that
and the method
that can be raised to cubic with the choice .
Instead, we leave to have the method
For example, for , we obtain from Equation (73)
For , we obtain from Equation (73)
Equation (73), as well as higher order methods, could have been derived directly, in reverse, from
14. The Direct Construction of a Super-Quadratic Method
To locate root a of , , we start by writing the fixed-point iterative method
for constants A and B. Then we require that
where is any parameter.
Differentiating once and twice, the previous system of two equations in the two unknowns A and B becomes
which we solve to have
Since root a of is unknown we replace a by to have the method
where etc. Here
and convergence is from below if , while convergence is from above if .
the method becomes
For example, for , and we have and . For we have and .
makes method (82) the quartic
15. The Simplest of All Methods
A simple routine for constructing a rational approximation to an irrational number consists of starting with any good rational approximation p/q to, say, , then adding one to p if , or adding one to q if . Starting with 3/2 we obtain this way the alternating sequence
The method is sluggish, yet we can glean from this long sequence some very good Pell approximations to , such as ; ; ; ; ; ; ; . Number .
Going up to 4-digit approximations we find , , and then , . Among the 5-digit approximations we find , and , .
Thus, the alternating sequence of rational approximations to
is of excellent p/q rational approximations to such that if , and if .
For N = 7 we find this way ; ; for the upper bounds, and ; ; ; for the lower bounds.
To understand the convergence mechanism of this algorithm, let p/q be the last fraction less then , namely, such that , but . Then
and the bounds on become tighter as q increases by the repeated addition of 1 to it.
16. Bisection by Mediants
Mediant m of the two nonzero rationals is
Lemma 2. We have
Proof. Since , , and the result follows.
Lemma 3. We have
If , then , and . (93)
Proof. The result follows by some simple algebra.
For example, from Equation (89) we have that with . Here the mediant , and with . The next , and with ; all spreads between the upper and lower bounds having a numerator equal to one.
Unlike ordinary bisections, bisection by mediants converges to a rational number in a finite number of steps. For example, by mediants
while by ordinary bisection
17. Root Bracketing
We start with the following result.
Lemma 4. Let the integer pair satisfy Pell’s equation , and let , . Then
Proof. The result follows by common denominator.
Numerical example. For we have that . Hence, in accordance with Lemma 1
Choosing the Pell (k = 1) pair , , we obtain the Pell ( ) pair , , and
of a numerator equal to one.
Similarly, choosing the Pell (k = 1) pair we obtain the Pell ( ) pair , and
The mediant in Equation (99) is , and with it
In this paper we have examined single-step iterative methods for the solution of the nonlinear algebraic equation , for some integer N, which produce rational approximations p/q that are optimal in the sense of Pell’s equation for some integer k. We have also considered the most elementary bisection method for iteratively creating upper and lower bounds on the targeted root.
Conflicts of Interest
The authors declare no conflicts of interest regarding the publication of this paper.