Date post: | 21-Dec-2015 |
Category: |
Documents |
Upload: | ivann-lukas |
View: | 234 times |
Download: | 0 times |
4251
0011 0010
UNIVERSIDADE FEDERAL DE UBERLÂNDIAFACULDADE DE MATEMÁTICA
PROJETO PIBEG
Unidade
Zeros de funções reais
4251
0011 0010
1 – Introdução 1.1 – Isolamento das raízes 1.2 – Refinamento
2 – Método da Bisseção 2.1 – Interpretação Geométrica 2.2 – Algoritmo 2.3 – Estimativa do Número de Iterações 2.4 – Estudo da Convergência
3 – Método do Ponto Fixo 3.1 – Interpretação Geométrica 3.2 – Estudo da convergência do MPF 3.3 – Algoritmo 3.4 – Ordem de convergência do MPF
4 – Método de Newton - Raphson 4.1 – Interpretação Geométrica 4.2 – Estudo da convergência do MNR 4.3 – Algoritmo 4.4 – Ordem de convergência do MNR
Sumário:
4251
0011 0010
Em muitos problemas de Ciência e Engenharia há a necessidade de se determinar um número r para o qual uma função f (x) seja zero, ou seja, f (r)=0.
Este número é chamado zero ou raiz da função f (x) e pode ser real ou complexo. Em nossos estudos r representará uma raiz real.
Graficamente, os zeros reais são representados pelos pontos de interseção da curva com o eixo Ox, conforme figura abaixo:
f(x)
x1r 2r 3r
4251
0011 0010
O objetivo desta unidade é o estudo de métodos numéricos
para a resolução de equações não-lineares, as quais não possuem
solução analítica.
Exemplo: )()( xsenexf x A idéia central destes métodos é partir de uma aproximação
inicial para a raiz e em seguida refinar essa aproximação através
de um processo iterativo do tipo:
n,...,1i),x(Fx
xdado
1ii
0
F(x) é chamada função de iteração.
4251
0011 0010
Portanto, o processo iterativo pode ser dividido em duas fases:
Fase I - Localização ou isolamento das raízes: Consiste em obter um intervalo [a,b] que contém uma única raiz;
Fase II - Refinamento: Consiste em, escolhidas aproximações iniciais no intervalo [a,b], melhorá-las sucessivamente até se obter uma aproximação para a raiz dentro de uma precisão prefixada.
4251
0011 0010
1.1 – Fase I: Isolamento das raízes
Nesta fase é feita uma análise gráfica e teórica da função.
A precisão desta análise é o pré-requisito para o sucesso da fase II.1.1.1 - Análise Gráfica
Esta análise pode ser feita através de um dos seguintes processos:
i) Esboçar o gráfico da função f (x) e localizar as abscissas
dos pontos de interseção da curva com o eixo ; xo
Exemplo: 39)( 3 xxxf
-4 -3 -2 -1 0 1 2 3 4-30
-20
-10
0
10
20
30
40
1r 2r 3r
]3,2[
]1,0[
]3,4[
3
2
1
r
r
r
4251
0011 0010
ii) A partir da equação f (x) = 0, obter a equação equivalente g(x) = h(x), esboçar os gráficos g(x) e h(x) no mesmo eixo cartesiano e localizar os pontos x de interseção das duas curvas, pois
).()(0)( rhrgrf
Exemplo: 0)( xexf x
Resolução:
xxh
exg
exx
x
)(
)(
]1,0[r
-2 -1 0 1 2 3 4-2
-1
0
1
2
3
4
5
6
7
8
h(x)
g(x)
r
4251
0011 0010
1.1.2 – Análise Teórica
Nesta análise usamos freqüentemente o teorema de Bolzano:
“Seja uma função contínua no intervalo [a, b]. Se f (a) f (b) < 0,
então existe pelo menos um ponto x = r entre a e b que é zero de f (x)”
Graficamente:
ab
1r2r
f(x)
x
1r2r
3ra
b
f(x)
x
4251
0011 0010
Sob as hipóteses do teorema anterior, se f’(x) existir e preservar o sinal em [a, b], então existe uma única raiz neste intervalo.
Graficamente:
f(x)
x
a
b
f(x)
xab
],[,0)(' baxxf ],[,0)(' baxxf
4251
0011 0010
Podemos aplicar este teorema atribuindo valores para x e analisar o sinal de f (x).
Exemplo: f(x) =
- Analisando a mudança de sinal podemos concluir que existe pelo
menos uma raiz dentro dos intervalos indicados.
- Derivando a função descobrimos que conserva o sinal em cada um dos intervalos, portanto cada raiz é única no intervalo.
393 xx
x -10 -5 -3 -1 0 1 2 3 4
f(x) - - + + + - - + +
93)(' 2 xxf
4251
0011 0010
Observação
Se f (a) f (b) > 0 então pode existir ou não raízes no intervalo [a,b].
Graficamente:
f(x)
x
f(x)
x
x
f(x)
a b1r 2r
a b1r
a b
4251
0011 0010
1.2 – Fase II: Refinamento
Esta fase consiste em aproximarmos uma raiz r dentro dointervalo [a, b] através de um método iterativo.
Um método iterativo é uma seqüência de instruções que são executadas passo a passo, algumas das quais são repetidas em ciclos, cada ciclo recebe o nome de iteração.
Estas iteração utilizam valores obtidos em iterações anteriorespara encontrar uma nova aproximação para a raiz.
Estes métodos fornecem uma aproximação para a raiz exata.
1.2.1 – Critérios de parada
Durante a aplicação de uma método para determinar-se uma raiz, necessitamos que uma certa condição seja satisfeita para
estabelecer se o valor de xi está suficientemente próximo de r.
4251
0011 0010
rix
f(x)
x
||
|)(|
rx
xf
i
i
rix x
f(x)
|)(|
||
i
i
xf
rx
i) || rxi
ii) |)(| ixf
O valor de xi é raiz aproximada com precisão se:
Nem sempre é possível ter as duas exigências satisfeitas
simultaneamente, analisemos os casos abaixo:
4251
0011 0010
|| 1ii xx
i
ii
x
xx 1
Como não conhecemos o valor da raiz r para aplicar o teste
i) |xi – r| < , usamos freqüentemente os conceitos de erro
absoluto e erro relativo para determinarmos o critério de parada.
a) Erro absoluto:
b) Erro relativo:
4251
0011 0010
Condições para aplicação:
-A função deve ser contínua no intervalo [a, b], onde contém pelo menos uma raiz, ou seja, f (a) f (b) < 0.
-Caso o intervalo contenha duas ou mais raízes, o método encontrará uma delas.
O objetivo deste método é reduzir a amplitude do intervalo
inicial que contém a raiz até que seu comprimento seja menor que a precisão desejada, usando para isso sucessivas divisões de [a, b] ao meio.
4251
0011 0010
f(x)
x
Iteração 1:
2.1 – Interpretação Geométrica
ra0
b0x0
a1
b1
x0 = (a0 + b0)2
f (x0) > 0
a1 = a0
b1 = x0
r a1 , b1]
Iteração 2:
x1 = (a1 + b1)2
x1
f (x1) < 0
a2 = x1
a2
b2 = b1
b2
r a2 , b2]
Iteração 3:
x2 = (a2 + b2)2
x2
f (x2) < 0
a3 = x2
a3
b3 = b2
b3
r a3 , b3]
4251
0011 0010
2.2 – Algoritmo
Seja f (x) contínua em [a, b] e tal que f (a) f (b) < 0.
1) Dados iniciais:
a) intervalo inicial [a, b]; b) precisão
2) Se (b – a) < , então escolha para r FIM. ]. ,[ bax
3) k = 1
4) 2
baxk
5) Se , faça Vá para o passo 7 0)()( kxfaf .kxa
6) .kxb
7) Se (a – b) < , escolha para r FIM. ].,[ bax
8) k = k +1. Volte ao passo 4.
4251
0011 0010
2.3 - Estimativa do número de iterações
0a 0b
1a 1b
2
ab 00
2a2b
20011
2
ab
2
ab
3a 3b
30022
2
ab
2
ab
k00
2
ab
Dada uma precisão e um intervalo [a, b], vamos determinar quantas
iterações k serão efetuadas pelo método da Bisseção até que
bk – ak < . Sendo k um número inteiro.
4251
0011 0010
kab
k ,2log
log)log( 00
Deve-se obter o valor de k tal que , ou seja: kk ab
0000 2
2
abab kk
00log2logab
k
4251
0011 0010
2.4 - Estudo da convergência da Bisseção:
Seja f (x) uma função contínua em [a, b], onde f (a) f (b) < 0.
O método da bisseção gera três seqüências:
não-decrescente e limitada superiormente por tal que:
:}{ ka 0b IRttak
k
lim
:}{ kb não-crescente e limitada inferiormente por tal que:
0a IRssbk
k
lim
:}{ kx por construção temos que kbxaba
x kkkkk
k
,2
A amplitude de cada intervalo gerado é a metade da amplitude doanterior, assim temos:
kkk
abab
200
4251
0011 0010
Aplicando o limite temos:
kk
kk
kk
kk
kkkk
k
abab
abab
limlim0limlim
02
lim)(lim 00
Seja = t = s o limite das duas seqüências, aplicando o limite na seqüência xk temos que:
22limlim kk
kk
k
bax
Então t = s
Resta provarmos que é zero da função, ou seja, f ( ) = 0.
Em cada iteração k temos que , então:0)()( kk bfaf
0)(0)]([0
)]([)()()lim()lim(0
)(lim)(lim)()(lim0
2
2
ff
fsftfbfaf
bfafbfaf
kk
kk
kk
kk
kkk
4251
0011 0010
,2,1),( 1 ixx ii
Seja f (x) uma função contínua em [a, b], intervalo que contém uma raiz r da equação f (x) = 0.
O Método da Iteração Linear (MIL ou MPF) consiste em transformar f (x) = 0 em uma equação equivalente x = (x), onde (x) é uma função de iteração.
A partir de uma aproximação inicial gerar uma seqüência . de aproximações sucessivas através do processo iterativo dado por:
0x}{ kx
4251
0011 0010
3.1 - Interpretação Geométrica
Graficamente, uma raiz da equação x = (x) é a abcissa do ponto de intersecção da reta y = x e da curva y = (x)
0x1x2xr
xy )(xy
f(x)
x
4251
0011 0010
31 6)(a) xx
Existem várias funções de iteração para esta equação, por exemplo:
converge não
3.1772)088.12(6
088.12625.26
625.25.16
6
33
32
31
31
x
x
x
x
converge
635.1632.16
632.1651.16
651.15.16
6
33
32
31
32
x
x
x
x
5.1 dado 0 x
32 6 b) x
1
6 c)
23
x
xx
16 d)
24
e)
Exemplo: Encontre uma função de iteração (x) para a seguinte equação .063 xx
4251
0011 0010
Analisemos alguns casos de função de iteração:
x0x1x
f(x))(x
2x
Não Converge
x0x1x2x
f(x)
)(x
Não Converge
x0x1x2x
f(x) )(x
Converge
f(x)
x0x1x
)x(
Converge
2x
4251
0011 0010
Teorema 2:
i) e são contínuas em I)(x )(' x
IxMx ,1|)('|ii)
Ix 0iii)
então a seqüência gerada converge para a raiz r.}{ kx
3.2 – Estudo da Convergência do MIL
Para que o MIL forneça uma solução da equação f (x) = 0 é necessário que a seqüência gerada , dada por , seja convergente.
}{ kx )(1 kk xx
A convergência será dada pelo seguinte teorema:
Seja r uma raiz da equação f (x) = 0, isolada num intervalo I centrado em r. Seja (x) uma função de iteração para a equação f (x) = 0. Se:
4251
0011 0010
Demonstração
r é uma raiz exata da equação f (x) = 0.
Assim, e, )(0)( rrrf
para qualquer k, temos: )(1 kk xx
)()(1 rxrx kk
x)é contínua e diferenciável em I, então, pelo Teorema do Valor Médio, se existe entre e r tal que:,Ixk kc kx
)()())((' rxrxc kkk
Portanto, comparando (1) e (2), resulta
)()('1 rxcrx kkk
(1)
1) Provemos que se então :, kIxk ,0 Ix
(2)
4251
0011 0010
Então, ,k
|||||)('|||1
1 rxrxcrx kkkk
ou seja, a distância entre e r é estritamente menor que a distância entre e r e, como I está centrado em r, temos que se . então
1kxkx
,Ixk .1 Ixk
Por hipótese, então ,0 Ix ., kIxk
2) Provemos que :lim rxk
k
De (1) , segue que:
|||||)('||| 0001 rxMrxcrxM
( está entre e r )0c 0x
4251
0011 0010
|||||||)('||| 02
1112 rxMrxMrxcrxM
|||||||)('||| 0111 rxMrxMrxcrx kkk
M
kk
Então, pois 0 < M < 1.0||lim||lim 0
rxMrx k
kk
k
Assim,
.lim0||lim rxrx kk
kk
( está entre e r )kc kx
( está entre e r ) 1c 1x
4251
0011 0010
3.3 – Algoritmo do MIL
Considere a equação f (x) = 0 e a equação equivalente x = x)
1) Dados iniciais:
0xa) : aproximação inicial;
2) Se faça FIM. ,|)(| 10 xf .0xr
3) i = 1
4) )( 01 xx
5) Se 11 |)(| xf
ou se 201 || xxentão faça FIM. .1xr
6) 10 xx
7) i = i +1. Volte ao passo 4.
b) e : precisões.1 2
4251
0011 0010
3.4 – Ordem de convergência do MIL
Definição: Seja uma seqüência que converge para um número r e seja o erro na iteração k.
}{ kxrxe kk
Se existir um número p > 1 e uma constante C > 0, tais que
Ce
ep
k
k
k
||
||lim 1
então p é chamada de ordem de convergência da seqüência e C é a constante assintótica de erro.
}{ kx
Uma vez obtida a ordem de convergência p de um método iterativo, ela nos dá uma informação sobre a rapidez de convergência do processo.
(2)
keCe pkk para|||| 1
De (2) podemos escrever:
4251
0011 0010
Provaremos que o MIL tem convergência apenas linear.
Conforme foi demonstrado, temos que:
))(('1 rxcrx kkk
)('1k
k
k crx
rx
Tomando o limite quando k
)('))(lim(')('limlim 1 rccrx
rxk
kk
kk
k
k
1|| e )('lim 1
CCr
e
e
k
k
k
Então para grandes valores de k o erro em qualquer iteração é proporcional ao erro na iteração anterior, sendo ’(r ) o fator de proporcionalidade.
Portanto,
4251
0011 0010
No estudo do método do ponto fixo, vimos que:
i) uma das condições de convergência é que onde I contém a raiz r;
,,1|)('| IxMx
ii) a convergência do método será mais rápida quanto menor for |’(r)|.
Com a finalidade de acelerar e garantir a convergência, o MNR procura uma função de iteração x) tal que ’(r) = 0. Partindo da forma geral para x), iremos obter a função A(x) tal que ’(r) = 0.
)()()( xfxAxx )(')()()('1)(' xfxAxfxAx
)(')(1)('
)(')()()('1)('
rfrAr
rfrArfrAr
4251
0011 0010
Então, dada f (x), a função de iteração representada por
)('
)()(
xf
xfxx
22
2
)]('[
)('')(
)]('[
)('')()]('[1)('
xf
xfxf
xf
xfxfxfx
Assim,
donde tomamos
)('
1)(0)(')(10)('
rfrArfrAr
)('
1)(
xfxA ).0)(' que (desde rf
será tal que ’(r) = 0, pois como podemos verificar:
0)]('[
)('')()('
2
rf
rfrfr
4251
0011 0010
4.1 – Interpretação Geométrica
0x
1x2x
0L
1L
f(x)
x
f (x)
r
Dado o ponto traçamos a reta tangente à curva neste ponto, dado por
))(,( ii xfx )(xLi
))((')()( iiii xxxfxfxL
4251
0011 0010
4.2 – Estudo da Convergência do MNR
Teorema 3:
Sejam f (x), f’(x), f’’(x) contínuas num intervalo I que contém a raiz x = r de f (x) = 0. Suponha que f’(r) 0.
Então, existe um intervalo contendo a raiz r, tal que se . a função de iteração
convergirá para a raiz.
,II ,0 Ix
)('
)(1
k
kkk xf
xfxx
Demonstração
Devemos provar que as hipóteses do Teorema 2 estão satisfeitaspara
)('
)()(
xf
xfxx
4251
0011 0010
i) Afirmação: (x) e ’(x) são contínuas em .1I
Assim, no intervalo , tem-se que f (x), f ’(x) e f ’’(x) são contínuas e f ’(x) 0. Então (x) e ’(x) são contínuas em
II 1
.1I
ii) Afirmação: |’(x)| < 1, 2Ix
Por hipótese, f ’(r) 0 e, como f ’(x) é contínua em I, é possível obter tal que f ’(x) 0, II 1
.1Ix
Concluindo, conseguimos obter um intervalo , centrado em r, tal que (x) e ’(x) sejam contínuas eme |’(x)| < 1, .
II 2
2I
2Ix
Como ’(x) é contínua em e ’(r) = 0, é possível escolher tal que |’(x)| < 1, de forma que r seja seu centro.
1I2IxII 2
2)]('[
)('')()(' e
)('
)()(
xf
xfxfx
xf
xfxx Temos:
4251
0011 0010
4.3 – Algoritmo do MNR
Seja f (x) = 0.1) Dados iniciais:
a) aproximação inicial;:0x
b) precisões: e 21
2) Se , faça .FIM 10 |)(| xf 0xr
3) k = 1
4) )('
)(
0
001 xf
xfxx
5) FIM . faça
|| seou
|)(| Se1
201
11 xrxx
xf
6) 10 xx
7) k = k + 1 Volte ao passo 4.
4251
0011 0010
4.4 – Ordem de Convergência do MNR
Seja a função de iteração (x) desenvolvida em série de Taylor,em torno de x = r:
],[,!2
)()("
!1
)()(')()(
2
rxrxrxr
rx
mas,
)(
)(
0)('
1ii xx
rr
r
Generalizando para , resulta: 1ix
],[,!2
)()(")( 11
211
1 rxrx
rx iiii
i
ou,
2
112
11
2
)(")(
2
)("i
iii
ii eerxrx
2
)("limlim 1
21
i
ii
i
i e
e