formulario numerico

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, 2017.
Nome:
1 Conversão de Base e Erros
Base Binária
Um número na base 2 pode ser escrito como:
m∑
i=n
ai 2
i; ai = {0, 1}, n,m ∈ Z; n ≤ 0 e m ≥ 0.
• Para mudar da base 2 para base 10, basta multiplicar o
dígito binário por uma potência de 2 adequada.
• Para converter um número da base 10 para a base 2, tem-se
que aplicar um processo para a parte inteira e outro para
a parte fracionária.
1. Parte inteira:
N 2
q1r1 2q2r2 2q3r3 . . .qn−1 2
1rn−1
Portanto,
(N)10 = (1 rn−1 rn−2 . . . r3 r2 r1)2 .
2. Parte Fracionária.
(a) Multiplica-se o número fracionário por 2;
(b) Do resultado do passo (a), a parte inteira é o
primeiro dígito binário;
(c) Do resultado do passo (b), a parte fracionária é
novamente multiplicada por 2;
(d) O processo continua até que a parte fracionária seja
nula.
Aritmética de Ponto Flutuante
±︸︷︷︸
sinal
0, d1d2d3 . . . dp︸ ︷︷ ︸
mantissa
×B
expoente︷︸︸︷
e .
Erros
Denotando por aex o valor exato e aaprox o valor aproximado,
temos:
Erro absoluto:
Eabs = |aex − aaprox|
Erro relativo:
Erel =
Eabs
aaprox
2 Raízes de Equações
Em todos os métodos, escolha a, b de modo que
f(a) · f(b) < 0.
Usaremos o seguinte critério de parada:
|xk+1 − xk| ≤ ε .
Método da Bissecção
xk+1 =
ak + bk
2
, k = 0, 1, . . .
Número mínimo de iterações k :
k ≥ log2
(
b− a
ε
)
− 1 .
A seguir, encontra-se um esquema prático para resolver este
método:
k ak bk f(ak) f(bk) xk f(xk) |xk − xk−1|
0 a b f(a) f(b)
a+ b
2
f
(
a+ b
2
)
−
...
...
...
...
...
...
...
...
Método do Ponto Fixo
Teorema 2.1 Seja ξ ∈ [a, b] uma raiz da equação f(x) = 0
e F (x) contínua, diferenciável em [a, b] e F (x) ∈ [a, b]. Se
|F ′(x)| ≤ k < 1 para todos os pontos em [a, b] e x0 ∈ [a, b],
então, os valores dados pela equação
xk+1 = F (xk), k = 0, 1, 2, ...
converge para ξ.
Método de Newton
Teorema 2.2 Uma condição suficiente para a convergência do
método de Newton é, se f(a) ·f(b) < 0, f ′(x), f ′′(x) forem não-
nulas e preservem o sinal em (a, b) de modo que
f(x0) · f ′′(x0) > 0.
1
xk+1 = xk − f(xk)
f ′(xk)
, k = 0, 1, 2, ...
Método da Secante
Considere x0 = a e x1 = b.
xk+1 = xk − f(xk) · (xk − xk−1)
f(xk)− f(xk−1)
Método Regula Falsi
Considere x0 = a e x1 = b.
xk+1 = xk − f(xk) · (xk − xk−1)
f(xk)− f(xk−1)
O método Regula Falsi retém o ponto no qual o valor da fun-
ção tem sinal oposto no ponto mais recente, assegurando desta
forma, que a raiz continue isolada entre dois pontos.
3 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: Primeira coluna 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
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 .
2
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 .
Norma de Matriz
• Norma do Máximo (norma linha):
‖A‖∞ = máx
1≤i≤n
n∑
j=1
|aij |;
• Norma da Soma (norma coluna):
‖A‖1 = máx
1≤j≤n
n∑
i=1
|aij |;
• Norma Euclidiana:
‖A‖E =
√√√√ n∑
i,j=1
a2ij
Método de Gauss-Jacobi
Convergência: São duas situações:
1. Se A for estritamente diagonalmente dominante (e.d.d.),
isto é,
n∑
j=1
|aij |
j 6=i
< |aii|, i = 1, 2, . . . , n .
2. Ou se ‖F‖∞ < 1 ou ‖F‖1 < 1, onde F = (fij) é dada por
fij =
{
0, i = j
−aijaii , i 6= j
(1)
Algoritmo:
x
(k+1)
1 =
1
a11
(
b1 − a12 x(k)2 − a13 x(k)3 − ...− a1n x(k)n
)
x
(k+1)
2 =
1
a22
(
b2 − a21 x(k)1 − a23 x(k)3 − ...− a2n x(k)n
)
...
...
x(k+1)n =
1
ann
(
bn − an1 x(k)1 − an2 x(k)2 − ...− ann−1 x(k)n−1
)
Critério da Parada:
‖X(k+1) −X(k)‖∞
‖X(k+1)‖∞ < ε
onde ε é a precisão pré-fixada.
Método de Gauss-Seidel
Convergência: Ocorre nas seguintes situações:
1. O critério de Sanssenfeld for satisfeito, isto é, se
máx
1≤i≤n
βi < 1,
onde
βi =
i−1∑
j=1
∣∣∣∣aijaii
∣∣∣∣ βj + n∑
j=i+1
∣∣∣∣aijaii
∣∣∣∣ , i = 1, 2, . . . , n.
2. Se a matriz A do sistema AX = B for estritamente diago-
nalmente dominante.
3. O critério das linhas é satisfeito, isto é, ‖F‖∞ < 1, onde F
é dado em (1).
Algoritmo:
x
(k+1)
1 =
1
a11
(
b1 − a12 x(k)2 − a13 x(k)3 − ...− a1n x(k)n
)
x
(k+1)
2 =
1
a22
(
b2 − a21 x(k+1)1 − a23 x(k)3 − ...− a2n x(k)n
)
x
(k+1)
3 =
1
a33
(
b3 − a31 x(k+1)1 − a32 x(k+1)2 − a34 x(k)4 ...− a3n x(k)n
)
...
...
x(k+1)n =
1
ann
(
bn − an1 x(k+1)1 − an2 x(k+1)2 − ...− ann−1 x(k+1)n−1
)
Critério da Parada:
‖X(k+1) −X(k)‖∞
‖X(k+1)‖∞ < ε
onde ε é a precisão pré-fixada.
3