formulario numerico2

Prévia do material em texto

Formulário - Cálculo Numérico
Wellington José Corrêa
Universidade Tecnológica Federal do Paraná
Campus Campo Mourão
DAMAT, 2016.
Nome:
1 Interpolação
Os métodos de Lagrange, Newton e Newton-Grégory possuem
a mesma estimativa para o erro dada por:
E(x) ≤ |Ψ(x)|
(n+ 1)!
M (1)
onde Ψ(x) =
n∏
i=0
(x− xi) e
M = máx
{∣∣∣f (n+1)(ξ)∣∣∣ ; ξ ∈ [x0, xn]} .
Fórmula de Lagrange
Coeficientes `k’s:
`k(x) =
(x− x0) · (x− x1) · · · (x− xk−1) · (x− xk+1) · · · (x− xn)
(xk − x0) · (xk − x1) · · · (xk − xk−1) · (xk − xk+1) · · · (xk − xn)
(2)
Polinômio interpolador:
P (x) =
n∑
k=0
yk `k(x) . (3)
Fórmula Interpolatória de Newton
Diferenças Divididas
x
O
rd
em
0
O
rd
em
1
O
rd
em
2
x
0
f
[x
0
]
f
[x
0
,x
1
]
=
f
[x
1
]
−
f
[x
0
]
x
1
−
x
0
x
1
f
[x
1
]
f
[x
0
,x
1
,x
2
]
=
f
[x
1
,x
2
]
−
f
[x
0
,x
1
]
x
2
−
x
0
f
[x
1
,x
2
]
=
f
[x
2
]
−
f
[x
1
]
x
2
−
x
1
x
2
f
[x
2
]
f
[x
1
,x
2
,x
3
]
=
f
[x
2
,x
3
]
−
f
[x
1
,x
2
]
x
3
−
x
1
f
[x
2
,x
3
]
=
f
[x
3
]
−
f
[x
2
]
x
3
−
x
2
x
3
f
[x
3
]
Polinômio interpolador baseado nas diferenças divididas:
P (x) = f [x0] + (x− x0) f [x0, x1] + (x− x0) (x− x1) f [x0, x1, x2]
+ . . .+ (x− x0) (x− x1) . . . (x− xn−1) f [x0, x1, . . . , xn]
(4)
Fórmula Interpolatória de Newton - Grégory
Diferenças Finitas:
∆0f ∆1f ∆2f ∆3f
x0 ∆
0f(x0)
∆1f(x0)
x1 ∆
0f(x1) ∆
2f(x0)
∆1f(x1) ∆
3f(x0)
x2 ∆
0f(x2) ∆
2f(x1)
∆1f(x2)
x3 ∆
0f(x3)
onde
∆rf(xi) = ∆
r−1f(xi+1)−∆r−1f(xi), r ≥ 1 . (5)
Polinômio interpolador baseado nas diferenças finitas:
P (x) = ∆0f(x0) + (x− x0) · ∆
1f(x0)
1!h1
+ (x− x0) · (x− x1) · ∆
2f(x0)
2!h2
+ ... + (x− x0) · (x− x1)...(x− xn−1) · ∆
nf(x0)
n!hn
.
(6)
1
Spline Cúbica Natural
Neste caso, consideremos µ0 = µn = 0 e devemos resolver o
seguinte sistema de (n− 1) equações lineares:
2(h0+h1) h1
h1 2(h1+h2) h2 0
h2 2(h2+h3) h3
. . . . . . . . .
0 hn−2 2(hn−2+hn−1)

×

µ1
µ2
µ3
...
µn−1
 =

b1 − b0
b2 − b1
b3 − b2
...
bn−1 − bn−2

(7)
com
bi = 6
(
yi+1 − yi
hi
)
.
Os n polinômios de interpolação por spline para i =
0, 1, . . . , n− 1 são:
pi(x) = yi + αi (x− xi) + βi (x− xi)2 + γi (x− xi)3 (8)
onde
αi =
yi+1 − yi
hi
− µi+1
6
hi − µi
3
hi (9)
βi =
µi
2
(10)
γi =
µi+1 − µi
6hi
. (11)
Método dos Mínimos Quadrados: Caso Discreto
Dada a função
g(x) = α1 g1(x) + α2 g2(x) + . . .+ αn gn(x),
devemos resolver o seguinte sistema
〈g1, g1〉 〈g1, g2〉 · · · 〈g1, gn〉
〈g2, g1〉 〈g2, g2〉 · · · 〈g2, gn〉
...
...
. . .
...
〈gn, g1〉 〈gn, g2〉 · · · 〈gn, gn〉


α1
α2
...
αn
 =

〈g1, f〉
〈g2, f〉
...
〈gn, f〉

(12)
onde o produto interno neste caso é dado por
〈x, y〉 =
m∑
k=1
xk · yk, ∀x, y ∈ Rm . (13)
Método dos Mínimos Quadrados: Caso Contínuo
Dada a função
g(x) = α1 g1(x) + α2 g2(x) + . . .+ αn gn(x) ,
devemos resolver o sistema (12) onde agora o produto interno
é definido como
〈f(x), g(x)〉 =
∫ b
a
f(x) g(x) dx . (14)
2 Integração Numérica
Regra do Trapézio
• Regra do Trapézio Simples
Para h = x1 − x0, temos:∫ x1
x0
f(x) dx ≈ h
2
[f(x0) + f(x1)] . (15)
Erro:
E = −h
3
12
f ′′(ξ), x ∈ [x0, xn] . (16)
• Regra dos Trapézios Generalizadas
Considerando
h =
xn − x0
n
, x0 = a, xn = b,
temos:∫ xn
x0
f(x) dx ≈ h
2
[f(x0) + 2f(x1) + 2f(x2) + . . . + 2f(xn−1) + f(xn)] dx .
(17)
cuja estimativa do erro é
|E| ≤ h
2
12
M · (xn − x0),
onde
M = max {|f ′′(ξ)|; ξ ∈ [x0 , xn]} .
Regra de Simpson
• Regra 1/3 de Simpson
∫ x2
x0
f(x) dx ≈ h
3
[f(x0) + 4 f(x1) + f(x2)] ,
onde h =
x2 − x0
2
.
Uma estimativa para o erro nesta situação é
|E| ≤ h
5
90
M,
onde
M = max
{
|f (4)(ξ)|; ξ ∈ [x0 , x2]
}
.
2
• Regra 1/3 de Simpson Generalizada:
Tendo em mente que h =
xn − x0
n
temos que
∫ xn
x0
f(x) dx ∼= h
3
[
f(x0) + 4f(x1) + 2f(x2) + 4f(x3)
+ . . .+ 2f(xn−2) + 4f(xn−1) + f(xn)
]
(18)
onde n é um número par e o erro estimado é
|E| ≤ h
4
180
(xn − x0)M
onde
M = max{|f (4)(θ)|, θ ∈ [x0, xn]}.
• Regra 3/8 de Simpson
∫ x3
x0
f(x) dx ∼= 3
8
h [f(x0) + 3 f(x1) + 3 f(x2) + f(x3)]
com h =
x3 − x0
3
e um limitante superior para o erro é
|E| ≤ 3
80
h5M
onde
M = max{|f (4)(θ)|, θ ∈ [x0, x3]}.
• Regra 3/8 de Simpson Generalizada:
∫ xn
x0
f(x) dx ∼= 3
8
h
[
f(x0)
+ 3 (f(x1) + f(x2) + f(x4) + f(x5) + . . . + f(xn−2) + f(xn−1))
+ 2 (f(x3) + f(x6) + . . . + f(xn−3)) + f(xn)
]
com h =
xn − x0
n
, onde n é múltiplo de três. Neste caso,
o limitante para o erro superior é
|E| ≤ h
4
80
(xn − x0)M
onde
M = max{|f (4)(θ)|, θ ∈ [x0, xn]}.
Quadratura de Gauss
Se P (x) é qualquer polinômio de grau menor que 2n, então,∫ 1
−1
P (x) dx =
n∑
i=1
ci · P (xi) . (19)
Os valores das contantes ci quanto das raízes xi dos polinô-
mios de Legendre são extensivamente tabuladas. A seguinte
tabela lista esses valores para n = 2, 3, 4 e 5.
n raízes xi Coeficientes ci i
2 0,5773502692 1 1
-0,5773502692 1 2
3 0,7745966692 0,5555555556 1
0 0,8888888889 2
-0,7745966692 0,5555555556 3
4 0,8611363116 0,3478548451 1
0,3399810436 0,6521451549 2
-0,3399810436 0,6521451549 3
-0,8611363116 0,3478548451 4
5 0,9061798459 0,2369268850 1
0,5384693101 0,4786286705 2
0 0,5688888889 3
-0,5384693101 0,4786286705 4
-0,9061798459 0,2369268850 5
Figura 1: Tabela que lista os valores das raízes xi e dos coefici-
entes ci para n = 2, 3, 4, 5.
Para aplicar o método da quadratura de Gauss para a integral∫ b
a
f(x) dx sobre um intervalo arbitrário [a, b], devemos usar a
seguinte mudança de variável
x =
1
2
[(b− a) t+ a+ b],
o que resulta∫ b
a
f(x) dx =
(b− a)
2
∫ 1
−1
f
(
(b− a) t+ a+ b
2
)
dt . (20)
3 Solução Numérica de Equações
Diferenciais Ordinárias
Considere o seguinte problema de valor inicial:{
y′ = f(x, y)
y(x0) = y0
Método de Euler
Tomando n subintervalos de [a, b], n ≥ 1 de modo que
xj = x0 + j · h; h = b− a
n
, (21)
onde j = 0, 1, . . . , n, x0 = a e xn = b.
O método de Euler é
yj+1 = yj + h f(xj , yj), j = 0, 1, . . . , n− 1.
com erro dado por
en =
h2
2!
y′′(ξ), ξ ∈ [xn, xn+1] . (22)
3
Método de Runge - Kutta
• Método de Runge - Kutta de Segunda Ordem
Considere n subintervalos de [a, b], n ≥ 1, tendo em mente
que
xj = x0 + j · h; h = b− a
n
, (23)
onde j = 0, 1, . . . , n, x0 = a e xn = b.
O Método de Runge - Kutta de Segunda Ordem é
yj+1 = yj +
h
2
(k1 + k2),
k1 = f(xj , yj),
k2 = f(xj + h, yj + h k1)
, j = 0, 1, 2, . . . , n− 1.
(24)
• Método de Runge–Kutta de Ordem 4
Neste caso, temos as seguintes fórmulas:

yj+1 = yj +
h
6
(k1 + 2 k2 + 2 k3 + k4) ,
k1 = f(xj , yj)
k2 = f
(
xj +
h
2
, yj +
h
2
k1
)
k3 = f
(
xj +
h
2
, yj +
h
2
k2
)
k4 = f (xj + h, yj + h k3)
, j = 0, 1, . . . , n− 1 .
(25)
4 Sistemas Lineares
Decomposição LU
Se det(Ak) 6= 0, k = 1, 2, . . . , n− 1.
Então,
A = L · U ,
onde
L =

1
l21 1 0
l31 l32 1
...
...
...
. . .
ln1 ln2 ln3 · · · 1

, U =

u11 u21 u31 · · · un1
u22 u23 · · · un2
u33 · · · u3n
0 . . . ...
unn

E ainda,
det(A) = u11 u22 . . . unn.
Procedimento:
• Passo 1: Primeira linha de U .
u1j = a1j , j = 1, 2, . . . , n .
• Passo 2: Primeiracoluna de L .
li1 =
ai1
u11
, i = 2, . . . , n .
• Passo 3: Segunda linha de U .
u2j = a2j − l21 u1j , j = 2, . . . , n .
• Passo 4: Segunda coluna de L .
li2 =
ai2 − li1 u12
u22
, i = 3, . . . , n .
• Passo 5: Terceira linha de U, 3a coluna de L, 4a linha de
U, 4a de L, etc.
uij = aij −
i−1∑
k=1
lik ukj , i ≤ j
lij =
aij −
j−1∑
k=1
lik ukj
ujj
, i > j .
Resolução de sistema linear AX = B :
Resolva primeiramente
L · Y = B
e depois
U · X = Y .
Método de Cholesky
Se A = At e det(A) > 0, k = 1, 2, . . . , n, então
A = G · Gt
onde
G =

g11
g21 g22 0
g31 g32 g33
...
...
...
. . .
gn1 gn2 gn3 · · · gnn

.
Além disso,
det(A) = (g11 g22 . . . gnn)
2
.
Procedimento:
• Elementos Diagonais
g11 =
√
a11
gii =
(
aii −
i−1∑
k=1
g2ik
) 1
2
, i = 2, 3, · · · , n .
• Elementos não diagonais de G
4
1. Primeira coluna:
gi1 =
ai1
g11
, i = 2, 3, · · · , n .
2. Segunda coluna:
gi2 =
ai2 − gi1 g21
g22
, i = 3, 4, · · · , n .
3. Demais colunas:
gij =
aij −
j−1∑
k=1
gikgjk
gjj
, 2 ≤ j < i .
Resolução de sistema linear AX = B :
G · Y = B Gt · X = Y .
Método de Eliminação de Gauss
Considere o sistema linear AX = B caracterizado matricial-
mente pela matriz aumentada:
a
(1)
11 a
(1)
12 a
(1)
13 . . . a
(1)
1n b
(1)
1
a
(1)
21 a
(1)
22 a
(1)
23 . . . a
(1)
2n b
(1)
2
a
(1)
31 a
(1)
32 a
(1)
33 . . . a
(1)
3n b
(1)
3
...
...
...
. . .
...
...
a
(1)
n1 a
(1)
n2 a
(1)
n3 . . . a
(1)
nn b
(1)
n

onde i, j = 1, 2, . . . , n, a(1)ij = aij e b
(1)
i = bi .
De modo geral, o k-ésimo passo do método da eliminação de
Gauss é obtido por
a
(k+1)
ij = a
(k)
ij − a(k)kj
a
(k)
ik
a
(k)
kk
, k = 1, 2, . . . , n− 1;
i = k + 1, . . . , n;
b
(k+1)
i = b
(k)
i − b(k)k
a
(k)
ik
a
(k)
kk
, j = k, k + 1, . . . , n .
5