Resolução Numérica de Equações Parte II

Prévia do material em texto

Cálculo Numérico
Resolução Numérica
de Equações (Parte II)
Prof.: Ednaldo Cardoso
Unidom
2
� Métodos Iterativos para a Obtenção de Zeros
Reais de Funções
� Bissecção (ou de Bolzano)
Falsa Posição
Cálculo Numérico – Métodos
� Falsa Posição
� Ponto Fixo
� Newton-Raphson
� Secante
3
Cálculo Numérico – Bissecção
� Método da Bissecção (ou de Bolzano)
Dada uma função f(x)f(x) contínua no
intervalo [a,b][a,b] onde existe uma raiz única,
é possível determinar tal raiz subdividindoé possível determinar tal raiz subdividindo
sucessivas vezes o intervalo que a contém
pelo ponto médio de aa e bb.
4
� Definição do intervalo inicial
� Atribui-se [a,b] como intervalo inicial
● a0 = a
● b = b
Cálculo Numérico – Bissecção
● b0 = b
� Condições de aplicação
● f(a)*f(b) < 0
● Sinal da derivada constante
5
� Definição dos subintervalos
� Subdivide-se o intervalo pelo ponto médio de a
e b
●● xx11 == (a+b)/(a+b)/22
Cálculo Numérico – Bissecção
●● xx11 == (a+b)/(a+b)/22
� Verifica-se se xx11 é uma aproximação da raiz da
equação
● Se verdadeiro ���� xx11 é a raiz procurada
● Caso contrário ���� define-se um novo intervalo
6
�Determina-se em qual dos subintervalos - [a, xx11]
ou [xx11 , b] - se encontra a raiz
● Calcula-se o produto f(a)*f(xx )
Cálculo Numérico – Bissecção
� Definição do novo intervalo
● Calcula-se o produto f(a)*f(xx11)
● Verifica-se se f(a)*f(xx11) < 0
� Se verdadeiro ���� ξξξξ ∈∈∈∈ (a, x1) (Logo a = a e b = xx11)
� Caso contrario ���� ξξξξ ∈∈∈∈ (x1 , b) (Logo a = xx11 e b = b)
�Repete-se o processo até que o valor de x atenda
às condições de parada.
7
Cálculo Numérico – Bissecção
� Análise gráfica
f(x)
xx11 = (a + b)/2= (a + b)/2
xa = a1 ξξξξξξξξ
f(x)
x1 = b1
xx22 = (a + x= (a + x11)/2)/2
xx22
xa = a0 ξξξξξξξξ b = b0xx11
xξξξξξξξξ
f(x)
x1 = b2
xx33 = (x= (x22 + x+ x11)/2)/2
x2 = a2
xx33Repete-se o processo até que o
valor de x atenda às condições de
parada.
8
Cálculo Numérico – Bissecção
� Condições de parada
�Se os valores fossem exatos
● f(x) = 0
● (x – x )/x = 0● (xk– xk+1)/xk = 0
�Não o sendo
● |f(x)| ≤≤≤≤ tolerância
● |(xk– xk+1)/xk| ≤≤≤≤ tolerância
9
�Aproximação de zero, dependente do
equipamento a ser utilizado e da precisão
necessária para a solução do problema
Cálculo Numérico – Bissecção
� Tolerância
10
Estimativa do número de iterações do método da 
bissecção
11
Algoritmo
k := 0; a0 := a; b0 := b; x0 := a;
xk+1 := (ak + bk)/2;
while critério de convergência não satisfeito and k≤≤≤≤L
if f(ak)f(xk+1) < 0 then /* raiz em [ak , xk+1] */
ak+1 := ak; bk+1 := xk+1;
Cálculo Numérico – Bissecção
ak+1 := ak; bk+1 := xk+1;
else /* raiz em [xk+1, bk] */
ak+1 := xk+1; bk+1 := bk ;
endif
k := k +1; xk+1 := (ak + bk)/2;
endwhile
if k>L
convergência falhou
endif
12
Exemplo 6:
Resgatando o Exemplo 5, no qual f(x)f(x) == xxlogxlogx –– 11
h(x)y
ξξξξξξξξ2 3
Cálculo Numérico – Bissecção
� Verificou-se que ξξξξξξξξ ∈∈∈∈ [[22,, 33]]
ξξξξξξξξ
g(x)
x1 2 3 4 5 6
ξξξξξξξξ2 3
13
Exemplo 6:
Considerando o método da bissecção e adotando
[[22,, 33]] como intervalo inicial
� x1 = (2 + 3)/2 = 2,5
�� f(f(22)) == --00,,39793979 << 00
�� ξξξξξξξξ ∈∈∈∈[[22,,55 ,, 33]]
Cálculo Numérico – Bissecção
�� f(f(22)) == --00,,39793979 << 00
�� f(f(33)) == 00,,43144314 >> 00
�� f(f(22,,55)) == --55,,1515..1010--33 << 00
� a1 = x1 = 2,5
� b1 = b0 = 3
� x2 = (2,5 + 3)/2 = 2,75
�� f(f(22,,55)) == --55,,1515..1010--33 << 00
�� f(f(33)) == 00,,43144314 >> 00
�� f(f(22,,7575)) == 00,,20822082 >> 00
�� ξξξξξξξξ ∈∈∈∈ [[22,,55 ,, 22,,7575]]
� a2 = a1 = 2,5
� b2 = x2 = 2,75
14
Exemplo 6:
� x3 = (2,5 + 2,75)/2 = 2,625
�� f(f(22,,55)) == --55,,1515..1010--33 << 00
�� f(f(22,,7575)) == 00,,20822082 >> 00
�� ξξξξξξξξ ∈∈∈∈ [[22,,55 ,, 22,,625625]]
� a3 = a2 = 2,5
� b3 = x3 = 2,625
Cálculo Numérico – Bissecção
�� f(f(22,,625625)) == 00,,10021002 >> 00
� b3 = x3 = 2,625
� x4 = (2,5 + 2,625)/2 = 2,5625
�� f(f(22,,55)) == --55,,1515..1010--33 << 00
�� f(f(22,,625625)) == 00,,10021002 >> 00
�� f(f(22,,56255625)) == 00,,04720472 >> 00
�� ξξξξξξξξ ∈∈∈∈ [[22,,55 ,, 22,,56255625]]
� a3 = a2 = 2,5
� b3 = x4 = 2,5625
15
Exemplo 7:
Considere-se f(x)f(x) == xx33 –– xx –– 11
Cálculo Numérico – Bissecção
y
3
4
Intervalo inicial atribuído: [1, 2] 
tol = 0,002
f(a0) = -1
x1 2 3 4 50-1-2-3-4
1
2
3
-4
-3
-2
-1
f(a0) = -1
f(b0) = 5
f’(x) = 3x2 – 1
f(a0) * f(b0) = -5 < 0
Sinal da derivada constante 
(f’(a0) = 2 e f’(b0) = 11)
16
Cálculo Numérico – Bissecção
� Cálculo da 1ª aproximação
� x1 = (a0 + b0)/ 2 = (1 + 2)/2 = 1,5
� f(x ) = 1,51,533 –– 1,5 1,5 –– 1 = 0,8751 = 0,875
Exemplo 7
� f(x1) = 1,51,5
33 –– 1,5 1,5 –– 1 = 0,8751 = 0,875
� Teste de Parada
● |f(x1)| =|0,875| = 0,875 > 0,002
� Escolha do novo intervalo
● f(a0).f(x1) = (-1).0,875 = -0,875
logo: a1 = a0 = 1,0 e b1 = x1 = 1,5
17
Cálculo Numérico – Bissecção
k ak bk f(ak) f(bk) xk+1 f(xk+1 )
0 1,0000000 2,0000000 -1,000000 5,000000 1,50000000 0,875000
1 1,0000000 1,5000000 -1,000000 0,875000 1,25000000 -0,296875
Exemplo 7
2 1,2500000 1,5000000 -0,296875 0,875000 1,37500000 0,224609
3 1,2500000 1,3750000 -0,296875 0,224609 1,31250000 -0,051514
4 1,3125000 1,3750000 -0,051514 0,224609 1,34375000 0,082611
5 1,3125000 1,3437500 -0,051514 0,082611 1,32812500 0,014576
6 1,3125000 1,3281250 -0,051514 0,014576 1,32031250 -0,018711
7 1,3203125 1,3281250 -0,018700 0,014576 1,32421875 -0,002128
tol = 0,002tol = 0,002
18
� Método da Falsa Posição
Dada uma função f(x)f(x) contínua no
intervalo [a,b][a,b] onde existe uma raiz única,
é possível determinar tal raiz a partir de
Cálculo Numérico – Falsa Posição
é possível determinar tal raiz a partir de
subdivisões sucessivas do intervalo que a
contém, substituindo f(x)f(x) no intervalo
[a,b][a,b] de cada iteração por uma reta e
tomando como aproximação da raiz a
intersecção da reta com o eixo das
abscissas.
19
� Método da Falsa Posição (MPF) vs
Método da Bissecção (MB)
MB: calcula a média aritmética entre
Cálculo Numérico – Falsa Posição
MB: calcula a média aritmética entre
a e b, e
MPF: calcula a média ponderada
entre a e b com pesos lf(b)l e lf(a)l,
respectivamente.
20
� MPF: calcula a média ponderada
entre a e b com pesos l(b)l e lf(a)l,
respectivamente.
Cálculo Numérico – Falsa Posição
� X = ( a lf(b)l + b lf(a)l ) / (lf(b)l + lf(a)l)
� = ( a f(b) - b f(a) ) / (f(b) - f(a))
� Observe que f(a) e f(b) têm sinais opostos.
21
� Definição do intervalo inicial
� Atribui-se [a,b] como intervalo inicial
● a0 = a
● b = b
Cálculo Numérico – Falsa Posição
● b0 = b
� Condições de aplicação
● f(a)*f(b) < 0
● Sinal da derivada constante
22
� Definição dos subintervalos
� Subdivide-se o intervalo pelo ponto de
intersecção da reta que liga f(a) a f(b) e o eixo
das abscissas
Cálculo Numérico – Falsa Posição
das abscissas
� Verifica-se se xx11 é uma aproximação da raiz da
equação (ξξξξ)
● Se verdadeiro ���� xx11 é a raiz procurada
● Caso contrário ���� define-se um novo intervalo
23
�Determina-se em qual dos subintervalos -
[a0, xx11] ou [xx11, b0] - se encontra a raiz ξξξξ
● Calcula-se o produto f(a)*f(xx11)
� Definição do novo intervalo
Cálculo Numérico – Falsa Posição
● Calcula-se o produto f(a)*f(xx11)
● Verifica-se se f(a)*f(xx11) < 0
� Se verdadeiro ���� ξξξξ ∈∈∈∈ (a0, x1)
Logo: a1 = a0 e b1 = x1
� Caso contrario ���� ξξξξ ∈∈∈∈ (x1, b0)
Logo a1 = x1 e b1 = b0)
�Repete-se o processo até que o valor de x atenda
às condições de parada.
24� Análise gráfica
f(x)
xx11 = (a|f(b)| + b|f(a)| )/ (|f(b)| + |f(a)|) = (a|f(b)| + b|f(a)| )/ (|f(b)| + |f(a)|) 
Cálculo Numérico – Falsa Posição
xa = a1
ξξξξξξξξ
f(x)
b1 = x1
xx22 = (a|f(x= (a|f(x11)| + x)| + x11|f(a)| )/ (|f(x|f(a)| )/ (|f(x11)| + |f(a)|) )| + |f(a)|) 
xx22
xa = a0 ξξξξξξξξ b = b0xx11
Repete-se o processo até que o
valor de x atenda às condições de
parada.
xa = a2
f(x)
b2 = x1
xx33 = (a|f(x= (a|f(x22)| + x)| + x22|f(a)| )/ (|f(x|f(a)| )/ (|f(x22)| + |f(a)|) )| + |f(a)|) 
xx22
ξξξξξξξξ
25
Cálculo Numérico – Falsa Posição
� Condições de parada
�Se os valores fossem exatos
● f(x) = 0
● (x – x )/x = 0● (xk– xk+1)/xk = 0
�Não o sendo
● |f(x)| ≤≤≤≤ tolerância
● |(xk– xk+1)/xk| ≤≤≤≤ tolerância
26
Algoritmo
k := 0; a0 := a; b0 := b; x0 := a; F0 := f(a0); G0 := f(b0);
xk+1 := ak - Fk(bk – ak)/(Gk – Fk); ou xk+1 := (akGk- bkFk)/(Gk – Fk);
while critério de convergência não satisfeito and k≤≤≤≤L
if f(ak)f(xk+1) ≤ 0 then /* raiz em [ak , xk+1] */
ak+1 := ak; bk+1 := xk+1;
Cálculo Numérico – Falsa Posição
ak+1 := ak; bk+1 := xk+1;
else /* raiz em [xk+1, bk] */
ak+1 := xk+1; bk+1 := bk ;
endif
k := k +1; xk+1 := ak - Fk(bk – ak)/(Gk – Fk);
endwhile
if k>L
convergência falhou
endif
27
1ª iteração
Utilizando o método da falsa posição e adotando
[[a0,, b0]] = [[22,, 33]] como intervalo inicial
Exemplo 8: Considerando f(x)f(x) == xxlogxlogx –– 11 (Exemplo 6)
Cálculo Numérico – Falsa Posição
1ª iteração
� a0 == 22 b0 == 33
f(f(a0)) == --00,,39793979 << 00
f(f(b0)) == 00,,43144314 >> 00
�x1 == [[22..00,,43144314 –– 33..((--00,,39793979)]/[)]/[00,,43144314 –– ((--00,,39793979)])] ==
== 22,,47984798
��f(f(x1)) == --00,,02190219 << 00
28
Exemplo 8:
2ª iteração
� a1 == x1 == 22,,47984798 b1 == b0 == 33
f(f(a1)) == --00,,02190219 << 00
Cálculo Numérico – Falsa Posição
f(f(a1)) == --00,,02190219 << 00
f(f(b1)) == 00,,43144314 >> 00
�x2 == [[22,,47984798..00,,43144314 –– 33..((--00,,02190219)]/[)]/[00,,43144314 –– ((--00,,02190219)])] ==
== 22,,50495049
��f(f(x2)) == --00,,00110011 << 00
29
Exemplo 8:
3ª iteração
� a2 == x2 == 22,,50495049 b1 == b0 == 33
f(f(a2)) == --00,,00110011 << 00
Cálculo Numérico – Falsa Posição
f(f(a2)) == --00,,00110011 << 00
f(f(b2)) == 00,,43144314 >> 00
�x3 == [[22,,50495049..00,,43144314 –– 33..((--00,,00110011)]/[)]/[00,,43144314 –– ((--00,,00110011)])] ==
== 22,,50615061
��f(f(x3)) == --77,,01180118..1010--55 << 00
30
Exemplo 9:
Resgatando a função do Exemplo 7, f(x)f(x) == xx33 –– xx –– 11
y
3
4
Intervalo inicial atribuído: [1, 2] 
tol = 0,002
f(a ) = -1
Cálculo Numérico – Falsa Posição
x1 2 3 4 50-1-2-3-4
1
2
3
-4
-3
-2
-1
f(a0) = -1
f(b0) = 5
f’(x) = 3x2 – 1
f(a0) * f(b0) = -5 < 0
Sinal da derivada constante 
(f’(a0) = 2 e f’(b0) = 11)
31
� Cálculo da 1ª aproximação
� x1 = [(a0.f(b0) - b0.f(a0)] / [f(b0) - f(a0)]
= [1.5 – 2.(-1)]/[5 – (-1)] = 1,166667
Exemplo 9
Cálculo Numérico – Falsa Posição
= [1.5 – 2.(-1)]/[5 – (-1)] = 1,166667
� f(x1) = 1,166667
3 – 1,166667 – 1 = -0,578703
� Teste de Parada
● |f(x1)| =|-0,578703| = 0,578703 > 0,002
� Escolha do novo intervalo
● f(a0).f(x1) = (-1).(-0,578703) = 0,578703
logo: a1 = x1 = 1,166667 e b1 = b0 = 2
32
k ak bk f(ak) f(bk) xk+1 f(xk+1 )
0 1,00000000 2,00000000 -1,00000000 5,00000000 1,16666667 -0,57870370
1 1,16666667 2,00000000 -0,57870370 5,00000000 1,25311203 -0,28536303
Exemplo 9
Cálculo Numérico – Falsa Posição
1 1,16666667 2,00000000 -0,57870370 5,00000000 1,25311203 -0,28536303
2 1,25311203 2,00000000 -0,28536303 5,00000000 1,29343740 -0,12954209
3 1,29343740 2,00000000 -0,12954209 5,00000000 1,31128102 -0,05658849
4 1,31128102 2,00000000 -0,05658849 5,00000000 1,31898850 -0,02430375
5 1,31898850 2,00000000 -0,02430375 5,00000000 1,32228272 -0,01036185
6 1,32228272 2,00000000 -0,01036185 5,00000000 1,32368429 -0,00440395
7 1,32368429 2,00000000 -0,00440395 5,00000000 1,32427946 -0,00186926
tol = 0,002tol = 0,002
33
� Método da Falsa Posição Modificado
Dada uma função f(x)f(x) contínua no
intervalo [a,b][a,b], o qual contém uma raiz
única, é possível determinar tal raiz a
Cálculo Numérico – Falsa Posição Modificado
única, é possível determinar tal raiz a
partir de subdivisões sucessivas do
intervalo que a contém, evitando, ao
mesmo tempo, que as aproximações
geradas pela fórmula de iteração se
aproximem da raiz por um único lado.
34
� Definição do intervalo inicial
� Atribui-se [a,b] como intervalo inicial
● a0 = a
● b = b
Cálculo Numérico – Falsa Posição Modificado
● b0 = b
� Condições de aplicação
● f(a)*f(b) < 0
● Sinal da derivada constante
35
� Definição dos subintervalos
� Subdivide-se o intervalo pelo ponto de
intersecção da reta que liga f(a) a f(b) e o eixo
das abscissas
Cálculo Numérico – Falsa Posição Modificado
das abscissas
� Verifica-se se xx11 é uma aproximação da raiz da
equação (ξξξξ)
● Se verdadeiro ���� xx11 é a raiz procurada
● Caso contrário ���� define-se um novo intervalo
36
�Determina-se em qual dos subintervalos -
[a0, x1] ou [x1, b0] - se encontra a raiz ξξξξ
● Calcula-se o produto f(a)*f(x1)
� Definição do novo intervalo
Cálculo Numérico – Falsa Posição Modificado
● Calcula-se o produto f(a)*f(x1)
● Verifica-se se f(a)*f(x1) < 0
� Se verdadeiro ���� ξξξξ ∈∈∈∈ (a0, x1)
Logo: a1 = a0 e b1 = x1
� Caso contrario ���� ξξξξ ∈∈∈∈ (x1, b0)
Logo a1 = x1 e b1 = b0)
�Repete-se o processo até que o valor de x atenda
às condições de parada.
37
� Análise gráfica
f(x)
xx11 = (a|f(b)| + b|f(a)| )/ (|f(b)| + |f(a)|) = (a|f(b)| + b|f(a)| )/ (|f(b)| + |f(a)|) 
xa = a1
ξξξξξξξξ
f(x)
b1 = x1
xx22 = (a|f(x= (a|f(x11)| + x)| + x11|f(a)| )/ (|f(x|f(a)| )/ (|f(x11)| + |f(a)|) )| + |f(a)|) 
xx22
Cálculo Numérico – Falsa Posição Modificado
xx22
xa = a0 ξξξξξξξξ b = b0xx11
Repete-se o processo até que o
valor de x atenda às condições de
parada.
f(a1)/2
38
� Condições de parada
�Se os valores fossem exatos
● f(x) = 0
● (x – x )/x = 0
Cálculo Numérico – Falsa Posição Modificado
● (xk– xk+1)/xk = 0
�Não o sendo
● |f(x)| ≤≤≤≤ tolerância
● |(xk– xk+1)/xk| ≤≤≤≤ tolerância
39
Algoritmo
k := 0; a0 := a; b0 := b; x0 := a; F0 := f(a0); G0 :=
f(b0);
xk+1 := ak - Fk(bk – ak)/(Gk – Fk);
while critério de convergência não satisfeito and k ≤≤≤≤ L
if f(ak)f(xk+1) ≤ 0 then /* raiz em [ak , xk+1] */
ak+1 := ak; bk+1 := xk+1; Gk+1= f(xk+1)
Cálculo Numérico – Falsa Posição Modificado
ak+1 := ak; bk+1 := xk+1; Gk+1= f(xk+1)
if f(xk)f(xk+1) > 0 then Fk+1= Fk/2
endif
else /* raiz em [xk+1, bk] */
ak+1 := xk+1; bk+1 := bk ; Fk+1= f(xk+1)
if f(xk)f(xk+1) > 0 then Gk+1= Gk/2
endif
endif
k := k +1; xk+1 := ak - Fk(bk – ak)/(Gk – Fk);
endwhile
if k ≤≤≤≤ L
xk+1 é uma aproximação aceitável para a raiz
endif
40
Cálculo Numérico – Ponto Fixo
� Método do Ponto Fixo (MPF)
Dada uma função f(x)f(x) contínua no intervalo
[a,b][a,b] onde existe uma raiz única, f(x)f(x) == 00, é[a,b][a,b] onde existe uma raiz única, f(x)f(x) == 00, é
possível transformar tal equação em uma
equação equivalente xx == g(x)g(x) e, a partir de
uma aproximação inicial xx00, gerar uma
seqüência {x{xkk}} de aproximações para ξξξξξξξξ
pela relação xxk+k+11 == g(xg(xkk)), uma vez que g(x)g(x)
é tal que f(f(ξξξξξξξξ)) == 00 se e somente se g(g(ξξξξξξξξ)) == ξξξξξξξξ.
41
Cálculo Numérico – Ponto Fixo
� Método do Ponto Fixo (MPF)
Implicação de tal procedimento:
Problema de determinação
de um zero de f(x)f(x)
Problema de determinação
de um ponto fixo de g(x)g(x)
função de 
iteração
42
Exemplo 9:
Seja aequação xx22 ++ xx –– 66 == 00 . Funções de
iteração possíveis:
� g (x) = 6 - x2
Cálculo Numérico – Ponto Fixo
� g1(x) = 6 - x
2
� g2(x) = ±√6 - x
� g3(x) = (6/x) – 1
� g4(x) = 6/(x + 1)
Dada uma equação do
tipo f(x) = 0, há para
tal equação mais de
uma função de
iteração g(x), tal que:
f(x) = 0⇔⇔⇔⇔ x = g(x)
43
� Análise gráfica da Convergência
y
g(x)g(x)
Cálculo Numérico – Ponto Fixo
y = xy = x Situação 1
x
{xk}→→→→ ξξξξ quando k→→→→ inf
ξξξξξξξξ x1 xx00x2
44
� Análise gráfica da Convergência
y
g(x)g(x)
Cálculo Numérico – Ponto Fixo
y = xy = x
Situação 2
x
{xk}→→→→ ξξξξ quando k→→→→ inf
ξξξξξξξξx1 xx00x2x3
45
� Análise gráfica da Convergência
y
g(x)g(x)
Cálculo Numérico – Ponto Fixo
y = xy = x
Situação 3
xξξξξξξξξ x1xx00 x2
{xk} ↑↑↑↑ ξξξξ
46
� Análise gráfica da Convergência
y g(x)g(x)
Cálculo Numérico – Ponto Fixo
y = xy = x Situação 4
xξξξξξξξξx1 xx00 x2
{xk} ↑↑↑↑ ξξξξ
x3
47
Exemplo 10:
Resgatando o Exemplo 9, no qual xx22 ++ xx –– 66 == 00 :
� Não há necessidade de uso de método numérico
para a determinação das raízes ξξξξξξξξ11 == --33 ee ξξξξξξξξ22 == 22
Cálculo Numérico – Ponto Fixo
para a determinação das raízes ξξξξξξξξ11 == --33 ee ξξξξξξξξ22 == 22
� Aproveitamento do Exemplo 9 puramente para
demonstração numérica e gráfica da convergência
ou não do processo iterativo
� Seja a raiz ξξξξξξξξ22 == 22 ee gg11 (x)(x) == 66 -- xx22
� Considere-se xx00== 11,,55 ee g(x)g(x) == gg11 (x)(x)
48
Exemplo 10:
A partir de xx00 == 11,,55 ee g(x)g(x) == gg11 (x)(x) :
�� xx11 == g(xg(x00)) == 66 –– 11,,55
22== 33,,7575
Cálculo Numérico – Ponto Fixo
xx == g(xg(x )) == 66 –– 33,,757522== --88,,06250625�� xx22 == g(xg(x11)) == 66 –– 33,,7575
22== --88,,06250625
�� xx33 == g(xg(x22)) == 66 –– ((--88,,06250625))
22== --5959,,003906003906
� Conclui-se que {xxkk}} nãonão convergiráconvergirá parapara ξξξξξξξξ22 == 22
�� xx44 == g(xg(x33)) == 66 –– ((--5959,,003906003906))
22== --34753475,,46094609
49
Exemplo 10:
Análise Gráfica:
Cálculo Numérico – Ponto Fixo
y y = xy = x
xξξξξ2ξξξξ2 x1
g(x)g(x)
xx00
{xk} ↑↑↑↑ ξξξξ2
x2 ξξξξ1ξξξξ1
50
Exemplo 10:
Seja ainda a raiz ξξξξξξξξ22 == 22,, gg22 (x)(x) == √66 -- xx e xx00 == 11,,55
�� xx11 == g(xg(x00)) == √66 –– 11,,55== 22,,121320343121320343
Cálculo Numérico – Ponto Fixo
xx == g(xg(x )) == √66 –– 22,,121320343121320343 == 11,,969436380969436380�� xx22 == g(xg(x11)) == √66 –– 22,,121320343121320343 == 11,,969436380969436380
�� xx33 == g(xg(x22)) == √66 –– 11,,969436380969436380 == 22,,007626364007626364
� Conclui-se que {xxkk}} tendetende aa convergirconvergir parapara ξξξξξξξξ22 == 22
�� xx44 == g(xg(x33)) == √66 –– 22,,007626364007626364 == 11,,998092499998092499
�� xx55 == g(xg(x44)) == √66 –– 11,,998092499998092499 == 22,,000476818000476818
51
Exemplo 10: Análise Gráfica
Cálculo Numérico – Ponto Fixo
g(x)g(x)
y
y = xy = x
xξξξξ2ξξξξ2
x1
xx00
x2 {xk} →→→→ ξξξξ2 quando k →→→→ inf
52
Cálculo Numérico – Ponto Fixo
� TEOREMA 2:
Sendo ξξξξ uma raiz de f(x) = 0, isolada em um
intervalo I centrado em ξξξξ e g(x) uma função
de iteração para f(x) = 0. Se
1. g(x) e g’(x) são contínuas em I
2. |g’(x)| ≤≤≤≤ M < 1, ∀∀∀∀ x ∈∈∈∈ I e
3. x1∈∈∈∈ I
então a seqüência {xk} gerada pelo processo
iterativo xk+1 = g(xk) convergirá para ξξξξ .
53
Exemplo 11:
Resgatando o Exemplo 10, verificou-se que:
g1 (x)���� geração de uma seqüência divergente de ξξξξ2=2
g (x)���� geração de uma seqüência convergente p/ ξξξξ =2
Cálculo Numérico – Ponto Fixo
g2 (x)���� geração de uma seqüência convergente p/ ξξξξ2=2
� g1 (x) = 6 - x
2 e g’1 (x) = - 2x ���� contínuas em I
� |g’1 (x)|< 1 ⇔⇔⇔⇔ |-2x|< 1⇔⇔⇔⇔ -½ < x< ½
� Não existe um intervalo I centrado em ξξξξ2=2, tal
que |g’(x)|< 1, ∀∀∀∀ x ∈∈∈∈ I ���� g1 (x) não satisfaz a
condição 2 do Teorema 2 com relação a ξξξξ2=2 .
54
Exemplo 11:
Cálculo Numérico – Ponto Fixo
� g2 (x) = √ 6 - x e g’2 (x) = - (1/2 )√ 6 - x
���� g2 (x) é contínua em S = {x ∈∈∈∈ R | x ≤≤≤≤ 6}
g’2 (x) é contínua em S’ = {x ∈∈∈∈ R | x < 6}g’2 (x) é contínua em S’ = {x ∈∈∈∈ R | x < 6}
� |g’2 (x)|< 1⇔⇔⇔⇔ |1/2 √ 6 - x |< 1⇔⇔⇔⇔ x< 5,75
� É possível obter um intervalo I centrado em ξξξξ2=2,
tal que todas as condições do Teorema 2 sejam
satisfeitas.
55
� Critérios de parada
�Se os valores fossem exatos
● f(xk) = 0
● |x – x |= 0
Cálculo Numérico – Ponto Fixo
● |xk– xk-1|= 0
�Não o sendo
● |f(xk)| ≤≤≤≤ tolerância
● |xk– xk-1| ≤≤≤≤ tolerância
56
� Algoritmo
k := 0; x0 := x;
while critério de interrupção não satisfeito and k ≤≤≤≤ L
k := k +1;
Cálculo Numérico – Ponto Fixo
k := k +1;
xk+1 := g(xk);
endwhile
57
� Algoritmo Completo
(1) Seja f(x)= 0 e a equação Equivalente x=g(x)
Dados: x0 (aprox. inicial) e εεεε1 e εεεε2 (precisões)
Supor que as hipóteses do Teorema 2 foram satisfeitas
(2) Se: lf(x0)l < εεεε1, Então: x´= x0. FIM
Cálculo Numérico – Ponto Fixo
(2) Se: lf(x0)l < εεεε1, Então: x´= x0. FIM
(3) Senão: k = 0; NI = 1;
(4) xk+1 = g(xk);
(5) Se ( lf(xk+1)l < εεεε1 ou l xk+1 – xk l < εεεε2 ou NI >L )
Então x´= xk+1. FIM
(6) Xk=xk+1 ; NI = NI+1
Volta para (4)
X´= raiz aproximada
(NI = No. de iterações)
58
� Método de Newton-Raphson
Dada uma função f(x)f(x) contínua no
intervalo [a,b][a,b] onde existe uma raiz única,
é possível determinar uma aproximação de
Cálculo Numérico – Newton-Raphson
é possível determinar uma aproximação de
tal raiz a partir da interseção da tangente
à curva em um ponto xx00 com o eixo das
abscissas.
xx00 - atribuído em função da geometria do método
e do comportamento da curva da equação nas
proximidades da raiz.
59
� Considerações Iniciais
� Método do Ponto Fixo (MPF)
● Uma das condições de convergência é que
|g’(x)| ≤≤≤≤ M < 1, ∀∀∀∀ x ∈∈∈∈ I , onde I é um intervalo
centrado na raiz
Cálculo Numérico – Newton-Raphson
|g’(x)| ≤≤≤≤ M < 1, ∀∀∀∀ x ∈∈∈∈ I , onde I é um intervalo
centrado na raiz
● A convergência será tanto mais rápida quanto
menor for |g’(x)|
� O método de Newton busca garantir e acelerar a
convergência do MPF
● Escolha de g(x), tal que g’(ξξξξ) = 0, como função
de iteração
60
� Considerações Iniciais
� Dada a equação f(x) = 0 e partindo da forma
geral para g(x)
g(x) = x + A(x)f(x)
Cálculo Numérico – Newton-Raphson
g(x) = x + A(x)f(x)
busca-se obter a função A(x) tal que g’(ξξξξ) = 0
� g(x) = x + A(x)f(x)⇒⇒⇒⇒
g’(x) = 1 + A’(x)f(x) + A(x)f’(x) ⇒⇒⇒⇒
g’(ξξξξ) = 1 + A’(ξξξξ)f(ξξξξ) + A(ξξξξ)f’(ξξξξ)⇒⇒⇒⇒
g’(ξξξξ) = 1 + A(ξξξξ)f’(ξξξξ)
61
� Considerações Iniciais
� Assim
g’(ξξξξ) = 0⇔⇔⇔⇔ 1 + A(ξξξξ)f’(ξξξξ) = 0⇔⇔⇔⇔ A(ξξξξ) = -1/f’(ξξξξ)
donde se toma A(x) = -1/f’(x)
Cálculo Numérico – Newton-Raphson
donde se toma A(x) = -1/f’(x)
� Então, dada f(x), a função de iteração
g(x) = x - f(x)/f’(x) será tal que g’(ξξξξ) = 0, posto
que
g’(x) = 1 – {[f’(x)]2 – f(x)f”(x)}/[f’(x)]2
e, como f(ξξξξ) = 0, g’(ξξξξ) = 0 (desde que f’(ξξξξ) ≠≠≠≠ 0 )
62
� Considerações Iniciais
� Deste modo, escolhido x0 , a seqüência {xk}
será determinada por
Cálculo Numérico – Newton-Raphson
xk+1 = xk – f(xk)/f’(xk)
onde k = 0, 1, 2, ...
63
� Motivação Geométrica
� Dado o ponto (xk , f(xk))
● Traça-se a reta Lk(x) tangente à curva neste
ponto:
Cálculo Numérico – Newton-Raphson
ponto:
Lk(x) = f(xk) + f’(xk)(x-xk)
● Determina-se o zero de Lk(x), um modelo linear
que aproxima f(x) em uma vizinhança xk
Lk(x) = 0 ⇔⇔⇔⇔ x = xk - f(xk)/f’(xk)
● Faz-se xk +1 = x
64
� Análise Gráfica
Cálculo Numérico – Newton-Raphson
f(x)
x
ξξξξξξξξ
x1xx00
x2
x3
1a iteração
2a iteração
3a iteração
4a iteração
Repete-seo processo até que
o valor de x atenda às
condições de parada.
65
Exemplo 12:
Resgatando o Exemplo 9, no qual xx22 ++ xx –– 66 == 00 :
� Seja a raiz ξξξξξξξξ22 == 22 ee xx00 == 11,,55
� Assim:
Cálculo Numérico – Newton-Raphson
� Assim:
�� xx11 == g(xg(x00)) == 11,,55 –– ((11,,55
22++ 11,,55 –– 66)/()/(22..11,,55 ++ 11)) ==
== 22,,062500000062500000
�� xx22 == g(xg(x11)) == 22,,000762195000762195
�� xx33 == g(xg(x22)) == 22,,000000116000000116
�� g(x)g(x) == xx -- f(x)/f’(x)f(x)/f’(x) == xx –– (x(x 22++ xx –– 66)/()/(22xx ++ 11))
ee
66
Exemplo 12:
Comentários:
� A parada poderá ocorrer na 3a iteração
(xx == 22,,000000116000000116), caso a precisão do cálculo
com 6 casas decimais for satisfatória para o
Cálculo Numérico – Newton-Raphson
com 6 casas decimais for satisfatória para o
contexto do trabalho
� Observe-se que no Exemplo 10, o MPF com
g(x) = √6 - x só veio a produzir
x = 2,000476818 na 5a iteração
67
� Estudo da Convergência
TEOREMA 3:
Sendo f(x), f’(x) e f”(x) contínuas em um
intervalo I que contém uma raiz x = ξξξξ de
Cálculo Numérico – Newton-Raphson
intervalo I que contém uma raiz x = ξξξξ de
f(x) = 0 e supondo f’(ξξξξ) ≠≠≠≠ 0, existirá um
intervalo Ī ⊆⊆⊆⊆ I contendo a raiz ξξξξ, tal que se
x0 ∈∈∈∈ Ī , a seqüência {xk} gerada pela
fórmula recursiva
xk+1= xk - f(xk)/f’(xk)
convergirá para a raiz.
68
Exemplo 13:
Considere-se a função f(x) = xx33 -- 99xx ++ 33 , cujos
zeros encontram-se nos intervalos:
Cálculo Numérico – Newton-Raphson
ξξξξ1∈∈∈∈ I1 = (-4, -3), ξξξξ2∈∈∈∈ I2 = (0, 1) e ξξξξ3∈∈∈∈ I3 = (2, 3)
� Seja x0 = 1,5
� xk+1 = xk - f(xk)/f’(xk)
� e g(x) = x – (xx3 -- 99x + 3x + 3)/(3xx2 –– 9)9)
69
Exemplo 13:
A seqüência {x{xk}} gerada pelo método de Newton será:
Cálculo Numérico – Newton-Raphson
f(x)
13,37037028
x
-1,66666667
Iteração
1 13,37037028-1,66666667
18,38888989
12,36601106
8,40230714
5,83533843
4,23387371
3,32291104
2,91733895
2,82219167
2,81692988
1
2
3
4
5
6
7
8
9
10
6055,72648668
1782,69441818
520,57174528
149,18208182
40,79022981
9,78451301
1,57303193
0,07837072
0,00023432
70
Exemplo 13:
Comentários:
� Constata-se nas primeiras iterações uma
divergência da região em que se encontram as
raízes, a qual é revertida a partir da 7a iteração
Cálculo Numérico – Newton-Raphson
raízes, a qual é revertida a partir da 7a iteração
� Tal divergência inicial deve-se à proximidade de x0
de √3 , que é um zero de f’(x). Tal proximidade
inicial gera x1 = -1,66666667 ≈ -√3, outro zero
de f’(x).
71
� Cálculo das aproximações
� As aproximações subseqüentes serão
determinadas a partir da equação
Cálculo Numérico – Newton-Raphson
|(f(x0).f”(x0))/f’(x0) 
2)|= 
|(f(xk).f’(xk+1))/f’(x0)
2)|
onde xk+1 = xk – (f(xk)/f’(xk+1))
72
� Testes de Parada
� A cada iteração, testa-se se a aproximação
encontrada poderá ser considerada como a
solução do problema.
Cálculo Numérico – Newton-Raphson
solução do problema.
● |f(xk)| ≤≤≤≤ tolerância
● |((xk+1 – xk)/xk+1 )| ≤≤≤≤ tolerância
73
� Algoritmo
k := 0; x0 := x;
while critério de interrupção não satisfeito and k ≤≤≤≤ L
k := k +1;
Cálculo Numérico – Newton-Raphson
k := k +1;
xk+1 := xk – f(xk)/f’(xk)
endwhile
74
� Método da Secante
Dada uma função f(x)f(x) contínua no
intervalo [a,b][a,b] onde existe uma raiz única,
Cálculo Numérico – Secante
é possível determinar uma aproximação de
tal raiz a partir da interseção da secante à
curva em dois pontos xx00 e xx11 com o eixo
das abscissas.
xx00 e xx11 - atribuídos em função da geometria do
método e do comportamento da curva da equação
nas proximidades da raiz.
75
� Considerações Iniciais
� Método de Newton-Raphson
● Um grande inconveniente é a necessidade
da obtenção de f’(x) e o cálculo de seu valor
numérico a cada iteração
Cálculo Numérico – Secante
numérico a cada iteração
� Forma de desvio do inconveniente
● Substituição da derivada f’(xk) pelo
quociente das diferenças
f’(xk) ≈ [f(xk) - f(xk-1)]/(xk - xk-1)
onde xk-1 e xk são duas aproximações para a
raiz
76
� Considerações Iniciais
� A função de iteração será
g(x) = xk - f(xk)/[(f(xk) - f(xk-1))/(xk - xk-1)]
Cálculo Numérico – Secante
k k k k-1 k k-1
= (xk - xk-1) . f(xk)/[f(xk) - f(xk-1)]
= [xk-1 .f(xk) – xk . f(xk-1)]/[f(xk) - f(xk-1)]
g(x) = [xk-1 .f(xk) – xk . f(xk-1)]/[f(xk) - f(xk-1)]g(x) = [xk-1 .f(xk) – xk . f(xk-1)]/[f(xk) - f(xk-1)]
77
� Interpretação Geométrica
Cálculo Numérico – Secante
� A partir de duas aproximações xk-1 e xk
● Obtém-se o ponto xk+1 como sendo ak+1
abscissa do ponto de intersecção do eixo ox
e da reta que passa pelos pontos
(xk-1, f(xk-1)) s (xk, f(xk)) (secante à curva
da função)
78
� Análise Gráfica
f(x)
Cálculo Numérico – Secante
xξξξξξξξξx1xx00 x2
x3
1a iteração
2a iteração
3a iteração
4a iteração
Repete-se o processo até que
o valor de x atenda às
condições de parada.
x4
x5
79
Exemplo 12:
Resgatando o Exemplo 9, no qual xx22 ++ xx –– 66 == 00 :
� Sejam xx00 == 11,,55 ee xx11 == 11,,77
� Assim:
Cálculo Numérico – Secante
� x3 = [x1 .f(x2) – x2 . f(x1)]/[f(x2) - f(x1)]
= 1,99774
� x2 = [x0 .f(x1) – x1 . f(x0)]/[f(x1) - f(x0)]
= [1,5.(-1,41) – 1,7.(-2,25)]/(-1,41 + 2,25)
= 2,03571
� x4 = [x2 .f(x3) – x3 . f(x2)]/[f(x3) - f(x2)]
= 1,99999
80
� Testes de Parada
� A cada iteração, testa-se se a aproximação
encontrada poderá ser considerada como a
solução do problema.
Cálculo Numérico – Newton-Raphson
solução do problema.
● |f(xk)| ≤≤≤≤ tolerância
● |((xk+1 – xk)/xk+1 )| ≤≤≤≤ tolerância
81
� Algoritmo
k := 0; x0 := X0; x1 := X1
while critério de interrupção não satisfeito and k ≤≤≤≤ L
k := k +1;
Cálculo Numérico – Newton-Raphson
k := k +1;
xk+1 := (xk-1*f(xk) - xk*f(xk-1))/(f(xk) - f(xk-1))
endwhile