TweetFollow Us on Twitter

Curve Fitting 2
Volume Number:1
Issue Number:12
Column Tag:Forth Forum

Curve Fitting, Part II

By Jörg Langowski, Chemical Engineer, Grenoble, France, MacTutor Editorial Board

After last month's refresher on accessing floating point routines from Forth, this column is now going to show you the main part of the curve fitter program.

Let's state our objective again: We have a series of data points (measurements) yi at certain time points ti. The measured data is supposed to follow some quantitative law, so that we can state a theoretical relationship between time t and data y:

The ai are parameters that determine the exact form of the function f.

Lets assume we have estimated initial values for the parameters ai° somehow so that they are not too far away from the true values. Then we need a method that creates some correction terms ai, which when added to the initial values give new, better estimates of the parameters ai':

As you could read in last month's column, the ai are eventually obtained from the solution of a system of linear equations, and we had defined the word gauss to implement the Gauss algorithm that solves such a system.

This month I am going to show you how one sets up the equations (example given for three parameters),

starting from the data and the initial estimate of the function that one wants to fit to it. The full details of the method are given in an appendix to this column.

At this point it is only important to know that the coefficients cij, as defined in last month's column, look like the following:

where N is the total number of data points and fk/ai is the first derivative of the theoretical function at the time tk with respect to the parameter ai.

The terms on the right hand side of the equations, bi, are:

Ri are the residuals (as defined last month),

the differences between the theoretical and measured values at the time points ti.

Therefore, the curve fitting algorithm will consist of the following major parts:

- one routine that calculates the theoretical function value f(ti), given a set of parameters (this will be the 'model' that you use to fit your data),

- one routine that calculates the derivative of this function with respect to one of the parameters ai,

- calculation of all the derivatives fk/ai with k ranging from 0 to (# of data points - 1) and i from 0 to (# of parameters - 1) and saving those derivatives in a matrix,

- computation of the coefficients cij and bi (and setting them up in a matrix),

- solution of the linear equation system thus obtained, giving correction values for the parameters ai,

- changing the parameters by the correction terms and repetition of the whole algorithm if the change is still larger than some predefined (small) number.

The algorithm is implemented in this month's program example (listing 1). The first part contains some additions to the floating point and Gauss algorithm routines that you've already seen last month. One bug had to be corrected in gauss, which left a number on the stack that was supposed to be dropped (added drop in italics in the listing). The floating point output routine has been slightly modified so that real numbers are always printed with one digit in front of the decimal.

In order to be able to check whether the iteration has been completed or not, we will have to compare real numbers, so first we define the

Floating point comparison operator

The SANE package provides a routine for the comparison of two floating point numbers. Four cases are distinguished and the processor status register flags set accordingly:

X N Z V C

x < y 1 1 0 0 1

x = y 0 0 1 0 0

x > y 0 0 0 0 0

unordered0 0 0 1 0

where the address of x is on top of the address of y on the stack.

The operation code for floating point comparison in SANE is 8, so we define

hex : f> 8 fp68k @sr 10 and ;

for comparing two real numbers on the stack. Bit 5 of the result (the X flag) is and-ed out, the reason being that this is the only one that is left unchanged after the SANE trap has been called and the Forth interpreter has taken over again. All the other flags cannot be used, so we won't be able to compare two real numbers for being equal. With 80-bit precision, however, such a test does not make much sense, you will almost never check for equality but rather if a number is less than one other or whether their difference is smaller than some predefined value.

The comparison for 'unorderedness', which sets the V flag, is also trashed by the Forth interpreter. This would only be important if we wanted to test for a NaN (Not a Number), which for instance results from a 0/0 division.

This leaves us with the X flag as the only one usable after the fp68k call. It is set when the real number whose address is on top of the stack is less than the number whose address is below it.

Random number generator - floating point version

For initializing the 'data points' as an input to the curve fitting program, we are going to use simulated data from the same function that we are fitting. We add some 'random noise' to it and need a random number generator for that. SANE contains a floating point random number generator, which computes from an 80-bit floating point input a new random 80-bit floating point number in the range 0 < x < 231-1. We want a number between 0 and 1 (for convenience) so the word ranf scales this number after calling the random number routine. ranf leaves the address of the result on the stack. For initializing the random number generator with an arbitrary seed, ranset is defined.

You will notice one important concept in the definition of ranf and ranset: both words operate on variables (rr, rs and sf) that are axed after the definition is completed. The variables are erased from the vocabulary that way and stay local to the random number routines. This is the way the 'nameless' tokens are created that you read about some issues ago.

The function to be fitted is defined as the word func. 50 bytes are reserved for the array par, so that at maximum 5 parameters (extended precision) can be used in the function. The data points are stored in the single precision arrays xdat and ydat. init_pars initializes the parameters to some arbitrary values, in this case par[1] = 1.0, par[2] = 2.0, and par[3] = -0.1. Calling func with these values, init then creates a set of simulated data (including random noise).

deriv calculates the first derivatives of the function with respect to the parameters from differences,

This definition, too, uses the local variables da1, da2, da3 and da4, which are axed afterwards.

make_derivmat computes all necessary derivative values and sets them up in a single precision matrix. This matrix is then used by the word make_resmat to compute the sums that make up the coefficient matrix. For the right-hand-side coefficients one also needs the residuals, which are calculated and stored into a matrix by residuals.

One iteration of the curve fitting process is done by the word one_iter, which sets up the derivative matrix and computes the residuals by calling the appropriate words, prints the sum of error squares (so you can check the quality of the fit) then sets up the coefficient matrix and calls gauss to solve the linear equation system. The solution is stored in the array delta; these are the correction terms that have to be added to the parameters to get improved estimates. new_pars does this correction and prints out the values of the new parameters, leaving false (zero) on the stack if any parameter has changed by more than one part in 10-5.

The actual curve fitter, nlsqfit, then loops through the iteration until the best fit is obtained.

You can check the fitting process by calling init first and then, for instance, setting par[1] = 2.0, par[2] = 1.0, par[3] = -0.05:

two par x2x  one par 10+ x2x
two par 20 + f/

and start nlsqfit. This will bring you back close to the simulated values, par[1] = 1.0, par[2] = 2.0, and par[3] = -0.1 in about 4 to 5 iterations. The fitted values will not be exactly equal to the simulated ones because of the random noise added to the data.

So far, this is only a skeleton of a curve fitting program because we cannot input floating point numbers manually or from the clipboard (e.g. it would be nice to transfer data from a spreadsheet); also a graphical output will be needed to display the data points and the fitted curve. Next column will deal with those problems.

Listing 1: Non-linear least squares curve fitting routine
( © 1985 J.Langowski by MacTutor )
( Note that this is not stand-alone but needs some definitions from last 
month's example. Only the changed parts are printed here )

hex
: f> 8 fp68k @sr 10 and ;  : fabs f fp68k ;
: lnx 0 elems68k ; : log2x 2 elems68k ;
: ln1x 4 elems68k ; : log21x 6 elems68k ;
: expx 8 elems68k ; : exp2x a elems68k ;
: exp1x c elems68k ; : exp21x e elems68k ;
: x^i 8010 elems68k ; : x^y 8012 elems68k ;
: compoundx c014 elems68k ; 
: annuityx c016 elems68k ;
: sinx 18 elems68k ; : cosx 1a elems68k ;
: tanx 1c elems68k ; : atanx 1e elems68k ;
: randomx 20 elems68k ;   decimal

: dec. ( float\format# -- )
       zzformat ! zzformat swap zzs1 b2d
       zzs1 dup w@ 255 > if ." -" else ."  " then
       dup 4+ count over 1 type ." ."
       swap 1+ swap 1- type ( mantissa )
       2+ w@ ( get exponent )
            1 w* zzformat @ + 1- 
            ." E" . ;

( define constants )
float one  float -one  float zero  float two  float four
1 sp@ one in2x drop  -1 sp@ -one in2x drop 
0 sp@ zero in2x drop
2 sp@ two in2x drop  4 sp@ four in2x drop
( define some floating accumulators)
float fa1   float fa2   float fa3   float fa4

( Gauss algorithm for linear equations)          
float dg    float fk    float ee
variable nv   variable coeff variable solution
( addresses for storing actual parameters)
: gauss ( z\x\n | --)  nv !  8- coeff !  solution !
  nv @ 1- 0 do  ( i-loop)
     i dup coeff @ calc.offset dg s2x ( diag elem)
     nv @ i 1+ do  ( j-loop)
        i j coeff @ calc.offset fk s2x   dg fk f/
        nv @ 1+ j do  ( k-loop)
            k i coeff @ calc.offset fa1 s2x
                      fk fa1 f*  fa1 fneg  ( -fk*x[i,k])
            j i coeff @ calc.offset dup fa1 s+
                      fa1 swap x2s
                  loop
              loop
           loop
nv @ dup 0 do i over coeff @ calc.offset  fa1 s2x
                       fa1 solution @ i 4* + x2s loop drop
1 nv @ 1- do
     i dup coeff @ calc.offset dg s2x
     solution @ i 4* + ee s2x  dg ee f/
     0 i 1- do i j coeff @ calc.offset fa1 s2x
                         ee fa1 f* fa1 fneg
               solution @ i 4* + dup fa1 s+ fa1 swap x2s
            -1 +loop
       -1 +loop
nv @ 0 do  solution @ i 4* +  fa1 s2x
           i dup coeff @ calc.offset  fa1 s/
           fa1 solution @ i 4* + x2s
       loop ;

( declarations for curve fitter )
create ydat 400 allot   create xdat 400 allot
create residues 400 allot
100 10 matrix derivmat    10 11 matrix resmat
     3 constant npars        10 constant npts
create par 50 allot   create delta 20 allot
float eps  float errsum
1 sp@ eps in2x drop  10000 sp@ eps in/ drop
float onehundred  100 sp@ onehundred in2x drop
float ten  10 sp@ ten in2x drop
( define function )                              
: func ( x -- f[x] = par[1] + par[2] * exp[par[3]*x] )
  par 20 + over f* dup expx  
  par 10 + over f*  par over f+ ;
: test 10 0 do i sp@ fa1 in2x . 2 spaces
                          fa1 func 10 dec. cr loop ;
: >fa1  fa1 s2x ;
: init_pars
  one par x2x  two par 10+ x2x
 -one par 20 + x2x  ten par 20 + f/ ;
init_pars

( derivative, matrix of derivs )                 
float da1 float da2 float da3 float da4  ( local vars )
: deriv ( par \ x -- d-func/d-par at x )
  dup da1 x2x da2 x2x  dup da4 x2x  eps da4 f*
  da4 over f+          da2 func  da3 x2x
  da4 over 2dup f- f-  da1 func  da3 f-
  da4 da3 f/   two da3 f/  da4 swap f+  da3  ;
axe da1 axe da2 axe da3 axe da4

: make_derivmat
  npts 0 do  npars 0 do
       xdat j 4* +  >fa1
       par i 10 * +   fa1 deriv  j i derivmat x2s
     loop  loop ;

( calculate residuals )
: residuals
  zero errsum x2x
  npts 0 do
     xdat i 4* + >fa1   fa1 func   ydat i 4* +  swap  s-
     fa1 residues i 4* + x2s  fa1 dup f*  fa1 errsum f+
     loop  ;
: .resid 
   npts 0 do  residues i 4* + >fa1  fa1 7 dec. cr loop ;

( make matrix of residuals )
 make_resmat
  npars 0 do   npars 0 do    zero fa1 x2x
    npts 0 do
      i k derivmat fa2 s2x    i j derivmat fa2 s*
      fa2 fa1 f+  loop
    fa1  i j resmat x2s    fa1  j i resmat x2s
  loop  loop
  npars 0 do  zero fa1 x2x
     npts 0 do
            i j derivmat fa2 s2x  residues i 4* + fa2 s*
            fa2 fa1 f-  loop
          fa1  i npars  resmat x2s loop ;

( calculate correction terms)
: one_iter
  make_derivmat    residuals  
  ." sum of error squares: " errsum 7 dec. cr
  make_resmat      delta 0 0 resmat npars gauss ;

: new_pars 16 ( true if no significant changes )
  npars 0 do par i 10 * +
    delta i 4* +  over  s+
    ." par[" i . ." ] = " dup  7 dec. cr
    delta i 4* + fa1 s2x  fa1 f/
    fa1 fabs  eps fa1 f> and loop ;

( ranf, initialize data matrices ) 
float rr float rs float sf ( local to ranf )
1 31 scale 1 - sp@ sf in2x drop
: ranset rr x2x ;
: ranf rr randomx  rr rs x2x  sf rs f/  rs ;
axe rr axe rs axe sf
12345678 sp@ fa1 in2x drop fa1 ranset
80 ' npts !    
: init npts 0 do i sp@ fa1 in2x 4*
          xdat over + fa1 swap x2s
          ydat over + fa1 func  ranf fa2 x2x
          ten fa2 f/  fa2 over f+  swap x2s
          i .  xdat over + >fa1 fa1 7 dec. 2 spaces
               ydat  +   >fa1   fa1 7 dec. cr    loop ;

( print matrices for debugging )
: .dmat
  npts 0 do
    npars 0 do  j i derivmat >fa1 fa1 5 dec. loop
    cr loop ;
: .rmat
  npars 0 do
    npars 1+ 0 do  j i resmat >fa1 fa1 5 dec. loop
    cr loop ;

( nonlinear fit, core routine) 
: nlsqfit cr   begin  one_iter cr  new_pars cr  until ;

Appendix: Theoretical background of the curve fitting routine

We want to determine the values of the ai in such a way that the differences between the theoretical function and the measured yk values at times tk become a minimum. These differences are called the residuals rk:

rk = f (tk, a1, a2, a3, .... , an) - yk

and one usually tries to minimize the sum of the squared residuals of all data points.

Lets assume ri are the 'true' residuals that one obtains with the exact ai values. If we estimate the parameters by some initial values ai°, then 'computed' residuals

Rk = f (tk, a1°, a2°, a3°, .... , an°) - yk

can be calculated, which are usually larger than the true ones. To get a correction term that brings the ai° closer to the 'true' ai, one now linearly expands the function f around the estimated value:

f(tk,a1,a2,....,an)

f(tk,a1°,a2°,....,an°) + fk/a1(a1-a1°)

+ fk/a2 (a2-a2°)

. . . . .

+ fk/an(an-an°)

The differences, (ai-ai°), are denoted by ai, now we can write

f(tk,a1,a2,....,an) - yk   
 f(tk,a1°,a2°,....,an°) - yk 
 +  fk/a1 a1 +  fk/a2 a2
 . . . . .
 +  fk/an an

which gives us a relationship between the true and the computed residuals

rk   Rk +  fk/a1 a1 +  fk/a2 a2
 . . . . .
 +  fk/an an .

It is the sum of the squares of the true residuals (N being the number of data points)

that has to be minimized with respect to changes in ai, this means all the derivatives Q/(ai) have to be zero simultaneously. When you evaluate the expressions for the Q/(ai) and set them to zero, you arrive at the equation system that was desribed in the main article.

 

Community Search:
MacTech Search:

Software Updates via MacUpdate

Dash 4.1.3 - Instant search and offline...
Dash is an API documentation browser and code snippet manager. Dash helps you store snippets of code, as well as instantly search and browse documentation for almost any API you might use (for a full... Read more
MacFamilyTree 8.2.7 - Create and explore...
MacFamilyTree gives genealogy a facelift: modern, interactive, convenient and fast. Explore your family tree and your family history in a way generations of chroniclers before you would have loved.... Read more
WhatsApp 0.2.8000 - Desktop client for W...
WhatsApp is the desktop client for WhatsApp Messenger, a cross-platform mobile messaging app which allows you to exchange messages without having to pay for SMS. WhatsApp Messenger is available for... Read more
TotalFinder 1.10.7 - Adds tabs, hotkeys,...
TotalFinder is a universally acclaimed navigational companion for your Mac. Enhance your Mac's Finder with features so smart and convenient, you won't believe you ever lived without them. Features... Read more
Box Sync 4.0.7886 - Online synchronizati...
Box Sync gives you a hard-drive in the Cloud for online storage. Note: You must first sign up to use Box. What if the files you need are on your laptop -- but you're on the road with your iPhone? No... Read more
Espresso 5.1 - Powerful HTML, XML, CSS,...
Note from the developer: For the new Espresso, we changed our versioning and licensing approach with more consistent pricing and a simpler development timeline: "X+1". Each new update would increase... Read more
VueScan 9.6.04 - Scanner software with a...
VueScan is a scanning program that works with most high-quality flatbed and film scanners to produce scans that have excellent color fidelity and color balance. VueScan is easy to use, and has... Read more
Slack 3.0.5 - Collaborative communicatio...
Slack is a collaborative communication app that simplifies real-time messaging, archiving, and search for modern working teams. Version 3.0.5: Bug Fixes: An important security update. Security... Read more
VirtualBox 5.2.6 - x86 virtualization so...
VirtualBox is a family of powerful x86 virtualization products for enterprise as well as home use. Not only is VirtualBox an extremely feature rich, high performance product for enterprise customers... Read more
Vivaldi 1.13.1008.40 - An advanced brows...
Vivaldi is a browser for our friends. In 1994, two programmers started working on a web browser. Our idea was to make a really fast browser, capable of running on limited hardware, keeping in mind... Read more

Latest Forum Discussions

See All

The 7 best games that came out for iPhon...
Well, it's that time of the week. You know what I mean. You know exactly what I mean. It's the time of the week when we take a look at the best games that have landed on the App Store over the past seven days. And there are some real doozies here... | Read more »
Popular MMO Strategy game Lords Mobile i...
Delve into the crowded halls of the Play Store and you’ll find mobile fantasy strategy MMOs-a-plenty. One that’s kicking off the new year in style however is IGG’s Lords Mobile, which has beaten out the fierce competition to receive Google Play’s... | Read more »
Blocky Racing is a funky and fresh new k...
Blocky Racing has zoomed onto the App Store and Google Play this week, bringing with it plenty of classic kart racing shenanigans that will take you straight back to your childhood. If you’ve found yourself hooked on games like Mario Kart or Crash... | Read more »
Cytus II (Games)
Cytus II 1.0.1 Device: iOS Universal Category: Games Price: $1.99, Version: 1.0.1 (iTunes) Description: "Cytus II" is a music rhythm game created by Rayark Games. It's our fourth rhythm game title, following the footsteps of three... | Read more »
JYDGE (Games)
JYDGE 1.0.0 Device: iOS Universal Category: Games Price: $4.99, Version: 1.0.0 (iTunes) Description: Build your JYDGE. Enter Edenbyrg. Get out alive. JYDGE is a lawful but awful roguehate top-down shooter where you get to build your... | Read more »
Tako Bubble guide - Tips and Tricks to S...
Tako Bubble is a pretty simple and fun puzzler, but the game can get downright devious with its puzzle design. If you insist on not paying for the game and want to manage your lives appropriately, check out these tips so you can avoid getting... | Read more »
Everything about Hero Academy 2 - The co...
It's fair to say we've spent a good deal of time on Hero Academy 2. So much so, that we think we're probably in a really good place to give you some advice about how to get the most out of the game. And in this guide, that's exactly what you're... | Read more »
Everything about Hero Academy 2: Part 3...
In the third part of our Hero Academy 2 guide we're going to take a look at the different modes you can play in the game. We'll explain what you need to do in each of them, and tell you why it's important that you do. [Read more] | Read more »
Everything about Hero Academy 2: Part 2...
In this second part of our guide to Hero Academy 2, we're going to have a look at the different card types that you're going to be using in the game. We'll split them up into different sections too, to make sure you're getting the most information... | Read more »
Everything about Hero Academy 2: Part 1...
So you've started playing Hero Academy 2, and you're feeling a little bit lost. Don't worry, we've got your back. So we've come up with a series of guides that are going to help you get to grips with everything that's going on in the game. [Read... | Read more »

Price Scanner via MacPrices.net

9.7-inch 2017 WiFi iPads on sale starting at...
B&H Photo has 9.7″ 2017 WiFi #Apple #iPads on sale for $30 off MSRP for a limited time. Shipping is free, and pay sales tax in NY & NJ only: – 32GB iPad WiFi: $299, $30 off – 128GB iPad WiFi... Read more
Wednesday deal: 13″ MacBook Pros for $100-$15...
B&H Photo has 13″ #Apple #MacBook Pros on sale for up to $100-$150 off MSRP. Shipping is free, and B&H charges sales tax for NY & NJ residents only: – 13-inch 2.3GHz/128GB Space Gray... Read more
Apple now offering Certified Refurbished 2017...
Apple has Certified Refurbished 9.7″ WiFi iPads available for $50-$80 off the cost of new models. An Apple one-year warranty is included with each iPad, and shipping is free: – 9″ 32GB WiFi iPad: $... Read more
10″ iPad Pros on sale for $50-$75 off MSRP, n...
B&H Photo has 10″ and #Apple #iPad Pros on sale for up to $75 off MSRP. Shipping is free, and B&H charges sales tax in NY & NJ only. Note that some sale prices are restricted to certain... Read more
Apple refurbished Mac minis available startin...
Apple has restocked Certified Refurbished Mac minis starting at $419. Apple’s one-year warranty is included with each mini, and shipping is free: – 1.4GHz Mac mini: $419 $80 off MSRP – 2.6GHz Mac... Read more
Amazon offers Silver 13″ Apple MacBook Pros f...
Amazon has new Silver 2017 13″ #Apple #MacBook Pros on sale today for up to $150 off MSRP, each including free shipping: – 13″ 2.3GHz/128GB Silver MacBook Pro (MPXR2LL/A): $1199.99 $100 off MSRP – 13... Read more
Sale: 12″ 1.3GHz MacBooks on sale for $1499,...
B&H Photo has Space Gray and Rose Gold 12″ 1.3GHz #Apple MacBooks on sale for $100 off MSRP. Shipping is free, and B&H charges sales tax for NY & NJ residents only: – 12″ 1.3GHz Space... Read more
Apple offers Certified Refurbished 2017 iMacs...
Apple has a full line of Certified Refurbished iMacs available for up to $350 off original MSRP. Apple’s one-year warranty is standard, and shipping is free. The following models are available: – 27... Read more
13″ MacBook Airs on sale for $120-$100 off MS...
B&H Photo has 2017 13″ 128GB MacBook Airs on sale for $120 off MSRP. Shipping is free, and B&H charges sales tax for NY & NJ residents only: – 13″ 1.8GHz/128GB MacBook Air (MQD32LL/A): $... Read more
15″ Touch Bar MacBook Pros on sale for up to...
Adorama has Space Gray 15″ MacBook Pros on sale for $200 off MSRP. Shipping is free, and Adorama charges sales tax in NJ and NY only: – 15″ 2.8GHz MacBook Pro Space Gray (MPTR2LL/A): $2199, $200 off... Read more

Jobs Board

*Apple* Solutions Consultant - Apple (United...
# Apple Solutions Consultant Job Number: 113384559 Brandon, Florida, United States Posted: 10-Jan-2018 Weekly Hours: 40.00 **Job Summary** Are you passionate about Read more
Art Director, *Apple* Music + Beats1 Market...
# Art Director, Apple Music + Beats1 Marketing Design Job Number: 113258081 Santa Clara Valley, California, United States Posted: 05-Jan-2018 Weekly Hours: 40.00 Read more
*Apple* Pay & Wallet Engineering Manager...
# Apple Pay & Wallet Engineering Manager, Apple Watch Job Number: 83769531 Santa Clara Valley, California, United States Posted: 06-Nov-2017 Weekly Hours: 40.00 Read more
UI Tools and Automation Engineer, *Apple* M...
# UI Tools and Automation Engineer, Apple Media Products Job Number: 113136387 Santa Clara Valley, California, United States Posted: 11-Jan-2018 Weekly Hours: 40.00 Read more
Senior Product Architect, *Apple* Pay - App...
# Senior Product Architect, Apple Pay Job Number: 58046427 Santa Clara Valley, California, United States Posted: 04-Jan-2018 Weekly Hours: **Job Summary** Apple , Read more
All contents are Copyright 1984-2011 by Xplain Corporation. All rights reserved. Theme designed by Icreon.