Factorisation LU et nullité des applications composées
Introduit| English | Sens |
|---|---|
| nullity/ˈnʌlɪti/ | nullité |
| forward substitution/ˈfɔːwəd ˌsʌbstɪˈtjuːʃn/ | substitution directe |
| back substitution/bæk ˌsʌbstɪˈtjuːʃn/ | substitution arrière |
Une machine, plusieurs charges
- Un réseau fixe peut faire face à de nombreux vecteurs de demande $b$. Dans un modèle linéaire $Ax=b$, factoriser la même matrice une seule fois, puis résoudre rapidement pour chaque nouvelle demande.
- Une seconde question porte sur les entrées qu'une chaîne d'applications linéaires perd. Sa nullité compte les directions d'entrée indépendantes envoyées vers zéro ; elle ne compte pas le nombre d'entrées nulles.
Fixer la convention de factorisation
- Pour la résolution, prendre une matrice $n\times n$ inversible et écrire $PA=LU$. Ici $P$ permute les lignes, $L$ est triangulaire inférieure avec des éléments diagonaux $1$, et $U$ est triangulaire supérieure avec des éléments diagonaux non nuls.
- Écrire $d=Pb$ et $y=Ux$. Puis résoudre $Ly=d$ d'abord et $Ux=y$ ensuite. Si $P=I$, cela se réduit à $A=LU$ ; aucune matrice inverse explicite n'est nécessaire.
L'élimination stocke ses multiplicateurs
- Pour $A=\begin{pmatrix}2&1\\6&4\end{pmatrix}$, soustraire $3$ fois la ligne 1 à la ligne 2. Cela donne $U=\begin{pmatrix}2&1\\0&1\end{pmatrix}$ et stocke le multiplicateur dans $L=\begin{pmatrix}1&0\\3&1\end{pmatrix}$. La multiplication vérifie $LU=A$.
- Avec $b=(2,7)$, résoudre d'abord $Ly=b$ : $y_1=2$ et $y_2=7-3(2)=1$. Puis $x_2=1$ et $x_1=(2-1)/2=1/2$. La substitution dans $Ax=b$ vérifie les deux équations.
Let $L=\begin{pmatrix}1&0\\3&1\end{pmatrix}$, $U=\begin{pmatrix}2&1\\0&1\end{pmatrix}$ et $b=(2,7)$. Solve $LUx=b$; give $x_1$.
Difficulté 2/5 · 140 pièces + un petit bonus lors de la première réussite aujourd'hui
Forward substitution gives $y=(2,1)$. Then $x_2=1$ et $x_1=(2-1)/2=1/2$. The product $LU=\begin{pmatrix}2&1\\6&4\end{pmatrix}$ checks the original system.
Progression dans le triangle inférieur
- La substitution avant résout chaque ligne en utilisant les entrées déjà trouvées au-dessus. Avec une diagonale unitaire $L$, utiliser $y_i=d_i-\sum_{j<i}l_{ij}y_j$. Une diagonale non unitaire nécessite une division par $l_{ii}\ne0$.
- Dans l'exemple original à trois lignes, $L=\begin{pmatrix}1&0&0\\2&1&0\\-1&3&1\end{pmatrix}$ et $d=(-1,-1,12)$. Ainsi $y_1=-1$, $y_2=-1-2(-1)=1$ et $y_3=12+(-1)-3(1)=8$.
Solve $Ly=d$ for $L=\begin{pmatrix}2&0\\3&1\end{pmatrix}$ et $d=(4,7)$. Give $y_2$.
Difficulté 2/5 · 140 pièces + un petit bonus lors de la première réussite aujourd'hui
Divide by $l_{11}=2$: $y_1=2$. Then $y_2=7-3(2)=1$. Assuming $y_1=d_1$ would be wrong for this non-unit L.
Rétrogression dans le triangle supérieur
- La substitution arrière commence par le bas : $x_i=(y_i-\sum_{j>i}u_{ij}x_j)/u_{ii}$. La division est valide car chaque pivot diagonal est non nul.
- Pour $U=\begin{pmatrix}2&1&-1\\0&3&2\\0&0&4\end{pmatrix}$ et $y=(-1,1,8)$, obtenir $x_3=2$, $x_2=(1-4)/3=-1$ et $x_1=(-1+1+2)/2=1$. D'où $x=(1,-1,2)$ ; $Ux=y$ et $Ly=b$ vérifient le système original.
Un échange de lignes doit déplacer le côté droit
- Prendre $A=\begin{pmatrix}0&2\\1&3\end{pmatrix}$ et $b=(4,7)$. Échanger les lignes : $P=\begin{pmatrix}0&1\\1&0\end{pmatrix}$ donne $PA=\begin{pmatrix}1&3\\0&2\end{pmatrix}=U$ et $L=I$. Le nouveau côté droit est $Pb=(7,4)$.
- Résoudre $y=(7,4)$, puis $x_2=2$ et $x_1=7-3(2)=1$. Les équations originales donnent $2x_2=4$ et $x_1+3x_2=7$. Utiliser l'ancien $b$ avec $PA$ permettrait de résoudre un système différent.
For an invertible square matrix with $PA=LU$, put the steps for solving $Ax=b$ in order.
Difficulté 3/5 · 200 pièces + un petit bonus lors de la première réussite aujourd'hui
$PAx=LUx=Pb$. Set $y=Ux$, solve the lower-triangular system first, then the upper-triangular system, and check $Ax=b$.
Pour $A=\begin{pmatrix}0&2\\1&3\end{pmatrix}$, $b=(4,7)$ and the row-swap matrix $P$, which pair gives $Pb$ and the solution $x$?
Difficulté 1/5 · 100 pièces + un petit bonus lors de la première réussite aujourd'hui
Swap the right side with the rows. Back substitution in $\begin{pmatrix}1&3\\0&2\end{pmatrix}x=(7,4)$ gives $x_2=2$, then $x_1=1$.
L'inversibilité ne garantit pas une décomposition LU sans pivotage
- La matrice $A$ précédente est inversible, car son déterminant vaut $-2$. Cependant, une matrice unitaire inférieure $L$ donnerait $a_{11}=u_{11}=0$ et $a_{21}=l_{21}u_{11}=0$, ce qui contredit $a_{21}=1$. Cette matrice ne possède donc aucune forme de $A=LU$ sans pivotement.
- En arithmétique exacte, toute matrice carrée inversible admet $PA=LU$ avec des permutations de lignes appropriées. Une entrée principale non nulle seule ne garantit pas que tous les pivots suivants soient non nuls. Dans le calcul numérique, les permutations évitent aussi les petits pivots qui amplifient les erreurs d'arrondi.
Some invertible square matrices require a row exchange before a factorisation with unit-lower L and upper-triangular U exists.
Difficulté 1/5 · 100 pièces + un petit bonus lors de la première réussite aujourd'hui
True. For $A=\begin{pmatrix}0&2\\1&3\end{pmatrix}$, an unpivoted unit-lower factorisation would force $a_{21}=0$. A row swap gives $PA=U$ et $L=I$.
Pour $A=\begin{pmatrix}0&1\\2&3\end{pmatrix}$ et $b=(2,8)$, exhibit $PA=LU$, solve $Ax=b$ and check the original equations. Explain why unit-lower unpivoted LU fails.
Comparer les étapes intermédiaires, l'ordre des opérations et les hypothèses avec la réponse du modèle.
Une diagonale nulle nécessite une approche différente
- Une matrice singulière peut tout de même posséder une factorisation LU : $L=I$ et $U=\begin{pmatrix}1&1\\0&0\end{pmatrix}$ constituent un exemple. Une diagonale nulle empêche la règle de division pour une solution unique ; elle ne prouve pas par elle-même qu'aucune solution n'existe.
- Pour cette $U$, le côté droit $(2,0)$ donne infiniment de solutions $x_1=2-t$, $x_2=t$. Le côté droit $(2,1)$ ne donne aucune solution, car la dernière ligne indiquerait $0=1$. Vérifiez la cohérence et les variables libres plutôt que de diviser par zéro.
Pour $U=\begin{pmatrix}1&1\\0&0\end{pmatrix}$, how many solutions do $Ux=(2,0)$ et $Ux=(2,1)$ have, in that order?
Difficulté 1/5 · 100 pièces + un petit bonus lors de la première réussite aujourd'hui
The first system leaves $x_2$ free. The second requires $0=1$. A zero pivot does not allow a unique-solution division step.
Réutilisez les facteurs, pas l'ancienne solution
- Pour une matrice dense générale $n\times n$, l'élimination standard coûte $O(n^3)$ opérations arithmétiques. Chaque résolution triangulaire coûte $O(n^2)$, donc $k$ côtés droits coûtent $O(n^3+kn^2)$ lorsque les mêmes $P,L,U$ sont réutilisés.
- Recalculez $Pb$, $y$ et $x$ pour chaque côté droit. Vérifiez le résidu $b-Ax$ dans l'ordre des lignes original ; un résidu nul exact confirme une solution exacte. Un petit résidu numérique seul ne garantit pas une faible erreur de solution si $A$ est mal conditionné.
À quelle étape du calcul ?
Séparer la permutation, la résolution directe, la résolution rétroactive et la vérification pour le système inversible 3x3 PA=LU avec L à diagonale unité.
Using standard dense LU, what is the total arithmetic cost for $k$ right sides of the same invertible $n\times n$ matrix, reusing its factors?
Difficulté 1/5 · 100 pièces + un petit bonus lors de la première réussite aujourd'hui
Factor once at cubic cost, then perform two quadratic-cost triangular solves for each right side. This is a general dense estimate.
Suivez les espaces avant les dimensions
- Considérons maintenant $B:V\to W$ et $A:W\to Z$ comme des applications linéaires entre des espaces de dimension finie sur le même corps. Le produit $AB=A\circ B$ applique d'abord $B$. Écrivez $\dim V=n$, $\dim W=m$, $\operatorname{rank}B=r$ et $\dim\ker A=s$.
- Puisque $Bv=0$ implique $A(Bv)=0$, $\ker B\subseteq\ker(AB)$. Les directions supplémentaires perdues apparaissent lorsque $Bv$ est non nul mais appartient à $\ker A$. L'intersection $\operatorname{im}B\cap\ker A$ se situe dans $W$.
Déduire l'identité de composition
- Restreindre $B$ à $T:\ker(AB)\to\operatorname{im}B\cap\ker A$. Cette application est surjective : si $w=Bv$ et $Aw=0$, alors $ABv=0$. Son noyau est exactement $\ker B$.
- Le théorème du rang pour $T$ donne donc $\dim\ker(AB)=\dim\ker B+t$, où $t=\dim(\operatorname{im}B\cap\ker A)$. Autrement dit, $\operatorname{rank}(AB)=r-t$ : seules les directions effectivement atteintes par $B$ peuvent être perdues lors de la seconde application.
For linear maps $B:V\to W$ et $A:W\to Z$, suppose rank $B=4$ and rank $AB=2$. Give $\dim(\operatorname{im}B\cap\ker A)$.
Difficulté 2/5 · 140 pièces + un petit bonus lors de la première réussite aujourd'hui
Rank $AB=r-t$, so $t=4-2=2$.
Bornes de l'intersection dans l'espace intermédiaire
- Pour les sous-espaces $S,K\subseteq W$ de dimensions $r,s$, écrire $t=\dim(S\cap K)$. L'identité $\dim(S+K)=r+s-t\le m$ donne $t\ge r+s-m$. De même $0\le t\le\min(r,s)$.
- La borne inférieure pour $t$ est $\max(0,r+s-m)$ ; la borne supérieure est $\min(r,s)$. Ajouter $\dim\ker B=n-r$ pour les bornes de nullité, ou soustraire $t$ de $r$ pour les bornes de rang. La dimension ambiante est $m$, qui n'est pas nécessairement égale à $n$.
Les deux extrémités de l'intervalle à six dimensions sont atteintes
- Pour les endomorphismes de $\mathbb R^6$, supposons nullité $A=2$ et nullité $B=3$. Alors $r=3$, $s=2$, $m=6$, donc $0\le t\le2$ et $3\le\dim\ker(AB)\le5$.
- Choisir $A=\operatorname{diag}(1,1,1,1,0,0)$. Soit $B$ envoyant ses trois premiers vecteurs de base vers $(e_1,e_2,e_3)$, $(e_1,e_2,e_5)$ ou $(e_1,e_5,e_6)$, et les trois derniers vers zéro. Ces choix donnent $t=0,1,2$ et des nullités $3,4,5$ respectivement.
Activé $\mathbb R^4$, let $A=\operatorname{diag}(1,1,0,0)$ and let $B$ have nullity $2$. Find every possible nullity of $AB$, and construct B for each value.
Comparer les étapes intermédiaires, l'ordre des opérations et les hypothèses avec la réponse du modèle.
Calculer les bornes d'origine à cinq dimensions
- Pour $A,B:\mathbb R^5\to\mathbb R^5$ avec des nullités $1,2$, un rang $B=3$ et $0\le t\le1$. Ainsi, la plus petite nullité possible de $AB$ est $2$, et la plus grande est $3$.
- Fixer $A=\operatorname{diag}(1,1,1,1,0)$. Prendre $B=\operatorname{diag}(1,1,1,0,0)$ donne $t=0$ ; prendre $B=\operatorname{diag}(1,1,0,0,1)$ donne $t=1$. Donc les deux bornes sont atteintes. Additionner les deux nullités donne toujours le mauvais résultat dans le premier cas.
Let $A,B:\mathbb R^5\to\mathbb R^5$ have nullities $1$ et $2$, respectively. What is the largest possible nullity of $AB$?
Difficulté 2/5 · 140 pièces + un petit bonus lors de la première réussite aujourd'hui
Rank $B=3$. The image of $B$ can contain the one-dimensional kernel of $A$, giving nullity $AB=2+1=3$.
Let $A,B:\mathbb R^5\to\mathbb R^5$ have nullities $1$ et $2$, respectively. What is the smallest possible nullity of $AB$?
Difficulté 2/5 · 140 pièces + un petit bonus lors de la première réussite aujourd'hui
The intersection can have dimension $\max(0,3+1-5)=0$. Thus the minimum is $2+0=2$, attained by the two diagonal maps in the lesson.
Des tailles de domaine différentes peuvent forcer une intersection
- Soient $\dim V=7$, $\dim W=4$, $\dim Z=3$, nullité $B=4$ et nullité $A=2$. Alors $r=3$, $s=2$ et $1\le t\le2$. Donc la nullité $AB$ varie de $5$ à $6$, et $1≤\operatorname{rank}(AB)≤2$.
- Pour réaliser les bornes, soit $A(w_1,w_2,w_3,w_4)=(w_1,w_2,0)$. Envoyer les trois premiers vecteurs de base de $V$ vers $(e_1,e_2,e_3)$ pour $t=1$, ou $(e_1,e_3,e_4)$ pour $t=2$ ; envoyer les quatre autres vers zéro. L'espace intermédiaire a pour dimension $4$, et non $7$.
Let $\dim V=7$, $\dim W=4$, nullity $B=4$ and nullity $A=2$ for $B:V\to W$, $A:W\to\mathbb R^3$. What is the smallest possible nullity of $AB$?
Difficulté 2/5 · 140 pièces + un petit bonus lors de la première réussite aujourd'hui
Rank $B=3$. The intersection in the four-dimensional middle space has dimension at least $3+2-4=1$, so the minimum nullity is $4+1=5$.
Let $B:\mathbb R^6\to\mathbb R^3$ have nullity $4$, and $A:\mathbb R^3\to\mathbb R^2$ have nullity $2$. Find the sharp bounds for nullity $AB$ and give maps attaining both.
Comparer les étapes intermédiaires, l'ordre des opérations et les hypothèses avec la réponse du modèle.
Inverser les applications change le problème
- Même pour des matrices carrées, $AB$ et $BA$ n'ont pas nécessairement la même nullité. Prenant $A=\begin{pmatrix}1&0\\0&0\end{pmatrix}$ et $B=\begin{pmatrix}0&1\\0&0\end{pmatrix}$. Alors $AB=B$ a pour rang $1$ et pour nullité $1$, tandis que $BA=0$ a pour nullité $2$.
- L'identité pour $BA$ utilise $\operatorname{im}A\cap\ker B$ et ajoute une nullité $A$. Conserver l'ordre réel des applications. Pour des applications rectangulaires, $AB$ et $BA$ peuvent avoir des dimensions de domaine différentes, ou un produit peut être indéfini.
Two square matrices always give the same nullity for AB and BA.
Difficulté 1/5 · 100 pièces + un petit bonus lors de la première réussite aujourd'hui
False. With $A=\operatorname{diag}(1,0)$ et $B=\begin{pmatrix}0&1\\0&0\end{pmatrix}$, $AB=B$ has nullity $1$ mais $BA=0$ has nullity $2$.
Lire les cas d'égalité depuis l'image
- Si $\operatorname{im}B\cap\ker A=\{0\}$, alors $\ker(AB)=\ker B$ : $A$ est injective sur l'image atteinte par $B$. Une application inversible $A$ garantit cela, mais ce n'est pas nécessaire. Si $\operatorname{im}B\subseteq\ker A$, alors $AB=0$ et nullité $AB=\dim V$.
- Si $B$ est un isomorphisme, il transporte $\ker(AB)$ bijectivement sur $\ker A$, donc leurs dimensions coïncident. Leurs noyaux ne doivent pas être le même sous-espace. En général, la nullité $A$ seule ne dit rien sur lesquelles de ses directions perdues $B$ atteint.
Que garantit la carte information ?
Utiliser B compatible de dimension finie, puis A, avec nullité B=k, dim V=n et t=dim(im B ∩ ker A).
Let $A=\operatorname{diag}(1,0)$ on $\mathbb R^2$ et $B=\begin{pmatrix}0&1\\1&0\end{pmatrix}$. Find $\ker A$ et $\ker(AB)$. Explain why their dimensions agree but their subspaces differ.
Comparer les étapes intermédiaires, l'ordre des opérations et les hypothèses avec la réponse du modèle.
Résumé
- Avec $PA=LU$, permuter le côté droit, résoudre $Ly=Pb$, puis résoudre $Ux=y$. Vérifier les pivots non nuls avant d'utiliser la division, et vérifier $Ax=b$.
- Pour $B:V\to W$ suivi de $A:W\to Z$, ajoutez la nullité $B$ à la dimension du recouvrement image-noyau. Bornez ce recouvrement dans $W$ et vérifiez si le résultat demandé est un minimum, un maximum ou une valeur fixe.
- nullité : La dimension du noyau d'une application linéaire.
- substitution directe : Résolution d'un système triangulaire inférieur en partant de la première ligne vers le bas.
- substitution réciproque : Résolution d'un système triangulaire supérieur en partant de la dernière ligne vers le haut.