\documentclass[11pt,onecolumn]{article}
\usepackage{amssymb, amsmath, amsthm,graphicx, paralist,algpseudocode,algorithm,cancel,url,color}
\usepackage{sectsty}
\usepackage{fancyvrb}
\usepackage{mathrsfs}
\usepackage{multirow}
\usepackage{hhline}
\usepackage{booktabs}
\usepackage[table]{xcolor}
\usepackage{tikz}
% \usepackage[framed,numbered,autolinebreaks,useliterate]{mcode}
\usepackage{listings}
\usepackage{enumitem}
\newcommand{\bvec}[1]{\mathbf{#1}}
\newcommand{\R}{\mathbb{R}}
\newcommand{\calO}{\mathcal{O}}
\DeclareMathOperator{\Tr}{Tr}
\DeclareMathOperator{\trace}{trace}
\DeclareMathOperator{\diag}{diag}
\sectionfont{\Large\sc}
\subsectionfont{\sc}
\usepackage[margin=1 in]{geometry}
\begin{document}
\noindent
\textsc{\Large CS 4220 / MATH 4260: Homework 4}\\
Instructor: Anil Damle\\
Due: April 17, 2019\\
\subsection*{Policies}
You may discuss the homework problems freely with other students, but please
refrain from looking at their code or writeups (or sharing your own).
Ultimately, you must implement your own code and write up your own solution to
be turned in. Your solution, including plots and requested output from your code
should be typeset and submitted via the CMS as a pdf file. Additionally, please
submit any code written for the assignment via the CMS as well. This can be done
by either including it in your solution as an appendix, or uploading it as a zip
file via the CMS.\\
\hrule
\vspace{1cm}
\noindent
Note, this HW is shorter and focused on root finding since the second project (focused on optimization) will be available soon.
\subsection*{Question 1:}
Implement Newton's method and the Secant method. For each of the following use a sensible convergence criteria (describe it) and compute a root of the function. Illustrate the order of convergence (and the rate if linear) exhibited by the method and discuss if you observe what you expect.
\begin{enumerate}[label=(\alph*)]
\item $f(x) = x^2$
\item $f(x) = \sin{x} + x^3$
\item $f(x) = \sin{\frac{1}{x}}$ for $x\neq 0$
\end{enumerate}
\subsection*{Question 2:}
For any positive integer $p$ prove Newton's method used to find a root of $f(x) = x^p$ converges for any initial guess. Furthermore, give the analytic rate of convergence including constants (\emph{i.e.}, explicitly bound or express the error at the step $k+1$ in terms of the error at step $k$).
\subsection*{Question 3 (an interesting ungraded problem):}
Suppose we have a function $f:\mathbb{R}^n\rightarrow \mathbb{R}$ with a local minimizer $x^*$ such that for any direction $\delta x \in \mathbb{R}^n$ (say with $\|\delta x\|_2 = 1$) there exists an $\epsilon > 0$ such that $f(x^*+\alpha (\delta x)) > f(x^*)$ for all $\alpha \in (-\epsilon,\epsilon).$ Does this guarantee that $x^*$ is a strict local minimizer of $f(x)$? Why or why not?
\end{document}