Ponder This

July 2006

<<June July August>>

Ponder This Challenge:

Puzzle for July 2006.

Let f be a function and g an approximation to f. We define the relative error in the approximation g to f at a point x to be abs((g(x)-f(x))/f(x)) where abs means absolute value.

This month's problem involves finding approximations to the functions 1/x and sqrt(x). Recall Newton's method for refining an approximate root r of an equation h(r)=0 replaces r with the new approximation r-h(r)/h'(r) where h' denotes the derivative of h.

1. Let r = p*x + q be an approximation to the function 1/x on the interval (a,b). Suppose we refine r by performing one iteration of Newton's method (applied to the equation 1/r-x=0). Figure out how to choose p and q so that the maximum relative error on the interval (a,b) after refinement is minimized. What is this minimum maximum relative error on the interval (1,2)? Give your answer as a decimal value with 4 significant figures.

2. Let r = p*x + q be an approximation to the function sqrt(x) on the interval (a,b). Suppose we refine r by performing one iteration of Newton's method (applied to the equation r*r-x=0). Figure out how to choose p and q so that the maximum relative error on the interval (a,b) after refinement is minimized. What is this minimum maximum relative error on the interval (1,2)? Give your answer as a decimal value with 4 significant figures.

It is only necessary to submit the two decimal values requested above for credit. Remember leading zeros do not count as significant figures.

Please note you are being asked to find and submit the minimum maximum relative error produced by a linear approximation followed by one Newton iteration. You are not being asked for the minimum maximum relative error before the Newton iteration.

The first 100 people who answer all parts correctly will be listed. The answer will be posted a week after the 100th is received, or at the end of the month.

We will post the names of those who submit a correct, original solution! If you don't want your name posted then please include such a statement in your submission!

We invite visitors to our website to submit an elegant solution. Send your submission to the ponder@il.ibm.com.

If you have any problems you think we might enjoy, please send them in. All replies should be sent to: ponder@il.ibm.com

  

Challenge: 06/30/2006 @ 03:00 PM EST
Solution: 08/02/2006 @ 03:30 PM EST
List Updated: 08/02/2006 @ 03:30 PM EST

People who answered correctly:

Balakrishnan V (07.01.2006 @03:17:10 AM EDT)
Alan Murray (07.01.2006 @04:13:53 PM EDT)
Firat Solgun (07.02.2006 @09:15:29 PM EDT)
James Dow Allen (07.03.2006 @03:15:16 AM EDT)
Jan Rubak (07.04.2006 @08:17:28 AM EDT)
Eugene Vasilchenko (07.06.2006 @01:09:47 AM EDT)
Dan Dima (07.08.2006 @10:43:28 AM EDT)
David McQuillan (07.09.2006 @04:20:17 PM EDT)
Dan Stronger (07.11.2006 @04:12:53 PM EDT)
Steven Noble (07.12.2006 @02:54:04 PM EDT)
Timothy S. Lewis (07.17.2006 @01:27:00 PM EDT)
Wolfgang Kais (07.17.2006 @03:23:25 PM EDT)
Chris Shannon (07.21.2006 @01:09:27 PM EDT)
Du Yang (07.23.2006 @07:56:04 PM EDT)
John G. Fletcher (07.24.2006 @12:55:59 PM EDT)
Phil Muhm (07.25.2006 @09:09:57 PM EDT)
J. Lewandowski (07.26.2006 @03:22:01 PM EDT)
Jiri Hrdina (07.31.2006 @02:10:23 PM EDT)

Attention: If your name is posted here and you wish it removed please send email to the ponder@il.ibm.com.