I want to display a list of items. That is why I use:
Code: Select all
\begin{description}
\item [blablabla] définition de blablabla
\end{description}line131
Code: Select all
\item [void \texttt{aff_vect}(double** \texttt{q}):] affiche le vecteur \texttt{q} de dimension $N\times1$.
\item [void \texttt{multi}(double** \texttt{a}, double** \texttt{b2}, double** \texttt{c}):]
multiplie la matrice \texttt{a} par la matrice-colonne \texttt{b2} et stocke le résultat dans la matrice-colonne \texttt{c}.
\item [void \texttt{init_id}(void):] crée et initialise la matrice identité $Id$ de dimension $N\timesN$.do not appear on the final rendering. The missing items are displayed anarchically on the next page, over the text already there.
Here is my Latex code:
Code: Select all
\documentclass[a4paper,11pt]{article}
\usepackage[latin1]{inputenc}
\usepackage[T1]{fontenc}
\usepackage[francais]{babel}
\title{Rapport de TP de programmation \\ Le pivot de Gauss }
\author{Gros Matou}
\date{mai 2013}
\begin{document}
\maketitle
\newpage
\tableofcontents
\newpage
\section{Positionnement du problème}
On souhaite résoudre le système suivant:
~~\\
$(S_1)\left\lbrace
\begin{array}{lcl}
a_{11}\,x_1+a_{12}\,x_2+... &=& b_1\\
a_{21}\,x_1+a_{22}\,x_2+... &=& b_2\\
... \\
a_{n1}\,x_1+a_{n2}\,x_2+... &=& b_n
\end{array}\right.$
~~\\
avec $a_{ij}$ ($1 \le i,j \le n$) et $b_k$ ($1 \le k \le n$).
\\ Ces coefficients sont fournis par l'utilisateur.
\textbf{\\La formulation matricielle du problème} est: $$A\,X&=&B$$ où $A&=&(a_{ij})\ (n\times n)$ et $B&=&(b_k)\ (n\times1)$
\\\\
On cherche, dans la mesure où le système admet une ou des solutions, à déterminer X.
On s’intéressera ici, au cas où la matrice \textbf{A est inversible}.
~~\\\\
\section{Résolution théorique du système}
\begin{description}
\item [Unicité:] ~~\\ Montrons que si elle existe, la solution au système donné est unique:
\\
Soient $X_1$ et $X_2$ tels que $\;A\,X_1&=&B\;$ et $\:A\,X_2&=&B\:$. En soustrayant ces deux équations membre à membre, on obtient:
$\;A\,(X_1-X_2)&=&0\;$. Or A est inversible, donc $Ker\,(A)&=&{0}$ (noyau de A) aussi$\;X_1-X_2&=&0\;$ soit$\;X_1 &=& X_2\;$.
\\
\item [Existence:] ~~\\ Je pose $X_0&=&A^{-1}\,B$. En réinjectant $X_0$ dans$\;A\,X&=&B\;$, j'ai $\;A\,X_0&=&A\,(A^{-1}\,B)&=&B\;$ donc $X_0$ est solution du système.
\end{itemize}
~~\\
\textbf{Conclusion}: On a donc démontré que, en ayant supposé A inversible, \textbf{$X_0&=&A^{-1}\,B$ est l'unique solution du système}.
\newpage
\section{Résolution pratique du système}
Par la démonstration faite ci-dessus, trouver $X_0$ revient donc à déterminer $A^{-1}$ l'inverse de $A$. C’est ce que nous allons faire.
Supposons qu'il faille \textbf{$p$ opérations élémentaires} pour \textbf{transformer $A$ en la matrice identité $Id$}. Notons $T_1$, $T_2$, ... $T_p$ les matrices associées à ces opérations élémentaires. Alors$\;T_p\,T_{p-1}\,T_{p-2}\,...\,T_2\,T_1\,A&=&Id\;$. Ainsi l'inverse de $A$ vaut$\;A^{-1}&=&T_p\,T_{p-1}\,T_{p-2}\,...\,T_2\,T_1\;$. Mais, $(T_p\,T_{p-1}\,T_{p-2}\,...T_2\,T_1)\,Id&=&(T_p\,T_{p-1}\,T_{p-2}\,...\,T_2\,T_1)$.
Pour obtenir $A^{-1}&=&T_p\,T_{p-1}\,T_{p-2}\,...\,T_2\,T_1$, il suffit donc d'\textbf{appliquer les mêmes opérations élémentaires sur $Id$ que celles effectuées pour transformer $A$ en $Id$}.
En pratique, on triagonalise $A$, on réduit les éléments diagonaux à $1$, puis on diagonalise.
Par des opérations élémentaires (transposition de deux lignes, dilatation d'une ligne par un facteur $k$, addition de deux lignes), on peut réduire la matrice $A$ à une matrice triangulaire. Ceci n'est valable que parce que ces opérations élémentaires effectuées sur les lignes sont réversibles\footnote{Autrement dit, les matrices associées à ces différentes opérations sont inversibles. Aussi elles ne modifient pas le noyau de $A$, $Ker\,(A)$.}.
Afin d'effectuer la trigonalisation, on procède ainsi:
on cherche \textbf{l'élément le plus grand en valeur absolue} dans la 1\iere{} colonne\footnote{Le choix de maximiser la valeur absolue assure une plus grande stabilité numérique.}. C’est le 1\ier{} \textbf{pivot}. On échange la ligne à laquelle il se trouve avec la première ligne. Par une combinaison linéaire judicieusement choisie, on parvient ensuite à créer une colonne de zéro en dessous du pivot. \textbf{On fait abstraction de la 1\iere{} ligne et de la 1\iere{} colonne} et l'on recommence: on cherche l'élément le plus grand en valeur absolue dans la 2\ieme{} colonne. C’est le 2\ieme{} pivot. On échange la ligne à laquelle il appartient avec la 2\ieme{} ligne, puis l'on crée sur la colonne des zéros sur toutes les lignes se trouvant en dessous de celle du pivot.
On procède ainsi $n$ fois. \textbf{La matrice ainsi obtenue est triangulaire}.
\textbf{Si à un quelconque moment, le programme trouve un pivot nul}, puisque la valeur absolue du pivot est supérieure à celles des autres éléments de la même colonne, tous les éléments de la colonne sont donc nuls. La matrice $A$ est donc non inversible ($rang\,(A)\le n$), et le programme s'arrête.
Sur le même principe, on peut \textbf{diagonaliser ensuite la matrice $A$ et la réduire à l'identité}. On fait des combinaisons linéaires judicieusement choisies à partir de la dernière ligne pour créer des zéros sur la dernière colonne, au dessus de l'élément diagonal. On procède de même sur les autres colonnes.
Par ces opérations élémentaires, on a donc transformé $A$ en $Id$ et $Id$ en $A^{-1}$.
Évidemment, on calcule$\;X_0&=&A^{-1}\,B$ pour obtenir la solution du problème.
Le programme testera la validité de la solution trouvée en calculant$\;A\,X_0\;$ et en s'assurant que le résultat est identique à $B$.
\newpage
\section{Implémentation algorithmique}
J'ai besoin des \textbf{variables} suivantes:
\begin{description}
\item [int \texttt{N}:] le nombre d’inconnues du probllème (fourni par l’utilisateur).
\item [double* \texttt{f}:] matrice $A$ (N\timesN) (fournie par l’utilisateur).
\item [double* \texttt{b}:] matrice-colonne $B$ ($N\times1$) (fournie par l’utilisateur).
\item [double* \texttt{id}:] matrice identité $Id$ ($N\timesN$).
\item [double* \texttt{s}:] matrice-colonne ($N\times1$) qui contiendra la solution du problème.
\end{description}
~~\\
\textbf{Implémentation des matrices en C}:
\\Voici comment je vais procéder pour implémenter mes matrices en C:
soit une matrice $M$ de dimmension $N\timesN$. Je crée un vecteur \texttt{M} de type \textbf{double} de taille $N\timesN$ par allocation dynamique ($\texttt{M}&=&(\textbf{double*}) \textbf{malloc}(\texttt{N}*\texttt{N}*\textbf{sizeof}(\textbf{double}));$\,). Les $N$ premiers éléments \textt{M[0]},\,\texttt{M[1]},\,...,\,\texttt{M[N-1]} correspondent à la 1\iere{} ligne, les $N$ suivants à la 2\ieme{} ligne... Si l'on souhaite accéder à l'élément se trouvant à la i\ieme{} ligne et à la j\ieme{} colonne, on utilise \texttt{M[i*N+j]}.
Bien entendu, je n'oublierai pas de \textbf{désallouer la mémoire associée à \texttt{M}} à la fin de l'exécution de mon programme. (\textbf{free}(\texttt{M});).
~~\\\\
J'ai besoin des \textbf{fonctions} suivantes:
\begin{description}
\item [void \texttt{dilatation}(double* \texttt{m}, int \texttt{i}, double \texttt{k}):]
multiplie la i\ieme{} ligne de la matrice \texttt{m} par un facteur \textt{k}.
\item [void \texttt{transposition}(double* \texttt{m}, int \texttt{i1}, int \texttt{i2}):]
échange dans la matrice \texttt{m} la ligne \texttt{i1} et la ligne \texttt{i2}.
\item [void \texttt{additionner}(double* \texttt{m}, int \texttt{i1}, int \texttt{i2}):]
additionne dans la matrice \texttt{m}, la ligne \texttt{i2} à la ligne \texttt{i1}.
\item [void \texttt{soustraire}(double* \texttt{m}, int \texttt{i1}, int \texttt{i2}):]
soustraie dans la matrice \texttt{m}, la ligne \texttt{i2} à la ligne \texttt{i1}.
\item [int \texttt{ligne}(int \texttt{d}):] donne la ligne qui correspond à l'indice \texttt{d}.
\item [int \texttt{colonne}(int \texttt{d})]: donne la colonne qui correspond à l'indice \texttt{d}.
\item [int \texttt{pivot}(double* \texttt{m}, int \texttt{i}, int \texttt{j}):]
renvoie l'indice du pivot se trouvant dans la j\ieme{} colonne,
en restreignant la recherche à la sous-matrice de \texttt{m}, définie à partir de la i\ieme{} ligne et de la j\ieme{} colonne.
\item [void \texttt{afficher}(double* \texttt{m}):] affiche la matrice \texttt{m} de dimension $N\timesN$.
\item [void \texttt{aff_vect}(double** \texttt{q}):] affiche le vecteur \texttt{q} de dimension $N\times1$.
\item [void \texttt{multi}(double** \texttt{a}, double** \texttt{b2}, double** \texttt{c}):]
multiplie la matrice \texttt{a} par la matrice-colonne \texttt{b2} et stocke le résultat dans la matrice-colonne \texttt{c}.
\item [void \texttt{init_id}(void):] crée et initialise la matrice identité $Id$ de dimension $N\timesN$.
\end{description}
Les \textbf{librairies} à importer sont:
celles habituelles pour les flux entrant et sortant: \textbf{\texttt{stdio.h}, \texttt{stdlib.h}};
pour les fonctions mathématiques (utilisation de la valeur absolue): \textbf{\texttt{math.h}}
~~\\\\
\section{Structure du programme}
La structure du programme est donc la suivante:
\begin{itemize}
\item l'initialisation: allocations dynamiques pour les matrices
\item l'acquisition: entrée par l’utilisateur du système à résoudre (nombre d’inconnues N, matrice A et matrice-colonne B)
\item la trigonalisation du système
\item la diagonalisation du système
\item le calcul de la solution
\item la vérification de la validité de la solution
\item la libération de la mémoire (désallocations dynamiques)
\end{itemize}
~~\\\\
\section{Utilisation du programme}
Il suffit de fournir $N$ (nombre d’inconnues), la matrice $A$ de dimension $N\timesN$, la matrice-colonne $B$.
Le code source est annoté de commentaires.
\newpage
\section{Conclusion}
La résolution d'un système par pivot de Gauss n'a pas posé de réelles difficultés.
%Difficultés rencontrées, améliorations, ce qui reste à faire:
Analyse des résultats fournis - remarques:
L'efficacité et la robustesse du présent programme sont très appréciables. Malgré la limite de précision de la machine ($10^{-20}$), les résultats fournis sont corrects. La recherche du pivot par maximisation de la valeur absolue est cruciale dans la stabilité numérique du programme. En effet, si l'on supprime cet étape et si l'on prend systématiquement l'élément diagonal comme pivot, les résultats fournis pour de grandes valeurs de $N$ ($N&=&20$ par exemple) sont faux.
\end{document}The five last items have been eaten (aff_vect, multi, init_id. They are displayed in a strange way on page 6, 2nd line.
I thank you very much. See you!
Kevung
