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

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

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

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

%%------------------------------------------------------------------------------
%% 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}}}

\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}

\renewcommand{\Im}{\operatorname{Im}}
\renewcommand{\Re}{\operatorname{Re}}
\newcommand{\Id}{\operatorname{Id}}
\DeclareMathOperator{\Tr}{Tr}

\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 2 : Résolution de systèmes non linéaires}
\end{center}
\bigskip

%% \noindent%
%% \begin{center}%
%%   \begin{minipage}{0.8\textwidth}%
%%     \noindent\hrulefill
%%   \end{minipage}%
%% \end{center}

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

\ex (Dichotomie)
\begin{enumerate}
\item Programmer la méthode de dichotomie pour trouver votre nombre irrationnel préféré.
\item Afficher les résultats
\item Pour une erreur initiale inférieure à 1/2, combien faut-il d'itérations pour arriver à une erreur de $10^{-4}$ ?
  Comparer avec une méthode quadratique.
\end{enumerate}

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

\ex (Méthode de Héron)
Soit $a>0$. On cherche à approximer $\alpha = \sqrt a$.
Le but est de construire une suite de rectangles $(R_n)_n$ d'aire $a$ se rapprochant du carré de côté $\alpha$.
\begin{enumerate}
\item Partant de $x_0$ qui est une approximation grossière de $\alpha$, quelle est la longueur $y_0$ de l'autre côté du rectangle $R_0$ ?
\item On pose $x_1 = \frac{x_0 + y_0}{2}$, et on recommence... définir alors les suites récurrentes $(x_n)_n$ et $(y_n)_n$.
\item Cette méthode converge-t-elle ?
\item Reprendre la question précédente avec 
  \begin{equation*}
    x_{n+1} = -\frac{x_n^2}{a^2} + x_n + \frac 1 a.
  \end{equation*}
  Pour $a = 2$, montrer que si $x_0 \in [1,2]$, la méthode de point fixe converge.
\end{enumerate}

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

\ex Dans cet exercice, on va comparer la méthode de Newton et celle de la sécante appliquées aux fonctions
\[
f(x) = \cos(2x)^2 -x^2,\quad
g(x) = \frac{x \pare{63 x^{4}  - 70 x^{2}  + 15 }}{8},
\]
autour des zéros \(0.515...\) (pour \(f\)) et \(0.538...\) (pour \(g\)).
\begin{enumerate}
  \item Programmer la méthode de Newton.
  \item Programmer la méthode de la sécante.
  \item Programmer une méthode de visualisation de l'ordre de ces deux méthodes.
\end{enumerate}

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

\ex (Méthode de la sécante : ordre de convergence)
Soit $f$ une fonction de classe $C^2$ sur $\R$ et $\bar x$ un zéro simple de $f$.
Soit $I$ un voisinage de $\bar x$ tel que $|f'| \geq m >0$  sur $I$, 
et soient $M = \max_I |f''|$ et $J = \osbra{\bar x - \beta,\bar x + \beta}$, tel que $0 < \frac{2M}{m}\beta < 1$.
\begin{enumerate}
\item Montrer que si $(x_0,x_1) \in J^2$, la suite définie par :
  \begin{equation*}
    x_{n+1} = x_n - f(x_n) \frac{x_n - x_{n-1}}{f(x_n) - f(x_{n-1})}
  \end{equation*}
  converge vers $\bar x$ avec $|\bar x - x_{k+1}|\leq C |\bar x - x_{k}||\bar x - x_{k-1}|$.
\item Montrer de plus que l'ordre de la convergence est au moins $\frac{1 + \sqrt 5}{2}$.
\item Comment pourrait-on généraliser la méthode de la sécante en dimension supérieure à 1 ? (cela s'appelle en fait la méthode de Broyden)
\end{enumerate}

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

\ex (Convergence locale de la méthode de Newton)
On se place dans $\C$, dans le carré $[-1,1]^2$. On cherche à approximer les racines cubiques de l'unité par la méthode de Newton.
Quadrillez le carré suivant un petit pas de discrétisation et pour chaque case :
\begin{itemize}
\item Résolvez $z^3 = 1$ par la méthode de Newton en partant du centre de la case.
\item Coloriez la case dans une couleur différente suivant que la méthode converge vers 1, $j$ ou $\bar j$...
\item Que remarquez-vous ?
\end{itemize}

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

\ex 
Soit $a >0$. On cherche à calculer $1/a$.
\begin{enumerate}
\item Montrer qu'une méthode de Newton (pour une fonction auxiliaire bien choisie) peut s'écrire :
  \begin{equation*}
    x_0 \in \R, \ x_{n+1} = x_n(2 - a x_n).
  \end{equation*}
\item Trouver les $x_0$ tel que la suite $(x_n)$ converge vers $\frac{1}{a}$. 
\end{enumerate}

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

\ex (Racines d'un polynôme)
Soit $P$ un polynôme de degré $n\geq 2$ à coefficients réels admettant $n$ racines réelles distinctes $\zeta_n < \zeta_{n-1} < \dots < \zeta_1$.
Montrer qu'une méthode de Newton initialisée à $x_0 > x_1$ converge quadratiquement.

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

\ex (Recherche de vecteur propre)
Soit $A \in M_n(\R)$ une matrice symétrique possédant une valeur propre $\mu$.
Soit $v$ un vecteur propre associé à $\mu$ de norme $\norm v_2 = 1$.
\begin{enumerate}
\item Mettre le problème sous la forme $F(v,\mu) = 0$.
\item Calculer $\nabla F$. À quelle condition la méthode de Newton converge-t-elle localement quadratiquement ?
\end{enumerate}

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

\ex (Recherche de racine carrée de matrice)
Soit $A \in M_n(\C)$ une matrice inversible et $F : X\mapsto X^2 - A$ définie sur $M_n(\C)$.
\begin{enumerate}
\item Écrire l'algorithme de Newton pour $F$.
\item Soit $T$ une matrice triangulaire supérieure vérifiant :
  \begin{equation*}
    \forall j\neq k, \ T_{jj} + T_{kk} \neq 0.
  \end{equation*}
  Montrer que pour $C \in M_n(\C)$ donné, l'équation $TH + HT = C$ admet une unique solution.
  On montrera que le système obtenu est triangulaire sous réserve d'une bonne numérotation des $H_{ij}$, $i,j \in \dbra{1, n}$.
\item Supposons (ou exercice, montrez-le) que $A$ admette une racine carrée $B$ vérifiant :
  \begin{equation*}
    \forall j\neq k, \ B_{jj} + B_{kk} \neq 0. 
  \end{equation*}
  Montrer alors que l'algorithme de Newton converge localement autour de $B$.
\item Comment mettriez-vous en place pratiquement un tel algorithme ? 
\end{enumerate}

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

\ex (Accélération d'Aitken)
Soit $(u_n)_n$ une suite réelle convergent vers $l$ vérifiant :
\begin{equation*}
  \forall n\in \N, l \neq u_n \neq u_{n-1}, \text{ et }\lim_{n\to +\infty} \frac{u_n - l}{u_{n-1} - l} = \lambda \in \osbra{-1,1}\backslash \{0\}.
\end{equation*}
On cherche à améliorer la convergence de $u_n$.
\begin{enumerate}
\item Montrer que $\lambda_n$ définie par
  \begin{equation*}
    \forall n\in \N, \ \lambda_n = \frac{u_{n+1} - u_n}{u_{n} - u_{n-1}}
  \end{equation*}
  converge vers $\lambda$.
\item Montrer que la suite $(v_n)_n$ définie par :
  \begin{equation*}
    \forall n \text{ assez grand, } v_n = \frac{u_{n+1} - \lambda_n u_n}{1 - \lambda_n}
  \end{equation*}
  vérifie $\lim_{n \to +\infty} \frac{v_n - l }{u_n - l} = 0$. Conclure.
\item Pourquoi cette méthode s'appelle-t-elle $\Delta^2$ (on réécrira $v_n$ sous forme de différences de $u_n$) ?
\end{enumerate}
Cette méthode est due à Aitken (1926). 
\begin{enumerate}[resume]
\item Décrire la suite d'Aitken d'une suite arithmético-géométrique.
\item Soit $f : [a,b]\rightarrow[a,b]$ de classe $C^2$ vérifiant $\norm{f'}_{\infty} < 1$. 
  $f$ a alors un unique point fixe (pourquoi ?) $l$.
  Si on suppose $f'(l) \neq 0$, la convergence de la méthode de point fixe est linéaire de rapport $|f'(l)|$.
  
  Montrer que si $f''(l)\neq 0$, alors la suite accélérée d'Aitken converge aussi linéairement mais de rapport $f'(l)^2$.
  \emph{Indication : }En notant $e_n = u_n - l$, on montrera en particulier que 
  \begin{equation*}
    v_n - l = \frac{f'(l) f''(l) + o(1)}{2(f'(l) - 1) + +o(1)}e_{n-1}^2
  \end{equation*}
\end{enumerate}
\emph{Remarque : }Il existe bien sûr d'autres méthodes d'accélération. On pourra regarder les méthodes de Steffensen ou Richardson.

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

\ex (Méthode des approximations successives de Picard)
\begin{enumerate}
\item Coder une routine qui, à partir d'un vecteur de valeurs d'une fonction \((f(i/n))_{i\in\dbra{0,n}}\), renvoit la valeur approchée de l'intégrale de \(f\) sur \([0,1]\), en pensant par exemple à l'intégration de Riemann.
\item Implémenter la méthode de Picard pour résoudre le problème de Cauchy
  \[
  \left\{
  \begin{aligned}
    y' &= \cos(y) &&\text{pour }x\in(0,1)\\
    y(0) &= 0 &&
  \end{aligned}\right.
  \]
  et comparer les itérations successives avec la solution explicite, \(y(x)= 2\arctan(\tanh(x/2))\).
\end{enumerate}

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

