%! TEX root=cours.tex
\documentclass{article}
\usepackage{cancel}
\usepackage{amsmath, amssymb, amsfonts}
\usepackage{stmaryrd}
\usepackage{import}
\usepackage{pdfpages}
\usepackage{transparent}
\usepackage{xcolor}
% \usepackage{tikz}
\newcommand{\mult}{\operatorname{mult}} 
\newcommand{\img}{\operatorname{Im}} 
\newcommand{\trivial}{$\mathbb{TRIVIAL}$} 
\newcommand{\Sp}{\operatorname{Sp}} 
\newcommand{\image}{\operatorname{im}} 
\newcommand{\rg}{\operatorname{rg}} 
\renewcommand{\dim}{\operatorname{dim}} 
\newcommand{\cM}{\mathcal{M}}
\newcommand{\cP}{\mathcal{P}}
\newcommand{\cT}{\mathcal{T}}
\newcommand{\cF}{\mathcal{F}}
\newcommand{\cO}{\mathcal{O}}
\newcommand{\cE}{\mathcal{E}}
\newcommand{\R}{\mathbb{R}}
\newcommand{\Q}{\mathbb{Q}}
\newcommand{\C}{\mathbb{C}}
\newcommand{\K}{\mathbb{K}}
\newcommand{\N}{\mathbb{N}}
\newcommand{\Z}{\mathbb{Z}}
\newcommand{\dx}{\mathrm{d}x}
\newcommand{\dy}{\mathrm{d}y}
\newcommand{\dz}{\mathrm{d}z}
\newcommand{\dt}{\mathrm{d}t}
\newcommand{\df}{\mathrm{d}f}
\renewcommand{\epsilon}{\varepsilon}


\newenvironment{theorem}[1][\unskip]{
	\paragraph{Théorème #1}

}{}

\newenvironment{remarque}{
	\paragraph{Remarque}
}{}

\newenvironment{corollary}[1][\unskip]{
	\paragraph{Corollaire #1}

}{}

\newenvironment{lemma}[1][\unskip]{
	\paragraph{Lemme #1}

}{}

\newenvironment{proposition}[1][\unskip]{
	\paragraph{Proposition #1}

}{}

\newenvironment{proof}[1][\unskip]{
	\def\temp{#1}\ifx\temp\empty
		\paragraph{Preuve}
	\else
		\paragraph{Preuve \emph{(#1)}}
	\fi

}{}

\newenvironment{definition}[1][\unskip]{
	\paragraph{Définition: #1}

}{}

\begin{document}
\section{Rappels d'algèbre linéaire}

\begin{description}
	\item[Matrice de permutation] \begin{align*}
		P_\sigma := \left(\sum_{j=1}^{n} E_{\sigma(i),j}\right)_i
	\end{align*} avec $E_{i, j}$ la matrice élémentaire $(i, j)$.
\end{description}

\begin{theorem}[de Schur]
	$\forall  A \in \cM_n(\C), \exists U \in \cM_n(\C), \underbrace{U^\ast = U^{-1}}_{\text{unitaire}} \land U^\ast AU \in \cT_{n, s}(\C)$
\end{theorem}

\subsection{Méthodes itératives}

\paragraph{Principe}

On cherche une suite $x^{(p)}$ de $\R^{n}$ convergeant vers la solution de $Ax = b$:

\begin{align*}
	\forall x^{(0)}\quad x^{(p+1)} = H(x^{(p)})
\end{align*}

\paragraph{Propriétés}

\begin{itemize}
	\item $A$ n'est jamais modifiée
	\item Problème du suivi de la convergence et du choix du test d'arrêt
	\item Solution obtenue inexacte
	\item Matrice doit vérifier conditions de convergence
	\item Vitesse de convergence dépend de la matrice
\end{itemize}

\section{Décomposition en valeurs singulières}

\paragraph{Objectif}
Soit $A \in \cM_{n}(\R)$, $n \ge 1$.

On pose $
	A = U \Sigma V^\top
$  avec $\begin{cases}
U \in \cO_n(\R) \\
V \in \cO_n(\R) \\
\Sigma \in \cM_n(\R)
\end{cases}$

On a 

\[
	\Sigma = \begin{pmatrix} \sigma_i & 0 & \cdots & | & 0 & \cdots & 0 \\ 0 & \sigma_i & \cdots & | & 0 & \cdots & 0 \\ 0 & 0 & \ddots & | & 0 & \cdots  & 0 \\ \hline 0  & 0  & \cdots 0 & | & 0 & \cdots & 0 \\ 0  & 0 & \cdots 0 & | & 0 & \cdots & 0\end{pmatrix} 
\] 


\subsection{SVD d'une matrice}

\paragraph{SVD} Singular value decomposition

Soit $A \in \cM_n(\R)$ telle que $\operatornam{rg}A \ge  1$


\subsubsection{Propriétés}

\begin{enumerate}
	\item $A$ est symétrique réelle semi-définie-positive i.e. $\forall x \in \R^n,\ x^\top (A^\top A)x \ge 0$ i.e. $\forall x\in \R^n,\ \|Ax\|^2\ge 0$
	\item $\operatorname{Sp}(A) \subset \R_+$
	\item $A^\top A$ est orthoDZ: $\begin{cases}
		\ker(A^\top A) &= \ker A \\
		\image(A^\top A) &= \image (A^\top) \\
	\end{cases}$

	\begin{proof}[de 3.]
		\begin{itemize}
			\item $\ker A \subset  \ker(A^\top A)$: \trivial
			\item $\ker A \supset \ker(A^\top A)$
			Soit $x\in \ker(A^\top A)$.

			On a \begin{align*}
				A^\top A x &= 0 \\
				\implies x^\top (A^\top A x) &= 0 \\
				\implies \|Ax\|^2 &= 0 \\
				\implies x &\in \ker A
			\end{align*}

			\item $\image A \subset  \image(A^\top A)$ 
				\begin{align*}
					\dim \ker (A^\top A) + \rg (A^\top A) &= n \\
					\implies \rg(A^\top A) &= n - \dim \ker(A^\top A) \\
					&= n - \dim \ker A \quad&\text{car $\ker A = \ker (A^\top A)$} \\
					&=  \rg A \\
					&= \rg (A^\top) \\
					\implies \image(A^\top A) &\subset   \image A \\
				\end{align*}
			\item $\image A \supset  \image(A^\top A)$ : \trivial
		\end{itemize}
	\end{proof}

	\item $A ^\top A \in GL_n(\R) \iff \rg A = n$
		\begin{proof}[de 4.]
		\begin{align*}
			A^\top A \in GL_n(\R) &\iff \ker(A^\top A) = \{0\}  \\
					      &\iff \ker A = \{0\} \\
					      &\iff \rg A = n \quad&\text{par théorème du rang}
		\end{align*}
	\end{proof}
\end{enumerate}

\subsection{Construction de la SVD de $A$}

Soit $A \in \cM_{m,n}(\R)$ tel que $\rg A \ge 1$. On note $r := \rg A$.

\begin{itemize}
	\item $\dim \ker (A^\top A) = n - r$ par théorème du rang. 

		Donc $0 \in \Sp(A^\top A)$ et $\mult_{A^\top A}(0) = n -r$
	\item On note $(\lambda_i)_{i\in \llbracket 1, n \rrbracket} = \Sp(A^\top A) \subset \R_+^\ast$, {\bf telles que $i < j \implies \lambda_i \le  \lambda_j$}

		On note $(v_i)_{i\in \llbracket 1, r\rrbracket}$ une bond DZante de $A^\top A$ associée à $(\lambda_i)_{i\in \llbracket 1, n \rrbracket}$

		Et on pose enfin

		\begin{align*}
		\cE = \left(\underbrace{v_1, \ldots, v_r}_{\text{bon de $(\ker A)^\top$}}, \underbrace{v_{r+1}, \ldots, v_n}_{\text{bon de $\ker A$}} \right)
		\end{align*}


		\item 
		On pose $V = (v_1, \ldots, v_r) \in \cO_n(\R)$
		Et \[
			\forall i\in \llbracket 1, n\rrbracket u_i = \frac{1}{\sqrt{\lambda_i} } A v_i \in \R^n 
		\] 

		\begin{align*}
			\forall (i, j) \in \llbracket 1, r \rrbracket^2\quad \left<U_i, U_j \right> &= \frac{1}{\sqrt{\lambda_i \lambda_j} } \left<Av_i, Av_j \right> \\
												    &= \frac{1}{\sqrt{\lambda_i \lambda_j} } \left<\underbrace{A^\top A v_i}_{\lambda_i v_i}, A^\top Av_j \right> \\
												    &= \sqrt{\frac{\lambda_i}{\lambda_j}} \underbrace{\left<v_i, v_j \right>}_{\delta_{ij}} \quad&\text{car $(v_i)_i$ orthonormée} \\
												    &= \delta_{ij} \quad&\text{car si $i=j$, ça fait 1, sinon ça fait 0} \\
		\end{align*}

		Donc $(U_i)_i$ est une famille orthonormée de $\R^m$
	
		Donc $\rg (U_i)_{i\in \llbracket 1, n \rrbracket} = r$

		Or $(u_i)_i \subset \image A$

		D'où $\Vect(u_i)_i \subset  \image A$ et $(\rg u_i)_i = \rg A$

		Donc  $(\Vect U_i)_i = \image A$ 

		 et $(U_i)_i$ bon de $\image A$.

		 D'où  $0\in \Sp(A^\top A)$ avec $\image A$

		 On la complète en  $(U_i)_{i\in \llbracket 1, m\rrbracket}$ bon de $\R^m$

		 \[
			 \cF = \left( \underbrace{u_1, \ldots, u_{r}}_{\text{bon de $\image A$ }}, \underbrace{u_{r+1}, \ldots, u_m}_\text{bon de $(\image A)^\top$} \right) 
		 \] 

		 Posons $U = (U_1, \ldots, U_m) \in \cO_n(\R)$

		 \paragraph{Remarque}
		 $\forall i\in \llbracket 1, r \rrbracket$
		 \begin{align*}
			 B u_i &= \mu_i u_i \\
		 \end{align*}


		 Avec $B, \mu_i$ à determiner.

		  \begin{align*}
			  A A ^\top U_i &= \frac{1}{\sqrt{\lambda_i} } \underbrace{A A^\top A v_i}_{=\lambda_i v_i\quad \text{par def de $v_i$}} \\
			  &= \sqrt{\lambda_i} A v_i  \\
			  &= \lambda_i \underbrace{\left( \frac{1}{\sqrt{\lambda_i} } A v_i \right) }_{U_i} \\
			  &= \lambda_i U_i \\
		 \end{align*}


		 D'où $U_i$ vecteur propre de $A A^\top$ associé à  $\lambda_i$

		 \item  On pose \begin{align*}
		 	\Sigma &= U^\top AV \\
			       &= U^\top \left(\underbrace{Av_1, \ldots, Av_r}_{\sqrt{\lambda_i} u_i }, \underbrace{A v_{r+1}, \ldots, A v_n}_{0\ \text{car $v_i \in \ker A$}}\right) \\
			       &= \begin{pmatrix} u_1^\top \\ \vdots \\ u_m^\top \end{pmatrix} \begin{pmatrix} \sqrt{\lambda_j}  \left<u_i, u_j \right> | (0) \\ \hline \sqrt{\lambda_j} \left<u_i, u_j \right> | (0) \end{pmatrix}   \\
			       &= \begin{pmatrix} \sqrt{\lambda_1} &  & (0) &  | & \\  & \ddots &  & |  & (0) \\  (0) &  & \sqrt{\lambda_r}  & | & \\ \hline & (0) & & | & (0) \end{pmatrix}  \\
			       \implies A &= U \sigma V^\top \\
		 \end{align*}


		 \begin{definition}[SVD de $A$]
		 	Décomposition de la forme \[
		 		A = U \Sigma V^\top
		 	\] 

			Avec $U, \Sigma, V$ comme définies précédemment

			On appelle valeurs singulières notées  $(\sigma_i)_i$ les valeurs propres racines carrées
		 \end{definition}


\end{itemize}


%\begin{align*}
%	A\quad {}^\top A^\top,\  A \\
%	A\quad{}^\top k\tau,\ B
%\end{align*}

\begin{center}
    {\Large\bf Il manque un passage, j'étais en retard de 7 minutes au cours :/}
\end{center}

\subsection{Matrice pseudo-inverse}
Ou pseudo-inverse généralisée

Soit $A\in \cM_{n, n}(\R)$ telle que $\rg A = r \ge 1$



\begin{definition}[Matrice pseudo-inverse]
   Soit $A = U \Sigma U^\top$  la SVD de $A$

   \begin{figure}[H]
       \centering
       \begin{tikzpicture}
           \draw[->] (-1, 0) -- (10, 0) node{$\ker A$ };
           \draw[->] (0, -1) -- (0, 10) node{$\ker A^\top$ };
           \draw[->] (1, 1) node{$U_{|\ker A}^{|\img A \top}$ -- (20, 1) node{$A = [U]$};
       \end{tikzpicture}
       \caption{}
       \label{fig:}
   \end{figure}

   On définit la pseudo-inverse  \begin{align*}
       A^+ &= V\Sigma^+ U^\top \\
   \end{align*}
   avec $\Sigma^+ = \begin{pmatrix} \Sigma_r^{-1} & | & 0 \\\hline 0 & | & 0 \end{pmatrix} $ avec le bloc non-nul de taille $r  \times r$.
\end{definition}

\begin{proposition}
    \begin{enumerate}
        \item $A A^+ = \Pi_{\img A}$
         \item $A^+ A = \Pi_{\ker A^\top}$
    \end{enumerate}

    Avec $\Pi_A$ la projection orthogonale sur  $A$
\end{proposition}

\begin{lemme}
    Soit $Q\in \cO_{n, r}(\R)$.

    ALors $Q Q^\top$ est une projection othogonale sur le sous-espace engendré par les colonnes de $Q$.
\end{lemme}

\begin{proof}
    cf. CTD factorisation $Q_r$
\end{proof}
%

\begin{enumerate}
    \item \begin{align*}
        A A^+ &= U \Sigma \underbrace{V^\top V}_{\img} \Sigma^+ U^\top \\
              &= \begin{pmatrix} u_1 & u_2 \end{pmatrix} \begin{pmatrix} \Sigma_1 & 0 \\ 0 & 0 \end{pmatrix} \begin{pmatrix} \Sigma_1^{-1} & 0 \\ 0 & 0 \end{pmatrix} \begin{pmatrix} u_1^\top \\ u_2^\top \end{pmatrix}  \\
              &= u_1 u_1^\top \\
    \end{align*}

Avec $U_1 = \begin{pmatrix} u_1 & \ldots & u_r \end{pmatrix} \in \cM_{m, r}$ telle que $u_1^\top u_2 = I_r$.

Donc \begin{align*}
    A A^+ &= \underbrace{\Pi_{\vect(u_1, \ldots, u_r)}}_{\img A} \\
    &= \Pi_{\img A} \\
\end{align*}

\item \begin{align*}
    A A^+ &= V_1 V_1^\top \\
    &= \underbrace{\Pi_{\vect(v_1, \ldots, v_r)}}_{\ker A^\top} \\
    &= \Pi_{\ker A^\top} \\
\end{align*}

\end{enumerate}

\begin{theorem}[Caractérisation de Moore-Penrose]
   $A^+$ est l'unique solution du système

   \begin{align*}
       (MP) \begin{cases}
           AXA &= A \\
           XAX &= X \\
           (AX)^\top &=  AX \\
           (XA)^\top &= XA \\
       \end{cases}
   \end{align*}

   Avec $X \in \cM_{n, n}(\R)$
\end{theorem}

\begin{proof}[Etude de $(MP)$]
    \paragraph{Existance de solution}
    \begin{enumerate}
        \item \begin{align*}
            A A^+ A &=  U \Sigma \underbrace{\img}_{V^\top V} \Sigma^+ \underbrace{U^\top U}_{\img} \Sigma V^\top \\
            &= U \Sigma \Sigma^+ \Sigma V^\top \\
        \end{align*}

        Or \begin{align*}
            \Sigma \Sigma^+ \Sigma &= \begin{pmatrix} \Sigma_r & 0 \\ 0 & 0 \end{pmatrix}  \begin{pmatrix} \Sigma_r^{-1} & 0 \\ 0 & 0 \end{pmatrix} \begin{pmatrix} \Sigma_r & 0 \\ 0 & 0 \end{pmatrix}  \\
                                   &= \begin{pmatrix} \Sigma_r & 0 \\ 0 & 0 \end{pmatrix} \begin{pmatrix} I_r & 0 \\ 0 & 0 \end{pmatrix} \\
                                   &= \begin{pmatrix} \Sigma_r & 0 \\ 0 & 0 \end{pmatrix}  \\
                                   &= \Sigma \\
        \end{align*}
    \end{enumerate}

    Donc \begin{align*}
        A A^+ A &= U \Sigma V^\top = A \\
    \end{align*}

    \item \begin{align*}
        A^+ A A^+ &= V \underbrace{\Sigma^+ \Sigma \Sigma^+}_{\Sigma^+} U^\top \\
        &= V \Sigma^+ U^\top \\
        &= A^+ \\
    \end{align*}

    \item \begin{align*}
            (A A^+)^\top &= (U_1 U_1^\top)^\top \quad&\text{cf. prop. sur $A A^\top$ et $A^+ A$} \\
            &= U_1 U_1^\top \\
            &= A A^+ \\
    \end{align*}

    \item \begin{align*}
            (A^+ A)^\top &= (V_1 V_1^\top)^\top \\
            &= V_1 V_1^\top \\
            &= A^+ A \\
    \end{align*}

    d(où $A^+$ solution de $(MP)$ associée à $A$ 

\paragraph{Unicité de la solution}
Soient $X_1, X_2$ deux solutions de $(MP)$ associées à $A$.

\begin{itemize}
    \item Montrons $AX_1 = AX_2$ 
        \begin{align*}
            AX_1 &= (AX_1)^\top \quad&\text{par 3. appliquée à $X_1$} \\
            &= X_1^\top A^\top \\
            &= X_1^\top (AX_2 A )^\top \\
            &= X_1^\top A^\top X_2^\top A^\top \\
            &= (A X_1)^\top (AX_2)^\top \\
            &= (AX_1) (AX_2) \quad&\text{par 3.} \\
            &= \underbrace{AX_1 A}_{A} X_2 \quad&\text{par 1. appliquée à $X_1$}\\
            &= AX_2 \\
        \end{align*}

        \item On montre de même: $X_1 A = X_2 A$.

    \item Montrons $X_1 A X_2 = A$

        \begin{align*}
            X_1A X_2 &= X_2 A X_2 \\
            &= X_2 \quad&\text{par 2. appliquée à $X_2$} \\
            &= X_2 \quad&\text{car $AX_1 = AX_2$} \\
            \text{i.e.}\quad X_1 &= X_2 \quad&\text{par 2. appliquée à $X_1$} \\
        \end{align*}
\end{itemize}


{\bf Donc on peut permuter $ \cdot ^\top$ et $ \cdot ^+$.}

\end{proof}

\begin{theorem}[$^\top = ^+$]
    \begin{align*}
        A^\top ^+ = A^+ ^\top
    \end{align*}
\end{theorem}

\begin{proof}
    On vérifie que $(A^+)^\top$ est solution de $(MP)$ associée à $A$.

    \begin{enumerate}
        \item \begin{align*}
            A^\top (A^+)^\top A^\top &= (A A^+ A)^\top \\
            &= A^\top \quad&\text{par 1. appliquée à $A^+$} \\
        \end{align*}

        \item \begin{align*}
                (A^+)^\top A^\top (A^+)^\top &= \underbrace{(A^+ A A^+)^\top}_{A+} \quad&\text{par 2 appliquée à $A^+$} \\
                &= (A^+)^\top \\
        \end{align*}

        \item \begin{align*}
                (A^\top (A^+)^\top)^\top &= ( \underbrace{(A^+ A)^\top}_{A^+ A})^\top \quad&\text{par 4. appliquée à $A^+$ } \\
                &= (A^+A)^\top \\
                &= A^\top (A^+)^\top \\
        \end{align*}

        \item \begin{align*}
                ((A^+)^\top A^\top)^\top &= [\underbrace{(A A^+)^\top}_{A A^+}]^\top \quad&\text{par 3. appliquée à $A^+$} \\
                &= (A^+)^\top A^\top \\
        \end{align*}

    \end{enumerate}
        d'où  $A^+^\top $ solution de  $(MP)$ associée à $A^\top$.

        Par caractérisation de Moore-Penrose:

         \begin{align*}
             A^{\top +} &= A^{+ \top} \\
        \end{align*}
\end{proof}

\begin{theorem}[Caractérisation de $A^+$ par l'image d'un vecteur de $\R^n$ ]
    Soit $b\in \R^n$.

    Alors $A^{+} b$ est la solution de norme $\| \cdot \|_2$ minimale de 

    \begin{align*}
        (\cP) \min_{x \in \R^n} f(x) &= \frac{1}{2} \| Ax - b \|_2^2 \\
    \end{align*}
\end{theorem}

\begin{proof}
    \begin{itemize}
        \item \begin{align*}
            \forall x\in \R^n, \begin{cases}
               \nabla f(x) &= A^\top (Ax - b) \\
               \nabla ^2 f(x) &= A^\top A \text{ semi-def pos.} \\
            \end{cases}
        \end{align*}

        Donc $f$ convexe sur $\R^n$ et les points critiques ont des minima globaux.

        \item \begin{align*}
            \nabla f &= A^\top (A A^+b-b) \\
            &= V_1 \Sigma_1 U_1^\top (U_1 \Sigma_r \underbrace{V_1^\top V_1}_{I_2} \Sigma_r^{-1} U_1^\top b-b)  \\
            &= V_1 \Sigma_r \underbrace{(\underbrace{U_1^\top U_1}_{I_2} U_1^\top - U_1^\top }_{0})b \\
            &= 0 \\
        \end{align*}

        car \begin{align*}
            A &= U\Sigma V^\top = U_1 \Sigma_r V_1^\top \\
            A^+ &= V \Sigma^+ U^\top = V_1 \Sigma_r^{-1} U_1^\top  \\
        \end{align*}

        et $A^+ b$ est solution de $(\cP)$

        \item Montrons $\forall v \in \R^n,\text{ $v$ solution de $(\cP)$}, \exists x_0 \in \ker A,\ x=x_0 + A^+ b$

            Soit $x\in \R^n$ solution de $(\cP)$.

            Or $\R^n = \ker A \oplus \ker A^\bot $.

            D'où $\exists ! (x_0, x_{\bot}) \in \ker A  \times \ker A^\bot, x = x_0 + x_{\bot} $.

            Or $x$ solution de $(\cP)$ donc $\nabla f(x)=0$.

            D'où 
            \begin{align*}
                A^\top  A x &= A^\top b\\
                \iff A^\top  A(x_0 + x_{\bot}) &= A^\top b \\
                \iff A^\top \underbrace{A x_0}_{\text{$0$ car $x_0\in \ker A$}} + A^\top  A x_{\bot} &= A^\top b \\
                \iff A^\top  A x_{\bot} &= A^\top b \\
            \end{align*}

            Or $A^\top  A (A^+ b) =A^\top b$ car $A^\top b$ solution de $(\cP)$ 

            D'où $A^\top  A x_{\bot} = A^\top  A(A^+b) \text{ i.e. } A^\top A(x_{\bot} - A^+ b) = 0$.

            D'où $x_{\bot}-A^+ b \in \ker(A^\top  A) = \ker A$ (cf. prop. de $A^\top A$ )

            \begin{align*}
                A^+ b &= X_1 \Sigma_r^{-1} U_1^\top b \\
                      &\in \img V_1 \\
                \text{or } V_1 &= \begin{pmatrix} v_1 & \ldots & v_r \end{pmatrix} \quad \text{avec les $(u_i)_i$ b.o.n. de $\ker A^\top $} \\
            \end{align*}

            D'où $A^+ b \in \ker A^\bot$

            Or $x_{\bot}\in \ker A^\bot$ donc $x_{\bot} - A^+ b \in \ker A^\bot$ 

            D'où $x_{\bot} - A^+ b \in \ker A \cap \ker A^\bot = \{0\} $ car $\ker A \oplus \ker A^\bot = \R^n$

            et $x_{\bot} = A^+ b$ 

            D'où $\exists x_0 \in \ker A, x=x_0 + A^+ b$ 

        \item {\bf Bilan} \begin{align*}
            \forall x \in \R^n,\quad \text{solution de $(\cP)$} \implies \|x\|_2 \ge \|A^{+}b\|_2
        \end{align*}

    \end{itemize}
\end{proof}

\begin{corollary}[Equation normale]
    $\forall b\in \R^m, (A^\top A) A^+ b = A^\top b$, 
\end{corollary}

\begin{proposition}[Cas particuliers]
   \begin{enumerate}
       \item $A$ inversible:  $\rg A = m = n$
           \begin{align*}
               A^+ = A^{-1}
           \end{align*}

        \item $\rg A = m$ ($m \ge n$ )
            \begin{align*}
                A^+ = (A^\top A)^{-1} A^\top 
            \end{align*}

        \item $\rg A = m \quad (n\ge m)$

            \begin{align*}
                A^+ = A^\top (A A^\top )^{-1}
            \end{align*}
   \end{enumerate} 
\end{proposition}

\begin{proof}
   \begin{enumerate}
       \item $A^{-1}$ vérifie $(MP)$
        \item $\rg A = n$ donc $A^\top A$ inversible. (cf. prop. de $A^\top A$ ).

            D'après les équations normales, 

            \begin{align*}
                \forall b\in \R^m,\quad (A^\top A) A ^+ b &= A^\top b \\
                \text{donc}\quad (A^\top A) A^+ &= A^\top  \\
                \text{donc}\quad A^+ &= (A^\top A)^{-1} A^\top  \\
            \end{align*}

        \item On pose $B = A^\top $. On a $B^\top B$ inversible.

            \begin{align*}
                \rg B = m
            \end{align*}
            d'où par 2.

            \begin{align*}
                B^+ &= (B^\top B)^{-1} B^\top \\
                \text{i.e. }(A^\top )^+ &= (A A^\top )^{-1} A \\
                \text{i.e. }(A^{+})^\top &= (A A^\top )^{-1} A \quad&\text{car $ \cdot ^+$ et $ \cdot ^\top $ permuttent} \\
                \text{i.e. }A^+ &= A^\top  (A A^\top )^{-1} \\
            \end{align*}
   \end{enumerate} 
\end{proof}

\ldots gros passage à rattraper \ldots

\begin{definition}[Précision machine $\epsilon_n$ ]
    Le nombre représentable en machine juste après 1.
\end{definition}

\begin{example}
    Soit $x_1 \in \R_+^\ast$ représentable en machine.

    \begin{align*}
        x_1 &= \underbrace{(a_1 + \frac{a_2}{b} + \cdots + \frac{a_p}{b^{p-1}}}_{m} b^{e} \\
    \end{align*}

    Soit $x_2$ le nombre représentable en machine juste ``au dessus" de $x_1$ :

    \begin{align*}
        x_2 &= (a_1 + \frac{a_2}{b} + \cdots + \frac{a_p}{b^{p-1}} b^{e} \\
    \end{align*}

    d'où
    \begin{align*}
        \frac{|x_1 - x_2|}{|x_1|} &= \frac{b^{e}}{b^{p-1}} \frac{1}{m b^{e}} \\
        &= \frac{1}{m b^{p-1}} \\
        m b^{p-1} &= (a_1 + \frac{a_2}{b} + \cdots + \frac{a_p}{b^{p-1}} b^{p-1} \\
        &= a_1 b^{p-1} + a_2 b^{p-2} + \cdots + a_p \\
    \end{align*}

    or $\forall i \in \llbracket 1, p \rrbracket$, $a_1\le b-1$

    \begin{align*}
        mb^{p-1} &\le (b-1) \underbrace{\sum_{k=0}^{p-1} b^{k}}_{\frac{1-b^{p}}{1-b}} \\
                 &\le b^{p} - 1 \\
                 &\le b^{p}
    \end{align*}

    Donc \begin{align*}
        \frac{|x_2 - x_1|}{|x_1|} > \frac{1}{b^{p}} = \frac{\epsilon_n}{b}
    \end{align*}

\paragraph{Implication pour les critères d'arrêt}

\begin{align*}
    \frac{|x_{k+1} - x_k|}{|x_k|} \le \epsilon_{\text{tol}}
\end{align*}

Avec $\epsilon_{\text{tol}}$ précision définie par l'utilisateur.

$\epsilon_\text{tol}$ à choisir en fonction de $\epsilon_n$ ( $\epsilon_\text{tol} \ge  \frac{\epsilon_n}{b}$ )


\section{Sensibilité de la solution d'un système à des perturbations des données}

Soit $(A, b) \in GL_n(\K)  \times \K^{n}$

On cherche à résoudre $Ax=b$ 

En pratique, on résoud plutôt

\begin{align*}
    (A + \Delta A)(x + \Delta x) &= b + \Delta b \\
\end{align*}

donc 
\begin{align*}
    \frac{\|\Delta x\|}{\|x\|}
\end{align*}

\subsection{Conditionnement d'une matrice}

\begin{definition}[Conditionnement $K$]
    Soit $A\in \cM_n(\K)$ inversible.

    Soit $\|\|$ une norme sur $\K^{n}$ 

On note également $\|\|$ la norme induite sur $\cM_n(\K)$.

\begin{align*}
    \|A\| = \sup_{x\neq 0} \frac{\|Ax\|}{\|x\|} = \sup_{\|x\|=1} \|Ax\|
\end{align*}

Le conditionnement de $A$, noté $K(A)$ est définit par $K(A) = \|A\| \|A^{-1}\|$

\end{definition}

\begin{definition}[Bon conditionnement]
   Si $K(A)$ est petit 
\end{definition}

\begin{proposition}
    \begin{enumerate}
        \item Soit $\alpha\in \R$ alors $K(\alpha A) = K(A)$.
        \item $K(A) \ge 1$.

        \item Avec $\| \cdot \|_2$:
            \begin{align*}
                K_2(A) &= \frac{\sigma_1}{\sigma_n} \\
            \end{align*}

            Avec $\sigma_1 \ge \sigma_2 \ge \cdots \ge \sigma_n > 0$ les valeurs singulières de $A$.
        \item Avec $\| \cdot \|_2$ 

            \begin{align*}
                K_2(A) = 1 &\iff \exists \alpha\in \K \setminus \{0\},\  \exists U\in \cO_n(\K), A = \alpha U
            \end{align*}
    \end{enumerate}
\end{proposition}

\begin{definition}[Distance relative à la non-inversibilité $d_s$]
    

    Soit $A\in \cM_n(\K)$ non-nulle.

    
    \begin{align*}
        d_s(A) &:= \min \left\{\frac{\|\Delta A\|}{\|A\|},\ \Delta A \in \cM_n(\K), A + \Delta A \not\in GL_n(\K)\right\} \in [0, 1] \\
    \end{align*}
\end{definition}

\begin{theorem}[Gastinel, Katram]
    Soit $A\in GL_n(\K)$.

    \begin{align*}
        d_s(A) &= \frac{1}{K(A)} = \frac{1}{\|A\| \|A^{-1}\|} \\
    \end{align*}
\end{theorem}

\begin{remarque}
    Le conditionnement d'une matrice informe sur l'amplitude minimale des pertubations à ajouter à $A$ pour la rendre non inversible.

    \paragraph{Exemples}
    \begin{enumerate}
        \item $K(A) \approx 1O^{6}$
    \end{enumerate}
    
\end{remarque}

\subsection{Sensibilité de la solution d'un système linéaire aux perturbations de $A$ et/ou $b$}

\begin{proposition}
    Soit $(A, b) \in GL_n(\K) \times \K^{n}$.

    Soit $\| \cdot \|$ unr norme sur $\K^{n}$, et on note $\| \cdot \|$ la norme qu'elle induit sur $\cM_n(\K)$;

    On a
    \begin{description}
        \item[Perturbation de $b$] Soit $y = x+\Delta x$ solution de  $Ay = b + \Delta b$ avec  $A b \in \K^{n}$

            Alors \begin{align*}
                \frac{\|\Delta x\|}{\|x\|} \le K(A) \frac{\|\Delta b\|}{\|b\|}.
            \end{align*}
        \item[Perturbation de $A$] Soit $y = x+\Delta x$ solution de $(A + \Delta A)x = b$.

            On a 

            \begin{align*}
                \frac{\|\Delta x\|}{\|x + \Delta x\|} &\le \frac{K(A) \frac{\|\Delta A \|}{\|A\|}}{1 - K(A) \frac{\|\Delta A\|}{\|A\|}}  \\
                &= K(A) + \frac{\|\Delta A\|}{\|A\|} + O\left( \frac{\|\Delta A\|^2}{\|A\|^2} \right)  \\
            \end{align*}
    \end{description}
\end{proposition}

\begin{remarque}
    \begin{itemize}
        \item 
    \begin{align*}
        K(A) \frac{\|\Delta A\|}{\|A\|} < 1 &\iff \frac{\|\Delta A\|}{\|A\|} < \frac{1}{K(A)} \\
                                            &\iff \frac{\|\Delta A\|}{\|A\|} < d_s(A)
    \end{align*}
    \item On suppose que $A + \Delta A$ reste inversible
    \end{itemize}
\end{remarque}

\begin{proof}
\begin{enumerate}
    \item \begin{align*}
        A(x+\Delta x) = b + \Delta b \quad&\text{avec $A x = b$}
    \end{align*}

    d'où \begin{align*}
        A \Delta x &= \Delta b \\
        \iff \Delta x &= A^{-1} \Delta b \\
    \end{align*}

    Il vient \begin{align*}
        \|\Delta x\| &= \|A^{-1} \Delta b\|  \\
                     &\le \|A^{-1}\| \|\Delta b\| \frac{\|A\|}{\|A\|} \\
        \|\Delta x\| &\le K(A) \frac{\|\Delta b\|}{\|A\|} \\
        \frac{\|\Delta x\|}{\|x\|} &\le K(A) \frac{\|\Delta b\|}{\|A\| \|x\|}
    \end{align*}

    Or $Ax = b$ d'où $\|b\| \le \|A\| \|x\|$


    et $\frac{\|\Delta x\|}{\|x\|} \le  K(A) \frac{\|\Delta b\|}{\|b\|}$

 \item $(A+\Delta A)(x + \Delta x) = b$ avec  $Ax = b$

     Donc  \begin{align*}
         A \Delta x &= - \Delta A (x + \Delta x ) \\
         \Delta x &= -A^{-1} \Delta A (x + \Delta x ) \\
     \end{align*}


     D'où $\|\Delta x\| \le \|A^{-1}\| \|\Delta A\| \|x + \Delta x \|$

     et $\frac{\|\Delta x\|}{\|x + \Delta x \|} \le  \underbrace{\|A^{-1}\| \|A\|}_{K(A)} \frac{\|\Delta A\|}{\| A\|}$


     Si de plus $K(A) \frac{\|\Delta A\|}{\|A\|} < 1$

     \begin{align*}
         \|\Delta x\| \le  K(A) \frac{\|\Delta A\|}{\|A\|} \underbrace{\|x + \Delta x \|}_{\|x\| + \|\Delta x\|} \\
         \implies \overbrace{1 - K(A) \frac{\|\Delta A\|}{\|A\|} \|\Delta x\|}^{> 0} \le K(A) \frac{\|\Delta A\|}{\|A\|} \|x\| \\
         \implies \frac{\|\Delta x\|}{\|x\| } \le \frac{K(A) \frac{\|\Delta A\|}{\|A\|}}{1 - K(A) \frac{\|\Delta A\|}{\|A\|}}
     \end{align*}
\end{enumerate} 
\end{proof}

\end{example}

\section{Erreurs directe et inverse par la résolution de systèmes linéaires}

Soit $(A, b) \in GL_n(\K)  \times \K^{n}$.
 
On suppose disposer d'une application $f$, opérant en arithmétique exacte, et calculant $f(A, b) = x$ avec $x\in \K^{n}$ tel que $Ax = b$.

( $f$ algorithme théorique)

On dispose d'un algorithme numérique $g$, opérant en arithmétique finie, instanciant $f$ :

\begin{align*}
    g(A, b) = \tilde{x} \in \K^{n}
\end{align*}

\subsection{Erreur inverse d'un algorithme}

\begin{definition}
    Soit $g$ un algorithme numérique, opérant en arithmétique finie, et calculant la solution de $Ax=b$ par $A\in GL_n(\K)$ et $b\in \K^{n}$.

    Soit $\| \cdot \|$ une norme sur $\K^{n}$. On note $\| \cdot \|$ la norme induite à $\cM_n(\K)$.

    On appelle ``erreur inverse de $g$ ", notée $\text{Ben}$.

    \begin{align*}
        \text{Ben}&= \min \{\epsilon > 0,\ \exists \Delta A \in \cM_n(\K) \text{ tq } (A + \Delta A) \text{ et } \ldots \textbf{à récupérer} \ldots  \}  \\
    \end{align*}
\end{definition}


\ldots à récupérer \ldots

\end{document}
