\documentclass[a4,11pt]{article}

\usepackage[utf8]{inputenc}
\usepackage[french]{babel}
\usepackage{fullpage}
\usepackage[a4paper]{geometry}
\geometry{top=1cm, bottom=1.5cm, left=2cm, right=2cm}
\usepackage[french]{algorithm2e}
\usepackage{url}

\title{TD1~: Inversion de matrice}
\date{Vendredi 4 février 2011}

\begin{document}
\maketitle

Le but de ce problème est de programmer un algorithme pour l'inversion
de matrices réelles, connu sous le nom d'élimination de Gauss-Jordan
(ou pivot de Gauss). C'est l'occasion de revenir sur les pointeurs et
l'allocation de mémoire, et à ce titre il est indispensable de bien
travailler les deux premières parties. La troisième, plus difficile,
est un peu plus optionnelle. Dans la suite, $A$, désignent une matrice
de réels et $a_{ij}$ le coefficient de la $i$e ligne et $j$e colonne.


\section*{Représentation mémoire d'une matrice}
\begin{enumerate}
\item Proposer un type C pour représenter les matrices de réels, à la
  manière de ce qui a été vu en cours pour les vecteurs. Les matrices
  seront de dimension $m \times n$ (lignes/colonnes). 
\item \'Ecrire une fonction \verb|create_matrix| permettant de créer
  une matrice, dont les coefficients ne sont pas initialisés.
\item \'Ecrire une fonction \verb|free_matrix| permettant de libérer
  la mémoire allouée à une matrice.
\item \'Ecrire une fonction de copie de matrice, de prototype
\begin{verbatim}
matrix copy_matrix(matrix m);
\end{verbatim}
\item Soit $c$ une constante réelle, on souhaite disposer de
  constructeurs produisant des matrices courantes~:
  \begin{itemize}
  \item la matrice pleine, $a_{ij} = c$ pour tous $i,j$,
  \item la matrice diagonale, $a_{ii} = c$ pour tout $i$ et $a_{ij} =
    0$ pour $i \neq j$,
  \item les matrices triangulaires supérieures (resp. inférieures),
    telles que $a_{ij} = c$ si $i \leq j$, et $a_{ij} = 0$ sinon
    (resp. $a_{ij} = c$ si $i \geq j$, et $a_{ij} = 0$ sinon).
  \end{itemize}
  \'Ecrire une fonction pour chaque type de matrice, qui initialisera
  une matrice déjà existante. 
\end{enumerate}
{\bf Remarque}~: on dit qu'une fonction agit {\bf en place} quand elle
stocke le résultat d'un calcul dans ses arguments, plutôt que
d'allouer de la mémoire.

\section*{Opérations usuelles}
\begin{enumerate}
\item \'Ecrire une fonction d'affichage des matrices
  \verb|print_matrix|, en utilisant la fonction \verb|printf| et
  notamment~:
  \begin{itemize}
  \item le caractère de tabulation \verb|\t| pour aligner les
    colonnes de la matrice affichée.
  \item le formatage des flottants, par exemple \verb|%.2f| ou
    \verb|%g|, pour limiter le nombre de décimales affichées.
  \end{itemize}
\item Implémenter l'opération de transposition, définie par $B = A^T$
  avec $b_{ij} = a_{ji}$. Le prototype attendu est 
\begin{verbatim}
void transpose_matrix(matrix A, matrix B);
\end{verbatim}
et la fonction doit mettre le résultat attendu dans le deuxième
argument. Penser à vérifier que les matrices sont de dimensions
compatibles~!
\begin{quote}
  (Optionnel) Que se passe-t-il lors d'un appel du type \verb|transpose_matrix(A,A)|~?
\end{quote}
\item Dans le même esprit, implémenter l'addition de deux matrices. Le
  prototype attendu est 
\begin{verbatim}
void matrix_add(matrix A, matrix B, matrix C);
\end{verbatim}
\begin{quote}
  (Optionnel) Que se passe-t-il lors d'un appel du type \verb|add_matrix(A,B,A)|~?
\end{quote}
\item Idem, écrire la multiplication de deux matrices. Rappel~: les
  coefficients de $A \times B$ sont les $c_{ij}$ définis par
$$ c_{ij} = \sum_{k=1}^n a_{ik}b_{kj}$$
\begin{quote}
  (Optionnel) Que se passe-t-il lors d'un appel du type
  \verb|mult_matrix(A,B,A)|~? Quelle mesure faut-il prendre~?
\end{quote}
\item On définit $P^{kl}$ comme la matrice égale à la matrice identité
  sauf pour 4 coefficients~: $p_{kk} = p_{ll} = 0$ et $p_{kl} = p_{lk}
  = 1$. La matrice $P^{kl}$ est appelée \emph{matrice de permutation}~;
  expliquez pourquoi en calculant $AP_{kl}$ et $P_{kl}A$, où A est une
  matrice quelconque.
\end{enumerate}

\section*{\'Elimination de Gauss-Jordan}
Le pivot de Gauss consiste à transformer une matrice $A$ en la matrice
identité par une série d'opérations sur les lignes de $A$. L'astuce
est que ces opérations reviennent à multiplier $A$ à gauche par des
matrices bien choisies. On obtient ainsi en $n$ étapes l'égalité~:
$$ (J_n \dots J_2 J_1) A = I$$
où les matrices $J_1,\dots,J_n$ sont les transformations successives
appliquées à $A$. Par conséquent on a $A^{-1} = J_n \dots J_2
J_1$. L'algorithme consistera donc à transformer $A$ en la matrice
identité, et à appliquer les mêmes transformations à la matrice
identité pour calculer $A^{-1}$.

\noindent Notation~: $l_i$ représente la $i$e ligne de $A$.
\begin{enumerate}
\item Nous aurons besoin de l'opération qui échange (ou permute) en
  place deux lignes d'une matrice, dont le prototype est~:
\begin{verbatim}
void permutation(matrix m, int i, int j);
\end{verbatim}
\item Proposer une fonction pour l'opération d'``élimination'' qui
  remplace la $i$e ligne $l_i$ de $A$ par $l_i - a_{ik} l_k$, de
  prototype~:
\begin{verbatim}
void elimination(matrix m, int i, int k);
\end{verbatim}
\item Le pseudo-code suivant permet de transformer une matrice $A$ de
  dimension $n$ en la matrice identité~:

  \begin{algorithm}
    \Pour{$k$ allant de 1 à $n$}{
      \eSi{il existe $i \geq k$ t.q. $a_{ik} \not=0$}{
        \'Echanger les lignes $l_i$ et $l_k$\;
        $l_k \leftarrow \frac{1}{a_{kk}} l_k$ \;
        \Pour{$i$ allant de 1 à $n$, et $i \neq k$}{
          $l_i \leftarrow l_i-a_{ik} \times l_k$
        }
      }{
        $A$ n'est pas inversible, abandonner.
      }
    }
  \end{algorithm}

  En vous inspirant de cet algorithme, implémentez une fonction qui
  inverse une matrice et dont le prototype est 
\begin{verbatim}
void inverse(matrix A, matrix B);
\end{verbatim}
La fonction écrira son résultat dans le deuxième argument et on
veillera bien à ce que le premier argument ne soit pas modifié.
\end{enumerate}

\section*{Références}
\begin{itemize}
\item Page wikipedia sur le pivot de Gauss 
  \begin{center}
    \url{http://fr.wikipedia.org/wiki/Elimination_de_Gauss-Jordan}
  \end{center}
\end{itemize}
\end{document}

%%% Local Variables: 
%%% mode: latex
%%% TeX-master: t
%%% End: 
