livro-py-56

Prévia do material em texto

100 Cálculo Numérico
flutuante (flops) feitas pelo algoritmo (observe que o tempo total não depende ape-
nas disso, mas também de outros fatores como memória, taxas de transferências
de dados da memória para o cpu, redes,...). Entretanto vamos nos concentrar na
contagem do número de operações (flops) para realizar determinada tarefa.
No passado (antes dos anos 80), os computadores demoravam mais tempo para
realizar operações como multiplicação e divisão, se comparados à adição ou à sub-
tração. Assim, em livros clássicos eram contados apenas o custo das operações
× e /. Nos computadores atuais as quatro operações básicas demandam aproxi-
madamente o mesmo tempo. Não obstante, como na maioria dos algoritmos de
álgebra linear, o número de multiplicações e divisões é proporcional ao número
somas e subtrações (pois a maioria dessas operações podem ser escritas como a
combinações de produtos internos), é justificável dizer que o tempo de computação
continua podendo ser estimado pelo número de multiplicações e divisões. Desta
forma, na maior parte deste material, levaremos em conta somente multiplicações
e divisões, a não ser que mencionado o contrário.
Teremos em mente que a ideia é estimar o custo quando lidamos com vetores
e matrizes muito grande, isto é, o custo quando estas dimensões crescem infinita-
mente.
Exemplo 4.2.1 (Produto escalar-vetor). Qual o custo para multiplicar um escalar
por um vetor?
Solução. Seja a ∈ R e xxx ∈ Rn, temos que
axxx = [a× x1, a× x2, ...,a× xn] (4.44)
usando n multiplicações, ou seja, um custo computacional, C, de
C = n flops. (4.45)
♦
Exemplo 4.2.2 (Produto vetor-vetor). Qual o custo para calcular o produto in-
terno xxx · yyy?
Solução. Sejam xxx,yyy ∈ Rn, temos que
xxx · yyy = x1 × y1 + x2 × y2 + ...+ xn × yn (4.46)
São realizadas n multiplicações (cada produto xi por yi) e n−1 somas, ou seja,
o custo total de operações é de
C := (n) + (n− 1) = 2n− 1 flops (4.47)
♦
Licença CC-BY-SA-3.0. Contato: reamat@ufrgs.br
https://creativecommons.org/licenses/by-sa/3.0/
reamat@ufrgs.br
4.2. COMPLEXIDADE DE ALGORITMOS EM ÁLGEBRA LINEAR 101
Exemplo 4.2.3 (Produto matriz-vetor). Qual o custo para calcular o produto de
matriz por vetor Axxx?
Solução. Sejam A ∈ Rn×n e xxx ∈ Rn, temos que
a11 a12 · · · a1n
... ...
an1 · · · ann


x1
...
xn
 =

a11 × x1 + a12x2 + ...+ a1n × xn
...
an1 × x1 + an2x2 + ...+ ann × xn
 (4.48)
Para obter o primeiro elemento do vetor do lado direito, devemos multiplicar
a primeira linha de A pelo vetor coluna xxx. Note que esse é exatamente o custo
do produto vetor-vetor do exemplo anterior. Como o custo para cada elemento do
vetor do lado direito é o mesmo e temos n elementos, teremos que o custo para
multiplicar matriz-vetor é1
C := n · (2n− 1) = 2n2 − n flops. (4.50)
À medida que n→∞, temos
O(2n2 − n) = O(2n2) = O(n2) flops. (4.51)
♦
Exemplo 4.2.4 (Produto matriz-matriz). Qual o custo para calcular o produto
de duas matrizes A e B?
Solução. Sejam A,B ∈ Rn×n temos que
a11 a12 · · · a1n
... ...
an1 · · · ann


b11 b12 · · · a1n
... ...
bn1 · · · bnn
 =

c11 c12 · · · c1n
... ...
cn1 · · · cnn
 (4.52)
onde o elemento dij é o produto da linha i de A pela coluna j de B,
dij = ai1 × b1j + ai2 × b2j + ...+ ai2 × b2j (4.53)
1Contando apenas multiplicações/divisões obtemos
n · O(n) = O(n2) flops. (4.49)
Licença CC-BY-SA-3.0. Contato: reamat@ufrgs.br
https://creativecommons.org/licenses/by-sa/3.0/
reamat@ufrgs.br