4.2 Algorithme de GAUSS

4.2.1 Exemple

englishméthode d'élimination de Gauss pour un système 3*3

4.2.2 Principe

1. transformation du système $A.x=b$
   en un système triangulaire $U.x=d$
2. résolution de $U.x=d$

4.2.3 Système triangulaire

$$U.x=d \mbox{{ avec }} U_{ij}=0 \mbox{si} i>j$$

Pour $i$ de $N$ à $1$

$$x_{i}=\frac{d_{i}-\sum_{j=i+1}^{n}U_{ij}*x_{j}}{U_{ii}}$$

Algorithme

5

4.2.4 Exemple d'élimination

$$\left[\begin{array}{ccc} 1 & 0 & 0\\ -1 & 2 & -1\\ -1 & -1... ...ay}\right]=\left[\begin{array}{c} 1\\ 0\\ 0\end{array}\right]$$

$$\left[\begin{array}{ccc} 1 & 0 & 0\\ 0 & 2 & -1\\ 0 & -1 &... ...ay}\right]=\left[\begin{array}{c} 1\\ 1\\ 1\end{array}\right]$$

$$\left[\begin{array}{ccc} 1 & 0 & 0\\ 0 & 2 & -1\\ 0 & 0 & ... ...ay}\right]=\left[\begin{array}{c} 1\\ 1\\ 3\end{array}\right]$$

4.2.5 Algorithme de GAUSS

• initialisation $A^{1}=A$
• étape 1: élimination de $A_{i1}$ pour i de 2 à n
  
  
  $$\leadsto A_{ij}^{2}.x_{j}=b_{i}^{2}$$
  
  
  ligne i ($A^{2}$) = ligne i ($A^{1}$) - $\frac{A_{i1}^{1}}{A_{11}^{1}}$ ligne 1 ($A^{1}$)

Détail

de l'algorithme

• étape 1: élimination de $A_{i1}$ pour i de 2 à n
  
  $$A_{1j}^{2}=A_{1j}^{1} \mbox{{pour }}j=1,n$$
  
  
  
  
  $$A_{i1}^{2}=0 \mbox{{pour }}i=2,n$$
  
  
  
  
  $$A_{ij}^{2}=A_{ij}^{1}-\frac{A_{i1}^{1}}{A_{11}^{1}}A_{1j}^{1} \mbox{{pour }}i=2,n \mbox{{et}} j=2,n$$
  
  

• $\ldots$
• étape k: élimination de $A_{ik}$ pour i de k+1 à n
  
  $$\leadsto A_{ij}^{k+1}.x_{j}=b_{i}^{k+1}\mbox{ pour i de k+1 à n}$$
  
  
  ligne i ($A^{k+1}$) = ligne i ($A^{k}$) - $\frac{A_{ik}^{k}}{A_{kk}^{k}}$ ligne k ($A^{k})$
  
  $$A_{ij}^{k+1}=A_{ij}^{k} \mbox{{ pour }}i=1,k \mbox{{ et }}j=1,n$$
  
  
  
  
  $$A_{ij}^{k+1}=0 \mbox{{ pour }}i=k+1,n\mbox{{ et }}j=1,k$$
  
  
  
  
  $$A_{ij}^{k+1}=A_{ij}^{k}-\frac{A_{ik}^{k}}{A_{kk}^{k}}A_{kj}^{k}{ pour }i=k+1,n \mbox{{ et }}j=k+1,n$$
  
  

Algorithme

6

coût

$\theta(N^{2})$ opérations

4.2.6 Pivotage

2 stratégies si $A_{kk}^{k}=0$

4.2.6.1 Pivotage partiel

permutation de ligne à chaque étape k
remplace la ligne k par la ligne p telle que

$$\left\vert A_{pk}^{k}\right\vert=\max_{k\leq i\leq n}\left\vert A_{ik}^{k}\right\vert$$

4.2.6.2 Pivotage total

permutation

ligne p colonne q pour amener en $A_{kk}$ l'élément $A_{pq}$ telle que

$$\left\vert A_{pq}^{k}\right\vert=\max_{k\leq i;j\leq n}\left\vert A_{ij}^{k}\right\vert$$

remarque:

si un pivot est nul apres pivotage partiel ou total, alors la matrice $A$ est singulière