Mathematics 371 – Numerical Analysis Midterm Problem Set 1 – Selected Solutions October 6, 2001

E. and F. Both of these problems can be handled in much the same way. Our hypothesis in both is that f(x) has a root of multiplicity m at x = p, so

f(x) = (x − p)^{m}h(x),

where lim_{x→p}h(x) = L ≠ 0. To determine the order of convergence of Newton-Raphson (question E) and the “modified Newton-Raphson” iteration

x_{n} = x_{n−1} − \frac{mf(x_{n−1})}{f′(x_{n−1})}

we must analyze lim_{x→p} g′(x) for the appropriate iteration function g(x):

g(x) = x − \frac{f(x)}{f′(x)} for Newton-Raphson, and
g_{m}(x) = x − \frac{mf(x)}{f′(x)} for modified Newton-Raphson.

Note that the term G(x) = \frac{f(x)}{f′(x)} appears in both iteration functions, and

g′(x) = 1 − G′(x) for Newton-Raphson, and

g′_{m}(x) = 1 − mG′(x) for modified Newton-Raphson.

For f(x) = (x − p)^{m}h(x), for x ≠ p, we get:

G(x) = \frac{(x − p)^{m}h(x)}{m(x − p)^{m−1}h(x) + (x − p)^{m}h′(x)}

= \frac{(x − p)h(x)}{mh(x) + (x − p)h′(x)}

⇒ G′(x) = \frac{(mh(x) + (x − p)h′(x))(h(x) + (x − p)h′(x))}{(mh(x) + (x − p)h′(x))^{2}}

− \frac{(x − p)h(x)((m + 1)h′(x) + (x − p)h′′(x))}{(mh(x) + (x − p)h′(x))^{2}}

Hence, lim_{x→p}G′(x) = \frac{mL^{2}}{m^{2}L^{2}} = \frac{1}{m}.

In the Newton-Raphson case (problem E), we get

lim_{x→p} g′(x) = 1 − lim_{x→p} G′(x) = 1 − \frac{1}{m}

Since this is not zero when m ≥ 2, the convergence of Newton-Raphson is (only) linear in these cases. Moreover, the bigger m is, the closer lim_{x→p} g′(x) is to 1, so the slower convergence will be. Double roots (m = 2) will give faster convergence than triple roots (m = 3) and so forth.

In the modified Newton-Raphson case (problem F), we get

lim_{x→p} g′_{m}(x) = 1 − m lim_{x→p} G′(x) = 1 − m · \frac{1}{m} = 0

The convergence of modified Newton-Raphson is quadratic. However, we do need to know the right m to use in order to set up the correct iteration function to get quadratic convergence. That information might not be known (or easy to determine), so Steffensen might be superior in many cases.

G. First, by Taylor’s theorem, if g′′′ is continuous, and if g′(p) = g′′(p) = 0, then for the fixed-point iteration x_{n} = g(x_{n−1}), we have

x_{n} = g(x_{n−1}) = g(p) + g′(p)(x_{n−1} − p) + \frac{g′′(p)}{2}(x_{n−1} − p)^{2} + \frac{g′′′(ξ)}{6}(x_{n−1} − p)^{3}

= p + \frac{g′′′(ξ)}{6}(x_{n−1} − p)^{3}

⇒ |x_{n} − p| = \frac{|g′′′(ξ)|}{6}|x_{n−1} − p|^{3}

which gives cubic convergence (at least).

So the rest of the problem is to show that g′(p) = g′′(p) = 0 when f(p) = 0, f′(p) ≠ 0, and

g(x) = x − \frac{f(x)}{f′(x)} − \frac{1}{2} \frac{f′′(x)}{f′(x)} (\frac{f(x)}{f′(x)})^{2}

Since g′′′(x) will contain f^{(4)}(x), the hypotheses should also include the condition that f^{(4)}(x) is continuous on some interval containing p. Let us first compute g′(x), simplifying whenever possible, using the product, quotient, and chain rules:

g′ = 1 − \frac{(f′)^{2} − ff′′}{(f′)^{2}} − \frac{1}{2} \frac{f′f′′′ − (f′′)^{2}}{(f′)^{2}} · (\frac{f}{f′} )^{2}

− \frac{f′′}{f′} · \frac{f}{f′} · \frac{(f′)^{2} − ff′′}{(f′)^{2}}

= \frac{2ff′′(f′)^{2} − f^{2}f′f′′′ + f^{2}(f′′)^{2} − 2ff′′(f′)^{2} + 2f^{2}(f′′)^{2}}{2(f′)^{4}}

= \frac{3f^{2}(f′′)^{2} − f^{2}f′f′′}{2(f′)^{4}}

Let’s try a bit of “creative laziness” here. Note that both terms on the top have a factor of f^{2} so we can write g′(x) = (f(x))^{2}H(x). Since we assume f(p) = 0 and f′(p) ≠ 0, we get g′(p) = 0. Moreover, if we differentiate again,

g′′(x) = 2f(x)f′(x)H(x) + (f(x))^{2}H′(x)

and g′′(p) = 0 also since both terms still contain a factor of f(x), while the denominators in H, H′ contain only powers of f′. This completes the proof that g′(p) = g′′(p) = 0.