Lagrange
Diferenças de Newton
Erro de interpolação
Fenômeno de Runge
Interpolação por intervalo
Splines
Mínimos quadrados
INTERPOLAÇÃO E APROXIMAÇÃO POLINOMIAL
Nadir Arada
Cálculo Numérico - Interpolação e aproximção polinomial
Lagrange
Diferenças de Newton
Erro de interpolação
Fenômeno de Runge
Interpolação por intervalo
Splines
Mínimos quadrados
Posição do problema geral
Considere a tabela seguinte
x0
y0
x1
y1
x2
y2
···
···
xn−1
yn−1
xn
yn
onde x0 , x1 , · · · , xn são distictos.
Objectivo: Encontrar um polinómio Π n de grau n tal que
Πn (xi ) = yi
i = 0, 1, 2, · · · , n
O polinómio é chama-se polinómio de interpolação nos pontos x i ,
i = 0, 1, 2, · · · , n.
Cálculo Numérico - Interpolação e aproximção polinomial
Lagrange
Diferenças de Newton
Erro de interpolação
Fenômeno de Runge
Interpolação por intervalo
y0
Πn
y1
yn
y2
x0 x1
x2
xn
Exemplo de um polinómio de interpolação de grau 3
Cálculo Numérico - Interpolação e aproximção polinomial
Splines
Mínimos quadrados
Lagrange
Diferenças de Newton
Erro de interpolação
Fenômeno de Runge
Interpolação por intervalo
Splines
Mínimos quadrados
Caso particular: Interpolação de uma função continua
Seja f ∈ C([a, b]) e sejam x0 , x1 , · · · , xn , n + 1 pontos em [a, b]. Se
consideramos
yi = f (xi )
então o polinómio Πn chama-se polinómio interpolador de f nos
pontos (xi =i=0,··· ,n , e usa-se a notação Πn f (x).
Πn
f
x0
Cálculo Numérico - Interpolação e aproximção polinomial
x1
xn
Lagrange
Diferenças de Newton
Erro de interpolação
Fenômeno de Runge
Interpolação por intervalo
Splines
Mínimos quadrados
Base de Lagrange
Considere os polinómios ϕk ∈ P
I n [x], k = 0, 1, · · · , n, definidos por
n
Y
(x − xi )
ϕk (x) =
(xk − xi )
i=0
i6=k
É facile verificar que
(
ϕk (xk ) = 1
ϕk (xi ) = 0
e que (ϕk )k=0,1,··· ,n é uma base de P
I n [x]
Cálculo Numérico - Interpolação e aproximção polinomial
se i 6= k
Lagrange
Diferenças de Newton
Erro de interpolação
Fenômeno de Runge
Interpolação por intervalo
Splines
Mínimos quadrados
Exemplo 1. Para n = 1, x0 = −1 e x1 = 1, os polinómios da base de
Lagrange são
ϕ0 (x) =
x − x1
1
= − (x − 1)
x0 − x 1
2
e
ϕ1 (x) =
x − x0
1
= (x + 1)
x1 − x 0
2
Exemplo 2. Para n = 2, x0 = −1, x1 = 0 e x2 = 1, os polinómios da
base de Lagrange são

(x − x1 )(x − x2 )
1


ϕ0 (x) =
= x(x − 1)


(x0 − x1 )(x0 − x2 )
2




(x − x0 )(x − x2 )
ϕ1 (x) =
= −(x + 1)(x − 1)

(x1 − x0 )(x1 − x2 )





(x − x0 )(x − x1 )
1

 ϕ2 (x) =
= x(x + 1)
(x2 − x0 )(x2 − x1 )
2
Cálculo Numérico - Interpolação e aproximção polinomial
Lagrange
Diferenças de Newton
Erro de interpolação
ϕ0
Fenômeno de Runge
ϕ2
Interpolação por intervalo
ϕ1
Base de Lagrange para n = 2, x0 = −1, x1 = 0 e x2 = 1
Cálculo Numérico - Interpolação e aproximção polinomial
Splines
Mínimos quadrados
Lagrange
Diferenças de Newton
Erro de interpolação
Fenômeno de Runge
Interpolação por intervalo
Splines
Mínimos quadrados
Existência e unicidade do polinómio de interpolação
Teorema 1. Sejam x0 , x1 , · · · , xn , n + 1 pontos distinctos e sejam y0 ,
y1 , · · · , yn , os valores associados. O polinómio Π n ∈ P
I n [x] definido
por
n
X
Πn (x) =
yk ϕk (x)
k=0
é o único polinómio de interpolação nos pontos x i , i = 1, 2, · · · , n.
Cálculo Numérico - Interpolação e aproximção polinomial
Lagrange
Diferenças de Newton
Erro de interpolação
Fenômeno de Runge
Interpolação por intervalo
Splines
Mínimos quadrados
Demonstração. É facile verificar que para qualquer i = 0, 1, · · · , n,
tem-se
n
X
Πn (xi ) =
yk ϕk (xi ) = yi ϕ(xi ) = yi
k=0
o que prova que Πn é um polinómio de interpolação nos pontos x i .
Para provar a unicidade, suponha que existe um polinómio Q n ∈ P
I n [x]
tal que Qn (xi ) = yi . Então Πn − Qn ∈ P
I n [x] satisfaz
(Πn − Qn )(xi ) = 0
i = 0, 1, · · · , n
e portanto é identicamente nulo. Isto é Q n ≡ Πn
Cálculo Numérico - Interpolação e aproximção polinomial
Lagrange
Diferenças de Newton
Erro de interpolação
Fenômeno de Runge
Interpolação por intervalo
Splines
Mínimos quadrados
Exemplo. Considere a função f (x) = sin x em [0, 3π].
1. Grau n = 1 com x0 = 0 e x1 = 3π. Tem-se f (x0 ) = 0 e f (x1 ) = 0.
O polinómio interpolador de f nos pontos x 0 e x1 é
Π1 (x) = f (x0 ) × ϕ0 (x) + f (x1 )ϕ1 (x) = 0
2. Grau n = 2 com x0 = 0, x1 = 3π
2 e x2 = 3π. Tem-se f (x0 ) = 0,
f (x1 ) = −1 e f (x1 ) = 0. O polinómio interpolador de f nos pontos x 0 ,
x1 e x 2 é
Π2 (x) = f (x0 ) × ϕ0 (x) + f (x1 )ϕ1 (x) + f (x2 )ϕ2 (x)
= f (x1 )ϕ1 (x) = −ϕ1 (x)
=−
(x − x0 )(x − x2 )
4
= 2 x(x − 3π)
(x1 − x0 )(x1 − x2 )
9π
Cálculo Numérico - Interpolação e aproximção polinomial
Lagrange
Diferenças de Newton
Erro de interpolação
Fenômeno de Runge
Interpolação por intervalo
Π4 (x)
sin x
3
6
9
Π2 (x)
Interpolação de f (x) = sin x em [0, 3π]
Cálculo Numérico - Interpolação e aproximção polinomial
Splines
Mínimos quadrados
Lagrange
Diferenças de Newton
Erro de interpolação
Fenômeno de Runge
Interpolação por intervalo
Splines
Mínimos quadrados
Algoritmo de Newton- Diferenças divididas
Definição. O coeficiente de xn no polinómio de Lagrange Πn é notado
f [x0 , x1 , · · · , xn ]
e chama-se diferença dividida de ordem n dos dados (x i , yi )0≤i≤n .
Uma vez que
Πn (x) =
n
X
yk ϕk (x) =
k=0
tem-se
f [x0 , x1 , · · · , xn ] =
n
X
yk
k=0
n
X
k=0
n
Y
i=0
i6=k
Cálculo Numérico - Interpolação e aproximção polinomial
n
Y
x − xi
xk − x i
i=0
i6=k
yk
(xk − xi )
Lagrange
Diferenças de Newton
Erro de interpolação
Fenômeno de Runge
Interpolação por intervalo
Splines
Mínimos quadrados
Teorema. Seja Πn o polinómio de interpolação de Lagrange definido
por
Πn (xi ) = yi
i = 0, 1, · · · , n
e seja Πn+1 o polinómio de interpolação de Lagrange definido por
Πn+1 (xi ) = yi
i = 0, 1, · · · , n, n + 1
Então
Πn+1 (x) = Πn (x) + f [x0 , x1 , · · · , xn , xn+1 ]
n
Y
i=0
Cálculo Numérico - Interpolação e aproximção polinomial
(x − xi )
Lagrange
Diferenças de Newton
Erro de interpolação
Fenômeno de Runge
Interpolação por intervalo
Splines
Demonstração. Seja Qn+1 o polinómio definido por
Qn+1 (x) = Πn (x) + f [x0 , x1 , · · · , xn , xn+1 ]
n
Y
(x − xi )
i=0
Para qualquer xi , i = 0, 1, · · · , n, tem-se
(Qn+1 − Πn+1 ) (xi ) = Πn (xi ) − Πn+1 (xi ) = yi − yi = 0
Por outro lado, os polinómios Qn+1 e Πn+1 têm o mesmo o
coeficiente de maior grau. Assim
Qn+1 − Πn+1 é de grau n e tem n + 1 zeros
e portanto
Qn+1 = Πn+1
Cálculo Numérico - Interpolação e aproximção polinomial
Mínimos quadrados
Lagrange
Diferenças de Newton
Erro de interpolação
Fenômeno de Runge
Interpolação por intervalo
Splines
Mínimos quadrados
Consequência.
Π0 (x) = y0
Π1 (x) = Π0 (x) + f [x0 , x1 ](x − x0 )
= y0 + f [x0 , x1 ](x − x0 )
Π2 (x) = Π1 (x) + f [x0 , x1 , x1 ](x − x0 )(x − x1 )
= y0 + f [x0 , x1 ](x − x0 ) + f [x0 , x1 , x1 ](x − x0 )(x − x1 )
Cálculo Numérico - Interpolação e aproximção polinomial
Lagrange
Diferenças de Newton
Erro de interpolação
Fenômeno de Runge
Interpolação por intervalo
Splines
Mínimos quadrados
Por recorrência, deduz-se a forma de Newton com diferenças
divididas para o polinómio de interpolação
Πn (x) = y0
+f [x0 , x1 ](x − x0 )
+f [x0 , x1 , x2 ](x − x0 )(x − x1 )
+···
+f [x0 , x1 , · · · , xn ] (x − x0 )(x − x1 ) · · · (x − xn−1 )
Cálculo Numérico - Interpolação e aproximção polinomial
Lagrange
Diferenças de Newton
Erro de interpolação
Fenômeno de Runge
Interpolação por intervalo
Splines
Mínimos quadrados
Cálculo efectivo das diferenças divididas
Prova-se que a uma diferença de ordem n é relacionada com duas
diferenças de ordem (n − 1) do seguinte modo
f [xi , xi+1 , · · · , xi+k ] =
f [xi+1 , xi+1 , · · · , xi+k ] − f [xi , xi+1 , · · · , xi+k−1 ]
xi+k − xi
Na prática usa-se a tabela das diferenças divididas
x0
x1
x2
x3
y0
y1
y2
y3
= f [x0 ]
= f [x1 ]
= f [x2 ]
= f [x3 ]
f [x0 , x1 ]
f [x1 , x2 ]
f [x2 , x3 ]
f [x0 , x1 , x2 ]
f [x1 , x2 , x3 ]
f [x0 , x1 , x2 , x4 ]
Table: Organização das diferenças divididas de Newton
Cálculo Numérico - Interpolação e aproximção polinomial
Lagrange
Diferenças de Newton
Erro de interpolação
Fenômeno de Runge
Interpolação por intervalo
Splines
Mínimos quadrados
Exemplo. Considere a função f (x) = sin(πx) em [−1, 1] e seja Π 4 o
polinómio de interpolação de grau 4 nos pontos x i = −1 + 2i ,
i = 0, 1, · · · , 4. A tabela das diferenças divididas é dada por
−1
−0.5
0
−1
0
0.5
1
0
1
0
−1−0
−0.5−(−1) = −2
0−(−1)
0−(−0.5) = 2
1−0
0.5−0 = 2
0−1
1−0.5 = −2
2−(−2)
0−(−1) = 4
2−2
0.5−(−0.5) = 0
−2−2
1−0 = −4
0−4
0.5−(−1)
−4−0
1−(−0.5)
= − 83
= − 83
O polinómio de interpolação é
Π4 (x) = 0−2(x + 1) + 4(x + 1)(x + 0.5)− 83 (x + 1)(x + 0.5)x
+0(x + 1)(x + 0.5)x(x − 0.5)
= −2(x + 1) + 4(x + 1)(x + 0.5) − 83 (x + 1)(x + 0.5)x
Cálculo Numérico - Interpolação e aproximção polinomial
0
Lagrange
Diferenças de Newton
Erro de interpolação
Fenômeno de Runge
Interpolação por intervalo
Splines
Mínimos quadrados
Caso de pontos equidistantes: diferenças finitas
Consider a sucessão de dados (xi , yi )0≤i≤n . Defina-se o operador ∆yi
∆yi = yi+1 − yi
i = 0, 1, · · · n − 1
e, de modo recursivo, o operador de ordem superior ∆ k yi
∆k yi = ∆(∆k−1 yi )
k = 2, · · ·
A forma de interpolação de Newton com diferenças divididas é valida
no caso de uma distribução qualquer dos pontos de interpolação. Se a
distribução é uniforme com passo h, prova-se que
f [x0 , x1 , x2 , · · · , xn ] =
Cálculo Numérico - Interpolação e aproximção polinomial
1
∆n y0
n!hn
Lagrange
Diferenças de Newton
Erro de interpolação
Fenômeno de Runge
Interpolação por intervalo
Splines
Mínimos quadrados
Por conseguinte, obtem-se a forma de Newton com diferenças finitas
para o polinómio de interpolação
Πn (x) = y0
+
∆y0
(x − x0 )
h
+
∆2 y0
(x − x0 )(x − x1 )
2!h2
+···
+
∆n y0
(x − x0 )(x − x1 ) · · · (x − xn−1 )
n!hn
Cálculo Numérico - Interpolação e aproximção polinomial
Lagrange
Diferenças de Newton
Erro de interpolação
Fenômeno de Runge
Interpolação por intervalo
Splines
Cálculo efectivo das diferenças finitas
Na prática usa-se a tabela das diferenças finitas
x0
x1
x2
x3
x4
y0
y1
y2
y3
y4
∆y0
∆y1
∆y2
∆y3
∆2 y0
∆2 y1
∆2 y3
∆3 y0
∆3 y1
∆4 y0
Table: Organização das diferenças finitas de Newton
Cálculo Numérico - Interpolação e aproximção polinomial
Mínimos quadrados
Lagrange
Diferenças de Newton
Erro de interpolação
Fenômeno de Runge
Interpolação por intervalo
Splines
Mínimos quadrados
Exemplo. Considere a função f (x) = sin(πx) em [−1, 1] e seja Π 4 o
polinómio de interpolação de grau 4 nos pontos x i = −1 + 2i ,
i = 0, 1, · · · , 4. A tabela das diferenças finitas é dada por
−1
−0.5
0
0.5
1
0
−1
0
1
0
−1 − 0 = −1
0 − (−1) = 1
1−0=1
0 − 1 = −1
1 − (−1) = 2
1−1 =0
−1 − 1 = −2
0 − 2 = −2
−2 − 0 = −2
0
O polinómio de interpolação é
1
Π4 (x) = 0− 1!(0.5)
(x + 1) +
2
(x
2!(0.5)2
2
− 3!(0.5)
3 (x + 1)(x + 0.5)x +
+ 1)(x + 0.5)
0
(x
4!(0.5)4
+ 1)(x + 0.5)x(x − 0.5)
= −2(x + 1) + 4(x + 1)(x + 0.5) − 83 (x + 1)(x + 0.5)x
Cálculo Numérico - Interpolação e aproximção polinomial
Lagrange
Diferenças de Newton
Erro de interpolação
Fenômeno de Runge
Interpolação por intervalo
Splines
Mínimos quadrados
Erro de interpolação de uma função regular
Teorema 2. Seja f ∈ C n+1 ([a, b]) e seja Πn o polinómio interpolador
de f nos pontos x0 , x1 , · · · , xn . Então para qualquer x ∈ [a, b], existe
ζ(x) ∈ [a, b] tal que o erro de interpolação f − Π n satisfaz
n
f (n+1) (ζ) Y
f (x) − Πn (x) =
(x − xi )
(n + 1)!
i=0
Demonstração. 1. Se x = xi , i = 0, 1, · · · , n, então o resultado é
sempre valido.
Cálculo Numérico - Interpolação e aproximção polinomial
Lagrange
Diferenças de Newton
Erro de interpolação
Fenômeno de Runge
Interpolação por intervalo
Splines
2. Se x 6= xi , considere-se a função
F(t) = f (t) − Πn (t) −
onde ωn (x) =
n
Y
f (x) − Πn (x)
ωn (t)
ωn (x)
(x − xi ) = (x − x0 )(x − x1 ) · · · (x − xn )
i=0
É facile ver que
F(x) = 0
e
F(xi ) = 0
∀ i = 0, 1, · · · , n
e portanto
F tem pelo menos n + 2 zeros em [a, b]
Cálculo Numérico - Interpolação e aproximção polinomial
Mínimos quadrados
Lagrange
Diferenças de Newton
Erro de interpolação
Fenômeno de Runge
Interpolação por intervalo
Aplicando o teorema de Rolle, conclui-se que
F 0 tem pelo menos n + 1 zeros em [a, b]
F” tem pelo menos n zeros em [a, b]
···
F (n+1) tem pelo menos 1 zero em [a, b]
Existe então ζ ∈]a, b[ tal que
F (n+1) (ζ) = 0
Cálculo Numérico - Interpolação e aproximção polinomial
Splines
Mínimos quadrados
Lagrange
Diferenças de Newton
Erro de interpolação
Fenômeno de Runge
Interpolação por intervalo
Splines
Mínimos quadrados
Uma vez que
(n+1)
F (n+1) (t) = f (n+1) (t) − Πn
= f (n+1) (t) −
(t) −
f (x)−Πn (x)
ωn (x) (n
f (x)−Πn (x)
(ωn (t))(n+1)
ωn (x)
+ 1)!
conclui-se que
f (n+1) (ζ) −
f (x) − Πn (x)
(n + 1)! = 0
ωn (x)
Isto é
f (x) − Πn (x) =
Cálculo Numérico - Interpolação e aproximção polinomial
f (n+1) (ζ)
ωn (x)
(n + 1)!
Lagrange
Diferenças de Newton
Erro de interpolação
Fenômeno de Runge
Interpolação por intervalo
Splines
Mínimos quadrados
Erro de interpolação no caso de uma distribução de pontos
uniforme
Teorema 2. Seja f ∈ C n+1 ([a, b]) e seja Πn o polinómio interpolador
de f nos pontos equidistantes (xi )0≤i≤n definidos por
xi = a + i h
com h =
b−a
n
Então, o erro de interpolação f − Πn satisfaz
max |f (x) − Πn (x)| ≤ max f (n+1) (x)
x∈[a,b]
Cálculo Numérico - Interpolação e aproximção polinomial
x∈[a,b]
hn+1
4(n + 1)
Lagrange
Diferenças de Newton
Erro de interpolação
Fenômeno de Runge
Interpolação por intervalo
Splines
Mínimos quadrados
Demonstração. Do teorema precedente, sabe-se que para quelquar
x ∈ [a, b] existe ζ ∈ [a, b] tal que
n
(n+1) Y
f
(ζ)
|f (x) − Πn (x)| = (n+1)!
(x − xi )
i=0
n
|f (n+1) (ζ)| Y
= (n+1)! (x − xi )
i=0
max f (n+1) (ζ) Y
n
x∈[a,b]
≤
(x − xi )
(n+1)!
i=0
n
Y
Falta estimar (x − xi ) .
i=0
Cálculo Numérico - Interpolação e aproximção polinomial
Lagrange
Diferenças de Newton
Erro de interpolação
Fenômeno de Runge
Interpolação por intervalo
Splines
Mínimos quadrados
Uma vez que x ∈]x0 , xn [, então existe um intervalo ]xi , xi+1 [ tal que
x ∈]xi , xi+1 [. Suponha, para simplificar, que x ∈]x 0 , x1 [.
|x − x2 | ≤ |x − x1 | + |x1 − x2 | ≤ 2h
|x − x3 | ≤ |x − x2 | + |x2 − x3 | ≤ 3h
···
|x − xn | ≤ |x − xn−1 | + |xn−1 − xn | ≤ nh
Portanto
n
n
Y
Y
(x
−
x
)
=
|(x
−
x
)(x
−
x
)|
|x − xi |
i 0
1
i=0
i=2
≤ |(x − x0 )(x − x1 )| (2h)(3h) · · · (nh)
= (x − x0 )(x1 − x) n!hn−1
Cálculo Numérico - Interpolação e aproximção polinomial
Lagrange
Diferenças de Newton
Erro de interpolação
Fenômeno de Runge
Interpolação por intervalo
Splines
Mínimos quadrados
No intervalo [x0 , x1 ] a função (x − x0 )(x − x1 ) atinge o seu máximo no
1
ponto x∗ = x0 +x
2 . Portanto
(x − x0 )(x1 − x) ≤ (x∗ − x0 )(x1 − x∗ )
1
h2
= (x1 − x0 )2 =
4
4
Assim
e
n
Y
hn+1
h2
n!hn−1 =
n!
(x − xi ) ≤
4
4
i=0
max f (n+1) (ζ) Y
n
x∈[a,b]
|f (x) − Πn (x)| ≤
(x
−
x
)
i (n+1)!
i=0
max f (n+1) (ζ)
x∈[a,b]
≤
hn+1
4(n+1)
Cálculo Numérico - Interpolação e aproximção polinomial
Lagrange
Diferenças de Newton
Erro de interpolação
Fenômeno de Runge
Interpolação por intervalo
Splines
Mínimos quadrados
Observação. Este resultado é interessante se a quantidade
max f (n+1) (x) x∈[a,b]
b − a n+1
En =
4(n + 1)
n
tende para zero. É suficiente, por exemplo, existir M > 0
independente de n tal que
(n+1) max f
(x) ≤ M
x∈[a,b]
Assim
lim En = 0
n→+∞
o que garante a convergência do método para um grau de interpolação
suficientemente elevado.
Cálculo Numérico - Interpolação e aproximção polinomial
Lagrange
Diferenças de Newton
Erro de interpolação
Fenômeno de Runge
Interpolação por intervalo
Splines
Mínimos quadrados
Exemplo. Considere a função f (x) = sin(πx) em [−1, 1] e seja Π n o
polinómio de interpolação de grau n nos pontos equidistantes
xi = −1 + 2in , i = 0, 1, · · · , n.
Uma vez que
(n+1) (x) ≤ π n+1
f
∀ x ∈ [−1, 1]
conclui-se que o erro de interpolação satisfaz
max |sin(πx) − Πn (x)| ≤
x∈[−1,1]
−→ 0
Cálculo Numérico - Interpolação e aproximção polinomial
π n+1
4(n + 1)
quando n → +∞
n+1
2
n
Lagrange
Diferenças de Newton
Erro de interpolação
Fenômeno de Runge
Interpolação por intervalo
Splines
0.5
−1.0
−0.5
0
0.5
Função erro E4 (x) = |sin(πx) − Π4 (x)|
Cálculo Numérico - Interpolação e aproximção polinomial
1.0
Mínimos quadrados
Lagrange
Diferenças de Newton
Erro de interpolação
Fenômeno de Runge
Interpolação por intervalo
Splines
0.05
−1.0
−0.8
−0.6
−0.4
−0.2
0
0.2
0.4
Função erro E5 (x) = |sin(πx) − Π5 (x)|
Cálculo Numérico - Interpolação e aproximção polinomial
0.6
0.8
1.0
Mínimos quadrados
Lagrange
Diferenças de Newton
Erro de interpolação
Fenômeno de Runge
Interpolação por intervalo
Splines
0.005
−1.00
−0.75
−0.50
−0.25
0
0.25
0.50
Função erro E8 (x) = |sin(πx) − Π8 (x)|
Cálculo Numérico - Interpolação e aproximção polinomial
0.75
1.00
Mínimos quadrados
Lagrange
Diferenças de Newton
Erro de interpolação
Fenômeno de Runge
Interpolação por intervalo
Splines
Mínimos quadrados
1
Exemplo. Considere a função de Runge f (x) = 1+x
2 definida em
[−5, 5] e seja Πn o polinómio interpolador de f nos pontos
equidistantes xi = −5 + 10i
n , i = 0, 1, · · · , n.
1.5
1.0
0.5
−5
−4
−3
−2
−1
0
1
2
3
4
Interpolação da função de Runge com 6 pontos equidistantes
Cálculo Numérico - Interpolação e aproximção polinomial
5
Lagrange
Diferenças de Newton
Erro de interpolação
Fenômeno de Runge
Interpolação por intervalo
Splines
Mínimos quadrados
No caso de pontos equidistantes, o polinómio interpolador apresenta
oscilações na vizinhança das extremidades do intervalo. Estas
oscilações crescem com o numéro de pontos.
1.5
1.0
0.5
−5
−4
−3
−2
−1
0
1
2
3
4
Interpolação da função de Runge com 11 pontos equidistantes
Cálculo Numérico - Interpolação e aproximção polinomial
5
Lagrange
Diferenças de Newton
Erro de interpolação
Fenômeno de Runge
Interpolação por intervalo
Splines
1.5
1.0
0.5
3
4
Distribução uniforme dos pontos- Função erro E6 (x) =
1
1+x2
−5
−4
−3
−2
Cálculo Numérico - Interpolação e aproximção polinomial
−1
0
1
2
5
− Π6 (x)
Mínimos quadrados
Lagrange
Diferenças de Newton
Erro de interpolação
Fenômeno de Runge
Interpolação por intervalo
Splines
1.5
1.0
0.5
3
4
Distribução uniforme dos pontos- Função erro E11 (x) =
1
1+x2
−5
−4
−3
−2
Cálculo Numérico - Interpolação e aproximção polinomial
−1
0
1
2
5
− Π11 (x)
Mínimos quadrados
Lagrange
Diferenças de Newton
Erro de interpolação
Fenômeno de Runge
Interpolação por intervalo
Splines
Mínimos quadrados
Remédio. Considerar como pontos de interpolação, os pontos de
Chebyshev definidos no intervalo [a, b] por
b−a
iπ
i = 0, 1, · · · , n
xi = a+b
2 − 2 cos n ,
1.0
0.5
−5
−4
−3
−2
−1
0
1
2
3
4
Interpolação da função de Runge com 6 pontos de Chebychev
Cálculo Numérico - Interpolação e aproximção polinomial
5
Lagrange
Diferenças de Newton
Erro de interpolação
Fenômeno de Runge
Interpolação por intervalo
Splines
Mínimos quadrados
As oscilações desaparacem e o erro diminua quando o número de
pontos de Chebychev cresce
1.0
0.5
−5
−4
−3
−2
−1
0
1
2
3
4
5
Interpolação da função de Runge com 11 pontos de Chebychev
Cálculo Numérico - Interpolação e aproximção polinomial
Lagrange
Diferenças de Newton
Erro de interpolação
Fenômeno de Runge
Interpolação por intervalo
Splines
1.5
1.0
0.5
2
3
Pontos de Chebychev- Função erro E6 (x) =
1
1+x2
−5
−4
−3
−2
Cálculo Numérico - Interpolação e aproximção polinomial
−1
0
1
4
− Π6 (x)
5
Mínimos quadrados
Lagrange
Diferenças de Newton
Erro de interpolação
Fenômeno de Runge
Interpolação por intervalo
Splines
1.5
1.0
0.5
2
3
Pontos de Chebychev- Função erro E11 (x) =
1
1+x2
−5
−4
−3
−2
Cálculo Numérico - Interpolação e aproximção polinomial
−1
0
1
4
− Π11 (x)
5
Mínimos quadrados
Lagrange
Diferenças de Newton
Erro de interpolação
Fenômeno de Runge
Interpolação por intervalo
Splines
Mínimos quadrados
Outro Remédio: Interpolação linear por intervalo
Sejam x0 = a < x1 < x2 < · · · < xn = b, (n + 1) pontos que
subdivisam o intervalo [a, b] em n subintervalos I k = [xk , xk+1 ] de
cumprimento h = b−a
n .
Ideia. Em cada subintervalo Ik , interpolar f|Ik por um polinómio Πh1 de
grau 1. É facile de ver que
Πh1 (x) = f (xk ) +
f (xk+1 ) − f (xk )
(x − xk )
xk+1 − xk
Cálculo Numérico - Interpolação e aproximção polinomial
x ∈ Ik
Lagrange
Diferenças de Newton
Erro de interpolação
Fenômeno de Runge
Interpolação por intervalo
Splines
Mínimos quadrados
Exemplo. Consideram-se os polinómios Π h1 linear por secção que
interpolam a função de Runge em [−5, 5] com 5 e 10 subintervalos.
1.0
0.5
−5
−4
−3
−2
−1
0
1
2
3
4
Interpolação da função de Runge por Πh1 com h = 2
Cálculo Numérico - Interpolação e aproximção polinomial
5
Lagrange
Diferenças de Newton
Erro de interpolação
Fenômeno de Runge
Interpolação por intervalo
Splines
1.0
0.5
−5
−4
−3
−2
−1
0
1
2
3
4
Interpolação da função de Runge por Πh1 com h = 1
Cálculo Numérico - Interpolação e aproximção polinomial
5
Mínimos quadrados
Lagrange
Diferenças de Newton
Erro de interpolação
Fenômeno de Runge
Interpolação por intervalo
Splines
0.5
−5
−4
−3
−2
−1
Função erro Eh (x) =
Cálculo Numérico - Interpolação e aproximção polinomial
0
1
1+x2
1
2
3
4
− Πh1 (x) com h = 2
5
Mínimos quadrados
Lagrange
Diferenças de Newton
Erro de interpolação
Fenômeno de Runge
Interpolação por intervalo
Splines
0.5
−5
−4
−3
−2
−1
Função erro Eh (x) =
Cálculo Numérico - Interpolação e aproximção polinomial
0
1
1+x2
1
2
3
4
− Πh1 (x) com h = 1
5
Mínimos quadrados
Lagrange
Diferenças de Newton
Erro de interpolação
Fenômeno de Runge
Interpolação por intervalo
Splines
Mínimos quadrados
Teorema. Seja f ∈ C 2 ([a, b]) e sejam x0 = a < x1 < · · · < xn = b,
(n + 1) pontos que subdivisam o intervalo [a, b] em n subintervalos
Ik = [xk , xk+1 ] de cumprimento h = b−a
n . Então
h2
max f (x) − Πhi (x) ≤
max |f ”(x)|
8 x∈[a,b]
x∈[a,b]
Demonstração. Da formula do erro de interpolação de uma função
regular, deduz-se que em cada subintervalo I k , tem-se
h2
max f (x) − Πhi (x) ≤
max |f ”(x)|
x∈Ik
8 x∈Ik
O resultado é uma consequência directa desta estimativa
Cálculo Numérico - Interpolação e aproximção polinomial
Lagrange
Diferenças de Newton
Erro de interpolação
Fenômeno de Runge
Interpolação por intervalo
Splines
Mínimos quadrados
Interpolação por intervalo com polinómios de grau n
Se f ∈ C(n+1) ([a, b]), em vez de uma interpolação linear, podemos
considerar polinómios de interpolação de grau superior em cada
subintervalo.
Do mesmo modo, tem-se a estimativa do erro
max f (x) − Πhi (x) ≤
x∈[a,b]
Cálculo Numérico - Interpolação e aproximção polinomial
hn+1
max f (n+1) (x)
4(n + 1) x∈[a,b]
Lagrange
Diferenças de Newton
Erro de interpolação
Fenômeno de Runge
Interpolação por intervalo
Splines
Mínimos quadrados
Exemplo. Considere o polinómio Πh2 de grau 2 que interpola a função
de Runge em [−5, 5] com 5 subintervalos.
1.0
0.5
−5
−4
−3
−2
−1
0
1
2
3
4
Interpolação da função de Runge por Πh2 com h = 2
Cálculo Numérico - Interpolação e aproximção polinomial
5
Lagrange
Diferenças de Newton
Erro de interpolação
Fenômeno de Runge
Interpolação por intervalo
Splines
1.0
0.5
−5
−4
−3
−2
−1
Função erro Eh (x) =
Cálculo Numérico - Interpolação e aproximção polinomial
0
1
1+x2
1
2
3
4
− Πh2 (x) com h = 2
5
Mínimos quadrados
Lagrange
Diferenças de Newton
Erro de interpolação
Fenômeno de Runge
Interpolação por intervalo
Splines
Mínimos quadrados
Interpolação por splines cúbicos
Ideia. Interpolação local (por intervalo) com polinómios de grau 3 de
modo a garantir que a função interpoladora seja suficientemente
regular sem apresentar oscilações
Definição. Um spline cubico de interpolação é uma função g tal que
I
I
I
g(xi ) = yi , i = 0, 1, · · · , n
Em cada subintervalo [xi , xi+1 ], g coincide com um polinómio de
grau 3
g ∈ C2 [a, b]
Cálculo Numérico - Interpolação e aproximção polinomial
Lagrange
Diferenças de Newton
Erro de interpolação
Fenômeno de Runge
Interpolação por intervalo
Splines
Mínimos quadrados
Determinação do spline
Seja gi o polinómio de grau 3 que coincide com g em [x i , xi+1 ]. Neste
subintervalo a função gi ” é um polinómio de grau 1 e é determinada
por dois valores
mi = gi ”(xi )
e
mi+1 = gi ”(xi+1 )
Isto é, para qualquer x ∈ [xi , xi+1 ], tem-se
gi ”(x) = mi+1
com hi = xi+1 − xi
Cálculo Numérico - Interpolação e aproximção polinomial
x − xi
xi+1 − x
+ mi
hi
hi
Lagrange
Diferenças de Newton
Erro de interpolação
Fenômeno de Runge
Interpolação por intervalo
Splines
Mínimos quadrados
Integrando uma primeira, e depois uma segunda vez obtem-se
g0i (x) = mi+1
(x − xi )2
(xi+1 − x)2
− mi
+ ai
2hi
2hi
e
gi (x) = mi+1
(x − xi )3
(xi+1 − x)3
+ mi
+ ai (x − xi ) + bi
6hi
6hi
onde ai e bi são constantes a determinar
Cálculo Numérico - Interpolação e aproximção polinomial
Lagrange
Diferenças de Newton
Erro de interpolação
Fenômeno de Runge
Interpolação por intervalo
Splines
Mínimos quadrados
Utilizando o facto que xi e xi+1 são pontos de interpolação, obtem-se
(
gi (xi ) = yi
gi (xi+1 ) = yi+1
⇐⇒

2
 y i = m i hi + b i
6

yi+1 = mi+1
h2i
6
+ a i hi + b i

 b = y − m h2i
i
i
i 6
⇐⇒
 a = 1 (y − y ) −
i
i
hi i+1
Cálculo Numérico - Interpolação e aproximção polinomial
hi
6 (mi+1
− mi )
Lagrange
Diferenças de Newton
Erro de interpolação
Fenômeno de Runge
Interpolação por intervalo
Splines
Mínimos quadrados
Portanto, para x ∈ [xi , xi+1 ], o spline cúbico gi escreve-se
2
mi
3 + mi+1 (x − x )3 + 1 y − m hi (x
gi (x) = 6h
(x
−
x)
i+1
i
i
i 6
i+1 − x)
6hi
hi
i
h2
+ h1i yi+1 − mi+1 6i (x − xi )
i = 0, 1, · · · , n − 1
Por outro lado, uma vez que g0 é contínua, para i = 1, 2, · · · , n − 1,
tem-se
g0i (xi ) = g0i−1 (xi )
⇐⇒
Cálculo Numérico - Interpolação e aproximção polinomial
−mi
hi
hi−1
+ ai = mi
+ ai−1
2
2
Lagrange
Diferenças de Newton
Erro de interpolação
Fenômeno de Runge
Interpolação por intervalo
Splines
Mínimos quadrados
Por conseguinte, para i = 1, · · · , n − 1, os coeficientes m i satisfazam
as equações
yi+1 − yi yi − yi−1
hi−1 mi−1 + 2(hi + hi−1 ) mi + hi mi+1 = 6
−
hi
hi−1
Tem-se n + 1 incógnitas m0 , m1 , · · · , mn−1 , mn e n − 1 equações.
Precisamos de mais duas condições. Existem varias possibilidades.
Por exemplo
m0 = m n = 0
Spline natural
Cálculo Numérico - Interpolação e aproximção polinomial
Lagrange
Diferenças de Newton
Erro de interpolação
Fenômeno de Runge
Interpolação por intervalo
Splines
Mínimos quadrados
Observação. O sistema obtido pode ser escrito na forma matricial

 

m1
s1

 

 m   s 
2 

 2 

 

 .   . 



A  ..  =  .. 
,

 


 

 mn−2   sn−2 

 

mn−1
sn−1
onde
si = 6
Cálculo Numérico - Interpolação e aproximção polinomial
yi+1 − yi yi − yi−1
−
hi
hi−1
Lagrange
Diferenças de Newton
Erro de interpolação
Fenômeno de Runge
Interpolação por intervalo
Splines
Mínimos quadrados
e onde A é uma matriz tridiagonal dependente de h i , i = 1, · · · , n − 1
dada por












2(h0 + h1 )
h1
0
0
···
0
h1
2(h1 + h2 )
h2
0
···
0
0
h2
2(h2 + h3 )
h3
···
0
..
.
..
.
..
.
..
.
..
.
..
.
0
···
hn−2
2(hn−2 + hn−1 )
hn−1
0
0
···
···
0
hn−2
2(hn−1 + hn )
Cálculo Numérico - Interpolação e aproximção polinomial












Lagrange
Diferenças de Newton
Erro de interpolação
Fenômeno de Runge
Interpolação por intervalo
Splines
1
−5
−4
−3
−2
−1
0
1
2
3
4
5
Interpolação por spline natural da função de Runge com n = 5
Cálculo Numérico - Interpolação e aproximção polinomial
Mínimos quadrados
Lagrange
Diferenças de Newton
Erro de interpolação
Fenômeno de Runge
Interpolação por intervalo
Splines
1
−5
−4
−3
−2
−1
0
1
2
3
4
5
Função de Runge: interpolação por spline cúbico com n = 10
Cálculo Numérico - Interpolação e aproximção polinomial
Mínimos quadrados
Lagrange
Diferenças de Newton
Erro de interpolação
Fenômeno de Runge
Interpolação por intervalo
Splines
Mínimos quadrados
Aproximação no sentido dos mínimos quadrados
Considere-se n + 1 pontos x0 , x1 , · · · , xn e medidas associadas y0 , y1 ,
· · · , yn . Para 1 ≤ m << n, procura-se um polinómio P m de grau m
que aproxima os dados no sentido dos mínimos quadrados, isto é tal
que
n
n
X
X
|yi − Pm (xi )|2 ≤
|yi − Qm (xi )|2
i=0
i=0
para qualquer polinómio Qm de grau m. Se existir, o polinómio Pm é
chamado aproximação no sentido dos mínimos quadrados dos dados
(xi , yi )i=0,··· ,n .
Uma vez que m < n, em geral não é possível garantir que P m (xi ) = yi
para qualquer i.
Cálculo Numérico - Interpolação e aproximção polinomial
Lagrange
Diferenças de Newton
Erro de interpolação
Fenômeno de Runge
Interpolação por intervalo
Splines
Mínimos quadrados
Se Pm (x) = a0 + a1 x + · · · + am xm , o problema dos mínimos
quadrados pode ser reescrito na forma
Φ(a0 , a1 , · · · , am ) =
min
bi , i=0,1,··· ,m
Φ(b0 , b1 , · · · , bm )
onde Φ é definida por
Φ(b0 , b1 , · · · , bm ) =
n
X
2
|yi − (b0 + b1 xi + · · · + bm xm
i )|
i=0
O vector (a0 , a1 , · · · , am ) onde Φ atinge o mínimo satisfaz as
condições necessárias de optimalidade
∂Φ
(a0 , a1 , · · · , am ) = 0
∂bi
Cálculo Numérico - Interpolação e aproximção polinomial
i = 0, 1, · · · , m
Lagrange
Diferenças de Newton
Erro de interpolação
Fenômeno de Runge
Interpolação por intervalo
Splines
Para simplificar, suponha que m = 1. Então
Φ(b0 , b1 )
=
n
X
y2i + b20 + b21 x2i + 2b0 b1 xi − 2b0 yi − 2b1 xi y2i
i=0
∂Φ
∂Φ
Das condições de optimalidade ∂b
(a0 , a1 ) = ∂b
(a0 , a1 ) = 0,
0
1
deduz-se

n
n
X
X



a0 (n + 1) + a1
xi =
yi








 a0
n
X
xi + a 1
i=0
Cálculo Numérico - Interpolação e aproximção polinomial
i=0
n
X
i=0
n
X
(xi )2 =
i=0
i=0
xi yi
Mínimos quadrados
Lagrange
Diferenças de Newton
Erro de interpolação
Fenômeno de Runge
Interpolação por intervalo
Splines
Mínimos quadrados
No caso geral, obtem-se o sistema com (m + 1) × (m + 1) sistema
linear dado por

n
n
n
X
X
X

m

 a0 (n + 1) + a1
xi + · · · a m
(xi ) =
yi




i=0
i=0
i=0



n
n
n
n

X
X
X
X



xi + a 1
x2i + · · · am
(xi )m+1 =
xi yi
 a0
i=0















i=0
i=0
i=0
..
.
a0
n
X
i=0
(xi )m + a1
n
X
(xi )m+1 + · · · am
i=0
Cálculo Numérico - Interpolação e aproximção polinomial
n
X
i=0
(xi )2m =
n
X
i=0
(xi )m yi
Lagrange
Diferenças de Newton
Erro de interpolação
Fenômeno de Runge
Interpolação por intervalo
Splines
Mínimos quadrados
1.0
0.5
−5
−4
−3
−2
−1
0
1
2
3
4
5
Função de Runge: aproximação pelo método dos mínimos quadrados com m = 6 e n = 20
Cálculo Numérico - Interpolação e aproximção polinomial
Lagrange
Diferenças de Newton
Erro de interpolação
Fenômeno de Runge
Interpolação por intervalo
Splines
Mínimos quadrados
1.0
0.5
−5
−4
−3
−2
−1
0
1
2
3
4
5
Função de Runge: aproximação pelo método dos mínimos quadrados com m = 6 e n = 100
Cálculo Numérico - Interpolação e aproximção polinomial
Lagrange
Diferenças de Newton
Erro de interpolação
Fenômeno de Runge
Interpolação por intervalo
Splines
Mínimos quadrados
1.0
0.5
−5
−4
−3
−2
−1
0
1
2
3
4
5
Função de Runge: aproximação pelo método dos mínimos quadrados com m = 10 e n = 100
Cálculo Numérico - Interpolação e aproximção polinomial