Main Content

La traduction de cette page n'est pas à jour. Cliquez ici pour voir la dernière version en anglais.

Factorisations

Introduction

Les trois factorisations matricielles abordées dans cette section utilisent des matrices triangulaires, où tous les éléments au-dessus ou au-dessous de la diagonale sont égaux à zéro. Les systèmes d’équations linéaires impliquant des matrices triangulaires sont faciles et rapides à résoudre à l’aide d’une substitution avant ou arrière.

Factorisation de Cholesky

La factorisation de Cholesky exprime une matrice symétrique comme le produit d’une matrice triangulaire et de sa transposée

A = RR,

R est une matrice triangulaire supérieure.

Toutes les matrices symétriques ne peuvent pas être factorisées de cette manière ; les matrices qui présentent une factorisation de ce type sont dites définies positives. Cela implique que tous les éléments de la diagonale de A sont positifs et que les éléments hors diagonale ne sont « pas trop grands ». Les matrices de Pascal offrent un exemple intéressant. Tout au long de ce chapitre, la matrice A utilisée comme exemple était la matrice de Pascal de dimension 3 x 3. Passez temporairement à la matrice de dimension 6 par 6 :

A = pascal(6)

A =
       1     1     1     1     1     1
       1     2     3     4     5     6
       1     3     6    10    15    21
       1     4    10    20    35    56
       1     5    15    35    70   126
       1     6    21    56   126   252

Les éléments de A sont des coefficients binomiaux. Chaque élément est la somme de ses voisins au nord et à l’ouest. La factorisation de Cholesky est

R = chol(A)

R =
     1     1     1     1     1     1
     0     1     2     3     4     5
     0     0     1     3     6    10
     0     0     0     1     4    10
     0     0     0     0     1     5
     0     0     0     0     0     1

Les éléments sont à nouveau des coefficients binomiaux. Le fait que R'*R est égal à A démontre une identité impliquant les sommes de produits des coefficients binomiaux.

Remarque

La factorisation de Cholesky s’applique également aux matrices complexes. Toute matrice complexe ayant une factorisation de Cholesky satisfait

A′ = A

et est dite hermitienne définie positive.

La factorisation de Cholesky permet de remplacer le système linéaire

Ax = b

par

RRx = b.

Étant donné que l’opérateur antislash reconnaît les systèmes triangulaires, ceci peut être résolu rapidement dans l’environnement MATLAB® avec

x = R\(R'\b)

Si A a une taille de n x n, la complexité algorithmique de chol(A) est O(n3), mais la complexité de la solution précédente utilisant l'operateur antislash est seulement de O(n2).

Factorisation LU

La factorisation LU, ou élimination de Gauss-Jordan, exprime toute matrice carrée A comme le produit d’une permutation d’une matrice triangulaire inférieure et d’une matrice triangulaire supérieure

A = LU,

L est une permutation d’une matrice triangulaire inférieure avec des 1 sur sa diagonale et U est une matrice triangulaire supérieure.

Les permutations sont nécessaires pour des raisons à la fois théoriques et liées au calcul. La matrice

[0110]

ne peut pas être exprimée comme le produit de matrices triangulaires sans échanger ses deux lignes. Bien que la matrice

[ε110]

puisse être exprimée comme le produit de matrices triangulaires, lorsque ε est petite, les éléments dans les facteurs sont grands et amplifient les erreurs, c’est pourquoi même si les permutations ne sont pas strictement nécessaires, elles sont souhaitables. Le pivotement partiel garantit que les éléments de L sont bornés à 1 en amplitude et que les éléments de U ne sont pas beaucoup plus grands que ceux de A.

Par exemple :

[L,U] = lu(B)

L =
    1.0000         0         0
    0.3750    0.5441    1.0000
    0.5000    1.0000         0

U =
    8.0000    1.0000    6.0000
         0    8.5000   -1.0000
         0         0    5.2941

La factorisation LU de A permet de résoudre rapidement le système linéaire

A*x = b

avec

x = U\(L\b)

Les déterminants et les inverses sont calculés à partir de la factorisation LU avec

det(A) = det(L)*det(U)

et

inv(A) = inv(U)*inv(L)

Vous pouvez également calculer les déterminants à l’aide de det(A) = prod(diag(U)), bien que les signes des déterminants puissent être inversés.

Factorisation QR

Une matrice orthogonale, ou une matrice avec des colonnes orthonormales, est une matrice réelle dont les colonnes sont perpendiculaires entre elles et de norme 1. Si Q est orthogonale, alors

QTQ = I,

I est la matrice identité.

Les matrices orthogonales les plus simples sont des rotations de coordonnées à deux dimensions :

[cos(θ)sin(θ)sin(θ)cos(θ)].

Pour les matrices complexes, le terme correspondant est unitaire. Les matrices orthogonales et unitaires sont intéressantes pour le calcul numérique, car elles conservent les longueurs ainsi que les angles et n’amplifient pas les erreurs.

La factorisation orthogonale, ou QR, exprime toute matrice rectangulaire comme le produit d’une matrice orthogonale ou unitaire et d’une matrice triangulaire supérieure. Elle peut également impliquer une permutation de colonnes :

A = QR

ou

AP = QR,

Q est orthogonale ou unitaire, R est triangulaire supérieure et P est une permutation.

Il existe quatre variantes de factorisation QR – complète ou réduite, et avec ou sans permutation de colonnes.

Les systèmes linéaires surdéterminés impliquent une matrice rectangulaire avec plus de lignes que de colonnes, c’est-à-dire de dimension m x n avec m > n. La factorisation QR complete produit une matrice orthogonale carrée Q de dimension m x m et une matrice triangulaire supérieure rectangulaire R de dimension m x n :

C=gallery('uniformdata',[5 4], 0);
[Q,R] = qr(C)

Q =

    0.6191    0.1406   -0.1899   -0.5058    0.5522
    0.1506    0.4084    0.5034    0.5974    0.4475
    0.3954   -0.5564    0.6869   -0.1478   -0.2008
    0.3167    0.6676    0.1351   -0.1729   -0.6370
    0.5808   -0.2410   -0.4695    0.5792   -0.2207


R =

    1.5346    1.0663    1.2010    1.4036
         0    0.7245    0.3474   -0.0126
         0         0    0.9320    0.6596
         0         0         0    0.6648
         0         0         0         0

Souvent, les m – n dernières colonnes de Q ne sont pas nécessaires, car elles sont multipliées par les 0 de la portion basse de R. La factorisation QR réduite produit donc une matrice rectangulaire Q de dimensionm x n avec des colonnes orthonormales et une matrice triangulaire supérieure carrée R de dimension n x n. Pour l’exemple de dimension 5 x 4, le gain est limité, mais pour des matrices plus grandes et très rectangulaires, les gains en temps et en mémoire peuvent être assez significatifs :

[Q,R] = qr(C,0)	
Q =

    0.6191    0.1406   -0.1899   -0.5058
    0.1506    0.4084    0.5034    0.5974
    0.3954   -0.5564    0.6869   -0.1478
    0.3167    0.6676    0.1351   -0.1729
    0.5808   -0.2410   -0.4695    0.5792


R =

    1.5346    1.0663    1.2010    1.4036
         0    0.7245    0.3474   -0.0126
         0         0    0.9320    0.6596
         0         0         0    0.6648

Contrairement à la factorisation LU, la factorisation QR ne nécessite pas de pivotement ou de permutations. Mais une permutation facultative de colonne, déclenchée par la présence d’un troisième argument de sortie, est utile pour détecter une singularité ou une déficience de rang. À chaque étape de la factorisation, la colonne de la matrice restante non factorisée, dont la norme est la plus grande, est utilisée comme base pour cette étape. Ceci permet de garantir que les éléments de la diagonale de R apparaissent par ordre décroissant et que toute dépendance linéaire au niveau des colonnes est presque certainement révélée par l’examen de ces éléments. Pour le petit exemple donné ici, la deuxième colonne de C a une norme plus grande que la première, les deux colonnes sont donc échangées :

[Q,R,P] = qr(C)

Q =
   -0.3522    0.8398   -0.4131
   -0.7044   -0.5285   -0.4739
   -0.6163    0.1241    0.7777

R =
  -11.3578   -8.2762
         0    7.2460
         0         0

P =
     0     1
     1     0

Lorsque les méthodes de factorisation réduite et de permutations de colonnes sont combinées, le troisième argument de sortie est un vecteur de permutation, plutôt qu’une matrice de permutation :

[Q,R,p] = qr(C,0)

Q =
   -0.3522    0.8398
   -0.7044   -0.5285
   -0.6163    0.1241

R =
  -11.3578   -8.2762
         0    7.2460


p =
     2     1

La factorisation QR transforme un système linéaire surdéterminé en un système triangulaire équivalent. L’expression

norm(A*x - b)

équivaut à

norm(Q*R*x - b)

La multiplication par les matrices orthogonales préserve la norme euclidienne, ce qui fait que cette expression est aussi égale à

norm(R*x - y)

y = Q'*b. Étant donné que les dernières m-n lignes de R sont nulles, cette expression se scinde en deux parties :

norm(R(1:n,1:n)*x - y(1:n))

et

norm(y(n+1:m))

Lorsque A est de rang plein, il est possible de la résoudre pour x de manière à ce que la première de ces expressions soit nulle. La seconde expression donne alors la norme du résidu. Lorsque A n’est pas de rang plein, la structure triangulaire de R offre la possibilité de trouver une solution basique au problème des moindres carrés.

Utilisation du calcul multithread pour la factorisation

Le logiciel MATLAB supporte le calcul multithread pour plusieurs fonctions d’algèbre linéaire et des fonctions numériques calculées éléments par éléments. Ces fonctions s’exécutent automatiquement sur plusieurs threads. Pour qu’une fonction ou une expression s’exécute plus rapidement sur plusieurs processeurs, plusieurs conditions doivent être remplies :

  1. La fonction effectue des opérations qui peuvent facilement être partitionnées en sections qui s’exécutent simultanément. Ces sections doivent pouvoir s’exécuter avec une communication limitée entre les processus. Elles doivent nécessiter peu d’opérations séquentielles.

  2. La taille des données est suffisamment importante pour que les avantages d’une exécution simultanée fassent plus que compenser le temps requis pour partitionner les données et gérer des threads d’exécution séparés. Par exemple, la plupart des fonctions s’accélèrent uniquement lorsque la matrice contient au minimum plusieurs milliers d’éléments.

  3. L’opération n’est pas liée à la mémoire ; la durée de traitement ne dépend pas de la durée d’accès à la mémoire. En règle générale, les fonctions plus complexes sont davantage accélérées que les fonctions simples.

lu et qr démontrent une vitesse d'exécution significativement accrue sur des matrices de grandes tailles en double précision (de l’ordre de 10 000 éléments).

Voir aussi

| |

Sujets associés