Capítulo 6 - Equações Não- balsa/teaching/1011/MN/cap6.pdf · Equações Não-Lineares Métodos

  • View
    215

  • Download
    0

Embed Size (px)

Text of Capítulo 6 - Equações Não- balsa/teaching/1011/MN/cap6.pdf · Equações Não-Lineares Métodos

Equaes No-LinearesMtodos Numricos para uma Dimenso

Sistemas de Equaes No-Lineares

Captulo 6 - Equaes No-Lineares

Carlos Balsabalsa@ipb.pt

Departamento de MatemticaEscola Superior de Tecnologia e Gesto de Bragana

2o Ano - Eng. Civil e Electrotcnica

Carlos Balsa Mtodos Numricos 1/ 28

Equaes No-LinearesMtodos Numricos para uma Dimenso

Sistemas de Equaes No-Lineares

Sumrio

1 Equaes No-LinearesEquaes No-LinearesSolues e SensibilidadeConvergncia

2 Mtodos Numricos para uma DimensoMtodo da BissecoMtodo de Newton-RaphsonOutros Mtodos

3 Sistemas de Equaes No-LinearesMtodo de NewtonConsideraes Finais

Carlos Balsa Mtodos Numricos 2/ 28

Equaes No-LinearesMtodos Numricos para uma Dimenso

Sistemas de Equaes No-Lineares

Equaes No-LinearesSolues e SensibilidadeConvergncia

Equaes No-Lineares

Dada uma funo f , procuramos x , tal que

f (x) = 0

Soluo x raiz da equao, ou zero da funo f

Pelo que o problema conhecido como encontrar a raiz daequao ou encontrar o zero da funo

Carlos Balsa Mtodos Numricos 3/ 28

Equaes No-LinearesMtodos Numricos para uma Dimenso

Sistemas de Equaes No-Lineares

Equaes No-LinearesSolues e SensibilidadeConvergncia

Equaes No-Lineares

Dois casos importantesEquao no-linear nica sobre uma nica incgnita, em que

f : IR IR

Soluo o escalar x para o qual f (x) = 0Sistema de n equaes simultneas em n incgnitas, em que

F : IRn IRn

Soluo o vector x para o qual todas as componentes de Fso nulas simultneamente, F (x) = 0

Carlos Balsa Mtodos Numricos 4/ 28

Equaes No-LinearesMtodos Numricos para uma Dimenso

Sistemas de Equaes No-Lineares

Equaes No-LinearesSolues e SensibilidadeConvergncia

Existncia e Unicidade da Soluo

Existncia e unicidade da soluo so mais difceis de averiguarpara equaes no-lineares em comparao com as equaeslinearesSe f contnua e sinal (f (a)) 6= sinal(f (b)), ento o Teorema doValor Mdio implica que exista x [a, b] tal que f (x) = 0No existe um resultado anlogo to simples para o caso de ndimenses (sistema de n equaes no-lineares)

Carlos Balsa Mtodos Numricos 5/ 28

Equaes No-LinearesMtodos Numricos para uma Dimenso

Sistemas de Equaes No-Lineares

Equaes No-LinearesSolues e SensibilidadeConvergncia

Exemplos 1: Uma Dimenso

Equaes no-lineares podem ter um numero variado desolues

exp(x) + 1 = 0 no tem soluoexp(x) x = 0 tem uma soluox2 4 sin(x) = 0 tem duas soluox3 6x2 + 11x 6 = 0 tem trs soluosin(x) = 0 tem infinitas soluo

Carlos Balsa Mtodos Numricos 6/ 28

Equaes No-LinearesMtodos Numricos para uma Dimenso

Sistemas de Equaes No-Lineares

Equaes No-LinearesSolues e SensibilidadeConvergncia

Multiplicidade

Se f (x) = 0 e f (x) 6= 0, ento x uma raiz simplesSe f (x) = f (x) = f (x) = . . . = f (m1)(x) = 0 masf (m)(x) 6= 0, ento a raiz x tem multiplicidade m

Carlos Balsa Mtodos Numricos 7/ 28

Equaes No-LinearesMtodos Numricos para uma Dimenso

Sistemas de Equaes No-Lineares

Equaes No-LinearesSolues e SensibilidadeConvergncia

Exemplos 2: Multiplicidade de uma Raiz

x2 2x + 1 tem raiz x = 1 de multiplicidade 2x3 3x2 + 3x 1 tem raiz x = 1 de multiplicidade 3

Carlos Balsa Mtodos Numricos 8/ 28

Equaes No-LinearesMtodos Numricos para uma Dimenso

Sistemas de Equaes No-Lineares

Equaes No-LinearesSolues e SensibilidadeConvergncia

Sensibilidade e Condicionamento

Numero de condio do problema de clculo da razes x def : IR IR 1/ |f (x)|Raiz mal condicionada se a linha tangente foraproximadamente horizontalEm particular, razes mltiplas (m > 1) so mal condicionadasNumero de condio do problema de clculo da razes x deF : IRn IRn

J1F (x), com JF a matriz Jacobiana de j ,{Jf (x)}ij = fi(x)/xj

Raiz mal condicionada se a matriz Jacobiana foraproximadamente singular

Carlos Balsa Mtodos Numricos 9/ 28

Equaes No-LinearesMtodos Numricos para uma Dimenso

Sistemas de Equaes No-Lineares

Equaes No-LinearesSolues e SensibilidadeConvergncia

Sensibilidade e Condicionamento

Bem Condicionado Mal Condicionado

Carlos Balsa Mtodos Numricos 10/ 28

Equaes No-LinearesMtodos Numricos para uma Dimenso

Sistemas de Equaes No-Lineares

Equaes No-LinearesSolues e SensibilidadeConvergncia

Sensibilidade e Condicionamento

Que entendemos por soluo aproximada de um sistemano-linear,

F (x) 0 ou x x 0?

Primeira medida corresponde a um resduo pequeno, segundamede a proximidade em relao (geralmente desconhecida)soluo verdadeira x

Critrios de soluo no so necessariamente pequenos emsimultneo

Resduo pequeno implica soluo exacta apenas se o problemafor bem condicionado

Carlos Balsa Mtodos Numricos 11/ 28

Equaes No-LinearesMtodos Numricos para uma Dimenso

Sistemas de Equaes No-Lineares

Equaes No-LinearesSolues e SensibilidadeConvergncia

Taxa de Convergncia

Para um mtodo iterativo genrico, define-se o erro na iteraok por

ek = xk x

em que xk a soluo aproximada e x a soluo verdadeiraPara mtodos que mantm o intervalo onde se situa a soluoconhecido, em vez de se utilizar uma aproximao especifica soluo verdadeira, considera-se que o erro igual aocomprimento do intervalo que contm a soluoSequncia dos erros converge com uma taxa r se

limk

ek+1ekr

= C

para alguma constante finita e no-nula C

Carlos Balsa Mtodos Numricos 12/ 28

Equaes No-LinearesMtodos Numricos para uma Dimenso

Sistemas de Equaes No-Lineares

Equaes No-LinearesSolues e SensibilidadeConvergncia

Taxa de Convergncia, continuao

Alguns casos particulares com interesser = 1: linear (C < 1)r > 1: superlinearr = 2: quadrtica

Taxa de convergncia Dgitos ganhos por iteraolinear constante

superlinear aumentaquadrtica duplica

Carlos Balsa Mtodos Numricos 13/ 28

Equaes No-LinearesMtodos Numricos para uma Dimenso

Sistemas de Equaes No-Lineares

Mtodo da BissecoMtodo de Newton-RaphsonOutros Mtodos

Mtodo da Bisseco

Mtodo da bisseco consiste em dividir sucessivamente ameio o intervalo onde est situada a raiz at que a soluo sejaisolada com a correco pretendida

ALGORITMO: MTODO DA BISSECOInput: a e b tal que x [a, b]Output: x (soluo aproximada)while ((b a) > tol)

m = (a + b) /2se f (a)f (m) > 0

a = melse

b = mend

end

Carlos Balsa Mtodos Numricos 14/ 28

Equaes No-LinearesMtodos Numricos para uma Dimenso

Sistemas de Equaes No-Lineares

Mtodo da BissecoMtodo de Newton-RaphsonOutros Mtodos

Exemplo 3: Mtodo da Bisseco

Aproxime, com uma exactido de duas casas decimais (tol 0.5e 2),a raiz da equao

f (x) = x2 4 sin(x) = 0sabendo que x [1, 3], pois f (1) = 2.365884 e f (3) = 8.435520

k a b m f (m) x = b a0 1 3 2 0.3628101 1 2 1.5 -1.7399802 1.5 2 1.75 -0.8734443 1.75 2 1.875 -0.3007184 1.875 2 1.9375 0.0198495 1.875 1.9375 1.906250 -0.143255 0.1256 1.906250 1.9375 1.929688 -0.143255 0.06257 1.921875 1.9375 1.929688 -0.021454 0.03137 1.929688 1.9375 1.933594 -0.000846 0.01568 1.933594 1.9375 1.935547 0.009491 0.00799 1.933594 1.935547 0.0040 < tol

Carlos Balsa Mtodos Numricos 15/ 28

Equaes No-LinearesMtodos Numricos para uma Dimenso

Sistemas de Equaes No-Lineares

Mtodo da BissecoMtodo de Newton-RaphsonOutros Mtodos

Mtodo da Bisseco, continuao

Mtodo da bisseco converge de certeza, mas lentoEm cada iterao o cumprimento do intervalo contendo asoluo reduzido a metade, taxa de convergncia linear,com r = 1 e C = 0.5Dado um intervalo de partida [a, b], o cumprimento do intervalodepois de k iteraes (b a) /2k , pelo que a reduo do erroabaixo de certo valor tol implica que

k log2(

b atol

)independentemente da funo f envolvida

Carlos Balsa Mtodos Numricos 16/ 28

Equaes No-LinearesMtodos Numricos para uma Dimenso

Sistemas de Equaes No-Lineares

Mtodo da BissecoMtodo de Newton-RaphsonOutros Mtodos

Mtodo de Newton-Raphson

Desenvolvimento de uma funo em Srie de Taylor

f (x + h) = f (x) + f (x) h + f (x)h2

2!+ f (x)

h3

3!+ . . .

Truncando a srie de Taylor a partir do termo de primeira ordem

f (x + h) f (x) + f (x) h

obtemos uma funo linear em h que aproxima f em torno de xSubstituindo a funo no-linear pela funo linear, cujo zero h = f (x) /f (x), obtemos uma aproximao do zero de fComo os zeros das duas funes no so exactamente osmesmo repete-se este processo sucessivamente, originando omtodo de Newton-Raphson

xk+1 = xk f (xk )f (xk )

k = 0,1,2, . . .

Carlos Balsa Mtodos Numricos 17/ 28

Equaes No-LinearesMtodos Numricos para uma Dimenso

Sistemas de Equaes No-Lineares

Mtodo da BissecoMtodo de Newton-RaphsonOutros Mtodos

Mtodo de Newton-Raphson, continuao

Mtodo de Newton-Raphson aproxima a funo no-linear f , navizinhana de xk , pela recta tangente em f (xk )

Carlos Balsa Mtodos Numricos 18/ 28

Equaes No-LinearesMtodos Numricos para uma Dimenso

Sistemas de Equaes No-Lineares

Mtodo da BissecoMtodo de Newton-RaphsonOutros Mtodos

Exemplo 4: Mtodo de Newton-Raphson

Aproximar com uma exactido de duas casas decimais (tol 0.5e 2)a raiz da equao

f (x) = x2 4 sin(x) = 0sabendo que x [1, 3]Derivada

f (x) = 2x 4 cos(x)pelo que o esquema iterativo

xk+1 = xk x2k 4 sin(xk )