Oakland CPM Archive/oakcpm.iso/sigm/vol195/fluf11/t.lbr/FLUF11.DOC

Text File | 1985-02-10 | 12.5 KB | 339 lines

                              FLUF

                           Version 1.1
                        TURBO Pascal (tm)
                          July 11, 1984

                        D.M. Fritz-Rohner
                      Post Office Box 9080
                        Akron, Ohio 44305


     Thi≤á prograφá derive≤ froφ thσ BASI├ languagσ versioεá preì
senteΣá iε thσ articlσ '┴ Simplσ Minima° Algorithmº b∙ Steveεá A« ì
Ruzinsk∙ founΣ iε Dr« Dobb'≤ Journal¼ Numbe≥ 93¼ July¼ 1984«

     FLU╞á 1.▒ i≤ aε updatσ t∩ thσ FLU╞ 1.░ TURB╧ Pasca∞ version« ì
Seσ FLUF10.DO├ iε FLUF10.LBR«  Thi≤ prograφ i≤ intendeΣ t∩ ruε iε ì
CP/═á (tm⌐á compatiblσá environments«á  Versioε 1.░á i≤á ßá closσ ì
translatioεá oµ thσ MBASI├ (tm⌐ compatiblσ prograφ  founΣ iεá thσ ì
abovσ article«

     Thi≤á versioε furthe≥ reorganize≤ anΣ modifie≤ thσ referencσ ì
code.

     Thσ operatinτ environmen⌠ interfacσ i≤ modifieΣ t∩á externaì
lizσá contro∞á paramete≥ specificatioε anΣ t∩ providσ simplσá I/╧ ì
redirectioε o≥ 'steering'«  Prograφ contro∞ inpu⌠ i≤ takeε froφ ß ì
datß filσ anΣ outpu⌠ ma∙ bσ redirecteΣ t∩ thσ CP/═ lst║ devicσ o≥ ì
t∩ ß file« Seσ USAGE.

Thσ contro∞ datß filσ ha≤ thσ followinτ structure;

     cnx                      - maximum number of iterations
     ccS                      - error convergence value
     m                        - number of parameters
     a(1) cca(1)              - initial parameter values and
     a(2) cca(2)                convergence criteria
      :     :
     a(m) cca(m)
     n                        - number of data points
     ys(1) xs(1) ...          - data values
     ys(2) xs(2) ...
       :     :
     ys(n) xs(n) ...

     Notσ tha⌠ thσ usage≤ oµ ═ anΣ ╬ arσ interchageΣ witΦ respec⌠ ì
t∩ thσ referencσ program.

     Thσá codσá i≤á enhanceΣ t∩ imposσá reasonablenes≤á test≤á oε ì
contro∞ data«á  Prograφ contro∞ i≤ achieveΣ througΦ ß combinatioε ì
oµá test≤ oε iteratioε count¼á minima° fit¼á anΣ paramete≥á valuσ ì
convergence«á Thσ prograφ test≤ eacΦ iteratioε t∩ determinσá wheì
the≥á minima°á fi⌠á i≤ equa∞ o≥ bette≥ thaε cc╙ anΣá whethe≥á thσ ì
difference≤á betweeε parameter≤ fo≥ best-ye⌠ fi⌠ anΣ presen⌠á fi⌠ ì
arσ closσ withiε thσ ccß values«  FLU╞ convergencσ i≤ no⌠ monotoìèniπ s∩ tha⌠ thi≤ latte≥ tes⌠ i≤ onl∙ loosel∙ relateΣ t∩ ßá Cauch∙ ì
criterion.
ì
     Minima° fi⌠ i≤ modifieΣ t∩ bσ absolutσ rathe≥ thaε relative« ì
Relativσ minima° fault≤ wheε thσ independen⌠ variablσ i≤ zero« Iµ ì
thσ ccß parameter≤ arσ se⌠ t∩ somethinτ 'largeº theε iteratioε i≤ ì
performeΣ withou⌠ regarΣ t∩ paramete≥ convergence«á  Likewisσ fo≥ ì
thσá minima°á criterion«á  Thσ dependen⌠ variablσ value≤á iεá thσ ì
contro∞ filσ neeΣ no⌠ bσ uniforml∙ spaced.

     Thσáá initializatioεá oµá thσá 'statσá vectorºá list¼áá i.e« ì
x[1..N,1..M]¼ i≤ externalizeΣ iε ß routinσ giveε thσ generiπ namσ ì
SVIni⌠á t∩á facilitatσá convenien⌠á alternatioεá amonτá differen⌠ ì
applications.

     Thσá paramete≥ value≤ arσ useΣ t∩ initializσ thσá sequentia∞ ì
leas⌠á square≤á segmen⌠á oµá thσá processinτá which¼áá iεáá turn¼ ì
initialize≤ thσ 'fluffingº process«  Thσ largσ initia∞ covariancσ ì
matri°á inversσ diagona∞ value≤ makσ thσ sequentia∞ leas⌠ square≤ ì
proces≤ relativel∙ insensitivσ t∩ thσ initia∞ coefficien⌠ values.


USAGE

     Selec⌠á thσá appropriatσ SVIni⌠ versioεá fo≥á inclusioεá anΣ ì
compilσáá thσá prograφá witΦá thσá TURB╧á Com-filσá optioεáá set«  ì
Otherwisσ thσ I/╧ redirectioε i≤ no⌠ meaningful. The command;

     A>fluf data

execute≤ FLU╞ usinτ thσ datß filσ DAT┴ anΣ output≤ thσ result≤ t∩ ì
thσ CP/═ con║ device«

     A>fluf sp lst:

execute≤ FLU╞ witΦ datß froφ S╨ anΣ route≤ thσ outpu⌠ t∩ thσ CP/═ ì
lst║ device.

     A>fluf polyfit results

execute≤ FLU╞ usinτ POLYFI╘ anΣ put≤ thσ outpu⌠ t∩ filσ RESULTS.


EXAMPLES

Example: 'Simple Polynomial'

     Thσá filσá SP/╞á correspond≤ t∩ thσá simples⌠á casσá iεá thσ ì
referencσ articlσ anΣ contain≤ thσ data;

     100
     1.e-4
     3
     1.0 1.0
     -.167 1.0
è     .00833 1.0
     50
     3.141076E-02 2.000000E-02
     6.279052E-02 4.000000E-02
          :           :
          :           :
     9.995066E-01 9.800000E-01
     1.000000E+00 1.000000E+00

     Thσá 10░á mean≤á t∩á iteratσ thσá fluffinτá portioεá oµá thσ ì
algorithφá n∩ morσ thaε 10░ times«á  Thσ cc╙ valuσ require≤á tha⌠ ì
thσáá absolutσá valuσá oµá thσá maximuφá differencσá betweeεá an∙ ì
specifieΣá independen⌠ variablσ valuσ anΣ thσ applieΣá polynomia∞ ì
a⌠ thσ correspondinτ dependen⌠ variablσ valuσ bσ n∩ greate≥á thaε ì
1.e-4.

     Thσ │ specifie≤ tha⌠ thei≥ arσ threσ coefficient≤ oµ thσ odΣ ì
polynomial«á  Therefore¼á thσá polynomia∞á i≤á 5tΦá degree«á  Thσ ì
followinτá threσ pair≤ oµ number≤ arσ thσ coefficient≤ anΣá thei≥ ì
convergencσá criteria«á  Thesσá coefficient≤á arσá thσá truncateΣ ì
value≤á oµ thσ firs⌠ threσ term≤ oµ thσ Talo≥ serie≤ fo≥ thσ sinσ ì
function«  Thσ convergencσ criteriß arσ 'largeº s∩ tha⌠ iteratioε ì
i≤ convergencσ controlleΣ b∙ cc╙ anΣ loo≡ controlleΣ b∙ nc°á witΦ ì
coefficien⌠ convergencσ effectivel∙ ignored.

     Thσá 5░ specifie≤ tha⌠ therσ arσ fift∙ datß point≤á defininτ ì
thσá functioεá t∩ bσ fitted«á  Thσ value≤ listeΣ herσá arσá thosσ ì
computeΣá b∙ TURB╧ usinτ thσ SI╬ functioε fo≥ thσ samσá uniforml∙ ì
spaceΣ abscissaσ a≤ thosσ iε thσ publisheΣ program.

Thσ followinτ command;

     A>fluf sp/f test/f

processe≤ thi≤ datß anΣ put≤ thσ result≤ iε TEST/╞ whicΦ contain≤ ì
thσ following;

   0 1.567756E+00 -1.70207E-01 8.306739E-03 1.000000E+00 4.058555E-01
   1 1.569051E+00 -3.71677E-01 -1.97375E-01 4.961373E-02 4.961373E-02
   2 1.570772E+00 -6.43186E-01 7.241231E-02 1.534320E-04 1.534320E-04
   3 1.570772E+00 -6.43186E-01 7.241231E-02 1.534320E-04 1.566227E-04
   4 1.570678E+00 -6.43058E-01 7.243098E-02 1.244030E-04 1.244030E-04
   5 1.570637E+00 -6.43135E-01 7.256355E-02 1.125686E-04 1.125686E-04
   6 1.570614E+00 -6.42965E-01 7.243932E-02 1.053334E-04 1.053334E-04
   7 1.570587E+00 -6.43024E-01 7.253747E-02 1.006899E-04 1.006899E-04
   8 1.570587E+00 -6.43024E-01 7.253747E-02 1.006899E-04 1.035726E-04
   9 1.570548E+00 -6.42736E-01 7.225356E-02 1.000070E-04 1.000070E-04
  10 1.570524E+00 -6.42757E-01 7.230616E-02 9.094802E-05 9.094802E-05

wherσá thσá firs⌠á columε i≤ iteratioεá number¼á thσá nex⌠á threσ ì
column≤á arσ coefficien⌠ values¼á thσ nex⌠ columε i≤ best-ye⌠ fi⌠ ì
anΣ thσ las⌠ columε i≤ presen⌠ iteratioε minimax«  Iteratioε zer∩ ì
show≤á thing≤ a⌠ thσ enΣ oµ sequentia∞ leas⌠ square≤á anΣá beforσ ì
fluffing«á  Therefore¼á thσ threσ coefficient≤ fo≥ iteratioε zer∩ ì
arσ thosσ fo≥ thσ leas⌠ square≤ fit«  Thσ best-ye⌠ i≤ arbitraril∙ ìèinitializeΣ t∩ somethinτ 'large'¼ here¼ one«  Thσ minima° fi⌠ fo≥ ì
thσ leas⌠ square≤ coefficient≤ i≤ abou⌠ 0.40¼á whicΦ i≤ no⌠ grea⌠ ì
fo≥ ß functioε tha⌠ range≤ betweeε zer∩ anΣ one.

     Successivσá iteration≤á reducσ minima° t∩ abou⌠ 9.e-╡á whicΦ ì
achieve≤ convergencσ t∩ bette≥ thaε 1.e-┤ withiε 10░á iterations« ì
Thσ coefficient≤ expres≤ thσ relation;

                                                3              5
     SIN(1.570796327*x) ~ 1.570524 x - .642757 x  + .07230616 x


Example: Michaelis-Menten

     Thσ articlσ 'Fittinτ Curve≤ t∩ Dataº b∙ Marc∩ S«á CacecΘ anΣ ì
Williaφ P«á Cacheri≤ iε BYT┼ Magazine¼á Volumσ 9¼á Numbe≥ 5¼ May¼ ì
198┤á illustrate≤ applicatioε oµ thσ SIMPLE╪ algoritφ usinτ leas⌠ ì
square≤á fi⌠á criterion«á  Thσá functioε fitteΣá i≤á ßá so-calleΣ ì
Michaelis-Menteε function;

     ^      a' x
     y  =  ------
           x + b'

                          ~     ~
usinτá si°á measurement≤ oµ ° anΣá y«á  Transforφá thi≤á relatioε ì
using;
           ~   ~
     z = - y / x

to form;

     y = a' + b' z

compatible with FLUF.  The data file MM/F contains;

     200
     5.3e-3
     2
     0.2 1.0
     3.0 1.0
     6
     0.172 1.68
     0.250 3.33
     0.286 5.00
     0.303 6.67
     0.334 10.0
     0.384 20.0

anΣá thσ codσ iε MM/F.PA╙ fo≥ SVIni⌠ tha⌠ initialize≤ thσá 'statσ ì
vectorº lis⌠ x[1..N,1..M▌ contains;

     x[i,1] := 1.0 ;
     x[i,2] := -ys[i]/xs[i] ;

èThen compiling FLUF and executing the command;

     A>fluf mm/f test/f

produce≤á ß filσ tha⌠ contain≤ two hundreΣ and one lines¼á thσ firs⌠á anΣ ì
last of which are;

   0 4.303436E-01 2.523454E+00 1.000000E+00 1.270990E-02
          :
          :
 200 4.209807E-01 2.398137E+00 9.063552E-03 9.087233E-03


PERFORMANCE

The command;

     A>fluf sp/f test/f

execute≤ iε abou⌠ 2│ second≤ oε ß ┤ MHz« Z-8░ baseΣ system« Abou⌠ ì
1▓á second≤á i≤ requireΣ fo≥ loaΣ anΣ leas⌠á square≤á completion« ì
Therefore¼ abou⌠ onσ seconΣ pe≥ flufµ i≤ required.

     An∙á comparison≤ t∩ result≤ reporteΣ b∙ Hasting≤ anΣá other≤ ì
depend≤ oε qualificatioε oµ TURBO'≤ SI╬ functioεá representation¼ ì
floatinτ poin⌠ arithmetic¼ etc«  Wσ d∩ no⌠ infe≥ that;

          Pi
     sin( -- x) ~ SIN(1.570796327*x)
           2

     For comparison, consider the command;

     A>simp sp test/s

wherσ thσ filσ S╨ contain≤ datß comparablσ t∩ SP/F« Therσ arσ onσ ì
hundreΣ anΣ onσ line≤ iε TEST/S¼ thσ firs⌠ anΣ las⌠ oµ whicΦ are;

   0 1.000000E+00 -1.67000E-01 8.330000E-03 2.477106E-01 6.929252E-01
          :
          :
 100 1.548642E+00 -6.22970E-01 8.073769E-02 8.232326E-03 8.428058E-03

wherσá columε usagσ correspond≤ t∩ FLUF«á  Thσ algorithφ diΣá no⌠ ì
convergσ anΣ drovσ thσ extremuφ t∩ abou⌠ 8.e-3¼á abou⌠ tw∩ order≤ ì
oµá magnitudσ greate≥ thaε specified«á  Thσ commanΣ requireΣá 12▒ ì
second≤á o≥á abou⌠ 1.▓ second≤ pe≥ simp«á  Thσá slo≈á convergencσ ì
arise≤á mostl∙ froφ thσ cus≡ geometr∙ oµ thσ extremuφ spacσ whicΦ ì
force≤á prematurσá contractioε oµ thσá simple°á figure«á  Furthe≥ ì
convergencσá caεá bσ provokeΣ b∙ restartinτá thσá iteratioεá witΦ ì
fina∞ coefficien⌠ estimate≤ anΣ initia∞ ste≡ sizes.

The command;

     A>fluf mm/f test/f
è
requires about 49 seconds while the command;

     A>simp mm test/s

require≤á abou⌠á 4╖á seconds«á  Thσ filσá SIMP11/T.DO├á founΣá iε ì
SIMP11/T.LB╥á discusse≤ thσ result≤ oµ applyinτ thσ minima°á verì
sioε oµ SIM╨ t∩ thi≤ problem with results;

   0 3.000000E-01 3.000000E+00 1.231304E-01 1.835169E-01
         :
         :
 200 5.991796E-01 7.085686E+00 5.843624E-02 5.844566E-02

     Neithe≥á SIM╨á no≥á FLU╞á convergeΣá t∩á thσá requireΣá fit«  ì
However¼á inspectioε oµ thσ completσ result≤ show≤ FLU╞ unablσ t∩ ì
improvσ thσ fi⌠ afte≥ abou⌠ iteratioε 17╣ whilσ SIM╨ continueΣ t∩ ì
convergσá slowly«á  Notσá tha⌠ FLU╞ qui⌠ witΦ aε erro≥ abou⌠á onσ ì
fiftΦáá oµá SIMP's«áá  Thσá convergencσá criterioεá i≤áá probabl∙ ì
infeasible.


DISCUSSION

     Thσá referencσ articlσ present≤ ß PolyFORTH (tm⌐ »á FM╠á (c⌐ ì
versioεá oµ thσ algorithφ whicΦ incorporate≤ tw∩ modification≤ to ì
thσáá fundamenta∞áá algorithφáá intendeΣáá t∩áá improvσáá runtimσ ì
performance.
  ì
     Thσá firs⌠á compute≤á ßá modifieΣá 'gainºá matri°á baseΣá oε ì
empirica∞ evidencσ oµ faste≥ convergence« Thσ seconΣ modificatioε ì
contract≤á thσá fitteΣ datß se⌠ b∙ retaininτá thosσá point≤á witΦ ì
larges⌠ minima° values«  Thi≤ tend≤ t∩ reducσ thσ fitteΣ datß se⌠ ì
t∩ thosσ point≤ clustereΣ abou⌠ thσ erro≥ functioε extrema.

     Neithe≥á oµá thesσ modification≤á i≤á incorporated«á  First¼ ì
empiricall∙á fudginτ thσ gaiε matri° detract≤ froφ thσá ingenuit∙ ì
oµá FLU╞á b∙ failinτ t∩ identif∙ anΣ directl∙ appl∙á thσá probleφ ì
element≤áá analogou≤áá t∩áá measuremen⌠áá variancσáá anΣáá simpl∙ ì
demonstrate≤á thσ robustnes≤ oµ thσ underlyinτ linea≥á estimatioε ì
formulation«áá  Fo≥á example¼áá iεá Kalmaεá contexts¼áá wheεá thσ ì
measuremen⌠á variancσ goe≤ t∩ zero¼á thσ gaiε goe≤ t∩ onσ anΣ thσ ì
estimato≥ converge≤ now.

     Second¼á thσá datßá se⌠ contractioεá proces≤á i≤á indirectl∙ ì
estimatinτá thσ coordinate≤ oµ thσ erro≥ functioεá extrema«á  Fo≥ ì
an∙á reasonablσ functioε thi≤ correspond≤ t∩ computinτ thσá zeros ì
oµá thσ erro≥ functioε derivative«á  Somσ adaptivσ formulatioε iε ì
whicΦá thσá extremß location≤ arσ cas⌠ int∩ thσá samσá estimatioε ì
frameworδ a≤ thσ coefficient≤ woulΣ seeφ ß desireablσ objective.

     Conside≥á estimatioε oµ thσ parameter≤ fo≥ ß straigh⌠á line«  ì
Iε ß mathematica∞ sense¼á an∙ tw∩ point≤ suffice« However¼ floatì
inτá poin⌠ representatioε map≤ thσ rea∞ number≤ t∩ preservσ relaì
tivσ error«á  Thi≤ mean≤ tha⌠ absolutσ erro≥ i≤ large≥ fo≥ large≥ ìènumber≤á s∩á tha⌠á FLUF'≤ datß se⌠ contractioεá wil∞á selec⌠á thσ ì
large≥ numbers.


CP/M (tm) Digital Research

MBASIC (tm) MicroSoft

TURBO Pascal (tm) Borland International

PolyFORTH (tm) Forth Technology

FML (c) Steven A. Ruzinsky