d. Construa um algoritmo utilizando a eliminação de Gauss para descobrir
, mas não faça multiplicações quando for conhecido que um dos fatores é 1, e não faça adições/subtrações quando for conhecido que um dos elementos envolvidos é 0 . Mostre que os cálculos necessários são reduzidos para
multiplicações/divisões e
adições/subtrações.
e. Mostre que a resolução do sistema linear
, quando
for conhecido, ainda exige
multiplicações/divisōes e
adições/subtrações.
f. Mostre que a resolução de
sistemas lineares
, para
, pelo método
requer
multiplicaçöes e
adições, se
for conhecido.
g. Seja
uma matriz
. Compare o número de operações necessárias para resolver
sistemas lineares envolvendo
por eliminação de Gauss com substituição regressiva e invertendo
, em primeiro lugar, e depois multiplicando
por
, para
. Es sempre vantajoso calcular
com a finalidade de resolver de sistemas lineares?
e. Mostre que a resolução do sistema linear
f. Mostre que a resolução de
g. Seja
Passo 1
Resumo do enunciado: queremos comparar o custo em operações aritméticas de três procedimentos:
- usar eliminação de Gauss para calcular
(parte d), - resolver um sistema
quando já é conhecido (parte e) e generalizar para sistemas (parte f), - comparar o custo de resolver
sistemas usando eliminaçã ubstituição para cada um contra calcular primeiro e depois multiplicar por (parte g).
Para isso, precisaremos contabilizar cuidadosamente multiplicações/divisões e adições/subtrações, evitando multiplicar por 1 e somar 0 sempre que possível.
Passo 2
Algoritmo de Gauss–Jordan para
: escrevemos a matriz aumentada
de tamanho
e fazemos eliminações de pivô em cada coluna
até zerar todas as entradas fora da diagonal de
, transformando o lado esquerdo em
e o lado direito em
.
Cálculo do número de operações:
Cálculo do número de operações:
- Para cada pivô
e para cada linha fazemos
- divisão para obter o multiplicador
(1 operação), - atualização das colunas
de (cada uma: 1 multiplicação subtração), - atualização das
colunas correspondentes à parte (cada uma: 1 multiplicação subtração).
- Seja
. Então, para cada temos para cada :
divisão,
•multiplicaçõe ubtrações na parte ,
•multiplicaçõe ubtrações na parte . - Somando sobre
a e , o total de multiplicações/divisões é
e o total de adições/subtrações é
Passo 3
Para resolver
conhecendo
basta calcular
. Cada componente
exige multiplicações e
somas. Como há
componentes, totalizamos
• multiplicações/divisões: ,
• adições/subtrações: .
exige
• multiplicações/divisões:
• adições/subtrações:
Passo 4
Para
sistemas
,
, repetimos o produto matriz-vetor
vezes. Logo
• multiplicações/divisões: ,
• adições/subtrações: .
• multiplicações/divisões:
• adições/subtrações:
Passo 5
Comparemos agora o custo de resolver
sistemas de duas maneiras:
A) aplicar eliminação de Gaus ubstituição independente a cada sistema (ou seja, para cada
fazemos eliminação numa matriz
). O custo típico de eliminação num sistema é da ordem de
multiplicações (e termos de grau inferior). Para
sistemas isso dá aproximadamente
A) aplicar eliminação de Gaus
B) primeiro invertamos
(custo de parte d:
multiplica./divisões) e depois façamos
produtos
(custo de parte f:
multiplica.). Total
Para
temos
Para
o método A (eliminação repetida) é mais barato; para
o método B (inversão seguida de multiplicações) já fica vantajoso.
Não é, portanto, sempre vantajoso calcular
para resolver sistemas: para matrizes muito pequenas compensa eliminar cada vez, mas a partir de certo tamanho (aqui já a partir de
no nosso critério) vale a pena achar a inversa e só depois multiplicar.
Resposta
d.
multiplicações/divisões e
adições/subtrações.
e. multiplicações/divisões e
adições/subtrações.
f. multiplicações/divisões e
adições/subtrações.
g. Para resolver sistemas:
– eliminação repetida: multiplicações;
– inversão + produtos: multiplicações.
Em compensa eliminação repetida, em
compensa inversão. Portanto, não é sempre vantajoso calcular
; só quando
(ou o número de sistemas) for suficientemente grande.
e.
f.
g. Para resolver
– eliminação repetida:
– inversão + produtos:
Em