Introdução aos Métodos Numéricosotton/graduacao/introducaonumericos/... · 2019-01-22 · Sistemas de equações lineares Nos exercícios vimos que: O número de condição para

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


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 )


Exemplo de Wilson


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 )


Exemplo de Wilson


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 )


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

)


Exemplo de Wilson


(10 7 8 77 5 6 58 6 10 97 5 9 10

) x=(32233331

)xT

=(1,82 ;−0,36 ;1,35 ;0,79 )


Exemplo de Wilson


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 )


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

)


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

)


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 )


● A técnica de substituir a solução encontrada na equação pode nos enganar


● A técnica de substituir a solução encontrada na equação pode nos enganar

● Estamos olhando o problema da forma errada


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


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


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.


Mas há casos patológicos!

Matrizes de Hilbert

hij=1

i+ j−1; j=1,⋯n ,i=1,⋯,n


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

)


Seja um sistema da forma

H matriz de Hilbert.

As componentes da solução são sempre inteiros.

H x=(111⋮1

)


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

)


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...


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



● Só é nula se o vetor for nulo

Normas

Norma de um vetor



● 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


Esta é a Norma 1 ou Norma Manhattan

‖v‖1=|v1|+|v2|+|v3|+⋯+|vn|=∑i=1

n

|v i|

v

Normas


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|


Para que isto?


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‖


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‖


Uma matriz é tão mais bem condicionada quanto o seu número de condição for mais próximo de 1.


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)


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.


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


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




● E assim, o vetor obtido pelo algoritmo poderá estar distante do vetor solução

● Se diz que este algoritmo é numericamente Instável


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


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


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


Parece que nossos problemas foram resolvidos...



Só que não...



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



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


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


O qual, de novo, não me dá o resultado correto mas uma aproximação …z2


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


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


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


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


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


Apresentaremos um outro assunto mas retornaremos ao Método dos Resíduos em breve...


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

Documents

Introdução aos Métodos Numéricosotton/graduacao/introducaonumericos/... · 2019-01-22 · Sistemas de equações lineares Nos exercícios vimos que: O número de condição para