Formulario

Prévia do material em texto

Universidade da Beira Interior
Algebra Linear Numérica / Matemática Computacional
Formulário
• Mudança para a Base Decimal
n = ∗(ckck−1 . . . c0, c−1 . . . c−p)b = ∗
k∑
i=−p
cib
i, ci ∈ {0, 1, ..., b− 1}
• Sistema de ponto flutuante
x ∈ FP (b, t, ε)⇔ x = ±(m)b × b±(e)b
m = m1m2 . . .mt, e = cε−1cε−2 . . . c1c0 mi, ci ∈ {0, 1, . . . , b− 1}, (0.1)b ≤ m < 1,
• Definição de erros Seja x̄ a aproximação do valor exacto x então
Ea(x̄) = |x− x̄| e Er(x̄) =
|x− x̄|
|x|
• Polinómio de Taylor
Pn(x) = f(x0)+(x−x0)f ′(x0)+
(x− x0)2
2
f ′′(x0)+
(x− x0)3
3!
f (3)(x0)+· · ·+
(x− x0)n
n!
f (n)(x0)
Rn(x) =
(x− x0)(n+1)
(n+ 1)!
f (n+1)(ξ) ξ ∈ (x, x0)
• Diferenciação numérica
f ′(xi) = f
′′(xi) =
1
h
[f(xi+1)− f(xi)]− h2f
′′(ξ) 1
h2
[f(xi)− 2f(xi+1) + f(xi+2)]− hf ′′′(ξ)
1
h
[f(xi)− f(xi−1)] + h2f
′′(ξ) 1
h2
[f(xi−1)− 2f(xi) + f(xi+1)]− h
2
12
f (4)(ξ)
1
2h
[−3f(xi) + 4f(xi+1)− f(xi+2)] + h
2
3
f ′′′(ξ) 1
h2
[f(xi−2)− 2f(xi−1) + f(xi)] + hf ′′′(ξ)
1
2h
[−f(xi−1) + f(xi+1)]− h
2
6
f ′′′(ξ)
1
2h
[f(xi−2)− 4f(xi−1) + 3f(xi)] + h
2
3
f ′′′(ξ)
xi − xi−1 = h > 0, i = 1, 2, . . .
• Propagação dos erros
Seja f(x̄) = f(x̄1, . . . , x̄n) uma aproximação do valor exacto f(x) = f(x1, . . . , xn) então
Ea(f(x̄)) ≤
n∑
i=1
| ∂f
∂xi
(x̄1, . . . , x̄n)||xi − x̄i|, Er(f(x̄)) ≤
n∑
i=1
∣∣∣∣∣ x̄i
∂f
∂xi
(x̄1, . . . , x̄n)
f(x̄1, . . . , x̄n)
∣∣∣∣∣ |xi − x̄i||xi|
• Condicionamento
Cond(f, a) =
af ′(a)
f(a)
, cond(A) = ‖A‖.‖A−1‖
1
• Localização das ráızes
Teorema de Bolzano: Seja f(x) uma função cont́ınua em [a, b], se f(a)f(b) < 0 então existe
c ∈ [a, b] tal que f(c) = 0.
Teorema de Rolle: Seja f(x) uma função cont́ınua e derivável em [a, b], se f(a) = f(b) então
existe c ∈ [a, b] tal que f ′(c) = 0.
• Zeros de funções f(x) = 0
– Bissecção xk =
ak + bk
2
, Ea(xk) ≤
b− a
2k+1
, k = 0, 1, . . .
– Corda falsa xk = bk − f(bk)
bk − ak
f(bk)− f(ak)
, k = 0, 1, . . .
– Newton-Raphson xk+1 = xk −
f(xk)
f ′(xk)
, k = 0, 1, . . .
– Secante xk+1 = xk −
f(xk)
f(xk)− f(xk−1)
(xk − xk−1), k = 1, 2, . . .
Condições de convergência para os métodos de Newton e da secante
- f ∈ C2([a, b])
- f(a)f(b) < 0
- f ′(x) 6= 0, x ∈ [a, b]
- f ′′(x) não muda de sinal em [a, b]
-
∣∣∣ f(a)f ′(a) ∣∣∣ ≤ b− a e ∣∣∣ f(b)f ′(b) ∣∣∣ ≤ b− a ou ∃x0 ∈ [a, b] : f(x0)× f ′′(x0) > 0
– Ponto fixo x = G(x) xk+1 = G(xk), |G′(x)| < 1,∀x ∈ [a, b], k = 0, 1, . . .
– Muller
xk+1 = xk−
2f(xk)
w ±∗
√
w2 − 4fk−2,k−1,kf(xk)
, w = fk−1,k+fk−2,k−fk−2,k−1, k = 2, 3, . . .
em ∗ escolhe-se o sinal de w. Para o cálculo de fi,j e fi,j,k ver em diferenças divididas.
• Extremos de Funções
– Razão de ouro φ =
√
5− 1
2
Ik = [ak, bk], ck = bk − φ(bk − ak) , dk = ak + φ(bk − ak), k = 0, 1, . . .
Maximizar Minimizar
f(ck) < f(dk)⇒ Ik+1 = [ck, bk] f(ck) < f(dk)⇒ Ik+1 = [ak, dk]
f(ck) > f(dk)⇒ Ik+1 = [ak, dk] f(ck) > f(dk)⇒ Ik+1 = [ck, bk]
Ea(xk) ≤ (1− φ)(bk − ak)
– Interpolação quadrática
xk+1 =
f(xk−2)(x
2
k−1 − x2k) + f(xk−1)(x2k − x2k−2) + f(xk)(x2k−2 − x2k−1)
2f(xk−2)(xk−1 − xk) + 2f(xk−1)(xk − xk−2) + 2f(xk)(xk−2 − xk−1)
k = 2, 3, . . .
2
• Sistemas de equações lineares Ax = b
– Cholesky A = UTU
u11 =
√
a11, u1j =
a1j
u11
, ujj =
√√√√ajj − j−1∑
k=1
u2kj, j = 2, . . . , n
uij =
1
uii
(
aij −
i−1∑
k=1
ukiukj
)
, i = 2, . . . , n, j = i+ 1, . . . , n uij = 0, i > j
– Normas
‖x‖1 = |x1|+ · · ·+ |xn|, ‖x‖2 =
√
|x1|2 + · · ·+ |xn|2, ‖x‖∞ = max
i=1,...,n
{|x1|, . . . , |xn|}
‖A‖1 = max
j=1,...,n
n∑
i=1
|aij|; ‖A‖∞ = max
i=1,...,n
n∑
j=1
|aij|; ‖A‖E =
√√√√ n∑
i,j=1
a2ij
– Jacobi A = D + L+ U
x
(k+1)
i =
bi
aii
−
n∑
j=1
j 6=i
aij
aii
x
(k)
j , i = 1, . . . , n k = 0, 1, . . .
x(k+1) = −D−1(L+ U)x(k) +D−1b M = −D−1(L+ U)
– Gauss-Seidel A = D + L+ U
x
(k+1)
i =
bi
aii
−
i−1∑
j=1
aij
aii
x
(k+1)
j −
n∑
j=i+1
aij
aii
x
(k)
j , i = 1, . . . n k = 0, 1, . . .
x(k+1) = −(D + L)−1Ux(k) + (D + L)−1b M = −(D + L)−1U
– Erro Ea(x
(k)) ≤ ‖M‖
1− ‖M‖
‖x(k) − x(k−1)‖ ou Ea(x(k)) ≤
‖M‖k
1− ‖M‖
‖x(1) − x(0)‖
– Condições de convergência: A matriz A do sistema ser estritamente diagonal dominante
ou a matriz de iteração M ter ‖M‖ < 1.
• Sistemas de equações não lineares F (x) = 0⇔

f1(x1, . . . , xn) = 0
f2(x1, . . . , xn) = 0
...
fn(x1, . . . , xn) = 0
– Newton
JF (x
(k))d = −F (x(k)), x(k+1) = x(k) + d, JF (xk) =
[
∂fi
∂xj
(x(k))
]
, k = 0, 1, . . .
3
• Interpolação polinomial Pn(xi) = f(xi), i = 0, 1, . . . , n
– Polinómio de Lagrange
Pn(x) =
n∑
k=0
f(xk)Lk(x), Lk(x) =
n∏
i=0,i 6=k
x− xi
xk − xi
– Polinómio de Newton
Diferenças Divididas
* ordem 1 : fi,j = f [xi, xj] =
f(xj)− f(xi)
xj − xi
* ordem j : fi,...,i+j = f [xi, . . . , xi+j] =
fi+1,...,i+j − fi,...,i+j−1
xi+j − xi
Pn(x) = f(x0) +
n∑
k=1
f0,...,k(x− x0) . . . (x− xk−1),
– Erro para os polinómios de Lagrange e de Newton
Se f(x) é conhecida:
|f(x)− Pn(x)| ≤
max
x∈(x0,xn)
|f (n+1)(x)|
(n+ 1)!
|(x− x0) . . . (x− xn)|, x ∈ (x0, xn)
Se f(x) é desconhecida:
|f(x) − Pn(x)| ≤ M |(x − x0) . . . (x − xn)| onde M é o maior módulo das diferenças
divididas de ordem n+ 1 e x ∈ (x0, xn).
– Polinómio de Hermite
H2n+1(x) = f(x0) + f0,0(x− x0) + f0,0,1(x− x0)2 + f0,0,1,1(x− x0)2(x− x1) + . . .
· · ·+ f0,0,...,n,n(x− x0)2 . . . (x− xn−1)2(x− xn)
fi,i = f
′(xi)
– Erro |f(x)−H2n+1(x)| ≤
max
x∈(x0,xn)
|f (2n+2)(x)|
(2n+ 2)!
|(x− x0)2 . . . (x− xn)2|.
– Spline cúbico natural f ′′(x0) = f
′′(xn) = 0
Sj(x) = aj + bj(x−xj) + cj(x−xj)2 + dj(x−xj)3, x ∈ [xj, xj+1], j = 0, 1, . . . , n− 1
hj = xj+1 − xj, aj = f(xj)
bj = fj,j+1 − (2cj + cj+1)hj/3, dj =
cj+1 − cj
3hj
1 0 0 0 . . . 0 0
h0 2(h0 + h1) h1 0 . . . 0 0
0 h1 2(h1 + h2) h2 . . . 0 0
...
...
...
...
. . .
...
...
0 0 0 0 . . . 2(hn−2 + hn−1) hn−1
0 0 0 0 . . . 0 1


c0
c1
c2
...
cn−1
cn

=

0
3(f21 − f10)
3(f32 − f21)
...
3(fn,n−1 − fn−1,n−2)
0

4
• Aproximação polinomial f(x) ≈ pn(x)
– Mı́nimos quadrados pn(x) =
n∑
i=0
aiϕi(x)
{ϕ0(x), ϕ1(x), . . . , ϕn(x)} é uma base para o espaço dos polinómios de grau menor ou
igual a n e os coeficientes ak são obtidos pela solução do sistema
� caso discreto
n∑
k=0
(
ak
m∑
j=1
ϕk(xj)ϕi(xj)
)
=
m∑
j=1
f(xj)ϕi(xj), i = 0, 1, . . . , n
� caso cont́ınuo
n∑
k=0
(
ak
∫ b
a
ϕk(x)ϕi(x) dx
)
=
∫ b
a
f(x)ϕi(x) dx, i = 0, 1, . . . , n
– Polinómios de Legendre
{
P0(x) = 1 ; P1(x) = x
Pn+1(x) =
2n+1
n+1
xPn(x)− nn+1Pn−1(x), n ≥ 1
, x ∈ [−1, 1]
– Polinómios de Chebyshev
{
T0(x) = 1 ; T1(x) = x
Tn+1(x) = 2xTn(x)− Tn−1(x), n ≥ 1
, x ∈ [−1, 1]
– Nós de Chebyshev ( ráızes de Tn ) zk = cos
(
2k + 1
2n
π
)
, k = 0, 1, . . . , n− 1
– Mudança de variável
[−1, 1] 7→ [a, b]
z → x = a+ b−a
2
(z + 1)
– Erro padrão
1
m
(
m∑
j=1
(f(xj)− pn(xj))2
) 1
2
ou
1
b− a
(∫ b
a
(f(x)− pn(x))2 dx
) 1
2
• Integrais∫
k dx = kx+ C∫
f ′fk dx =
fk+1
k + 1
+ C, k 6= −1∫
f ′
f
dx = ln(|f |) + C∫
f ′ef dx = ef + C∫
f ′af dx =
af
ln(a)
+C, a ∈]0,+∞[\{−1}
∫
f ′cos(f) dx = sin(f) + C∫
f ′sin(f) dx = −cos(f) + C∫
f ′
cos2(f)
dx = tan(f) + C∫
f ′
sin2(f)
dx = − 1
tan(f)
+ C
5
• Integração numérica I =
∫ b
a
f(x) dx =
∫ 1
−1 g(w) dw, com g(w) =
b−a
2
f
(
b+a
2
+ b−a
2
w
)
– Regras de Newton-Cotes de intervalo fechado
∗ Trapézio I = h
2
[f(a) + f(b)]− h
3
12
f ′′(ξ), h = b− a
∗ Simpson I = h
3
[
f(a) + 4f(
a+ b
2
) + f(b)
]
− h
5
90
f (4)(ξ), h =
(b− a)
2
– Regras compostas de intervalo fechado h =
(b− a)
n
, xi = a+ hi, ξ ∈ (a, b)
∗ Trapézio I = h
2
[
f(a) + 2
n−1∑
j=1
f(xj) + f(b)
]
− b− a
12
h2f ′′(ξ),
∗ Simpson I = h
3
[
f(a) + 2
(n/2)−1∑
j=1
f(x2j) + 4
(n/2)∑
j=1
f(x2j−1) + f(b)
]
− b− a
180
h4f (4)(ξ)
– Regras de Newton-Cotes de intervalo aberto
∗ I = 3h
2
[f(x1) + f(x2)] +
3h3
4
f ′′(ξ), h =
b− a
3
∗ I = 4h
3
[2f(x1)− f(x2) + 2f(x3)] +
14h5
45
f (4)(ξ), h =
(b− a)
4
– Romberg I ≈ Rn,n
Rm,1 é obtido utilizando o método do trapézio com 2
m−1 sub-intervalos e
Rm+1,j+1 =
4jRm+1,j−Rm,j
4j − 1
, j = 1, . . . ,m , m = 1, . . . , n−1 , e Ea ≈ |Rn−1,n−1−Rn,n|
– Gauss com n pontos∫ 1
−1
g(x) dx =
n∑
i=1
cig(wi) +
22n+1(n!)4
(2n+ 1)[(2n)!]2
g(2n)(ξ)
(2n)!
onde
n pesos ci nós wi
2 c1 = c2 = 1 w1 = −w2 = − 1√3
3 c1 = c3 =
5
9
, c2 =
8
9
w1 = −w3 = −
√
3
5
, w2 = 0
4 c1 = c4 = 0.347854845 w1 = −w4 = −0.861136312
c2 = c3 = 0.652145155 w2 = −w3 = −0.339981044
5 c1 = c5 = 0.236926885 w1 = −w5 = −0.906179846
c2 = c4 = 0.478628670, c3 = 0.568888889 w2 = −w4 = −0.538469310, w3 = 0
6
• Transformada de Laplace
→Transformada de Laplace →Transformada de Laplace
1 → 1
s
, s > 0 f(x) →L[f(x)] = F (s) =
∫ ∞
0
e−sxf(x) dx
xk → k!
sk+1
, s > 0, k ∈ N xkf(x) → (−1)k d
k
dsk
F (s)
eax → 1
s− a
, s > a f (k)(x) → s
kF (s)− sk−1f(0)− sk−2f ′(0)− . . .
· · · − f (k−1)(0)
cos(ax) → s
s2 + a2
, s > 0
∫ x
0 f(u) du→
1
s
F (s)
sin(ax) → a
s2 + a2
, s > 0 f(ax) → 1
a
F
(s
a
)
cosh(ax)→ s
s2 − a2
, s > |a| eaxf(x) →F (s− a)
sinh(ax)→ a
s2 − a2
, s > |a| →
• Equações diferenciais ordinárias
– Problemas de valores iniciais:
y′ = f(t, y)y(t0) = y0 , t ∈ [a, b]
Euler expĺıcito: yi+1 = yi + hf(ti, yi)
Euler impĺıcito: yi+1 = yi + hf(ti+1, yi+1)
Trapézios: yi+1 = yi +
h
2
[f(ti, yi) + f(ti+1, yi+1)]
Taylor de ordem n: yi+1 = yi + hf(ti, yi) +
h2
2
f ′(ti, yi) + · · ·+ h
n
n!
f (n−1)(ti, yi); f
′ = f ′t + f
′
y × f(t, y)
Runge-Kutta 2: yi+1 = yi +
h
2
(k1 + k2), k1 = f(ti, yi), k2 = f(ti + h, yi + hk1)
Runge-Kutta 4: yi+1 = yi +
h
6
(k1 + 2k2 + 2k3 + k4), k1 = f(ti, yi), k2 = f(ti +
h
2
, yi +
h
2
k1)
k3 = f(ti +
h
2
, yi +
h
2
k2), k4 = f(ti + h, yi + hk3)
Adams-Bashforth 2: yi+1 = yi +
h
2
(3f(ti, yi)− f(ti−1, yi−1))
Adams-Bashforth 3: yi+1 = yi +
h
12
(23f(ti, yi)− 16f(ti−1, yi−1) + 5f(ti−2, yi−2))
Adams-Bashforth 4: yi+1 = yi +
h
24
(55f(ti, yi)− 59f(ti−1, yi−1) + 37f(ti−2, yi−2)− 9f(ti−3, yi−3))
Adams-Multon 2: yi+1 = yi +
h
2
(f(ti+1, yi+1) + f(ti, yi))
Adams-Multon 3: yi+1 = yi +
h
12
(5f(ti+1, yi+1) + 8f(ti, yi)− f(ti−1, yi−1))
Adams-Multon 4: yi+1 = yi +
h
24
(9f(ti+1, yi+1) + 19f(ti, yi)− 5f(ti−1, yi−1) + f(ti−2, yi−2))
ti = t0 + h× i, y(ti) ≈ yi = yi,h
Ea(yi,h) ≈
∣∣∣∣yi/2,2h − yi,h1− 2v
∣∣∣∣ , v − ordem do método,
Melhoramento da estimativa y∗i =
2vyi,h − yi/2,2h
2v − 1
Picard : yi+1(t) = y0 +
∫ t
t0
f(x, yi(x)) dx
7