%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\documentclass[a4paper, 10pt]{article}
\usepackage[T1]{fontenc}
\usepackage[utf8]{inputenc}

\title{}
\author{}
\date{}

%%------------------------------------------------------------------------------
%% Packages

\usepackage[]{geometry}
\usepackage{amsmath,amsfonts,amsthm}
\usepackage[matha,mathb]{mathabx} % french mathematical symbols and more
\usepackage[svgnames]{xcolor}
\usepackage{fancyhdr}
\usepackage{hyperref}
\usepackage{mathtools}
\usepackage{lastpage}

\usepackage[french]{babel}

%%------------------------------------------------------------------------------
%% Packages setup

% geometry
\geometry{textwidth = 0.75\paperwidth,
  textheight = 0.75\paperheight}
%defaults : textwidth = 0.7\paperwidth = 1675.8pt, textheight = 0.7\paperheight = 4788pt

% hyperref
\hypersetup{colorlinks=true,
  citecolor=DarkBlue,
  linkcolor=DarkBlue,
  linktoc=page,
  urlcolor=black}

% fancyhdr
%% BUG: Do not issue \fancypagestyle{fancy}{<fancyhdr commands>}, the LaTeX compiler will hang at the first \pagestyle{fancy} call since it will enter in an infinite recursive loop.

%% \fancypagestyle{fancy}{%
%%   \fancyhf{} % clear all header and footer fields
%%   \lhead{École Normale Supérieure de Lyon\\Département de mathématiques}
%%   \rhead{2021--2022\\Option B pour l'agrégation}
%%   \rfoot{\thepage /\pageref{LastPage}}
%%   \renewcommand{\footrulewidth}{0.5pt}
%%   \setlength{\headheight}{24.2pt}} % required for headers spanning two lines

\fancypagestyle{plain}{%
  \fancyhf{}
  \rfoot{\thepage /\pageref{LastPage}}
  \renewcommand{\headrulewidth}{0pt}}

\pagestyle{fancy} % sets page style for the whole document
\fancyhf{} % clear all header and footer fields
\lhead{École Normale Supérieure de Lyon\\Département de mathématiques}
\rhead{2021--2022\\Option B pour l'agrégation}
\rfoot{\thepage /\pageref{LastPage}}
\renewcommand{\footrulewidth}{0.5pt}
\setlength{\headheight}{24.2pt} % required for headers spanning two lines


%%------------------------------------------------------------------------------
%% Custom environments/macros

\theoremstyle{definition}
\newtheorem*{defi}{Définition}

%% correction stuff
%\newcommand{\correc}[1]{}
%\renewcommand{\correc}[1]{#1}  % comment out to remove corrections
% do not forget to compile twice to get page numbering right

\newtheorem*{solution}{Solution}
\newcommand{\sol}[1]{%
  \correc{\begin{solution}
      #1 \end{solution}}}

%\renewcommand{\thesection}{\Alph{section}}

\newcommand{\R}{\mathbb{R}}
\newcommand{\C}{\mathbb{C}}
\newcommand{\Z}{\mathbb{Z}}
\newcommand{\Q}{\mathbb{Q}}
\newcommand{\N}{\mathbb{N}}
\newcommand{\Sph}{\mathbb{S}}
\newcommand{\mc}{\mathcal}
\newcommand{\eps}{\varepsilon}

\renewcommand{\Im}{\operatorname{Im}}
\renewcommand{\Re}{\operatorname{Re}}
\newcommand{\Id}{\operatorname{Id}}
\DeclareMathOperator{\argmin}{arg\,min}
\DeclareMathOperator{\Tr}{Tr}

\newcommand{\fonction}[5]{%
  \begin{array}[t]{lrcl}
    #1 :&#2 &\longrightarrow &\displaystyle #3\\
    &#4& \longmapsto &\displaystyle #5
  \end{array}
}


\newcommand{\dbra}[1]{\ldbrack #1 \rdbrack}
\DeclarePairedDelimiter{\norm}{\lVert}{\rVert} %% requires mathtools
\DeclarePairedDelimiter{\abs}{\lvert}{\rvert}
\DeclarePairedDelimiter{\sbra}{[}{]}
\DeclarePairedDelimiter{\pare}{(}{)}
\DeclarePairedDelimiter{\osbral}{]}{]}
\DeclarePairedDelimiter{\osbra}{]}{[}
\DeclarePairedDelimiter{\osbrar}{[}{[}

% Exercices numbering and more 
\newcounter{exercice}
\newcounter{question}[section]
\newcounter{subquestion}[question]

\newcommand{\qstn}{\stepcounter{question}\paragraph{\thequestion.}~}
\newcommand{\sqstn}{\stepcounter{subquestion}\paragraph{\thequestion.\thesubquestion.}~}
\newcommand{\ex}{\refstepcounter{exercice}\paragraph{Exercice \theexercice.}}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{document}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%


\begin{center}
  {\Large \bf TD 3 : Interpolation et approximation polynômiale}
\end{center}
\bigskip

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\section*{Interpolation}

\ex (Algorithme des différences divisées)
Construire une fonction qui prend en entrée une fonction, un entier $n$ et un intervalle $[a,b]$ et qui renvoit les différences divisées de $f$ associée à la subdivision uniforme à $n+1$ points sur $[a,b]$.
\emph{Attention :} on fera attention à bien gérer la mémoire.
Comment cette fonction se transpose-t-elle dans le cas non uniforme ?

%%%%%%%%%%%%%%%%%%%%

\ex
Construire une fonction prenant en entrée un entier $n$, une fonction $f$ un intervalle $[a,b]$, et qui renvoit le polynôme d'interpolation de Lagrange de $f$ associé à la subdivision uniforme à $n+1$ points de $[a,b]$.  
On pourra utiliser un algorithme de Horner qui construit la suite des coefficients du polynôme à partir de son écriture via les différences divisées.
  
Tester l'interpolation de Lagrange sur la fonction exponentielle. La tester ensuite sur
\[
\fonction{f}{[-1,1]}{\R}{x}{\frac{1}{1+25x^2}.}
\]
Que remarque-t-on ?

%%%%%%%%%%%%%%%%%%%%

\ex (Optimalité du résultat de convergence)
\begin{enumerate}
\item On se replace dans le cas d'une subdivision uniforme $ x_i = a+i\frac{b-a}{n} = a+ih$. 
  On note $\pi_{n+1}(x) = \prod_{i = 0}^n(x-x_i)$ et $\varphi(s) = |s(s-1)\cdots (s-n)|$.
  \begin{enumerate}
  \item On rappelle la formule de Stirling : \(n!\sim \sqrt{2\pi n}(n/e)^n\) lorsque \(n\to+\infty\). Montrer qu'à partir d'un certain rang,
    \[
    \varphi\left(\frac 1 2 \right) \geq \frac{1}{2\sqrt 2}\pare*{\frac{n}{e}}^n.
    \]
  \item En déduire que $\norm{\pi_{n+1}}_\infty \geq \frac{1}{n\sqrt 8}\left(\frac{b-a}{e} \right)^{n+1}$ à partir d'un certain rang.
  \end{enumerate}
\item On cherche à réduire l'erreur dans l'approximation uniforme de l'interpolation en minimisant $\norm{\pi_{n+1}}_\infty$. On définit ainsi les points de \emph{Tchebychev} :
  on considère la suite de polynômes $T_n$ définie par $T_0 = 1$, $T_1 = X$ et pour tout $n\geq 1$, 
  \begin{equation*}
    T_{n+1} = 2XT_n - T_{n-1}.
  \end{equation*}
  \begin{enumerate}
  \item Établir le degré ainsi que le coefficient dominant de \(T_n\), et montrer que pour tout $n\in\N$, $T_n(x) = \cos(n \arccos(x)).$
  \item Déterminer les racines de $T_n$ (que l'on notera $(\lambda_k^n)_{0\leq k\leq n}$).
  \item Montrer que \(X^{n} - 2^{-n}T_n\) est la meilleure approximation uniforme de \(X^{n}\) d'ordre \(n\). En d'autres termes,
    \[
    2^{-n}T_n = \argmin \{\norm{\pi}_\infty, \pi\in\R^n[X]\text{ unitaire}\}.
    \]
    (\emph{Rappel :} \(p\in\R_n[X]\) est la meilleure approximation uniforme d'ordre \(n\) de \(f\) si, et seulement si, \(f-p\) équioscille sur au moins \(n+2\) points.)
  \item On définit alors la subdivision à $n+1$ points :
    \begin{equation*}
      x_i = \frac{a+b}{2} + \frac{b-a}{2} \lambda^{n+1}_i.
    \end{equation*}
    Pour ce choix de \(x_i\), expliciter le polynôme \(\pi_{n+1}\) correspondant en fonction de \(T_{n+1}\), et montrer qu'alors 
    \begin{equation*}
      \norm{\pi_{n+1}}_\infty = 2\left(\frac{b-a}{4}\right)^{n+1}.
    \end{equation*}
  \end{enumerate}
\item Programmer une méthode d'interpolation complète aux points de Tchebychev (avec l'algorithme de différences divisées), et la comparer avec celle pour des points équirépartis et pour la fonction \(f\) de l'exercice précédent.
\end{enumerate}
 
%%%%%%%%%%%%%%%%%%%%

\section*{Approximation}

%%%%%%%%%%%%%%%%%%%%

\ex (Les polynômes de Bernstein - convergence en norme $L^\infty$)
Construire une fonction qui prend en entrée une fonction $f$ définie sur $[0,1]$ et un entier $n$, et renvoit son $n$ième polynôme de Bernstein \(B_n(f) = \sum_{k=0}^n C^k_nf(k/n)X^k(1-X)^{n-k}\).
Illustrer graphiquement la convergence de \(B_n(f)\) vers \(f\).

%%%%%%%%%%%%%%%%%%%%

\ex
\begin{enumerate}
\item On va construire un jeu de données modélisant une fonction "cosinus bruitée"
  \begin{enumerate}
  \item Construire une suite de 50 points $(x_i)_{1\leq i \leq 50}$ de $[0,1]$ générés aléatoirement et rangés dans l'ordre croissant.
    (On pourra utiliser la fonction \texttt{rand} de \texttt{numpy.random} et une fonction de tri built-in.)
  \item Construire une suite de points $(y_i)_{1\leq i \leq 50}$ définis par $y_i = \cos(x_i) + \eps_i$, avec $\eps_i$ un bruit aléatoire donné par une gaussienne centrée de variance 0.01.
  \item Tracez l'ensemble des points $(x_i,y_i)$ ainsi que la fonction cosinus sur $[0,1]$.
  \end{enumerate}
\item Construire une fonction qui prenne en entrée un entier $p$ et le jeu de données $(x_i,y_i)$
  et qui renvoie le polynôme de degré $p$ de meilleure approximation au sens des moindres carrés de ce jeu de données, i.e. 
  \begin{equation*}
    P_{bruit} = \argmin_{P \in \mathcal P_p} \sum_{i=1}^{50}|y_i - P(x_i)|^2. 
  \end{equation*}
  Tracer ce polynôme pour différents (petits) degrés. On pourra utiliser des solveurs linéaires built-in de \texttt{numpy}.
\item Refaire la question précédente avec le jeu de donnée modifié avec $y_1 = -1$.
  Cela modifie-t-il drastiquement le polynôme de meilleure approximation ?
\item Que retrouve-t-on comme polynôme dans le cas où le degré $p$ et le nombre de points $n$ vérifient $p = n-1$ ?
\item Comparer le polynôme d'approximation trouvé sur la solution bruitée avec celui de même degré donné par
  l'approximation continue au sens des moindres carrés de la fonction non bruitée, i.e.
  \begin{equation*}
    P_{exact} = \argmin_{P \in \mathcal P_p} \int_{0}^1 |\cos(t) - P(t)|^2 \mathrm dt. 
  \end{equation*}
\item Refaire l'exercice  avec la fonction :
  \begin{equation*}
    \fonction{f}{[0,1]}{\R}{x}
             {
               \begin{cases}
                 \cos(x) &\text{ si } x\leq 0.5 \\
                 \cos(x) +2 &\text{ sinon }
               \end{cases}
             }
  \end{equation*}
\end{enumerate}

%%%%%%%%%%%%%%%%%%%%

\ex (Le cas de la régression linéaire)
On se donne une série statistique $(x_i,y_i)_{1\leq i \leq n}$ et deux réels $a$ et $b$ qui minimisent le résidu :
$R = \sum_{i=1}^n |y_i - ax_i - b|^2$.
\begin{enumerate}
\item Écrire $u = \begin{pmatrix} a \\ b \end{pmatrix}$ comme solution du système linéaire 
  \begin{equation*}
    B^T B u = B^T y
  \end{equation*}
  où l'on explicitera $B$, $B^TB$ et $B^T y$.
\item En déduire des formules explicites pour $a$ et $b$ en fonction des $x_i$ et des $y_i$.
\item Interpréter $a$ en terme de variance et de covariance de la série statistique.
\end{enumerate}
  

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\end{document}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
