Tod means Fox

Need to find the root of a real-valued function and simple algebra just won’t cut it? Then Newton’s method is for you (if you can remember back to your calculus days, that is).

Newton’s method is a root-finding algorithm and uses iteration to solve nonlinear equations. The process involves making a guess at the true solution and then applying a formula to get a better guess. This process repeats until the (approximate) answer is found. The methodology is part of numerical analysis, which is the “branch of mathematics dealing with methods for obtaining approximate numerical solutions of mathematical problems (dictionary.com)”. Specifically, the type of problems fit into the “continuous mathematics” category that are common in medicine, engineering, science, and business industries. (For a good discussion on continuous verses discrete mathematics, check out this blog entry by Mark C. Chu-Carroll or this page from ESC.EDU.) As you might guess, continuous mathematics is very important in business intelligence, specifically statistical analysis of data.

The general form to find the approximation is as follows:

Here’s how it works: Start with an initial guess (get out your graph paper!). Then the function draws a tangent to approximate the function based on your initial guess. Next, the function computes the x-intercept. This x-intercept will be better than the initial guess, and closer to the answer (the root). It then repeats with the x-intercept as the new guess.

The FoxPro code:

LOCAL lcFunction, lnInitialGuess, lnIterations 
 
*-- set the fuction, my initial guess, and number of iterations
lcFunction = "(1/4)*x^3 - 3*x^2 + (3/4)*x - 2"
lnInitialGuess = 2
lnIterations = 10 
 
*-- run newton
newton(lcFunction, lnInitialGuess, lnIterations )
 
*-- foxpro does newton:
FUNCTION newton
LPARAMETERS tcFunction, tnInitialGuess , tnIterations 
 
LOCAL lcDerivative AS String
LOCAL lnNewGuess, lnIter , x , lnY , lnSlope , lnCol5 , lnCol6
 
CREATE CURSOR crNewton (col_n n(2), col_Xn n(14,5), col_fXn n(14,5), col_f1Xn n(14,5), col_ys n(14,5) , col_ng n(14,5))
 
limh = .000001
lcFunction = ALLT(tcFunction)
lnInitialGuess = EVL(tnInitialGuess,0)
lnIterations = EVL(tnIterations,1) 
 
lnNewGuess = lnInitialGuess
 
*-- Loop for each user iterations
FOR lnIter = 1 TO lnIterations
 
  *-- Set guess
  x = lnNewGuess
 
  *-- Run Function
  lnY = &lcFunction
 
  *-- Find Derivative
  lnHoldx = x
  x = x + limh
  lnFuncpluslimh = &lcFunction
  x = lnHoldx
  lnFuncminlimh = &lcFunction
  lnSlope = (lnFuncpluslimh - lnFuncminlimh) / limh 
 
  lnys = lny/lnSlope 
 
  *-- Find New guess
  lnNewGuess = x - lnys
 
  *-- Populate the cursor
  INSERT INTO crNewton (col_n  ,col_Xn ,col_fXn ,col_f1Xn ,col_ys ,col_ng) ;
                VALUES (lnIter ,x      ,lnY     ,lnSlope  ,lnys   ,lnNewGuess)
 
  *-- Reset the guess and continue
  lnNewGuess = lnNewGuess
 
NEXT
 
SELECT crNewton
LOCATE
BROWSE NORMAL

In this run, with the equation I have defined, the approximation of x is 11.80326. If you plug this number in for x in the original equation, it evaluates to .00014. Pretty close! And that’s exactly what this algorithm is great for. Try these additional functions to get the hang of it. You can change the guess and iterations as you like as well:

• “x + 1″
• “x^3-12″
• “x*(x^3)-(3/4)*x”
• “((x^4+1)*(x^3+2))-11″