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

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

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

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

\usepackage{algorithm}
\usepackage{algpseudocode}

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

% algpseudocode

\algrenewcommand{\algorithmicrequire}{\textbf{Entrée :}}
\algrenewcommand{\algorithmicensure}{\textbf{Sortie :}}
\algrenewcommand{\algorithmicreturn}{\textbf{renvoyer}}
\algrenewcommand{\algorithmicend}{\textbf{fin}}
\algrenewcommand{\algorithmicif}{\textbf{si}}
\algrenewcommand{\algorithmicthen}{\textbf{alors}}
\algrenewcommand{\algorithmicelse}{\textbf{sinon}}
\algrenewcommand{\algorithmicfor}{\textbf{pour}}
\algrenewcommand{\algorithmicforall}{\textbf{pour tout}}
\algrenewcommand{\algorithmicdo}{\textbf{faire}}
\algrenewcommand{\algorithmicwhile}{\textbf{tant que}}
\algrenewcommand{\algorithmicfunction}{\textbf{fonction}}

% fancyhdr
\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

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

\theoremstyle{definition}
\newtheorem*{defi}{Définition}
%% \newtheorem{qstn}{}
%% \newtheorem{subqstn}{}[qstn]

%% 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{\Tr}{Tr}
\DeclareMathOperator{\cond}{cond}
\renewcommand{\sp}{\operatorname{sp}}

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

\newtheorem*{thrm}{Théorème}

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

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

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

\begin{center}
  {\Large \bf Méthode de Newton \(\bm n\)-dimensionnelle}
\end{center}
\bigskip

La méthode de Newton en dimension 1 se généralise naturellement en dimension \(n\). Soit \(U\subset \R^n\) un ouvert, et \(F\in\mc C^2(U, \R^n)\).
L'algorithme de Newton s'écrit alors
\begin{algorithmic}[1]
  \leftskip4em
  \rightskip\leftskip
  \Require \(F, dF, x_0, \eps\)
  \State $k \gets 0,\,\eps_0 = 1 $
  \While{$\eps_k>\eps$}
  \State \(x_{k+1} = x_k - (dF(x_k))^{-1}F(x_k)\)
  \State \( \eps_{k+1} = \abs {x_{k+1}-x_k}\)
  \State \( k \gets k+1 \)
  \EndWhile
  \State \Return $x_k$
\end{algorithmic}
Sa convergence (et sa bonne définition) est assurée par le théorème suivant :
\begin{thrm}
  Si \(F\) est de classe \(\mc C^2\), s'annule en \(x\in U\), et \(dF(x)\) est inversible, alors il existe \(\delta >0\) tel que la méthode de Newton est bien définie pour tout \(x_0\in B(x,\delta)\), converge localement vers \(x\), et est d'ordre au moins 2.
\end{thrm}
\begin{proof}
  D'une part, notons que \(y\mapsto \det(dF(y))\) est continue, et donc \(dF(y)\) est inversible pour tout \(y\) dans un voisinage de \(x\). De plus, \(y\mapsto \norm{(dF(y))^{-1}}\) est continue sur son ensemble de définition, car
  \[
  (dF(y))^{-1}= \frac{\operatorname{Com}(dF(y))^T}{\det(dF(y))},
  \]
  et donc il existe \(\delta>0\) tel que \(\forall y\in B(x,\delta)\), 
  \begin{enumerate}[label=(\roman*)]
  \item \(dF(y)\) est inversible,
  \item \(\norm{(dF(y))^{-1}} \leq 2\norm{(dF(x))^{-1}}\).
  \end{enumerate}

  D'autre part, en utilisant la formule de Taylor appliquée à \(f(t)=F(tx+(1-t)y\), on obtient
  \begin{align*}
    0 = F(x)= f(1) &= f(0) + f'(0) + \int_0^1 (1-t)f''(t)dt \\
    &= F(y) + dF(y)(x-y) + \int_0^1 (1-t)d^2F(tx+(1-t)y)(x-y,x-y)dt,
  \end{align*}
  et donc
  \[
  \norm{F(y) + dF(y)(x-y)} \leq \frac{\norm{d^2F}_\infty}{2}\norm{x-y}^2,
  \]
  où \(\norm{d^2F}_\infty=\sup_{\xi\in B(x,\delta)} \norm{d^2F(\xi)}.\)

  Finalement, il vient, en posant \(\tilde y = y - (dF(y))^{-1}F(y)\), qui est bien défini si \(y\in B(x,\delta)\),
  \begin{align*}
    \norm{x-\tilde y} &= \norm{ x-y + (dF(y))^{-1}F(y)} \\
    &= \norm{(dF(y))^{-1}(dF(y)(x-y) + F(y)}\\
    &\leq \norm{(dF(y))^{-1}} \norm{ dF(y)(x-y) + F(y)} \\
    &\leq C \norm{x-y}^2,
  \end{align*}
  avec \(C=\norm{ (dF(x))^{-1} } \norm{d^2F}_\infty\).

  Quitte à remplacer \(\delta\) par \(\min(\delta,1/C)\), on peut supposer que \( \delta\leq 1/C \). Dans ce cas, si \(y\in B(x,\delta)\), alors \(\norm{x-\tilde y}< C\delta^2\leq \delta\), ce qui prouve la bonne définition de la méthode, et que son ordre est au moins~2. Par ailleurs, la convergence est immédiate en remarquant que
  \begin{align*}
    \norm{x_k-x} &\leq C \norm{x_{k-1}-x}^2 \leq C^{1+2}\norm{x_{k-2}-x}^4\leq \dots\\
    &\leq \frac{1}{C}(C\norm{x_0-x})^{2^k}.
  \end{align*}
\end{proof}

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