d. Construa um algoritmo utilizando a eliminação de Gauss para descobrir A^{-1}, 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 n^{3} multiplicações/divisões e n^{3}-2 n^{2}+n adições/subtrações.
e. Mostre que a resolução do sistema linear A \mathbf{x}=\mathbf{b}, quando A^{-1} for conhecido, ainda exige n^{2} multiplicações/divisōes e n^{2}-n adições/subtrações.
f. Mostre que a resolução de m sistemas lineares A \mathbf{x}^{(p)}=\mathbf{b}^{(p)}, para p=1,2, \ldots, m, pelo método \mathbf{x}^{(\rho)}=A^{-1} \mathbf{b}^{(\rho)} requer m n^{2} multiplicaçöes e m\left(n^{2}-n\right) adições, se A^{-1} for conhecido.
g. Seja A uma matriz n \times n. Compare o número de operações necessárias para resolver n sistemas lineares envolvendo A por eliminação de Gauss com substituição regressiva e invertendo A, em primeiro lugar, e depois multiplicando A \mathbf{x}=\mathbf{b} por A^{-1}, para n=3,10,50,100. Es sempre vantajoso calcular A^{-1} com a finalidade de resolver de sistemas lineares?

Passo 1

Resumo do enunciado: queremos comparar o custo em operações aritméticas de três procedimentos:
  1. usar eliminação de Gauss para calcular A^{-1} (parte d),
  2. resolver um sistema A\mathbf x=\mathbf b quando A^{-1} já é conhecido (parte e) e generalizar para m sistemas (parte f),
  3. comparar o custo de resolver n sistemas usando eliminaçã o+substituição para cada um contra calcular primeiro A^{-1} e depois multiplicar por \mathbf b (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 A^{-1}: escrevemos a matriz aumentada \bigl[A\mid I\bigr] de tamanho n\times 2n e fazemos eliminações de pivô em cada coluna k=1,2,\dots,n até zerar todas as entradas fora da diagonal de A, transformando o lado esquerdo em I e o lado direito em A^{-1}.
Cálculo do número de operações:
  • Para cada pivô k=1,\dots,n-1 e para cada linha i=k+1,\dots,n fazemos
  1. divisão para obter o multiplicador m_{ik} (1 operação),
  2. atualização das colunas j=k+1,\dots,n de A (cada uma: 1 multiplicação +1 subtração),
  3. atualização das n colunas correspondentes à parte I (cada uma: 1 multiplicação +1 subtração).
  • Seja s=n-k. Então, para cada k temos para cada i:
    \bullet 1 divisão,
    s multiplicaçõe s+subtrações na parte A,
    n multiplicaçõe s+subtrações na parte I.
  • Somando sobre k=1 a n-1 e i, o total de multiplicações/divisões é
\sum_{k=1}^{n-1}(n-k)\bigl[1 + (n-k)+n\bigr] =\sum_{s=1}^{n-1}s\,(2n-s+1) =n^{3},
e o total de adições/subtrações é
\sum_{k=1}^{n-1}(n-k)\bigl[(n-k)+(n)\bigr] =\sum_{s=1}^{n-1}s\,(2n-s) =n^{3}-2n^{2}+n.

Passo 3

Para resolver A\mathbf x=\mathbf b conhecendo A^{-1} basta calcular \mathbf x=A^{-1}\mathbf b. Cada componente \displaystyle x_i=\sum_{j=1}^{n}(A^{-1})_{ij}\,b_j
exige n multiplicações e n-1 somas. Como há n componentes, totalizamos
• multiplicações/divisões: n\times n = n^{2},
• adições/subtrações: n\times(n-1)=n^{2}-n.

Passo 4

Para m sistemas A\mathbf x^{(p)}=\mathbf b^{(p)}, p=1,\dots,m, repetimos o produto matriz-vetor m vezes. Logo
• multiplicações/divisões: m\,n^{2},
• adições/subtrações: m\,(n^{2}-n).

Passo 5

Comparemos agora o custo de resolver n sistemas de duas maneiras:
A) aplicar eliminação de Gaus s+substituição independente a cada sistema (ou seja, para cada \mathbf b^{(p)} fazemos eliminação numa matriz n\times(n+1)). O custo típico de eliminação num sistema é da ordem de \tfrac13n^{3} multiplicações (e termos de grau inferior). Para n sistemas isso dá aproximadamente
\text{eliminações repetidas:}\quad n\times\frac{1}{3}n^{3} \;=\;\frac{1}{3}n^{4}\quad\text{multiplicações}.çõçõ
B) primeiro invertamos A (custo de parte d: n^{3} multiplica./divisões) e depois façamos n produtos A^{-1}\mathbf b (custo de parte f: n\times n^{2}=n^{3} multiplica.). Total
\text{inversão+produtos:}\quad n^{3}+n^{3}=2\,n^{3}\quad\text{multiplicações}.ãçõ
Para n=3,10,50,100 temos
\begin{array}{c|c|c} n&\tfrac{1}{3}n^{4}&2\,n^{3}\\hline 3&\tfrac13\cdot81=27&2\cdot27=54\\\\ 10&\tfrac13\cdot10^{4}\approx3333&2\cdot10^{3}=2000\\\\ 50&\tfrac13\cdot50^{4}\approx2\,083\,333&2\cdot125\,000=250\,000\\\\ 100&\tfrac13\cdot10^{8}\approx33\,333\,333&2\cdot10^{6}=2\,000\,000 \end{array}
Para n=3 o método A (eliminação repetida) é mais barato; para n\ge10 o método B (inversão seguida de multiplicações) já fica vantajoso.
Não é, portanto, sempre vantajoso calcular A^{-1} para resolver sistemas: para matrizes muito pequenas compensa eliminar cada vez, mas a partir de certo tamanho (aqui já a partir de n\approx6 no nosso critério) vale a pena achar a inversa e só depois multiplicar.

Resposta

d. n^{3} multiplicações/divisões e n^{3}-2n^{2}+n adições/subtrações.
e. n^{2} multiplicações/divisões e n^{2}-n adições/subtrações.
f. m\,n^{2} multiplicações/divisões e m\,(n^{2}-n) adições/subtrações.
g. Para resolver n sistemas:
– eliminação repetida: \tfrac{1}{3}n^{4} multiplicações;
– inversão + produtos: 2n^{3} multiplicações.
Em n=3 compensa eliminação repetida, em n\ge10 compensa inversão. Portanto, não é sempre vantajoso calcular A^{-1}; só quando n (ou o número de sistemas) for suficientemente grande.