MetodoSecante

Esta é uma pré-visualização de arquivo. Entre para ver o arquivo original

Cálculo Numérico
Prof. Aparecido J. de Souza
aparecidosouza@ci.ufpb.br
Método da Secante.
Comparações entre os vários métodos.
Preliminares.
Hipótese. Seja f : [a,b]⊂ R→ R contínua tal que a equação
f (x) = 0 possua uma única raíz x = ξ em (a,b), e também
com f ′ e f ′′ contínuas em [a,b] e f ′(x) 6= 0, ∀x ∈ [a,b].
Lembrete: A sequência de iteradas no método de
Newton-Raphson para aproximar a raiz ξ de f (x) = 0 é
xk+1 = xk − f (xk )f ′(xk ) , k = 0,1,2, · · · .
Ideia. Modificar a fórmula acima de tal forma a evitar o cálculo
da derivada f ′(xk ) a cada iteração e o método não ficar tão
custoso computacionalmente.
Procedimento 1: Trocar f ′(xk ) por f ′(x0) e assim calcular a
derivada uma única vez.
Procedimento 2: Trocar f ′(xk ) (a inclinação da reta tangente
no ponto (xk , f (xk )) pela inclinação da reta secante pelos
pontos (xk−1, f (xk−1)) e (xk , f (xk )).
Método da Secante.
Lembrete: A sequência de iteradas no método de
Newton-Raphson para aproximar a raiz ξ de f (x) = 0 é
xk+1 = xk − f (xk )f ′(xk ) , k = 0,1,2, · · · .
Procedimento 1: Trocar f ′(xk ) por f ′(x0) e assim calcular a
derivada uma única vez.
Procedimento 2: Trocar f ′(xk ) (a inclinação da reta tangente
no ponto (xk , f (xk )) pela inclinação da reta secante pelos
pontos (xk−1, f (xk−1)) e (xk , f (xk )).
Consequencias: Melhora o custo computacional. Baixa a
ordem de convergência (quadrática) para uma ordem de
convergência ainda acima da linear (superlinear).
Método da Secante.
Lembrete: A sequência de iteradas no método de
Newton-Raphson para aproximar a raiz ξ de f (x) = 0 é
xk+1 = xk − f (xk )f ′(xk ) , k = 0,1,2, · · · .
Procedimento 2: Troca da inclinação da derivada em xk pela
inclinação da secante por (xk−1, f (xk−1)) e (xk , f (xk )).
f ′(xk )≈ f (xk )− f (xk−1)xk −xk−1 .
Substituindo esta última expressão na fórmula das iteradas
obtemos o Método da Secante dado por
xk+1 = xk − f (xk ) (xk −xk−1)f (xk )− f (xk−1) =
xk−1f (xk )−xk f (xk−1)
f (xk )− f (xk−1) .
Resumo
Método de Newton-Raphson: Dado x0,
xk+1 = xk − f (xk )f ′(xk ) , k = 0,1,2, . . . .
Método da secante: Dados x0 e x1,
xk+1 =
xk−1 f (xk ) − xk f (xk−1)
f (xk )− f (xk−1) , k = 1,2, . . . .
O método da secante é de passo-2: São necessárias duas
aproximações iniciais x0 e x1 para começar as iterações.
O método de Newton-Raphson, assim como os MPFs em
geral, é de de passo-1: É necessário apenas a aproximação
inicial x0 para começar as iterações.
Os métodos da bisseção e da posição falsa são
autoinicializáveis, não sendo necessário fornecer
aproximações iniciais.
O Método da Secante
Conhecidos xk−1 e xk :
xk+1 =
xk−1 f (xk ) − xk f (xk−1)
f (xk )− f (xk−1) , k = 1,2, . . . .
Ordem de convergência?
Ordem menor do que a de Newton-Raphson e superior ao da
bisseção: p = (1 +
√
5)/2≈ 1.618... (número de ouro). É
superlinear, mas não quadrática.
Fórmula do erro:
|ek+1| ≤
maxx∈[a,b] |f ′′(x)|
2minx∈[a,b]|f ′(x)|
|ek | |ek−1| .
Ver Conte, S. D. & Boor, C.; Elementary Numerical Analysis, an
Algorithmic Approach, 3a Edt., McGraw-Hill, 1981.
O Método da Secante.
Método da secante: Conhecidos xk−1 e xk :
xk+1 = ϕ(xk−1,xk )≡ xk−1 f (xk ) − xk f (xk−1)f (xk )− f (xk−1) , k = 1,2, . . . .
Exemplo 1(a). Determine uma aproximação do zero da função
f (x) = x3−9x + 3 localizada no intervalo [−5,−3], com
precisão até a terceira casa decimal, via Erro Absoluto em x .
Newton-Raphson com x0 =−4 =⇒ x¯ = x4 =
−3.1545, |EA4|= 0.00012373, f (x¯) =−0.000000...
Aproximações iniciais para o Método da Secante:
x0 =−4, f0 =−25; x1 =−3.5, f1 =−8.3750 (bisseção).
Iterações:
x2 = ϕ(x0,x1) =−3.2481, |EA2|= 0.2519, f2 =−2.0355
x3 = ϕ(x1,x2) =−3.1672, |EA3|= 0.0809, f3 =−0.2668
x4 = ϕ(x2,x3) =−3.1550, |EA4|= 0.0122, f4 =−0.0109
x5 = ϕ(x3,x4) =−3.1545, |EA5|= 0.00051809, f5 =
−0.0000... Quatro Iterações.
O Método da Secante.
Método da secante: Conhecidos xk−1 e xk :
xk+1 = ϕ(xk−1,xk )≡ xk−1 f (xk ) − xk f (xk−1)f (xk )− f (xk−1) , k = 1,2, . . . .
Exemplo 1(b). Determine uma aproximação do zero da função
f (x) = x3−9x + 3 localizada no intervalo [0, 1], com precisão
até a terceira casa decimal, via Erro Absoluto em x .
Newton-Raphson com x0 = 0.5
=⇒ x¯ = x3 = 0.3376, |EA3| ≈ 0.0000002, f (x¯)≈ 0.0000...
Aproximações iniciais para o Método da Secante:
x0 = 0.5, f0 =−1.3750, x1 = 0.25, f1 =−3.3281 (bisseção).
Iterações:
x2 = ϕ(x0,x1) = 0.3240, |EA2|= 0.4260, f2 = 0.1180
x3 = ϕ(x1,x2) = 0.3386, |EA3|= 0.0146, f3 =−0.0085
x4 =ϕ(x2,x3) = 0.3376, |EA4|= 0.00097778, f4 =−0.0000...
Três Iterações.
O Método da Secante.
Método da secante: Conhecidos xk−1 e xk :
xk+1 = ϕ(xk−1,xk )≡ xk−1 f (xk ) − xk f (xk−1)f (xk )− f (xk−1) , k = 1,2, . . . .
Exemplo 1(c). Determine uma aproximação do zero da função
f (x) = x3−9x + 3 localizada no intervalo [2, 3], com precisão
até a terceira casa decimal, via Erro Absoluto em x .
Newton-Raphson com x0 = 2.5
=⇒ x¯ = x4 = 2.8169, |EA4|= 0.00000.., f (x¯)≈ 0.0000...
Aproximações iniciais para o Método da Secante:
x0 = 2.5, f0 =−3.8750, x1 = 2.75, f1 =−0.9531 (bisseção).
Iterações:
x2 = ϕ(x0,x1) = 2.8316, |EA2|= 0.0816, f2 = 0.2185
x3 = ϕ(x1,x2) = 2.8163, |EA3|= 0.0152, f3 =−0.0085
x4 = ϕ(x2,x3) = 2.8169, |EA4|= 0.00056778, f4 =
−0.000007...
Três Iterações.
O Método da Secante.
Método da secante: Conhecidos xk−1 e xk :
xk+1 = ϕ(xk−1,xk )≡ xk−1 f (xk ) − xk f (xk−1)f (xk )− f (xk−1) , k = 1,2, . . . .
Exemplo 2. Determine uma aproximação do zero da função
f (x) = x2−sen(x) localizada no intervalo [1, 5], com precisão
até a terceira casa decimal, via Erro Absoluto em x .
Método de Newton-Raphson com x0 = 3.0
=⇒ x¯ = x6 = 0.8767, |EA5|= 0.00002683, f (x¯)≈ 0.0000...
Método da Secante com
x0 = 3.0, f0 = 8.8589, x1 = 2, f1 = 3.0907 (arbitrário).
=⇒ x¯= x7 = 0.8767, |EA7|= 0.000068553, f (x¯)≈ 0.0000...
Comparações entre os vários métodos numéricos.
Parâmetros de Comparação.
• Garantia de Convergência,
• Ordem de convergência (número de iterações),
• Custo Computacional (tempo de execução).
Convergência.
• Os métodos da Bisseção e o da Posição Falsa tem
convergência garantida desde que f seja contínua em
[a,b] e f (a)× f (b) < 0.
• O métodos MPF, Newton-Raphson e Secante tem
convergência garantida, desde que haja restrições
adicionais envolvendo as derivadas de até segunda ordem
da função f .
Comparações entre os vários métodos numéricos.
Ordem de Convergência.
• O método da Bisseção tem convergência lenta. Depende
do comprimento de [a,b]. Quanto maior for [a,b]
comparado com a tolerância TOL, maior será o número de
iterações.
• O método da Posição Falsa
xk =
ak |f (bk )|+ bk |f (ak )|
|f (bk )|+ |f (ak )| ,
também tem convergência lenta, principalmente de |f (ak )|
for grande em comparação com |f (bk )| ou vice-versa, pois
estes são pesos na fórmula das iteradas.
• Os métodos MPFs em geral têm pelo menos Ordem de
Convergência Linear. O erro decresce linearmente a cada
iterada: |Ek+1| ≈ C|Ek |, com 0 < C < 1.
Comparações entre os vários métodos numéricos.
Ordem de Convergência.
• O método de Newton-Raphson
xk+1 = xk − f (xk )f ′(xk ) , k = 0,1,2, . . .
tem Ordem de Convergência quadrática. O erro decresce
quadraticamente a cada iterada: |Ek+1| ≈ C|Ek |2 ( o
número de zeros após a vírgula geralmente duplica a cada
iteração).
Se |f ′(xk )| for muito pequeno pode ocorrer overflow.
Comparações entre os vários métodos numéricos.
Ordem de Convergência.
• O método da Secante
xk+1 =
xk−1 f (xk ) − xk f (xk−1)
f (xk )− f (xk−1) , k = 1,2, . . .
tem Ordem de Convergência superlinear, isto é, é melhor
do que convergência linear dos MPFs em geral e pior do
que a convergência quadrática do método de Newton.
Se f (xk ) for próximo de f (xk−1) pode ocorrer overflow
porque o denominador pode ser muito pequeno.
Comparações entre os vários métodos numéricos.
Custo Computacional (tempo de execução).
Este item está relacionado com o número de operações
efetuadas a cada iteração, da complexidade destas operações,
do número de decisões lógicas, do número de avaliações de
funções externas a cada iteração e do número total de
iterações.
• O método da Bisseção realiza cálculo bastante simples a
cada iteração, por isto tem menor custo computacional.
• Os métodos da Posição Falsa e o da Secante realizam um
pouco mais de cálculo do que o método da bisseção em
cada iteração, por ter que calcular as inclinações das
secantes.
• O método de Newton-Raphson realiza operações mais
sofisticadas a cada iteração e depende também da
avaliação de duas funções externas ( f (xk ) e f ′(xk )). Por
isto tem maior custo computacional.
Exemplo 3. (Ex. 18, Ruggiero, pg 79).
f (x) = e−x2−cos(x), ξ ∈ (1,2), min{|EAx¯ |, |f (x¯)|}< 10−4.
Exemplo 3. (Ex. 18, Ruggiero, pg 79).
f (x) = e−x2−cos(x), ξ ∈ (1,2), min{|EAx¯ |, |f (x¯)|}< 10−4.
f ′(x) =−2x e−x2 + sen(x) 6= 0.
Exemplo 3. (Ex. 18, Ruggiero, pg 79).
f (x) = e−x2−cos(x), ξ ∈ (1,2), min{|EAx¯ |, |f (x¯)|}< 10−4.
MPF: ϕ(x) = x−e−x2 + cos(x).
ϕ ′(x) = 1 + 2xe−x2−sen(x) (|ϕ ′(x)|< 1).
Exemplo 3. (Ex. 18, Ruggiero, pg 79).
f (x) = e−x2−cos(x), ξ ∈ (1,2), min{|EAx¯ |, |f (x¯)|}< 10−4.
Bisseção.
x¯ = 1.44741821 f (x¯) = 2.1921×10−5
|EAx |= 6.1035×10−5 14 Iterações.
P. Falsa.
x¯ = 1.44735707 f (x¯) =−3.6387×10−5
|EAx |= .552885221 4 Iterações.
MPF com ϕ(x) = x−e−x2 + cos(x) e x0 = 1.5
x¯ = 1.44752471 f (x¯) = 7.0258×10−5
|EAx |= 1.9319×10−4 6 Iterações.
Newton-Raphson com x0 = 1.5.
x¯ = 1.44741635 f (x¯) = 1.3205×10−6
|EAx |= 1.7072×10−3 2 Iterações.
Secante com x0 = 1, x1 = 2.
x¯ = 1.44741345 f (x¯) =−5.2395×10−7
|EAx |= 1.8553×10−4 5 Iterações.
Exemplo 4. (Ex. 19, Ruggiero, pg 79).
f (x) = x3−x −1, ξ ∈ (0,2), min{|EAx¯ |, |f (x¯)|}< 10−6.
Exemplo 3. (Ex. 19, Ruggiero, pg 79).
f (x) = x3−x −1, ξ ∈ (0,2), min{|EAx¯ |, |f (x¯)|}< 10−6.
f ′(x) = 3x2−1 (se anula para x ≈ 0.6).
Exemplo 3. (Ex. 19, Ruggiero, pg 79).
f (x) = x3−x −1, ξ ∈ (0,2), min{|EAx¯ |, |f (x¯)|}< 10−6.
MPF: Função de iteração ϕ(x) = (x + 1)1/3.
ϕ ′(x) = 13(x + 1)
−2/3 (|ϕ ′(x)|< 1).
Exemplo 3. (Ex. 19, Ruggiero, pg 79).
f (x) = x3−x −1, ξ ∈ (0,2), min{|EAx¯ |, |f (x¯)|}< 10−6.
Bisseção (no intervalo (1,2)).
x¯ = 0.1324718×101 f (x¯) =−0.1847744×10−5
|EAx |= 0.9536743×10−6 20 Iterações.
P. Falsa (no intervalo (1,2)).
x¯ = 0.1324718×101 f (x¯) =−0.7897615×10−6
|EAx |= 0.6752825 17 Iterações.
MPF com ϕ(x) = (x + 1)1/3 e x0 = 1.
x¯ = 0.1324717×101 f (x¯) =−0.52154406×10−6
|EAx |= 0.3599538×10−6 9 Iterações.
Newton-Raphson com x0 = 0.
x¯ = 0.1324718×101 f (x¯) = 0.1821000×10−6
|EAx |= 0.6299186×10−6 21 Iterações., f′(0.6)≈ 0.
Secante com x0 = 0, x1 = 0.5.
x¯ = 0.1324718×101 f (x¯) =−0.8940697×10−7
|EAx |= 0.8998843×10−5 27 Iterações, f′(0.6)≈ 0.
Exemplo 4. (Ex. 20, Ruggiero, pg 80).
f (x) = 4sen(x)−ex , ξ ∈ (0,1), min{|EAx¯ |, |f (x¯)|}< 10−5.
Exemplo 4. (Ex. 20, Ruggiero, pg 80).
f (x) = 4sen(x)−ex , ξ ∈ (0,1), min{|EAx¯ |, |f (x¯)|}< 10−5.
f ′(x) = 4cos(x)−ex (se anula para x ≈ 0.9).
Exemplo 4. (Ex. 20, Ruggiero, pg 80).
f (x) = 4sen(x)−ex , ξ ∈ (0,1), min{|EAx¯ |, |f (x¯)|}< 10−5.
MPF: Função de iteração ϕ(x) = x−2sen(x) + 12ex .
ϕ ′(x) = 1−2cos(x) + 12ex (|ϕ ′(x)|> 1, se x ≥ 0.9).
Exemplo 4. (Ex. 20, Ruggiero, pg 80).
f (x) = 4sen(x)−ex , ξ ∈ (0,1), min{|EAx¯ |, |f (x¯)|}< 10−5.
Bisseção.
x¯ = 0.370555878 f (x¯) =−1.3755×10−5
|EAx |= 7.6394×10−6 17 Iterações.
P. Falsa.
x¯ = 0.370558828 f (x¯) = 1.6695×10−6
|EAx |= 0.370562817 8 Iterações.
MPF com ϕ(x) = x−2sen(x) + 0.5ex e x0 = 0.5.
x¯ = 0.370556114 f (x¯) =−4.5191×10−6
|EAx |= 1.1528×10−4 5 Iterações.
Newton-Raphson com x0 = 0.5.
x¯ = 0.37058084 f (x¯) =−2.7632×10−8
|EAx |= 1.3863×10−4 3 Iterações.
Secante com x0 = 0, x1 = 1.
x¯ = 0.370558098 f (x¯) = 5.8100×10−9
|EAx |= 5.7404×10−6 7 Iterações.
Exemplo 5. (Ex. 21, Ruggiero, pg 80).
f (x) = x log10(x)−1, ξ ∈ (2,3), min{|EAx¯ |, |f (x¯)|}< 10−7.
Exemplo 5. (Ex. 21, Ruggiero, pg 80).
f (x) = x log10(x)−1, ξ ∈ (2,3), min{|EAx¯ |, |f (x¯)|}< 10−7.
f ′(x) = log10(x) + 1/ln(10) 6= 0.
Exemplo 5. (Ex. 21, Ruggiero, pg 80).
f (x) = x log10(x)−1, ξ ∈ (2,3), min{|EAx¯ |, |f (x¯)|}< 10−7.
MPF: Função de iteração ϕ(x) = x−1.3(x log10(x)−1).
ϕ ′(x) = 1−1.3(log10(x) + 1/ln(10)) (|ϕ ′(x)|<< 1).
Exemplo 5. (Ex. 21, Ruggiero, pg 80).
f (x) = x log10(x)−1, ξ ∈ (2,3), min{|EAx¯ |, |f (x¯)|}< 10−7.
Bisseção.
x¯ = 2.506184413 f (x¯) = 1.2573×10−8
|EAx |= 5.9605×10−8 24 Iterações.
P. Falsa.
x¯ = 2.50618403 f (x¯) =−9.9419×10−8
|EAx |= .49381442 5 Iterações.
MPF com ϕ(x) = x−1.3(x log(x)−1) e x0 = 2.5.
x¯ = 2.50618417 f (x¯) = 2.0489×10−8
|EAx |= 3.8426×10−6 5 Iterações.
Newton-Raphson com x0 = 2.5.
x¯ = 2.50618415 f (x¯) = 4.6566×10−10
|EAx |= 3.9879×10−6 2 Iterações.
Secante com x0 = 2.3, x1 = 2.7.
x¯ = 2.50618418 f (x¯) = 2.9337×10−8
|EAx |= 8.0561×10−5 3 Iterações.