2013-2 - 05 - Soluções Aproximadas de Equações Algébricas e Transcendentais - 2 A5 Corpo 18

1

5. Solues Aproximadas de Equaes Algbricas e

Transcendentais

5.1 Isolamento de Razes

Equation Chapter 5 Section 1Se uma equao algbrica ou

transcendental for, em geral, complicada, normalmente no se pode

encontrar suas razes exatas. Assim, so importantes os mtodos de

aproximao de uma raiz e a estimativa de seu grau de preciso.

Seja ento uma equao qualquer 0f x , definida e contnua em um

intervalo ,a b , isto , ,f x C a b .

Em determinados casos necessrio que se garanta a continuidade,

tambm, da primeira derivada f x e da segunda derivada f x . Assim,

precisa-se que a funo 0f x seja definida em um espao 2 ,C a b .

A cada valor de x , onde a funo identicamente nula, denomina-se zero

ou raiz da equao. Assim, se em um determinado x , a funo f x for

nula, uma raiz dela.

Assumir-se- que as razes de f x so isoladas, isto , para cada raiz de

f x existe uma vizinhana ,V r em que no existe nenhuma outra raiz.

Teorema 1: Se uma funo contnua y f x assume valores opostos

em sinal nos pontos extremos de um intervalo ,a b , isto , se 0f a f b ,

ento no intervalo existir no mnimo uma raiz da equao 0f x .

Teorema 2: Seja uma raiz exata e x uma raiz aproximada da equao

0f x , ambas localizadas em algum intervalo ,a b e seja 0f x m para

a x b . Ento a seguinte estimativa permanece verdadeira:

3

f xxm

(Prove como exerccio. Sugesto: Use o teorema do valor mdio)

Seqncias de Sturm

O isolamento das razes importante, como j se viu acima. Outro

procedimento de fazer isso pelo estabelecimento de seqncias de

Sturm. Seja ento a equao a ser resolvida 0 0f x diferencivel no

segmento ,a b . Ento as funes contnuas

0 1, , , mf x f x f x (5.1.1)

formam uma seqncia de Sturm 0

m

k kf sobre ,a b se elas satisfazem as

seguintes condies:

0f x , tem pelo menos uma raiz em ,a b ; (5.1.2)

mf x , no se anula em ,a b ; (5.1.3)

se 1 10 0, ,k k kf f f a b ; (5.1.4)

se 0 0 10 0, ,f f f a b ; (5.1.5)

Teorema 3: O nmero de zeros de 0f x em ,a b igual diferena

entre o nmero de variaes de sinal em 0 1, , , mf a f a f a e em

0 1, , , mf b f b f b sabendo-se que 0 0 0f a f b e 0 1, , , mf x f x f x forma

uma seqncia de Sturm em ,a b .

Demonstrao

O nmero de variaes de sinais pode mudar quando x varia de a at b por meio de alguma funo que muda o sinal

sobre o intervalo. Por (5.1.3) a funo no pode ser mf x . Assumindo que em algum , 0ka b f para

algum k em 0 k m . Numa vizinhana de , o sinal precisa ser qualquer dos seguintes:

x 1kf kf 1kf ou x 1kf kf 1kf

+ - - +

+ 0 - - 0 +

5

+ - - +

Os sinais na linha x seguem de (5.1.4) Os sinais na primeira e ltima coluna advm da continuidade devido a que

ser suficientemente pequeno. A possibilidade de sinal na coluna central genrica. V-se que dessas tabelas que x

passa atravs de sem mudana de sinal. Examinando agora a variao de 0f x prximo da raiz x :

x 0f x 1f x ou x 0f x 1f x

+ - - +

0 - 0 +

- - + +

As colunas de 0f x representam os dois casos possveis para uma raiz simples. O sinal de 1f segue da condio

(5.1.5) e a continuidade implica nos demais sinais nas ltimas colunas. Claramente, existe nesse caso um decrscimo de

uma mudana no nmero de variaes quando x cresce a partir da raiz de 0f x . Quando esses resultados so

cambiados, segue o estabelecido no teorema.

relativamente fcil a construo de uma seqncia de Sturm quando

0f x um polinmio qualquer. Definindo-se:

1 0f x f x (5.1.6)

que satisfaz a condio (iv) para raiz simples. Ento se divide 0f x por

1f x e o resto 2f x . Divide-se ento 1f x por 2f x e o resto 3f x .

Continuando este procedimento at o fim (quando o polinmio

encontrado tiver grau menor que o seu predecessor):

0 1 1 2

1 2 2 3

2 1 1

1

m m m m

m m m

f x q x f x f x

f x q x f x f x

f x q x f x f x

f x q x f x

(5.1.7)

7

Este procedimento conhecido como algoritmo Euclidiano para

determinao do mximo divisor comum, mf x entre 0f x e 1f x .

EXERCCIOS

1. Isole as razes da equao 4 4 1 0f x x x

2. Uma aproximao de uma das razes da equao 4 1f x x x

1,22 . Estime o erro absoluto desta raiz.

5.2 Mtodo da Diviso em Duas Partes ou da Bisseo

Equation Section (Next)Seja a equao 0f x onde f x contnua em

,C a b e 0f a f b . Para achar a raiz da funo dada, existente no

intervalo ,a b , divide-se o intervalo ao meio. Se 2f a b , ento 2a b

a raiz procurada. Se 2 0f a b , ento se escolhe um novo intervalo,

ou , 2a a b ou 2,a b b de modo que o produto dos valores da funo

calculado nos extremos do novo intervalo seja menor que zero. Procede-

se assim, continuamente, at que se ache a raiz procurada, com um erro

estabelecido. Ou seja, tem-se a seqncia infinita de intervalos:

1 1, , , , , , ,n na b a b a b (5.2.1)

de modo que:

9

0, 1,2,2

n n n n n

b af a f b n b a

(5.2.2)

Isso garante que lim limn nn n

a b

que o que se procura.

Algoritmo da Diviso em Duas Partes ou da Bisseo

Entrar com os pontos extremos ,a b

Entrar com a tolerncia TOL

Entrar com o nmero mximo de iteraes N

1i

FA = f a Enquanto i N faa

/ 2p a b a % ponto mdio

FP = f p % valor da funo no ponto p

Se FP=0 ou / 2b a TOL

Ento imprima p

Pare;

1i i

Se 0FA FP Ento

a p

FA FP Seno

b p

Fim enquanto

Imprima mtodo falhou aps N iteraes =, N

fim

Exemplo

A equao 3 24 10 0f x x x tem razes em 1, 2 uma vez que 1 5f e

2 14f . Usando o algoritmo acima se escreveu o seguinte programa em

Matlab, para solucionar o problema:

% Mtodo da Diviso em 2 Partes - Biseco

%

clear; clc;

disp(' =========== Razes pelo Mtodo da Diviso ===========');

% funo f a ser determinada a raiz

f = @(x) x^3+4*x^2-10;

11

%

a = input('Entre com o extremo esquerdo = ');

b = input('Entre com o extremo direito = ');

TOL = input('Entre com a tolerncia = ');

N = input('Entre com o nmero mximo de iteraes = ');

fprintf('\n n= an= bn= pn= fpn=');

i=1;

FA=f(a);

while i

1 1.2 1.4 1.6 1.8 2-5

0

5

10

15

Eixo dos XE

ixo d

os

Y

Funo Polinomial do 3 Grau

Figura 5.1 Funo Polinomial de 3 Grau

13

Figura 5.2 Mtodo da Diviso para determinao de raiz entre 1 e 2

EXERCCIOS:

1. Determine a raiz da equao abaixo pelo mtodo da diviso, no

intervalo indicado com preciso de 510 :

a. 4 32 1 0f x x x x , no intervalo [0,1].

b. 3 20,2 0,2 1,2 0f x x x x , no intervalo [1,2].

c. 1 2sin( ) 0f x x x , nos intervalos 0;0,5 e 0,5;1 .

2. Uma calha de comprimento L tem sua seo transversal na forma

de um semicrculo de raio r . Quando cheia de gua at uma

distancia h do topo, o volume V de gua dado por:

1/ 22 2 2 20,5 arcsin hV L r r h r hr

. Supondo que 5L m , 0,50r m ache

a profundidade h quando:

15

a. 30,20V m , e

b. 31,40V m com preciso de 310 e de 510 respectivamente.

5.3 Mtodo das Cordas ou Mtodo da Falsa-Posio

Equation Section (Next)Este mtodo semelhante ao anterior e usa as

mesmas hipteses, isto , para se determinar uma raiz de ,f x C a b

necessrio se ter um intervalo ,a b tal que 0f a f b , pois isso implica

que exista pelo menos uma raiz no intervalo ou um nmero impar delas.

Seja, por exemplo, 0 0f a f b e que exista apenas uma raiz em ,a b .

Ento ao invs de se dividir o intervalo ao meio, dividimo-lo na razo

f a

f b . Isto produz uma aproximao do valor da raiz procurada:

1 1x a h (5.3.1)

onde

1

f a b ah

f b f a

(5.3.2)

17

Ento aplicando o mesmo procedimento ao intervalo 1 1, ,a x x b ,

conforme seja a situao em que o produto dos valores da funo nos

extremos seja menor que zero, encontra-se 2x , e assim sucessivamente.

Seja a corda existente entre o ponto ,A a f a e ,B b f b , cuja equao

(reta que passa por dois pontos):

( )( ) ( )

x a y f a

b a f b f a

Considerando que em 1x x , 0y , pois o ponto onde a corda corta o eixo

dos x , tem-se:

1

( ).( )

( ) ( )

f ax a b a

f b f a

(5.3.3)

Dependendo de que 0f a ou 0f b , o ponto contrrio ficar fixo, assim

poder-se- ter uma das seguintes frmulas vlidas (que so

completamente equivalentes):

1( )

.( ), 0,1,2,( ) ( )

nn n n

n

f xx x x a n

f x f a

(5.3.4)

ou

1( )

.( ), 0,1,2,( ) ( )

nn n n

n

f xx x b x n

f b f x

(5.3.5)

Comparando o mtodo das cordas com o da bisseo pode-se verificar

que no primeiro mtodo o erro 1n nnn

x x

x decresce mais rapidamente

que no segundo, mostrando que o esquema do mtodo das cordas

mais eficiente que o da bisseo.

19

Abaixo se apresenta o algoritmo das cordas desenvolvido em linguagem

em Matlab:

Algoritmo das Cordas

% Mtodo das Cordas ou da Falsa-Posio

%

clear;

clc;

%

% funo f a ser determinada a raiz (pode ser substituda pela

% funo que o leitor quiser, sempre na mesma sintaxe)

%

f = @(x) x^3+4*x^2-10;

%

TOL=0; N=0; a=0; b=0;

neg = 1;

while neg==1

disp(' ========== Razes pelo Mtodo das Cordas ==========');

a = input('Entre com o extremo esquerdo = ');

b = input('Entre com o extremo direito = ');

TOL = input('Entre com a tolerncia = ');

N = input('Entre com o nmero mximo de iteraes = ');

x0 = input('Entre com o valor inicial das iteraes = ');

if (f(a)*f(b) < 0 && x0 < b && x0 > a && TOL < 0.01)

neg = 0;

else

clc;

disp('Erro: Verifique limites ou valor inicial');

disp('----- Entre com os dados novamente -----');

end

end

%

fprintf('\n n= x(n)= x(n+1)= erro');

i=1;

x=linspace(1,2,100);

for k=1:100

y(k)=f(x(k));

end

h = figure(1); plot(x,y);grid on; axis on;hold on;

xlabel('Eixo dos X');

ylabel('Eixo dos Y');

title('Funo Polinomial do 3 Grau');

%

fa = f(a); % valor da funo no ponto a

fb = f(b); % valor da funo no ponto b

x(1) = 1.2;

if fa < 0

while i

21

fprintf('\n %2.0i %15.10f %15.10f %15.10f',i,x(i),x(i+1),erro);

if fp == 0 || erro < TOL

fprintf('\n Valor final da raiz = %16.12g',x(i+1));

disp(' ');

plot(x(i+1),fp,'dr'); %plota um diamante vermelho na raiz

return;

end

i=i+1;

end

else % f(b) < 0

while i

Executando-se o programa acima para o mesmo problema do exemplo

utilizado no mtodo da diviso em duas partes, com os mesmos

parmetros, se obtm os resultados apresentados a seguir. Observamos

que o mtodo das cordas tem convergncia mais rpida que o mtodo da

diviso em duas partes (Figura 5.2), pois enquanto este precisou de 17

iteraes aquele precisou de apenas 8 iteraes para a obteno da raiz

com erro da ordem 510 (Figura 5.3):

23

Figura 5.3 Metodo das Cordas determinao raiz [1 e 2].

EXERCCIOS

1. Determine a raiz da equao abaixo pelo mtodo das cordas e

mtodo da bisseo, com erro da ordem de 510 :



c. 20.5 2.5 4.5f x x x , no intervalo [0, 10].

2. Ache a menor raiz positiva da funo 2 cos 5x x usando os mtodos

das cordas e da bisseo. Para localizar a regio onde se encontra a

raiz, plot a funo no intervalo de 0 a 5. Realiza os clculos at que o

erro 1n nnn

x x

x seja menor que 1%. Cheque sua resposta final

substituindo na funo original.

25

3. A velocidade v de um pra-quedista caindo dada por 1 c m tgmv ec

onde 9,8g m/s2. Para um pra-quedista com um coeficiente de

arrasto 15c kg/s, calcule a massa m assim que a velocidade alcanar

35v m/s em 9t s. Use os mtodos conhecidos para obter uma

resposta com 1n nnn

x x

x

5.4 Mtodo de Newton-Raphson ou Mtodo da Tangente para

Equao Simples

Equation Section (Next)Este mtodo j foi apresentado na seo 4.4, para

o caso de aproximao de funes. Agora ser aplicado para a

determinao de razes.

Seja 0f x uma funo contnua definida em 2 ,C a b , semelhana do

que se admitiu nos casos anteriores, e que

0f a f b , e mais, que f x e f x sejam

contnuas e preservem o sinal em ,a b .

Seja n nx h (5.4.1)

uma raiz de f x , onde nh uma quantidade

pequena. Aplicando o desenvolvimento de Figura 5.4 Mtodo Newton-Raphson

27

Taylor, usando os dois primeiros termos, tem-se:

0 n n n nf f x h f x h f x

Donde se pode determinar nh :

n

n

n

f xh

f x

que substituindo em (5.4.1), encontra-se:

1

, 0,1,2,nn nn

f xx x n

f x

(5.4.2)

e onde uma boa aproximao para 0x aquela para qual a inequao

abaixo satisfeita:

0 0 0f x f x

Se v assm que este mtodo requer que 0f x tenha uma soluo e

mais, que sua derivada primeira seja contnua na vizinhana de e no

seja singular em .

EXERCCIOS

1. Determine a raiz da equao abaixo pelo mtodo de Newton:



c. 4 23 75 10000 0f x x x x , no intervalo [-100, -10]

d. tan 0f x x x , no intervalo [/2, 3/2]

29

Outra forma de apresentao deste mtodo, com uma pequena variao,

o conhecido como Mtodo de Newton Modificado, que ser visto a

seguir.

Se a derivada f x varia lentamente em um intervalo ,a b , ento a

frmula do Mtodo de Newton-Raphson Modificado :

1( )

'( )

nn n

n

f xx x

f x (5.4.3)

Pode-se fazer

0'( ) '( )nf x f x (5.4.4)

Assim o processo de aproximao, dar-se- pela frmula:

10

( )

'( )

nn n

f xx x

f x (5.4.5)

Este mtodo tem uma vantagem sobre o Mtodo de Newton-Raphson

Simples, pois se evita nele o clculo de nf x em cada aproximao.

EXERCCIOS

1. Determine a raiz da equao abaixo pelo Mtodo de Newton-

Raphson Modificado:

a. 4 22 1 0f x x x x , no intervalo [0, 1].

b. 3 20,2 0,2 1,2 0f x x x x , no intervalo [1, 2].

c. 4 23 75 10000 0f x x x x , no intervalo [-100, -10]

d. tan 0f x x x , no intervalo [/2, 3/2]

31

Usando o Mathcad para solucionar as razes de polinmios, atravs do

uso do menu Simbolics / Variable / Solve v-se abaixo alguns exemplos:

x4

3 x3 17.2x

2 3 x 60.5

has solution(s)

1.84464298797634823253.5421915825432999264i

1.84464298797634823253.5421915825432999264i

.344642987976348232451.9168634105775423629i

.344642987976348232551.9168634105775423629i

x3

5 x2 4 x 20

has solution(s)

5

2

2

1

2x2 x 2

has solution(s)

1 i 3

1 i 3

Figura 5.5 Determinao de Razes pelo MathCad

Outra forma de soluo de razes no Mathcad a seguinte, onde se usa o

menu Simbolics / Polinomial Coeficientes e logo depois a funo

polyroots:

33

p x( ) x4

2 x2 x 1

has coefficients

v

1

1

2

0

1

r polyroots v( )r

0.482

0.172 1.577i

0.172 1.577i

0.825

p x( )

x

1 0.5 0 0.5 1

1.5

1

0.5

0.5

Figura 5.6 Raizes pelo MathCad usando polyroots

5.5 Mtodo da Iterao

Equation Section (Next)Um dos mtodos mais importante para a soluo

numrica de equaes o mtodo das aproximaes sucessivas ou

mtodo da iterao,

Essencialmente, o mtodo consiste no seguinte. Seja uma equao

0y f x (5.5.1)

com f x contnua em 2 ,C a b e deseja-se determinar suas razes reais.

Troca-se a equao (5.5.1) como posta por outra equivalente, da forma:

x x (5.5.2)

De alguma maneira, escolhe-se uma aproximao inicial 0x para o valor

da raiz desejada e faz-se:

35

1 0

1n n

x x

x x

(5.5.3)

Se esta seqncia convergente, ento existe um limite lim nn

x

. Levando

esta hiptese em (5.5.3) obtm-se:

1 1lim lim limn n nn n n

x x x

ou seja,

(5.5.4)

Assim, o limite a raiz procurada de (5.5.2) e pode ser calculada pela

frmula iterativa (5.5.3).

Teorema 1: Seja a funo x definida e diferencivel no segmento

,a b com todos os valores ,x a b . Ento se existir uma frao prpria q ,

tal que:

1x q (5.5.5)

para a x b , ento:

o processo de iterao 1n nx x , converge, qualquer que seja o valor

inicial 0 ,x a b ;

o valor limite lim nn

x

a raiz da equao x x no intervalo ,a b .

a sucesso satisfaz a 1 1 0nn nx x q x x

Demonstrao:

Sejam duas aproximaes sucessivas

1n nx x e 1n nx x

37

Ento 1 1n n n nx x x x

Aplicando o teorema do valor mdio, tem-se:

1 _1n n n nx x x x (1)

Onde 1,n nx x . Mas 1x q e 11

n n

n n

x xx

x x

Logo 1 1n n n nx x q x x (2)

para 1,2,n , pode-se construir

2 1 1 0

2

3 2 2 1 1 0

1 1 1 0

n

n n n n

x x q x x

x x q x x q x x

x x q x x q x x

(3)

Seja ento a srie:

0 1 0 2 1 1n nx x x x x x x (4)

Para a qual as aproximaes sucessivas de nx so 1n somas parciais, que leva seguinte expresso: 1n nx S . De

(3) v-se que os termos de (4) so menores em valores absolutos que a correspondente srie geomtrica de razo 1q ;

logo (4) converge absolutamente. Assim

1lim limn nn n

S x

onde ,a b e a raiz de 1n nx x , a qual no tem qualquer outra raiz no intervalo ,a b . E mais, se

e ento:

1 0

c

c

com ,c ; como 1 0c , logo 0 donde se conclui que e nica.

Est demonstrado o teorema.

Nota: Este teorema permanece vlido se a funo x estiver definida e

for diferencivel num intervalo infinito , .

Teorema 2: Seja o segmento ,a b no qual ,x a b , isto , x existe e

satisfaz a desigualdade: 1x . Seja a seqncia 1 2 3, , ,x x x definida por

1 0, ,n nx x x a b . Se

1 1 0 ,1

x x x a b

39

Ento o teorema 1 acima permanece vlido.

5.5.1 Estimativa de uma aproximao.

Da terceira concluso do teorema 1 da seo anterior se tem:

1 1 2 1

1 2

1 0 1 0 1 0

2 1

1 0

1

n p n n p n p n p n p n n

n p n p n

n p

x x x x x x x x

q x x q x x q x x

q x x q q q

O ltimo termo do produto acima uma progresso geomtrica, cuja

soma 11

pq

q, logo se tem:

1 0 1 01

1 1

p nn

n p n

q qx x q x x x x

q q

Permitindo, na expresso acima, que no limite p v para o infinito, ento:

lim n p n np

x x x

logo

1 01

n

n

qx x x

q

(5.5.6)

donde se conclui que o processo de iterao converge o mais rpido

quanto menor for q. Ento como nx , tem-se

1 0(1 )

nqx x

q (5.5.7)

ou se considerar o erro na n-sima iterao tem-se

1(1 )

n

n n

qx x

q

(5.5.8)

41

Teorema 2: Seja a funo x definida e diferencivel em algum

intervalo ,a b e a equao

x x (5.5.9)

Ter uma raiz localizada em um pequeno intervalo , , onde:

1

3

1

3

a b a

b b a

No caso, se

0

1

,

a x q a x b

b x

ento:

1. todas as aproximaes sucessivas permanecem no intervalo ,a b :

1 , , 1n nx x a b n

2. o processo de aproximaes sucessivas convergente, isto , o

limite de nx existe: lim n

nx

e a nica raiz de (5.5.9) no intervalo

,a b .

3. a estimativa 1 0(1 )

n

n

qx x x

q

vlida.

Exemplo

Seja achar a raiz da equao sin 0,25x x , com trs dgitos

significantes, no intervalo [1,1; 1,3].

Soluo:

43

Escrevendo-se a equao dada como sin 0,25x x , ento:

sin 0,25x x e sua derivada cosx x e ento, pelo teorema 1,

precisa-se ter, para o valor inicial a condio:

1x q ento 0cos 1x q

Tomando-se q o menor possvel como, por exemplo, seja 0,5q ,

ento:

arccos 0,5 60 1,05x x rad

Seja ento a equao de iterao:

1sin 0,25n nx x

x(n+1) x(n) erro

1,0500000

1,1174232 1,1174232 0,0674232

1,1489748 1,1489748 0,0315516

1,1623447 1,1623447 0,0133699

1,1677369 1,1677369 0,0053922

1,1698653 1,1698653 0,0021284

1,1706980 1,1706980 0,0008327

1,1710227 1,1710227 0,0003247

1,1711491 1,1711491 0,0001264

1,1711983 1,1711983 0,0000492

1,1712175 1,1712175 0,0000191

Tabela 5.1 Dados iterao x=sin(x)+0.25

Analisando a tabela acima, v-se que o valor 1,171 tem os dgitos

significativos pedidos, pois na 7 e 8 iterao coincidem trs dgitos

significativos; assim,

41,171 1,26 10

45

EXERCCIOS

Achar as razes das equaes abaixo pelo mtodo da iterao.

1. 3 1000 0x x

2. 3 1 0x x

3. tan 0x x

4. 3 26 8 6 0x x x

5.6 Mtodo da Iterao para Sistemas de Duas Equaes

Equation Section (Next)Seja o sistema:

12

, 0

, 0

f x y

f x y (5.6.1)

cujas razes reais so necessrias serem determinadas com uma dada

preciso. Graficamente as razes do sistema so as intersees das curvas

de 1( , )f x y e 2 ,f x y .

Seja 0 0,x y uma primeira aproximao de uma raiz de (5.6.1) obtida de

alguma forma (graficamente ou por tentativas).

Mostra-se a seguir um processo iterativo o qual sob certas condies,

permite melhorar o valor da aproximao da raiz. Para fazer isso, (5.6.1)

deve ser reescrita da seguinte forma:

47

1

2

,

,

x x y

y x y

(5.6.2)

E se constri as aproximaes sucessivas de acordo com o seguinte

esquema:

1 1 0 0 1 2 0 0

2 1 1 1 1 2 1 1

1 1 1 2

, ; ,

, ; ,

, ; ,n n n n n n

x x y y x y

x x y y x y

x x y y x y

(5.6.3)

Se o processo de iterao acima converge, isto , se os limites abaixo

existem:

lim ; limn nn n

x y

ento, assume-se que 1 ,x y e 2 ,x y sejam contnuos, tem-se

1 2, ; ,x y x y

Teorema 1: Em uma regio fechada na vizinhana de uma raiz ,

do sistema (5.6.2), se as funes 1 ,x y e 2 ,x y forem definidas e

continuamente diferencivel em , a aproximao inicial 0 0,x y e todas as

aproximaes que se sucedem , , 1,2,n nx y n permanecem em , e as

seguintes desigualdades forem vlidas em :

1 21

1 22

1

1

qx x

qy y

ento o processo de aproximaes sucessivas (5.6.3) converge para as

razes do sistema (5.6.2), isto ,

lim limn nn n

x e y

49

Exemplo

Sejam

2

1

2

2

( , ) 2 5 1 0

( , ) 3log( ) 0

f x y x xy x

f x y x x y

Ache a raiz positiva prxima de 0 0, 3,5; 2,2x y para 4 dgitos

significativos.

Soluo

Para aplicar o mtodo iterativo do teorema 2 acima, se devem

reescrever as equaes dadas da seguinte forma:

1

2

( 5) 1( , )

2

( , ) 3log( )

x yx x y

y x y x x

e ento

1

2

1

2

5

( 5) 14

2

31

2 3log( )

( 5) 14

2

0

y

x x y

M

x

x x x

x

y x y

y

com ln 10 0,43429M .

51

Restringindo o espao de soluo a uma vizinhana do ponto 0 0,x y ,

tem-se, por exemplo,

3,5 0,1; 2,2 0,1x y

Que gera a regio 3,4 3,6 ; 2,1 2,3x y

Substituindo esses valores nas expresses das derivadas parciais,

obtm-se, colocando no numerador os x e y de maior valor e no

denominador os x e y de menor valor, de modo a que a expresso

seja a maior possvel, obtm-se:

1 2.3 5 0,543.4(2.1 5) 1

42

x

1 3,6 0,273,4(2,1 5) 1

42

y

23*0,43

13,4

0,422 3,4 3log(3.4)x

2 0y

logo

1 2 0,54 0,42 0,96 1x x

1 2 0,27 0 0,27 1y y

satisfazendo a condio (2) do teorema 1 acima.

53

Seja agora construir as aproximaes sucessivas pelas frmulas:

1

1

( 5) 1

2

3. log( )

0,1,2,...

n nn

n n n

x yx

y x x

n

(5.6.4)

n Xn Yn

- 3,500000 2,200000

1,000000 3,478505 2,265437

2,000000 3,483738 2,258912

3,000000 3,484835 2,260503

4,000000 3,485804 2,260836

5,000000 3,486391 2,261131

6,000000 3,486771 2,261309

7,000000 3,487013 2,261425

8,000000 3,487168 2,261498

9,000000 3,487267 2,261545

10,000000 3,487331 2,261575

11,000000 3,487371 2,261595

Tabela 5.2 Iterao pra Eqs 5.6.4

Logo 3,487nx e 2,261ny , nos quais a casa decimal j se repete a

partir da 6 iterao, logo, para quatro dgitos significativos, a

soluo :

3,48732,2615

Outra forma de resolver o problema exposto utilizar a ferramenta

de computao Mathcad, que utiliza o mtodo de Levenberg-

Marquardt que um mtodo quasi-Newton (uma variao do

mtodo do gradiente).

Veja como fcil a soluo do sistema de equaes dadas, no

Mathcad (Figura 5.7):

55

x 3.5 y 2.2

Given

2 x2 x y 5 x 1 0

x 3 log x( ) y2

0

Find x y( )3.487

2.262

Figura 5.7 Soluo Eqs.5.6.4 pelo MathCad

Ou seja, com poucas definies, obtm-se a soluo desejada.

Uma maneira de acelerar o processo iterativo fazer na construo

do esquema de aproximaes sucessivas uma alterao, utilizando

sempre os resultados mais recentes da iterao imediatamente

anterior. Este processo conhecido como processo de Seidel:

1 1

1 2 1

,

, , 0,1,2,

n n n

n n n

x x y

y x y n

Aplicando este processo ao exemplo anterior, tem-se:

n Xn Yn

- 3,500000 2,200000

1,000000 3,478505 2,258912

2,000000 3,482109 2,258912

3,000000 3,483986 2,260008

4,000000 3,485238 2,260579

5,000000 3,486032 2,260959

6,000000 3,486541 2,261200

7,000000 3,486866 2,261355

8,000000 3,487074 2,261454

9,000000 3,487207 2,261517

10,000000 3,487292 2,261557

11,000000 3,487346 2,261583

Tabela 5.3 Soluo das Eqs 5.6.4 usando o processo de Seidel

Logo 3,487nx e 2,261ny , nos quais a casa decimal j se repete a

partir da 8 iterao, logo, para 4 dgitos significativos, a soluo

57

3,48732,2615

5.7 Mtodo de Newton-Raphson para Sistemas de Equaes

5.7.1 Mtodo de Newton-Raphson para Sistemas de Duas Equaes

Equation Section (Next)Seja nx , ny uma raiz aproximada do sistema de

equaes:

1

2

, 0

, 0

f x y

f x y

(5.7.1)

onde 1 ,f x y e 2 ,f x y so funes continuamente diferenciveis. Colocando

n nn n

x x h

y y k (5.7.2)

tem-se

1

2

, 0

, 0

n n n n

n n n n

f x h y k

f x h y k

(5.7.3)

ou ainda

1 1

1

2 22

( , ) ( , )( , )

( , ) ( , )( , )

n n n nn n n n

n n n nn n n n

f x y f x yf x y h k

x y

f x y f x yf x y h k

x y

(5.7.4)

Se o jacobiano

1 1

2 2

( , ) 0n n

f f

x yJ x y

f f

x y

Ento de (5.7.4) tem-se

59

1 1

1 1

2 2) )2 2

,,

1 1

( , ( ,

n nn n

n n

n n n n

x yx y

f ff fy x

h e kf fJ x y J x y

f fy x

como

n nn n

h x x

k y y

tem-se

1

1

1

2)2

1

( ,n n

n n

ff

yx x

fJ x yf

y

(5.7.5)

1

1

1

2)2

1

( ,n n

n n

ff

xy y

fJ x yf

x

(5.7.6)

para 0,1,2,n , onde 0 0,x y pode ser determinado da maneira mais

grotesca possvel.

Exemplo

Seja o sistema de equaes

3 2

1

3

2

( , ) 2 1 0

( , ) 4 0

f x y x y

f x y xy y

(5.7.7)

Ache a raiz prxima de 0 0, 1.2;1.7x y .

Soluo:

Calculemos o valor das funes em 0 0,x y ; ento,

61

1 0 02 0 0

, 0,434

, 0,1956

f x y

f x y

Calculando, encontra-se:

0 0

0

0

, 97,910

0,0349

0,0390

J x y

h

k

Logo

1 0 01 0 0

1,2349

1,6610

x x h

y y k

Continuando a fazer os clculos da iteratividade tem-se:

n J hn kn xn yn

0 1,200000 1,700000

1 97,954760 0,034876 (0,039020) 1,234876 1,660980

2 99,585918 (0,000602) 0,000547 1,234275 1,661526

3 99,539742 (0,000000) 0,000000 1,234274 1,661526

4 99,539730 (0,000000) 0,000000 1,234274 1,661526

5 99,539730 0,000000 0,000000 1,234274 1,661526

6 99,539730 0,000000 (0,000000) 1,234274 1,661526

7 99,539730 0,000000 (0,000000) 1,234274 1,661526

Tabela 5.4 Iterao para raizes das Eqs. 5.7.7

Ver-se assim que a raiz procurada :

1,234274

1,661526

n

n

x

y

A soluo deste problema em Mathcad:

63

x 1.2 y 1.7

Given

2 x3 y

21 0

x y3 y 4 0

Find x y( )1.234274

1.661526

Figura 5.8 Soluo das Eqs 5.7.7 pelo MathCas

Observamos que a funo Find(x,y,) do Mathcad (Figura 5.8) pode

resolver at 50 equaes simultneas.

5.7.2 Mtodo de Newton-Raphson para Sistemas de n Equaes No-Lineares

Seja o sistema de equaes no-lineares:

1 1 2

2 1 2

1 2

. , , 0

. , , 0

. , , 0

n

n

n n

f x x x

f x x x

f x x x

(5.7.8)

ou de uma forma compacta:

0f x (5.7.9)

Seja px a p-sima aproximao de (5.7.9), pelo mtodo das aproximaes

sucessivas:

1 2, , ,p p p pnx x xx

Ento a raiz exata de (5.7.9) pode ser representada por:

p p x x (5.7.10)

65

onde 1 2, , ,p p p pn a correo. Levando-se (5.7.10) em (5.7.9), tem-

se:

0p pf x f x (5.7.11)

Sob a hiptese de que a funo f x continuamente diferencivel em

algum domnio convexo contendo x e px , pode-se expandir o lado

esquerdo de (5.7.11) em potncia do pequeno vetor p , retendo apenas

seus termos lineares:

0p p p p pf x f x f x f x (5.7.12)

pf x uma matriz especial conhecida na anlise matemtica como

matriz jacobiana de 1 2, , , nf f ff com relao s variveis 1 2. , , nx x x , isto

,

1 1 1

1 2

2 2 2

1 2

1 2

...

...'( ) ( )

... ... ... ...

...

n

n

n n n

n

f f f

x x x

f f f

x x x

f f f

x x x

f x J x

(5.7.13)

ou ainda de uma forma mais compacta:

, , 1, 2, ,ij

fi j n

xf x J x

Reescrevendo-se (5.7.12) tem-se:

0p p p p p pf x f x f x J x (5.7.14)

ou ainda, se a matriz jacobiana for no-singular,

1p p p J x f x (5.7.15)

67

Levando (5.7.15) em (5.7.10), e considerando-se que a prxima

aproximao seja a 1p -sima, tem-se:

1 1 , 0,1,2, ,p p p p p nx x J x f x (5.7.16)

e conhecido como Mtodo de Newton-Raphson, que anlogo quele

mtodo apresentado no item 5.4.

EXERCCIOS

Determine uma aproximao ( 310erro ) da soluo positiva do

seguinte sistema de equaes:

2

1 10

2

2

, 3

, 2 5 1

f x y x log x y

f x y x xy x

pelo Mtodo de Newton , tomando como soluo inicial 3,4x e

2,2y .

5.8 Interao Funcional para Sistemas de Equaes

Equation Section (Next)Seja um espao vetorial ou euclidiano

completo. Seja x um vetor coluna n-dimensional com componentes

1 2. , , nx x x e : f x uma funo vetorial n-dimensional, isto , com

componentes 1 2, , , nf f fx x x . Ento o sistema a ser resolvido :

x f x (5.8.1)

Ou de forma aberta

1 1 1 2

2 2 1 2

1 2

( , ,..., )

( , ,..., )

( , ,..., )

n

n

n n n

x f x x x

x f x x x

x f x x x

A soluo ou raiz de (5.8.1) algum vetor com componentes 1 2, , , n

os quais so por sua vez algum ponto no espao euclidiano dado. O

processo iterativo iniciado com uma aproximao 0x da raiz , isto ,

69

0 0 0 01 2, , , nx x xx

ou seja

1 , 0,1,2,n n n x f x (5.8.2)

Para anlise, pode-se usar uma norma qualquer dentre as seguintes:

1

11

2

21

max ii n

n

i

i

n

i

i

x

x

ou

x

x

x

x

(5.8.3)

Teorema 1: Seja f x satisfazendo a

1 2 1 2 f x f x x x (5.8.4)

para todos os elementos ,1 2x x , tal que 01x x e

0

2x x , com a

constante de Lipschitz satisfazendo a seguinte relao:

0 1 (5.8.5)

Seja 0x numa vizinhana da raiz , de maneira que a iterao inicial 0x

satisfaa a

(0) (0)( ) (1 ) f x x (5.8.6)

Ento todas as iteraes (5.8.2) satisfazem a

( ) (0)nx x (5.8.7)

as iteraes convergem para algum vetor:

lim nn

x (5.8.8)

71

onde a raiz de (5.8.1). Logo a nica raiz de (5.8.1) em (0)x x .

Demonstrao:

Provar-se- (i) por induo. Seja ento 1 0x f x , ento de (5.8.6) e (5.8.2) tem-se

2

(1 ) (1 )

... (1 )n n

(0) (0) (1) (0)

(n+1) (n) (n) (n-1) (n-1) (n-2) (1) (0)

f x x x x

x x x x x x x x (5.8.9)

Ento aplicando recursivamente

1

...

...

( ... 1)(1 ) (1 )n n n

(n+1) (0) (n+1) (n) (n) (n-1) (1) (0)

(n+1) (n) (n) (n-1) (1) (0)

x x x x x x x x

x x x x x x

visto que < 1 . Logo (i) est demonstrado.

Para provar (ii) deve-se provar que a seqncia nx de Cauchy. Assim, para inteiros positivos e arbitrrios m e p ,

seja:

1 1

...

...

( ... )(1 ) (1 )m m m p p m

(m) (m+p) (m) (m+1) (m+1) (m+2) (m+p-1) (m+p)

(m) (m+1) (m+1) (m+2) (m+p-1) (m+p)

x x x x x x x x

x x x x x x .

Tem-se usado aqui as inequaes (5.8.9), as quais so vlidas, pois (i) foi provado. Agora dado 0 , com 0,1

fixo, pode-se achar um N tal que m m p x x para todo ; 0m N p . Veja que, necessita-se que

N

, ento a seqncia nx uma seqncia de Cauchy e tem limite em uma vizinhana V 0x de 0x .

Assim f x contnua em V 0x e a seqncia nf x tambm de Cauchy e tem um limite f que por (5.8.2) tambm , isto , f . Logo

1 0n n n n n x f x f x x

Para a parte (iii) que a prova da unicidade da soluo, seja outra raiz de (5.8.1) na vizinhana V 0x . Ento e

esto ambas em V 0x , assim como (5.8.4) verdadeiro, tem-se

( ) ( ) f f

Isto uma contradio, logo implica que . Est provado (iii). Como esto provados (i), (ii). (iii), o teorema est

demonstrado.

73

Teorema 2: Seja, x f x , com uma raiz x . Sejam os componentes

de f x contnuas e que tenham tambm a primeira derivada parcial

contnua e satisfazendo a

( )ij

f

x n

x (5.8.10)

< 1 para todos os elementos

x x (5.8.11)

Ento para qualquer 0x satisfazendo (5.8.11), todas as iteraes nx de

(5.8.2) tambm satisfazem a (5.8.11).

Para qualquer 0x satisfazendo (5.8.11) as iteraes de (5.8.2) convergem

para uma raiz de (5.8.1) a qual nica em (5.8.11).

Demonstrao:

Para quaisquer dois elementos , 1 2x x e satisfazendo a (5.8.11), pelo teorema de Taylor (desenvolvimento de

funes em srie) tem-se:

( )

1, 2,

1 1,

( )( ) ( )

ini

i i j j

j j

ff f x x

x

1 2x x (5.8.12)

para 1,2, ,i n e onde i

um ponto do segmento aberto que une , 1 2x x e onde 1, 2,,j jx x so os

componentes dos elementos , 1 2x x , respectivamente. Assim

i satisfaz (5.8.11). Usando (5.8.3) e (5.8.10) tem-

se:

( )

1, 2,

1 1,

( )

1,

( )( ) ( ) .

( )

ini

i i j j

j j

i

i

j

ff f x x

x

f

x

1 2

1 2 1 2

x x

x x x x

(5.8.13)

Assim, a inequao permanece para i, e tem-se ( ) ( ) .

1 2 1 2

f x f x x x e assim prova-se que f x contnua

no domnio (5.8.11) com relao norma indicada. Note que para qualquer 01

x em (5.8.11)

( ) ( ) . .

(1) (0) (0)1 1 1x f x f x

onde 01

x tambm satisfaz a (5.8.11). bvio, que por induo, obtm-se:

75

( ) ( )

.

...

. .n n

(n) (n-1)

1 1

(n-1)

1

(0)

1

x f x f

x

x

(5.8.14)

Logo todos os n1

x esto em (5.8.11), o que segue sua convergncia (5.8.14) acima, com < 1. A prova da unicidade

semelhante o que se fez no teorema 1 anterior.

O ponto crucial da demonstrao acima a derivao em (5.8.13). claro que em (5.8.10) preciso ser substitudo por

um nmero de condies as quais devem ser, talvez, menos restritivas, mas permanecendo vlido o teorema. Uma

dessas condies :

1

max ( ) 1,n

iji

j

f

x x (5.8.15)

onde se introduz o elemento iijj

ff

x

x. Se ijf F x x uma matriz, ento (5.8.15) pode ser reescrito como:

( ) 1 F x , onde a norma da matriz induzida pela norma de mximo vetor ou norma uniforme

.

Se a funo f x tal que a raiz

( )( ) 0, , 1,2,...,i

j

fi j n

x

F (5.8.16)

e essas derivadas so contnuas prximas raiz, ento (5.8.10) bem como (5.8.15) pode ser satisfeita para algum > 0 .

Se, alm disso, as derivadas segundas dos componentes de f x em relao aos componentes de x : 2 ( )i

j k

f

x x

x existem

na vizinhana da raiz. Novamente pelo teorema de Taylor, tem-se:

2 ( )

1 1

1 ( )( ) ( )

2

in ni

i i j j k k

j k j k

ff f x x

x x

x .

Agora, na iterao (5.8.2), tem-se: 2

.M

(n) (n-1)x x onde M escolhido de maneira que:

2

2, ,

( ) 2.max ii j k

j k

f M

x x n

x.

Logo a convergncia quadrtica pode ocorrer na soluo do sistema de equaes por iterao.

77

5.8.1 Alguns Esquemas Explcitos de Iterao para Sistemas

Em geral, o sistema a ser resolvido est na forma:

0f x (5.8.17)

Tal sistema pode ser representado na forma estudada (5.8.1) do item

anterior, de diversas maneiras. Aqui ser escolhida a seguinte forma:

g x x A x f x (5.8.18)

onde A x uma matriz quadrada de n-sima ordem com componentes

ija x . As equaes (5.8.1) e (5.8.17) tero as mesmas solues, se A x for

no singular, isto , se

0 0 A x f x f x

Uma escolha simples para A x uma matriz constante, A x A , no

singular. Seja ento a matriz

( )( ) ij

f

x

xJ x

cujo determinante o jacobiano das funes if x ; ento de (5.8.18),

considerando as definies anteriores, tem-se:

( )( ) . ( )ij

f

x

xg x I A J x (5.8.19)

Pelo segundo teorema da seo anterior, ou pela sua modificao onde

(5.8.15) substitui (5.8.10) as iteraes usando:

( ) (n+1) (n) (n)x x Af x (5.8.20)

79

converge, para um nx suficientemente prximo de , se os elementos da

matriz (5.8.19) forem suficientemente pequenos, por exemplo, quando

no caso de J ser no singular e A ser aproximadamente igual inversa

de J . Este procedimento anlogo ao Mtodo das Cordas e ele sugere

uma alterao natural, a qual, novamente, denominada de Mtodo de

Newton.

No mtodo de Newton, a matriz A x substituda por:

-1A x J x (5.8.21)

onde se assume a hiptese de 0J x para x em x . O uso desse

procedimento interessante, pois no se necessita calcular uma inversa

a cada iterao; e melhor ainda, um sistema linear de ordem n tem que

ser resolvido. Para ver isso, e ao mesmo tempo ganhar algum

discernimento do mtodo, note que usando (5.8.21) em (5.8.18) as

iteraes do Mtodo de Newton so:

n+1 n n n n-1x g x x J x f x (5.8.22)

onde 0g x dado. Da tira-se:

n n n+1 nJ x x x f x (5.8.23)

e requer que f x tenha duas derivadas e J x seja no singular em para

que o mtodo tenha convergncia quadrtica.

81

Exemplo

Solucionar o sistema abaixo usando o mtodo de Newton para

determinar uma raiz positiva prxima de 0 0 01 2 3, , 0,5;0,5;0,5x x x0

x :

2 2 2

1 2 3

2 2

1 2 3

2 2

1 2 3

1

2 4. 0

3 4 0

x x x

x x x

x x x

(5.8.24)

Reescrevendo o sistema acima na forma (5.8.19), tem-se:

2 2 2

1 2 3

2 2 4

1 2 3

2 2

1 2 3

1 0

( ) 2 4 0

3 4 0

x x x

x x x

x x x

f x

ento

0,25 0,25 0,25 1 0,25

( ) 0,5 0,25 2 1,25

0,75 2 0,25 1

(0)f x

o Jacobiano

1 2 3

1 2

1 3

2 2 2

4 2 4

6 4 2

1 1 1

( ) 2 1 4 det ( ) 40

3 4 1

x x x

x x

x x

(0) (0)

J x

J x J x

A matriz inversa

115 5 5

114 2 6

4011 7 1

(0)J x

usando (5.8.22), obtm-se a primeira aproximao:

83

( ) ( )

3 1 18 8 80,5 0,25

7 310,5 1,2520 20 20

0,5 1711 140 40 40

[0,875;0,500;0,375]

(1) (0) -1 (0) (0)

(1)

x x J x f x

x

Procedendo de maneira semelhante para as demais iteraes,

encontra-se:

0,78981

0,49662

0,36993

0,78521

0,49662

0,36992

(2)

(3)

x

x

Usando-se agora o Mathcad:

Sejam x = x1, y = x2 e z= x3, tem-se:

x 0.5 y 0.5 z 0.5

Given

x2

y2

z2

1 0

2 x2 y

24 z 0

3 x2 4 y z

20

Find x y z( )

0.785197

0.496611

0.369923

Figura 5.9 Soluo das Eqs 5.8.24 pelo Mathcad.

85

5.8.2 Observaes Gerais sobre a Convergncia do Mtodo de

Newton

Se a iterao inicial (0)x suficientemente fechada em torno da raiz de

0f x , ento o teorema 2 da seo 5.8 pode ser usado para provar que a

iterao n( )x definida em (5.8.22) converge para a raiz. Entretanto no se

sabe de antemo se uma dada iterao inicial (0)x est bastante prxima

da raiz procurada .

Desenvolver-se- uma condio suficiente, sob a qual o mtodo de

Newton converge, sem que se saiba de antemo o valor de .

Teorema 1: Seja (0)x uma aproximao inicial tal que a matriz jacobiana (0)

J x tem uma inversa com norma limitada por:

0 a-1J x (5.8.25)

Seja a norma da diferena das duas primeiras iteraes pelo mtodo de

Newton, limitada por:

1 0 0 0 b -1x x J x f x (5.8.26)

Sejam os componentes de f x terem segundas derivadas contnuas e que

satisfaam a:

2

1

( )n i

k j k

f c

x x n

x (5.8.27)

para todos os elementos 0 2 , , 1,2, ,b i j nx x x .

Se as constantes , ,a b c so tais que

1. .2

a b c (5.8.28)

87

Ento as iteraes de Newton ((5.8.22) e (5.8.23)) da seo 5.8.1 e

repetidas abaixo:

n+1 n n n n-1x g x x J x f x

n n n+1 nJ x x x f x

so unicamente definidas e permanecem na bola em torno de (0)x ,

denominado de 2b-bola :

0 2bx x

as iteraes convergem para algum lim nn

x para o qual 0f e mais

22

n

n

bx (5.8.29)

OBS: Todas as normas vetoriais deste teorema so normas mximas .

e as normas das matrizes so aquelas induzidas pela norma mxima, isto

:

1

maxn

iji

j

aA (5.8.30)

Demonstrao:

A prova deste teorema requer, por convenincia, uma notao mais enxuta, sucinta. Assim, usar-se- a notao

n nJ J x para as matrizes jacobianas e 1

1 1 0,1,2, ,n n n n

A I J J . Assim

1 1

2

2

1( )

2

( ) 2 .

n

n

b

b

a

(n+1) (n)

(n+1) (0)

-1

n+1 n n n+1

-1 -1

n+1 n+1 n

x x

x x

A J J J

J I A J

(5.8.31)

89

Da hiptese (5.8.26) segue que (5.8.31)(a) e (5.8.31)(b) so satisfeitas para n=0. Agora, quando (5.8.31)(b)

estabelecido para quaisquer valores de n , ento 1n

x e n

x esto dentro da 2b-bola em torno de 0

x na qual

assegurada a existncia e continuidade das segundas derivadas de if x . Dessa forma pode-se aplicar o teorema de

Taylor para os componentes de 1nJ , para obter:

( 1) ( )

1

( ) ( )

.

ni in ni i

k k

kj j j k

ff fx x

x x x x

(n) (n+1) (n)

(n+1) (n) x x xx x

com 0 < i < 1 .

Assim ,(n+1) (n)

x x esto na 2b-bola, isto , esto em 0 2b ( )x x , logo o ponto n (n+1) (n)x x x tambm est inserido nesta bola, o que, aplicando (5.8.27) fornece:

.c (n+1) (n)n+1 n

J J x x (5.8.32)

No presente estgio s vlido para n=0. Mas usando (5.8.25), (5.8.26) e (5.8.28) em (5.8.31)(c), com 0n , tem-se:

1. . . . .

2a c a b c -1 (1) (0)1 0 1 0A J J J x x

Agora, (5.8.31)(a), (5.8.31)(b) e (5.8.31)(c) foi estabelecido para 0n . Se para qualquer valor de n a matriz nJ for no

singular e obedece a seguinte identidade

( ) n+1 n n+1

J J I J

onde, como em (5.8.31)(a), -1n+1 n n n-1A J J J . Mas sabe-se que se 1n+1A ento 1nJ no singular, e

1

-1

n-1

n+1

n+1

JJ

A (5.8.33)

Desde que (c) seja vlido para 0n , pode-se usar este resultado em (5.8.33), o que produz:

2a-11

J . Assim (5.8.31) tem se verificado para 0n .

Seja agora fazer uma hiptese de que (5.8.31) vlido para todos 1n k e proceder demonstrao de tambm

vlido para n k .

Desde que kJ seja no singular, a 1k -sima iterao de Newton 1k

x unicamente definida e de (5.8.22) da

seo anterior obtm-se:

. (k+1) (k) -1 (k) -1 (k)k kx x J f x J f x (5.8.34)

Entretanto, desde que (5.8.31)(b) seja vlido para 1n k , o ponto k

x est na 2b-bola em torno de 0

x . Ento pelo

teorema de Taylor, com o termo do resto e tendo em vista (5.8.22) com 1n k , tem-se:

1

1 1

( , )

( , )

( , )

k

k k

R

R

R

(k) (k-1) (k) (k-1) (k) (k-1)

(k-1) (k) (k) (k-1) (k) (k-1)

(k) (k-1)

f x f x J x x x x

J x x J x x x x

x x

usando (5.8.3) pode-se limitar o termo R acima para produzir (5.8.35) a seguir:

91

( ) ( 1) ( ) ( 1) 2

1 1

i

max ( , )

.max . .

2!

com 0< 12

i

k k k kn nj j i i i

ii

j i i j

R

x x x x f

x x

c

(k+1) (k) (k-1)

(k-1) (k) (k-1)

(k) (k-1)

f x x x

x x x

x x

(5.8.35)

Novamente usar-se- o fato de que (k+1) (k) (k-1)x x x est dentro da 2b-bola em torno de 0( )x desde que (k)x e (k-1)

x tambm estejam. Usando (5.8.35) em (5.8.34) e relembrando (5.8.31), que por hiptese vlida para 1n k ,

tem-se:

2 2

1 1 1

1

k

. .2

. . .2 . . .

2 2 2 2

1 .

2 2

b

2

k

k k k

k

c

c b a b c ba a b c

b

(k+1) (k) -1 (k) (k-1)

kx x J x x

Desta forma (5.8.31)(a) estabelecido vlido para n k , Ento, desde que:

( 1) (0) ( 1) ( )0

( 1) ( )

0

0

1 .

2

2.

kk p p

p

kp p

p

k

pp

x x x x

x x

b

b

(5.8.36)

a expresso (5.8.31)(b) tambm estabelecida vlida para n k . Mas ento (k 1)x est em 2b-bola em torno de 0( )x e

(5.8.32) tambm vlida para n k . Isso fornece:

.

. .

. .

1

2

c

a b c

-1

k+1 k k k-1

-1

k k k-1

-1 (k) (k-1)

k

A J J J

J J J

J x x

Isso prova que (5.8.31)(c) vlido para n k e implica que 1kJ no-singular. Ento usando (5.8.33) com n k ,

produz (5.8.31)(d) e assim est completa a prova indutiva de (5.8.31).

A parte (i) do teorema segue de (5.8.31)(b) e (5.8.31)(d). A convergncia de n( )x segue de (5.8.31)(a) desde que eles

formem uma seqncia de Cauchy, isto ,

93

1

1 1

1

.2

2

n p

q n

n p n p

qq n q n

n

qb

b

(n+p) (n) (q+1) (q)

(q+1) (q)

x x x x

x x (5.8.37)

Lembrando que o limite limn

(n)x usa-se (5.8.31)(a), (5.8.35) e a continuidade de f x para deduzir que

22. .

4kb c

(k)f x . Como no limite 0 (k)f x f , ento (5.8.36) ao limite quando p , tem-se:

2nb

(n) x , e assim a parte (ii) do teorema est estabelecida vlida e, por conseguinte, o teorema todo est

demonstrado.

Este teorema muito importante. Verifica-se que a condio 1. .2

a b c pode

ser satisfeita apenas se for igual a 11p

e se f for uma raiz de ordem

1p e se 2p . Por exemplo, se pf x x e 0 0x ento:

0

0

0 0

1 ( ) 1. . . . ( ) 1

( ) ( )a b c

p

f xf x

f x f x

Por outro lado, se 12

h abc , ento Kantarovich demonstrou que:

2 1

2.

2 1

n

n

hb(n)x (5.8.38)

isto , tem convergncia quadrtica.

95

5.8.3 Mtodo de Newton-Raphson Modificado

Um inconveniente essencial na formao do processo de Newton-

Raphson

(n+1) (n) -1 (n) (n)x x J x f x

a necessidade de calcular a matriz inversa -1 (n)J x para cada iterao. Se

a matriz -1J x contnua na vizinhana da soluo desejada e a

aproximao inicial 0x suficientemente prxima de (muitas vezes se

diz fechada em torno de ), ento se pode fazer a seguinte aproximao:

-1 (n) -1 (0)J x J x

Assim, chega-se ao processo de Newton-Raphson modificado:

f (n+1) (n) -1 (0) (n)x x J x x (5.8.39)

para 0,1,2,n .

Este processo conseqncia direta do resultado do ltimo teorema da

seo anterior.

Exerccios

Ache a soluo dos sistemas no-lineares abaixo e discuta sua

convergncia:

21 1

4 16

1 1sin

3 2

x y

x y

2

2

2 1

3 2

x y

x y

97

2

2

0,25 1,25

0,25 1,25

x y

x y

Mostre que o sistema 2

2

4 1,4

4 1,6

x y

x y tem uma e somente uma soluo em

0,1x e 0,1y . Ache a soluo com preciso de 410 . Prove que o

resultado obtido est dentro da preciso requerida.

Considere a soluo do sistema linear: 0,9 0,1 1

0,4 0,4 0

0,8 0,1 0

x y z

x y z

x y z

pelo seguinte

processo de iterao: 1

1

1

1 0 0,9 0,1

0 0,4 0 0,4

0 0,8 0,1 0

n n

n n

n n

x x

y y

z z

e mostre que esta

iterao converge para a nica soluo do sistema, para qualquer

conjunto arbitrrio de valores iniciais.

99

5.9 Anlises de Erro para Mtodos Iterativos

Equation Section (Next)Nesta seo se investigar a ordem de

convergncia dos esquemas iterativos de Newton. Para isso e necessrio

que se tenha uma medida de quo rapidamente uma seqncia

converge.

Definio 1: Seja 0n nx uma seqncia que converge para nx ,

com nx x para todo e qualquer n . Se existirem constantes positivas ,

tal que

1

lim

n

n n

x x

x x (5.9.1)

Ento 0n nx converge para x com ordem , com constante assinttica

de erro .

Uma tcnica iterativa da forma 1n nfx x dita ser ordem se a

seqncia 0n nx convergir para a soluo fx x de ordem .

Em geral, uma seqncia com uma ordem de convergncia mais alta

converge mais rapidamente que uma com ordem de convergncia mais

baixa. A constante assinttica afeta a velocidade de convergncia, mas

no to importante quanto ordem. Dois casos de ordem merecem

ateno:

Se (e ), a seqncia linearmente convergente;

Se , a seqncia quadraticamente convergente.

Para ver essa diferena entre a ordem de convergncia, seja o seguinte

exemplo: `

Exemplo:

101

Supondo que 0n nx seja linearmente convergente para 0 (zero) com

1

lim 0,5

n

n n

x

x

Seja tambm a seqncia 0n nz quadraticamente convergente para

0 (zero) com

1

2lim 0,5

n

n n

z

z

Por simplicidade, sejam 1 1

20,5 0,5

n n

n ne

x z

x z

Para o esquema que linearmente convergente isto significa que

21 1 2 00,5 0,5 0,5 nn n n nx 0 x x x x

Enquanto no esquema que quadraticamente convergente se tem

22 2 431 1 2 1

42 83 73 1

22 1 0

0,5 0,5 0,5 0,5

0,5 0,5 0,5

0,5nn

n n n n n

n n

z 0 z z z x

z z

x

2 1 2

10,5 .i i

iz z

; 10,5 .i

ix x

As tabelas a seguir ilustram a velocidade relativa de convergncia

das seqncias para zero, quando 0 0 1x z (feitas em Mathcad).

i 2 3 10

103

V-se que a seqncia

quadraticamente convergente

(valores z na Figura 5.10)) na sua

6 iterao j convergiu para o

resultado, enquanto a

linearmente convergente

(valores x na Figura 5.10) com 10 iteraes chega apenas prxima ao

valor obtido na 4 iterao da seqncia anterior. Entretanto bom

salientar que muitas tcnicas de convergncia so apenas lineares.

x1 1

z1 1

x

0

0

1

2

3

4

5

6

7

8

9

10

0

1

0.25

0.125

0.063

0.031

0.016

-37.81310

-33.90610

-31.95310

-49.76610

z

0

0

1

2

3

4

5

6

7

8

9

10

0

1

0.125

-37.81310

-53.05210

-104.65710

0

0

0

0

0

Figura 5.10 Sequencias de convergncia

O teorema 1 apresentado na seo 5.5 acima ser reapresentado a seguir

e dado uma demonstrao similar (porm no igual `aquela j

apresentada) como forma de obter alguns resultados intermedirios

necessrios para fundamentar a anlise de erro que se quer realizar:

Teorema 1: Seja ,f C a b tal que , , ,f x a b x a b . Seja, em adio, f

contnua sobre ,a b e que uma constante positiva 1q existe de modo

que

, ,f x q x a b

Se 0f x , ento para qualquer nmero inicial 0x em ,a b , a seqncia.

1 , 1n nx f x para n (5.9.2)

converge sempre linearmente para x em ,a b .

Demonstrao (veja demonstrao similar na seo 5.5):

105

Por hiptese existe um, e apenas um ponto x , raiz em ,a b . Dessa forma f mapeia ,a b nele mesmo e a seqncia

0n nx definida para todo 0n e ,nx a b . Usando o teorema do Valor Mdio e o fato de que

, ,f x q x a b se tem, para cada n ,

1 1 1.n n n n nx x f x f x f x x q x x

onde ,n a b . Aplicando a inequao acima indutivamente, se tem

2

1 2 0

n

n n nx x q x x q x x q x x (5.9.3)

Assim como 0 1q ter-se- que o limite da exponenciao de q lim 0nn

q e mais

0 0lim lim 0nn n nn n

x x q x x x x

E o teorema est provado.

Corolrio: Se f satisfaz as hipteses do teorema 1 acima, ento os

limites do erro envolvido no uso de nx para aproximar x dado por

0 0max ,nnx x q x a b x

e 1 0 , 11

n

n

qx x x x n

q

Demonstrao:

Seja ,x a b ento para o primeiro limite, tira-se de (5.9.3) o seguinte:

0 0 0max ,n n

nx x q x x q x a b x

Para 1n , se tem

2

1 1 1 1 2 1 0

n

n n n n n n n nx x f x f x q x x q x x q x x

Agora para 1m n , se tem

1 1 1

1 1 2 1

1 2

1 0 1 0 1 0

2 1

1 0 1

m n m m m n n

m m m m n n

m m n

n m n

x x x x x x x

x x x x x x

q x x q x x q x x

q x x q q q

Mas do teorema 1 acima se tem que lim mm

x x logo,

1

1 0 1 0

0 0

lim limm n

n i n i

n m nm m

i i

x x x x q x x q q x x q

Mas a somatria 0

i

i

q uma serie geomtrica com razo q e 0 1q ; essa seqncia converge para 1

1 q (como

se sabe do estudo das sries), o que leva ao segundo limite

107

1 01

n

n

qx x x x

q

Assim est demonstrado o corolrio.

Exemplos:

1 - Seja a equao 3 24 10 0x x ; ela tem uma raiz no segmento

, 1, 2a b . De quantas maneiras diferentes se pode representar a

equao de ponto fixo na forma x f x usando apenas

manipulaes algbricas. A partir das formas encontradas fazer um

estudo sobre a soluo das funes para verificar se elas so

realmente solues da equao original.

Soluo:

As formas de recorrncia que podem ser encontradas so:

(a) 3 2 3 214 10 0 4 10x x x f x x x x

(b) 12

3 2 2

2

10 104 10 0 4 0 4x x x x x x f x x

x x

(c) 123 2 2 3 31

3 24 10 0 4 10 10x x x x x f x x

(d) 12

3 2 2

42

10 104 10 0 4

4x x x x x f x

x x

(e) 1

33 2 3 2 2

54 10 0 4 10 0 10 4x x x x x f x x

Tomar-se- como ponto inicial 0 1,5x que o ponto mdio do

intervalo onde se sabe conter uma raiz.

Fazendo um procedimento em Mathcad para se estudar o resultado

de cada funo, se tem: como se v as funes dos casos (a), (b) e

(e) no atendem a equao original, enquanto as funes dos casos

109

(c) e (d) convergem para o valor da raiz, cujo valor 1,365230013.

Os resultados obtidos pelo procedimento Mathcad acima, para os

casos (a), (b) e (e) so respectivamente:

Resultado 15.1 Caso (a)

x1

1.5

0.875

6.732421875

469.720012002

1.027545552 108

1.084933871 1024

1.277055591 1072

2.082712909 10216

Resultado 5.2 Caso (b)

x2

1.5

0.816496581

2.996908806

2.941235061i

2.753622388 2.753622388i

1.814991519 3.53452879i

2.384265848 3.434388064i

2.1827719 3.596879228i

111

Resultado 25.3 Caso (e)

Para os casos (c) e (d) se tem as seguintes seqncias de

convergncia:

x5

1.5

1

1.817120593

0.737397496 1.277209928i

2.497908941 0.406090203i

1.629663175 1.951899706i

2.897699627 1.05712025i

2.312403297 2.130274605i

x4

0

0

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

1.5

1.348399725

1.367376372

1.364957015

1.365264748

1.365225594

1.365230576

1.365229942

1.365230023

1.365230012

1.365230014

1.365230013

1.365230013

1.365230013

1.365230013

1.365230013

1.365230013

1.365230013

1.365230013

1.365230013

1.365230013

x3

0

0

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

1.5

1.286953768

1.402540804

1.345458374

1.375170253

1.360094193

1.367846968

1.363887004

1.365916733

1.364878217

1.365410061

1.365137821

1.365277209

1.36520585

1.365242384

1.36522368

1.365233256

1.365228353

1.365230863

1.365229578

1.365230236

1.365229899

1.365230072

1.365229984

1.365230029

1.365230006

1.365230017

1.365230011

1.365230014

1.365230013

1.365230014

113

Resultado 5.4 Caso (c) Resultado 5.5

Caso (d)

V-se assim, que a funo 3f converge mais lentamente (30

iteraes foram necessrias) que a funo 4f (que necessitou de

apenas 11 iteraes para convergncia.)

2 - Faa estudo das 5 funes encontradas no exemplo acima, luz

do teorema 1 e seu corolrio.

Soluo:

Para 3 21 4 10x f x x x x como se tem que 1 11 6, 2 12f f

bvio que 1f no mapeia o intervalo 1, 2 nele mesmo. Alm do mais

21 11 3 8 1, 1, 2f x x x f x x . Pelo teorema 1, isso garante que o

mtodo falha e a convergncia no acontecem.

Com 12

2

104x f x x

x pode-se ver que

2f no mapeia 1, 2 em 1, 2 e

mais, a seqncia 0n n

x no definida nos quando 0 1.5x . Alm

disso, no existe intervalo que contenha 1.365x tal que 2 1f x , uma

vez que 2 3.4f x . Esta a razo pela qual ele no converge.

Para a funo 1231

3 210x f x x a sua derivada

122 33

3 410 0f x x x

em 1, 2 . Isso mostra que 3f estritamente decrescente em 1, 2 .

Entretanto 3 2 2.12f e falha a condio 3 1f x q sobre o intervalo

1, 2 . Entretanto examinando a funo mais de perto, v-se que a

seqncia 0n n

x iniciando com 0 1.5x pode ser considerada no

intervalo 1,1.5 em vez de 1, 2 . Sobre este novo intervalo 3 0f x e

115

que 3f estritamente decrescente em 1,1.5 ; e mais

3 3 31 1.28 1.5 1 1.5f f x f para todo e qualquer x pertencente a

1,1.5 . Isso mostra que 3f mapeia 1,1.5 em 1,1.5 e neste intervalo se

tem 3 3 1.5 0.66 1f x f que confirma a convergncia da funo.

Para a funo 12

4

10

4x f x

x, se tem

4 3 2

5

10 4f x

x de modo que

4 3 2 3 2

5 50.15, 1, 2

10 4 10 5f x x

x. O limite da magnitude de

4f x muito menor que o limite achado para 3f x , o que explica a

rpida convergncia de 4f .

5.10 Razes Mltiplas

Equation Section (Next)Para a funo 1

32

5 10 4x f x x v-se que ela no

mapeia 1, 2 em 1, 2 e mais, a seqncia 0n n

x no definida nos

quando 0 1.5x . Esta a razo para sua no convergncia.

Uma raiz mltipla corresponde a um ponto onde uma funo tangente

ao eixo dos x . Por exemplo, uma raiz dupla resultante de

2 ( 3) 1 1f x x x x (5.10.1)

ou multiplicando os termos: 3 22 5 7 3f x x x x . Essa funo tem uma raiz

dupla devido a que o valor 1x zerar dois termos na equao (5.10.1).

Fazendo o grfico se tem a Figura 5.11 abaixo, onde se pode ver que as

curvas tocam tangencialmente o eixo dos x na raiz dupla, sem cort-lo.

x 0 0.001 3.4

117

f2 x( ) x 3( ) x 1( ) x 1( )

f3 x( ) x 3( ) x 1( ) x 1( ) x 1( )

f4 x( ) x 3( ) x 1( ) x 1( ) x 1( ) x 1( )

0 0.44 0.88 1.31 1.75 2.19 2.63 3.06 3.5

32.672.33

21.671.33

10.670.33

0.330.67

11.331.67

22.332.67

33.333.67

4

Grfico de funoes com raizes multiplas

f2 x( )

f3 x( )

f4 x( )

x

Figura 5.11 Grficos das Funes f2, f3 e f4

119

Similarmente uma raiz tripla corresponde ao caso em que um valor de x

anula 3 termos em uma equao como a 3 ( 3) 1 1 ( 1)f x x x x x , que na

forma expandida :

4 3 26 12 10 3f x x x x x (5.10.2)

V-se no grfico acima que esta funo est representada por um trao

na cor azul e nota-se que ela corta o eixo dos x , sendo tangente no

ponto; alm disso, v-se tambm que ela muda de concavidade na raiz

mltipla.

Em geral as funes com um nmero impar de razes mltiplas, corta o

eixo dos x , o nem sempre verdade no caso de um nmero par de razes

mltiplas como se pode verificar na funo 4 ( 3) 1 1 ( 1)( 1)f x x x x x x

que est representado no grfico anterior com uma linha na cor marrom.

A determinao de razes mltiplas sempre um problema, pois nem

sempre possvel devido a diversas causas como a de que s vezes a

derivada da funo tambm tem um zero (ou raiz) no ponto onde a

funo original tem; isso pode levar a uma diviso por zero na frmula

iterativa do mtodo de Newton-Raphson(vide frmula (5.4.2)) uma vez

que nela existe a funo derivada f x no denominador:

1

, 0,1,2,nn nn

f xx x n

f x

Para contornar esse problema define-se uma nova funo u x , que a

razo entre a funo e sua derivada:

f xu xf x

(5.10.3)

121

Pode-se mostrar que esta funo tem as mesmas razes da funo

original. Substituindo (5.10.3) na expresso da formula de Newton-

Raphson se tem:

1

, 0,1,2,nn nn

u xx x n

u x

(5.10.4)

Calculando a derivada da funou x se tem:

2

f x f x f x f xu x

f x (5.10.5)

Levando (5.10.3) e (5.10.5) em (5.10.4) e simplificando se obtm:

1 2

n n

n n

n n n

f x f xx x

f x f x f x (5.10.6)

Exemplo:

Calcular a raiz 1x da equao (5.10.2) pelo mtodo de Newton-

Raphson como pelo mtodo modificado, tomando como valor inicial

0 0x .

Soluo:

Pelo Mtodo de Newton-Raphson:

A primeira derivada de 4 3 26 12 10 3f x x x x x 3 24 18 24 10f x x x x , logo

4 3 2

1 3 2

6 12 10 3

4 18 24 10n n

x x x xx x

x x x

Pelo mtodo modificado:

123

Aqui h necessidade da derivada segunda, isto , 212 36 24f x x x , logo

4 3 2 3 2

1 23 2 4 3 2 2

6 12 10 3 4 18 24 10

4 18 24 10 6 12 10 3 12 36 24n n

x x x x x x xx x

x x x x x x x x x

Utilizando-se o Excel para a realizao dos clculos iterativos se tem:

Newton-Raphson Newton-Raphson-modificado

Iterao x Erro x Erro

0 - 100,00% - 100,00%

1 0,300000 70,00% 1,071429 -7,14%

2 0,514773 48,52% 1,000914 -0,09%

3 0,666632 33,34% 1,000000 0,00%

4 0,772703 22,73% 1,000000 0,00%

5 0,845976 15,40% 1,000000 0,00%

6 0,896122 10,39% 1,000000 0,00%

7 0,930188 6,98% 1,000000 0,00%

8 0,953200 4,68% 1,000000 0,00%

9 0,968682 3,13% 1,000000 0,00%

10 0,979068 2,09% 1,000000 0,00%

11 0,986021 1,40% 1,000000 0,00%

12 0,990670 0,93% 1,000000 0,00%

13 0,993775 0,62% 1,000000 0,00%

14 0,995848 0,42% 1,000000 0,00%

15 0,997231 0,28% 1,000000 0,00%

Tabela 5.5 Sequencia de convergncia usando Excel

125

5.11 Razes de Polinmios

Equation Section (Next)V-se assim que o mtodo modificado tem uma

convergncia muito mais rpida que o mtodo de Newton-Raphson.

Quando a equao for um polinmio existem mtodos especficos para e

determinar as suas razes de maneira mais abrangente. Como se sabe os

polinmios tm a seguinte forma:

20 1 2

n

n nf x a a x a x a x (5.11.1)

Os coeficientes 0, na a podem ser reais ou complexos, mas nosso estudo

neste livro resume-se aos coeficientes reais.

Um polinmio de n -sima ordem tem n razes reais ou complexas e mais,

elas no so necessariamente distintas. As razes complexas sempre

aparecem em pares conjugados, isto , se uma p qj outra p qj onde

1j .

Teorema: Se a bj for um raiz complexa de multiplicidade m de um

polinmio com coeficientes reais, ento a bj tambm uma raiz de

multiplicidade m do mesmo polinmio e mais, o polinmio tem um fator

igual a 2 2 22 mx ax a b .

O software MATLAB trs embutido em si uma srie de funes que

auxiliam a determinao de razes de polinmios e outras caractersticas

dos polinmios:

poly p =poly(A)

p =poly(v)

- quando A for uma matriz n n retorna

um vetor p linha com 1n elementos,

que so os coeficientes do polinmio

127

caracterstico, ordenados em ordem

decrescente;

- quando v um vetor com as razes de

um polinmio retorna um vetor linha

com os coeficientes do polinmio

procurado cujas razes esto em v.

roots R=roots(p) - retorna um vetor coluna com as razes

do polinmio cujos coeficientes esto

no vetor p.

polyv

al

Y=polyval(p,x

)

- retorna o valor do polinmio de grau

n no ponto x. p um vetor contendo os

n+1 coeficientes de um polinmio de

grau n; x o ponto onde se quer avaliar

o valor do polinmio;

poly

der

k=polyder(p)

k=polyder(a,

b)

[q,d]=polyde

r(b,a)

- retorna a derivada do polinmio p;

- retorna a derivada do produto dos

polinmios a e b;

- retorna o numerador q e o

denominador d da derivada da diviso

do polinmio b/a;

- a, b e p so vetores contendo os

coeficientes de polinmios

deco [q,r]=deconv - retorna o polinmio quociente dos

polinmios u por v bem como o

129

nv (u,v) polinmio resto da referida diviso

Tabela 5.6 Funes Matlab para determinao de razes de Polinmios

No entanto, muito importante sabermos os algoritmos para a

determinao de razes. Para se determinar as razes de um polinmio,

quer sejam elas reais ou complexas, apresentar-se- a seguir alguns

mtodos entre os quais se destacam o mtodo de Mller e o mtodo de

Bairstow.

5.11.1 Mtodo de Mller

O mtodo de Mller consiste de determinar os coeficientes de uma

parbola que liga trs pontos. Esses pontos podem ser substitudos em

uma frmula quadrtica para obter o ponto onde a parbola intercepta o

eixo dos x , isto a raiz estimada. O procedimento facilitado escrevendo

a equao da parbola numa forma conveniente

22 2 2f x a x x b x x c (5.11.2)

O que se quer que esta parbola intercepte trs pontos 0 0,x f x ,

1 1,x f x e 2 2,x f x . Os coeficientes de (5.11.2) podem ser determinados

substituindo cada ponto na equao dada:

2

0 0 2 0 2

2

1 1 2 1 2

2

2 2 2 2 2

f x a x x b x x c

f x a x x b x x c

f x a x x b x x c

(5.11.3)

131

Por conciso retirou-se o ndice 2 da funo. Agora se tem 3 equaes e 3

incgnitas. V-se que da 3 equao de (5.11.3) se tem 2c f x ; levando

esse resultado as demais equaes, se tem:

20 2 0 2 0 2f x f x a x x b x x (5.11.4)

21 2 1 2 1 2f x f x a x x b x x (5.11.5)

Fazendo as manipulaes algbricas necessrias se tem:

0 1 0 1 2 1

1 0 2 1

0 1

1 0 2 1

h x x h x x

f x f x f x f x

x x x x

(5.11.6)

Substituindo (5.11.6) em (5.11.4) e (5.11.5) se tem

2

0 1 0 1 0 0 1 1

2

1 1 1 1

h h b h h a h h

h b h a h

Resolvendo para os coeficientes a e b encontra-se:

1 01 0

ah h

(5.11.7)

1 1b ah (5.11.8)

2c f x (5.11.9)

133

Para se achar a raiz aplica-se a frmula quadrtica equao (5.11.2).

Entretanto, devido a um erro de arredondamento em potencial, em vez

de se usar a forma tradicional pode-se usar a forma alternativa1:

3 2 2

2

4

cx x

b b ac (5.11.10)

Isolando o valor de 3x se tem:

1 Devido a problemas de cancelamento por subtrao de valores muito prximos a forma tradicional pode ser trocado por outra,

quando 2 4b ac , similar a (5.11.10). Isso minimiza o cancelamento por subtrao que , em geral, causa de instabilidade ou no

convergncia de processo iterativo.

3 2 2

2

4

cx x

b b ac (5.11.11)

Verifica-se que por esta formulao tanto as razes reais quanto as

complexas podem ser encontradas; isto o grande benefcio deste

mtodo.

O erro pode ser calculado ente as estimativas anteriores, 2x , e atual , 3x :

3 23

x x

x

O problema agora que a expresso (5.11.11) produz dois valores

correspondentes ao sinal existente no denominador. No mtodo de

Mller o sinal escolhido de modo a concordar com o sinal do

coeficiente b . Essa escolha ira produzir um denominador maior levando a

uma raiz estimada mais prxima de 2x .

135

Uma vez determinado o valor de 3x o processo se repete. Os prximos

valores a serem considerados para a determinao de 4x deve seguir a

uma das polticas a seguir:

se apenas razes reais sero localizadas, escolhe 3x e dois outros pontos

mais prximos dele;

se razes reais e complexas podem ser localizadas escolhe-se 3 2 1, ,x x x para

substituir 2 1 0, ,x x x .

Algoritmo do Mtodo de Muller

Algoritmo do Mtodo de Muller para solucionar 0f x dadas as

aproximaes 0 1 2, ,x x x :

So conhecidos a priori as aproximaes da raiz procurada 0 1 2, ,x x x , o erro ou tolerncia

desejada e o nmero de iteraes mximas desejadas.

Fazer

0 1 0

1 2 1

1 0

0

0

2 1

1

1

1 0

0 1

3

h x x

h x x

f x f x

h

f x f x

h

dh h

i

Enquanto i N fazer

1 1b h d

122

24D b f x d

137

Se b D b D

Ento E b D

Seno E b D

Faa

2

2

2 f xh

E

p x h

Se h erro

Ento p a raiz desejada, mostre-a e finalize o algoritmo

Faa (preparando a prxima iterao):

0 1

1 2

2

0 1 0

1 2 1

1 0

0

0

2 1

1

1

1 0

0 1

1

x x

x x

x p

h x x

h x x

f x f x

h

f x f x

h

dh h

i i

Mtodo Falhou, pois ultrapassou o nmero de iteraes estabelecido a priori.

139

Exemplo:

Fazer um programa em Matlab que encontre uma raiz de um

polinmio dado, conhecidos as aproximaes iniciais 3 2 1, ,x x x , o

nmero de iteraes e o erro tolerado. Mostrar passo a passo os

valores no decorrer do desenvolvimento do algoritmo.

Soluo:

O programa em Matlab o seguinte (seguindo o algoritmo supra

estabelecido):

% ================================================================

% == DETERMINAO DE RAIZES DE POLINOMIOS PELO MTODO DE MULLER ==

% ================================================================

clc

clear

% =========== DEFINIAO DE MENSAGENS E STRINGS ================

mens0 = '--------------------------------------------------';

mens1 = 'Ordem do Polinmio..................: ';

mens2 = 'Tolerncia a ser adotada ...........: ';

mens3 = 'Nmero mximo de iteraes..........: ';

mens4 = 'Coeficiente ';

mens5 = 'Aproximao x0 ....................: ';

mens6 = 'Aproximao x1 ....................: ';

mens7 = 'Aproximao x2 ....................: ';

mens8 = 'Polinmio Dado ...........: ';

mens9 = 'Raiz Procurada ...........: ';

mens10 = 'Nmero de iteraes ......: ';

mens11 = 'ERRO - Falha no Nmero de Iteraes ';

mens12 = 'Determinao de Razes pelo Mtodo de Mller';

mens13 = 'O valor da raiz procurada ';

mens14 = 'Parabns o Mtodo Convergiu';

dlgTitle = 'Dados do Problema: Mtodo de Mller';

format1 = ' %+12.8g ';

format2 = ' %+12.8g \n';

disp(mens0);disp(mens12);disp(datestr(now));disp(mens0);

% ===============================

% === ENTRADA DE DADOS GERAIS ===

%================================

prompt={mens1,mens2,mens3,mens5,mens6,mens7};

defp = {'4','0.00001','30','0.5','-0.5','0.0'};

dlgTitle = 'Dados do Problema: Mtodo de Mller';

lineNo = 1;

answer=inputdlg(prompt,dlgTitle,lineNo,defp);

ordem = str2double(answer(1)); % ordem do polinmio

tol = str2double(answer(2)); % tolerancia

nmax = str2double(answer(3)); % nmero maximo de iteraes

x0 = str2double(answer(4)); % aproximao x0



141

disp(mens0);disp(dlgTitle);disp(mens0);

fprintf(strcat(mens1,format2),ordem);

fprintf(strcat(mens2,format2),tol);

fprintf(strcat(mens3,format2),nmax);

fprintf(strcat(mens5,format2),x0);



disp(mens0);disp(' ');

% =============================================

% === ENTRADA DOS COEFICIENTES DO POLINOMIO ===

%==============================================

coef = [];

% at potencia 8 entrada via prompt, mais de 8 entrada via input

lineNo = 1;

switch ordem

case 2

prompt={strcat(mens4,'2'),strcat(mens4,'1'),strcat(mens4,'0')};

defp = {'1','1','1'};


a0 = str2double(answer(1)); %a0 = coef. da maior potencia

coef = [coef a0];

a1 = str2double(answer(2)); % a1 = coef de ordem-1

coef = [coef a1];


coef = [coef a2];

case 3

prompt={strcat(mens4,'3'),strcat(mens4,'2'),strcat(mens4,'1'),...

strcat(mens4,'0')};

defp = {'1','0','-13','-12'};


a0 = str2double(answer(1)); % a0 = coef da maior potencia

coef = [coef a0];


coef = [coef a1];


coef = [coef a2];


coef = [coef a3];

case 4


strcat(mens4,'1'),strcat(mens4,'0')};

defp = {'16','-40','5','20','6'};


% a0x(n)+a1x(n-1)+...+a7x(n-7)+a8x(n-8)

a0 = str2double(answer(1));% a0 = coef da maior potencia

coef = [coef a0];


coef = [coef a1];


coef = [coef a2];


coef = [coef a3];


coef = [coef a4];

case 5


strcat(mens4,'2'),strcat(mens4,'1'),strcat(mens4,'0')};

defp = {'1','-3.5','2.75','2.125','-3.875','1.25'};



coef = [coef a0];


coef = [coef a1];


coef = [coef a2];


coef = [coef a3];


143

coef = [coef a4];


coef = [coef a5];

case 6


strcat(mens4,'3'),...


defp = {'1','1','1','1','1','1','1'};



coef = [coef a0];


coef = [coef a1];


coef = [coef a2];


coef = [coef a3];


coef = [coef a4];


coef = [coef a5];


coef = [coef a6];

case 7


strcat(mens4,'4'),strcat(mens4,'3'),strcat(mens4,'2'),...

strcat(mens4,'1'),strcat(mens4,'0')};

defp = {'1','1','1','1','1','1','1','1'};



coef = [coef a0];


coef = [coef a1];


coef = [coef a2];


coef = [coef a3];


coef = [coef a4];


coef = [coef a5];


coef = [coef a6];


coef = [coef a7];

case 8


strcat(mens4,'5'),strcat(mens4,'4'),strcat(mens4,'3'),...


defp = {'1','1','1','1','1','1','1','1','1'};


%a0x(n)+a1x(n-1)+...+a7x(n-7)+a8x(n-8)


coef = [coef a0];

a1 = str2double(answer(2));

Documents

2013-2 - 05 - Soluções Aproximadas de Equações Algébricas e Transcendentais - 2 A5 Corpo 18