Fórmula de quadratura
Regras simples
Regras compostas
Erro de quadratura
Acceleração da convergência
INTEGRAÇÃO NUMÉRICA
Nadir Arada
Cálculo Numérico - Integração numérica
Romberg
Fórmula de quadratura
Regras simples
Regras compostas
Erro de quadratura
Acceleração da convergência
Objectivo. Aproximar
I(f ) =
Z
b
a
f (x) dx
onde f : [a, b] −→ R
I é uma função contínua, suficientemente regular.
Cálculo Numérico - Integração numérica
Romberg
Fórmula de quadratura
Regras simples
Regras compostas
Erro de quadratura
Acceleração da convergência
Fórmula de quadratura
Considere x0 < x1 < · · · < xn , n + 1 pontos em [a, b] e seja
Πn f (x) =
n
X
f (xi )ϕi (x)
i=0
o polinómio interpolador de f nos pontos (x i )i=0,1,··· ,n . Uma vez que
f (x) = Πn f (x) +
vem que
I(f ) =
Cálculo Numérico - Integração numérica
Z
f (n+1) (ζx )
(n+1)!
|
b
a
n
Y
(x − xi ),
i=0
{z
En f (x)
Πn (x) dx +
Z
b
a
ζx ∈]a, b[
}
En f (x) dx
Romberg
Fórmula de quadratura
Regras simples
Regras compostas
Erro de quadratura
Acceleração da convergência
Por conseguinte
I(f ) =
=
Z
b
a i=0
n
X
f (xi )ϕi (x) dx +
f (xi )
i=0
Assim
n
X
Z
|a
b
ϕi (x) dx +
{z
}
Z
b
a
Z
b
a
En f (x) dx
En f (x) dx
αi
I(f ) é aproximado por
n
X
αi f (xi )
i=0
n
A soma
n
αi f (xi ) é a fórmula de quadratura. A diferença I(f ) −
i=0
αi f (xi ) é o erro de
i=0
quadratura. Os pontos xi e as constantes αi são, respectivamente, os nós e os pesos de
quadratura.
Cálculo Numérico - Integração numérica
Romberg
Fórmula de quadratura
Regras simples
Regras compostas
Erro de quadratura
Acceleração da convergência
Regra do ponto médio (ou do rectangulo) simples. É obtida com
n = 0, x0 = a+b
2 e Π0 (x) = f (x0 ). A fórmula de quadratura associada
escreve-se
Z b
IR (f ) =
Π0 (x) dx = (b − a)f a+b
2
a
f
Π0 f
a
Cálculo Numérico - Integração numérica
a+b
2
b
Romberg
Fórmula de quadratura
Regras simples
Regras compostas
Erro de quadratura
Acceleração da convergência
Regra do trapézio simples. É obtida com n = 1, x 0 = a e x1 = b. A
fórmula de quadratura associada escreve-se
Z b
(b)
IT (f ) =
Π1 (x) dx = (b − a) f (a)+f
2
a
f
a
Cálculo Numérico - Integração numérica
Π1 f
b
Romberg
Fórmula de quadratura
Regras simples
Regras compostas
Erro de quadratura
Acceleração da convergência
Regra de Simpson simples. É obtida com n = 2, x 0 = a, x1 = a+b
2 e
x2 = b. A fórmula de quadratura associada escreve-se
Z b
f (a) + 4f a+b
+ f (b)
IS (f ) =
Π1 (x) dx = b−a
6
2
a
f
a
Cálculo Numérico - Integração numérica
Π2 f
a+b
2
b
Romberg
Fórmula de quadratura
Regras simples
Regras compostas
Erro de quadratura
Acceleração da convergência
Exemplo 1. Aproximar
Z
5
0
dx
1+x2
= arctan(5) ≈ 1.373400766945016
• Utilizando a regra do ponto médio simples, obtem-se
IR (f ) = (5 − 0)f 52 = 55 2 = 0.6896551724137931
1+( 2 )
O erro correspondente (em valor absoluto) é dado por
|I(f ) − IR (f )| = 0.6837455945312227
Cálculo Numérico - Integração numérica
Romberg
Fórmula de quadratura
Regras simples
Regras compostas
Erro de quadratura
Acceleração da convergência
• Do mesmo modo, utilizando a regra do trapézio simples, tem-se
(0)
5
1
IT (f ) = (5 − 0) f (5)+f
=
+
1
= 2.596153846153846
2
2 1+52
com o erro
|I(f ) − IT (f )| = 1.22275307920883
• Finalmente, aplicando a regra de Simpson simples, obtem-se
IS (f ) = (5 −
5
f (5)+2f 2 +f (0)
0)
6
=
5
6
1
1+52
+
2
1+( 52 )
= 1.09526967285588
e o erro é
|I(f ) − IS (f )| = 0.2781310940891359
Cálculo Numérico - Integração numérica
2
+1
Romberg
Fórmula de quadratura
Regras simples
Regras compostas
Erro de quadratura
Acceleração da convergência
Regras de integração compostas
Considere uma subdivisão de [a, b] em m subintervalos [x k−1 , xk ],
k = 1, · · · , m, de igual comprimento h = b−a
m .
Ideia.
Aproximar
Z
xk
xk−1
f (x) dx por
Z
xk
xk−1
Πkn f (x) dx
onde Πkn f é o polinómio interpolador de f no subintervalo [x k−1 , xk ].
Cálculo Numérico - Integração numérica
Romberg
Fórmula de quadratura
Regras simples
Regras compostas
Uma vez que
I(f ) =
Erro de quadratura
m Z
X
k=1
xk
xk−1
Acceleração da convergência
f (x) dx
então
I(f ) é aproximado por
m Z
X
k=1
Cálculo Numérico - Integração numérica
xk
xk−1
Πkn f (x) dx
Romberg
Fórmula de quadratura
Regras simples
Regras compostas
Erro de quadratura
Acceleração da convergência
Romberg
Regra do ponto médio composta. É obtida aplicando a regra simples
do ponto médio em cada subintervalo [x k−1 , xk ]:
m
X
x
+x
m
IR (f ) = h
f k−12 k
k=1
f
Π10 f
Π20 f
a=x0
Cálculo Numérico - Integração numérica
x1
xm =b
Fórmula de quadratura
Regras simples
Regras compostas
Erro de quadratura
Acceleração da convergência
Π10 f
f
Π20 f
Πm
0f
a=x0
x1
x2
Regra do ponto médio composta com m subintervalos
Cálculo Numérico - Integração numérica
xm =b
Romberg
Fórmula de quadratura
Regras simples
Regras compostas
Erro de quadratura
Acceleração da convergência
Romberg
Exemplo 2. Considere o integral do Exemplo 1. Utilizando a regra do
ponto médio composta com m = 2, obtem-se
IR2 (f ) = 52 f 54 + f 15
= 1.141584859832
4
O erro correspondente (em valor absoluto) é dado por
I(f ) − IR2 (f ) = 0.2318159071130159
e é claramente menor que o erro obtido com a regra do ponto médio
simples. Os resultados obtidos aumentando o número de
subintervalos, são resumidos na seguinte tabela
m
4
8
IRm (f )
1.353866933486058
1.373505133232817
Cálculo Numérico - Integração numérica
|I(f ) − IRm (f )|
0.01953383345895787
1.04366287801 × 10 −4
Fórmula de quadratura
Regras simples
Regras compostas
Erro de quadratura
Acceleração da convergência
Regra do trapézio composta. É obtida aplicando a regra simples do
trapézio em cada subintervalo [xk−1 , xk ]:
ITm (f )
f
=
h
2
m
X
(f (xk−1 ) + f (xk ))
k=1
Π11 f
Π21 f
a=x0
Cálculo Numérico - Integração numérica
x1
xm =b
Romberg
Fórmula de quadratura
Regras simples
Regras compostas
Erro de quadratura
Acceleração da convergência
f
Π11 f
Π21 f
Πm
1 f
a=x0
x1
x2
Regra do trapézio composta com m subintervalos
Cálculo Numérico - Integração numérica
xm =b
Romberg
Fórmula de quadratura
Regras simples
Regras compostas
Erro de quadratura
Acceleração da convergência
Romberg
Exemplo 3. Considere o integral do Exemplo 1. Utilizando a regra do
trapézio composta com m = 2, obtem-se
IT2 (f ) = 52 f (0) + 2f 52 + f (5) = 1.64290450928382
O erro correspondente (em valor absoluto) é dado por
I(f ) − IT2 (f ) = 0.269503742338804
e é claramente menor que o erro obtido com a regra do trapézio
simples. Os resultados obtidos aumentando o número de
subintervalos, são resumidos na seguinte tabela
m
4
8
ITm (f )
1.39224468455791
1.373055809021984
Cálculo Numérico - Integração numérica
|I(f ) − ITm (f )|
0.01884391761289406
3.44957923032 × 10 −4
Fórmula de quadratura
Regras simples
Regras compostas
Erro de quadratura
Acceleração da convergência
Regra de Simpson composta. É obtida aplicando a regra simples de
Simpson em cada subintervalo [xk−1 , xk ]:
m X
x
+x
ISm (f ) = h6
f (xk−1 ) + 4f k−12 k + f (xk )
k=1
f
Π12 f
Π22 f
a=x0
Cálculo Numérico - Integração numérica
x1
x2 =b
Romberg
Fórmula de quadratura
Regras simples
Regras compostas
Erro de quadratura
Acceleração da convergência
f
Π12 f
Π22 f
Πm
2 f
a=x0
x1
x2
Regra de Simpson composta com m subintervalos
Cálculo Numérico - Integração numérica
xm =b
Romberg
Fórmula de quadratura
Regras simples
Regras compostas
Erro de quadratura
Acceleração da convergência
Romberg
Exemplo 4. Considere o integral do Exemplo 1. Utilizando a regra de
Simpson composta com m = 2, obtem-se
5
IS2 (f ) = 12
f (0) + 4f 54 + 2f 52 + 4f 15
4 + f (5)
= 1.308691409649274
O erro correspondente (em valor absoluto) é dado por
I(f ) − IS2 (f ) = 0.06470935729574179
e é menor que o erro obtido com a regra de Simpson simples. Os
resultados obtidos aumentando o número de subintervalos, são
resumidos na seguinte tabela
I(f ) − I m (f )
m
ISm (f )
S
4 1.366659517176675
0.006741249768341
8 1.373355358495872 4.5408449144e × 10 −5
Cálculo Numérico - Integração numérica
Fórmula de quadratura
Regras simples
Regras compostas
Erro de quadratura
Acceleração da convergência
Erro de quadratura: regra do ponto médio
Teorema. Seja f ∈ C 2 [a, b] e seja IR (f ) a aproximação de I(f ) pela
regra do ponto médio simples. O erro correspondente satisfaz
|I(f ) − IR (f )| ≤
onde M2 = max |f ”(x)|.
x∈[a,b]
Cálculo Numérico - Integração numérica
M2
(b − a)3
24
Romberg
Fórmula de quadratura
Regras simples
Regras compostas
Erro de quadratura
Acceleração da convergência
Demonstração. Utilizando a formula de Taylor a volta do ponto
médio x̄ = a+b
2 , obtem-se
f (x) = f (x̄) + f 0 (x̄)(x − x̄) +
f ”(ζx )
2 (x
− x̄)2 ,
ζx ∈]a, b[.
Portanto
Z b
|I(f ) − IR (f )| = f (x) dx − (b − a)f (x̄)
Za b
=
(f (x) − f (x̄)) dx
Za b f ”(ζx )
0
2
=
f (x̄)(x − x̄) + 2 (x − x̄) dx
a
Cálculo Numérico - Integração numérica
Romberg
Fórmula de quadratura
Regras simples
Regras compostas
Erro de quadratura
Acceleração da convergência
Uma vez que
Z
a
b
0
0
f (x̄)(x − x̄) dx = f (x̄)
=
f 0 (x̄)
2
=
f 0 (x̄)
2
=0
Z
b
a
(x − x̄) dx
(x − x̄)2
b−a 2
2
b
a
−
e que
|f ”(ζx )| ≤ max |f ”(x)| = M2
x∈[a,b]
Cálculo Numérico - Integração numérica
a−b 2
2
Romberg
Fórmula de quadratura
Regras simples
Regras compostas
Erro de quadratura
Acceleração da convergência
conclui-se que
Z b
2
f
”(ζ
)(x
−
x̄)
dx
x
a
Z b
1
|f ”(ζx )| (x − x̄)2 dx
≤2
|I(f ) − IR (f )| =
1
2
a
Cálculo Numérico - Integração numérica
Z
b
≤
1
2
=
M2
2
=
M2 2
2 3
a
h
M2 (x − x̄)2 dx
i
(x−x̄)3 b
3
a
b−a 3
2
=
=
M2
2
M2
24
b−a
2
3
−
3
(b − a)3
a−b
2
3
Romberg
Fórmula de quadratura
Regras simples
Regras compostas
Erro de quadratura
Acceleração da convergência
Corolário. Seja f ∈ C 2 [a, b] e seja IRm (f ) a aproximação de I(f ) pela
regra do ponto médio composta associada a m subintervalos de igual
comprimento h= b−a
m . O erro correspondente satisfaz
|I(f ) − IRm (f )| ≤
onde M2 = max |f ”(x)|.
x∈[a,b]
Cálculo Numérico - Integração numérica
M2 (b − a) 2
h
24
Romberg
Fórmula de quadratura
Regras simples
Regras compostas
Demonstração. Seja x̄k =
Erro de quadratura
Acceleração da convergência
xk−1 +xk
,
2
k = 1, · · · , m. Tem-se
m Z
X xk
|I(f ) − IRm (f )| = (f (x) − f (x̄k )) dx
k=1 xk−1
Z
m xk
X
(f (x) − f (x̄k )) dx
≤
xk−1
k=1
Aplicando o teorema precedente a cada subintervalo, obtem-se
Z
xk
max
x∈[xk−1 ,xk ] |f ”(x)| 3
2 3
(f (x) − f (x̄k )) dx ≤
h ≤M
24
24 h
xk−1
Combinando a duas inequações, conclui-se que
|I(f ) −
IRm (f )|
≤
m
X
k=1
Cálculo Numérico - Integração numérica
M2
24
h3 =
M2
24
mh3 =
M2
24
(b − a)h2
Romberg
Fórmula de quadratura
Regras simples
Regras compostas
Erro de quadratura
Acceleração da convergência
Erro de quadratura: regra do trapézio
Teorema. Seja f ∈ C 2 [a, b] e seja ITm (f ) a aproximação de I(f ) pela
regra do trapézio composta associada a m subintervalos de igual
comprimento h= b−a
m . O erro correspondente satisfaz
|I(f ) − ITm (f )| ≤
onde M2 = max |f ”(x)|.
x∈[a,b]
Cálculo Numérico - Integração numérica
M2 (b − a) 2
h
12
Romberg
Fórmula de quadratura
Regras simples
Regras compostas
Erro de quadratura
Acceleração da convergência
Erro de quadratura: regra do Simpson
Teorema. Seja f ∈ C 4 [a, b] e seja ISm (f ) a aproximação de I(f ) pela
regra de Simpson composta associada a m subintervalos de igual
comprimento h= b−a
m . O erro correspondente satisfaz
|I(f ) − ISm (f )| ≤
onde M4 = max f (4) (x).
x∈[a,b]
Cálculo Numérico - Integração numérica
M4 (b − a) h4
16
180
Romberg
Fórmula de quadratura
Regras simples
Regras compostas
Erro de quadratura
Acceleração da convergência
Romberg
Acceleração da convergência: Extrapolação de Richardson
É um processo que combina várias aproximações de uma certa
quantidade, de modo a garantir uma convergência de ordem superior
sem custo suplementare.
Mais precisamente, suponha que A é uma dada quantidade e seja
(Am )m uma aproximação de A tal que
2k+2
A = Am + C1 h2m + C2 h4m + · · · + Ck h2k
m + O hm
onde
hm+1 =
1
2
hm ,
(1)
m≥0
e onde C1 , C2 , · · · , Ck são constantes positivas independentes de m.
Cálculo Numérico - Integração numérica
Fórmula de quadratura
Regras simples
Regras compostas
Erro de quadratura
Acceleração da convergência
Uma vez que
hm =
1
2
hm−1 =
vem que
1 2
hm−2
2
1 m
h0
2
m→+∞
lim hm = lim
m→+∞
Portanto
lim (A − Am ) = lim
m→+∞
m→+∞
= ··· =
1 m
h0
2
=0
2k+2
C1 h2m + · · · + Ck h2k
m + O hm
=0
A − Am
2k−2
= C1
= lim C1 + · · · + Ck hm
+ O h2k
m
2
m→+∞
m→+∞
hm
lim
o que implica que Am é uma aproximação a ordem 2 de A.
Cálculo Numérico - Integração numérica
Romberg
Fórmula de quadratura
Regras simples
Regras compostas
Erro de quadratura
Acceleração da convergência
Romberg
De (1), deduz-se que para m ≥ 1, tem-se
2k+2
A = Am−1 + C1 h2m−1 + C2 h4m−1 + · · · + Ck h2k
m−1 + O hm−1
2k+2
= Am−1 + C1 (2hm )2 + C2 (2hm )4 + · · · + Ck (2hm )2k + O hm
2k+2
= Am−1 + 22 C1 h2m + 24 C2 h4m + · · · + 22k Ck h2k
m + O hm
Multiplicando (1) por 4 e substraindo (2), obtem-se
(4 − 1) A = 4 Am − Am−1 + 4 − 24 C2 h4m
2k+2
+ · · · + 4 − 2k Ck h2k
m + O hm
Cálculo Numérico - Integração numérica
(2)
Fórmula de quadratura
Regras simples
Regras compostas
Erro de quadratura
Acceleração da convergência
Romberg
Isto é
A=
4 Am −Am−1
4−1
+
(4−24 )C2
22 −1
h4m + · · · +
(4−2k )Ck
22 −1
2k+2
e 2 h4m + · · · + C
e k h2k
= Bm,1 + C
m + O hm
2k+2
h2k
m + O hm
Em outras palavras
Bm,1 =
4 Am − Am−1
,
4−1
é uma aproximação de A a ordem 4.
Cálculo Numérico - Integração numérica
m≥1
(3)
Fórmula de quadratura
Regras simples
Regras compostas
Erro de quadratura
Acceleração da convergência
Romberg
Utilizando (3) e repetindo o processo, obtem-se
e 2 h4 + · · · + C
e k h2k + O h2k+2
A = Bm−1,1 + C
m−1
m−1
m−1
2k+2
e 2 (2hm )4 + · · · + C
e k (2hm )2k + O hm
= Bm−1,1 + C
2k+2
e 2 h4m + · · · + 22k Ck h2k
= Bm−1,1 + 24 C
m + O hm
Multiplicando (3) por 24 = 42 e substraindo (4), obtem-se
e 3 h6m
42 − 1 A = 42 Bm,1 − Bm−1,1 + 24 − 26 C
2k+2
e k h2k
+ · · · + 24 − 2 k C
m + O hm
Cálculo Numérico - Integração numérica
(4)
Fórmula de quadratura
Regras simples
Regras compostas
Erro de quadratura
Acceleração da convergência
Romberg
Isto é
A=
42 Bm,1 −Bm−1,1
42 −1
+
(24 −26 )C3
24 −1
h6m + · · · +
(24 −2k )Ck
24 −1
2k+2
b 3 h6m + · · · + C
b k h2k
= Bm,2 + C
m + O hm
2k+2
h2k
m + O hm
Em outras palavras
Bm,2 =
42 Bm,1 − Bm−1,1
,
42 − 1
é uma aproximação de A a ordem 6.
Cálculo Numérico - Integração numérica
m≥2
Fórmula de quadratura
Regras simples
Regras compostas
Erro de quadratura
Acceleração da convergência
O mesmo processo permite de construir por indução, uma sucessão
Bm,n definida por

Bm,0 = Am




4n Bm,n−1 − Bm−1,n−1
=
B

m,n


4n − 1

e que aproxima A a ordem 2(n + 1).
Cálculo Numérico - Integração numérica
m = 0, · · · , k
n = 1, · · · , k − 1
m = n, · · · , k
Romberg
Fórmula de quadratura
Regras simples
Regras compostas
Erro de quadratura
Acceleração da convergência
Romberg
Método de Romberg
Proposição (Fórmula de Euler-MacLaurin) Seja f ∈ C 2k+2 [a, b] e
m
seja hm = b−a
2m (m ≥ 0). Seja IT (f ) a aproximação do integral I(f )
obtida pela aplicação da regra do trapézio composta com 2 m
subintervalos. Tem-se
(2k+2)
2k+2
I(f ) = ITm (f ) + C1 h2m + C2 h4m + · · · + Ck h2k
(ζm ) hm
m + Ck+1 f
onde C1 , C2 , · · · , Ck , Ck+1 são constantes positivas independentes de
m e onde ζm ∈]a, b[.
Cálculo Numérico - Integração numérica
Fórmula de quadratura
Regras simples
Regras compostas
Erro de quadratura
Acceleração da convergência
Aplicando o método de extrapolação de Richardson, constrói-se uma
sucessão R(m, n)

R(m, 0) = ITm




4n R(m, n − 1) − R(m − 1, n − 1)
R(m,
n)
=



4n − 1

cuja convergência para I(f ) é de ordem 2(n + 1).
Cálculo Numérico - Integração numérica
m = 0, · · · , k
n = 1, · · · , k − 1
m = n, · · · , k
Romberg
Fórmula de quadratura
Regras simples
Regras compostas
Erro de quadratura
Acceleração da convergência
Algoritmo de Romberg
A sucessão assim construida pode ser organisada da seguinte forma
R(0, 0)
R(1, 0)
R(2, 0)
..
.
R(1, 1)
R(2, 1)
..
.
R(2, 2)
..
.
R(n, 0)
R(n, 1)
R(n, 2)
Cálculo Numérico - Integração numérica
···
R(n, n)
Romberg
Fórmula de quadratura
Regras simples
Regras compostas
Erro de quadratura
Acceleração da convergência
Exemplo 5. Aplicando a regra do trapézio para aproximar o integral
Z π
sin x dx = 2
0
obtem-se a seguinte tabela
m
1
2
4
8
10
12
Cálculo Numérico - Integração numérica
ITm (f )
0
1.570796326794897
1.896118897937040
1.974231601945551
1.993570343772340
1.998393360970145
I(f ) − ITm (f )
2
0.429203673205103
0.103881102062960
0.025768398054449
0.006429656227660
0.001606639029855
Romberg
Fórmula de quadratura
Regras simples
Regras compostas
Erro de quadratura
Acceleração da convergência
Aplicando o método de Romberg, obtem-se
n
0
1
2
3
4
5
R(n, 0)
0
1.57079633
1.89611890
1.97423160
1.99357034
1.99839336
R(n, 1)
R(n, 2)
R(n, 3)
R(n, 4)
R(n, 5)
2.09439510
2.00455975
2.00026917
2.00001659
2.00000103
1.99857073
1.99998313
1.99999975
2.0000000
2.0000055
2.0000001
2.0000000
1.9999999
2.0000000
2.0000000
Cálculo Numérico - Integração numérica
Romberg