<html><head><meta name="color-scheme" content="light dark"></head><body><pre style="word-wrap: break-word; white-space: pre-wrap;">\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 11, 2025\\

\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:}
Consider the CG iteration from $x^{(0)}=0$ described by Algorithm~\ref{alg:CG}. Prove that as the iteration progresses $(r^{(k)})^Tr^{(j)} = 0$ for $j&lt;k,$ i.e., the residuals are orthogonal.

\begin{algorithm}
\caption{CG}
\label{alg:CG}
\begin{algorithmic}[1]
\State {\bf Input:} SPD $A$ and right hand side $b.$
\State {\bf Initialize} $x^{(0)} = 0,$ $r^{(0)} = b,$ $p^{(0)} = r^{(0)},$ and $k=1.$ 
\While{not converged}
  \State $\alpha_k = \frac{(r^{(k-1)})^Tr^{(k-1)}}{(p^{(k-1)})^TAp^{(k-1)})}$
  \State $x^{(k)} = x^{(k-1)} +\alpha_k p^{(k-1)}$
  \State $r^{(k)} = r^{(k-1)} - \alpha_k A p^{(k-1)}$
  \State $\beta_k = \frac{(r^{(k)})^Tr^{(k)}}{(r^{(k-1)})^Tr^{(k-1)}}$
  \State $p^{(k)} = r^{(k)}+\beta_k p^{(k-1)}$
  \State $k = k+1$
\EndWhile
\State {\bf return} $x^{(k)}$
\end{algorithmic}
\end{algorithm}

\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 &gt; 0$ such that $f(x^*+\alpha p) &gt; 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}</pre></body></html>