Math 128a - Homework 3 - Due Sept 21 at the beginning of class

1) Sometimes is difficult or expensive to compute f
(xn ) for use in Newton’s method, so we use an
approximation α instead. Find the condition on α to ensure that the iteration xn+1 = xn −f (xn )/α
will converge (at least) linearly to a zero of f if started near enough to the zero.
Answer: Let z be a zero of f and let en = xn − z. The iteration is xn+1 = xn − f (xαn ) , so
en+1 = en − f (xαn ) . Now compute using the Taylor series about z:

f (xn )
en+1 = en −
α
1
= en − [f (z) + f
(z)en + O(e2n )]
α
en
= en − [f
(z) + O(en )]
α
f
(z)
= [1 − + O(en )]en
α
So in order to get linear convergence we need

f
(z) |α − f
(z)|
|1 − |= <1
α α


which is the same as α having the same sign as f
(z) and |f 2(z)| < |α|.
2) Show that when f (z) = f
(z) = 0 = f

(z), i.e. z is a double zero, then Newton’s method only
converges linearly to z (with constant .5) when started close enough to z, not quadratically. Show
that if z is a double zero, then the modified Newton iteration xn+1 = xn − 2 · f (xn )/f
(xn ) is
quadratically convergent. (Note: A similar argument shows that if x is a root of multiplicity k,
then xn+1 = xn − k · f (xn )/f
(xn ) converges quadratically, but you do not have to show this.)
Answer: If f (z) = f
(z) = 0 = f

(z) then we compare en = xn − z and en+1 = xn+1 − z as
follows:
f (xn )
en+1 = en −
f
(xn )
f

(z)e2n
f (xn ) ≈
2
f
(xn ) ≈


f (z)en
1
|en+1 | ≈ |en − en |
2
1
= |en |
2
which implies linear convergence of xn to z with c = 1/2. (A similar argument shows that, for a
root of mulitplicity k > 1, convergence is linear with constant c = 1 − 1/k, which gets slower (c
gets closer to 1) for higher multiplicity k.
So if f (z) = f
(z) = 0 = f

(z), we try the modified iteration xn+1 = xn − 2 ff
(x n)
(xn ) . This

1
converges quadratically because:

f (xn )
en+1 = en − 2
f
(xn )
f

(z)e2n f


(ξ)e3n
f (xn ) = +
2! 3!
f (z)en f (z)e3n


2



≈ +
2! 3!




f (xn ) ≈ f (z)en so :
en f


(z)e2n
|en+1 | ≈ |en − 2( + )|
2 6f

(z)
f


(z)
= · |en |2
3f

(z)

3) Suppose we want to implement the squareroot function using Newton’s method xn+1 = (xn +
a/xn )/2 to solve f (x) = x2 − a = 0. The input a can be any positive normalized IEEE double
precision number (zero and subnormal numbers are handled as special cases). We want to quickly
find a starting value x1 that guarantees that 3 Newton steps are enough to get nearly full precision
(relative error near 2−52 ) no matter what a is. We will compute x1 with a little bit-fiddling and a
table as follows:

Part 1. Using the floating point representation a = 2e (1 + f ), where 0 ≤ f < 1, rewrite a as

a = 22e (1 + f
), where e
= e/2 (i.e. e/2 rounded down to the nearest integer) and f
is
modified appropriately. What range can 1 + f
lie in?


Answer: Write a = 2e (1 + f ) = 22e (1 + f
), where e
= e/2. If e is even, then e
= e/2,
2e
= e and so 1 ≤ 1 + f
= 1 + f < 2. If e is odd, then e
= (e − 1)/2, 2e
= e − 1 and so
2 ≤ 1 + f
= 2(1 + f ) < 4. Altogether 1 ≤ 1 + f
< 4.


Part 2. Since a1/2 = 2e (1 + f
)1/2 , it suffices to apply Newton to 1 + f
. We will pick a starting
value x1 by looking it up in a table. Write 1 + f
= bb.bbbbb...2 , i.e. as a binary number with
a fractional part, where each b is a bit. Suppose we take the leading k bits of this number
(which approximate 1 + f
, the better for larger k), and look up its square root x(1) in a
table (k bits means we need a table of 2k values, which we index into just by interpreting the
leading k bits as a binary integer). What is the smallest possible k that guarantees x(1) is
accurate enough to guarantee that we only need 3 Newton iterations? 2 Newton iterations?
Do not worry about roundoff in your analysis. (In actual IEEE arithmetic, which requires
the square root to be correctly rounded, extra care in the algorithm is needed to ensure this,
but this algorithm is nearly accurate enough, and has been frequently used in the past.)
Answer: Let y = 1 + f
. The problem is: Given y with 1 ≤ y < 4, let y
be the closest k-bit
binary number to y, so that |y − y
| ≤ 2−k+1 (because we have two bits in the integer part)
with 1 ≤ y
≤ 4. Now we wa nt to find x such that y = x2 and we are given (by the table) x


2 . We start Newton’s method for f (x) = x2 − y with x0 = x
such that y
= x
, and we want
to know how many iterations it will take, in terms of k, to get to maximum IEEE precision,
which, for 1 ≤ x ≤ 2 is an error of less than or equal to 2−53 . We begin by bounding the

2
 initial error e0 = x0 − x from the table, given that x0 is the exact square root of y
≈ y:

2−k+1 ≥ |

y − y|
x2 − x2 |
= |

= |x20 − x2 |
= |x0 − x| · |x0 + x|
≥ 2|x0 − x| because 1 ≤ x, x0 , so
|e0 | = |x − x0 |
≤ 2−k

f (x)


Next, we want |en | ≤ 2−53 . We know that |en+1 | ≤ C|en |2 where C ≈ 2f


(x) . But f (x) = 2x
1 n
and f

(x) = 2 so C ≈ 2x ≤ 12 (since 1 ≤ x). Thus |en+1 | ≤ 12 |en |2 , so |en | ≤ 21n |e0 |2 ≤
n
2−n−k2 ≤ 2−53 . The inequality that says |en | ≤ 2−53 is thus n + k2n ≥ 53; actually we want
to find k that make n = 2 Newton iterations and n = 3 Newton iterations work. Thus we
need k ≥ 53−n k 7
2n . For n = 3 we have k = 7 (a table of 2 = 2 = 128 words) and for n = 2 we
k 13
have k = 13 (a table of 2 = 2 = 8096 words). This shows that we may trade off time and
space, with a (much) bigger table (larger 2k ) yielding a faster algorithm (smaller n). This
tradeoff of time and space is common in designing numerical algorithms.

4) Prove that, if F : [a, b] → R, if F
is continuous and if |F
(x)| < 1 on [a, b] then F is a contraction
on [a, b]. Does F necessarily have a fixed point?
Answer: Proof: Since |F
(x)| < 1 on [a, b] and |F
| is a continuous function on the closed
interval [a, b], |F
| has a maximum value on [a, b], say λ, and λ < 1. Now pick two arbitrary points
x, y ∈ [a, b]. By the Mean-Value Theorem there exists a point c between x and y such that

F (x) − F (y)
= F
(c) so :
x−y
|F (x) − F (y)|
= |F
(c)|
|x − y|
≤ λ (since c ∈ [a, b]), so :
|F (x) − F (y)| ≤ λ|x − y|

Therefore F is a contraction.

F does not necessarily have a fixed point: for example, F (x) = x/2 − 1 has no fixed points as
a map F : [1, 2] → R.
5) Prove that if F is a continuous map of [a, b] into [a, b] then F must have a fixed point. Then
determine if this assertion is true for functions from R to R.
Answer: Proof: We want to find some x ∈ [a, b] such that F (x) = x; alternatively, letting
G(x) = F (x) − x, we want to find a value of x such that G(x) = 0. Note that G(a) = F (a) − a ≥ 0
because a ≤ F (a) ≤ b and that G(b) = F (b) − b ≤ 0 because a ≤ F (b) ≤ b. Thus, since G is
continuous, there must exist x between a and b such that G(x) = 0.

This is not true for functions from R to R: for example, F (x) = x − 1 has no fixed points.