apresentação do curso -...

Apresentacao do Curso

Luiz Antonio da Silva Medeiros(1)

[email protected]

(1)UAMAT / UFCG

UFCG, 2019.1

luiz:[email protected]

Outline

Outline

1 IntroducaoSistemas Lineares

2 Solucao de um Sistema Linear

3 Metodos NumericosClassificacao dos Metodos Numericos

4 (Mal) Condicionamento de Algoritmos

5 Nocoes de Problemas mal condicionados

6 Nocoes de Problemas mal condicionadosNormas MatriciaisNumero de Condicionamento

Medeiros Metodos Numericos

Sistemas LinearesSistema Linear

Metodos Numericos(Mal) Condicionamento de Algoritmos

Nocoes de Mal CondicionamentoNocoes de Mal Condicionamento

Sistemas Lineares

Representacao de uma Matriz

Representacao geral

Uma matriz A = [aij ]{m × n} disposta em m linhas e n colunas erepresentada por:

A =

a11 a12 . . . a1na21 a22 . . . a2n

......

. . ....

am1 am2 . . . amn





Sistemas Lineares

Definicao: Caso Geral.

Definicao

Uma equacao linear nas incognitas x1, x2, . . . , xn e qualquerequacao que pode ser escrita na forma

a1x1 + a2x2 + . . . anxn = b,

onde os coeficiente a1, a2, . . . , an e b sao constantes (escalares,reais ou complexos).

Sao exemplos de equacoes lineares nas incognitas x , y e z :

1 3x − 4y = 5 + 10z .

2√

2x + π4 y − sen(π5 )z = 1.

3 sen(10π)x + e−8y = ln(2)z .





Sistemas Lineares

Exemplo de equacoes nao-lineares.

Nao sao exemplos de equacoes lineares.

1 3xy + 4z = 5

2 x2 + y2 + z2 = 4.

3√

2x + 3y − z = 5.

4 sen(x) + e−8y = ln(2)z





Sistemas Lineares

Sistema Equacoes Lineares

Definicao

Um sistema de equacoes lineares com m equacoes e n incognitasx1, x2, . . . , xn e um conjunto de equacoes lineares do tipo:

a11x1 + a12x2 + · · ·+ a1nxn = b1a21x1 + a22x2 + · · ·+ a2nxn = b2

......

. . ....

...am1x1 + am2x2 + · · ·+ amnxn = bm

onde os coeficientes aij , bi , 1 ≤ i ≤ m e 1 ≤ j ≤ n saoconstantes (escalares, reais ou complexos).





Sistemas Lineares

Representacao Matricial

Definicao

Um sistema de equacoes lineares com m equacoes e n incognitasx1, x2, . . . , xn e um conjunto de equacoes lineares do tipo:

a11 a12 . . . a1na21 a22 . . . a2n

......

. . ....

am1 am2 . . . amn

·

x1x2...xn

=

b1b2...bm

onde os coeficientes aij , bi , 1 ≤ i ≤ m e 1 ≤ j ≤ n saoconstantes (escalares, reais ou complexos).





Sistemas Lineares

Nomenclatura

A matriz A = [aij ]m×n associada ao sistema linear e chamadamatriz dos coeficientes do sistema

A =

a11 a12 . . . a1na21 a22 . . . a2n

......

. . ....

am1 am2 . . . amn

Os vetores (matriz colunas)

x =

x1x2...xn

e b =

b1b2...bm

sao chamados vetor ou matriz das incognitas e vetor ou matrizdos termos independentes.Medeiros Metodos Numericos




Sistemas Lineares

Exemplo

Represente matricialmente o sistema abaixo, destacando cada umde seus termos.

x + y +z = 32x + 3y +z = 5x − y −2z = −5





Solucao de uma equacao linear

Definicao

Uma solucao de uma equacao linear

a1x1 + a2x2 + · · ·+ anxn = b

e um vetor (matriz coluna)

s = [s1, s2, . . . , sn]T

cujas coordenadas satisfazem a equacao quando substituimos xipor si com i = 1, 2, . . . , n.





Exemplos

Verifique que os vetores dados sao solucoes da equacao lineardada:

1 s =

[54

]e 3x − 4y = −1.

2 s =

61−1

e a− b + 2c = 3.

3 Mostre que s =

3 + α− 2βαβ

e solucao de x − y + 2z = 3

quaisquer que sejam α, β ∈ R.





Solucao de um sistema de equacoes lineares

Definicao

Uma solucao de um sistema lineara11x1 + a12x2 + · · ·+ a1nxn = b1a21x1 + a22x2 + · · ·+ a2nxn = b2

......

. . ....

...am1x1 + am2x2 + · · ·+ amnxn = bm

e um vetor (matriz coluna) s =

s1s2...sn

cujas coordenadas

satisfazem TODAS as equacoes quando substituimos x1 por s1, x2por s2 e assim por diante. Medeiros Metodos Numericos




Exemplos

Verifique que os vetores dados sao solucoes da equacao lineardada:

1 s =

[21

]e

{2x − y = 3x + 3y = 5

2 s =

3−12

e

x − y − z = 2

y + 3z = 55z = 10





Classificacao de um Sistema Linear quantoao numero de solucoes.

Possivel e Determinado: quando possui uma unica solucao.

Possivel e Indeterminado: quando possui uma unicasolucao.

Impossıvel: quando o conjunto solucao e vazio (nao hasolucoes no conjunto universo)





Sistema com Solucao:





Sistema sem Solucao:





Classificacao

Metodos Diretos e Metodos Iterativos

Definicao

Metodos Diretos sao aqueles que conduzem a solucao exata dosistema, a menos de erros introduzidos pela maquina, apos umnumero finito de passos.

Definicao

Metodos Iterativos sao aqueles que conduzem a solucaoaproximada do sistema, por meio de um processo iterativo quegera uma sequencia {xk}k∈N de aproximacoes da solucao exata.





Classificacao

Metodos Diretos × Metodos Iterativos

Metodos Diretos

VantagensNao Depende da condicao deConvergencia

Termina num numero finito de passos

DesvantagensNao e pratico para problemas de grandeporte

Inviavel para problemas malcondicionados





Classificacao

Metodos Diretos × Metodos Iterativos

Metodos Iterativos

Vantagens

E apropriado para problemas de largaescala.

Sob hipotese apropriadas pode convergirmuito rapido.

DesvantagensPode convergir lentamente paraproblemas mal condicionados.

Pode exigir um numero grande deoperacoes.





Problemas bem-postos.

Definicao: Um problema e bem posto quando ele satisfaz duascondicoes:

O problema tem uma unica solucao;

(?) quando pequenas pertubacoes nos dados de entradaprovocam pequenas pertubacoes nos dados de saıda.

A condicao (?) e chamada estabilidade do problema com relacaoaos dados.

Definicao: Um metodo e estavel se pequenas pertubacoes nosdados coonduzem a solucoes proximas.





Exemplo.

Considere o problema de encontrar as raızes dex2 − 100.22x + 1.2371 = 0.Usando Baskara e aritmetica de ponto flutuante com cinco dıgitos,temos:

x1 =100.22 + 100.19

2= 100.20 e x2 =

100.22− 100.19

2= 0.015.

Por outro lado, usando o fato que x1x2 = ca e aritmetica de ponto

flutuante com cinco dıgitos, temos:

x1 =100.22 + 100.19

2= 100.20 e x2 =

c

ax1=

1.2371

100.20= 0.012346.

Veja que, o erro relativo usando o primeiro procedimento e de21.5%, ao passo que o erro relativo com o segundo procedimento ede 0.0052%.





Conclusao.

“O equilıbrio entre as influencias dos erros de truncamento earredondamento depende do problema e da habilidade humana.”





Problemas Mal Condicionados

Seja x∗ a solucao exata do sistema Ax = b, e x a solucaoaproximada computada. O erro (resıduo) e :

e = b − Ax . (1)

Example

Considere o sistema{x + 1.001y = 2.001

0.999x + y = 1.999

Observe que x∗ = [1, 1]T e a solucao do sistema.





Agora, considere x = [2, 0.001]T . Observe que

e = b − Ax

=

[2.0011.999

]−[

1 1.0010.999 1

]·[

20.001

]=

[2.0011.999

]−[

2.0010011.999000

]=

[−0.000001

0

]





Conclusao.

Como o resıduo e pequeno, x poderia ser considerada uma”boa”solucao, o que de fato nao ocorre!!





Normas MatriciaisNumero de Condicionamento

Definicao.

Definicao

Uma matriz e bem condicionada quando pequenas alteracoes emseus elementos nao provocam grandes mudancas na solucao dosistema Ax = b. Caso contrario, ela e dita mal condicionada.






Normas Matricias.

Definicao

Seja V um espaco vetorial. Uma norma || · || sobre V e umafuncao || · · · || : v → R tal que

(i) ||v || ≥ 0,∀v ∈ V

(ii) ||tv || = |t| · ||v ||,∀t ∈ R,∀v ∈ V

(iii) ||v || = 0⇔ v = 0.

(iv) ||u + v || ≤ ||u||+ ||v ||,∀u, v ∈ V .






Normas Matricias.

Example

Seja V = Rn. Considere x = (x1, x2, . . . , xn) ∈ Rn.

(i) ||x ||2 =√x21 + x22 + · · ·+ x2n

(ii) ||x ||1 = |x1|+ |x2|+ · · ·+ |xn|(iii) ||x ||∞ = max{|x1|, |x2|, . . . , |xn|}






Exercıcio

1 Considerando V = Rn. Considere x = (x1, x2, . . . , xn) ∈ Rn.Mostre que

1

n||x ||1 ≤ ||x ||∞ ≤ ||x ||2

2 Mostre que existem constantes c1, c2 positivas tais que

c1||x ||∞ ≤ ||x ||1 ≤ c2||x ||2

3 Mais geralmente, se V e um espaco vetorial normado finitodimensional, quaisquer duas normas sao equivalentes.






Definicao.

Definicao

Dado um espaco vetorial normado (V , || · ||), dizemos que a norma|| · || e consistente se

||A · B|| ≤ ||A|| · ||B||,∀A,B ∈ V .






Exemplo: Norma de Frobenius

Definicao

Seja A = [aij ] ∈ M(Rn), defina

||A||F =

√√√√ n∑i=1

n∑j=1

a2ij . (2)






Observe que:

||A · B||2F =∑i ,j=1

(∑k=1

aikbkj)2 (3)

≤∑i ,j=1

(∑k=1

a2ik

)·

(∑k=1

b2kj

)(4)

≤

(∑i=1

∑k=1

a2ik

)·

∑j=1

∑k=1

b2kj

(5)

= ||A||2F · ||B||2F . (6)

Ou seja, || · ||F , como norma matricial, e consistente.






E facil ver que:

(I)

||A||F =

√∑j=1

||aj ||22,

onde aj e a j-esima coluna de A.

(II)

||A||F =

√∑i=1

||ai ||22,

onde ai e a i-esima linha de A.






Alem disso,

||A · x ||22 =∑i=1

∑j=1

aijxj

2

(7)

≤∑i=1

[∑j=1

a2ij ] · [∑j=1

x2j ]

(8)

= ||A||2F · ||x ||22. (9)






Outras Normas matriciais

(A)

||A|| = maxx 6=0{||Ax ||||x ||

}

(B)

||A||1 = maxx 6=0{||Ax ||1||x ||1

}

(C)

||A||∞ = maxx 6=0{||Ax ||∞||x ||∞

}






Teorema

||A||1 = max1≤j≤n

{∑i=1

|aij |}

e||A||∞ = max

1≤i≤n{∑j=1

|aij |






Demonstracao: Seja α = max1≤j≤n{∑

i=1 |aij |} =∑

i=1 |aik |.Observe que:

||Ax ||1 =∑i=1

∣∣∣∣∣∣∑j=1

aijxj

∣∣∣∣∣∣ ≤∑i=1

∑j=1

|aij | · |xj | (10)

=∑j=1

|xj | ·

(∑i=1

|aij |

)≤ α||x1||. (11)

Isto e:

||Ax ||1||x ||1

≤ alpha⇒ ||A||1 = maxx 6=0{||Ax ||1||x ||1

} ≤ α.

Mas, por outro lado,

||A · ek ||1 = ||ak || = α⇒ ||A||1 = α.






Analise de Erro

Seja A ∈ M(Rn) uma matriz invertıvel. Considere o sistemaAx = b.Chamemos x a solucao exata e y uma solucao aproximada, deforma que o erro da solucao e

e = x − y

Entao,||e|| := erro absoluto.

e||e||||x ||

=||y − x ||||x ||

:= erro relativo.






Analise de Erro

Sejam b = Ay e b = Ax Assim, o resıduo r e definido por

r = b − b = b − Ax

Segue que

r = b − Ay = Ax − Ay = A · e ⇒ e = A−1r .

Ou ainda,

||e|| ≤ ||A−1|| · ||r || e ||r || ≤ ||A · e|| ≤ ||A|| · ||e||.






Analise de Erro

Das ultimas desigualdades, obtemos

||r ||||A||

≤ ||e|| ≤ ||A−1|| · ||r ||. (12)

Por outro lado,

||b|| = ||A · x || ≤ ||A|| · ||x || e ||x || = ||A−1 · b|| ≤ ||A−1|| · ||b||.

Que implica||b||||A||

≤ ||x || ≤ ||A−1|| · ||b||. (13)

Ou equivalente,

||A||||b||

≥ 1

||x ||≥ 1

||A−1|| · ||b||. (14)






Analise de Erro

Escrevendo cond(A) = ||A|| · ||A−1||, obtemos de (12) e (14) que

||r ||cond(A) · ||b||

≤ ||e||||x ||

≤ cond(A)||r ||||b||

. (15)

Conclusao:Se cond(A) ≈ 1, o erro relativo ||e||||x || e o resıduo relativo ||r ||||b|| estarao

proximos, caso contrario, isto e, cond(A) >> 1 o erro relativo dasolucao pode ser muitas vezes maior do que o resıduo relativo.


apresentação do curso -...

Documents