%		SECOND EXAM
\magnification=1095
\parindent=30pt
\parskip=4pt plus 4pt minus 4pt
%\hsize=5.41in \vsize=7.5in     %for magnification=1200
 \hsize=5.91in \vsize=8.18in    %for magnification=1095
\baselineskip=13pt plus 2pt minus 1pt \lineskiplimit=2pt
\lineskip=2pt plus 2pt                                  %\raggedright
\tolerance=800

\font\bfVIII=cmbx8 \font\rmeight=cmr8  \def\rmVIII{\rmeight
\baselineskip=10pt
plus 1pt minus 1pt \lineskiplimit=2pt \lineskip=2pt plus 1pt minus 1pt
\parskip=0pt \def\strut{\vrule width 0pt height 7.5pt depth 2.5pt}}

%math symbol definitions
\def\n#1{\left\|#1\right\|}\def\mn#1{\left\|#1\right\|_\infty}
\def\tn#1{\left\Vert #1\right\Vert_2}
\def\:{\mathrel{\mathord:\mathord=}}
\def\la{\left\langle} \def\ra{\right\rangle} \def\cP{{\cal P}}
\def\QED{\hfil\penalty 0\null\nobreak\hfill\quad\hbox{\rm Q. E. D.}\par}

% Underscore selected text
{\def\under#1{\leavevmode\hbox{\vtop{\hbox{\hskip1pt#1\vphantom
{g)}\hskip1pt}
\hrule}}}

\centerline{\bf CS/MATH 3414 SECOND EXAM}
\bigskip\rightline{Name \leaders\hrule\hskip 2.5in}
\medskip\hrule\smallskip\noindent
Show your answers on these pages. Either show your work on these pages
or on attached sheets.\smallskip\hrule\medskip

\def\urule{\hbox{\leaders\hrule\hskip 40pt}}

\item{1. (15)}Consider the root finding problem $$f(x)=x^2\,\cos{\pi
x\over 4} =0.\eqno\rm(R)$$
\item{A.}Does Newton's method applied to (R)
converge to {\it some} root of (R) for any starting point $x_0$? Justify
your answer.
\medskip
\item{}No. $f(x)$ oscillates, with many points $x_0$ where $f'(x_0)=0$.
Newton's method started from any such $x_0$ will fail.
\bigskip
\item{B.}For $x_0=1$, Newton's method applied to (R) has rate of
convergence $p= 1$.
\item{C.}For $x_0=1.9$, $x_1=2.1$, the secant method applied to (R) has
rate of convergence $p= 1.618$.

\vskip .5in
\item{2. (15)}Consider the problem of finding the best discrete least
squares aproximation $p(x)=\alpha_0+\alpha_1\sin x+\alpha_2\cos x$ to
the data points $(x_i,f_i)$, $i=1$, \dots, 5, where $x_i=0.1i$,
$f_i=\sqrt{x_i}$. Set this up (do not solve) as a linear algebra problem:
minimize $\Vert{Au-b}\Vert_2$, where
\vskip .25in
$$A=\pmatrix{1&\sin.1&\cos.1\cr
1&\sin.2&\cos.2\cr
1&\sin.3&\cos.3\cr
1&\sin.4&\cos.4\cr
1&\sin.5&\cos.5\cr},
\hskip .5inu=\pmatrix{\alpha_0\cr
\alpha_1\cr
\alpha_2\cr},
\hskip .25inb=\pmatrix{\sqrt{.1} \cr
\sqrt{.2} \cr
\sqrt{.3} \cr
\sqrt{.4} \cr
\sqrt{.5} \cr}.
\hskip .25in$$
\vskip .5in

\item{3. (20)}The first two orthogonal polynomials $\psi_0$,
$\psi_1$ with respect to the inner product $$
\langle p,q \rangle=\int_0^1 p(x)q(x)\,dx \qquad\hbox{are}\qquad
\psi_0(x)=1,\qquad \psi_1(x)=x-{1\over2}. $$
Find the third orthogonal polynomial $\psi_2(x)$ with respect to this
inner product. $\psi_2(x)= {x^2-x+{1\over6}}$.
\bigskip
Use the three term recurrence relation for $\psi_2(x)$, or compute it
directly as follows.  

Write $\psi_2(x)=x^2+\alpha x+\beta$.  Then solve
\medskip
$\langle\psi_0, \psi_2\rangle=\int_0^1x^2+\alpha x +\beta\, dx=0,$

$\langle\psi_1, \psi_2\rangle=\int_0^1(x-{1\over2})(x^2+\alpha x+\beta)\, dx=0$ 
for $\alpha$ and $\beta.$ \vskip .5in \filbreak

\item{4. (15)}Find constants $w_0$, $\tilde w_0$, $w_1$ such that the
integration formula $$\int_0^2 f(x)dx \approx w_0f(0)+\tilde w_0f'(0)
+w_1f(1)$$ is exact if $f(x)$ is a polynomial of degree $\le2$.
$w_0=-{2\over3}$, $\tilde w_0=-{2\over3}$, $w_1={8\over3}$.
\bigskip

\noindent Let $L(f)=w_0f(0)+\tilde w_0f'(0)+w_1f(1)$, and form the three equations
\bigskip
\halign{\tabskip=3pt  & \hfil $ # $\cr 
L(1)&=&w_0&&&&&&+&w_1&=\int_0^2 1 \,dx=2,\cr}
\smallskip 
\halign{\tabskip=3pt & \hfil $ # $\cr
L(x)&=&&&&&&\tilde w_0&+&w_1&=\int_0^2 x \,dx=2,\cr}
\smallskip
\halign{\tabskip=3pt & \hfil $ # $\cr
L(x^2)&=&&&&&&&&&&&&&w_1&=\int_0^2 x^2 dx={8\over3}.\cr}
\medskip
\noindent Solving for the $ws$ makes $L(f)$ exact for $1, x, x^2$, and therefore
$L(f)$ is exact for any polynomial of degree $\leq2$.
\vskip .3in
\filbreak

\item{5. (10)}The best technique for the integral $$\int_0^1
{\sin\bigl(x^2+3\bigr)\over\sqrt{x}}dx$$would be {Gaussian
quadrature, since the integral is improper}.
\vskip .3in
\filbreak

\item{6. (10)}Suppose that an integration formula ${\cal F}(f;h)$
satisfies $$\int_a^b f(x)\,dx={\cal F}(f;h)+a_3h^3+a_6h^6+a_9h^9+
\cdots,$$where the $a_i$ are constants independent of $h$. Then an
${\cal O}\bigl(h^6\bigr)$ accurate estimate of $\int_a^b f(x)dx$, in
terms of ${\cal F}(f;h)$ and ${\cal F}(f;h/2)$, is $${8{\cal
F}(f;h/2)-{\cal F}(f;h)\over7}$$ 
\vskip .3in
\filbreak

\item{7. (15)}Let $S(x)$ be a $C^1$ cubic spline with breakpoints at
$x_i=i/10$, $i=0,1,\ldots,10$. Simpson's rule with $h=0.05$ is exact for
$\int_0^1 S(x)dx$, but it is not exact with $h=0.04$. Explain
why. 
\bigskip
$S(x)$ is a cubic polynomial on each of the intervals $[0, .1]$,
$[.1, .2]$, $\ldots$, $[.9, 1]$.  Simpson's rule with $h=.05$ places
3 points in each of these intervals, and thus essentially applies
Simpson's rule separately to the intervals.  Since Simpson's rule is
exact for cubics, it gives the exact integral for each of the
subintervals.  

With $h=.04$, Simpson's rule is being applied to the
interval $[0, .08]$ (where it is exact), then to $[.08, .16]$, and
so on.  $S(x)$ is not a single cubic in $[.08, .16]$, and therefore
Simpson's rule is not exact over $[.08, .16]$, or $[0, 1]$ either.
\vfill\eject\bye