Fatoração LU e nulidade de mapas compostos
Introduzido| English | Significado |
|---|---|
| nullity/ˈnʌlɪti/ | nulidade |
| forward substitution/ˈfɔːwəd ˌsʌbstɪˈtjuːʃn/ | substituição direta |
| back substitution/bæk ˌsʌbstɪˈtjuːʃn/ | substituição reversa |
Uma máquina, muitas cargas
- Uma rede fixa pode enfrentar muitos vetores de demanda $b$. Em um modelo linear $Ax=b$, fatorar a mesma matriz uma vez e resolver rapidamente para cada nova demanda.
- Uma segunda pergunta questiona quais entradas uma cadeia de transformações lineares perde. A nulidade conta direções de entrada independentes enviadas a zero; não conta o número de entradas nulas.
Estabelecer a convenção de fatoração
- Para a resolução, tome uma matriz $n\times n$ invertível e escreva $PA=LU$. Aqui $P$ permuta linhas, $L$ é triangular inferior com entradas diagonais $1$, e $U$ é triangular superior com entradas diagonais não nulas.
- Escrever $d=Pb$ e $y=Ux$. Resolver então $Ly=d$ primeiro e $Ux=y$ em seguida. Se $P=I$, isso se reduz a $A=LU$; nenhuma inversa explícita da matriz é necessária.
Eliminação armazena seus multiplicadores
- Para $A=\begin{pmatrix}2&1\\6&4\end{pmatrix}$, subtrair $3$ vezes a linha 1 da linha 2. Isso resulta em $U=\begin{pmatrix}2&1\\0&1\end{pmatrix}$ e armazena o multiplicador em $L=\begin{pmatrix}1&0\\3&1\end{pmatrix}$. A verificação multiplica $LU=A$.
- Com $b=(2,7)$, resolver primeiro $Ly=b$: $y_1=2$ e $y_2=7-3(2)=1$. Depois $x_2=1$ e $x_1=(2-1)/2=1/2$. A substituição em $Ax=b$ verifica ambas as equações.
Let $L=\begin{pmatrix}1&0\\3&1\end{pmatrix}$, $U=\begin{pmatrix}2&1\\0&1\end{pmatrix}$ e $b=(2,7)$. Solve $LUx=b$; give $x_1$.
Dificuldade 2/5 · Moedas 140 + pequeno bônus na primeira conclusão hoje
Forward substitution gives $y=(2,1)$. Then $x_2=1$ e $x_1=(2-1)/2=1/2$. The product $LU=\begin{pmatrix}2&1\\6&4\end{pmatrix}$ checks the original system.
Substituição direta através do triângulo inferior
- A substituição direta resolve cada linha usando entradas já encontradas acima dela. Com diagonal unitária $L$, usar $y_i=d_i-\sum_{j<i}l_{ij}y_j$. Uma diagonal não unitária exige divisão por $l_{ii}\ne0$.
- No exemplo original de três linhas, $L=\begin{pmatrix}1&0&0\\2&1&0\\-1&3&1\end{pmatrix}$ e $d=(-1,-1,12)$. Logo $y_1=-1$, $y_2=-1-2(-1)=1$ e $y_3=12+(-1)-3(1)=8$.
Solve $Ly=d$ for $L=\begin{pmatrix}2&0\\3&1\end{pmatrix}$ e $d=(4,7)$. Give $y_2$.
Dificuldade 2/5 · Moedas 140 + pequeno bônus na primeira conclusão hoje
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.
Substituição reversa através do triângulo superior
- A substituição reversa começa na parte inferior: $x_i=(y_i-\sum_{j>i}u_{ij}x_j)/u_{ii}$. A divisão é válida porque cada pivô diagonal é não nulo.
- Para $U=\begin{pmatrix}2&1&-1\\0&3&2\\0&0&4\end{pmatrix}$ e $y=(-1,1,8)$, obtenha $x_3=2$, $x_2=(1-4)/3=-1$ e $x_1=(-1+1+2)/2=1$. Logo $x=(1,-1,2)$; $Ux=y$ e $Ly=b$ verificam o sistema original.
Uma troca de linhas deve mover o lado direito
- Pegar $A=\begin{pmatrix}0&2\\1&3\end{pmatrix}$ e $b=(4,7)$. Trocar as linhas: $P=\begin{pmatrix}0&1\\1&0\end{pmatrix}$ resulta em $PA=\begin{pmatrix}1&3\\0&2\end{pmatrix}=U$ e $L=I$. O novo lado direito é $Pb=(7,4)$.
- Resolver $y=(7,4)$, então $x_2=2$ e $x_1=7-3(2)=1$. As equações originais fornecem $2x_2=4$ e $x_1+3x_2=7$. Usar o antigo $b$ com $PA$ resolveria um sistema diferente.
For an invertible square matrix with $PA=LU$, put the steps for solving $Ax=b$ in order.
Dificuldade 3/5 · Moedas 200 + pequeno bônus na primeira conclusão hoje
$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$?
Dificuldade 1/5 · Moedas 100 + pequeno bônus na primeira conclusão hoje
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$.
Invertibilidade não garante LU sem pivoteamento
- A matriz $A$ anterior é invertível, pois seu determinante é $-2$. Mas uma matriz unitária inferior $L$ resultaria em $a_{11}=u_{11}=0$ e $a_{21}=l_{21}u_{11}=0$, contradizendo $a_{21}=1$. Portanto, esta matriz não possui fatoração LU sem permutações $A=LU$ dessa forma.
- Em aritmética exata, toda matriz quadrada invertível admite fatoração LU $PA=LU$ com trocas de linha adequadas. Um pivô principal não nulo isoladamente não garante que todos os pivôs subsequentes sejam não nulos. No trabalho numérico, as trocas também evitam pivôs pequenos que amplificam erros de arredondamento.
Some invertible square matrices require a row exchange before a factorisation with unit-lower L and upper-triangular U exists.
Dificuldade 1/5 · Moedas 100 + pequeno bônus na primeira conclusão hoje
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$ e $L=I$.
A favor $A=\begin{pmatrix}0&1\\2&3\end{pmatrix}$ e $b=(2,8)$, exhibit $PA=LU$, solve $Ax=b$ and check the original equations. Explain why unit-lower unpivoted LU fails.
Compare os passos intermediários, a ordem das permutações e as suposições com a resposta modelo.
Uma diagonal nula exige uma decisão diferente
- Uma matriz singular ainda pode ter fatoração LU: $L=I$ e $U=\begin{pmatrix}1&1\\0&0\end{pmatrix}$ são um exemplo. Uma diagonal nula impede a regra de divisão para solução única; ela própria não prova que nenhuma solução existe.
- Para este $U$, lado direito $(2,0)$ oferece infinitas soluções $x_1=2-t$, $x_2=t$. Lado direito $(2,1)$ não tem solução, pois a última linha diria $0=1$. Verifique consistência e variáveis livres em vez de dividir por zero.
A favor $U=\begin{pmatrix}1&1\\0&0\end{pmatrix}$, how many solutions do $Ux=(2,0)$ e $Ux=(2,1)$ have, in that order?
Dificuldade 1/5 · Moedas 100 + pequeno bônus na primeira conclusão hoje
The first system leaves $x_2$ free. The second requires $0=1$. A zero pivot does not allow a unique-solution division step.
Reutilize os fatores, não a solução antiga
- Para uma matriz densa geral $n\times n$, a eliminação padrão custa $O(n^3)$ operações aritméticas. Cada resolução triangular custa $O(n^2)$, portanto $k$ lados direitos custam $O(n^3+kn^2)$ quando os mesmos fatores $P,L,U$ são reutilizados.
- Recalcule $Pb$, $y$ e $x$ para cada lado direito. Verifique o resíduo $b-Ax$ na ordem original das linhas; zero exato verifica uma solução exata. Um resíduo numérico pequeno sozinho não garante erro de solução pequeno quando $A$ está mal condicionado.
Qual fase da resolução?
Separe permutação, resolução direta, resolução reversa e verificação para inversível ⟨3⟩x3 PA=LU com L triangular unitária.
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?
Dificuldade 1/5 · Moedas 100 + pequeno bônus na primeira conclusão hoje
Factor once at cubic cost, then perform two quadratic-cost triangular solves for each right side. This is a general dense estimate.
Rastreie os espaços antes das dimensões
- Agora, seja $B:V\to W$ e $A:W\to Z$ aplicações lineares entre espaços de dimensão finita sobre o mesmo corpo. O produto $AB=A\circ B$ aplica $B$ primeiro. Escreva $\dim V=n$, $\dim W=m$, $\operatorname{rank}B=r$ e $\dim\ker A=s$.
- Como $Bv=0$ implica $A(Bv)=0$, $\ker B\subseteq\ker(AB)$. As direções extras perdidas surgem quando $Bv$ é não nulo, mas pertence a $\ker A$. A interseção $\operatorname{im}B\cap\ker A$ vive em $W$.
Derive a identidade da composição
- Restrinja $B$ a $T:\ker(AB)\to\operatorname{im}B\cap\ker A$. Este mapa é sobrejetor: se $w=Bv$ e $Aw=0$, então $ABv=0$. Seu kernel é exatamente $\ker B$.
- Rank–nullity para $T$ fornece $\dim\ker(AB)=\dim\ker B+t$, onde $t=\dim(\operatorname{im}B\cap\ker A)$. Equivalentemente, $\operatorname{rank}(AB)=r-t$: apenas direções realmente alcançadas por $B$ podem ser perdidas no segundo mapa.
For linear maps $B:V\to W$ e $A:W\to Z$, suppose rank $B=4$ and rank $AB=2$. Give $\dim(\operatorname{im}B\cap\ker A)$.
Dificuldade 2/5 · Moedas 140 + pequeno bônus na primeira conclusão hoje
Rank $AB=r-t$, so $t=4-2=2$.
Limite a interseção no espaço intermediário
- Para subespaços $S,K\subseteq W$ com dimensões $r,s$, escreva $t=\dim(S\cap K)$. A identidade $\dim(S+K)=r+s-t\le m$ resulta em $t\ge r+s-m$. Além disso, $0\le t\le\min(r,s)$.
- O limite inferior para $t$ é $\max(0,r+s-m)$; o limite superior é $\min(r,s)$. Adicione $\dim\ker B=n-r$ para limites de nulidade, ou subtraia $t$ de $r$ para limites de posto. A dimensão ambiente é $m$, que pode não ser igual a $n$.
Ambos os extremos do intervalo de seis dimensões ocorrem
- Para endomorfismos de $\mathbb R^6$, suponha nuloide $A=2$ e nuloide $B=3$. Então $r=3$, $s=2$, $m=6$, logo $0\le t\le2$ e $3\le\dim\ker(AB)\le5$.
- Escolha $A=\operatorname{diag}(1,1,1,1,0,0)$. Deixe $B$ enviar seus primeiros três vetores base para $(e_1,e_2,e_3)$, $(e_1,e_2,e_5)$ ou $(e_1,e_5,e_6)$, e os últimos três para zero. Essas escolhas produzem $t=0,1,2$ e nulidades $3,4,5$, respectivamente.
Ativo $\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 os passos intermediários, a ordem das permutações e as suposições com a resposta modelo.
Calcule os limites originais de cinco dimensões
- Para $A,B:\mathbb R^5\to\mathbb R^5$ com nulidades $1,2$, posto $B=3$ e $0\le t\le1$. Logo a menor possível nulidade de $AB$ é $2$, e a maior é $3$.
- Fixe $A=\operatorname{diag}(1,1,1,1,0)$. Tomar $B=\operatorname{diag}(1,1,1,0,0)$ resulta em $t=0$; tomar $B=\operatorname{diag}(1,1,0,0,1)$ resulta em $t=1$. Assim, ambos os limites ocorrem. Somar as duas nulidades sempre dá a resposta errada no primeiro caso.
Let $A,B:\mathbb R^5\to\mathbb R^5$ have nullities $1$ e $2$, respectively. What is the largest possible nullity of $AB$?
Dificuldade 2/5 · Moedas 140 + pequeno bônus na primeira conclusão hoje
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$ e $2$, respectively. What is the smallest possible nullity of $AB$?
Dificuldade 2/5 · Moedas 140 + pequeno bônus na primeira conclusão hoje
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 tamanhos de domínio podem forçar sobreposição
- Sejam $\dim V=7$, $\dim W=4$, $\dim Z=3$, nuloide $B=4$ e nuloide $A=2$. Então $r=3$, $s=2$ e $1\le t\le2$. Logo o nuloide de $AB$ varia de $5$ a $6$, e $1≤\operatorname{rank}(AB)≤2$.
- Para realizar os limites, considere $A(w_1,w_2,w_3,w_4)=(w_1,w_2,0)$. Mapeie os primeiros três vetores da base de $V$ para $(e_1,e_2,e_3)$ para $t=1$, ou para $(e_1,e_3,e_4)$ para $t=2$; mapeie os outros quatro para zero. O espaço intermediário tem dimensão $4$, não $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$?
Dificuldade 2/5 · Moedas 140 + pequeno bônus na primeira conclusão hoje
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 os passos intermediários, a ordem das permutações e as suposições com a resposta modelo.
Inverter os mapas altera o problema
- Mesmo para matrizes quadradas, $AB$ e $BA$ não precisam ter a mesma nulidade. Considere $A=\begin{pmatrix}1&0\\0&0\end{pmatrix}$ e $B=\begin{pmatrix}0&1\\0&0\end{pmatrix}$. Então $AB=B$ tem posto $1$ e nulidade $1$, enquanto $BA=0$ tem nulidade $2$.
- A identidade para $BA$ usa $\operatorname{im}A\cap\ker B$ e adiciona nulidade $A$. Mantenha a ordem real do mapeamento. Para mapeamentos retangulares, $AB$ e $BA$ podem ter dimensões de domínio diferentes, ou um produto pode ser indefinido.
Two square matrices always give the same nullity for AB and BA.
Dificuldade 1/5 · Moedas 100 + pequeno bônus na primeira conclusão hoje
False. With $A=\operatorname{diag}(1,0)$ e $B=\begin{pmatrix}0&1\\0&0\end{pmatrix}$, $AB=B$ has nullity $1$ mas $BA=0$ has nullity $2$.
Leia os casos de igualdade na imagem
- Se $\operatorname{im}B\cap\ker A=\{0\}$, então $\ker(AB)=\ker B$: $A$ é injetiva na imagem alcançada por $B$. Um $A$ invertível garante isso, mas não é necessário. Se $\operatorname{im}B\subseteq\ker A$, então $AB=0$ e nulidade $AB=\dim V$.
- Se $B$ for um isomorfismo, ele transporta $\ker(AB)$ bijetivamente para $\ker A$, logo suas dimensões coincidem. Seus núcleos não precisam ser o mesmo subespaço. Em geral, a nulidade $A$ sozinha não diz nada sobre quais de suas direções perdidas $B$ alcança.
O que as informações do mapa garantem?
Use B compatível de dimensão finita, depois A, com nulidade B=k, dim V=n e t=dim(im B ∩ ker A).
Let $A=\operatorname{diag}(1,0)$ on $\mathbb R^2$ e $B=\begin{pmatrix}0&1\\1&0\end{pmatrix}$. Find $\ker A$ e $\ker(AB)$. Explain why their dimensions agree but their subspaces differ.
Compare os passos intermediários, a ordem das permutações e as suposições com a resposta modelo.
Resumo
- Com $PA=LU$, permutar o lado direito, resolver $Ly=Pb$, depois resolver $Ux=y$. Verificar pivots não nulos antes da divisão e confirmar $Ax=b$.
- Para $B:V\to W$ seguido por $A:W\to Z$, some a nulidade $B$ à dimensão da interseção imagem–núcleo. Limite essa interseção em $W$, e verifique se o resultado solicitado é mínimo, máximo ou valor fixo.
- nulidade: A dimensão do kernel de um mapa linear.
- substituição direta: Resolver um sistema triangular inferior da primeira linha para baixo.
- substituição reversa: Resolver um sistema triangular superior da última linha para cima.