\documentclass[11pt]{article}

\usepackage{times}
\usepackage{geometry}
\usepackage{wrapfig}
\usepackage[colorlinks,urlcolor=blue]{hyperref}

\geometry{left=1in,right=0.75in,top=0.75in,bottom=0.75in}

\newif\ifpdf
\ifx\pdfoutput\undefined
\pdffalse % we are not running PDFLaTeX
\else
\pdfoutput=1 % we are running PDFLaTeX
\pdftrue
\fi

\ifpdf
\usepackage[pdftex]{graphicx}
\else
\usepackage{graphicx}
\fi

\newcommand{\myhead}[4]{
\framebox[1.005\linewidth]{\parbox[b]{\linewidth}
{\begin{tabular}{ *{2}{p{0.25\linewidth}} r }
\textsc{#1} & \hfill {#2} \hfill \ & \rule{78pt}{0pt} \textsc{Name:}\rule[-2pt]{100pt}{1pt}\rule{4pt}{0pt}\rule{0pt}{12pt} \\[1.5ex]
\textsc{#3} & \hfill {#4} \hfill \ &  \rule{78pt}{0pt} \textsc{Name:}\rule[-2pt]{100pt}{1pt}\rule{4pt}{0pt}\rule{0pt}{12pt}
\end{tabular} \\ }}
}

%%%%%%%%%%%%%%%%
\begin{document}
\graphicspath{{Images/}}

\ifpdf
\DeclareGraphicsExtensions{.pdf, .jpg, .tif}
\else
\DeclareGraphicsExtensions{.eps, .jpg}
\fi

\noindent\myhead{Mat 1110}{Modified Newton's Method}{Fall '10}{}

\thispagestyle{empty}

\section*{Group Project: Modified Newton's Method}
\subsection*{Background}
{\href{http://www-history.mcs.st-andrews.ac.uk/Biographies/Newton.html}{Isaac Newton}} (1642--1727)%
\footnote{Actually, Newton was born on Jan 4, 1643. In 1752, England switched from the Julian calendar to the Gregorian calendar making Newton's birthday become Dec 25, 1642. Which date is correct? Both are!}
introduced an algebraic technique for finding the roots of polynomials in his text {\href{http://www3.babson.edu/Archives/upload/Analysis1711.pdf}{\emph{De Analysi per Aequationes Numeri Terminorum Infinitas}}} 
(\emph{On Analysis by Infinite Numerical Series}). 
\begin{wrapfigure}{r}{1.6in}
	\ \ \fbox{\includegraphics[width=1.4in]{Newton}}
	\caption{Isaac~Newton (by G.~Kneller, c.~1689)}
\end{wrapfigure}
Newton's \emph{De Analysi} was written in 1669, but not published until 1711. Newton had not recognized the connection of his method with calculus. In 1740, {\href{http://www-history.mcs.st-andrews.ac.uk/Biographies/Simpson.html}{Thomas~Simpson}} (1710--1761) wrote \emph{A New Treatise of Fluxions} extending Newton's method to an iteration scheme for finding roots of differentiable functions---the form we now study. Simpson gave the formula for his generalization of Newton's method
\[	x_{n+1} = x_n - \frac{f(x_n)}{f^\prime(x_n)}	\]
shown in current calculus texts. (In fairness, Simpson learned the numerical integration technique we call ``Simpson's rule'' from Newton's writing.) Newton's method usually works and works quite well. Starting from a good initial value, every iteration with a `nice' function $f$ doubles the number of accurate decimals; we call this \emph{quadratic convergence}. Newton's method can fail by cycling among several values, wandering off to infinity, or finding a different root than intended. Using an appropriate value for $x_0,$ the initial estimate, is critical to success with Newton's method.


\subsection*{Modified Newton's Method}
Newton's method finds roots. We will investigate a modification of Newton's method to see what we can discover. Replace the fraction $f(x)/f^\prime(x)$ with $f^\prime(x)/f^{\prime\prime}(x)$ to obtain a new iteration formula
\[	x_{n+1} = x_n - \frac{f^\prime(x_n)}{f^{\prime\prime}(x_n)}.	\]
\begin{wrapfigure}{r}{1.6in}
	\rule{15pt}{0pt} \fbox{\includegraphics[width=1.in]{Simpson}}
	\caption{T.~Simpson}
\end{wrapfigure}
Write this expression as an iterating function
\[	M(x) = x - \frac{f^\prime(x)}{f^{\prime\prime}(x)}	\]
so that the sequence of $x_n$'s is generated by $x_{n+1}=M(x_n).$

It's time to experiment. We'll start with polynomials.
\subsubsection*{Polynomials}
\begin{enumerate}
\item Define the modified Newton's iterating function in Maple.
	\begin{itemize}
	\item[] \texttt{M := x -> x - dp(x)/ddp(x);}
	\end{itemize}
\clearpage
\item Use Maple to create a random polynomial $p(x)$  and find its derivative $dp.$ (\emph{Type exactly as shown!})
	\begin{itemize}
	\item[] \texttt{randomize(}{\it your phone number with no spaces} \texttt{):}
	\item[] \texttt{p := sort(randpoly(x, degree=(rand(4..6))(), coeffs=rand(-3..3))):}
	\item[] \texttt{p := unapply(p,x);}
	\item[] \texttt{dp := D(p);}
	\item[] \texttt{ddp := D(dp);}
	\end{itemize}

\item Graph $p$ in the initial window $[-5,5]\times[-5,5]$ to see its behavior. \mbox{Adjust the window as needed.}

\item Pick a value for $x_0.$ \quad\emph{Why should you not pick an inflection point?}

\item Generate a sequence $x_n$ using $x_{n+1}=M(x_n).$ \\
	We can use Maple to calculate the first 10 values for $x_n$ easily.
	\begin{itemize}
	\item[] \texttt{x[0] := } (\emph{your guess for $x_0$ as a decimal})\texttt{;}
	\item[] \texttt{for i from 0 to 9 do x[i+1] := M(x[i]) end do;}
	\end{itemize}
	
\item Pick a new value for $x_0.$ \emph{Do this at least 4 times for each polynomial.}
\item Generate a new sequence $x_n$ using $x_{n+1}=M(x_n).$

\item What feature(s) of the polynomial do the $x_n$ appear to find?
\end{enumerate}
Repeat the steps above with at least four different randomly generated polynomials. What do you conclude?

\subsubsection*{The Serpentine of Newton}
\begin{enumerate}
\item Compute your personal number $\alpha$ using Maple with
	\begin{itemize}
	\item[] \texttt{alpha := rand(3..9)();}
	\end{itemize}	

\item Investigate the result of applying our modified Newton's method to the \href{http://www.2dcurves.com/cubic/cubicse.html}{\emph{Serpentine of Newton}}
\[	S(x) = \frac{2\alpha x}{\alpha^2+x^2}	\]
using the technique above. Define the serpentine $S(x)$ and its derivatives (using \texttt{p} so we don't have to change \texttt{M}) by
	\begin{itemize}
	\item[] \texttt{p := x -> 2*alpha*x/(alpha\textasciicircum 2+x\textasciicircum 2)}
	\item[] \texttt{dp := D(p);}
	\item[] \texttt{ddp := D(dp);}
	\end{itemize}	
\end{enumerate}


\subsection*{Project Report}
Your project report should contain:
\begin{itemize}
\item Your and your partner's names at the top right of the first page.
\item A carefully-crafted, concise chronicle clarifying and connecting your conclusions.
\end{itemize}
Your project grade will be based on both the correctness of your results and your writing.

\end{document}
\end

