Minmaxline

# The Min-Max Line for the HP-41

Overview:

-Let be a set of n points ( x1 ; y1 ) ..... ( xn ; yn )
The min-max line:  y = m.x + p  minimizes the maximum "error"     h = supi  | yi - m xi - p |    over the entire set of points.

-This program uses the "exchange method":

1°) The Chebyshev line is found for the first 3 points.
2°) The greatest error is computed at all data points for this Chebyshev line.
3°) One of the first 3 points is exchanged with a data point at which the greatest error occurs ( so that errors are of alternating sign for this new triple )

-The process is repeated until the greatest error occurs at one of the first 3 points: this is always achieved and only a few exchanges are usually needed.

Data Registers:        Registers R00 thru R2n are used and all of them are to be initialized before executing MML

R00 = n = the number of point

R01 = x1  ;  R03 = x2  ;  .......... ; R2n-1 = xn    ( it's necessary to have x1 < x2 < x3 )
R02 = y1  ;  R04 = y2  ;  .......... ;  R2n = yn

Flags and subroutines:  none.

Program Listing

-Synthetic registers M N O P  can be replaced by any unused standard registers:
for instance R41 R42 R43 R44  if  n < 21.

-Lines 52-106-120 are three-byte GTOs

 01  LBL "MML"   02  LBL 01   03  RCL 02   04  RCL 04   05  +   06  RCL 06   07  RCL 02   08  -   09  RCL 05   10  RCL 01   11  -   12  /   13  STO M   14  RCL 01   15  RCL 03   16  +   17  *   18  -   19  2   20  /   21  STO N   22  RCL 00   23  ST+ X   24  0   25  LBL 02 26  DSE Y   27  RCL IND Y   28  RCL M   29  *   30  RCL N   31  +   32  ISG T   33  CLX   34  RCL IND T   35  -   36  ABS   37  XY   42  LAST X   43  STO P   44  LBL 03   45  RDN   46  DSE Y   47  GTO 02   48  RCL O   49  PI   50  ST+ X 51  X>Y?   52  GTO 10      53  RCL IND O   54  ISG O   55  CLX   56  RCL P   57  LAST X   58  *   59  X<0?   60  GTO 06   61  CLX   62  RCL 03   63  X>Y?   64  GTO 05   65  RCL 06   66  X<> IND O   67  STO 06   68  DSE O   69  RCL 05   70  LBL 04   71  X<> IND O   72  STO 05   73  GTO 01   74  LBL 05   75  RCL 02 76  X<> IND O   77  STO 02   78  DSE O   79  RCL 01   80  GTO 09   81  LBL 06   82  CLX   83  RCL 05   84  X>Y?   85  GTO 07   86  RCL 06   87  X<> 04   88  X<> IND O   89  STO 06   90  DSE O   91  RCL 05   92  X<> 03   93  GTO 04   94  LBL 07   95  CLX   96  RCL 01   97  X>Y?   98  GTO 08   99  RCL 04 100  X<> IND O 101  STO 04 102  DSE O 103  RCL 03 104  X<> IND O 105  STO 03 106  GTO 01   107  LBL 08 108  RCL 02 109  X<> 04 110  X<> 06 111  X<> IND O 112  STO 02 113  DSE O 114  RCL 01 115  X<> 03 116  X<> 05 117  LBL 09 118  X<> IND O 119  STO 01 120  GTO 01   121  LBL 10 122  RCL N 123  RCL M 124  CLA 125  END

( 186 bytes / SIZE 2n+1 )

 STACK INPUTS OUTPUTS T / 1 or 3 or 5 Z / 2*pi Y / p X / m L / +h or -h

Example:       Find the min-max line for the following data:

 xi 1 3 4 7 10 12 16 19 24 37 41 49 51 61 yi 1 2 3 6 8 9 12 14 20 31 38 41 48 57

1-   SIZE 029                        ( or greater )
2-  14 STO 00                       ( there are 14 points )
3-   1  STO 01       STO 02
3  STO 03   2  STO 04
..............................
61  STO 27   57 STO 28

4- XEQ "MML"  >>>>  m =  0.94             ---Execution time = 36s---
RDN   p =  -2.5

-The min-max line is  y = 0.94 x - 2.5

and the maximum error is  h = 2.56
( L-register contains -2.56 )

-Note that the least squares line is  0.9275 x - 1.4785 in this example.

Reference:

[1]  "Numerical Analysis" - Francis Scheid - McGraw-Hill  ISBN 07-055197-9