<< Héritage | PSOOIndex | >>

Plan (hide)

  1.   1.  Présentation
  2.   2.  Outils
    1.   2.1  La classe Vecteur
    2.   2.2  La classe Matrice
    3.   2.3  Lecture des coefficients
  3.   3.  Systèmes linéaires
    1.   3.1  Création de la classe abstraite
    2.   3.2  Création de la classe SysLinException
    3.   3.3  Classes systèmes linéaires triangulaires
    4.   3.4  Décomposition $LU$
    5.   3.5  Résolution d'un système par factorisation $LU$
  4.   4.  Liste des fichiers attachés

1.  Présentation

Nous nous proposons de résoudre des systèmes linéaires de différentes natures :

  1. triangulaire supérieur ou inférieur,
  2. à diagonale unité ou non,
  3. ou encore des systèmes généraux.

En nous appuyant sur le principe de réutilisabilité de la programmation objet, nous allons définir une classe abstraite générale qui sera le dénominateur commun de tous les sytèmes linéaires et dont héritera les classes spécialisées. On considérera qu'un système linéaire ne peut ếtre construit qu'après la construction effective de la matrice et du second membre du système et le constructeur d’un système ne peut donc se faire qu’avec ses deux éléments. Par ailleurs, la seule méthode qui nous intéresse, pour l'instant, est celle qui calcule la solution du système. Cette résolution peut éventuellement conduire à un échec si la matrice est singulière et non allons pour cela faire la gestion d’une exception SysLinException succeptible d'être levée en cours de calcul. Ce traitement pourra être laissé de coté dans un premier temps.

2.  Outils

On construit tout d'abord les différentes classes nécessaire à la résolution d'un système linéaire :

  1. Une classe Vecteur ;
  2. Une classe Matrice ;
  3. Une classe SysLinException.

2.1  La classe Vecteur

Pour cela vous pouvez reprendre et compléter la classe que vous avez déjà construite lors d'un précédent TP.

2.2  La classe Matrice

Vous devez construire une classe Matrice qui permet de définir les opérateursmatriciels classiques, d'une manière non exhaustive. Le stockage des coefficients de la matrice se fait grâce à un tableau d'objets du type Vecteur que vous avez défini précédemment. Chacun des vecteurs ont la même taille. Ce tableau est privé et on définit les fonctions coef(i ,j) et toCoef( i, j, x) qui permettent respectivement d’aller rechercher un coefficient et d’en changer la valeur.

Le squelette de classe est le suivant :

public class Matrice
{
  private Vecteur[] composant;

  Matrice (int dim1, int dim2)
  /** constructeur créant une matrice de coefficients nuls
   * de dim1 lignes
   * et dim2 colonnes
  */
  { /* A faire */ }

  Matrice (double tab [][])
  /** constructeur créant une matrice à partir d'un tableau de double */
  { /* A faire */ }

  Matrice (Matrice m)
  /** Constructeur d'une matrice à partir d'une existante.
    * m matrice à copier
  */
  { /* A faire */ }

  Matrice( int n, TypeMatrice type )
  /** Constructeur d'une matrice carrée d'un type donné.
      Les types reconnus sont VIDE et IDENTITE.
      TypeMatrice est une énumération que vous définirez.
  */
  { /* A faire */ }

  public int nbLignes()
  /** renvoie le nombres de lignes de la matrice */
  { /* A faire */ }

  public int nbColonnes()
  /** renvoie le nombre de colonnes de la matrice */
  { /* A faire */ }

  public double coef(int nl, int nc)
  /** renvoie le coefficient a la position (nl, nc) */
  { /* A faire */ }

  public void toCoef(int i, int j, double x)
  /** affecte la valeur de x au coefficient a la
    * position (nl, nc)
  */
  { /* A faire */ }

  public String toString()
  /** affiche les coefficients de la matrice */
  { /* A faire */ }

  public static Vecteur produit(Matrice m, Vecteur v)
  /** renvoie le vecteur obtenu en multipliant
    * la matrice m par le vecteur v
  */
  { /* A faire */ }

  public static Matrice produit(Matrice m1, Matrice m2)
  /** renvoie la matrice obtenue en multipliant les deux
    * matrices m1 et m2
  */
  { /* A faire */ }

  public static Matrice addition(Matrice m1, Matrice m2)
  /** renvoie la matrice obtenue en additionnant les deux
    * matrices m1 et m2
  */
  { /* A faire */ }

  public static Matrice soustraction(Matrice m1, Matrice m2)
  /** renvoie la matrice obtenue en soustrayant la matrice m2
    * a la matrice m1
  */
  { /* A faire */ }  
}
[$[Get Code]]

Vous devez tester maintenant votre classe avec des exemples simples.

2.3  Lecture des coefficients

Il faut maintenant définir une classe permettant de lire un vecteur et une autre une matrice. Ces classes devront être complétées par la suite de façon à lire les coefficients dans des fichiers.

3.  Systèmes linéaires

Les grandes bibliothèques connues d'algèbre linéaire (comme BLAS) construisent autant de fonctions de résolution distinctes qu’il y a de types différents de systèmes. S’appuyant sur le principe de réutilisabilité de la programmation objet, vous devez définir une classe abstraite générale qui sera le dénominateur commun de tous les systèmes linéaires et dont héritera les classes spécialisées.

On considère qu’un système linéaire ne peut être construit qu’après la construction effective de la matrice et du second membre du système et le constructeur d’un système ne peut donc se faire qu’avec ses deux éléments. Par ailleurs, la seule méthode qui nous intéresse, pour l’instant, est celle qui calcule la solution du système. Cette résolution peut éventuellement conduire à un échec si la matrice est singulière. Vous devez donc créer une classe SysLinException correspondant à une exception susceptible d'être levée en cours de calcul.

3.1  Création de la classe abstraite

La classe abstraite SysLin doit être composée de l'ordre du système, de la matrice du système représentant le premier membre (premierMembre) et du vecteur du système représentant le second membre (secondMembre). Vous devez évidemment compléter cette classe avec le ou les constructeurs nécessaires, une methode toString() affichant le système, une méthode getOrdre() et une méthode resolution() abstraite et susceptible de lever une exception de type SysLinException.

3.2  Création de la classe SysLinException

Pour créer votre classe elle doit hériter de la classe Exception. Les méthodes pouvant lever une telle exception doivent inclure une clause throws SysLinException dans leur en-tête.

3.3  Classes systèmes linéaires triangulaires

Écrivez maintenant une classe de systèmes linéaires triangulaires supérieurs SystTriangSup qui définit la méthode resolution() et lance l'exception SysLinException lorsqu'un élément de la diagonale de la matrice est nul.

L'algorithme de résolution est simple, il se fait en remontant les solutions dans les équations constituant le système, de la dernière à la première. Soit le système {$AX = B$} avec {$A = (A_{aj})_{i,j=1,n}$} triangulaire supérieure et inversible. Dans ce cas {$\forall i = 1..n, a_{ii} \neq 0$} puisque {$Det(A) = \prod_{i-1}^{n} a_{ii} \neq 0$}. L'algorithme de résolution est alors le suivant : {$$ \left\{ 

  \begin{array}{lcl}
    x_n & = & \frac{b_n}{a_{nn}} 
    \mbox{et} & & 
    x_i & = & \frac{1}{a_{ii}}(b_i - \sum_{j = i + 1}^{n} a_{ij}x_{j})\mbox{ pour } i = n-1, ..., 1
  \end{array}

\right. $$}

Tester maintenant votre méthode de résolution en écrivant une classe adéquate. Vous pourrez utiliser les fichiers joints suivants. Le format pour fichier concernant le second membre (vecteur) est le suivant :

  • sur la première ligne, la dimension du vecteur ;
  • sur la ligne suivante les coefficients du vecteur.

Le format pour le fichier contenant les données liées au premier membre (matice) est le suivant :

  • sur la première ligne, les dimensions de la matrice
  • sur les lignes qui suivent, chacune des lignes de la matrice.

Premier système : AX = B Vous pouvez modifier le système pour vérifier le traitement de l'exception en introduisant un élément nul sur la diagonale.

Créer une classe SystTriangInf que vous utiliserez par la suite pour mettre en œuvre la méthode de factorisation LU. Spécialisez ensuite cette classe en une classe triangulaire inférieure mais en considérant que la matrice constituant le premier membre est à diagonale unité.

3.4  Décomposition {$LU$}

On cherche à décomposition la matrice {$A$} d'ordre {$n$} en {$$ A = LU $$} avec {$L$} matrice triangulaire inférieure (Lower) à diagonale unité et {$U$} (Upper) matrice triangulaire supérieure. On a donc {$L_{ij} = 0$} si {$j > i $}, {$L_{ij} = 1$} si {$j = i$} et {$U_{ij} = 0$} si {$j < i$}. La formule du produit matriciel s'écrit : {$$ A_{ij}=\sum_{k=1}^n L_{ik}U_{kj} $$}

On considère alors les deux cas suivants :

  • {$j \ge i, \qquad U_{ij} = (A_{ij} - \sum\limits_{k=1}^{i - 1} L_{ik}U_{kj})/L_{ii}, \mbox{ on a }L_{ii} = 1$}
  • {$ j \lt i,\qquad L_{ij} = (A_{ij} - \sum\limits_{k=1}^{j - 1} L_{ik}U_{kj})/U_{jj}, \mbox{ avec }U_{jj} \neq 0$}

Compléter votre classe Matrice de façon à pouvoir la factoriser en {$LU$}. Une exception de type SysLinException devra être levé lorsque cela n'est pas possible.

3.5  Résolution d'un système par factorisation {$LU$}

Définir une classe résolvant un système après factorisation {$LU$}. On définira dans cette classe une méthode resolutionPartielle() qui permet de résoudre le système lorsque la matrice est déjà sous la forme factorisée. En effet, l'un des intérêts de cette méthode de factorisation est qu'elle ne nécessite pas de refactoriser la matrice (opération la plus couteuse) lorsque l'on doit résoudre plusieurs systèmes avec la même matrice. Par exemple, le calcul de l'inverse d’une matrice d'ordre {$n$} se fait en résolvant {$n$} systèmes ayant tous la même matrice : c'est la matrice à inverser. Les seconds membres sont, quant à eux, les {$n$} vecteurs de la base canonique.

4.  Liste des fichiers attachés