CAP. II – RESOLUÇÃO NUMÉRICA DE EQUAÇÕES NÃO … · Equações transcendentais – equações que envolvem funções transcendentais, tais como ex, sin x, ln x

Página 1 de 21 - Resolução numérica de equações

CAP. II – RESOLUÇÃO NUMÉRICA DE EQUAÇÕES NÃO LINEARES

Vamos estudar alguns métodos numéricos para resolver:

Equações algébricas (polinómios) não lineares;

Equações transcendentais – equações que envolvem funções

transcendentais, tais como ex, sin x, ln x.

DEFINIÇÃO (RAIZ DE UMA EQUAÇÃO OU ZERO DE UMA FUNÇÃO)

Um número z é uma raiz da equação f(x)=0 se f(z)=0.

Graficamente, a raiz real de uma equação f(x)=0 é o ponto onde a função f

“toca” o eixo dos xx.

x

y

ba

y=f(x)

raiz


O cálculo numérico de uma raiz envolve duas fases:

2.1 LOCALIZAÇÃO DAS RAÍZES

Nesta secção é feita uma análise teórica e gráfica da função f(x). Vejamos um teorema que nos vai ajudar a localizar as raízes de uma equação, num dado intervalo:

Teorema 1:

Seja f(x) contínua em [a,b]. Se f é tal que f(a).f(b)<0, então f tem pelo menos uma raiz z em ]a,b[.

Se, para além disso, f’(x) existe e preserva o sinal dentro do intervalo ]a,b[ (isto é, f’'(x)>0 ou f’(x)<0 para a<x<b, então a raiz z é única.

INTERPRETAÇÃO GRÁFICA:

1)

x

y

ba

y=f(x)

Fase I - Localização

Determinação de valores a e b de tal modo que a raiz z esteja

dontida num intervalo [a,b];

Fase II - Refinamento

Cálculo de uma sucessão x0, x1, x2, x3, x4, x5, ... de pontos do intervalo anterior, com lim xn = z; Objectivo: obter uma aproximação para z dentro de uma precisão ε prefixada.


2)

GRAFICAMENTE

Método mais simples para isolar uma raiz.

Para isolar graficamente uma raiz, basta fazer o esboço do gráfico de f(x) e

ver em que ponto ou pontos a função intersecta o eixo dos xx.

TÉCNICA:

Se a equação em causa é f(x)=0, escreve-se f(x) na forma h(x)-g(x) e

traçam-se os gráficos de h(x) e de g(x). Um valor z é raiz da equação

f(x)=0 precisamente quando os gráficos anteriores se intersectam, isto é,

se h(z)=g(z) pois, neste caso: f(z)=h(z)-g(z)=0.

x

y

ba

y=f(x)


EXEMPLO:

Considerar a função f(x)= ex - sinx -2.

Neste caso:

Sejam g(x)= ex e h(x)= sin(x)+2

-4 -3 -2 -1 0 1 2 3 40

5

10

15

20

25


2.2 REFINAMENTO DAS RAÍZES

O procedimento de um método iterativo para determinar a solução exacta z

de um problema pode, em linhas gerais, descrever-se do modo seguinte:

A aplicação do método requer o conhecimento de, em geral, uma

aproximação inicial x0 para a solução z.

Por meio de uma fórmula do tipo (fórmula de

iteração) é calculada uma sequência de aproximações (xk) para a solução.

Se são verificadas certas condições de convergência a solução procurada é

o limite desta sequência, i.e., kxk

z∞→

= lim , em que cada iteração xk está

mais perto da solução que a iteração anterior.

Assim, para se definir um processo finito de cálculo, xk pode ser tomada

como aproximação para z, i.e., kxz ≈ , e o erro kxz − é um erro de

truncatura que pode ser estimado.

2.3 CRITÉRIOS DE PARAGEM

Um método iterativo tem de terminar, necessariamente, num número finito

de passos. Assim, tornam-se necessários critérios de paragem que têm de

ser definidos, por forma a encontrar o resultado pretendido.

A decisão a tomar quanto ao critério de paragem deve ter em conta duas

situações:

1. a sequência de aproximações calculadas converge, com a rapidez

esperada, para a solução do problema e nessas condições o cálculo

xk = f ( xk-1 ), k=1,2,...


termina após a determinação de uma aproximação com a precisão

pretendida;

2. a sequência de aproximações calculadas não converge para a solução

ou verifica-se que a convergência é demasiado lenta.

Na situação 1., se a diferença entre duas iterações consecutivas é pequena

(entendendo-se por pequena se for menor que um dado valor pré-definido)

não se justifica a continuação do cálculo de iterações. Podemos, então,

definir os seguintes critérios:

onde 0>ε é a precisão do erro admitida.

Para evitar desperdiçar tempo de cálculo no computador no caso da

situação 2., ou de uma escolha incorrecta de um valor para ε (escolhido no

critério de paragem da situação 1.), um outro critério de paragem deve ser

usado adicionalmente:

O cálculo de iterações é interrompido com a determinação de xk se,

sendo kmax o número máximo de iterações especificado.

0sendo

1

1

≠<−

<−

k xε, kx

k - xkx

ε k - xk x

ii)

i)

k = kmax


2.4 MÉTODOS ITERATIVOS PARA RESOLUÇÃO DE EQUAÇÕES

2.4.1 MÉTODO DA BISSECÇÃO

Seja f(x) uma função contínua em [a,b], onde [a,b] é um intervalo que

contém uma única raiz de f(x)=0, que denotamos por z.

O método da bissecção consiste em construir uma sequência de intervalos

com amplitude sucessivamente menor dentro dos quais existe a raiz

procurada, até à precisão pretendida.

GRAFICAMENTE:

z

y

b

a

y=f(x)

xo x1


ANALITICAMENTE:

I0 = [a,b]

[ ]) ba, de médio ponto ( 2

bax0+

=

1ª iteração:

• se: f(a).f(x0) < 0, então z∈]a, x0[ e a1 = a, b1 = x0.

Neste caso, fazemos: 2

xa2

bax 0111

+=

+= e I1 = [a1,b1] = [a, x0] ;

• caso contrário, se f(x0).f(b) < 0, então z∈] x0, b [ e a1 = x0, b1 = a

e, neste caso, fazemos: 2

bx2

bax 0111

+=

+= e I1 = [a1,b1] = [

x0 , b] ;

• se nenhum dos casos anteriores acontecer então f(x0) = 0, logo z=x0.

2ª iteração:

• se: f(a1).f(x1) < 0, então z∈] a1, x1[ e a2 = a1, b2 = x1.

Neste caso, fazemos: 2

xa2

bax 11222

+=

+= e I2 = [a2,b2] = [a, x1] ;

• caso contrário, se f(x1).f(b1) < 0, então z∈] x1, b1 [ e a2 = x1, b2 = b1

e, neste caso, fazemos: 2

bx2

bax 11222

+=

+= e I1 = [a2, b2] = [x1, b1] ;

• se nenhum dos casos anteriores acontecer então f(x1) = 0, logo z=x1.


O processo é repetido até que se obtenha uma aproximação para a raiz

exacta z, com uma precisão não superior a ε .

EXEMPLO:

Calcular a raiz da equação f(x)= x2 -3 = 0 para x [ ]2 ,1∈ , com ε ≤ 0.03.

Raiz exacta:

Raiz aproximada:

k ak bk xk f(ak) f(bk) f(xk) erro

0 1 2 1.5 -2 1 -0.75 -

1 1.5 2 1.75 -0.75 1 0.0625 0.25

2 1.5 1.75 1.625 -0.75 0.0625 -0.359 0.125

3 1.625 1.75 1.6875 -0.3594 0.0625 -0.1523 0.0625

4 1.6875 1.75 1.7188 -0.1523 0.0625 -0.0459 0.0313

5 1.7188 1.75 1.7344 -0.0459 0.0625 0.0081 0.0156


CONVERGÊNCIA DO MÉTODO:

Este método gera uma sequência de intervalos I0, I1, I2, ... , Ik,... com

amplitude decrescente: I0 ⊃ I1 ⊃ I2 ⊃ … ⊃ Ik ⊃ ...

existindo z, xk ∈ Ik , k=0,1,2,... , tal que f(z)=0.

Sendo w (Ik) a amplitude do intervalo Ik, tem-se que:

)(I w21 ... )w(I

21.

21)w(I

21)(I w 0k2-k1-kk ====

Como w (I0)=b-a, obtém-se:

.0)(I wlim e 2

a-b)(I w kkkk ==

∞→

TEOREMA 2:

Seja f uma função contínua em [a,b] que satisfaz f(a).f(b)<0.

Seja xk o ponto médio do intervalo Ik gerado pelo método da bissecção.

Então,

ESTIMATIVA DO ERRO

Se z ∈ Ik = ]ak, bk[ , i.é, ak < z < bk , então ak – xk < z – xk < bk – xk ,

e se 2

bax kkk

+= obtém-se

2abxz

2ab kk

kkk −

<−<−

− .

Donde, ( )2Iw

2ab

xz kkkk =

−<− .

] [ zxlim e 0f(z) que tal b a, z k

==∈∃∞→

k


Assim, para determinar uma aproximação para uma raíz com erro ε, o

método iterativo é interrompido imediatamente após o cálculo do intervalo

Ik se metade da sua amplitude não excede ε, i.é, ( ) ε2Iw

<k .

ESTIMATIVA DO NÚMERO DE ITERAÇÕES (k)

Prova-se que:

Número mínimo de iterações k para determinar a raiz aproximada com um

erro não superior a ε : 1(2)

) /a-(bk −≥ ln

nl ε k +Ζ∈∧

PROPRIEDADES DE CONVERGÊNCIA

Dada uma equação f(x)=0 desde que se conheça um intervalo [a, b] ⊂ IR

onde f é contínua e tal que f(a).f(b)<0, é possível aplicar o método da

bissecção para calcular um intervalo tão estreito quanto se queira, contendo

uma raiz da equação.

Como não há restrições sobre a amplitude do intervalo inicial e portanto

sobre a distância dos extremos do intervalo inicial à raiz, o método da

bissecção é globalmente convergente.

2

ab 2

)w(I xx 1kk

1-kk εεε ≤−

⇔≤⇔≤− +


2.4.2 MÉTODO DA FALSA POSIÇÃO ( OU DO PONTO FIXO )

Seja f(x) uma função contínua em [a,b], onde f tem uma única raiz z no

intervalo [a, b].

O método da falsa posição consiste em, cada iteração, dividir o intervalo

[ak, bk] num ponto xk+1 :

( ) ( )( ) ( )kk

kkkk1k afbf

afbbfax−−

=+ (A)

correspondente à intersecção com o eixo dos xx da recta que passa pelos

pontos (ak, f(ak)) e (bk, f(bk)). É de notar que sendo f(ak).f(bk)<0 se tem que

xk+1∈ ]ak, bk[. Na iteração seguinte é utilizado o subintervalo ]ak, xk+1[ se

f(ak).f(xk+1)<0 ou o subintervalo ]xk+1, bk[, se f(xk+1).f(bk)<0.

GRAFICAMENTE:


ANALITICAMENTE:

• A equação da recta do tipo y - y0 = m.(x - x0), que passa pelos pontos

(ak, f(ak)) e (bk, f(bk)), com x0 = ak e fazendo x = xk+1, é dada por:

( ) ( )k1kkk

kkk ax

ba)f(b)f(aafy −

−−

=− +

A intersecção da recta anterior com o eixo dos xx origina o ponto (xk+1, 0),

donde:

( )kkkk

kk1k ba

)f(b)f(a)f(aa x −

−−=+ (B)

( ) ( )( ) ( )kk

kkkk1k afbf

afbbfa x−−

=⇔ + (A)

• A equação da recta do tipo y - y0 = m.(x - x0), que passa pelos pontos

(ak, f(ak)) e (bk, f(bk)), com x0 = bk e fazendo x = xk+1, é dada por:

( ) ( )k1kkk

kkk bx

ab)f(a)f(bbfy −

−−

=− +

A intersecção da recta anterior com o eixo dos xx origina o ponto (xk+1, 0),

donde:

( )kkkk

kk1k ab

)f(a)f(b)f(bbx −

−−=+ (C)

( ) ( )( ) ( )kk

kkkk1k afbf

afbbfa x−−

=⇔ + (A)


CONDIÇÕES DE CONVERGÊNCIA DO MÉTODO

Os teoremas seguintes estabelecem condições suficientes para a

convergência do método da falsa posição.

TEOREMA 3:

Sejam f e f ' contínuas no intervalo [a,b]. Se i) f(a).f(b) < 0

ii) f '(x) ≠ 0, (mantém o sinal), x ∈ [a,b]

então a sucessão de aproximações gerada pelo método da falsa posição

converge para z, único zero de f em [a,b].

TEOREMA 4:

Sejam f, f 'e f ''contínuas no intervalo [a,b]. Se i) f(a).f(b) < 0

ii) f '(x) ≠ 0, (mantém o sinal), x ∈ [a,b],

iii) f ' '(x) ≠0, (mantém o sinal), x ∈ [a,b],

então,

1) a sucessão de aproximações gerada pelo método da falsa posição

converge monotonamente para z, único zero de f em [a,b]

e, além disso,

2) um dos extremos do intervalo [a, b] é fixo, ao longo das iterações, tendo-se

( )cxf(c))f(x)f(xxx k

k

kk1k −

−−=+

com c = a ou c = b, tal que, f(c).f ' '(c) > 0.


Ao impormos a condição iii) no teorema 4, isto é, que a função f mantém a

concavidade em [a, b] ( f convexa para f ’’(x)>0, côncava para f ’’(x)<0 ),

estamos a restringir o método da posição falsa aos 4 casos seguintes:

CASO 1: f ’’(x)>0, f(a)<0 e f(b)>0

Da equação (B), para k=0, temos ( )00

00

001 ba

)f(b)f(a)f(aa x −

−−=

Fazendo a0 = x0 e mantendo b0 fixo, f(b0) > 0, obtemos

( )0000

001 bx

)f(b)f(x)f(xx x −

−−=

mas, f(x1) < 0 [ ]01101 b,xI 0)f(b)f(x =⇒<⋅⇒ e,

( )0101

112 bx

)f(b)f(x)f(xx x −

−−=

mas, f(x2) < 0 [ ]02102 b,xI 0)f(b)f(x =⇒<⋅⇒ e por indução,

temos que ( )0k0k

kk1k bx

)f(b)f(x)f(xx x −

−−=+ , isto é,

( )cxf(c))f(x)f(xx x k

k

kk1k −

−−=+ , com c = b0 tal que ( ) ( ) 0cfcf >′′⋅

x1 a0=x0 x2 z b0

fixo


CASO 2: f ’’(x)>0, f(a)>0 e f(b)<0

Da equação (C), para k=0, temos ( )00

00

001 ab

)f(a)f(b)f(bb x −

−−=

Fazendo b0 = x0 e mantendo a0 fixo, f(a0 ) > 0, obtemos

( )0000

001 ax

)f(a)f(x)f(xx x −

−−=

mas, f(x1) < 0 [ ]10110 x,aI 0)f(x)f(a =⇒<⋅⇒ e,

( )0101

112 ax

)f(a)f(x)f(xx x −

−−=

mas, f(x2) < 0 [ ]20220 x,aI 0)f(x)f(a =⇒<⋅⇒ e por indução,

temos que ( )0k0k

kk1k ax

)f(a)f(x)f(xx x −

−−=+ , isto é,


k

kk1k −

−−=+ , com c = a0 tal que ( ) ( ) 0cfcf >′′⋅

x1 x0=b0 x2 z a0

fixo


CASO 3: f ’’(x)<0, f(a)<0 e f(b)>0

Este caso 3 é semelhante ao caso 2:

Da equação (C), para k=0, temos ( )0000

001 ab

)f(a)f(b)f(bb x −

−−=

Fazendo b0 = x0 e mantendo a0 fixo, f(a0 ) < 0, obtemos

( )0000

001 ax

)f(a)f(x)f(xx x −

−−=

mas, f(x1) > 0 [ ]10110 x,aI 0)f(x)f(a =⇒<⋅⇒ ,

e por indução,

temos que ( )0k0k

kk1k ax

)f(a)f(x)f(xx x −

−−=+ , isto é,


k

kk1k −

−−=+ , com c = a0 tal que ( ) ( ) 0cfcf >′′⋅

x1

a0 fixo

x2 z x0=b0


CASO 4: f ’’(x)<0, f(a)>0 e f(b)<0

Este caso 4 é semelhante ao caso 1:

Da equação (B), para k=0, temos ( )0000

001 ba

)f(b)f(a)f(aa x −

−−=

Fazendo a0 = x0 e mantendo b0 fixo, f(b0) < 0, obtemos

( )0000

001 bx

)f(b)f(x)f(xx x −

−−=

mas, f(x1) > 0 [ ]01101 b,xI 0)f(b)f(x =⇒<⋅⇒ e,

( )0101

112 bx

)f(b)f(x)f(xx x −

−−=

e por indução,

temos que ( )0k0k

kk1k bx

)f(b)f(x)f(xx x −

−−=+ , isto é,


k

kk1k −

−−=+ , com c = b0 tal que ( ) ( ) 0cfcf >′′⋅

EXEMPLO:

Calcular a raiz da equação f(x)= x2-3=0 para x [ ]2 ,1∈ , com ε ≤ 0.03.

x1

b0 fixo

x2 z x0=a0


2.4.3 MÉTODO DE NEWTON - RAPHSON

Sejam f, f ', f '' contínuas em [a,b] e z raiz única da equação f(x)=0,

em [a, b].

O método de Newton consiste em, obter o valor de xk+1 como a intersecção

da tangente à curva de f no ponto (xk, f(xk)) com o eixo dos xx .

GRAFICAMENTE:

ANALITICAMENTE:

Escrevendo f em série de Taylor em torno de z, obtemos:

f(z) ≈ f(x0) + (z-x0) f '(x0) ( x0∈[a,b] )

Mas f(z)=0, donde

f(x0) + (z-x0) f '(x0) ≈ 0 ⇔

A relação anterior é a base da fórmula de recorrência do método de Newton:

xk+1 • z

y

xk

y=f(x)

)(xf)f(xx

0

00 '−≈z


CONVERGÊNCIA DO MÉTODO:

ESTIMATIVA DO ERRO

Uma estimativa para o erro da aproximação xk para z:

CONDIÇÕES DE CONVERGÊNCIA DO MÉTODO

O método de Newton (método da tangente) é localmente convergente, i.é,

para se verificar convergência, é necessário que a aproximação inicial x0

esteja suficientemente próxima da raiz z.

O teorema seguinte estabelece condições suficientes para a convergência

do método de Newton-Raphson.

TEOREMA 5:

Sejam f, f ', f '' contínuas no intervalo [a,b].

Se

i) f(a).f(b) < 0

ii) f '(x) ≠ 0, (mantém o sinal), x ∈ [a,b],

iii) f ' ' (x)≠ 0, (mantém o sinal), x ∈ [a,b],

iv) a aproximação inicial, extremo favorável, é x0 = a ou x0 = b,

onde f(x0). f ' ' (x0) > 0

então a sequência gerada pelo método de Newton converge para z, único

zero de f em [a,b].

As condições i) e ii) garantem que existe uma única raiz no intervalo [a,b];

)(xf)f(xxx

k'

kk1k −=+ Fórmula de recorrência

| z – xk | ≈ | xk – xk-1|


A condição iii) estabelece que f mantém a concavidade em [a,b] e além

disso, em conjunto com a condição ii), implica que f é monótona em [a, b];

A condição iv) diz que a tangente à curva quer em a quer em b intersecta o

eixos dos xx dentro do intervalo [a, b].

ORDEM DE CONVERGÊNCIA

O método de Newton tem ordem de convergência igual a 2, i.é,

convergência quadrática.

EXEMPLO:

Calcular a raiz da equação f(x)= x2-3=0 para x [ ]2 ,1∈ , com ε ≤ 0.03.

Documents

CAP. II – RESOLUÇÃO NUMÉRICA DE EQUAÇÕES NÃO … · Equações transcendentais – equações que envolvem funções transcendentais, tais como ex, sin x, ln x