QforMortals3/Example Newtons Method

From Kx Wiki
Jump to: navigation, search

1.13 Example: Newton’s Method for nth Roots

You may recall from elementary calculus the simple and powerful technique for computing roots of functions, called the Newton-Raphson method. (It actually bears little superficial resemblance to what Newton himself originally developed). The idea is to start with an initial guess that is not too far from the actual root. Then determine the tangent to the graph over that point and project the tangent line to the x-axis to obtain the next approximation. Repeat this process until the result converges within the desired tolerance.

We formulate this as a recursive algorithm for successive approximation.

Let’s use this procedure to compute the square root of 2. The function whose zero we need to find is f(x) = x2 - 2. The formula for successive approximation involves the derivative of f, which is f’(x) = 2*x.

Given that we know that there is a square root of 2 between 1 and 2 due to the sign change of f, we start with 1.0 as the base case x0. Then the first approximation is,

q)x0-((x0*x0)-2)%2*x0
1.5

We abstract this expression to a function that computes the n+1st approximation in terms of xn

q){[xn] xn-((xn*xn)-2)%2*xn}
_

Now use it to run the first two iterations.

q){[xn] xn-((xn*xn)-2)%2*xn}[1.0] 
_
q){[xn] xn-((xn*xn)-2)%2*xn}[1.5] 
_

Observe in your console session that this looks promising for convergence to the correct answer.

Wouldn’t it be nice of q had a higher-order function to apply a function recursively, starting at the base case, until the output converges? You won’t be surprised that there is another overload of our friend over that does exactly this. Just specify the base case and q iterates until the result converges within the system comparison tolerance (as of this writing—Sep 2015—that tolerance is 10-14)

q){[xn] xn-((xn*xn)-2)%2*xn}/[1.5] 
1.414214


To witness the convergence, do two things. First, set the floating point display to maximum.

q)\P 0               /note upper case P

Information.png Tip: This displays all digits of the underlying binary representation, including the 17th digit, which is usually schmutz..

Second, switch the adverb from over to scan so that we can see the intermediate results.

q){[xn] xn-((xn*xn)-2)%2*xn}\[1.0] 
_

As your console display shows, that is pretty fast convergence. Why limit ourselves to the square root of 2? Abstracting the constant 2 into a parameter c in the function f, the successive approximation function becomes,

q){[c; xn] xn-((xn*xn)-c)%2*xn} 
_

At this point we use a feature, related to currying in functional programming called projection in q, in which we only partially supply arguments to a function. The result is a function of the remaining, unspecified parameters. We indicate partial application by omitting the unspecified arguments. In our case, we specify the constant c as 2.0, leaving a monadic function of the remaining variable xn.

q){[c; xn] xn-((xn*xn)-c)%2*xn}[2.0;] 
_

Since this is solely a function of xn, we can apply it recursively to the base case until it converges to obtain the same result as the original square root function. 

q){[c; xn] xn-((xn*xn)-c)%2*xn}[2.0;]/[1.0] 
_

But now we are free to choose any (reasonable) value for c. For example, to calculate the square root of 3.0.

q){[c; xn] xn-((xn*xn)-c)%2*xn}[3.0;]/[1.0] 
_

Intoxicated with the power of function abstraction and recursion, why restrict ourselves to square roots? We abstract once more, turning the power into a parameter p. The new expression for the successive approximation has a pth power in the numerator and an p-1st power in the denominator, but we already know how to calculate these.

q){[p; c; xn] xn-(((*/)p#xn)-c)%p*(*/)(p-1)#xn}
_

Supplying p and c (only) leaves a function solely of xn, which we can once again iterate on the base case until convergence. We reproduce the previous case of the square root of 3.0; then we calculate the fifth root of 7.

q){[p; c; xn] xn-(((*/)p#xn)-c)%p*(*/)(p-1)#xn}[2; 3.0;]/[1.0] 
_
q){[p; c; xn] xn-(((*/)p#xn)-c)%p*(*/)(p-1)#xn}[5; 7.0;]/[1.0] 
_

It is amazing what can be done in a single line of code when you strip out unnecessary programming frou-frou. Perhaps this is intimidating to the qbie, but now that you have taken the blue pill, you will feel right as rain.



Prev: Example: Fibonacci Numbers, Next: Example: FIFO Allocation

Reprinted with the author's permission from: q for Mortals Version 3, An Introduction to Q Programming by Jeffry A. Borror.

The book is available on Amazon. In the United Kingdom, it is available at Amazon UK.

©2015 Jeffry A. Borror/ q4m LLC

Personal tools
Namespaces
Variants
Actions
Navigation
Print/export
Toolbox