Comment effectuer une factorisation LU?

Pour résoudre des systèmes de trois équations linéaires ou plus, on convertit généralement le problème en une matrice augmentée et la ligne est réduite à partir de là. Cependant, c'est lent et terriblement inefficace avec plus d'équations. Le nombre d'opérations arithmétiques à calculer augmente par la factorielle de la dimension de la matrice, de sorte que les systèmes de six équations ou plus sont peu pratiques à résoudre à la main. Dans la vraie vie, les systèmes de 1000 équations ne sont pas rares - même 50 équations impliquent de calculer un nombre d'opérations comparable au nombre d'atomes dans l'univers visible.

Il existe une autre méthode qui réduit le nombre d'opérations au cube de la dimension de la matrice. C'est ce qu'on appelle la factorisation LU - elle décompose une matrice en deux matrices triangulaires - $Toi,$ pour le triangulaire supérieur, et $L,$ pour le triangulaire inférieur - et après la configuration appropriée, les solutions sont trouvées par remplacement arrière. Certains ordinateurs utilisent cette méthode pour résoudre rapidement des systèmes qu'il serait difficile de gérer via la réduction de lignes.

Dans la factorisation LU, nous verrons que nous pouvons définir la relation où et sont tous deux des matrices triangulaires.

Dans cet article, nous allons montrer comment effectuer une factorisation LU pour un système de trois équations, pour plus de simplicité.

Pas

1
Commencez par l'équation matricielle. Fondamentalement, un système d'équations peut être écrit en termes d'équation matricielle Ax=b,{\displaystyle A\mathbf {x} =\mathbf {b},} $A{\mathbf {x}}={\mathbf {b}},$ où la matrice A{\displaystyle A} $UNE$ agit sur un vecteur x{ \displaystyle \mathbf {x} } ${\mathbf {x}}$ pour sortir un autre vecteur b.{\displaystyle \mathbf {b}.} ${\mathbf {b}}.$ C'est souvent le cas que l'on souhaite connaître x,{\displaystyle \mathbf {x},} ${\mathbf {x}},$ et ce n'est pas exception. Dans la factorisation LU, nous verrons que nous pouvons définir la relation A=LU,{\displaystyle A=LU,} $A=lu,$ où L{\displaystyle L} $L$ et U{\displaystyle U} $U$ sont toutes deux des matrices triangulaires.
- ${\begin{pmatrix}2and4and1\\-1and1and3\\3and2and5\end{pmatrix}}{\mathbf {x}}={\begin{pmatrix}2\\1\\7\end{pmatrix}}$
2
Réduisez $une$ en ligne en échelon de ligne. La forme en échelon de ligne deviendra notre matrice U.{\displaystyle U.} $U.$
- R2→2R2+R1, R3→2R3−3R1{\displaystyle R_{2}\à 2R_{2}+R_{1},\ R_{3}\à 2R_{3}-3R_{1}} $R_{{2}}\au 2r_{{2}}+r_{{1}},\ r_{{3}}\au 2r_{{3}}-3r_{{1}}$
  - ${\begin{pmatrix}2and4and1\\0and6and7\\0and-8and7\end{pmatrix}}$
- R3→3R3+4R2{\style d'affichage R_{3}\à 3R_{3}+4R_{2}} $R_{{3}}\à 3r_{{3}}+4r_{{2}}$
  - ${\begin{pmatrix}2and4and1\\0and6and7\\0and0and49\end{pmatrix}}=u$
- La matrice est maintenant sous forme d'échelon de ligne.
Pour résoudre des systèmes de trois équations linéaires ou plus, on convertit généralement le problème en une matrice augmentée et la ligne est réduite à partir de là.
3
Obtenez $je$ en annulant vos étapes de réduction de lignes. Cette étape peut être un peu délicate au début, mais nous construisons essentiellement une matrice en revenant en arrière.
- Regardons la réduction de ligne la plus récente R3→3R3+4R2.{\displaystyle R_{3}\to 3R_{3}+4R_{2}.} $R_{{3}}\à 3r_{{3}}+4r_{{2}}.$ Nous avons trouvé la nouvelle ligne 3 en la remplaçant par une combinaison linéaire de l' ancienne lignes de la matrice. Maintenant, nous souhaitons trouver l' ancienne ligne 3, alors résolvez simplement.
  - $R_{{3}}^{{{\text{old}}}}\à {\frac {r_{{3}}-4r_{{2}}}{3}}$
- Cela annule la deuxième réduction de rangée. Maintenant, nous le mettons sous forme matricielle. Appelons cette matrice S2.{\displaystyle S_{2}.} $S_{{2}}.$ Le vecteur colonne à droite clarifie simplement ce que nous faisons - cette matrice que nous construisons est une transformation linéaire qui fait la même chose que ce que nous venons d'écrire ci-dessus. Notez que, puisque nous n'avons rien fait sur les deux premières lignes, les éléments résultants pour les deux lignes de cette matrice sont les mêmes que dans la matrice identité. Seule la troisième ligne change.
  - ${\begin{pmatrix}1et0et0\\0et1et0\\0et-1,33et0,33\end{pmatrix}}{\begin{pmatrix}r_{{1}}\\r_{{2}}\\r_{{ 3}}\end{pmatrix}}$
- Construisez la matrice qui annule la première réduction de ligne. De même, nous résolvons pour les anciennes lignes 2 et 3. Nous appellerons cette matrice S1.{\displaystyle S_{1}.} $S_{{1}}.$
  - $R_{{2}}^{{{\text{old}}}}={\frac {r_{{2}}-r_{{1}}}{2}}$
  - $R_{{3}}^{{{\text{old}}}}={\frac {r_{{3}}+3r_{{1}}}{2}}$
  - $S_{{1}}={\begin{pmatrix}1and0and0\\-0,5and0,5and0\\1,5and0and0,5\end{pmatrix}}$
- Multipliez les matrices S{\displaystyle S} $S$ dans l'ordre dans lequel nous les avons trouvées. Cela signifie que S2S1=L.{\displaystyle S_{2}S_{1}=L.} $S_{{2}}s_{{1}}=l.$ Si vous avez fait la multiplication correctement, vous devriez obtenir une matrice triangulaire inférieure.
  - $L={\begin{pmatrix}1and0and0\\-0,5and0,5and0\\1,5and-0,67and0,17\end{pmatrix}}$
4
Réécrivez l'équation matricielle ax=b{\displaystyle a\mathbf {x} =\mathbf {b} } $a{\mathbf {x}}={\mathbf {b}}$ en termes de lu{\displaystyle lu} $lu$ . Maintenant que nous avons les deux matrices, nous pouvons voir ci-dessous que L{\displaystyle L} $L$ agissant sur le vecteur Ux{\displaystyle U\mathbf {x} } $U{\mathbf {x}}$ sort b.{\displaystyle \mathbf {b}.} ${\mathbf {b}}.$
- $L(u{\mathbf {x}})={\mathbf {b}}$
- Puisque $U{\mathbf {x}}$ est un vecteur, soit ${\mathbf {y}}=u{\mathbf {x}}.$ On voit alors que $L{\mathbf {y}}={\mathbf {b}}.$ Le but ici est d'abord de résoudre pour ${\mathbf {y}},$ puis de se connecter à $U{\mathbf {x}}={\mathbf {y}}$ à résoudre pour ${\mathbf {x}}.$
C'est ce qu'on appelle la factorisation LU - elle décompose une matrice en deux matrices triangulaires - pour le triangulaire supérieur et pour le triangulaire inférieur - et après la configuration appropriée, les solutions sont trouvées par substitution inverse.
5
Résoudre pour ${\mathbf {y}}$ . Parce que nous avons affaire à des matrices triangulaires, la rétro-substitution est la voie à suivre.
- $L{\mathbf {y}}={\begin{pmatrix}y_{{1}}\\-{\frac {1}{2}}y_{{1}}+{\frac {1}{2} }y_{{2}}\\{\frac {3}{2}}y_{{1}}-{\frac {2}{3}}y_{{2}}+{\frac {1}{ 6}}y_{{3}}\end{pmatrix}}={\begin{pmatrix}2\\1\\7\end{pmatrix}}$
- ${\mathbf {y}}={\begin{pmatrix}2\\4\\40\end{pmatrix}}$
6
Résolvez pour ${\mathbf {x}}$ . Cela impliquera à nouveau une rétro-substitution, car U{\displaystyle U} $U$ est triangulaire.
- $U{\mathbf {x}}={\begin{pmatrix}2x_{{1}}+4x_{{2}}+x_{{3}}\\6x_{{2}}+7x_{{3}} \\49x_{{3}}\end{pmatrix}}={\begin{pmatrix}2\\4\\40\end{pmatrix}}$
- ${\mathbf {x}}={\begin{pmatrix}51,759\\-0,29\\40/49\end{pmatrix}}$
- Bien que cette méthode puisse ne pas vous sembler très efficace (et en effet, la factorisation LU pour les systèmes de trois équations n'est pas meilleure que la réduction de ligne), les ordinateurs sont bien équipés pour effectuer la rétro-substitution, donc les résultats montrent vraiment que le nombre de les équations augmentent.

Lisez aussi: Comment tracer des coordonnées polaires?