Decomposição LU

Posição no roteiroMódulo 2 de 4 · Tópico 2 de 3

2.2 Decomposição LU

—Nota do lab— / 100XP total—Sequência—

A eliminação, guardada

A eliminação de Gauss resolve $A\mathbf{x}=\mathbf{b}$ subtraindo múltiplos de uma linha das linhas abaixo até obter uma matriz triangular superior $U$ . Vale guardar os multiplicadores usados: colocados abaixo da diagonal de uma matriz triangular inferior $L$ com uns na diagonal, dão $A=LU$ . A decomposição registra toda a eliminação, então o trabalho é feito uma vez e reaproveitado.

A=LU,\qquad L\mathbf{y}=\mathbf{b},\qquad U\mathbf{x}=\mathbf{y}

(1)

Para resolver, primeiro $L\mathbf{y}=\mathbf{b}$ por substituição progressiva (de cima para baixo) e depois $U\mathbf{x}=\mathbf{y}$ por substituição regressiva (de baixo para cima). Cada uma custa cerca de $n^2$ operações, enquanto a fatoração custa cerca de $\tfrac{2}{3}n^3$ . Com muitos lados direitos (muitos cenários sobre a mesma matriz), fatora-se uma vez e paga-se apenas $n^2$ por cenário.

Uma LU à mãoSeja

A=\begin{pmatrix}2&1\\4&5\end{pmatrix}

. O multiplicador é

4/2=2

: subtraia 2 vezes a linha 1 da linha 2 para obter

U=\begin{pmatrix}2&1\\0&3\end{pmatrix}

, e

L=\begin{pmatrix}1&0\\2&1\end{pmatrix}

. Conferência:

LU=\begin{pmatrix}2&1\\4&2+3\end{pmatrix}=A

. Resolvendo

A\mathbf{x}=(3,9)

L\mathbf{y}=\mathbf{b}

dá

y_1=3

y_2=9-2\cdot3=3

; depois

U\mathbf{x}=\mathbf{y}

dá

x_2=1

2x_1+1=3

, então

\mathbf{x}=(1,1)

$L$ : triangular inferior, uns na diagonal, os multiplicadores de eliminação abaixo.
$U$ : triangular superior, resultado da eliminação; sua diagonal guarda os pivôs.
Pivotamento: troque linhas para que o pivô seja grande, dando $PA=LU$ com uma matriz de permutação $P$ .

Um pivô nulo ou minúsculo exige troca de linhasPara

\begin{pmatrix}0&1\\1&1\end{pmatrix}

o primeiro pivô é 0 e a eliminação simples divide por zero, embora a matriz seja perfeitamente invertível. Trocar as linhas resolve. Um pivô minúsculo, em vez de nulo, não trava, mas produz multiplicadores enormes e arruína a precisão, por isso as bibliotecas reais sempre pivotam.

Lab: o que é avaliado

A matriz L15 pts
A matriz U15 pts
Um determinante a partir de U15 pts
Resolver com L e U15 pts
Por que pivotar15 pts
Os passos de uma resolução LU10 pts
Por que fatorar uma vez15 pts

0/ 7 respondidas

1Matriz · vetor15 ptsSem resposta

Seja $A=\begin{pmatrix}2&1\\4&5\end{pmatrix}$ . Preencha o fator triangular inferior $L$ (uns na diagonal) de $A=LU$ sem trocas de linhas.

L =

2Matriz · vetor15 ptsSem resposta

Seja $A=\begin{pmatrix}2&1\\4&5\end{pmatrix}$ . Preencha o fator triangular superior $U$ .

U =

3Resposta numérica15 ptsSem resposta

A matriz $A=\begin{pmatrix}2&1&1\\4&3&3\\8&7&9\end{pmatrix}$ se fatora sem trocas como $L=\begin{pmatrix}1&0&0\\2&1&0\\4&3&1\end{pmatrix}$ , $U=\begin{pmatrix}2&1&1\\0&1&1\\0&0&2\end{pmatrix}$ . Encontre $\det A$ .

\det A =

aceito: ± 0.001

4Resposta numérica15 ptsSem resposta

Seja $A=\begin{pmatrix}2&1\\4&5\end{pmatrix}$ . Use $L=\begin{pmatrix}1&0\\2&1\end{pmatrix}$ e $U=\begin{pmatrix}2&1\\0&3\end{pmatrix}$ para resolver $A\mathbf{x}=(5,13)$ . Quanto vale $x_1$ ?

x_1 =

aceito: ± 0.001

5Escolha15 ptsSem resposta

O que dá errado se se aplica a eliminação simples, sem trocas de linhas, a $\begin{pmatrix}0&1\\1&1\end{pmatrix}$ ?

6Ordenar os passos10 ptsSem resposta

Ponha em ordem os passos para resolver $A\mathbf{x}=\mathbf{b}$ com uma LU com pivotamento.

Arraste para reordenar, ou foque um item, Espaço para levantá-lo, setas para movê-lo e Espaço para soltá-lo.

1Substituição progressiva: resolver $L\mathbf{y}=P\mathbf{b}$
2Fatorar $PA=LU$
3Substituição regressiva: resolver $U\mathbf{x}=\mathbf{y}$
4Aplicar as trocas de linhas ao lado direito: $P\mathbf{b}$

7Explicar com palavras15 ptsSem resposta

Você precisa resolver $A\mathbf{x}=\mathbf{b}$ para 1000 vetores $\mathbf{b}$ diferentes com a mesma $A$ . Em duas frases, diga como a LU ajuda.

Avaliado por:A matriz é fatorada uma só vez e os fatores são reutilizadosCada lado direito adicional custa apenas duas resoluções triangulares baratas, cerca de n ao quadrado0 / 400 caracteres

Modo matemáticaEntrada por teclado ou LaTeXTarefa 1 de 7 · Ctrl ⏎ para verificar

Decomposição LU

Posição no roteiroMódulo 2 de 4 · Tópico 2 de 3

2.2 Decomposição LU

—Nota do lab— / 100XP total—Sequência—

A eliminação, guardada

A=LU,\qquad L\mathbf{y}=\mathbf{b},\qquad U\mathbf{x}=\mathbf{y}

(1)

Uma LU à mãoSeja

A=\begin{pmatrix}2&1\\4&5\end{pmatrix}

. O multiplicador é

4/2=2

: subtraia 2 vezes a linha 1 da linha 2 para obter

U=\begin{pmatrix}2&1\\0&3\end{pmatrix}

, e

L=\begin{pmatrix}1&0\\2&1\end{pmatrix}

. Conferência:

LU=\begin{pmatrix}2&1\\4&2+3\end{pmatrix}=A

. Resolvendo

A\mathbf{x}=(3,9)

L\mathbf{y}=\mathbf{b}

dá

y_1=3

y_2=9-2\cdot3=3

; depois

U\mathbf{x}=\mathbf{y}

dá

x_2=1

2x_1+1=3

, então

\mathbf{x}=(1,1)

$L$ : triangular inferior, uns na diagonal, os multiplicadores de eliminação abaixo.
$U$ : triangular superior, resultado da eliminação; sua diagonal guarda os pivôs.
Pivotamento: troque linhas para que o pivô seja grande, dando $PA=LU$ com uma matriz de permutação $P$ .

Um pivô nulo ou minúsculo exige troca de linhasPara

\begin{pmatrix}0&1\\1&1\end{pmatrix}

Lab: o que é avaliado

A matriz L15 pts
A matriz U15 pts
Um determinante a partir de U15 pts
Resolver com L e U15 pts
Por que pivotar15 pts
Os passos de uma resolução LU10 pts
Por que fatorar uma vez15 pts

0/ 7 respondidas

1Matriz · vetor15 ptsSem resposta

Seja $A=\begin{pmatrix}2&1\\4&5\end{pmatrix}$ . Preencha o fator triangular inferior $L$ (uns na diagonal) de $A=LU$ sem trocas de linhas.

L =

2Matriz · vetor15 ptsSem resposta

Seja $A=\begin{pmatrix}2&1\\4&5\end{pmatrix}$ . Preencha o fator triangular superior $U$ .

U =

3Resposta numérica15 ptsSem resposta

\det A =

aceito: ± 0.001

4Resposta numérica15 ptsSem resposta

Seja $A=\begin{pmatrix}2&1\\4&5\end{pmatrix}$ . Use $L=\begin{pmatrix}1&0\\2&1\end{pmatrix}$ e $U=\begin{pmatrix}2&1\\0&3\end{pmatrix}$ para resolver $A\mathbf{x}=(5,13)$ . Quanto vale $x_1$ ?

x_1 =

aceito: ± 0.001

5Escolha15 ptsSem resposta

O que dá errado se se aplica a eliminação simples, sem trocas de linhas, a $\begin{pmatrix}0&1\\1&1\end{pmatrix}$ ?

6Ordenar os passos10 ptsSem resposta

Ponha em ordem os passos para resolver $A\mathbf{x}=\mathbf{b}$ com uma LU com pivotamento.

Arraste para reordenar, ou foque um item, Espaço para levantá-lo, setas para movê-lo e Espaço para soltá-lo.

1Substituição progressiva: resolver $L\mathbf{y}=P\mathbf{b}$
2Fatorar $PA=LU$
3Substituição regressiva: resolver $U\mathbf{x}=\mathbf{y}$
4Aplicar as trocas de linhas ao lado direito: $P\mathbf{b}$

7Explicar com palavras15 ptsSem resposta

Você precisa resolver $A\mathbf{x}=\mathbf{b}$ para 1000 vetores $\mathbf{b}$ diferentes com a mesma $A$ . Em duas frases, diga como a LU ajuda.

Avaliado por:A matriz é fatorada uma só vez e os fatores são reutilizadosCada lado direito adicional custa apenas duas resoluções triangulares baratas, cerca de n ao quadrado0 / 400 caracteres

Modo matemáticaEntrada por teclado ou LaTeXTarefa 1 de 7 · Ctrl ⏎ para verificar

Decomposição LU

A eliminação, guardada

Lab: o que é avaliado

Entre para executar o seu código.

Decomposição LU

A eliminação, guardada

Lab: o que é avaliado

Entre para executar o seu código.