\documentclass[t,aspectratio=169]{beamer}
\usetheme{metropolis}
\metroset{block=fill}

\input{../../_assets/basicslide1}
\input{../../_assets/macros}

\author{Samuel Vaiter}
\date{}
\institute{
Created: 2023-11-10.\\
Last update: 2023-11-10.\\
Status: inprogress.
}
\title{Finite differences}

\begin{document}

\begin{frame}
  \maketitle
\end{frame}

\begin{frame}[fragile]
  \frametitle{Finite differences}

  For $f: \RR \to \RR$ and $\epsilon > 0$ small enough,
  \[ f'(x) \approx \frac{f(x + \epsilon) - f(x)}{\epsilon} \eqdef \Delta_{\epsilon} f(x) . \]

  \begin{proposition}
    Let $f: \RR \to \RR$ a $C^{2}$ function around $\bar x$.
    Then, there exists $C > 0$ such that for $\epsilon > 0$ small enough, one has
    \[
      \left|
        \frac{f(\bar x + \epsilon) - f(\bar x)}{\epsilon} - f'(\bar x)
      \right|
      \leq C \epsilon \quad \text{\alert{($O(\epsilon)$ approximation error)}}.
    \]
  \end{proposition}

  Simple to implement
  \footnotesize
\begin{verbatim}
def diff(f, x, eps=1e-5):
    return (f(x + eps) - f(x)) / eps
\end{verbatim}
\end{frame}

\begin{frame}
  \frametitle{\emph{Shortcoming 1:} round-off and truncation}
  \begin{center}
    \begin{tikzpicture}
     \node (img) at (0,0){\includegraphics[clip, width=0.8\linewidth]{figures/finite_differences.pdf}};
     % \node[below=1pt of img] {$\epsilon$};
     \node[rotate=90, left=3pt of img, anchor=center] {$\abs{\Delta_\epsilon f(x) - f'(x)}$};
     \node[font={\Large},orange] (rerror) at (-2.8,2.8) {round-off error};
     \node[font={\Large},blue] (terror) at (3,2.8) {truncation error};
    \end{tikzpicture}
  \end{center}
\end{frame}

\begin{frame}
  \frametitle{\emph{Shortcoming 2:} linear complexity w.r.t dimensions}

  $f: \RR^{\color{red}n} \to \RR$

  \begin{center}\color{blue}2 ca\tikzmarknode{sumcall}{}lls\end{center}
  \[
    \nabla f(x) \approx 
    \left.
    \begin{pmatrix}
      \displaystyle\frac{\tikzmarknode{call1}{f(x + \epsilon \mathbf{e}_1)} - \tikzmarknode{call2}{f(x)}}{\epsilon} \\
      \vdots \\
      \displaystyle\frac{f(x + \epsilon \mathbf{e}_{\color{red}n}) - f(x)}{\epsilon}
    \end{pmatrix}
    \right\}
    \text{\color{red}$n$ elements}
  \]
  \alert{Linear} cost:
  \[
    \text{Cost}(\nabla f) = {\color{blue}2}{\color{red}n} \cdot \text{Cost}(f)
  \]

  \begin{tikzpicture}[overlay,remember picture]
    \draw[blue,-latex] (sumcall) -- (call1);
    \draw[blue,-latex] (sumcall) -- (call2);
  \end{tikzpicture}
\end{frame}

\end{document}