hp41programs

Overview

 1°)  Min-Max Parabola
 2°)  Min-Max Polynomial
 
 

1°) Min-Max Parabola
 

-Given a set of n data points ( x₁ , y₁ ) ..... ( x_n , y_n )     ( n > 3 )
  the min-max parabola:  y = a.x² + b.x + c  minimizes the maximum "error"     h = sup_i  | y_i - a x_i² -  b x_i - c |    over the entire set of points.

-The following program uses the "exchange method":

  1°) The min-max parabola is found for the first 4 points.
  2°) The greatest error is computed at all data points for this parabola.
  3°) One of the first 4 points is exchanged with a data point at which the greatest error occurs ( so that the errors are still of alternating sign for this new quadruple )

-The process is repeated until the greatest error occurs at one of the first 4 points ( step 3 is skipped if it happens the first time )
 
 

Data Registers:           •  R00 = n = number of points                         ( Registers R00 thru R2n are to be initialized before executing "MMP2" )

                                      •  R01 = x₁   •  R03 = x₂    ..........  •  R2n-1 = x_n                    ( it's necessary to have x₁ < x₂ < x₃ < x₄ )
                                      •  R02 = y₁   •  R04 = y₂    ..........  •  R2n = y_n

Flag:  F10 is cleared at the end
Subroutines: /

-Lines 122-160-175-186-196-206-214  are three-byte GTOs
 
 

 
   ( 321 bytes / SIZE 2n+1 )
 
 

 
Example:     With the following set of n = 11 points    ( 11  STO 00 )
 
 

-Store these 22 numbers into

               R01      R03     ..............................................................................................      R21
               R02      R04     ..............................................................................................      R22      respectively

           XEQ "MMP2"  yields          a = -0.25          ( in 30 seconds )
                                    RDN          b =  5
                                    RDN          c = 0.975
                                    RDN    +/- h = -0.275

   >>>  whence the equation of the min-max parabola is  y = -0.25 x² + 5 x + 0.975  and the maximum "error" is  0.275

Notes:

-When the program stops, the order of the points will have probably changed.
-The abscissas can be unequally spaced.
-Due to roundoff errors, it's perhaps not impossible that the algorithm oscillates for ever between 2 very close | h |-values
-Add  VIEW Z  after line 120 to check
-If it ever happens, set flag F21 ( the program will stop each time VIEW Z is executed ) and press XEQ 09 to get the results.
 

2°) Min-Max Polynomial of degree d
 

-The same "exchange method" may also be used to find the min-max polynomial of degree d
-The data must contain at least (d+2) points
 

WARNING:
 

-The set of n data points ( x₁ , y₁ ) ..... ( x_n , y_n ) must be stored so that   x₁ < x₂ < x₃ < ............... < x_d+2
 

Data Registers:           •  R00 = n = number of points < 45                        ( Registers R00 thru R2n are to be initialized before executing "MMP" )

                                      •  R01 = x₁   •  R03 = x₂    ..........  •  R2n-1 = x_n     with     x₁ < x₂ < x₃ < ............... < x_d+2
                                      •  R02 = y₁   •  R04 = y₂    ..........  •  R2n = y_n

                                         R89 to R99: temp                           R100 to R105+d^2+5.d = the coefficients of the successive linear systems

Flag:  CF01  <-> pivoting
           SF 01 <-> no pivoting

Subroutine:  "LS"  ( cf "Linear and non-linear systems for the HP-41" )

-Lines 121-169-214-235-245-273 are three-byte GTOs
 
 
 

 
    ( 486 bytes / SIZE 106+d^2+5.d )
 
 

   Where       d       =  degree of the polynomial
               bbb.eee  =  control number of the min-max polynomial  ( in fact bbb = 2 n + 1 )
     and        | h |     =  sup_i  | y_i -  p( x_i ) |

Example:    With the following set of 7 data points, find the min-max polynomial of degree d = 3
 
 

     1  STO 01   2  STO 03   4  STO 05   7  STO 07  9  STO 09  10  STO 11  12  STO 13
     2  STO 02   5  STO 04   3  STO 06   7  STO 08  6  STO 10  12  STO 12  17  STO 14

     SIZE 130  ( or greater )

     3  XEQ "MMP"   >>>>    The HP-41 displays the successive h-values
                                              ( namely 1.32  -1.506666667  -1.705   1.75 )  and eventually

                                              bbb.eee = 15.018                                                                    ---Execution time = 4mn43s---
                               X<>Y         | h |    = 1.75

-The coefficients of the min-max polynomial of degree 3 are in R15-R16-R17-R18 and we get:

    p(x) = 0.033333333 x³ - 0.45 x² + 2.016666666 x + 1.75 = x³ / 30 - 0.45 x² + ( 121 / 60 ) x + 1.75

  and  | h | = 1.75
 

Notes:

-Since R89 is used for temporary data storage, the number of points must be < 45

-When the program stops, the order of the points will have probably changed.

-The abscissas can be unequally spaced.

-Due to roundoff errors and to avoid a possible infinite loop, I've added lines 164-165
-So, the iterations will stop if 2 consecutive h-values differ by less than 0.00001
-Change these lines ( or delete them ) if you prefer another value...

-If you set flag F01 ( SF 01 ), the linear systems will be solved without pivoting.
-With the example above, you will get ( almost ) the same results in 4m15s, thus saving 28 seconds.
-However, there is a risk of more roundoff-errors.

-If d = 2,  "MMP2" is much faster and for d = 1, cf "Min-Max Line for the HP-41" ( though "MMP" will work too... )
 

Reference:

[1]  F. Scheid -  "Numerical Analysis" - Mc Graw Hill   ISBN 07-055197-9