Applied Mathematics
Vol.09 No.07(2018), Article ID:86296,13 pages
10.4236/am.2018.97059
Newton, Halley, Pell and the Optimal Iterative High-Order Rational Approximation of
Isaac Fried
Department of Mathematics, Boston University, Boston, MA, USA
Copyright © 2018 by author and Scientific Research Publishing Inc.
This work is licensed under the Creative Commons Attribution International License (CC BY 4.0).
http://creativecommons.org/licenses/by/4.0/
Received: June 29, 2018; Accepted: July 27, 2018; Published: July 30, 2018
ABSTRACT
In this paper we examine single-step iterative methods for the solution of the nonlinear algebraic equation , for some integer N, generating rational approximations p/q that are optimal in the sense of Pell’s equation for some integer k, converging either alternatingly or oppositely.
Keywords:
Iterative Methods, Super-Linear and Super-Quadratic Methods, Square Roots, Pell’s Equation, Optimal Rational Iterants, Root Bounds
1. Introduction
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 [1] [2] [3] [4] ), 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 [5] [6] [7] ).
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 [1] [2] [3] [4] ):
(1)
are such that
(2)
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 [1] , 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
(3)
where variable n is taken odd for .
For example, if we take in Equation (3) n = 2, then (see [8] [9] , and also [10] [11] )
(4)
and
(5)
which is Newton’s method, preferably written as
(6)
Here
(7)
3. Super-Linear Iterative Method
We start with the general power series expansion around
(8)
and ask that , or that is a fixed-point of iteration function . Now we pass from the general to the specific
(9)
for parameters , and we ask, here specifically, that
(10)
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
(11)
in which in the second denominator is written for .
Writing and , the iterative method assumes the form
(12)
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
(13)
and the result follows.
For instance, if and , then
(14)
Observe that the iterative method (11) converges linearly for any , since then
(15)
and .
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)
(16)
with n = 1 and m = 1. Indeed, expansion of Equation (16) brings it to the form
(17)
which elicits the pair of equations
(18)
with A = p and C = q in Equation (11).
For example, taking in Equation (11) , , , , , we obtain from it the alternating sequence of convergents:
(19)
with
(20)
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
(21)
nearly, if is close to .
The method
(22)
is such that
(23)
or
(24)
if is close to . Here, convergence is quadratic and from below. Compare Equations ((21) and (24)).
The average of methods (5) and (22)
(25)
is quartic
(26)
Or
(27)
For example, for N = 2 and we obtain from method (6) , from method (22) , and for their average , and
(28)
Here, .
The biased average method
(29)
produces an oppositely converging quartic method such that, asymptotically
(30)
Compare Equations ((26) and (30)).
The biased average method
(31)
is a quintic method and such that
(32)
implying that the convergence of method (31) is alternating. Indeed, starting with we obtain from method (31)
(33)
6. More Convergence from Below
The noteworthy method
(34)
converges to quadratically and from below,
(35)
We write and and have for Equation (34) that
(36)
7. Super-Linear Alternating Methods
We put in Equation (11)
(37)
and obtain
(38)
nearly, if is close to and , the super-linear method
(39)
A small negative causes method (39) to ultimately oscillate, or alternate.
With
(40)
method (39) becomes cubic and of alternating convergence
(41)
8. Stacked Methods
From
(42)
we have the stacked method
(43)
or
(44)
It is such that if
(45)
then
(46)
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
(47)
with
(48)
9. Halley’s Third-Order Method
Halley’s cubic iterative method
(49)
becomes for and
(50)
and is verified to be such that
(51)
implying that if is an underestimate (k < 0), then so is , and if is an overestimate (k > 0), then so is .
Otherwise, here
(52)
nearly, if is close to .
10. Fourth-Order Method
The quartic method (see [12] [13] for higher order methods):
(53)
becomes for and
(54)
observed to be a repeated second order method and such that
(55)
Otherwise, here
(56)
if is close to . Convergence here is from above.
11. Fifth-Order Method
The quintic method
(57)
becomes for and
(58)
and happens to be such that
(59)
Otherwise, here
(60)
if is close to .
12. A Rational Quadratic Method
The method
(61)
is merely in disguise. Replacement of by the good rational approximation p/q turns the scheme into
(62)
and for the specific , it becomes
(63)
Starting with we obtain , . Starting with we obtain , . Then
(64)
From
(65)
obtained from Equation (62) with , we compute
(66)
with
(67)
13. The General Rational Super-Quadratic Method
We start by writing
(68)
to have
(69)
To have a factor in the numerator of the right-hand side of Equation (69), we ask that
(70)
resulting in
(71)
and the method
(72)
that can be raised to cubic with the choice .
Instead, we leave to have the method
(73)
such that
(74)
For example, for , we obtain from Equation (73)
(75)
For , we obtain from Equation (73)
(76)
Equation (73), as well as higher order methods, could have been derived directly, in reverse, from
(77)
with .
14. The Direct Construction of a Super-Quadratic Method
To locate root a of , , we start by writing the fixed-point iterative method
(78)
for constants A and B. Then we require that
(79)
where is any parameter.
Differentiating once and twice, the previous system of two equations in the two unknowns A and B becomes
(80)
which we solve to have
(81)
Since root a of is unknown we replace a by to have the method
(82)
where etc. Here
(83)
and convergence is from below if , while convergence is from above if .
For
(84)
the method becomes
(85)
For example, for , and we have and . For we have and .
The choice
(86)
makes method (82) the quartic
(87)
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
(88)
where .
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
(89)
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
(90)
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
(91)
Lemma 2. We have
(92)
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
(94)
while by ordinary bisection
(95)
17. Root Bracketing
We start with the following result.
Lemma 4. Let the integer pair satisfy Pell’s equation , and let , . Then
(96)
Proof. The result follows by common denominator.
Numerical example. For we have that . Hence, in accordance with Lemma 1
(97)
Choosing the Pell (k = 1) pair , , we obtain the Pell ( ) pair , , and
(98)
of a numerator equal to one.
Similarly, choosing the Pell (k = 1) pair we obtain the Pell ( ) pair , and
(99)
The mediant in Equation (99) is , and with it
(100)
18. Conclusion
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.
Cite this paper
Fried, I. (2018) Newton, Halley, Pell and the Optimal Iterative High-Order Rational Approximation of
References
- 1. Silverman, J.H. (2006) A Friendly Introduction to Number Theory, Chapter 12. Prentice Hall, New Jersey.
- 2. Whitford, E.E. (1912) The Pell Equation. E. E. Whitford, New York.
- 3. Barbeau, E.J. (2000) Pell’s Equation. Springer, New York.
- 4. Jacobson Jr., M.J. and Williams, H.C. (2009) Solving the Pell Equation. Springer, New York.
- 5. Fried, I. (2009) Oppositely Converging Newton-Raphson Method for Nonlinear Equilibrium Problems. International Journal for Numerical Methods in Engineering, 79, 375-378. https://doi.org/10.1002/nme.2574
- 6. Fried, I. (2013) High-Order Iterative Bracketing Methods. International Journal for Numerical Methods in Engineering, 94, 708-714. https://doi.org/10.1002/nme.4467
- 7. Fried, I. (2014) Effective High-Order Iterative Methods via the Asymptotic Form of the Taylor-Lagrange Remainder. Journal of Applied Mathematics, 2014, Article ID: 108976. https://doi.org/10.1155/2014/108976
- 8. Brown, L.M. (1997) An Algorithm for Square Roots: An Episode in the Campaign Against Dotage. The Mathematical Gazette, 81, 428-429. https://doi.org/10.2307/3619622
- 9. McBride, A. (1999) Remarks on Pell’s Equation and Square Root Algorithms. The Mathematical Gazette, 83, 47-52. https://doi.org/10.2307/3618682
- 10. Dunkel, O. (1927) A Note on the Computation of Arithmetic Roots. The American Mathematical Monthly, 34, 366-368. https://doi.org/10.2307/2300041
- 11. Uspensky, J.V. (1927) Note on the Computation of Roots. The American Mathematical Monthly, 34, 130-134. https://doi.org/10.1080/00029890.1927.11986665
- 12. Neta, B. (1979) A Sixth-Order Family of Methods for Nonlinear Equations. International Journal of Computer Mathematics, Section B, 7, 157-161. https://doi.org/10.1080/00207167908803166
- 13. Fried, I. (2016) A Remarkable Chord Iterative Method for Roots of Uncertain Multiplicity. Applied Mathematics, 7, 1207-1214. https://doi.org/10.4236/am.2016.711106