Programming Assignment Two

\def\R{{\bf R}} \hangindent\parindent \item{3a.} Consider the polynomial $ P(x)=a_0+a_1x+a_2x^2+\cdots+a_nx^n.$ Define $$m=\max\big\{\, |a_i| : i=0,\ldots,n-1\,\big\} \qquad\hbox{and}\qquad r={m\over |a_n|}+1.$$ Show that $P(x)\ne 0$ for $|x|>r$. \bigskip \hangindent\parindent \item{b.} Write a program to evaluate $P(x)$ and it's derivative using nested multiplication. Tabulate values for the polynomials given in the file{\tt\ file03.dat }at $20n$ equally spaced points on the interval $[-r,r]$. Plot each polynomial. \bigskip \hangindent\parindent \item{c.} There is a root in the interval between every two tabulated values of $P(x)$ which change sign. Use the method of false position to obtain an initial approximation and then Newton's method to find each root. Do this for each polynomial in{\tt\ file03.dat}. \bigskip \hangindent\parindent \item{d.} Did your program find all real roots for every polynomial? If not, explain why. What effect does increasing the number of tabulated values on the interval $[-r,r]$ have? \bigskip \hangindent\parindent \item{e.} [Extra Credit] Use M\"uller's method and deflation to find all roots (both real and complex) for the polynomials in{\tt\ file03.dat}.

\hangindent\parindent \item{4a.} Define $$ f(A)=\sum_{i=1}^n |A_{ii}|-\sum_{i\ne j}^n |A_{ij}|.$$ If $A$ is diagonally dominant, then $f(A)>0$. Consider the set $$ {\cal A}=\{\,PA:\hbox{$P$ is a permutation matrix}\,\}. $$ If there exists a diagonally dominant matrix $B\in{\cal A}$, then is it necessarily true that $B$ maximizes $f$ over all elements of ${\cal A}$? \bigskip \hangindent\parindent \item{b.} In general, how many elements does the set ${\cal A}$ contain? Discuss possible algorithms for maximizing $f$ over ${\cal A}$. Is there any way to avoid calculating $f(A)$ for every element of ${\cal A}$? What special cases may be easily treated? \bigskip \hangindent\parindent \item{c.} Write a program that uses Gauss-Seidel iteration to solve $Ax=b$ where the matrices $A$ and vectors $b$ are given in{\tt\ file04.dat}. Compute the residuals $r=b-Ax$ for each solution. \bigskip \hangindent\parindent \item{d.} Write a program to solve $Ax=b$ using the generalized Newton's method. Run your program for the matrices $A$ and vectors $b$ given in{\tt\ file04.dat} using values for the relaxation parameter $\omega$ of $0.6$, $0.8$, $1.2$, $1.4$ and $1.6$. Compare the speed of convergence to the Gauss-Seidel method.

Last updated: Mon Jan 22 12:30:01 PST 2001