July 2006
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