
\documentclass[a4paper,11pt]{amsart}
\usepackage{multicol,etex,fancyhdr}
\usepackage[latin1]{inputenc}
\usepackage[T1]{fontenc}
\usepackage[francais]{babel}


\usepackage[fourierbb,mathlf,textosf]{MinionPro}

\renewcommand{\sfdefault}{ucl}
\renewcommand{\ttdefault}{lmtt}
\usepackage[a4paper,DIVcalc,pagesize,headinclude]{typearea}
\typearea[11mm]{16}

% \documentclass[french,a4paper]{amsart}
% \usepackage{amsfonts,etex}
% \usepackage[latin1]{inputenc}
% \usepackage{multicol}
% \usepackage{a4wide}
% \usepackage[french]{babel}

\usepackage[thinlines,thiklines]{easybmat}
\usepackage{gauss}
\usepackage{listings,algorithm, algorithmic}

\input la2emath
% Personalisation
\newcommand{\matiere}{Analyse Num\'erique}
\newcommand{\annee}{2007-2008}
\newcommand{\cursus}{L2 Math - L2 Info}
\newcommand{\relief}[1]{\textbf{#1}}
% Environnements
\newcounter{noex}
\newcounter{noq}
\newcounter{noqq}
\newenvironment{exercice}[1]{\stepcounter{noex} %
\noindent\relief{Exercice \arabic{noex}.\ #1}}{}
\newenvironment{questions}{\setcounter{noqq}{1}%
  \begin{list}{(\alph{noq})}{\usecounter{noq}}}{\end{list}}
\newenvironment{qquestions}{%
  \begin{list}{-\roman{noqq}-}{\usecounter{noqq}}}{\end{list}}
\newcommand{\bex}{\begin{exercice}}
\newcommand{\eex}{\end{exercice}}
\newcommand{\bq}{\begin{questions}}
\newcommand{\eq}{\end{questions}}
\newcommand{\bqq}{\begin{qquestions}}
\newcommand{\eqq}{\end{qquestions}}
\newcommand{\fiche}[2]{\newpage\setcounter{noex}{0}
  \setbox1=\vbox{\hbox{\sffamily\small Universit\'e de Rouen}%
  %  \hbox{\sffamily\small\matiere}%
    \hbox{\sffamily\small\cursus}\hbox{\sffamily\small Ann\'ee \annee}}%
  \setbox2=\vbox{\hbox{\sffamily\matiere}%
\hbox{\sffamily #2}}%
  {\vglue-1.5cm \noindent$\vcenter{\box1}\hfill\vcenter{\box2}$}}
\newcommand{\pg}{\textrm{PGCD}}
\newcommand{\de}{\textrm{deg}}

\newcommand\etoi{\relax}%\noindent \makebox[0cm][r]{ $(*)$}}
\makeatletter
\def\th@definition{%
  \normalfont % body font
}
\def\th@plain{%
  \slshape % body font
}
\def\th@remark{%
  \normalfont % body font
  \thm@preskip\topsep
  \divide\thm@preskip\tw@
  \thm@postskip\thm@preskip
}
\renewcommand{\ALG@name}{Algorithme}
\makeatother
%\setlength{\parindent}{0cm}

% \addtolength{\textheight}{2cm}
% \addtolength{\textwidth}{3.5cm}
% \addtolength{\evensidemargin}{-1.7cm}
% \addtolength{\oddsidemargin}{-1.7cm}
% \addtolength{\voffset}{-1cm}



\newcommand\suite[2][n\in\N]{{\ensuremath{\left(#2\right)_{#1}}}}

\newcommand\ecart{\addtolength{\itemsep}{-0.05cm}}


\newcommand{\Atil}[1]{{\ensuremath{\widetilde{A}^{(#1)}}}}
\newcommand{\An}[1]{{\ensuremath{A^{(#1)}}}}

\newcommand{\atil}[1]{{\ensuremath{\widetilde{a}^{(#1)}}}}
\newcommand{\an}[1]{a^{(#1)}}

\lstdefinelanguage{maple}
{morekeywords={if,fi,local,proc,end,then,while,do,od,print,error,else,options,for,from,by,to,evalm},
sensitive=f
}

\theoremstyle{remark}


\newtheorem{rmq}{Remarque}%[subsection]


\theoremstyle{definition}
\newtheorem{defi}[rmq]{D\'efinition}
\newtheorem{exer}[rmq]{Exercice}
\newtheorem{exem}[rmq]{Exemple}
\newcommand{\idee}[1]{{\noindent{\makebox[0cm][r]{$\rightarrow$}\sffamily
      Id\'ee :}} #1\par}

\theoremstyle{plain}
\newtheorem{prop}[rmq]{Proposition}
\newtheorem{lemma}[rmq]{Lemme}
\newtheorem{theo}[rmq]{Th\'eor\`eme}
\newtheorem{coro}[rmq]{Corollaire}

\begin{document}


\lstset{extendedchars=true, emph={Digits},emphstyle=\underbar,
  language=maple}

\fiche{2}{Gauss et Cholesky}
\fancyfoot[C]{}
\fancyhead[LO]{Gauss et Cholesky}
\fancyhead[LE]{\thepage.}
\fancyhead[RE]{Gauss et Cholesky}
\fancyhead[RO]{\thepage.}
\thispagestyle{empty}
\pagestyle{fancy}
\normalsize
\par
\setlength{\columnseprule}{0.5pt}

\bigskip\bigskip

\section{Pivot de Gauss}
\subsection{Un exemple}
Soit \`a r\'esoudre le syst\`eme lin\'eaire $Ax=b$ avec 
\begin{gather*}
  A=
  \begin{pmatrix}
     2 & 3 &-1 &3\\ 4 & 6& 0& 2 \\-1&-2&0&5 \\-1&4&5&2
  \end{pmatrix},\qquad
 b=
 \begin{pmatrix}
  11 \\ 6 \\ 21 \\ 3
 \end{pmatrix}
\end{gather*}
Proc\'edons \`a l'\'elimination de Gauss ; la $1$\`ere \'etape
est\footnote{Deviner ce que veulent dire les fl\`eches et nombres
  plac\'es \`a droite des matrices!}
\begin{gather*}
  \begin{gmatrix}[p]
    2 & 3 &-1 &3\\ 4 & 6& 0& 2 \\-1&-2&0&5 \\-1&4&5&2
    \rowops
    \add[-2]{0}{1}
    \add[1/2]{0}{2}
    \add[1/2]{0}{3}
  \end{gmatrix}
  \qquad \text{qui donne}\qquad
  \begin{gmatrix}[p]
    2 &3 & -1 & 3\\
    0 & 0&  2&  -4\\
0& -1/2&  -1/2&  13/2\\
0 & 11/2 & 9/2& 7/2
\end{gmatrix}
\end{gather*}
La $2$\`eme \'etape est
\begin{gather*}
\begin{gmatrix}[p]
2 &3 & -1 & 3\\
0 & 0&  2&  -4\\
0& -1/2&  -1/2&  13/2\\
0 & 11/2 & 9/2& 7/2
\rowops
\swap{1}{2}
\add[11]{1}{3}
\end{gmatrix}
\qquad \text{qui donne}\qquad
\begin{gmatrix}[p]
2 & 3&  -1&  3\\ 0& -1/2&  -1/2& 13/2\\ 0& 0& 2& -4\\0& 0& -1& 75
\end{gmatrix}
\end{gather*}
Enfin la derni\`ere \'etape consiste en
\begin{gather*}
\begin{gmatrix}[p]
2 & 3&  -1&  3\\ 0& -1/2&  -1/2& 13/2\\ 0& 0& 2& -4\\0& 0& -1& 75
\rowops
\add[1/2]{2}{3}
\end{gmatrix}
\qquad \text{qui donne}\qquad
\begin{gmatrix}[p]
2 & 3 & -1&  3\\ 0& -1/2& -1/2& 13/2\\ 0& 0& 2& -4\\0& 0& 0& 73
\end{gmatrix}
\end{gather*}
Les m\^emes transformations appliqu\'ees au vecteur $b$,
\begin{gather*}
  \begin{gmatrix}[p]
  11 \\ 6 \\ 21 \\ 3
\rowops
\add[-2]{0}{1}
\add[1/2]{0}{2}
\add[1/2]{0}{3}
\swap{1}{2}
\add[11]{1}{3}
\add[1/2]{2}{3}
  \end{gmatrix}
\qquad \text{nous donne}\qquad 
\begin{gmatrix}[p]
  11 \\ 53/2 \\ -16 \\ 292
\end{gmatrix}.
\end{gather*}
Par remont\'ee du syst\`eme on trouve 
$$
x=
\begin{pmatrix}
  1 \\ -1 \\ 0 \\ 4
\end{pmatrix}.
$$

\begin{multicols}{2}

En termes matriciels, la $1$\`ere \'etape consiste
\`a \'etablir $\An{2}=E_1A$ avec
$$
\An{2}=
\begin{gmatrix}[p]
2 &3 & -1 & 3\\
0 & 0&  2&  -4\\
0& -1/2&  -1/2&  13/2\\
0 & 11/2 & 9/2& 7/2
\end{gmatrix}
$$
$$
\text{ et }
E_1=
\begin{pmatrix}
1 & 0 & 0 & 0 \\
-2 & 1 & 0 &0 \\
1/2 & 0 & 1 &0\\
1/2 & 0 & 0 & 1  
\end{pmatrix}.
$$

Puis $\An{3}=E_2P_2\An{2}$ avec
$$
\An{3}=
\begin{gmatrix}[p]
2 & 3&  -1&  3\\ 0& -1/2&  -1/2& 13/2\\ 0& 0& 2& -4\\0& 0& -1& 75
\end{gmatrix},
$$
$$
P_2=
\begin{gmatrix}[p]
  1 & 0 & 0 &0 \\
0 & 0 & 1 & 0 \\
0 & 1 & 0 & 0 \\
0 & 0 & 0 & 1 
\end{gmatrix}
\text{ et }
E_2=
\begin{gmatrix}[p]
  1 & 0 & 0 &0 \\
0 & 1 & 0 & 0 \\
0 & 0 & 1 & 0\\
0 & 11 & 0 & 1 
\end{gmatrix}
$$
Enfin, on obtient $\An{4}=E_3\An{3}$ avec
$$
\An{4}=
\begin{gmatrix}[p]
2 & 3 & -1&  3\\ 0& -1/2& -1/2& 13/2\\ 0& 0& 2& -4\\0& 0& 0& 73
\end{gmatrix}
$$
$$
\text{et }
E_3=
\begin{pmatrix}
  1 &0 & 0 &0 \\
0 & 1 & 0 & 0 \\
0 & 0 & 1 & 0 \\
0 & 0 & 1/2 & 1 
\end{pmatrix}
$$
La matrice $\An{4}$ est triangulaire sup\'erieure et est donn\'ee par
$\An{4}=E_3E_2P_2E_1A$. Simultan\'ement on calcule
$E_{3}E_{2}P_{2}E_{1}b$ pour r\'esoudre $\An{4}x=E_{3}E_{2}P_{2}E_{1}b$.
\end{multicols}


\subsection{Cas g\'en\'eral}
\begin{proof}
Soit $A=(a_{i,j})_{1\leq i,j\leq n}$ une matrice carr\'ee de taille
$n$ inversible. 
\par
\noindent{\sffamily \'Etape 1 : }
posons $A^{(1)}=(a^{(1)}_{i,j})_{1\leq i,j\leq
  n}=A$. Comme $A^{(1)}$ est inversible, il existe au moins un
coefficient de la $1$\`ere colonne de $\An{1}$ qui est non nul. Quitte
\`a permuter la $1$\`ere ligne avec une ligne $i$ on a $\Atil{1}=P_1
\An{1}$ avec $\atil{1}_{1,1}\neq 0$ (la matrice $P_1$ \'etant
\'eventuellement la matrice identit\'e). Pour \'eliminer les
coefficients de la $1$\`ere colonne des lignes $i$ pour $i\geq 2$, on
multiplie $\Atil{1}$ (\`a gauche) par $E_1$ avec

 $$
 E_1=\left(
 \begin{BMAT}(b){cccccc}{cccccc}
 1 & 0 & \cdots & \cdots & \cdots &  0 \\
 -{\atil{1}_{2,1}}/{\atil{1}_{1,1}} 
  & 1 & 0 & \cdots & \cdots & 0 \\
 -{\atil{1}_{3,1}}/{\atil{1}_{1,1}} & 0 & 1 & 0 &  & 0\\
\vdots & \vdots  & \ddots & \ddots & \ddots & \vdots \\
-{\atil{1}_{n-1,1}}/{\atil{1}_{1,1}} & \vdots & & \ddots &  1 & 0 \\
-{\atil{1}_{n,1}}/{\atil{1}_{1,1}} & 0  &\cdots &\cdots &  0 & 1 
\addpath{(0,0,.)uuuuurddddd}
 \end{BMAT}\right)
 $$
et on obtient $\An{2}=E_1\Atil{1}$ 
$$
\An{2}=\left(
\begin{BMAT}(@){cc}{c.c}
\atil{1}_{1,1} & 
\begin{BMAT}(b){cccc}{c}
\atil{1}_{1,2} & \cdots & \cdots & \atil{1}_{1,n} \\
\end{BMAT}\\
\begin{BMAT}(b){c}{ccc}
0 \\
\vdots \\
0
\end{BMAT} & 
\left(\begin{BMAT}(e)[2pt,2cm,2cm]{c}{c}
(\an{2}_{i,j})_{2\leq i,j\leq n}
\end{BMAT}
\right)
\addpath{(1,0,.)u}
\end{BMAT}
\right)
$$
\par
\noindent{\sffamily \'Etape 2 : } les matrices $E_1$ et $\Atil{1}$ \'etant inversibles, il existe au
moins un coefficient $i_0$ tel que $i_0\geq 2$ et $\an{2}_{i_0,2}\neq
0$ (sinon les deux premi\`eres colonnes de $\An{2}$ seraient
li\'ees). Quitte \`a permuter la ligne $2$ et la ligne $i_0$, on a donc
$\Atil{2}=P_2\An{2}$
(o\`u $P_2$ est la matrice identit\'e ou une matrice de permutation de
lignes) avec 
$$
\Atil{2}=\left(
\begin{BMAT}(@){cc}{c.c}
\atil{1}_{1,1} & 
\begin{BMAT}(b){cccc}{c}
\atil{1}_{1,2} & \cdots & \cdots & \atil{1}_{1,n} \\
\end{BMAT}\\
\begin{BMAT}(b){c}{ccc}
0 \\
\vdots \\
0
\end{BMAT} & 
\left(\begin{BMAT}(e)[2pt,2cm,2cm]{c}{c}
(\atil{2}_{i,j})_{2\leq i,j\leq n}
\end{BMAT}
\right)
\addpath{(1,0,.)u}
\end{BMAT}
\right) \qquad\text{ et } \atil{2}_{2,2}\neq 0.
$$
Pour \'eliminer les termes $\atil{2}_{i,2}$ pour $i\geq 3$, il suffit
de multiplier (\`a gauche) $\Atil{2}$ par $E_2$
$$
E_2=\left(
\begin{BMAT}(b){cccccc}{cccccc}
 1 & 0 & \cdots & \cdots & \cdots &  0 \\
0 & 1 & 0 & \cdots & \cdots & 0 \\
0 & -{\atil{2}_{3,2}}/{\atil{2}_{2,2}} 
  & 1 & 0 &  \cdots & 0 \\
\vdots & -{\atil{2}_{4,2}}/{\atil{2}_{2,2}} & 0 & 1 &   & \vdots\\
\vdots & \vdots  & \vdots & \ddots & \ddots & 0 \\
0 & -{\atil{2}_{n,2}}/{\atil{2}_{2,2}} & 0  &\cdots &  0 & 1 
\addpath{(1,0,.)uuuurdddd}
 \end{BMAT}\right)
 $$
pour obtenir $\An{3}=E_2\Atil{2}$
$$
\An{3}=\left(
\begin{BMAT}(@){ccc}{ccc}
\atil{1}_{1,1} & \, \atil{1}_{1,2}\, &
\begin{BMAT}(b){cccc}{c}
\atil{1}_{1,3} & \cdots & \cdots & \atil{1}_{1,n} \\
\end{BMAT}\\
0 & \atil{2}_{2,2} & \begin{BMAT}(b){cccc}{c}
\atil{2}_{2,3} & \cdots & \cdots & \atil{2}_{2,n} 
\end{BMAT} \\
\begin{BMAT}(b){c}{ccc}
\vdots \\
\vdots  \\
0
\end{BMAT} & 
\begin{BMAT}(b){c}{ccc}
0 \\
\vdots \\
0
\end{BMAT} &
\left(\begin{BMAT}(e)[2pt,2cm,2cm]{c}{c}
(\an{3}_{i,j})_{3\leq i,j\leq n}
\end{BMAT}
\right)
\addpath{(2,0,.)ulul}
\addpath{(2,1,.)r}
\end{BMAT}
\right) 
$$
Comme $\An{3}$ est inversible ($E_2$ et $\Atil{2}$ le sont), $P_3$ d\'esignant une matrice
permutant deux lignes ou la matrice identit\'e on a
$\Atil{3}=P_3\An{3}$ 
$$
\Atil{3}=\left(
\begin{BMAT}(@){ccc}{ccc}
\atil{1}_{1,1} & \, \atil{1}_{1,2}\, &
\begin{BMAT}(b){cccc}{c}
\atil{1}_{1,3} & \cdots & \cdots & \atil{1}_{1,n} \\
\end{BMAT}\\
0 & \atil{2}_{2,2} & \begin{BMAT}(b){cccc}{c}
\atil{2}_{2,3} & \cdots & \cdots & \atil{2}_{2,n} 
\end{BMAT} \\
\begin{BMAT}(b){c}{ccc}
\vdots \\
\vdots \\
0
\end{BMAT} & 
\begin{BMAT}(b){c}{ccc}
0 \\
\vdots \\
0
\end{BMAT} &
\left(\begin{BMAT}(e)[2pt,2cm,2cm]{c}{c}
(\atil{3}_{i,j})_{3\leq i,j\leq n}
\end{BMAT}
\right)
\addpath{(2,0,.)ulul}
\addpath{(2,1,.)r}
\end{BMAT}
\right) \qquad\text{ et } \atil{3}_{3,3}\neq 0
$$
\par
\noindent{\sffamily \ldots \'Etape $k$ :} on suppose que l'on a obtenu
la matrice $\An{k}$ dont les $k-1$ premi\`eres colonnes sont remplies
de z\'eros sous la diagonale et $\An{k}$ inversible, de la forme
$$
\An{k}=\left(
  \begin{BMAT}(@){cc}{cc}
\begin{BMAT}(b)[2pt,5.4cm,3.7cm]{cccc}{cccc}
\atil{1}_{1,1} & \atil{1}_{1,2} & \cdots &\cdots \\
0 & \atil{2}_{2,2} & \cdots & \cdots \\
\vdots & 0 & \ddots & \\
\vdots & \vdots & &  \atil{k-1}_{k-1,k-1} 
\addpath{(4,0,.)lu}
\addpath{(0,3,.)rdr}
\end{BMAT} 
&
\begin{BMAT}(b)[0pt,3.4cm,3.7cm]{ccc}{cccc} \cdots 
&\cdots &  \atil{1}_{1,n} \\
\cdots & \cdots & \atil{2}_{2,n} \\
 & \ &  \vdots \\
 &  \phantom{\cdots} & \phantom{0} \\
\end{BMAT} 
\\
\begin{BMAT}(b)[2pt,5.4cm,2.9cm]{cccc}{cccc}
 \vdots &  \vdots   & \ & 0 \\
 \vdots & \  & \  & \vdots\\
 \vdots & \  & \  & \vdots\\
0 & \cdots & \cdots & 0
\end{BMAT} 
& \left(\begin{BMAT}(e)[2pt,3.4cm,2.9cm]{c}{c}
(\an{k}_{i,j})_{k\leq i,j\leq n}
\end{BMAT}
\right) 
\addpath{(1,0,.)ur}
\end{BMAT}\right).
$$
La matrice $\An{k}$ \'etant inversible, quitte \`a permuter la ligne
$k$ avec une ligne $i_0$ (avec $i_0\geq k+1$), on a  $\Atil{k}=P_k\An{k}$ telle que
$$
\An{k}=\left(
  \begin{BMAT}(@){cc}{cc}
\begin{BMAT}(b)[2pt,5.4cm,3.7cm]{cccc}{cccc}
\atil{1}_{1,1} & \atil{1}_{1,2} & \cdots &\cdots \\
0 & \atil{2}_{2,2} & \cdots & \cdots \\
\vdots & 0 & \ddots & \\
\vdots & \vdots & &  \atil{k-1}_{k-1,k-1} 
\addpath{(4,0,.)lu}
\addpath{(0,3,.)rdr}
\end{BMAT} 
&
\begin{BMAT}(b)[0pt,3.4cm,3.7cm]{ccc}{cccc} \cdots 
&\cdots &  \atil{1}_{1,n} \\
\cdots & \cdots & \atil{2}_{2,n} \\
 & \ &  \vdots \\
 &  \phantom{\cdots} & \phantom{0} \\
\end{BMAT} 
\\
\begin{BMAT}(b)[2pt,5.4cm,2.9cm]{cccc}{cccc}
 \vdots &  \vdots   & \ & 0 \\
 \vdots & \  & \  & \vdots\\
 \vdots & \  & \  & \vdots\\
0 & \cdots & \cdots & 0
\end{BMAT} 
& \left(\begin{BMAT}(e)[2pt,3.4cm,2.9cm]{c}{c}
(\atil{k}_{i,j})_{k\leq i,j\leq n}
\end{BMAT}
\right) 
\addpath{(1,0,.)ur}
\end{BMAT}\right) \qquad\text{ et } \atil{k}_{k,k}\neq 0.
$$
On peut alors proc\'eder \`a l'\'elimination par la multiplication
(\`a gauche) de $\Atil{k}$ par $E_k$, $\An{k+1}=E_k\Atil{k}$ avec
$$
E_k=\left(
  \begin{BMAT}(@){cc}{cc}
    \begin{BMAT}(@)[2pt,4cm,4cm]{ccccc}{ccccc}
      1 & 0 & 0 & \quad & \quad \\
      0 & 1 & 0 &        &   \\
      0 & 0 & 1 &        &   \\
      &   &   & \ddots & \\
      &   &   &        & 1 
    \end{BMAT} 
    & 
    \begin{BMAT}(@)[2pt,8cm,4cm]{ccccc}{ccccc}
      0 &  \cdots & \quad &  & 0 \\
      \phantom{ -\atil{k}_{k+1,k}/\atil{k}_{k,k}}  &         &       &       &   \\
      &         &  \strut{\makebox[0cm][c]{\Huge 0}}     &       &   \\
      \vdots &    &       &       &   \\
      0 &         &       &       & 0 
    \end{BMAT}
    \\
    \begin{BMAT}(@)[2pt,4cm,4cm]{c}{c}
      \text{\Huge 0}
    \end{BMAT} &
    \protect{          
      \begin{BMAT}(@)[2pt,8cm,5cm]{ccccc}{ccccc}
        1 & 0 & & & \\
        -\atil{k}_{k+1,k}/\atil{k}_{k,k} &\  1 &\  0 &\  & \\
        -\atil{k}_{k+2,k}/\atil{k}_{k,k} & 0 & 1 & & \\
        \vdots &                            &  & \ddots & \\
        -\atil{k}_{n,k}/\atil{k}_{k,k} &  &  & & \ 1            
        % \addpath{(2,3,.)rd}
      \end{BMAT}}
  \end{BMAT}\right)
$$
et $\An{k+1}$ de la forme
$$
\An{k+1}=\left(
  \begin{BMAT}(@){cc}{cc}
\begin{BMAT}(b)[2pt,6.4cm,4.3cm]{ccccc}{ccccc}
\atil{1}_{1,1} & \atil{1}_{1,2} & \cdots & & \cdots \\
0 & \atil{2}_{2,2} & \cdots & \cdots &  \cdots  \\
\vdots & 0 & \ddots &  & \\
\vdots & \vdots & &  \atil{k-1}_{k-1,k-1} &\cdots \\
\vdots & \vdots & &  & \an{k}_{k,k} 
\addpath{(5,0,.)lulu}
\addpath{(0,4,.)rdr}
\end{BMAT} 
&
\begin{BMAT}(b)[0pt,3.4cm,4.3cm]{ccc}{ccccc} \cdots 
&\cdots &  \atil{1}_{1,n} \\
\cdots & \cdots & \atil{2}_{2,n} \\
 & \ &  \vdots \\
 \cdots & \ & \atil{k-1}_{k-1,n} \\
\cdots &  \phantom{\cdots} & \an{k}_{k,n} 
\end{BMAT} 
\\
\begin{BMAT}(b)[2pt,7.3cm,2.9cm]{ccccc}{cccc}
 \vdots &  \vdots &\   & \ & 0 \\
 \vdots & \  & \  & & \vdots\\
 \vdots & \  & \  & & \vdots\\
0 & \cdots & \cdots & & 0
\end{BMAT} 
&\left( \begin{BMAT}(e)[2pt,3.4cm,2.9cm]{c}{c}
(\an{k+1}_{i,j})_{k+1\leq i,j\leq n} 
\end{BMAT}\right)
\addpath{(1,0,.)ur}
\end{BMAT}\right).
$$
\par\medskip
Apr\`es $n-1$ \'etapes on obtient $\An{n}=\big(E_{n-1}P_{n-1}\cdots
E_{1} P_{1}\big)$ triangulaire sup\'erieure. La matrice $M$
d\'efinie par $M=E_{n-1}P_{n-1}\cdots E_{1} P_{1}$ v\'erifie le
r\'esultat demand\'e. Comme $E_{i}$ et $P_{i}$ sont inversibles pour
tout $1\leq i \leq n-1$, $M$ est inversible. R\'esoudre $\An{n}x=Mb$
est donc \'equivalent \`a r\'esoudre $Ax=b$.
\end{proof}


Voici une proc\'edure Maple \'el\'ementaire qui ex\'ecute la m\'ethode
du pivot de Gauss, sans permutation de ligne.
\begin{lstlisting}{}
restart;with(linalg): #charge le paquet linalg qui ajoute des
#   fonctions Maple concernant l'algèbre linéaire
gauss:=proc(A,b)
local AA,bb,i,j,k,p,n,solx;
n:=coldim(A);
AA:=matrix(n,n);  # AA matrice carrée vide de taille de n
AA:=copy(A);  # si on fait AA:=A alors toute modification faite sur 
bb:=copy(b);  # AA l'est aussi sur A, on utilise donc copy, idem pour b
solx:=vector(n);  # solx vecteur de taille n
#élimination
for k to n-1 do
    for i from k+1 to n do
        if (AA[k,k]=0) then error (`pivot nul`) fi;
        p:=AA[i,k]/AA[k,k];
        for j from k+1 to n do
            AA[i,j]:=AA[i,j]-AA[k,j]*p;
        od;
        bb[i]:=bb[i]-bb[k]*p;
        AA[i,k]:=0;
    od;
od;
# remontée
solx[n]:=bb[n]/AA[n,n];
i:=n-1;
for i from n-1 to 1 by -1 do
solx[i]:=(bb[i]-add(AA[i,j]*solx[j],j=i+1..n))/AA[i,i];
od;
evalm(solx);
end proc;
\end{lstlisting}
\begin{exer}{} Recompter le nombre de multiplications effectu\'ees
en fonction de $n$  dans le programme pr\'ec\'edent. Faire une version {\tt gauss1} qui permute les
  lignes si n\'ecessaire et utilise les fonctions Maple {\tt addrow},
  {\tt  swaprow} et  une version {\tt gauss2} qui utilise la
  strat\'egie du pivot partiel.   
\end{exer}

\subsection{Pivots non nuls}

On d\'emontre par r\'ecurrence qu'il n'est pas n\'ecessaire de permuter les lignes
(i.e. pour tout $1\leq k\leq n$ $\an{k}_{k,k}\neq 0$) si 
et seulement si toutes les sous-matrices
principales de $A$ sont inversibles. Clairement  $\Delta_1$ est
inversible si et seulement si $\det \Delta_1=a_{1,1}\neq 0$ ; l'\'elimination est
possible avec la ligne $1$ de $\An{1}=A$. Supposons que pour tout
$i\in\{1,\ldots,k-1 \}$ on ait $\an{i}_{i,i}\neq 0$. Dans le processus
d'\'elimination jusqu'\`a l'\'etape $k-1$, aucune permutation de ligne
n'a \'et\'e n\'ecessaire, ainsi $\An{k}=E_{k-1} E_{k-2} \cdots E_{1}
\An{1}$ et $\Atil{i}=\An{i}$ $\forall i\in\{1,\ldots,k-1\}$. Rappelons
que le d\'eterminant d'une matrice est inchang\'e quand on ajoute \`a
une ligne une combinaison lin\'eaire des autres lignes. Chaque \'etape
$i\in\{1,\ldots,k-1\}$ consiste \`a ajouter aux lignes $j\geq i+1$ un
facteur de la ligne $i$, ce qui entra\^\i ne $\det A=\det \An{k}$. Si
on restreint les op\'erations effectu\'ees \`a la sous-matrice
principale d'ordre $k$ de $A$, on obtient par le m\^eme argument que 
$$
\det \Delta_k= 
\left|
\begin{BMAT}(e){cccc}{cccc}
\an{1}_{1,1} & \an{1}_{1,2} & \cdots &\cdots \\
0 & \an{2}_{2,2} & \cdots & \cdots \\
\vdots & \ddots & \ddots & \\
0 & \cdots & 0  &  \an{k}_{k,k} 
\end{BMAT} 
\right|=\an{1}_{1,1}\times \an{1}_{1,2}\times \cdots \times  \an{k}_{k,k}. 
$$
Une autre fa\c con est de montrer que la structure triangulaire
inf\'erieure des matrices $E_i$ ($1\leq i\leq k-1$) entra\^\i ne que $(\An{k})_k=(E_{k-1})_k
(E_{k-2})_k \cdots (E_{1})_k \Delta_k$, o\`u $(\cdot)_k$ d\'esigne la
sous matrice principale d'ordre $k$ (utiliser les matrices blocs).
\par
Finalement $\det \Delta_k\neq 0$ \'equivaut \`a $\an{1}_{1,1}\times
\an{1}_{1,2}\times \cdots \times  \an{k}_{k,k}\neq 0$, soit
$\an{i}_{i,i}\neq0$ pour tout $i\in\{1,\ldots,k\}$. Le r\'esultat est
d\'emontr\'e par r\'ecurrence.





\section{D\'ecomposition de Cholesky}
\subsection{Rappel et th\'eor\`eme}
\begin{defi}
  Une matrice $A\in\cm_n(\R)$ est dite sym\'etrique d\'efinie positive
  si
  \begin{enumerate}
  \item $A^t=A$ ($A$ sym\'etrique)
  \item $x^t A x\geq 0$, \quad $\forall x\in\R^n$ ($A$ positive)
  \item $x^t Ax=0$ si et seulement si $x=0$ ($A$ d\'efinie)
  \end{enumerate}
\end{defi}


\begin{exer}
  Si $A\in\cm_n(\R)$ est sym\'etrique-d\'efinie-positive alors $\det A>0$
  et $A$ admet $n$ valeurs propres r\'eelles strictement
  positives. [chercher dans vos cours d'alg\`ebre, exercices, livres$\ldots$]
\end{exer}

\begin{prop}\label{sym}
Soit $A\in\cm_n(\R)$ une matrice sym\'etrique d\'efinie
positive. Alors toutes ses sous-matrices principales sont
sym\'etriques d\'efinies positives.  
\end{prop}
\begin{proof}
Notons $\Delta_k$ la sous-matrice principale de $A$ d'ordre $k$, qui 
est clairement sym\'etrique. Si $k=n$ c'est \'evident. Soient
$k\in\{1,\ldots,n-1\}$ et $z\in\R^k$ et d\'emontrons les points (2) et
(3) de la d\'efinition. L'id\'ee est de compl\'eter
le vecteur $z$ en un vecteur de $\R^n$ par 
$$y=
\begin{pmatrix}
  z_1 \\ \vdots \\ z_k \\ 0 \\ \vdots \\ 0
\end{pmatrix}\in\R^n.
$$
Clairement on a $y^t A y=z^t \Delta_k z \geq 0$, ce qui entra\^\i ne
$\Delta_k$ positive. De plus $y^t A y=z^t \Delta_k z=0$ \'equivaut
\`a $y=0$ (dans $\R^n$), soit $z=0$ (dans $\R^k$). La matrice
$\Delta_k$ est donc sym\'etrique d\'efinie positive.
\end{proof}

\begin{theo}[D\'ecomposition de Cholesky]
  Soit $A\in\cm_n(\R)$ une matrice sym\'etrique d\'efinie
  positive. Alors il  existe une unique matrice $T$ triangulaire
  inf\'erieure dont les termes de la diagonale sont positifs telle que
  $A=T T^t$. Une telle d\'ecomposition est appel\'ee d\'ecomposition
  de Cholesky.
\end{theo}
\begin{proof}
  D'apr\`es la proposition \ref{sym} (et l'exercice) nous savons que
  toutes les sous-matrices principales de $A$ sont de d\'eterminant
  non nul. La matrice $A$ admet donc une d\'ecomposition $LU$, la
  diagonale de $L$ n'\'etant compos\'ee que de $1$. De plus $\det
  \Delta_k=\prod_{i=1}^k u_{i,i}>0$ pour tout $k>0$ ce qui entra\^\i
  ne $u_{i,i}>0$ pour tout $i\in\{1,\ldots,n\}$. Posons
  $D=\text{diag}(\sqrt{u_{1,1}},\ldots,\sqrt{u_{n,n}}) $ matrice
  diagonale dont les coefficients de la diagonale sont respectivement
  $\sqrt{u_{1,1}},\ldots,\sqrt{u_{n,n}}$. Alors $A=L D D^{-1}
  U=(LD)(D^{-1}U)$. 
  \par
  Montrons que $T=LD$ convient, ce qui revient \`a
  d\'emontrer que $D^{-1} U=(L D)^t$. Comme $A$ est sym\'etrique
  l'\'egalit\'e $A^t=A$
  nous donne $U^t L^t=A$, soit $(U^t D^{-1}D^{-1})(D D L^t)=A$. D'apr\`es
  la d\'efinition de $D$, la matrice $U^t D^{-1}D^{-1}$ est une
  matrice triangulaire inf\'erieure avec des $1$ sur la diagonale et il est
  \'evident que $DDL^t$ est une matrice triangulaire
  sup\'erieure. Ainsi l'unicit\'e de la d\'ecomposition $LU$ entra\^\i
  ne que $L=U^t  D^{-1}D^{-1}$, d'o\`u $T^t=(LD)^t=(U^t
  D^{-1})^t=D^{-1} U$ [depuis le d\'ebut on utilise le fait que la
  transpos\'ee d'une matrice diagonale est elle-m\^eme]. 
\par
Montrons l'unicit\'e d'une telle d\'ecomposition. Soit $A=M M^t$ une
autre d\'ecomposition de Cholesky. L'\'egalit\'e $M M^t=T T^t$ nous
donne $T^{-1} M= T^t (M^t)^{-1}$, avec $T^{-1}M$ triangulaire
inf\'erieure et $T^t(M^t)^{-1}$ triangulaire sup\'erieure. Donc
$T^{-1} M$ est une matrice diagonale, not\'ee $D'$. Ajoutons que comme
$T^{-1}$ et $M$ sont des matrices triangulaires inf\'erieures dont les
coefficients de la diagonale sont positifs, il en est de m\^eme pour
$D'$. L'\'egalit\'e $T T^t=A=M M^t=T D' (TD')^t=TD' D' T^t$ implique que
$D'D'=I$. Du fait que les coefficients de $D'$ soient positifs nous en
d\'eduisons que $D'=I$, soit $M=T$.
\end{proof}



\par\bigskip
\subsection{Algorithme et nombre d'op\'erations \'el\'ementaires}
La m\'ethode pour trouver la d\'ecomposition de Cholesky est
d'\'ecrire $A=T T^t$ et d'identifier les coefficients de fa\c con
progressive. Commencer avant de lire la suite par faire un dessin
pour $T T^t\ldots$ puis \'ecrire l'algorithme correspondant (voir plus
loin le dit-algorithme).
\begin{algorithm}
\caption{D\'ecomposition de Cholesky}
\begin{algorithmic}[1]
  \STATE $t_{1,1}\leftarrow \sqrt{a_{1,1}}$
  \FOR{$i=2$ to $n$}
  \STATE $\displaystyle t_{i,1}\leftarrow 
  \frac{a_{1,i}}{t_{1,1}}$ \rule[0cm]{0cm}{4ex}
  \ENDFOR
  \FOR{ $k=2$ to $n-1$}
  \STATE $\displaystyle t_{k,k}\leftarrow (a_{k,k}-\sum_{i=1}^{k-1}
  t_{k,i}^2)^{1/2}$
  \rule[0cm]{0cm}{4ex}
  \FOR { $i=k+1$ to $n$}
  \STATE $\displaystyle t_{i,k}\leftarrow \big(a_{i,k}-\sum_{j=1}^{k-1} t_{i,j}t_{j,k}\big)
  /t_{k,k}$ \rule[0cm]{0cm}{4ex}
  \ENDFOR
  \ENDFOR
  \STATE $t_{n,n}\leftarrow \displaystyle\big(a_{n,n}-\sum_{i=1}^{n-1} t_{n,j}^2\big)^{1/2}$
\end{algorithmic}
\end{algorithm}

Pour les op\'erations \'el\'ementaires il faut distinguer ici les
additions-soustractions,
les multiplica\-tions-divisions et les extractions de racines (bien plus
compliqu\'ees).
\begin{itemize}
\item[\sffamily les $\mathbf {\sqrt{}}$:] ligne 3, $n-2$ lignes 8 et ligne
  11 ce qui fait $n$ extractions de racine 
\item[\sffamily les $\mathbf\times\div$:] ligne 3 : $n-1$, lignes 6 et 8 :
  $\displaystyle \sum_{k=2}^{n-1}\big[(k-1)+ \sum_{i=k+1}^n k\big]$,
  ligne 11 : $n-1$. D'o\`u un total 
$$n-1+\frac{(n-2)(n-1)}{2}+\big[\sum_{k=2}^{n-1} k(n-k)\big]
+n-1=\frac{n^3}{6}+\frac{n^2}{2}+ \frac{2n}{3}\approx
\frac{n^3}{6}$$
\item[\sffamily les $+-$:] on trouve 
$$
\frac{n^3-n}{6}\approx \frac{n^3}{6}
$$
\end{itemize}
Le temps de calcul des $n$ extractions de racine est n\'egligeable
devant les $n^3/3$ op\'erations \'el\'ementaires. Finalement la
d\'ecomposition de Cholesky n\'ecessite de l'ordre de $n^3/3$
op\'erations \'el\'ementaires, ce qui est moins comparativement \`a la
d\'ecomposition $LU$.

\begin{rmq}
 Si on sait que la matrice $A$ est sym\'etrique
d\'efinie positive il donc plus int\'eressant de chercher sa
d\'ecomposition de Cholesky plut\^ot que sa d\'ecomposition $LU$. Pour
des raisons non d\'evelopp\'ees dans ce cours, les matrices sym\'etriques
d\'efinies positives interviennent naturellement en analyse
num\'erique car issues d'un produit scalaire.
\end{rmq}

\subsection{Un exemple} 
Soit la matrice $A$
$$
\begin{pmatrix}
4&-6&8&2\cr -6&10&-15&-3\cr 8&-15&26&-1\cr 2&-3&-1&62
\end{pmatrix}
$$
%\newpage
Faisons le dessin
\par
\begin{tabular}{ll}
\null & $
\begin{pmatrix}
t_{1,1} & t_{2,1} & t_{3,1} & t_{4,1} \\
0 &  t_{2,2} & t_{3,2} & t_{4,2} \\
0 & 0 &  t_{3,3} & t_{4,3} \\
0 & 0 & 0 & t_{4,4}
\end{pmatrix}
$
\\[1cm]
$
\begin{pmatrix}
t_{1,1} & 0 & 0 & 0 \\
t_{2,1} & t_{2,2} & 0  &0 \\
t_{3,1} & t_{3,2} & t_{3,3} & 0 \\
t_{4,1} & t_{4,2} & t_{4,3} & t_{4,4} 
\end{pmatrix}
$
&
$
\begin{pmatrix}
4&-6&8&2\cr -6&10&-15&-3\cr 8&-15&26&-1\cr 2&-3&-1&62
\end{pmatrix}
$
\end{tabular}

\begin{enumerate}
\item  $ t_{1,1}^2=4 \quad\Rightarrow\quad t_{1,1}=2$
\item $2t_{2,1}=-6\quad\Rightarrow\quad t_{2,1}=-3$
\item $2t_{3,1}=8\quad\Rightarrow\quad t_{3,1}=4$
\item $2t_{4,1}=2\quad\Rightarrow\quad t_{4,1}=1$
\item $(-3)^2+t_{2,2}^2=10\quad\Rightarrow\quad t_{2,2}=1$
\item  $(-3)\times 4+t_{3,2}=-15\quad\Rightarrow\quad
  t_{3,2}=-3$
\item $-3+t_{4,2}=-3\quad\Rightarrow\quad t_{4,2}=0$
\item  $4^2+(-3)^2+t_{3,3}^2= 26\quad\Rightarrow\quad
    t_{3,3}=1$
\item $4\times 1+ t_{4,3}=-1\quad\Rightarrow\quad
    t_{4,3}=-5$
\item $1^2+0^2+(-5)^2+t_{4,4}^2=62\quad\Rightarrow\quad t_{4,4}=6$
\end{enumerate}













\end{document}




