\magnification=\magstep1
\centerline{Mathematics 371 -- Numerical Analysis}
\centerline{Midterm Problem Set 1 -- Selected Solutions}
\centerline{\it October 6, 2001}
\bigskip
\noindent
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\to p} h(x) = L \ne 0$.  To determine
the order of convergence of Newton-Raphson (question E)
and the ``modified Newton-Raphson'' iteration
$$x_n = x_{n-1} - {m f(x_{n-1})\over f'(x_{n-1})}$$
we must analyze $\lim_{x\to p} g'(x)$ for the appropriate
iteration function $g(x)$:
\medskip
\item{} $g(x) = x - {f(x)\over f'(x)}$ for Newton-Raphson, and
\medskip
\item{} $g_m(x) = x - {m f(x)\over f'(x)}$ for modified 
Newton-Raphson.
\medskip
\noindent
Note that the term $G(x) = {f(x)\over f'(x)}$ appears in both iteration
functions, and 
\medskip
\item{} $g'(x) = 1 - G'(x) $ for Newton-Raphson, and
\medskip
\item{} $g_m'(x) = 1 - m G'(x)$ for modified 
Newton-Raphson.
\medskip
\noindent
 For $f(x) = (x-p)^m h(x)$, for $x \ne p$, we get:
$$\eqalign{G(x) &= {(x-p)^m h(x)\over m(x-p)^{m-1}h(x) + (x-p)^m h'(x)}\cr
&= {(x-p)h(x)\over mh(x) + (x-p)h'(x)}\cr
\Rightarrow G'(x) &= {(mh(x) + (x-p)h'(x))(h(x) + (x-p)h'(x))\over (mh(x) + (x-p)h'(x))^2}\cr
&\qquad  - {(x-p)h(x)((m+1)h'(x) + (x-p)h''(x))
\over (mh(x) + (x-p)h'(x))^2}\cr}$$
Hence, $lim_{x\to p} G'(x) = {mL^2\over m^2L^2} = {1\over m}$.

In the Newton-Raphson case (problem E), we get 
$$\lim_{x\to p} g'(x) = 1 - \lim_{x\to p} G'(x) = 1 - {1\over m}$$
Since this is not zero when $m \ge 2$, the convergence of Newton-Raphson
is (only) linear in these cases.  Moreover, the bigger $m$ is, the closer
$\lim_{x\to p} g'(x)$ is to 1, so the {\it 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\to p} g_m'(x) = 1 - m\lim_{x\to p} G'(x) = 1 - m\cdot {1\over m} = 0$$
The convergence of modified Newton-Raphson
is quadratic.  However, we do {\it 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.  
\bigskip
\noindent
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
$$\eqalign{x_n = g(x_{n-1}) &= g(p) + g'(p)(x_{n-1}-p) + {g''(p)\over 2}(x_{n-1}-p)^2
+ {g'''(\xi)\over 6}(x_{n-1} - p)^3\cr
                        &= p +{g'''(\xi)\over 6}(x_{n-1} - p)^3\cr
\Rightarrow |x_n - p| &= {|g'''(\xi)|\over 6}|x_{n-1} - p|^3\cr}$$
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) \ne 0$, and 
$$g(x) = x - {f(x)\over f'(x)} - {1\over 2}{f''(x)\over f'(x)}
\left({f(x)\over f'(x)}\right)^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:
$$\eqalign{g' &= 1 - {(f')^2 - ff''\over (f')^2} 
- {1\over 2}{f'f'''-(f'')^2\over (f')^2}\cdot \left({f\over f'}\right)^2\cr
&\qquad -{f''\over f'}\cdot {f\over f'}\cdot{(f')^2 - ff''\over (f')^2}\cr
&= {2ff''(f')^2 - f^2 f'f''' + f^2(f'')^2 - 2ff''(f')^2 + 2f^2 (f'')^2 \over 2(f')^4}\cr
&= {3f^2 (f'')^2 -  f^2 f'f''\over 2(f')^4}\cr}$$ 
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) \ne 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$.

\bye 
