8ª Lista - Unidade I

Prévia do material em texto

Universidade Federal Rural do Semi-Árido
Departamento de Ciências Exatas e Naturais
Disciplina: Cálculo Numérico
Período: 2013.1
Aluno(a):
8
a
Nota de Cálculo Numérico: Método da iteração ponto �xo e um introdução método de
Newton - 10/06/2013
Exemplo A equação x3 + 4x2 − 10 = 0 tem um única raiz no intervalo [1, 2]. Há muitas maneiras de
se mudar essa equação para a forma de ponto �xo x = g(x) utilizando manipulações algébricas simples.
Por exemplo, para obter a função g podemos fazer 4x2 = 10− x3, o que implica em x2 = 14 (10− x3), ou
seja:
x = ±1
2
(10− x3) 13 , ou seja g(x) = 1
2
(10− x3) 13
Veja nos exemplos logoa baixo, exemplos da função g que pode ser extraida da equação x3+4x2−10 = 0.
i) x = g1(x) = x− x3 − 4x2 + 10.
ii)x = g2(x) = (
10
x
− 4x) 12
iii)x = g3(x) =
1
2 (10− x3)
1
3
iv)x = g4(x) = (
10
4 + x
)
1
2
Método da iteração do ponto �xo - MPF: Em geral, para obtermos um valor aproximado do ponto
�xo de um função g, escolhemos um aproximação inicial p0 e geramos a sequência {pn}∞n=0 fazendo
pn = g(pn−1) para cada n ≥ 1. Se a sequencia converge para p e g é contínua, então:
lim
n−→∞(pn) = limn−→∞(g(pn−1)) = g( limn−→∞(pn−1))
p = g(p)
Teorema do ponto Fixo Seja g ∈ C[a, b] tal que g(x) ∈ [a, b] para todo x ∈ [a, b]. Suponha, adicional-
mente, que g′ exista em (a, b) e que uma constante 0 < k < 1 exista, com |g′(x)| ≤ k, para todo x ∈ (a, b).
Então, para qualquer número p0 ∈ [a, b], a sequência de�nida por pn = g(pn−1), n ≥ 1 converge para o
único ponto �xo p ∈ [a, b].
Demonstração: O teorema da nota de aula 7 garante que a unicidade do ponto �xo, desde que g
mapeia o próprio intervaqlo [a, b], a sequencia {pn}∞n=0 é de�nida para todo n ≥ 0 e pn ∈ [a, b] para todo
n. Utilizando o fato de que |g′(x)| ≤ k e o teorem ado valor médio, temo, para cada n,
|pn − p| = |g(pn−1)− g(p)| = |g′(ξn)||pn−1 − p| ≤ k|pn−1 − p|
onde ξn ∈ (a, b). Aplicando essa desigualdade, por indução temos:
|pn − p| ≤ k|pn−1 − p| ≤ k2|pn−2 − p| ≤ · · · ≤ kn|p0 − p|
Como 0 < k < 1, temos que lim
n−→∞ k
n|p0 − p| = 0 e assim a sequencia {pn}∞n=0 converge para p.
1
Algoritmo da iteração do ponto �xo - MPF
Para encontar uma solução para p = g(p) dada uma solução inicial p0.
ENTRADA: aproximação inicial p0; tolerância TOL; número de iterações N0
SAÌDA: solução aproximda p ou mensagem de falha
Passo 1: Faça i = 1;
Passo 2: Enquanto i ≤ N0 siga os passos de 3− 6.
Faça p = g(p0). (Este passo calcula pi).
Passo 3: Se |p− p0| < TOL então
SAÌDA (p); (Aqui termina o procedimento, que foi bem sucedido)
PARE.
Passo 5 Faça i = i+ 1
Passo 6 Faça p0 = p. Este passo atualiza p0.
Passo 7 SAÍDA ('O método falhou após N0 iterações,O procedimento não foi bem sucedido..)
PARE
Método de Newton
Seja z a única raiz de f(x) = 0 no intervalo [a, b] e ze uma aproximação desta raiz, sendo que as
derivadas f ′(x) e f ′′(x) devem existir, ser contínuas e com sinal constante neste intervalo. Geometrica-
mente, o método de Newton é equivalente a aproximar um arco de curva por um reta tangente traçada
a partir de um ponto da curva, o que faz com que ele seja conhecido também como o método das tangentes.
A idéia do método baseia-se em:
i)A estimativa da raiz da função é feita a partir da reta tangente à função em um ponto de partida.
ii)O ponto em que esta reta tangente intercepta o eixo das abcissas correpsonde á estimativa do zero
da função.
iii)Se o valor estimado não atender à tolerância estabelecida para o problema, ou seja, |f(ze)| > TOL,
repete-se o esquema até que a mesma seja veri�cada.
Veja a equação de recorrência abaixo:
tan(θ) = f ′(a) =
f(a)
a− ze , ou seja ze = a−
f(a)
f ′(a)
A generalização da equação acima gera uma sequencia xk para ser utlizada no método de Newton.
xk+1 = xk − f(xk)
f ′(xk)
, para k = 0, 1, 2, 3, . . .
2
Teorema Se f(a)f(b) < 0, e f ′(x) e f ′′(x) forem não nulas e preservarem o sinal em [a, b], então partindo-
se da aproximação inicial x0 ∈ [a, b] tal que f(x0)f ′′(xo) > 0 é possível construir, pelo método de Newton,
uma sequencia {xi} quue convirja para a raiz ξ de f(x) = 0.
3