IBM Ponder This #099 · July 2006

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.

Solution

Best opened after a real attempt

To be added.