Quadraturas de Löıc Cerf

Prévia do material em texto

Quadraturas
Löıc Cerf
1 Quadratura de Newton-Cotes
Algoritmo 1 Newton-Cotes
Entrada: a ∈ R, b ∈ R, f ∈ R[a;b], n ∈ {1; 2; 3; 4; 5; 6; 7; 8}, m ∈ N \ {0}
Sáıda: Integral ∈ R, Erro ∈ {verdadeiro; falso}
se resto(m,n) 6= 0 então
retorne 0, verdadeiro
fim se
d←
(
2 6 8 90 288 840 17280 28350
)
c←

1
1 4
1 3
7 32 12
19 75 50
41 216 27 272
751 3577 1323 2989
989 5888 −928 10496 −4540

h← (b− a)/m
v ←
(
0 · · · 0
)
{vetor de n zeros}
para i = 1→ m− 1 faça
v[resto(i, n) + 1]← v[resto(i, n) + 1] + f(a+ i× h)
fim para
Integral ← c[n, 1]× (f(a) + f(b) + 2× v[1])
para i = 2→ quociente(n+ 1, 2) faça
Integral ← Integral + c[n, i]× (v[i] + v[n− i+ 2])
fim para
se resto(n, 2) = 0 então
i← quociente(n, 2) + 1
Integral ← Integral + c[n, i]× v[i]
fim se
retorne n× h/d[n]×Integral, falso
1
2 Quadratura de Gauss-Legendre
2.1 Demonstração do método
Dados dois números reais a e b e uma função real f definida no intervalo [a; b],
a quadratura de Gauss-Legendre objetiva aproximar
∫ b
a
f .
Pela substituição de variável x = b−a2 t+
a+b
2 , temos
∫ b
a
f = b−a2
∫ 1
−1 F , onde
F é a função t 7→ f( b−a2 t +
a+b
2 ). Assim, reduzimos o problema da integração
no intervalo [a; b] ao problema da integração no intervalo [−1; 1].
O objetivo que guia a demonstração da quadratura de Gauss-Legendre é
a integração sem erro de f se f for um polinômio de grau 2n − 1 ou menor,
sendo n ∈ N \ {0} quantas vezes f será avaliada. Mais precisamente, queremos
calcular as abscissas (t1, . . . , tn) ∈ Rn e os pesos (ω1, . . . , ωn) ∈ Rn tal que∫ 1
−1 F =
∑n
i=1 ωiF (ti) se f for um polinômio de grau 2n − 1 ou menor. Por
definição, F é também um polinômio de grau 2n− 1 ou menor.
Teorema 1. A quadratura de Gauss-Legendre com n ∈ N \ {0} avaliações
da função a ser integrada é exata para qualquer polinômio de grau 2n − 1 ou
menor se e somente se ela for exata para os polinômios t0, t1, . . . , e t2n−1.
Formalmente:
∀F ∈ R[2n− 1],
∫ 1
−1
F =
n∑
i=1
ωiF (ti)⇔ ∀k = 0..2n− 1,
∫ 1
−1
tk dt =
n∑
i=1
ωit
k
i .
Demonstração 1. A implicação da esquerda para a direita é óbvia:
∀k = 1..2n− 1, tk ∈ R[2n− 1]
⇒
∫ 1
−1
tk dt =
n∑
i=1
ωit
k
i . (uso da hipótese)
A implicação da direita para a esquerda requer mais trabalho. Começamos por
escrever F (t) na forma padrão para um polinômio, ou seja, como uma com-
binação linear das potências de t:
∀F ∈ R[2n− 1], ∃(c0, . . . , c2n−1) ∈ R2n | F (t) =
2n−1∑
k=0
ckt
k .
2
Logo,∫ 1
−1
F =
∫ 1
−1
2n−1∑
k=0
ckt
k dt
=
2n−1∑
k=0
ck
∫ 1
−1
tk dt (linearidade de
∫ 1
−1
)
=
2n−1∑
k=0
ck
n∑
i=1
ωit
k
i (uso da hipótese)
=
2n−1∑
k=0
n∑
i=1
ckωit
k
i (distributividade de × em relação a +)
=
n∑
i=1
2n−1∑
k=0
ckωit
k
i (comutatividade de +)
=
n∑
i=1
ωi
2n−1∑
k=0
ckt
k
i (distributividade de × em relação a +)
=
n∑
i=1
ωiF (ti) . (definição de F )
Por Teorema 1, a integração sem erro de qualquer polinômio de grau 2n− 1
ou menor equivale a este sistema de 2n equações não lineares:
∀k = 0..2n− 1,
n∑
i=1
ωit
k
i =
∫ 1
−1
tk dt =
[
tk+1
k + 1
]1
−1
=
1− (−1)k+1
k + 1
. (1)
Seja π o polinômio mônico de grau n cujos zeros são t1, t2, . . . , tn, ou seja,
π(t) =
∏n
i=1(t− ti). Como qualquer polinômio, π(t) se expressa também como
uma combinação linear das potências de t:
∃(c0, . . . , cn−1) ∈ Rn | π(t) =
n∑
k=0
ckt
k, com cn = 1 .
Vamos calcular os coeficientes c0, c1, . . . , cn−1 para conhecer π e assim
poder calcular seus zeros t1, t2, . . . , tn. Para isso, consideramos combinações
lineares de n+ 1 equações sucessivas do sistema (1), ou seja, das suas equações
com k = 0..n, k = 1..n + 1, . . . , k = n − 1..2n − 1. Os coeficientes usados em
3
qualquer uma dessas n combinações são c0, c1, . . . , cn:
∀j = 0..n− 1,
n∑
k=0
ck
1− (−1)k+j+1
k + j + 1
=
n∑
k=0
ck
n∑
i=1
ωit
k+j
i
=
n∑
k=0
n∑
i=1
ckωit
k+j
i (distributividade)
=
n∑
i=1
n∑
k=0
ckωit
k+j
i (comutatividade)
=
n∑
i=1
ωit
j
i
n∑
k=0
ckt
k
i (distributividade)
=
n∑
i=1
ωit
j
iπ(ti) (definição de π)
= 0 (∀i = 1..n, π(ti) = 0)
Resolvendo esse sistema linear de n equações e n variáveis, obtemos os coe-
ficientes c0, c1, . . . , cn−1, ou seja, conhecemos π
1. Calculamos numericamente
os zeros de π, ou seja, as abscissas t1, t2, . . . , tn.
Falta o cálculo dos pesos ω1, ω2, . . . , ωn. As abscissas t1, t2, . . . , tn
sendo agora conhecidas, o sistema (1) é um sistema de 2n equações lineares
e n varáveis. Porém calculamos os coeficientes c0, c1, . . . , cn−1 e, em seguida,
as abscissas t1, t2, . . . , tn de tal forma que:
∀j = 0..n− 1,
n∑
k=0
ck
n∑
i=1
ωit
k+j
i =
n∑
k=0
ck
1− (−1)k+j+1
k + j + 1
= 0 .
Em outros termos, existe uma dependência linear entre quaisquer n + 1
equações sucessivas do sistema (1). Por isso, obtemos um sistema equivalente
ao remover de cada dependência linear uma equação multiplicada por um coe-
ficiente não nulo. Removendo a última equação, multiplicada por cn = 1 6= 0,
de cada dependência linear, sobram as n primeiras equações do sistema (1):
∀k = 0..n− 1,
n∑
i=1
ωit
k
i =
1− (−1)k+1
k + 1
.
Resolvendo esse sistema linear de n equações e n variáveis, obtemos os pesos
ω1, ω2, . . . , ωn.
Notando Pn−1 o polinômio de grau n − 1 que interpola os pontos da curva
de f de abscissas b−a2 t1 +
a+b
2 ,
b−a
2 t2 +
a+b
2 , . . . ,
b−a
2 tn +
a+b
2 , a quadratura de
Gauss-Legendre com n pontos calcula
∫ b
a
Pn−1:∫ b
a
Pn−1 =
b− a
2
n∑
i=1
ωiPn−1(
b−a
2 ti +
a+b
2 ) (Pn−1 tem grau n− 1 ≤ 2n− 1)
=
b− a
2
n∑
i=1
ωif(
b−a
2 ti +
a+b
2 ) (Pn−1 interpola f em
b−a
2 ti +
a+b
2 )
1Ele é o polinômio de Legendre de grau n vezes um escalar, o inverso do coeficiente ĺıder
do polinômio de Legendre de grau n (que não é 1 como escolhemos arbitrariamente para π).
4
2.2 Algoritmo
Desconsiderando o cálculo das ráızes não negativas t1, t2, . . . , tdn2 e do polinômio
de Legendre de grau n e dos pesos ω1, ω2, . . . , ωdn2 e associados, a quadratura
de Gauss-Legendre com n pontos, b−a2
∑n
i=1 ωif(
b−a
2 ti +
a+b
2 ), é calculada em
um tempo que é o das n avaliações de f mais O(n) operações aritméticas.
Algoritmo 2 Gauss-Legendre
Entrada: a ∈ R, b ∈ R, f ∈ R[a;b], n ∈ N \ {0}
Sáıda: Integral ∈ R
(T,W )← Gauss-Legendre-AbsPes(n)
Integral ← 0
ba2← (b− a)/2
ab2← (a+ b)/2
impar ← resto(n, 2)
se impar = 1 então
Integral ←W [1]× f(ab2)
fim se
para i = 1 + impar → quociente(n, 2) + impar faça
z ← ba2× T [i]
Integral ← Integral + W [i]× (f(ab2− z) + f(ab2 + z))
fim para
retorne ba2×Integral
2.3 Ausência do fenômeno de Runge
Teorema 2. ∀n ∈ N \ {0}, os pesos da quadratura de Gauss-Legendre com n
pontos são positivos.
Demonstração 2. ∀n ∈ N \ {0}, ∀k = 1..n, seja Fk o seguinte polinômio:
Fk(t) =

n∏
j = 1
j 6= k
t− tj
tk − tj

2
com t1, t2, . . . , tn as abscissas da quadratura de Gauss-Legendre com n pontos.
Ela calcula
∫ 1
−1 Fk de forma exata, ou seja,
∫ 1
−1 Fk =
∑n
i=1 ωiFk(ti), já que o
grau de Fk é 2(n − 1) ≤ 2n − 1. Por definição de Fk, temos Fk(tk) = 1 e
∀i ∈ {1, . . . , n} \ {k}, Fk(ti) = 0. Logo,
∫ 1
−1 Fk = ωk. Também por definição,
Fk ≥ 0, o que implica
∫ 1
−1 Fk ≥ 0 e, usando a igualidade anterior, ωk ≥ 0.
5
Teorema 3. Dada qualquer função real f cont́ınua no intervalo [a; b], a qua-
dratura de Gauss-Legendre com n pontos, In(f) =
b−a
2
∑n
i=1 ωif(
b−a
2 ti +
a+b
2 ),
converge para
∫ b
a
f quando n→ +∞.
Demonstração 3. Seja En(f) =
∫ b
a
f − In(f). Por definição do limite, quer-
emos provar que ∀ε > 0, ∃N ∈ N tal que ∀n > N , |En(f)| < ε. A função f
sendo cont́ınua em [a; b], o teorema da aproximação de Weierstrass garante a
existência de um polinômio p tal que:
∀x ∈ [a; b], |(f − p)(x)| < ε
2|b− a|
. (2)
Adicionando a En(f) os termos
∫ b
a
p, In(p) e os opostos deles, temos:
En(f) =
∫ b
a
f −
∫ b
a
p+
∫ b
a
p− In(p) + In(p)− In(f) .
Por linearidade de
∫ b
a
e de
∑n
i=1 respectivamente,
∫ b
af −
∫ b
a
p =
∫ b
a
(f − p) e
In(p)− In(f) = b−a2
∑n
i=1 ωi(p− f)(
b−a
2 ti +
a+b
2 ). Logo:
En(f) =
∫ b
a
(f − p) +
∫ b
a
p− In(p) +
b− a
2
n∑
i=1
ωi(p− f)( b−a2 ti +
a+b
2 ) .
Por desigualidade triangular de |.|:
|En(f)| ≤
∣∣∣∣∣
∫ b
a
(f − p)
∣∣∣∣∣+
∣∣∣∣∣
∫ b
a
p− In(p)
∣∣∣∣∣+ |b− a|2
n∑
i=1
|ωi|
∣∣(p− f)( b−a2 ti + a+b2 )∣∣ .
Por (2),
∣∣∣∫ ba (f − p)∣∣∣ < |b−a| ε2|b−a| = ε2 . Qualquer que seja o grau g de p, defin-
imos N =
⌊
g
2
⌋
. Assim, ∀n > N , a quadratura de Gauss-Legendre In(p) fornece
o valor exato,
∫ b
a
p, pois g ≤ 2n− 1. Logo,
∣∣∣∫ ba p− In(p)∣∣∣ = 0. Finalmente:
|b− a|
2
n∑
i=1
|ωi|
∣∣(p− f)( b−a2 ti + a+b2 )∣∣
<
|b− a|
2
n∑
i=1
(
|ωi|
ε
2|b− a|
)
( b−a2 ti +
a+b
2 ∈ [a; b] e (2))
=
ε
4
n∑
i=1
|ωi| (distributividade)
=
ε
4
n∑
i=1
ωi (Teorema 2)
=
ε
2
(
n∑
i=1
ωi =
∫ 1
−1
1 dt = 2)
Somando:
∀n > N , |En(f)| <
ε
2
+ 0 +
ε
2
= ε .
6
Essa demonstração não se aplica à integração por Newton-Cotes, pois qual-
quer fórmula baseada em um polinômio interpolador de grau 10 ou maior tem
pelo menos um peso negativo. Em outros termos, para a integração por Newton-
Cotes, não existe um Teorema 2, usado perto do final da Demonstração 3.
Por avaliarem a função a ser integrada em abscissas igualmente espaçadas, as
fórmulas de Newton-Cotes baseadas em polinômios de graus elevados podem
sofrer do fenômeno de Runge: precisa compor as fórmulas para melhorar a ex-
atidão. Pelo contrário, a quadratura de Gauss-Legendre, que avalia preponder-
adamente a função a ser integrada perto dos extremos do intervalo de integração,
nunca sofre do fenômeno de Runge (Teorema 3) e não precisa ser composta.
Este documento está licenciado com uma Licença Creative Commons
Atribuição-CompartilhaIgual 4.0 Internacional.
7