Sistemas triangulares

Resolução de sistemas lineares triangulares

Vamos lá?

Nesta primeira aula sobre métodos numéricos para sistemas lineares, vamos começar com sistemas triangulares, por serem bem simples e, como veremos mais adiante, importantes em situações mais gerais.

Um sistema linear é dito quadrado quando a quantidade de equações do sistema é igual à quantidade de incógnitas. Já um sistema linear é dito triangular quando todos os elementos abaixo (ou acima) da diagonal são nulos. Sendo assim, por mais estranho que pareça, um sistema linear pode ser quadrado e triangular ao mesmo tempo!

Por que começamos o estudo de métodos numéricos para sistemas lineares por sistemas lineares quadrados e triangulares? Porque esses sistemas são simples de serem resolvidos, é fácil montar um algoritmo que encontre suas soluções e, principalmente, porque no caso de sistemas sem uma estrutura particular, veremos que uma estratégia de resolução será convertê-los em sistemas triangulares equivalentes, ou seja sistemas, que apesar de distintos, têm as mesmas soluções.

Um sistema triangular superior é aquele para o qual todas as entradas abaixo da diagonal são nulas. Note que não fazemos restrições sobre as entradas acima da diagonal, que podem ou não ser nulas. Como exemplo, um sistema linear triangular de ordem quatro tem a forma $$ \left\{ \begin{array}{rcrcrcrcr} a_{11}\: x_1 &+& a_{12}\: x_2 &+& a_{13}\: x_3 &+& a_{14}\: x_4 &=& b_1\\ & & a_{22}\: x_2 &+& a_{23}\: x_3 &+& a_{24}\: x_4 &=& b_2\\ & & & & a_{33}\: x_3 &+& a_{34}\: x_4 &=& b_3\\ & & & & & & a_{44}\: x_4 &=& b_4 \end{array} \right. $$

Claramente a última equação deste sistema linear determina diretamente o valor de $x_4,$ desde que $a_{44}$ seja não nulo. Mesmo que $a_{44}$ seja nulo, o sistema ainda pode ter solução, a depender do valor de $b_4.$ De qualquer modo, consideremos o caso mais simples, em que todos os coeficientes da diagonal são não nulos, ou seja, $a_{kk} \neq 0.$ Neste caso, determinamos progressivamente os valores de $x_4,$ $x_3$ (uma vez que $x_4$ já é conhecido), $x_2$ (uma vez que $x_4$ e $x_3$ são conhecidos) e, por fim, $x_1,$ usando $x_2$, $x_3$ e $x_4.$ No caso geral, $$ x_k = {b_k - \sum_{j=k+1}^n a_{kj}\:x_j \over a_{kk}}, \quad k=n,(n-1),\ldots, 1. $$

Esta fórmula explícita para a solução de um sistema linear triangular superior quase que diretamente motiva a construção de um algoritmo.

  • $x_n \leftarrow b_n/a_{nn}$
  • Para $k=(n-1),(n-2),\ldots,1$
    • $S \leftarrow b_k$
    • Para $j=k+1,\ldots,n$
      • $S \leftarrow S - a_{kj}x_j$
    • $x_k \leftarrow S/a_{kk}$

A análise desse algoritmo fica para a próxima aula.

Resolvendo sistemas no Octave

No Octave, a resolução de sistemas lineares é feita pelo operador \ (barra invertida). Por exemplo:

> A = [ 1 2 1; 3 0 4; 2 2 3 ]
A =

   1   2   1
   3   0   4
   2   2   3

> b = [2; 1; 3];
> x = A\b        # Resolução do sistema Ax = b
x =

  -1.0000
   1.0000
   1.0000

O operador \ faz diversas análises na matriz para escolher qual algoritmo utilizar na resolução do sistema linear. Claro que essa análise tem custo e se soubermos que a matriz, por exemplo, é tridiagonal, utilizar diretamente um algoritmo específico para esse caso é mais adequado. Em Quarteroni e Saleri (2007) p. 143 está descrito o algoritmo de decisão usado pelo operador \.

Referência

Gilbert Strang. Linear Algebra and Its Appllications. Thomson, Brooks/Cole, 2006.

A. Quarteroni e F. Saleri. Cálculo Científico com MATLAB e Octave. Springer, 2007.

1. Escreva a fórmula explícita para a solução de um sistema linear triangular inferior.

2. Suponha que um sistema linear triangular superior, de ordem $n,$ tem a propriedade adicional de ser de banda $3$, ou seja, $a_{ij} = 0,$ sempre que $j>i+3.$ Descreva como adequar a fórmula (e o algoritmo) para a resolução do sistema linear, aproveitando esta propriedade.