Sistemas Lineares

Conceitos de solução de sistemas lineares: método direto (exato) e método interativo

Os métodos numéricos destinados a resolver sistemas lineares são divididos em dois grupos: os métodos diretos e os métodos iterativos.

Métodos diretos

São métodos que produzem a solução exata de um sistema, a menos de erros de arredondamento, depois de um número finito de operações aritméticas. Com esses métodos é possível determinar, a priori, o tempo máximo gasto para resolver um sistema, uma vez que sua complexidade é conhecida. A clássica Regra de Cramer, ensinada no ensino médio, é um método direto. Entretanto, pode-se mostrar que o número máximo de operações aritméticas envolvidas na resolução de um sistema n × n por este método é (n + 1) (n!n − 1) + n. Assim, um computador que efetua uma operação aritmética em 10−8 segundos gastaria cerca de 36 dias para resolver um sistema de ordem n = 15. A complexidade exponencial desse algoritmo inviabiliza sua utilização em casos práticos. O estudo de métodos mais eficientes torna-se, portanto, necessário, uma vez que, em geral, os casos práticos exigem a resolução de sistemas lineares de porte mais elevado. Apresentaremos, a seguir, métodos mais eficientes, cuja complexidade é polinomial, para resolver sistemas lineares. Antes, porém, introduziremos uma base teórica necessária à apresentação de tais métodos.

Método de Gauss

O método de Gauss consiste em operar transformações elementares sobre as equações de um sistema Ax = b até que, depois de n−1 passos, se obtenha um sistema triangular superior, Ux = c.

...