solução numérica de sistemas lineares de grande porte · 2017-03-24 · descrição da solução...
TRANSCRIPT
![Page 1: Solução Numérica de Sistemas Lineares de Grande Porte · 2017-03-24 · Descrição da solução de 17 sistemas lineares até 5×5 por eliminação Gaussiana. Jiu Zhang Suan Shu](https://reader036.vdocumento.com/reader036/viewer/2022081522/5f3c1e3f2761ee4a942446fd/html5/thumbnails/1.jpg)
Solução Numérica de Sistemas Lineares de Grande Porte
Aurelio R. L. Oliveira
IMECC – UNICAMP
Sistemas Lineares – 2016 – p.1/37
![Page 2: Solução Numérica de Sistemas Lineares de Grande Porte · 2017-03-24 · Descrição da solução de 17 sistemas lineares até 5×5 por eliminação Gaussiana. Jiu Zhang Suan Shu](https://reader036.vdocumento.com/reader036/viewer/2022081522/5f3c1e3f2761ee4a942446fd/html5/thumbnails/2.jpg)
Resumo
⋆ Matrizes
⋆ Sistemas Lineares
⋆ Sistemas Triangulares
⋆ Decomposições
⋆ Matrizes Simétricas
⋆ Eliminação Gaussiana
⋆ Pivoteamento
⋆ Implementação
⋆ Decomposição SVD
⋆ Conclusões
Sistemas Lineares – 2016 – p.2/37
![Page 3: Solução Numérica de Sistemas Lineares de Grande Porte · 2017-03-24 · Descrição da solução de 17 sistemas lineares até 5×5 por eliminação Gaussiana. Jiu Zhang Suan Shu](https://reader036.vdocumento.com/reader036/viewer/2022081522/5f3c1e3f2761ee4a942446fd/html5/thumbnails/3.jpg)
Matriz Retangular
M =
813 622 536
393 316 298
173 222 222
161 173 188
156 118 141
154 129 127
140 122 152
135 172 166
97 79 112
92 99 95
88 86 120
71 56 80
61 76 99
55 74 98
50 57 111
Sistemas Lineares – 2016 – p.3/37
![Page 4: Solução Numérica de Sistemas Lineares de Grande Porte · 2017-03-24 · Descrição da solução de 17 sistemas lineares até 5×5 por eliminação Gaussiana. Jiu Zhang Suan Shu](https://reader036.vdocumento.com/reader036/viewer/2022081522/5f3c1e3f2761ee4a942446fd/html5/thumbnails/4.jpg)
Matriz Quadrada
A =
393 316 298
45 38 29
438 354 327
Sistemas Lineares – 2016 – p.4/37
![Page 5: Solução Numérica de Sistemas Lineares de Grande Porte · 2017-03-24 · Descrição da solução de 17 sistemas lineares até 5×5 por eliminação Gaussiana. Jiu Zhang Suan Shu](https://reader036.vdocumento.com/reader036/viewer/2022081522/5f3c1e3f2761ee4a942446fd/html5/thumbnails/5.jpg)
Matriz Quadrada
A =
393 316 298
45 38 29
438 354 327
Matriz Transposta
AT=
393 45 438
316 38 354
298 29 327
Posto
O posto de uma matriz quadrada é dado pelo número de linhas (colunas) linearmenteindependentes.
posto(A) = 2Sistemas Lineares – 2016 – p.4/37
![Page 6: Solução Numérica de Sistemas Lineares de Grande Porte · 2017-03-24 · Descrição da solução de 17 sistemas lineares até 5×5 por eliminação Gaussiana. Jiu Zhang Suan Shu](https://reader036.vdocumento.com/reader036/viewer/2022081522/5f3c1e3f2761ee4a942446fd/html5/thumbnails/6.jpg)
Motivação
⋆ Um dos problemas mais complexos que sabemos resolvercom exatidão
⋆ Pode ser aplicado na solução de centenas de classesproblemas
⋆ Aplicação nas mais diversas áreas do conhecimentohumano
⋆ Problema dos quadrados mínimos
⋆ Problemas de otimização
⋆ Solução numérica de EDPs
Sistemas Lineares – 2016 – p.5/37
![Page 7: Solução Numérica de Sistemas Lineares de Grande Porte · 2017-03-24 · Descrição da solução de 17 sistemas lineares até 5×5 por eliminação Gaussiana. Jiu Zhang Suan Shu](https://reader036.vdocumento.com/reader036/viewer/2022081522/5f3c1e3f2761ee4a942446fd/html5/thumbnails/7.jpg)
Evolução
⋆ 263. Descrição da solução de 17 sistemas lineares até 5× 5 poreliminação Gaussiana. Jiu Zhang Suan Shu Zhu “Nove capítulos daarte da matemática”, Liu Hui.
⋆ 1951. Pilot ICE resolve um sistema linear 17× 17 em algumas horas.
⋆ 1991. Pivoteamento parcial não é numericamente estável.
⋆ 2000. Resolução de sistemas lineares com milhões de equações emalgumas horas.
⋆ 2006. Resolução de sistemas lineares com bilhões de equações emalgumas horas.
⋆ 2012. Possível resolução de sistemas lineares com trilhões deequações em algumas horas.
Sistemas Lineares – 2016 – p.6/37
![Page 8: Solução Numérica de Sistemas Lineares de Grande Porte · 2017-03-24 · Descrição da solução de 17 sistemas lineares até 5×5 por eliminação Gaussiana. Jiu Zhang Suan Shu](https://reader036.vdocumento.com/reader036/viewer/2022081522/5f3c1e3f2761ee4a942446fd/html5/thumbnails/8.jpg)
� � �� � � � � � � � � � � � � � � � � � ��� � � ��� � � � �
�� � � �� � � � � � � � ��� � � � � � � � � �� � � � � � � �� � �� � � � � � ���� � ���Sistemas Lineares – 2016 – p.7/37
![Page 9: Solução Numérica de Sistemas Lineares de Grande Porte · 2017-03-24 · Descrição da solução de 17 sistemas lineares até 5×5 por eliminação Gaussiana. Jiu Zhang Suan Shu](https://reader036.vdocumento.com/reader036/viewer/2022081522/5f3c1e3f2761ee4a942446fd/html5/thumbnails/9.jpg)
Sistemas Lineares – 2016 – p.8/37
![Page 10: Solução Numérica de Sistemas Lineares de Grande Porte · 2017-03-24 · Descrição da solução de 17 sistemas lineares até 5×5 por eliminação Gaussiana. Jiu Zhang Suan Shu](https://reader036.vdocumento.com/reader036/viewer/2022081522/5f3c1e3f2761ee4a942446fd/html5/thumbnails/10.jpg)
Sistemas Lineares
Dado Ax = b, as seguintes afirmações são equivalentes:
1. Dado um vetor b, o sistema linear tem exatamente umasolução;
2. Se existe uma solução de Ax = b, então esta solução éúnica;
3. Ax = 0 → x = 0;
4. As colunas (linhas) de A são linearmente independentes;
5. Existe uma matriz A−1 tal queA−1A = AA−1 = I;
6. det(A) 6= 0.Sistemas Lineares – 2016 – p.9/37
![Page 11: Solução Numérica de Sistemas Lineares de Grande Porte · 2017-03-24 · Descrição da solução de 17 sistemas lineares até 5×5 por eliminação Gaussiana. Jiu Zhang Suan Shu](https://reader036.vdocumento.com/reader036/viewer/2022081522/5f3c1e3f2761ee4a942446fd/html5/thumbnails/11.jpg)
Determinantes
Pequenas alterações da matriz provocam grandes alterações novalor do determinante
det(σA) = σn det(A)
Se n = 30 (sistema pequeno) e det(A) = 1
det(0, 1 A) = 10−30
Muito úteis na teoria.
Na prática tem pouco valor.
Sistemas Lineares – 2016 – p.10/37
![Page 12: Solução Numérica de Sistemas Lineares de Grande Porte · 2017-03-24 · Descrição da solução de 17 sistemas lineares até 5×5 por eliminação Gaussiana. Jiu Zhang Suan Shu](https://reader036.vdocumento.com/reader036/viewer/2022081522/5f3c1e3f2761ee4a942446fd/html5/thumbnails/12.jpg)
Matrizes não Singulares
As matrizes que satisfazem qualquer das condições (1-6) sãodenominadas não singulares e a matriz A−1 é denominadamatriz inversa.
Propriedades
1. AB é não singular ⇔ A e B são não singulares(AB)−1 = B−1A−1
2. (AT )−1 = (A−1)T = A−T
Sistemas Lineares – 2016 – p.11/37
![Page 13: Solução Numérica de Sistemas Lineares de Grande Porte · 2017-03-24 · Descrição da solução de 17 sistemas lineares até 5×5 por eliminação Gaussiana. Jiu Zhang Suan Shu](https://reader036.vdocumento.com/reader036/viewer/2022081522/5f3c1e3f2761ee4a942446fd/html5/thumbnails/13.jpg)
Matrizes Inversas
A solução de um sistema linear Ax = b pode ser escrita emtermos de matrizes inversas
A−1b = A−1Ax = Ix = x
Em geral, calcular a inversa não é a melhor opção.Mesmo para problemas em uma dimensão a inversa não énormalmente utilizada.
Matrizes Triangulares
Sistemas Lineares – 2016 – p.12/37
![Page 14: Solução Numérica de Sistemas Lineares de Grande Porte · 2017-03-24 · Descrição da solução de 17 sistemas lineares até 5×5 por eliminação Gaussiana. Jiu Zhang Suan Shu](https://reader036.vdocumento.com/reader036/viewer/2022081522/5f3c1e3f2761ee4a942446fd/html5/thumbnails/14.jpg)
Matrizes Triangulares
Uma matriz é triangular inferior se todos os elementos acima da diagonalsão nulos.
L =
393 0 0
45 38 0
438 354 327
Uma matriz é triangular superior se todos os elementos abaixo dadiagonal são nulos.
U =
393 316 298
0 38 29
0 0 327
Sistemas Lineares – 2016 – p.13/37
![Page 15: Solução Numérica de Sistemas Lineares de Grande Porte · 2017-03-24 · Descrição da solução de 17 sistemas lineares até 5×5 por eliminação Gaussiana. Jiu Zhang Suan Shu](https://reader036.vdocumento.com/reader036/viewer/2022081522/5f3c1e3f2761ee4a942446fd/html5/thumbnails/15.jpg)
Sistemas Lineares Triangulares
Sistemas triangulares não singulares são fáceis de resolveratravés de substituição de variáveis.
for(i = 1; i ≤ n; i++){
....for(j = 1; j < i; j ++)
.........b[i] = b[i]− l[i][j] ∗ b[j];
....b[i] = b[i]/l[i][j];
}
São necessárias aproximadamente n2
2operações de ponto flutu-
ante para resolver sistemas triangulares.
Sistemas Lineares – 2016 – p.14/37
![Page 16: Solução Numérica de Sistemas Lineares de Grande Porte · 2017-03-24 · Descrição da solução de 17 sistemas lineares até 5×5 por eliminação Gaussiana. Jiu Zhang Suan Shu](https://reader036.vdocumento.com/reader036/viewer/2022081522/5f3c1e3f2761ee4a942446fd/html5/thumbnails/16.jpg)
Decomposição LU
Suponha que A = LU . Se A é não singular, então L e U também são nãosingulares. Podemos escrever o sistema Ax = b na forma LUx = b econsequentemente
Ux = L−1b ≡ y
De forma geral podemos escrever o seguinte algoritmo para resolverAx = b:
1. A = LU
2. Ly = b
3. Ux = y
São necessárias aproximadamente n3
3operações de ponto flutuante no cál-
culo da decomposição LU
Sistemas Lineares – 2016 – p.15/37
![Page 17: Solução Numérica de Sistemas Lineares de Grande Porte · 2017-03-24 · Descrição da solução de 17 sistemas lineares até 5×5 por eliminação Gaussiana. Jiu Zhang Suan Shu](https://reader036.vdocumento.com/reader036/viewer/2022081522/5f3c1e3f2761ee4a942446fd/html5/thumbnails/17.jpg)
Decomposição LDU
A decomposição LU não é única.A decomposição LDU por sua vez é única. Onde D é umamatriz diagonal, L e U além de triangulares são unitárias.A partir da decomposição LDU , podemos definir váriasdecomposições importantes:
⋆ (LD)U . Decomposição de Crout. U é unitária.
⋆ L(DU). Decomposição de Doolittle. L é unitária. Equivalea eliminação Gaussiana.
⋆ LDLT . Quando A é simétrica.
⋆ (LD12) (D
12LT ). Quando A é simétrica definida positiva.
Decomposição de Cholesky.Sistemas Lineares – 2016 – p.16/37
![Page 18: Solução Numérica de Sistemas Lineares de Grande Porte · 2017-03-24 · Descrição da solução de 17 sistemas lineares até 5×5 por eliminação Gaussiana. Jiu Zhang Suan Shu](https://reader036.vdocumento.com/reader036/viewer/2022081522/5f3c1e3f2761ee4a942446fd/html5/thumbnails/18.jpg)
Matriz Definida Positiva
Uma matriz não singular que pode ser decomposta na formaA = LLT tem as seguintes propriedades:
1. A é simétrica
2. x 6= 0 ⇒ xtAx > 0
3. A decomposição A = LLT é única
Sistemas Lineares – 2016 – p.17/37
![Page 19: Solução Numérica de Sistemas Lineares de Grande Porte · 2017-03-24 · Descrição da solução de 17 sistemas lineares até 5×5 por eliminação Gaussiana. Jiu Zhang Suan Shu](https://reader036.vdocumento.com/reader036/viewer/2022081522/5f3c1e3f2761ee4a942446fd/html5/thumbnails/19.jpg)
Matriz Definida Positiva
Uma matriz não singular que pode ser decomposta na formaA = LLT tem as seguintes propriedades:
1. A é simétrica
2. x 6= 0 ⇒ xtAx > 0
3. A decomposição A = LLT é única
⋆ Necessita armazenar apenas metade da matriz
⋆ Realiza aproximadamente metade das operações de umadecomposição LU (n
3
6)
Sistemas Lineares – 2016 – p.17/37
![Page 20: Solução Numérica de Sistemas Lineares de Grande Porte · 2017-03-24 · Descrição da solução de 17 sistemas lineares até 5×5 por eliminação Gaussiana. Jiu Zhang Suan Shu](https://reader036.vdocumento.com/reader036/viewer/2022081522/5f3c1e3f2761ee4a942446fd/html5/thumbnails/20.jpg)
Eliminação Gaussiana
Na eliminação Gaussiana, a matriz A é transformada em umamatriz triangular superior e o vetor b é simultaneamenteatualizado.
Se outras soluções de sistemas lineares forem necessárias estenão é o melhor esquema.
“Equivalente” à decomposição de Doolittle.
O vetor b não é atualizado simultaneamente.
Sistemas Lineares – 2016 – p.18/37
![Page 21: Solução Numérica de Sistemas Lineares de Grande Porte · 2017-03-24 · Descrição da solução de 17 sistemas lineares até 5×5 por eliminação Gaussiana. Jiu Zhang Suan Shu](https://reader036.vdocumento.com/reader036/viewer/2022081522/5f3c1e3f2761ee4a942446fd/html5/thumbnails/21.jpg)
Pivôs
Os elementos da diagonal de uma matriz durante o cálculo de uma decomposiçãorecebem o nome de pivôs.Quando um pivô nulo é encontrado temos um caso onde pode ou não existir umadecomposição LU .
Nao existe decomposicao LU
A =
(
0 1
1 0
)
Matriz Singular
(
0 1
0 0
)
=
(
1 0
0 1
)(
0 1
0 0
)
Situação pior: pivôs com valores muito pequenos devido a instabilidade numérica.
Sistemas Lineares – 2016 – p.19/37
![Page 22: Solução Numérica de Sistemas Lineares de Grande Porte · 2017-03-24 · Descrição da solução de 17 sistemas lineares até 5×5 por eliminação Gaussiana. Jiu Zhang Suan Shu](https://reader036.vdocumento.com/reader036/viewer/2022081522/5f3c1e3f2761ee4a942446fd/html5/thumbnails/22.jpg)
Instabilidade Numérica
13 6= 0, 33333 . . .
⋆ Computadores não sabem fazer contas
⋆ Computadores são muito rápidos
⋆ Métodos robustos × Métodos rápidos
Sistemas Lineares – 2016 – p.20/37
![Page 23: Solução Numérica de Sistemas Lineares de Grande Porte · 2017-03-24 · Descrição da solução de 17 sistemas lineares até 5×5 por eliminação Gaussiana. Jiu Zhang Suan Shu](https://reader036.vdocumento.com/reader036/viewer/2022081522/5f3c1e3f2761ee4a942446fd/html5/thumbnails/23.jpg)
Pivôs
Os elementos da diagonal de uma matriz durante o cálculo de uma decomposiçãorecebem o nome de pivôs.Quando um pivô nulo é encontrado temos um caso onde pode ou não existir umadecomposição LU .
Nao existe decomposicao LU
A =
(
ǫ 1
1 0
)
Matriz Singular
(
0 1
0 0
)
=
(
1 0
0 1
)(
0 1
0 0
)
Situação pior: pivôs com valores muito pequenos devido a instabilidade numérica.
Sistemas Lineares – 2016 – p.21/37
![Page 24: Solução Numérica de Sistemas Lineares de Grande Porte · 2017-03-24 · Descrição da solução de 17 sistemas lineares até 5×5 por eliminação Gaussiana. Jiu Zhang Suan Shu](https://reader036.vdocumento.com/reader036/viewer/2022081522/5f3c1e3f2761ee4a942446fd/html5/thumbnails/24.jpg)
Pivoteamento
⋆ A decomposição PA = LU permite trabalhar com matrizes como aanterior e aumenta a estabilidade numérica do algoritmo.
⋆ O pivoteamento é feito escolhendo o elemento abaixo da diagonal nacoluna coluna corrente com maior valor absoluto como o próximopivô.
⋆ Este procedimento equivale a permutar linhas da matriz A obtendo
PA = LU
onde P e uma matriz de permutação.
⋆ É possível também permutar colunas AQ
⋆ e, simultaneamente, linhas e colunas PAQ.
Sistemas Lineares – 2016 – p.22/37
![Page 25: Solução Numérica de Sistemas Lineares de Grande Porte · 2017-03-24 · Descrição da solução de 17 sistemas lineares até 5×5 por eliminação Gaussiana. Jiu Zhang Suan Shu](https://reader036.vdocumento.com/reader036/viewer/2022081522/5f3c1e3f2761ee4a942446fd/html5/thumbnails/25.jpg)
0 200 400 600 800
0
100
200
300
400
500
600
700
800
900
nz = 18476 Sistemas Lineares – 2016 – p.23/37
![Page 26: Solução Numérica de Sistemas Lineares de Grande Porte · 2017-03-24 · Descrição da solução de 17 sistemas lineares até 5×5 por eliminação Gaussiana. Jiu Zhang Suan Shu](https://reader036.vdocumento.com/reader036/viewer/2022081522/5f3c1e3f2761ee4a942446fd/html5/thumbnails/26.jpg)
0 200 400 600 800
0
100
200
300
400
500
600
700
800
900
nz = 73042 Sistemas Lineares – 2016 – p.24/37
![Page 27: Solução Numérica de Sistemas Lineares de Grande Porte · 2017-03-24 · Descrição da solução de 17 sistemas lineares até 5×5 por eliminação Gaussiana. Jiu Zhang Suan Shu](https://reader036.vdocumento.com/reader036/viewer/2022081522/5f3c1e3f2761ee4a942446fd/html5/thumbnails/27.jpg)
Abordagens Alternativas
⋆ Métodos Diretos
⋆ Fórmula fechada para obtenção da solução
⋆ Encontra a solução exata em tempo finito
⋆ Pode necessitar muito tempo e memória
⋆ Métodos Iterativos
⋆ Encontra aproximação da solução a cada passo
⋆ Converge para um ponto próximo o suficiente da solução
⋆ Geralmente não necessita muita memória
Sistemas Lineares – 2016 – p.25/37
![Page 28: Solução Numérica de Sistemas Lineares de Grande Porte · 2017-03-24 · Descrição da solução de 17 sistemas lineares até 5×5 por eliminação Gaussiana. Jiu Zhang Suan Shu](https://reader036.vdocumento.com/reader036/viewer/2022081522/5f3c1e3f2761ee4a942446fd/html5/thumbnails/28.jpg)
Métodos Diretos
⋆ Substituição - Inversa
⋆ Cramer
⋆ Gauss-Jordan - Escalonamento
⋆ Eliminação Gaussiana
⋆ LU UL
⋆ Decomposição de Crout
⋆ Decomposição de Cholesky
⋆ LDU
⋆ LDLt
⋆ LTLt
⋆ MD−1M t
⋆ Bunch-Parlett
⋆ QR - QL
⋆ Symmetric-Triangular DecompositionSistemas Lineares – 2016 – p.26/37
![Page 29: Solução Numérica de Sistemas Lineares de Grande Porte · 2017-03-24 · Descrição da solução de 17 sistemas lineares até 5×5 por eliminação Gaussiana. Jiu Zhang Suan Shu](https://reader036.vdocumento.com/reader036/viewer/2022081522/5f3c1e3f2761ee4a942446fd/html5/thumbnails/29.jpg)
Métodos Iterativos
⋆ SVD
⋆ (Gauss-)Jacobi - Gauss-Seidel
⋆ Relaxações Sucessivas
⋆ Relaxações Sucessivas Simétrico
⋆ Gradiente - Gradientes Conjugados
⋆ Gradiente Condicional
⋆ GC Equações Normais - GC Resíduo Mínimo
⋆ GC Quadrado
⋆ Minres
⋆ GMres - Solução Fraca
⋆ QMR
⋆ SYMMLQ
⋆ BGC - BGC Estabilizado
⋆ Iteração de ChebyshevSistemas Lineares – 2016 – p.27/37
![Page 30: Solução Numérica de Sistemas Lineares de Grande Porte · 2017-03-24 · Descrição da solução de 17 sistemas lineares até 5×5 por eliminação Gaussiana. Jiu Zhang Suan Shu](https://reader036.vdocumento.com/reader036/viewer/2022081522/5f3c1e3f2761ee4a942446fd/html5/thumbnails/30.jpg)
Porque Métodos Eficientes?
Método de Cramer (cada determinante):
⋆ n! operações de ponto flutuante FLOP pela definição
⋆ Por Laplace
⋆ n3 Por Eliminação Gaussiana
Método n= 5 n= 10 n= 20
Definição 2,5s 3,4d 20 bilhõesLaplace 0,4s 6min 5 mesesGauss 0,036s 0,22s 1,5s
Ivan Barros 1969 - 5× 103 FLOPS por segundo
Sistemas Lineares – 2016 – p.28/37
![Page 31: Solução Numérica de Sistemas Lineares de Grande Porte · 2017-03-24 · Descrição da solução de 17 sistemas lineares até 5×5 por eliminação Gaussiana. Jiu Zhang Suan Shu](https://reader036.vdocumento.com/reader036/viewer/2022081522/5f3c1e3f2761ee4a942446fd/html5/thumbnails/31.jpg)
Porque Métodos Eficientes?
Método de Cramer (cada determinante):
⋆ n! operações de ponto flutuante FLOP pela definição
⋆ Por Laplace
⋆ n3 Por Eliminação Gaussiana
Método n= 5 n= 10 n= 20
Definição 0s 0s 8:45hLaplace 0s 0s 10−8sGauss 0s 0s 0s
1018 FLOPS por segundo
Sistemas Lineares – 2016 – p.29/37
![Page 32: Solução Numérica de Sistemas Lineares de Grande Porte · 2017-03-24 · Descrição da solução de 17 sistemas lineares até 5×5 por eliminação Gaussiana. Jiu Zhang Suan Shu](https://reader036.vdocumento.com/reader036/viewer/2022081522/5f3c1e3f2761ee4a942446fd/html5/thumbnails/32.jpg)
Porque Métodos Eficientes?
Método de Cramer: n! operações de ponto flutuante FLOP
Considere um sistema linear com n = 109
Computador que faz 1018 FLOPS por segundo (2016)Tempo para solução:
Sistemas Lineares – 2016 – p.30/37
![Page 33: Solução Numérica de Sistemas Lineares de Grande Porte · 2017-03-24 · Descrição da solução de 17 sistemas lineares até 5×5 por eliminação Gaussiana. Jiu Zhang Suan Shu](https://reader036.vdocumento.com/reader036/viewer/2022081522/5f3c1e3f2761ee4a942446fd/html5/thumbnails/33.jpg)
Porque Métodos Eficientes?
Método de Cramer: n! operações de ponto flutuante FLOP
Considere um sistema linear com n = 109
Computador que faz 1018 FLOPS por segundo (2016)Tempo para solução:
• n! > 2n, menos que 2(109) FLOPS
Sistemas Lineares – 2016 – p.30/37
![Page 34: Solução Numérica de Sistemas Lineares de Grande Porte · 2017-03-24 · Descrição da solução de 17 sistemas lineares até 5×5 por eliminação Gaussiana. Jiu Zhang Suan Shu](https://reader036.vdocumento.com/reader036/viewer/2022081522/5f3c1e3f2761ee4a942446fd/html5/thumbnails/34.jpg)
Porque Métodos Eficientes?
Método de Cramer: n! operações de ponto flutuante FLOP
Considere um sistema linear com n = 109
Computador que faz 1018 FLOPS por segundo (2016)Tempo para solução:
• n! > 2n, menos que 2(109) FLOPS
• Um segundo: 1018 < 1618 = 272
Sistemas Lineares – 2016 – p.30/37
![Page 35: Solução Numérica de Sistemas Lineares de Grande Porte · 2017-03-24 · Descrição da solução de 17 sistemas lineares até 5×5 por eliminação Gaussiana. Jiu Zhang Suan Shu](https://reader036.vdocumento.com/reader036/viewer/2022081522/5f3c1e3f2761ee4a942446fd/html5/thumbnails/35.jpg)
Porque Métodos Eficientes?
Método de Cramer: n! operações de ponto flutuante FLOP
Considere um sistema linear com n = 109
Computador que faz 1018 FLOPS por segundo (2016)Tempo para solução:
• n! > 2n, menos que 2(109) FLOPS
• Um segundo: 1018 < 1618 = 272
• Um minuto: 64× 1072 = 278
Sistemas Lineares – 2016 – p.30/37
![Page 36: Solução Numérica de Sistemas Lineares de Grande Porte · 2017-03-24 · Descrição da solução de 17 sistemas lineares até 5×5 por eliminação Gaussiana. Jiu Zhang Suan Shu](https://reader036.vdocumento.com/reader036/viewer/2022081522/5f3c1e3f2761ee4a942446fd/html5/thumbnails/36.jpg)
Porque Métodos Eficientes?
Método de Cramer: n! operações de ponto flutuante FLOP
Considere um sistema linear com n = 109
Computador que faz 1018 FLOPS por segundo (2016)Tempo para solução:
• n! > 2n, menos que 2(109) FLOPS
• Um segundo: 1018 < 1618 = 272
• Um minuto: 64× 1072 = 278
• Uma hora: 64× 1078 = 284
Sistemas Lineares – 2016 – p.30/37
![Page 37: Solução Numérica de Sistemas Lineares de Grande Porte · 2017-03-24 · Descrição da solução de 17 sistemas lineares até 5×5 por eliminação Gaussiana. Jiu Zhang Suan Shu](https://reader036.vdocumento.com/reader036/viewer/2022081522/5f3c1e3f2761ee4a942446fd/html5/thumbnails/37.jpg)
Porque Métodos Eficientes?
Método de Cramer: n! operações de ponto flutuante FLOP
Considere um sistema linear com n = 109
Computador que faz 1018 FLOPS por segundo (2016)Tempo para solução:
• n! > 2n, menos que 2(109) FLOPS
• Um segundo: 1018 < 1618 = 272
• Um minuto: 64× 1072 = 278
• Uma hora: 64× 1078 = 284
• Um dia: 32× 1084 = 289
Sistemas Lineares – 2016 – p.30/37
![Page 38: Solução Numérica de Sistemas Lineares de Grande Porte · 2017-03-24 · Descrição da solução de 17 sistemas lineares até 5×5 por eliminação Gaussiana. Jiu Zhang Suan Shu](https://reader036.vdocumento.com/reader036/viewer/2022081522/5f3c1e3f2761ee4a942446fd/html5/thumbnails/38.jpg)
Porque Métodos Eficientes?
Método de Cramer: n! operações de ponto flutuante FLOP
Considere um sistema linear com n = 109
Computador que faz 1018 FLOPS por segundo (2016)Tempo para solução:
• n! > 2n, menos que 2(109) FLOPS
• Um segundo: 1018 < 1618 = 272
• Um minuto: 64× 1072 = 278
• Uma hora: 64× 1078 = 284
• Um dia: 32× 1084 = 289
• Um ano: 512× 1089 = 298
Sistemas Lineares – 2016 – p.30/37
![Page 39: Solução Numérica de Sistemas Lineares de Grande Porte · 2017-03-24 · Descrição da solução de 17 sistemas lineares até 5×5 por eliminação Gaussiana. Jiu Zhang Suan Shu](https://reader036.vdocumento.com/reader036/viewer/2022081522/5f3c1e3f2761ee4a942446fd/html5/thumbnails/39.jpg)
Porque Métodos Eficientes?
Método de Cramer: n! operações de ponto flutuante FLOP
Considere um sistema linear com n = 109
Computador que faz 1018 FLOPS por segundo (2016)Tempo para solução:
• n! > 2n, menos que 2(109) FLOPS
• Um segundo: 1018 < 1618 = 272
• Um minuto: 64× 1072 = 278
• Uma hora: 64× 1078 = 284
• Um dia: 32× 1084 = 289
• Um ano: 512× 1089 = 298
• Universo: 16× 109 × 1098 < 2102 × 169 = 2138
Sistemas Lineares – 2016 – p.30/37
![Page 40: Solução Numérica de Sistemas Lineares de Grande Porte · 2017-03-24 · Descrição da solução de 17 sistemas lineares até 5×5 por eliminação Gaussiana. Jiu Zhang Suan Shu](https://reader036.vdocumento.com/reader036/viewer/2022081522/5f3c1e3f2761ee4a942446fd/html5/thumbnails/40.jpg)
Porque Métodos Eficientes?
Método de Cramer: n! operações de ponto flutuante FLOP
Considere um sistema linear com n = 109
Computador que faz 1018 FLOPS por segundo (2016)Tempo para solução:
• n! > 2n, menos que 2(109) FLOPS
• Um segundo: 1018 < 1618 = 272
• Um minuto: 64× 1072 = 278
• Uma hora: 64× 1078 = 284
• Um dia: 32× 1084 = 289
• Um ano: 512× 1089 = 298
• Universo: 16× 109 × 1098 < 2102 × 169 = 2138
2(109) − 2
138= 2
(109)
Sistemas Lineares – 2016 – p.30/37
![Page 41: Solução Numérica de Sistemas Lineares de Grande Porte · 2017-03-24 · Descrição da solução de 17 sistemas lineares até 5×5 por eliminação Gaussiana. Jiu Zhang Suan Shu](https://reader036.vdocumento.com/reader036/viewer/2022081522/5f3c1e3f2761ee4a942446fd/html5/thumbnails/41.jpg)
Porque Métodos Eficientes?
Método de Cramer: n! operações de ponto flutuante FLOP
Considere um sistema linear com n = 109
Computador que faz 1018 FLOPS por segundo (2016)Tempo para solução:
• n! > 2n, menos que 2(109) FLOPS
• Um segundo: 1018 < 1618 = 272
• Um minuto: 64× 1072 = 278
• Uma hora: 64× 1078 = 284
• Um dia: 32× 1084 = 289
• Um ano: 512× 1089 = 298
• Universo: 16× 109 × 1098 < 2102 × 169 = 2138
2(109) − 2
138= 2
(109)
2(103) − 2138 = 1, 07150860718627× 10301 − 3, 48449143727041× 1041
Sistemas Lineares – 2016 – p.30/37
![Page 42: Solução Numérica de Sistemas Lineares de Grande Porte · 2017-03-24 · Descrição da solução de 17 sistemas lineares até 5×5 por eliminação Gaussiana. Jiu Zhang Suan Shu](https://reader036.vdocumento.com/reader036/viewer/2022081522/5f3c1e3f2761ee4a942446fd/html5/thumbnails/42.jpg)
Decomposição SVD
Teorema (SVD) Seja A ∈ Rn×m com posto r.Existem Un×n, Σn×m e V m×m tal que U e V são matrizes ortogonais,Σ uma matriz diagonal nas primeiras r linhas e colunas comσ11 ≥ σ22 ≥ σ33 ≥ . . . ≥ σrr > 0 e os demais elementos nulos.A pode ser escrita da forma: A = UΣV t.
Teorema (Posto) Seja A de posto r e A = UΣV t.Definimos Ak = UΣkV
t
Então o posto de Ak é k
σk+1 = ‖A− Ak‖2 = min{‖A− B‖2 | posto(B) ≤ k}
Sistemas Lineares – 2016 – p.31/37
![Page 43: Solução Numérica de Sistemas Lineares de Grande Porte · 2017-03-24 · Descrição da solução de 17 sistemas lineares até 5×5 por eliminação Gaussiana. Jiu Zhang Suan Shu](https://reader036.vdocumento.com/reader036/viewer/2022081522/5f3c1e3f2761ee4a942446fd/html5/thumbnails/43.jpg)
Representação de Imagens
⋆ Imagem jpg (dimensão m× n)
⋆ Três matrizes
⋆ Cores primárias: vermelho, verde e azul
⋆ Intensidade entre 0 e 255
⋆ Combinação das três matrizes ponto a ponto
⋆ Imagem aproximada pela matriz de posto k, Ak
⋆ Exemplo: 450× 600, Posto: 450.
Sistemas Lineares – 2016 – p.32/37
![Page 44: Solução Numérica de Sistemas Lineares de Grande Porte · 2017-03-24 · Descrição da solução de 17 sistemas lineares até 5×5 por eliminação Gaussiana. Jiu Zhang Suan Shu](https://reader036.vdocumento.com/reader036/viewer/2022081522/5f3c1e3f2761ee4a942446fd/html5/thumbnails/44.jpg)
07-03-2009 file:///home/aurelio/conf/palestras/arquivo.jpg #1
Sistemas Lineares – 2016 – p.33/37
![Page 45: Solução Numérica de Sistemas Lineares de Grande Porte · 2017-03-24 · Descrição da solução de 17 sistemas lineares até 5×5 por eliminação Gaussiana. Jiu Zhang Suan Shu](https://reader036.vdocumento.com/reader036/viewer/2022081522/5f3c1e3f2761ee4a942446fd/html5/thumbnails/45.jpg)
posto=1 posto=2 posto=3
posto=4 posto=5 posto=6
posto=7 posto=8 posto=9
Sistemas Lineares – 2016 – p.34/37
![Page 46: Solução Numérica de Sistemas Lineares de Grande Porte · 2017-03-24 · Descrição da solução de 17 sistemas lineares até 5×5 por eliminação Gaussiana. Jiu Zhang Suan Shu](https://reader036.vdocumento.com/reader036/viewer/2022081522/5f3c1e3f2761ee4a942446fd/html5/thumbnails/46.jpg)
posto=48 posto=95 posto=142
posto=189 posto=236 posto=283
posto=330 posto=377matriz original posto=450
Sistemas Lineares – 2016 – p.35/37
![Page 47: Solução Numérica de Sistemas Lineares de Grande Porte · 2017-03-24 · Descrição da solução de 17 sistemas lineares até 5×5 por eliminação Gaussiana. Jiu Zhang Suan Shu](https://reader036.vdocumento.com/reader036/viewer/2022081522/5f3c1e3f2761ee4a942446fd/html5/thumbnails/47.jpg)
25-04-2013 file:///home/aurelio/conf/palestras/marte.jpg #1
Sistemas Lineares – 2016 – p.36/37
![Page 48: Solução Numérica de Sistemas Lineares de Grande Porte · 2017-03-24 · Descrição da solução de 17 sistemas lineares até 5×5 por eliminação Gaussiana. Jiu Zhang Suan Shu](https://reader036.vdocumento.com/reader036/viewer/2022081522/5f3c1e3f2761ee4a942446fd/html5/thumbnails/48.jpg)
Conclusões
⋆ Importância dos Sistemas Lineares
⋆ Decomposição
⋆ Métodos Eficientes
⋆ Técnicas de Implementação
⋆ Métodos Iterativos
⋆ Aplicação
Sistemas Lineares – 2016 – p.37/37