\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{\C}{\mathbb{C}}
\newcommand{\Rn}{\R^{n\times n}}
\newcommand{\Rmn}{\R^{m\times n}}
\newcommand{\Cn}{\C^{n\times n}}
\newcommand{\Cmn}{\C^{m\times n}}
\newcommand{\cO}{\mathcal{O}}
\DeclareMathOperator{\Tr}{Tr}
\DeclareMathOperator{\trace}{trace}
\DeclareMathOperator{\diag}{diag}
\DeclareMathOperator{\vspan}{span}
\sectionfont{\Large\sc}
\subsectionfont{\sc}
\usepackage[margin=1 in]{geometry}
\begin{document}
\noindent
\textsc{\Large Numerical analysis: Homework 4}\\
Instructor: Anil Damle\\
Due: April 12, 2024\\

\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 Gradescope as a pdf file. This file must be self contained for grading. Additionally, please
submit any code written for the assignment as zip
file to the separate Gradescope assignment for code.\\
\hrule
\vspace{1cm}
\noindent

\subsection*{Question 1:}
Implement Newton's method for root finding. For each of the following compute a root of the function and illustrate the order of convergence (i.e., $q$ if $\lvert e_{k+1}\rvert = \rho \lvert e_{k}\rvert^q$, where $e_k = x^*-x_k$) and, if linear, the rate (i.e., $\rho$ if $\lvert e_{k+1}\rvert = \rho \lvert e_{k}\rvert$) exhibited by the method. 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:}
Show that given any initial guess the Jacobi method for solving $Ax=b $converges for any strictly diagonally dominant matrix $A$ (i.e., $\lvert a_{ii} \rvert > \sum_{j\neq i} \lvert a_{ij} \rvert$ for $i=1,\ldots,n$). 

You may find the following (restricted) version of the Gershgorin circle theorem useful for this question: Given a matrix $A,$ each of its eigenvalues lies within at least one of the discs $\{z\in\mathbb{C}\mid\lvert z - a_{ii} \rvert < R_i\}$ for $i=1,\ldots,n$, where $R_i = \sum_{j\neq i} \lvert a_{ij} \rvert.$ In other words, all of the eigenvalues of $A$ lie within the union of a set of discs centered around the diagonal entries of $A,$ each of whose radius is the sum of the magnitudes of the off diagonal entries in that row.  

\subsection*{Question 3:}
Prove that if $\nabla f(x) = 0$ but the Hessian $\nabla^2f(x)$ is indefinite (i.e., has positive and negative eigenvalues), then there is a direction we can move from $x$ that decreases the function value provided we take a small enough step. (I.e., show that $x$ is not a local minimizer and that we can make progress when running an optimization scheme using so-called directions of negative curvature.)

\subsection*{Question 4 (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 $p \in \mathbb{R}^n$ (say with $\|p\|_2 = 1$) there exists an $\epsilon > 0$ such that $f(x^*+\alpha p) > 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}