Ponder This Challenge - July 2006 - Approximations of 1/x and sqrt(x)

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

Solution

• Click here to view the solution

  Answer:

  1. Let r be an approximation to 1/x. Here h(r)=1/r-x, h'(r)=-1/(r*r). So the refined value of r, r*, produced by one iteration of Newton's method is r*=r-(1/r-x)/(-1/(r*r))=r+r-x*r*r= r+r*(1-x*r). The relative error in r is |(1/x-r)/(1/x)|=|1-x*r|. Let e=1-x*r. Then r*=r+r*e and the relative error in r* is
     |(1/x-r*)/(1/x)|=|1-x*r*|=|1-x*r-x*r*e|=|e-x*r*e=|e*(1-x*r)|=|e*e|= e*e. Now we wish to choose p and q so that if r=p*x+q then the maximum value of e*e over the interval (a,b) is minimized. Clearly it suffices to minimize the maximum value of |e| over (a,b). Let use choose p and q so e=0 at a and b. Then

  1.1 p*a+q=1/a
  1.2 p*b+q=1/b
  so
  1.3 p=(1/a - 1/b)/(a-b) = -1/(a*b)
  1.4 q= 1/a + 1/b

  then for a<x<b, e=(p*x+q-1/x)/(1/x)=p*x*x+q*x-1. e'=2*p*x+q so e has an extrema at x=-q/(2*p)=(a+b)/2. Let t be the value of the extrema. Then t = -q*q/(4*p) - 1 = .25*(a+b)*(a+b)/ab - 1 = (a-b)**2/(4*a*b). Choose s so that 1-s=s*(1+t)-1 or s=2/(2+t). Then if we choose p*=s*p and q*=s*q it is easy to see that e = -t/(2+t) at a and b, e = t/(2+t) at (a+b)/2 and |e| < t/(2+t) elsewhere on (a,b). Furthermore this is the minimum possible maximum value for |e| since reducing |e| at a or b will necessarily increase it at (a+b)/2. So the minimum maximum value of e*e on the interval (a,b) is 1/((2+t)*(2+t)) where t= (a-b)**2/(4*a*b). Plugging in a=1, b=2 we obtain t=1/8, t/(2+t)=1/17 and the desired minimum maximum relative error on the interval (1,2) is 1/289=.003460207612...=.003460 to four significant figures.

  2. The solution to the second part is similar. Let r be an approximation to sqrt(x). Here h(r)=r*r-x, h'(r)=2*r. So the refined value of r, r*, produced by one iteration of Newton's method is r*=r-(r*r-x)/(2*r)=(r*r+x)/2r=(r+x/r)/2. Suppose r=v*sqrt(x). Then r*=((v+1/v)/2)*sqrt(x). The relative error in r* is |(v+1/v)/2)-1|. Clearly this will be minimized when v lies between 1+w and 1/(1+w) for the minimum possible positive value of w. As above choose p and q so that w=1 at a and b. This implies

  2.1 p*a+q=sqrt(a)
  2.2 p*b+q=sqrt(b)
  so
  2.3 p=(sqrt(a)-sqrt(b))/(a-b) = 1/(sqrt(a)+sqrt(b))
  2.4 q= sqrt(a*b)/(sqrt(a)+sqrt(b))

  then for a<x<b, v=(p*x+q)/sqrt(x). v'=.5*p/sqrt(x)-.5*q/(x*sqrt(x) so v has an extrema at x=q/p=sqrt(ab). Let t be the value of the extrema. Then t=2*sqrt(a*b)/(sqrt(a)+sqrt(b))/sqrt(sqrt(a*b))= 2*sqrt(sqrt(a*b))/(sqrt(a)+sqrt(b)). So v=1 at a and b and is otherwise less than 1 with a minimum value of t. Let s=1/sqrt(t) and let p*=s*p, q*=s*q. Let v*=((p*)*x+q*)/sqrt(x). Let w=s-1. The it is easy to see that v* = s = 1+w at a and b that v* = t*s = sqrt(t) = 1/s = 1/(1+w) at sqrt(a*b) and that v* will lie between 1+w and 1/(1+w) elsewhere on (a,b). Further this is the smallest positive value of w for which we can find a linear approximation which always lies between (1+w)*sqrt(x) and sqrt(x)/(1+w) since reducing the relative error at a or b will increase the relative error at sqrt(a*b). So putting things together let t=2*sqrt(sqrt(a*b)/(sqrt(a)+sqrt(b), s=1/sqrt(t) and e=(s+1/s)-1. Then e is the minimum maximum relative after one Newton iteration which we are seeking. Letting a=1, b=2 we have

  t=2*sqrt(sqrt(2))/(1+sqrt(2))=.9851714310...,
  s=1/sqrt(t)=1.0074977742..., e=(s+1/s)-1=.00002789912802...=.00002790

  to four significant figures.

  ---

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

Solvers

• 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)