\documentclass[12pt, letterpaper]{article}

\usepackage{graphicx}
\usepackage{epsfig}
\usepackage{amssymb}
\usepackage{geometry}
\usepackage{setspace}

\title{Homework 4}
\author{Menyoung Lee}
\geometry{margin=1in}
%\doublespacing

\begin{document}
\maketitle

\subsection*{1.3 P7}
\[W(x) = \prod_{k=1}^{20} (x-k)\]
By the product rule,
\[W'(x) = \sum_{k=1}^{20} \frac{W(x)}{x-k}\]
\ldots which seems like it {\it should} be zero because $W(16) = 0$.
However, one of the terms of summation, $\frac{W(x)}{x-16}$ does have a limit at $x=16$ by cancellation.
This limit, which therefore is the desired $W'(x)$ by definition, equals \[\prod_{k=1}^{15} (16-k) \prod_{k=17}^{20} (16-k) = 15! \times (-1)(-2)(-3)(-4) = 15!4!\]
Similarly for $j \in {\mathbb Z}, 1 \leq j \leq 20$,
\[W'(j) = \prod_{k=1}^{j-1} (j-k) \prod_{k=j+1}^{20} (j-k) = (j-1)! \times (20-j)! \times (-1)^j\]
\subsubsection*{Why is this bad?}
This is bad because by having $f'(r)$ be really really big,
we get a ridiculously large backward-error.
The smallest difference in x from a root would produce a catastrophically non-zero $f(x)$.
This is also bad because for Newton's method, $g(x) = x - \frac{f(x)}{f'(x)}$,
near the roots $f(x)$ is by definition near zero, while $f'(x)$ is really big,
so it breaks Newton in the sense that is will go extremely slowly.

\subsection*{1.3 CP6}
With the normal $w(x)$,
\[w(x) = x^{20} - 210x^{19} + 20615x^{18} - 1256850x^{17} + 53327946x^{16} - 1672280820x^{15}\]
\[+ 40171771630x^{14} - 756111184500x^{13} + 11310276995381x^{12}\]
\[- 135585182899530x^{11} + 1307535010540395x^{10} - 10142299865511450x^9\]
\[+ 63030812099294896x^8 - 311333643161390640x^7 + 1206647803780373360x^6\] 
\[- 3599979517947607200x^5 + 8037811822645051776x^4 - 12870931245150988800x^3\]
\[+ 13803759753640704000x^2 - 8752948036761600000x + 2432902008176640000\]
\begin{verbatim}
>> fzero(@w, 15)

ans =

  14.99454333072242
\end{verbatim}
With the adustment to the $x^{15}$ term,
\[w(x) = x^{20} - 210x^{19} + 20615x^{18} - 1256850x^{17} + 53327946x^{16}\]
\[- 1.000000000000002\times1672280820x^{15} + 40171771630x^{14} - 756111184500x^{13}\]
\[+ 11310276995381x^{12} - 135585182899530x^{11} + 1307535010540395x^{10} - 10142299865511450x^9\]
\[+ 63030812099294896x^8 - 311333643161390640x^7 + 1206647803780373360x^6\] 
\[- 3599979517947607200x^5 + 8037811822645051776x^4 - 12870931245150988800x^3\]
\[+ 13803759753640704000x^2 - 8752948036761600000x + 2432902008176640000\]
\begin{verbatim}
>> fzero(@w1, 15)

ans =

  14.86480357685579
\end{verbatim}
By theory,
\[\epsilon = 2\times10^{-15}, g(x) = -1672280820x^{15} \rightarrow g(r) = -7.322815540790937 \times 10^{26}\]
\[\Delta r \approx -\frac{\epsilon g(r)}{f'(r)} = -\frac{2\times10^{-15}\cdot -7.322815540790937\times10^{26}}{14!5!} = -0.13999692354586\]
Numerically in MATLAB,
\[\Delta r = 14.86480357685579 - 14.99454333072242 = -0.12973975386663\]
Close enough, considering that $\Delta r$ is pretty large, having -1 magnitude.
\end{document}