(11C) Roots of f(x)=0 in an Interval

[Gamo]

Found this Solver Program from
HP-19C Solutions Book (Mathematics 1977) on Page 13

According to this solutions book this solver find Roots in an Interval.
This program uses a "half-interval" search to find the real roots of an equation
f(x)=0 in a closed interval [a,b]

Specify Accuracy Tolerance and search increment.

The program then begins at the left of the interval and compares the functional
values a the ends of the interval.

I have test these roots searching speed between the Newton's Method program from the
HP-11C User's Handbook with this HP-19C Solution Book and found that
the Half-Interval Method is faster than the Newton's Method.

--------------------------------------------------------

Procedure:

[A] Tolerance and Search Increment values
[B] Interval [x1,x2]
[C] Search for Roots [R/S] for more Roots

**Available Register**
R0 and R9 up to any available space.

---------------------------------------------------------
Example from 19C Solutions Book

X^3 - 8X^2 + 5X + 14 = 0

Set Tolerance 10^-6 and increment by 1
Interval between -10 to 10

Enter your equation at LBL E

STO 0
3
Y^X
RCL 0
X^2
8
x
-
5
RCL 0
x
+
1
4
+
RTN

Tolerance and Search Increment: [EEX] [CHS] 6 [ENTER] 1 [A]
Interval: 10 [CHS] [ENTER] 10 [B]
Search for Roots: [C] display -1 [R/S] 2 [R/S] 7

Answer:
x1 = -1
x2 = 2
x3 = 7

------------------------------------------------------
Program:

Code:


LBL A
STO 6
Rv
STO 5
RTN
-------------------------
LBL B
STO 7
Rv
STO 1
RTN
-------------------------
LBL C
RCL 1
GSB E
STO 3
X=0
GSB 9
RCL 1
RCL 6
+
STO 2
STO 8
GSB E
RCL 3
x
X<0
GTO 8
RCL 2
STO 1
RCL 6
+
STO 2
RCL 7
X<>Y
X>Y
R/S
GTO C
------------------------
LBL 6
RCL 4
STO 2
GTO 8
-----------------------
LBL 7
RCL 4
R/S
RCL 8
STO 1
GTO C
----------------------
LBL 9
RCL 1
R/S
RTN
----------------------
LBL 8
RCL 1
RCL 2
+
2
÷
STO 4
GSB E
ABS
RCL 5
X>Y
GTO 7
RCL 1
GSB E
STO 3
RCL 4
GSB E
RCL 3
x
X<0
GTO 6
RCL 4
STO 1
GTO 8
---------------------
LBL E
Start f(x)
.
.
.
.
RTN

Gamo

[Thomas Klemm]

(12-20-2018 07:38 AM)Gamo Wrote:  I have test these roots searching speed between the Newton's Method program from the
HP-11C User's Handbook with this HP-19C Solution Book and found that
the Half-Interval Method is faster than the Newton's Method.

The convergence speed of the binary search is linear while it is quadratic for Newton's method.
Therefore, I am somewhat skeptical of this statement.

For comparison, here is a skeleton for Newton's method for polynomials that uses Horner's method to compute both \(f(x)\) and \(f'(x)\):

Code:

01 RCL I
02 FRAC
03 STO I
04 CLx
05 ENTER
06 LBL 0
07 x<>y
08 R↑
09 ×
10 x<>y
11 +
12 LSTx
13 R↑
14 ×
15 RCL (i)
16 +
17 ISG
18 GTO 0
19 x<>y
20 ÷
21 -
22 ENTER

The coefficients of the polynomial are entered in the registers 0, 1, 2, …

Example:
Your polynomial \(x^3 - 8x^2 + 5x + 14\) is entered as:

1 STO 0
-8 STO 1
5 STO 2
-14 STO 3

The degree n is entered as nE-3 in register I:

0.003 STO I

The initial guess (e.g. 2.5) is entered in X and Y:

2.5 ENTER
R/S
2.015384615

It returns an improved estimate.
You can iterate the process for as long as you like by pressing R/S:

2.5
2.015384615
2.000030948
2.000000000

After only 3 iterations we end up with the exact result.

Cheers
Thomas

[Dieter]

(12-20-2018 07:38 AM)Gamo Wrote:  According to this solutions book this solver find Roots in an Interval.
This program uses a "half-interval" search to find the real roots of an equation
f(x)=0 in a closed interval [a,b]

This is usually called bisection. A simple but ineffective method.

(12-20-2018 07:38 AM)Gamo Wrote:  I have test these roots searching speed between the Newton's Method program from the HP-11C User's Handbook with this HP-19C Solution Book and found that
the Half-Interval Method is faster than the Newton's Method.

Bisection converges faster than Newton? Tell me about it. ;-)

Sorry, Gamo, but bisection is a simple but not very effective moethod for finding roots of a function. Newton's method usually is much faster. Of course for the particular example you give bisection works nicely: according to the input data the program checks the function at –10, –9, –8, ..., 8, 9 and 10 while the roots are at –1, 2 and 7. This means that the bisection algorithm does not even have to be applied, the three roots are directly found at the ends of an interval.

The advantage of this program is its ability to find multiple roots within an interval. But this should be combined with a method that is more effective than bisection. For instance the secant method or regula falsi. Here you can also specify an interval but the root within that interval is found much faster. I would recommend a modifed regula falsi, e.g. the Illinois method.

BTW, coding polynomials in RPN can be done much simpler and faster with Horner's method. Most important, this avoids the use of the y^x function which is very slow. You better do it this way:

Code:

LBL E
ENTER
ENTER
ENTER
8
-
x
5
+
x
1
4
+
RTN

Now, what about a program that uses the given basic structure but provides faster root finding e.g. with a regula falsi approach?

Dieter