View
15
Download
0
Category
Preview:
Citation preview
Introdução aos Métodos Numéricos
Instituto de Computação UFFDepartamento de Ciência da Computação
Otton Teixeira da Silveira Filho
Conteúdo temático
● Sistemas de Equações Lineares. Métodos diretos
Conteúdo específico
● Exemplo de Wilson
● Malcondicionamento
● Número de condição
● Método dos resíduos
Sistemas de equações lineares
“Pronto, fiz os cálculos e achei !
...Mas como sei se é a solução?“
x
Sistemas de equações lineares
Exemplo de Wilson
Substitua o vetor solução por
(10 7 8 77 5 6 58 6 10 97 5 9 10
) x=(32233331
)xT
=( 9,2 ;−12,6 ;4,5 ;−1,1 )
Sistemas de equações lineares
Exemplo de Wilson
Substitua o vetor solução por
Resultado:
(10 7 8 77 5 6 58 6 10 97 5 9 10
) x=(32233331
)xT
=( 9,2 ;−12,6 ;4,5 ;−1,1 )
bT=(32,1 ;22,9 ;33,1 ;30,9 )
Sistemas de equações lineares
Exemplo de Wilson
Substitua o vetor solução por
Resultado:
(10 7 8 77 5 6 58 6 10 97 5 9 10
) x=(32233331
)xT
=( 9,2 ;−12,6 ;4,5 ;−1,1 )
bT=(32,1 ;22,9 ;33,1 ;30,9 )
Sistemas de equações lineares
Exemplo de Wilson
Parece que estamos perto da solução...
A (9,2
−12,64,5
−1,1)=(
32,122,933,130,9
) ; b=(32233331
)
Sistemas de equações lineares
Exemplo de Wilson
Substitua o vetor solução por
(10 7 8 77 5 6 58 6 10 97 5 9 10
) x=(32233331
)xT
=(1,82 ;−0,36 ;1,35 ;0,79 )
Sistemas de equações lineares
Exemplo de Wilson
Substitua o vetor solução por
Resultado:
(10 7 8 77 5 6 58 6 10 97 5 9 10
) x=(32233331
)xT
=(1,82 ;−0,36 ;1,35 ;0,79 )
bT=(32,01 ;22,99 ;33,01 ;30,99 )
Sistemas de equações lineares
Exemplo de Wilson
Realmente parecia que estávamos perto da solução?
A (
1,82−0,361,350,79
)=(32,0122,9933,0130,99
) ; b=(32233331
)
Sistemas de equações lineares
Exemplo de Wilson
Repare...
Os vetores “solução“ são muito diferentes...
A (1,82
−0,361,350,79
)= (32,0122,9933,0130,99
) ; A (9,2
−12,64,5
−1,1)=(
32,122,933,130,9
) ; b=(32233331
)
Sistemas de equações lineares
Exemplo de Wilson
Solução:
(10 7 8 77 5 6 58 6 10 97 5 9 10
) x=(32233331
)xT
=(1;1;1 ;1 )
Sistemas de equações lineares
● A técnica de substituir a solução encontrada na equação pode nos enganar
Sistemas de equações lineares
● A técnica de substituir a solução encontrada na equação pode nos enganar
● Estamos olhando o problema da forma errada
Sistemas de equações lineares
Este sistema é mal-condicionado, portanto:
● Pequenas variações nos parâmetros do problema (neste caso o vetor constante) gera uma mudança muito maior na solução
Sistemas de equações lineares
Este sistema é mal-condicionado, portanto:
● Pequenas variações nos parâmetros do problema (neste caso o vetor constante) gera uma mudança muito maior na solução
● Cada vetor dado é a solução exata para o vetor constante correspondente
Sistemas de equações lineares
O exemplo de Wilson é ilustrativo da sensibilidade que sistemas de equações podem ter quanto à precisão de suas componentes. Pequenas variações daquelas podem gerar grandes variações no vetor solução.
Sistemas de equações lineares
Mas há casos patológicos!
Matrizes de Hilbert
hij=1
i+ j−1; j=1,⋯n ,i=1,⋯,n
Sistemas de equações lineares
Matrizes de Hilbert
H=( 1 1/21/2 1/3 ) H=(
1 1 /2 1/31 /2 1/3 1/41 /3 1 /4 1/5 ) H=(
1 1/2 1/3 1/41 /2 1/3 1/4 1/51/3 1/4 1/5 1 /61 /4 1/5 1 /6 1 /7
)
Sistemas de equações lineares
Seja um sistema da forma
H matriz de Hilbert.
As componentes da solução são sempre inteiros.
H x=(111⋮1
)
Sistemas de equações lineares
Seja um sistema da forma
H matriz de Hilbert.
As componentes da solução são sempre inteiros.
Isto pode ser demonstrado pela regra de Cramer!
H x=(111⋮1
)
Sistemas de equações lineares
No entanto, se você usar qualquer linguagem de programação convencional para resolver estes sistemas, você não obterá valores inteiros para as componentes do vetor solução mesmo para dimensões pequenas do sistemas.
N = 5 já teremos problemas...
Sistemas de equações lineares
Um pouquinho de matemática…
Norma de vetores e matrizes
Normas
Norma é uma “ampliação“ do conceito de módulo
É uma maneira de medir propriedades de objetos matemáticos complexos como vetores, matrizes e funções.
Normas
Norma (módulo) de um vetor
É uma maneira de medir o “comprimento“ de um vetor
Normas
Norma (módulo) de um vetor
É uma maneira de medir o “comprimento“ de um vetor
Observou as aspas?
Normas
Norma de um vetor
Nos interessa da norma três propriedades:
● É sempre positiva
Normas
Norma de um vetor
Nos interessa da norma três propriedades:
● É sempre positiva
● Só é nula se o vetor for nulo
Normas
Norma de um vetor
Nos interessa da norma três propriedades:
● É sempre positiva
● Só é nula se o vetor for nulo
● Se o vetor for multiplicado por um valor, a norma será a norma do vetor multiplicado pelo valor em módulo
Normas
vetor de dimensão n
Esta é a Norma Euclidiana
‖v‖2=√v1 v1+v2 v2+v3 v3+⋯+vn vn=√∑i=1
n
v i v i
v
Normas
vetor de dimensão n
Esta é a Norma 1 ou Norma Manhattan
‖v‖1=|v1|+|v2|+|v3|+⋯+|vn|=∑i=1
n
|v i|
v
Normas
vetor de dimensão n
Esta é a Norma do Máximo
‖v‖max=max i [|v1|,|v2|,|v3|,⋯,|vn|] ; i=1,⋯, n
v
Normas
Um exemplo:
vT=(−2,3,1)
‖v‖2=√(−2)×(−2)+3×3+1×1=√14≈3,741657
‖v‖1=|−2|+|3|+|1|=6
‖v‖max=max i [|−2|,|3|,|1|]=3
Normas
Um exemplo:
São todas medidas do vetor mas não dão a mesma medida. São maneiras diferentes de medir...
vT=(−2,3,1)
‖v‖2=√(−2)×(−2)+3×3+1×1=√14≈3,741657
‖v‖1=|−2|+|3|+|1|=6
‖v‖max=max i [|−2|,|3|,|1|]=3
Normas
A matriz n x n
São a Norma de Fröbenius, a Norma 1 e a Norma do Máximo ou Norma Infinito para matrizes
‖A‖2=√ (∑i=1
n
∑j=1
n
aij2 ) ‖A‖1=max1≤ j≤n∑
i=1
n
|aij| ‖A‖max=max1≤i≤n∑j=1
n
|aij|
Sistemas de equações lineares
Para que isto?
Sistemas de equações lineares
O número de condicionamento de uma matriz A é dado por
É fácil de ver que o número de condição da matriz identidade é 1 para as normas 1 e do máximo.
κ=‖A−1‖‖A‖
Sistemas de equações lineares
O número de condicionamento de uma matriz A é dado por
É fácil de ver que o número de condição da matriz identidade é 1 para as normas 1 e do máximo.
Não é difícil de demonstrar que o número de condição é sempre maior ou igual a 1
κ=‖A−1‖‖A‖
Sistemas de equações lineares
Uma matriz é tão mais bem condicionada quanto o seu número de condição for mais próximo de 1.
Sistemas de equações lineares
Vamos para alguns exemplos com o Maxima com a função mat_norm() nas seguintes formas
● mat_norm(M, 1)
● mat_norm(M, inf)
● mat_norm(M, frobenius)
Sistemas de equações lineares
Nos exercícios vimos que:
● O número de condição para o exemplo de Wilson é, usando a função mat_norm(M, 1), 4488.
● Para os casos de matrizes de Hilbert 3x3 é 748 e a 4x4 maior que 28375.
Sistemas de equações lineares
Nos exercícios vimos que:
● O número de condição para o exemplo de Wilson é, usando a função mat_norm(M, 1), 4488.
● Para os casos de matrizes de Hilbert 3x3 é 748 e a 4x4 maior que 28375.
Na grande maioria das vezes não calculamos diretamente o número de condição
Sistemas de equações lineares
Observemos o método de Eliminação gaussiana:
● Se um pivô for bem menor que o(s) elemento(s) eliminado(s), teremos ruído numérico afetando todos os cálculos subsequentes (a divisão, lembra?).
Sistemas de equações lineares
Observemos o método de Eliminação gaussiana:
● Se um pivô for bem menor que o(s) elemento(s) eliminado(s), teremos ruído numérico afetando todos os cálculos subsequentes (a divisão, lembra?).
● E assim, o vetor obtido pelo algoritmo poderá estar distante do vetor solução
Sistemas de equações lineares
Observemos o método de Eliminação gaussiana:
● Se um pivô for bem menor que o(s) elemento(s) eliminado(s), teremos ruído numérico afetando todos os cálculos subsequentes (a divisão, lembra?).
● E assim, o vetor obtido pelo algoritmo poderá estar distante do vetor solução
● Se diz que este algoritmo é numericamente Instável
Sistemas de equações lineares
Primeiro passo:
Como verificar se o vetor obtido é próximo da solução do sistema?
Método dos Resíduos
Seja o sistema
do qual obtemos uma solução aproximada devido à instabilidade numérica da eliminação gaussiana ou de outro método de solução
A x=b
x1
Método dos Resíduos
Então podemos escrever
que substituída na equação original resulta em
A ( x1+ z1 )=b⇒ A x1+A z1=b⇒ A z1=b−A x1
x= x1+ z1
Método dos Resíduos
Observe que podemos calcular . Definindo
teremos
Definindo o resíduo como ficaremos com
A z1=b−b1
b1=A x1b−A x1
r1=b−b1
A z1=r1
Método dos Resíduos
Parece que nossos problemas foram resolvidos...
Método dos Resíduos
Parece que nossos problemas foram resolvidos...
Só que não...
Método dos Resíduos
Parece que nossos problemas foram resolvidos...
Só que não...
Pelos mesmos motivos que não conseguimos a solução exata, não conseguiremos o valor de mas uma aproximação que chamaremos de
O que nos resta?
z1z1
Método dos Resíduos
Parece que nossos problemas foram resolvidos...
Só que não...
Pelos mesmos motivos que não conseguimos a solução exata, não conseguiremos o valor de mas uma aproximação que chamaremos de
O que nos resta?
Começar tudo de novo...
z1z1
Método dos Resíduos
Podemos escrever
que substituída na equação original resulta em
onde é o segundo resíduo. Teremos o sistema
A ( x2+ z2 )=b⇒ A x2+A z2=b⇒ A z2=b−A x2=r2
x2= x1+z1 e x= x2+ z2
r2
A z2=r2
Método dos Resíduos
O qual, de novo, não me dá o resultado correto mas uma aproximação …z2
Método dos Resíduos
O qual, de novo, não me dá o resultado correto mas uma aproximação …
Espero que esteja ficando claro que obteremos, de fato, as sequências
Esperamos que, se tudo estiver bem, teremos a cada passo valores melhores da solução e valores menores para a norma de
z2
{ x1, x2, x3,⋯, xi } e { z1 ,z2 ,
z3 ,⋯, z i }
z i
Método dos Resíduos
Se os valores em módulo do vetor de correção diminuirem consistentemente, podemos dizer que o sistema é bem-condicionado e que a solução obtida é confiável
Método dos Resíduos
Se os valores em módulo do vetor de correção diminuirem consistentemente, podemos dizer que o sistema é bem-condicionado e que a solução obtida é confiável
Obs: No mundo real sempre haverá uma situação de mal-condicionamento a medida que chegamos perto do limite de precisão da máquina
Método dos Resíduos
Observe que o método dos resíduos tem um problema:
Temos que resolver uma sequência de SEL
Aparentemente o custo é alto...
A z1=r1 ; A z2=r2 ; A z3=r3 ;⋯A zk=rk
Método dos Resíduos
Observe que o método dos resíduos tem um problema:
Temos que resolver uma sequência de SEL
Aparentemente o custo é alto...
Só que não...
A z1=r1 ; A z2=r2 ; A z3=r3 ;⋯A zk=rk
Método dos Resíduos
Apresentaremos um outro assunto mas retornaremos ao Método dos Resíduos em breve...
Método dos Resíduos
Observe que o valor que nos diz o quanto estamos próximos da solução não são os resíduos mas os vetores ri zi
Recommended