Factorización LU y nulidad de mapas compuestos
Introducido| English | Significado |
|---|---|
| nullity/ˈnʌlɪti/ | nulidad |
| forward substitution/ˈfɔːwəd ˌsʌbstɪˈtjuːʃn/ | sustitución hacia adelante |
| back substitution/bæk ˌsʌbstɪˈtjuːʃn/ | sustitución hacia atrás |
Una máquina, muchas cargas
- Una red fija puede enfrentar muchos vectores de demanda $b$. En un modelo lineal $Ax=b$, factorice la misma matriz una sola vez y resuelva rápidamente para cada nueva demanda.
- Una segunda pregunta indaga qué entradas pierde una cadena de mapas lineales. Su nulidad cuenta las direcciones independientes de entrada enviadas a cero; no cuenta el número de entradas nulas.
Fije la convención de factorización
- Para la resolución, tome una matriz $n\times n$ invertible y escriba $PA=LU$. Aquí $P$ permuta filas, $L$ es triangular inferior con entradas diagonales $1$, y $U$ es triangular superior con entradas diagonales no nulas.
- Escriba $d=Pb$ y $y=Ux$. Luego resuelva $Ly=d$ primero y $Ux=y$ después. Si $P=I$, esto se reduce a $A=LU$; no se necesita una inversa matricial explícita.
La eliminación almacena sus multiplicadores
- For $A=\begin{pmatrix}2&1\\6&4\end{pmatrix}$, subtract $3$ times row 1 from row 2. This gives $U=\begin{pmatrix}2&1\\0&1\end{pmatrix}$ and stores the multiplier in $L=\begin{pmatrix}1&0\\3&1\end{pmatrix}$. Multiplication checks $LU=A$.
- Con $b=(2,7)$, resuelva primero $Ly=b$: $y_1=2$ y $y_2=7-3(2)=1$. Luego $x_2=1$ y $x_1=(2-1)/2=1/2$. La sustitución en $Ax=b$ verifica ambas ecuaciones.
Let $L=\begin{pmatrix}1&0\\3&1\end{pmatrix}$, $U=\begin{pmatrix}2&1\\0&1\end{pmatrix}$ y $b=(2,7)$. Solve $LUx=b$; give $x_1$.
Dificultad 2/5 · 140 monedas + un pequeño bono en el primer intento de hoy
Forward substitution gives $y=(2,1)$. Then $x_2=1$ y $x_1=(2-1)/2=1/2$. The product $LU=\begin{pmatrix}2&1\\6&4\end{pmatrix}$ checks the original system.
Hacia adelante a través del triángulo inferior
- La sustitución hacia adelante resuelve cada fila usando las entradas ya encontradas por encima. Con diagonal unitaria $L$, use $y_i=d_i-\sum_{j<i}l_{ij}y_j$. Una diagonal no unitaria requiere división por $l_{ii}\ne0$.
- En el ejemplo original de tres filas, $L=\begin{pmatrix}1&0&0\\2&1&0\\-1&3&1\end{pmatrix}$ y $d=(-1,-1,12)$. Por lo tanto, $y_1=-1$, $y_2=-1-2(-1)=1$ y $y_3=12+(-1)-3(1)=8$.
Solve $Ly=d$ for $L=\begin{pmatrix}2&0\\3&1\end{pmatrix}$ y $d=(4,7)$. Give $y_2$.
Dificultad 2/5 · 140 monedas + un pequeño bono en el primer intento de hoy
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.
Hacia atrás a través del triángulo superior
- La sustitución hacia atrás comienza desde abajo: $x_i=(y_i-\sum_{j>i}u_{ij}x_j)/u_{ii}$. La división es válida porque cada pivote diagonal es no nulo.
- Para $U=\begin{pmatrix}2&1&-1\\0&3&2\\0&0&4\end{pmatrix}$ y $y=(-1,1,8)$, obtenga $x_3=2$, $x_2=(1-4)/3=-1$ y $x_1=(-1+1+2)/2=1$. De aquí $x=(1,-1,2)$; $Ux=y$ y $Ly=b$ verifican el sistema original.
Un intercambio de filas debe mover el lado derecho
- Tome $A=\begin{pmatrix}0&2\\1&3\end{pmatrix}$ y $b=(4,7)$. Intercambie las filas: $P=\begin{pmatrix}0&1\\1&0\end{pmatrix}$ da como resultado $PA=\begin{pmatrix}1&3\\0&2\end{pmatrix}=U$ y $L=I$. El nuevo lado derecho es $Pb=(7,4)$.
- Resuelva $y=(7,4)$, luego $x_2=2$ y $x_1=7-3(2)=1$. Las ecuaciones originales dan $2x_2=4$ y $x_1+3x_2=7$. Usar el viejo $b$ con $PA$ resolvería un sistema diferente.
For an invertible square matrix with $PA=LU$, put the steps for solving $Ax=b$ in order.
Dificultad 3/5 · 200 monedas + un pequeño bono en el primer intento de hoy
$PAx=LUx=Pb$. Set $y=Ux$, solve the lower-triangular system first, then the upper-triangular system, and check $Ax=b$.
A favor $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$?
Dificultad 1/5 · 100 monedas + un pequeño bono en el primer intento de hoy
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$.
La invertibilidad no garantiza LU sin permutación
- The previous $A$ is invertible, since its determinant is $-2$. But a unit-lower $L$ would give $a_{11}=u_{11}=0$ and $a_{21}=l_{21}u_{11}=0$, contradicting $a_{21}=1$. So this matrix has no unpivoted $A=LU$ of that form.
- En aritmética exacta, toda matriz cuadrada invertible admite $PA=LU$ con intercambios de filas adecuados. Un elemento principal no nulo por sí solo no garantiza que todos los pivotes posteriores sean no nulos. En trabajo numérico, los intercambios también evitan pivotes pequeños que amplifican el error de redondeo.
Some invertible square matrices require a row exchange before a factorisation with unit-lower L and upper-triangular U exists.
Dificultad 1/5 · 100 monedas + un pequeño bono en el primer intento de hoy
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$ y $L=I$.
A favor $A=\begin{pmatrix}0&1\\2&3\end{pmatrix}$ y $b=(2,8)$, exhibit $PA=LU$, solve $Ax=b$ and check the original equations. Explain why unit-lower unpivoted LU fails.
Compare los pasos intermedios, el orden de mapeo y las suposiciones con la respuesta del modelo.
Una diagonal cero requiere una decisión diferente
- Una matriz singular aún puede tener una factorización LU: $L=I$ y $U=\begin{pmatrix}1&1\\0&0\end{pmatrix}$ son un ejemplo. Una diagonal cero impide la regla de división para solución única; no prueba por sí misma que no exista solución.
- Para esta $U$, el lado derecho $(2,0)$ da infinitas soluciones $x_1=2-t$, $x_2=t$. El lado derecho $(2,1)$ no tiene solución, ya que la última fila indicaría $0=1$. Verifique consistencia y variables libres en lugar de dividir por cero.
A favor $U=\begin{pmatrix}1&1\\0&0\end{pmatrix}$, how many solutions do $Ux=(2,0)$ y $Ux=(2,1)$ have, in that order?
Dificultad 1/5 · 100 monedas + un pequeño bono en el primer intento de hoy
The first system leaves $x_2$ free. The second requires $0=1$. A zero pivot does not allow a unique-solution division step.
Reutilice los factores, no la solución antigua
- Para una matriz densa general $n\times n$, la eliminación estándar cuesta $O(n^3)$ operaciones aritméticas. Cada resolución triangular cuesta $O(n^2)$, por lo que $k$ lados derechos cuestan $O(n^3+kn^2)$ cuando se reutilizan los mismos $P,L,U$.
- Recalcule $Pb$, $y$ y $x$ para cada lado derecho. Verifique el residuo $b-Ax$ en el orden de filas original; cero exacto verifica una solución exacta. Un residuo numérico pequeño solo no garantiza un error de solución pequeño cuando $A$ está mal condicionado.
¿Cuál fase de la resolución?
Separe permutación, sustitución hacia adelante, sustitución hacia atrás y verificación para la invertible 3x3 PA=LU con L de diagonal unitaria.
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?
Dificultad 1/5 · 100 monedas + un pequeño bono en el primer intento de hoy
Factor once at cubic cost, then perform two quadratic-cost triangular solves for each right side. This is a general dense estimate.
Rastre los espacios antes de las dimensiones
- Ahora sea $B:V\to W$ y $A:W\to Z$ aplicaciones lineales entre espacios de dimensión finita sobre el mismo campo. El producto $AB=A\circ B$ aplica $B$ primero. Escriba $\dim V=n$, $\dim W=m$, $\operatorname{rank}B=r$ y $\dim\ker A=s$.
- Dado que $Bv=0$ implica $A(Bv)=0$, $\ker B\subseteq\ker(AB)$. Las direcciones perdidas adicionales surgen cuando $Bv$ es no nulo pero pertenece a $\ker A$. La intersección $\operatorname{im}B\cap\ker A$ vive en $W$.
Derive la identidad de composición
- Restrinja $B$ a $T:\ker(AB)\to\operatorname{im}B\cap\ker A$. Esta aplicación es sobreyectiva: si $w=Bv$ y $Aw=0$, entonces $ABv=0$. Su núcleo es exactamente $\ker B$.
- La relación rango-nulidad para $T$ da $\dim\ker(AB)=\dim\ker B+t$, donde $t=\dim(\operatorname{im}B\cap\ker A)$. Equivalentemente, $\operatorname{rank}(AB)=r-t$: solo las direcciones realmente alcanzadas por $B$ pueden perderse en la segunda aplicación.
For linear maps $B:V\to W$ y $A:W\to Z$, suppose rank $B=4$ and rank $AB=2$. Give $\dim(\operatorname{im}B\cap\ker A)$.
Dificultad 2/5 · 140 monedas + un pequeño bono en el primer intento de hoy
Rank $AB=r-t$, so $t=4-2=2$.
Coteje la intersección en el espacio medio
- Para subespacios $S,K\subseteq W$ con dimensiones $r,s$, escriba $t=\dim(S\cap K)$. La identidad $\dim(S+K)=r+s-t\le m$ da $t\ge r+s-m$. También $0\le t\le\min(r,s)$.
- El límite inferior para $t$ es $\max(0,r+s-m)$; el límite superior es $\min(r,s)$. Añada $\dim\ker B=n-r$ para límites de nulidad, o reste $t$ de $r$ para límites de rango. La dimensión del espacio ambiente es $m$, que no necesariamente es igual a $n$.
Ocurren ambos extremos del rango de seis dimensiones
- Para endomorfismos de $\mathbb R^6$, suponga nulidad $A=2$ y nulidad $B=3$. Entonces $r=3$, $s=2$, $m=6$, por lo que $0\le t\le2$ y $3\le\dim\ker(AB)\le5$.
- Elige $A=\operatorname{diag}(1,1,1,1,0,0)$. Sea $B$ que envíe sus primeros tres vectores base a $(e_1,e_2,e_3)$, $(e_1,e_2,e_5)$ o $(e_1,e_5,e_6)$, y los últimos tres a cero. Estas opciones dan $t=0,1,2$ y nulidades $3,4,5$, respectivamente.
Activado $\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.
Compare los pasos intermedios, el orden de mapeo y las suposiciones con la respuesta del modelo.
Trate los límites originales de cinco dimensiones
- Para $A,B:\mathbb R^5\to\mathbb R^5$ con nulledades $1,2$, rango $B=3$ y $0\le t\le1$. Por lo tanto, la nulidad más pequeña posible de $AB$ es $2$, y la mayor es $3$.
- Fija $A=\operatorname{diag}(1,1,1,1,0)$. Tomar $B=\operatorname{diag}(1,1,1,0,0)$ da $t=0$; tomar $B=\operatorname{diag}(1,1,0,0,1)$ da $t=1$. Así que ambos límites se cumplen. Sumar las dos nulidades siempre da el resultado incorrecto en el primer caso.
Let $A,B:\mathbb R^5\to\mathbb R^5$ have nullities $1$ y $2$, respectively. What is the largest possible nullity of $AB$?
Dificultad 2/5 · 140 monedas + un pequeño bono en el primer intento de hoy
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$ y $2$, respectively. What is the smallest possible nullity of $AB$?
Dificultad 2/5 · 140 monedas + un pequeño bono en el primer intento de hoy
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.
Diferentes tamaños de dominio pueden forzar la superposición
- Sea $\dim V=7$, $\dim W=4$, $\dim Z=3$, nulidad $B=4$ y nulidad $A=2$. Entonces $r=3$, $s=2$ y $1\le t\le2$. Por lo tanto, la nulidad $AB$ varía desde $5$ hasta $6$, y $1≤\operatorname{rank}(AB)≤2$.
- Para realizar los límites, considera $A(w_1,w_2,w_3,w_4)=(w_1,w_2,0)$. Mapea los primeros tres vectores base de $V$ a $(e_1,e_2,e_3)$ para $t=1$, o a $(e_1,e_3,e_4)$ para $t=2$; mapea los otros cuatro a cero. El espacio intermedio tiene dimensión $4$, no $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$?
Dificultad 2/5 · 140 monedas + un pequeño bono en el primer intento de hoy
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.
Compare los pasos intermedios, el orden de mapeo y las suposiciones con la respuesta del modelo.
Invertir los mapas cambia el problema
- Incluso para matrices cuadradas, $AB$ y $BA$ no necesitan tener la misma nulidad. Tome $A=\begin{pmatrix}1&0\\0&0\end{pmatrix}$ y $B=\begin{pmatrix}0&1\\0&0\end{pmatrix}$. Entonces $AB=B$ tiene rango $1$ y nulidad $1$, mientras que $BA=0$ tiene nulidad $2$.
- La identidad para $BA$ usa $\operatorname{im}A\cap\ker B$ y añade nulidad $A$. Mantén el orden real del mapeo. Para mapeos rectangulares, $AB$ y $BA$ pueden tener dimensiones de dominio diferentes, o un producto puede estar indefinido.
Two square matrices always give the same nullity for AB and BA.
Dificultad 1/5 · 100 monedas + un pequeño bono en el primer intento de hoy
False. With $A=\operatorname{diag}(1,0)$ y $B=\begin{pmatrix}0&1\\0&0\end{pmatrix}$, $AB=B$ has nullity $1$ pero $BA=0$ has nullity $2$.
Lea los casos de igualdad a partir de la imagen
- Si $\operatorname{im}B\cap\ker A=\{0\}$, entonces $\ker(AB)=\ker B$: $A$ es inyectiva sobre la imagen alcanzada por $B$. Un $A$ invertible garantiza esto, pero no es necesario. Si $\operatorname{im}B\subseteq\ker A$, entonces $AB=0$ y nulidad $AB=\dim V$.
- Si $B$ es un isomorfismo, lleva $\ker(AB)$ biyectivamente sobre $\ker A$, por lo que sus dimensiones coinciden. Sus núcleos no necesariamente son el mismo subespacio. En general, la nulidad $A$ sola no dice nada sobre cuáles de sus direcciones perdidas $B$ alcanza.
¿Qué garantiza la información del mapa?
Usa B compatible de dimensión finita luego A, con nulidad B=k, dim V=n y t=dim(im B ∩ ker A).
Let $A=\operatorname{diag}(1,0)$ on $\mathbb R^2$ y $B=\begin{pmatrix}0&1\\1&0\end{pmatrix}$. Find $\ker A$ y $\ker(AB)$. Explain why their dimensions agree but their subspaces differ.
Compare los pasos intermedios, el orden de mapeo y las suposiciones con la respuesta del modelo.
Resumen
- Con $PA=LU$, permuta el lado derecho, resuelve $Ly=Pb$, luego resuelve $Ux=y$. Verifica pivotes no nulos antes de usar la división, y verifica $Ax=b$.
- Para $B:V\to W$ seguido por $A:W\to Z$, suma la nulidad $B$ a la dimensión de superposición entre imagen y núcleo. Acota esa superposición en $W$, y verifica si el resultado solicitado es un mínimo, máximo o valor fijo.
- nulidad: La dimensión del núcleo de un mapa lineal.
- sustitución hacia adelante: Resolver un sistema triangular inferior desde la primera fila hacia abajo.
- sustitución hacia atrás: Resolver un sistema triangular superior desde la última fila hacia arriba.