Scribd
Importer
26 vues3 pages

CS TP 02 Algorithmes

Le document présente plusieurs algorithmes pour résoudre des systèmes d'équations linéaires, notamment l'algorithme de transformation de la matrice en forme triangulaire supérieure et l'algorithme de résolution par substitutions remontantes. Il décrit également l'algorithme de Doolittle pour décomposer une matrice en produits de matrices triangulaires inférieure et supérieure. Chaque algorithme est accompagné de pseudo-code et d'explications sur son fonctionnement.

Transféré par

lassire.romu
Copyright
© © All Rights Reserved
Nous prenons très au sérieux les droits relatifs au contenu. Si vous pensez qu’il s’agit de votre contenu, signalez une atteinte au droit d’auteur ici.
Formats disponibles
Téléchargez aux formats PDF, TXT ou lisez en ligne sur Scribd
26 vues3 pages

CS TP 02 Algorithmes

Le document présente plusieurs algorithmes pour résoudre des systèmes d'équations linéaires, notamment l'algorithme de transformation de la matrice en forme triangulaire supérieure et l'algorithme de résolution par substitutions remontantes. Il décrit également l'algorithme de Doolittle pour décomposer une matrice en produits de matrices triangulaires inférieure et supérieure. Chaque algorithme est accompagné de pseudo-code et d'explications sur son fonctionnement.

Transféré par

lassire.romu
Copyright
© © All Rights Reserved
Nous prenons très au sérieux les droits relatifs au contenu. Si vous pensez qu’il s’agit de votre contenu, signalez une atteinte au droit d’auteur ici.
Formats disponibles
Téléchargez aux formats PDF, TXT ou lisez en ligne sur Scribd

1 Algorithmes

1.1 Algorithme 1 : Obtention du système linéaire à matrice triangulaire supérieure


Nous donnons ci-après l’algorithme en pseudo-code, en convenant que les notations A et b désignent
dorénavant des variables de type array définies en Python à l’itération no k, 0 ≤ k ≤ (n −1). Par exemple,
la notation A[i , j ] désignera l’élément indexé par les entiers i et j , 0 ≤ i , j ≤ (n − 1) dans la variable
Python contenant la matrice A.

Algorithme 1
Début
# ——————————————————————— #
# 1 RE PARTIE DE L’ ALGORITHME 1 #
# ——————————————————————— #
k ← 0
TantQue k <= n − 1 Faire
nL ← k
TantQue A[nL, k] == 0 Faire
Si nL == n − 1 Alors
Afficher  Le système n'admet pas de solution 
Terminer l'algorithme
FinSi
nL ← (nL + 1)
FinTantQue
# ———————- F ONCTION « SWAP » À DÉVELOPPER ————————— #
Échanger les lignes nL et k dans A et b
# ——————————————————————— #
# 2 E PARTIE DE L’ ALGORITHME 1 #
# ——————————————————————— #
Pour i variantDe k +1 à n Faire
q ← A[i , k]/A[k, k]
b[i ] ← b[i ] − q ∗ b[k]
A[i , k] ← 0
Pour j variantDe k +1 à n Faire
A[i , j ] ← A[i , j ] − q ∗ A[k, j ]
FinPour
FinPour
k ← k +1
FinTantQue
Fin

1
Si la première partie de l’algorithme 1 est validée, on est assuré que le k-ième coefficient de la colonne k
de la matrice A est non nul 1 ; il s’appelle alors pivot de la colonne k et la position (k, k) dans la matrice
A est dite position de pivot. On sera assuré que le système est compatible si l’on parvient à trouver
n positions de pivot à l’issue de l’algorithme complet. La deuxième partie de l’algorithme en pseudo-
code permet d’effectuer les calculs numériques pour aboutir à la forme triangulaire supérieure à de
la matrice A et la forme b̃ du vecteur b correspondante. Le pseudo-code précédent ne comprend pas
les instructions pour réaliser les échanges de lignes dans la matrice A et le vecteur b. Il faudra donc
développer une fonction spécifique pour réaliser cette tâche.

1.2 Algorithme 2 : résolution du système Ãx = b̃ par substitutions remontantes


Dans l’algorithme en pseudo-code ci-après, x désigne le vecteur solution du système dans le cas où ce
dernier existe. L’algorithme de la fonction somme utilisé dans l’algorithme 2 est donné à la suite.

Algorithme 2
Début
x[n − 1] ← b[n − 1]/A[n − 1, n − 1]
Pour i variantDe (n − 1) à 0 Faire
x[i − 1] ← (b[i − 1] − somme(i , A, x)) /A[i − 1, i − 1]
FinPour
Fin

Fonction somme( i , A ,x : entier, tableaux de réels ): réel


Début
n ← len(x)
s ← 0.0
Pour j variantDe i+1 à n+1 Faire
s ← s + A[i − 1, j − 1] ∗ x[ j − 1]
FinPour
Retourner s
Fin

1. Les colonnes s’étendent de la 0-ième à la (n − 1)-ième.

2
1.3 Algorithme de Doolittle

Algorithme Doolittle
Début
Entrer la matrice A
L ← In
U ← 0n
Pour i variantDe 1 à n − 1 Faire
Pour j variantDe i à n Faire
Pi −1
ui , j ← ai , j − l u
k=1 i ,k k, j
FinPour
Pour j variantDe i + 1 à n Faire
1
a j ,i − ik=1
¡ P −1 ¢
l j ,i ← u i ,i l j ,k u k,i
FinPour
FinPour
Pn−1
u n,n ← a n,n − l u
k=1 n,k k,n
Afficher L et U
Fin

Fin du document

Vous aimerez peut-être aussi