Enunciado

3. Verifique que o número de operações necessárias no método de Eliminação de Gauss, sem pivoteamento parcial, é 2 n 3 3 + n 2 2 - 7 n 6 , na fase de triangularização da matriz A, e n 2 , na fase de resolução do sistema triangular superior. Estão sendo contadas as operações de divisão, multiplicação e soma.

Lembrando que ∑ k = 1 n - 1 k 2 = n - 1 n ( 2 n - 1 ) 6

Passo 1

O objetivo do método de Gauss consiste em eliminar os elementos a i j de forma a obter um sistema equivalente com uma matriz triangular superior. Tendo uma matriz triangular, basta aplicar substituições sucessivas para chegarmos à solução pretendida.

O método consiste em  n - 1 passos, onde construímos elementos  a i j ( k + 1 ) a partir dos elementos  a i j ( k ) considerando como [ a i j 1 ] a matriz inicial.

Desse modo, para um passo k , com k indo de 1 até n - 1 ...

  • Se o pivô a k k ( k ) = 0 então é preciso efetuar a troca de linha.
  • Já se a k k ( k ) ≠ 0 , temos o exposto na seguinte imagem abaixo:

Passo 2

No final dos n - 1 passos, obtemos o sistema triangular superior equivalente:

a 11 1 … … a 1 n 1 0 a 22 2 … a 2 n 2 ⋮ ⋱ ⋱ ⋮ 0 … 0 a n n n x 1 ⋮ ⋮ x n = b 1 1 b 2 2 ⋮ b n n

Cuja resolução é dada através de substituição ascendente...

x n = b n ( n ) a n n ( n )

E obtemos então, que...

x k = b k k - ∑ j = k + 1 n a j k k x j a k k ( k ) ,   k   d e s d e   1   a t é   n - 1

Passo 3

Agora, vamos ver qual o número de operações ( + - o u * / ) envolvido na resolução de um sistema

Na fase de triangularização da matriz A para cada passo m i k , temos um total de n - k divisões, o que corresponde a um total de...

∑ k = 1 n - 1 n - k

E calculando os a i j , temos um total de n - k 2 multiplicações e subtrações, o que corresponde a um total de...

∑ k = 1 n - 1 n - k 2

Quanto ao cálculo de b ( n ) , para cada passo k , temos n - k multiplicações e subtrações, o que nos faz chegar à...

∑ k = 1 n - 1 n - k

Sendo assim, no total temos que...

∑ k = 1 n = 1 n - k = n n - 1 2

E também...

∑ k = 1 n = 1 n - k 2 = n ( n - 1 ) ( 2 n - 1 ) / 6

E então, chegamos ao número de operações proposta pelo enunciado, que é dada por...

N ú m e r o   d e   o p e r a ç õ e s   n e c e s s á r i a s = 2 n 3 3 + n 2 2 - 7 n 6

Resposta

∑ k = 1 n = 1 n - k 2 = n n - 1 2 n - 1 6 → 2 n 3 3 + n 2 2 - 7 n 6

Ver Outros Exercícios desse livro

Exercícios de Livros Relacionados

Resolva o sistema linear abaixo utilizando o método da Eliminação de Gauss:
Para cada um dos sistemas lineares a seguir, analise a existência ou não de solução, bem como unicidade de solução, no caso de haver existência.
Para cada um dos sistemas lineares a seguir, analise a existência ou não de solução, bem como unicidade de solução, no caso de haver existência.
Para cada um dos sistemas lineares a seguir, analise a existência ou não de solução, bem como unicidade de solução, no caso de haver existência.
Para cada um dos sistemas lineares a seguir, analise a existência ou não de solução, bem como unicidade de solução, no caso de haver existência.