%&LaTeX
\documentclass[a4paper,12pt]{article}
\usepackage{amssymb,latexsym,amsmath,amsthm,amscd,graphpap}
%\documentclass{article}
%\usepackage{a4}
%\usepackage{vmargin}
\usepackage{amsmath}
\usepackage{amsfonts}
\usepackage{amssymb}
\usepackage[dvips]{epsfig}
%\usepackage{epsfig}

%\setpapersize{A4}
%\setmarginsrb{2cm}{2cm}{2cm}{2cm}{0cm}{0cm}{1.5cm}{1cm}
%%%%%%%%%%%%
  \oddsidemargin -10 pt      %   Left margin on odd-numbered pages.
    \evensidemargin 10 pt      %   Left margin on even-numbered pages.
    \marginparwidth 1 in       %   Width of marginal notes.
   \oddsidemargin 0 in      %   Note that \oddsidemargin = \evensidemargin
    \evensidemargin 0 in
    \marginparwidth 0.75 in
    \textwidth 6.375 true in % Width of text line.00000
    \footskip 0.5 in


\newtheorem{theorem}{Theorem}[section]
\newtheorem{prop}{Proposition}[section]
\newtheorem{defi}{Definition}[section]
\newtheorem{propr}{Property}[section]
\newtheorem{lemme}{Lemma}[section]
%\newtheorem{rem}{Remarque}[section]
\newtheorem{hyp}{Hypoth?ses}[section]
\newtheorem{coro}{Corollary}[section]
\newtheorem{nota}{Notations}[section]
\newenvironment{dem}{\emph{\textbf{Proof:}}}{\hfill $\square$}
\newenvironment{cor}{\emph{\textbf{Corollary :}}}{}
\newenvironment{con}{\emph{\textbf{Conjectures:}}}{}
\newenvironment{demo}{ \noindent \emph{\textbf{Proof :}}}{\hfill
$\square$\\ \bigskip}
\newenvironment{ques}{ \bigskip $\;$\\\noindent \emph{\textbf{Questions
      ouvertes       :\\}}}{  \bigskip \\} 
\newenvironment{rem}{ \noindent \emph{\textbf{Remark :}}}{  \bigskip \\}

\newcommand{\Rm}{\mathbb{R}}
\newcommand{\Lm}{\mathbb{L}}
\newcommand{\lm}{\mathcal{L}}
\newcommand{\Lc}{\mathcal{L}}
\newcommand{\Mm}{\mathcal{M}}
\newcommand{\Nm}{\mathbb{N}}
\newcommand{\Hm}{\mathbb{H}}
\newcommand{\Com}{\mathbb{C}}
\newcommand{\Unm}{\mathbb{I}}
\newcommand{\Gm}{\mathfrak{G}}
\newcommand{\Cm}{\mathcal{C}}
\newcommand{\Em}{\mathcal{E}}
\newcommand{\Am}{\mathcal{A}}
\newcommand{\Xm}{\mathcal{X}}
\newcommand{\Bm}{\mathcal{B}}
\newcommand{\Pm}{\mathcal{P}}
\newcommand{\Dm}{\mathcal{D}}
\newcommand{\Um}{\mathcal{U}}
\newcommand{\Vm}{\mathcal{V}}
\newcommand{\Sn}{\mathfrak{S}_n}
\newcommand{\Zm}{\mathcal{Z}}
\newcommand{\Drond}[2]{\frac{\partial #1}{\partial #2}}
\newcommand{\Dnu}[1]{\Drond #1 \nu}
\newcommand{\Diff}{\mathbb{D}\text{iff}^k_{id}(Q)}
\newcommand{\Difflocal}{\mathbb{D}\text{iff}^k_{id}(\Theta)}
\newcommand{\Dom}{\mathbb{H}^2 \cap \mathbb{H}^1_0}
\newcommand{\Domo}{\mathbb{H}^2(\Omega) \cap \mathbb{H}^1_0(\Omega)}
%\newcommand{\grad}{\stackrel{\rightarrow}{\nabla}}
\newcommand{\grad}{\overrightarrow{\nabla}}
\newcommand{\cbb}{\Cm^{2,\beta}}
\newcommand{\deuxvect}[2]{\left(\begin{array}{c}#1 \\ #2
    \end{array}\right)} 
\newcommand{\ch}{\text{ch}}


\newcounter{numeroexo}
\newcommand{\exercice}{ 

\vspace{0.5cm}

\noindent\stepcounter{numeroexo}{\bf{Exercice \arabic{numeroexo}~:~}}}

\newcommand{\partie}[1]{ 

\vspace{1cm}

\noindent{\large \bf \underline{#1}}}







\begin{document}

\noindent M\'ethodes num\'eriques \hfill Feuille 2: Syst\`emes lin\'eaires (m\'ethodes
directes) \hfill {L3 2013/2014}\\

%\vspace{1.2cm}

{\small
%\exercice Soit $E_{ij}(\lambda)$ la matrice \'egale \`a l'identit\'e
%sauf pour le coefficient $(i,j)$ qui vaut $\lambda$. Soit $A$ une
%matrice quelconque. Comment la multiplication \`a droite et \`a gauche
%par $E_{ij}(\lambda)$ agit-elle sur $A$ ?

\exercice Appliquer la m\'ethode de Gauss pour r\'esoudre le syst\`eme
$Ax=b$ o\`u
$$
A=\left(
  \begin{array}{cc}
    \varepsilon & 1\\
    1 & 1
  \end{array}
\right)
\qquad 
b=\left(
  \begin{array}{l} 
    1 \\ 
    2 
  \end{array}
\right)
$$
\begin{enumerate}
\item
Cette m\'ethode para\^it-elle judicieuse quand $\varepsilon$ est
petit?
Que se passe-t-il si l'on effectue cette m\'ethode avec une machine qui
travaille avec une pr\'ecision absolue de $\varepsilon$? 
\item Comparer avec
le syst\`eme obtenu en intervertissant les deux \'equations du syst\`eme.
\end{enumerate}

\exercice Soit
$$A=\left(\begin{array}{cc} 1&4\\
    -1&2 \end{array}\right)~~~~B=\left(\begin{array}{ccc} -2& 3&0\\
    1&0&-4\\ 2&0&5 \end{array}\right)~.$$
\begin{enumerate}
\item D\'etailler \'etape par \'etape le calcul de la d\'ecomposition
  $LU$ des matrices $A$ et $B$
\item
Calculer le d\'eterminant de $B$ \`a l'aide de cette d\'ecomposition.
\item R\'esoudre $Bx=(1,2,3)$ en utilisant la d\'ecomposition $LU$.
\item Calculer l'inverse de $B$ en r\'esolvant 3 syst\`emes lin\'eaires avec
la d\'ecomposition $LU$.
\end{enumerate}

\exercice \\
Soit $\alpha$ un param\`etre r\'eel.
On consid\`ere la matrice 
$$
A(\alpha)=
\left(
\begin{array}{ccc}
 \alpha & 1 \\
1&2 
\end{array}
\right)
.$$
\begin{enumerate}
\item Pour quels $\alpha$ la matrice $A(\alpha)$ admet-t'elle une
  factorisation $LU$? 
\item D\'eterminer la factorisation $LU$ de $A(1)$ \`a l'aide de la commande Xcas \texttt{lu}.
Interpr\'eter le r\'esultat de la commande \texttt{lu}
  appliqu\'ee \`a $A(0)$.
\end{enumerate}

\exercice \\
1) Entrer une matrice al\'eatoire $A$ de taille 5x5 et un vecteur al\'eatoire $b$ de taille 5x1
 (pr\'eciser la loi des coefficients de $A$ et $b$, commandes
 \verb|ranm| et \verb|ranv|) \\
2) Calculer le carr\'e de A. 
Calculer aussi le produit de Hadamard de $A$ avec $A$, 
c'est \`a dire la matrice dont le coefficient $(i,j)$ est $A_{i,j}^2$.\\
3) Inverser num\'eriquement $A$. \\
4) Trouver et ex\'ecuter la commande Xcas pour r\'esoudre le syst\`eme lin\'eaire $Ax=b$. On notera $c$ le r\'esultat num\'erique. \\
5) Calculer la norme $L_2$ de $\|Ac-b\|$. \\

\exercice \\
Mesurer le temps de calcul par Xcas de la factorisation LU d'une
matrice al\'eatoire \`a coefficients approch\'es 10x10, 100x100, 200 x 200, etc.... 
Comparer avec le r\'esultat th\'eorique du cours. 

% \exercice L'exercice pr\'ec\'edent sugg\`ere la strat\'egie suivante
% (appel\'ee m\'ethode de Gauss avec pivot partiel): \`a l'\'etape $k$,
% avant d'introduire des z\'eros sous la diagonale dans la $k$-\`eme
% colonne, on commence par intervertir la $k$-\`eme ligne avec une ligne
% d'indice $l\geq k$, de fa\c{c}on \`{a} utiliser un pivot le plus grand
% possible en valeur absolue.

% Le but de cet exercice est de donner une interpr\'etation matricielle
% de la m\'ethode de Gauss avec pivot partiel. On notera $e_1,\dots,e_n$
% la base standard de $\Com^n$. Une matrice de permutation est par
% d\'efinition la matrice d'une transformation lin\'eaire qui permute
% ces $n$ vecteurs.
% \begin{enumerate}
% \item Montrer que chaque \'etape revient \`a multiplier \`a gauche par
%   $L^{(k)}P^{k}$, o\`u $P^{(k)}$ est une matrice de permutation qui
%   correspond \`a \'echanger $e_k$ avec $e_l$, pour un $l\geq k$, et
%   $L^{(k)}=I-B^{(k)}$ avec $B^{(k)}$ une matrice $n\times n$ qui est nulle sauf
% \'eventuellement dans la $k$-\`eme colonne, strictement sous la
% diagonale. En d'autres termes, $B^{(k)}_{ij}=0$ si $j\neq k$ ou si
% $i\leq j$.
% \item Montrer qu'avec les notations du point pr\'ec\'edent, on a pour
%   $l>k$
% $$
% P^{(l)}L^{(k)} = \tilde{L}^{(k)} P^{(l)}
% $$
% o\`u $\tilde{L}^{(k)}$ est obtenue \`a partir de $L^{(k)}$ en
% interchangeant deux \'el\'ements sous la diagonale.
% \item En d\'eduire que pour toute matrice inversible $A$, il existe une
%   matrice de permutation $P$, une matrice triangulaire inf\'erieure
%   \`a diagonale unit\'e $L$ et une matrice triangulaire sup\'erieure
%   $U$ telles que $A=PLU$. Cette \'ecriture est-elle unique?
% \end{enumerate}


% \exercice Dans cet exercice, on fixe $n\in\Nm^*$ et, pour $1\leq k
% \leq n$ on note $B^{(k)}$ une matrice $n\times n$ qui est nulle sauf
% \'eventuellement dans la $k$-\`eme colonne, strictement sous la
% diagonale. En d'autres termes, $B^{(k)}_{ij}=0$ si $j\neq k$ ou si
% $i\leq j$.
% 
% \begin{enumerate}
% \item D\'ecrire l'effet sur un matrice $A\in M_n(\Com)$ de la
%   multiplication \`a gauche par $(I-B^{(k)})$, et expliquer le lien
%   avec la m\'ethode de Gauss et la factorisation $LU$.
% \item Montrer que $B^{(k)}B^{(l)}=0$ si $k\leq l$.
% \item Montrer que $I-B^{(k)}$ est inversible, et que $(I-B^{(k)})^{-1}
%   = I+B^{(k)}$.
% \item Montrer que $(I+B^{(k)})(I+B^{(l)})=I+B^{(k)}+B^{(l)}$ si $k\leq
%   l$. Interpr\'eter ceci en termes de la factorisation $LU$.
% \end{enumerate}



%\exercice Soit $A\in M_n(\Com)$ une matrice hermitienne d\'efinie
%positive. Montrer que $A$ admet une unique d\'ecomposition $LU$.

%Indication: On pourra montrer que $A$ ainsi que toutes les
%sous-matrices principales $(A_{ij})_{1\leq i,j\leq k}$, $k=1,\dots, n$
%sont inversibles.



\exercice Donner l'ordre de grandeur du nombre d'op\'erations
n\'ecessaires pour calculer le d\'eterminant et l'inverse d'une
matrice A de taille $n\times n$ gr\^ace aux formules
$$\det(A)=\sum_{\sigma\in\Sigma_n}  \varepsilon(\sigma) a_{1\sigma(1)}a_{2\sigma(2)}...a_{n\sigma(n)}~~\text{ et }~~A^{-1}=\frac 1{\det(A)}~^t\text{com}(A)~.$$
M\^eme question mais en utilisant la d\'ecomposition $A=LU$ (m\'ethode de Gauss).\\
Un ordinateur standard effectue de l'ordre de $10^{10}$ op\'erations
par secondes (10 gigaflops). Comparer les temps n\'ecessaires dans le
cas d'une matrice $100\times 100$.

\exercice Calculer le d\'eterminant d'une matrice de Hilbert de taille 50 puis 100
de mani\`ere num\'erique et de mani\`ere exacte. Comparer les
r\'esultats et temps de calcul.\\
Pour quelques matrices $M$ al\'eatoires de taille 100, 200, 300, calculez le
d\'eterminant de $M$, comparez avec la borne de Hadamard de $M$
(produit des normes des vecteurs colonnes). Qu'observe-t-on~? 
La librairie d'alg\`ebre lin\'eaire num\'erique LAPACK ne propose aucune
instruction pour calculer le d\'eterminant d'une matrice...
%(cf. \verb|http://www.netlib.org/lapack/lug/node72.html|)

%\exercice {\bf D\'ecomposition QR.}\\
%On munit $\Com^n$ du produit hermitien canonique $<x|y>=\sum x_i \overline y_i$.\\
%1) Soient $a_1,...,a_n$ des vecteurs formant une base de
%$\Com^n$. Montrer qu'il existe une base orthonorm\'ee $q_1,...,q_n$ et
%des nombres complexes $r_{ij}$ ($i\leq j$) tels que $r_{ii}$ est un
%r\'eel positif pour tout $i$ et
%$$\left\{\begin{array}{l}a_1=r_{11}q_1\\ a_2=r_{12}q_1+r_{22}q_2\\ ~~\vdots\\ a_n=r_{1n}q_1+\hdots+r_{nn}q_n \end{array}\right. $$ 
%2) En d\'eduire que toute matrice inversible $A$ peut s'\'ecrire $A=QR$ o\`u $Q$ est unitaire et $R$ est triangulaire sup\'erieure \`a \'el\'ements diagonaux r\'eels et positifs et que cette d\'ecomposition est unique.\\
%3) Comment utiliser cette d\'ecomposition pour r\'esoudre facilement le syst\`eme $Ax=b$ ?\\
%4) Soit $A\in GL_n(\Com)$, montrer que $^t\overline A A$ est
%hermitienne d\'efinie positive. Quel est le lien entre la
%d\'ecomposition de Choleski et la d\'ecomposition $QR$ ?

\exercice {\bf D\'ecomposition de Cholesky.}\\
Soit $A$ une matrice hermitienne d\'efinie positive. Il existe une unique matrice triangulaire sup\'erieure $C$ qui a des \'el\'ements diagonaux strictement positifs telle que $A=C^*C$ (d\'ecomposition de Cholesky).\\
1) Donner l'algorithme qui permet de calculer $C$. L'appliquer \`a la
matrice
$$A= \left(\begin{array}{ccc} 1& 2&1\\ 2&13&-1\\ 1&-1&3 \end{array}\right)~.$$
Cet algorithme est-il appliquable \`a des matrices non hermitiennes ?\\
2) Expliquer comment utiliser la d\'ecomposition de Cholesky pour r\'esoudre le syst\`eme $Ax=b$ et donner le nombre d'op\'erations.\\
3) Une matrice $A=(a_{ij})$ est appel\'ee $p-$bande si $a_{ij}=0$ d\`es que $|i-j|\geq p$.\\
$~~~~$a) Donner des exemples de matrices $p-$bandes.\\
$~~~~$b) Montrer que si $A$ est une matrice hermitienne d\'efinie positive $p-$bande, alors $C$ est\\ $~~~~~~~$aussi $p-$bande.

Pour $p=1$, compter le nombre d'op\'erations n\'ecessaires pour trouver $C$.

%\bigskip

% \exercice {\bf D\'ecomposition QR}
% On munit $\Com^n$ du produit scalaire hermitien standard:
% $$ \langle Z,Z'\rangle =\sum_{i=1}^n \bar{Z_i}Z'_i .
% $$
% Soit $A$ une matrice $n\times n$ \`a coefficients complexes inversible. 

% 1) En utilisant la décomposition de Cholesky pour la matrice $A^*A$, montrer qu'il existe un unique 
%  couple de matrices $(Q,R)$ tel que $Q$ est unitaire, $R$ triangulaire sup\'erieure à coefficients sur la diagonale strictement positifs et $A=QR$.\\
% 2) Soit $Q_k\in \Com^n$ le k-i\`eme vecteur colonne de $Q$ (resp. $A_k\in \Com^n$ le k-i\`eme vecteur colonne de $A$).
% Montrer que $Q_k$ appartient au sous espace vectoriel de $\Com^n$ engendr\'e par  $\{ A_1, \ldots, A_k \}$. \\
% 3) Montrer que $(Q_1, \ldots, Q_n)$ est l'unique base de $\Com^n$ telle que:
% \begin{enumerate}
%  \item $\langle Q_i,Q_j\rangle=\delta_{ij}$,
% \item Pour tout $k$, $Q_k$ appartient au sous espace vectoriel de $\Com^n$ engendr\'e par  $\{ A_1, \ldots, A_k \}$,
% \item $\langle Q_k,A_k\rangle\in \Rm^{+*}$.
% \end{enumerate}
% Ainsi $(Q_1, \ldots, Q_n)$ est l'orthonormalis\'ee de Gram-Schmidt de la base des colonnes de $A$
%  relativement au produit scalaire hermitien standard.



% \exercice Ecrire un programme donnant la d\'ecomposition $QR$ d'une
% matrice. Le transformer en un programme calculant l'inverse d'une
% matrice.

\exercice Ecrire un programme calculant l'inverse d'une matrice en
utilisant l'une des d\'ecompositions.


}
\end{document}


