8. Determine quantas multiplicações são efetuadas no algoritmo da fatoração LUP para:
a) uma matriz de ordem n, completa;
b) uma matriz de ordem n, tridiagonal.
a) Observe que, no algoritmo da fatoração LUP, para k=1, temos (n-1) repetições em i e (n - 1) repetições em j, efetuando um produto a cada iteração em j, i.e. (n - 1)²; para k=2, temos (n - 2) repetições em i e (n - 2) repetições em j, efetuando um produto a cada iteração em j, i.e. (n - 2)². Em geral, teremos (n - 1)² + (n - 2)² +...+ (n - (n - 1))² = n³⁄3 - n²⁄2 + n⁄6 multiplicações.
b) Para uma matriz tridiagonal, devemos observar que num bloco ativo da fatoração LUP, teremos duas linhas com apenas dois elementos não-nulos, e as demais com apenas três elementos não-nulos. Por analogia com a análise feita em (a), para k=1, teremos 2 linhas com apenas 2 produtos a serem efetuados (linhas i = k + 1 = 2 e i = n), e (n - 1) - 2 linhas com apenas 3 produtos a serem efetuados; para k=2, teremos 2 linhas com apenas 2 produtos a serem efetuados (linhas i = k + 2 = 3 e i = n), e (n - 1) - 3 linhas com apenas 3 produtos a serem efetuados. Em geral, teremos (3((n-1)-2)+4) + (3((n-2)-2)+4)+...+(3((n-(n-2))-2)+4) = 3n² - 7n +2 multiplicações.
a) uma matriz de ordem n, completa;
b) uma matriz de ordem n, tridiagonal.
a) Observe que, no algoritmo da fatoração LUP, para k=1, temos (n-1) repetições em i e (n - 1) repetições em j, efetuando um produto a cada iteração em j, i.e. (n - 1)²; para k=2, temos (n - 2) repetições em i e (n - 2) repetições em j, efetuando um produto a cada iteração em j, i.e. (n - 2)². Em geral, teremos (n - 1)² + (n - 2)² +...+ (n - (n - 1))² = n³⁄3 - n²⁄2 + n⁄6 multiplicações.
b) Para uma matriz tridiagonal, devemos observar que num bloco ativo da fatoração LUP, teremos duas linhas com apenas dois elementos não-nulos, e as demais com apenas três elementos não-nulos. Por analogia com a análise feita em (a), para k=1, teremos 2 linhas com apenas 2 produtos a serem efetuados (linhas i = k + 1 = 2 e i = n), e (n - 1) - 2 linhas com apenas 3 produtos a serem efetuados; para k=2, teremos 2 linhas com apenas 2 produtos a serem efetuados (linhas i = k + 2 = 3 e i = n), e (n - 1) - 3 linhas com apenas 3 produtos a serem efetuados. Em geral, teremos (3((n-1)-2)+4) + (3((n-2)-2)+4)+...+(3((n-(n-2))-2)+4) = 3n² - 7n +2 multiplicações.
Nenhum comentário:
Postar um comentário