Sistemas Triangulares

. Uma matriz é dita triangular se for triangular superior ou inferior.

Um sistema linear cuja matriz dos coeficientes é uma matriz triangular é denominado um sistema triangular e sua resolução é particularmente mais fácil e de baixo custo. Na eliminação Gaussiana, utilizamos operações elementares para reduzir um sistema linear até sua forma triangular, facilitando assim sua resolução.

Sistema Triangular Superior

Definição: Um sistema linear

Ax = b

com

n

equações e

n

incógnitas, tal que

A

é uma matriz

n \times n

invertível e triangular superior, é denominado sistema triangular superior e pode ser escrito da forma:

\left\lbrace \begin{array}{ccccccccccc} a_{11}x_1 & + & a_{12}x_2 & + & a_{13}x_3 & + & \cdots & + & a_{1n}x_n & = & b_1 \\ & & a_{22}x_2 & + & a_{23}x_3 & + & \cdots & + & a_{2n}x_n & = & b_2 \\ & & & & a_{33}x_3 & + & \cdots & + & a_{3n}x_n & = & b_3 \\ & & & & & & \ddots & & & \vdots & \\ & & & & & & & & a_{nn}x_n & = & b_n \end{array} \right.

uma vez que

a_{ij} = 0

para

i > j

.

Observe que a última equação desse sistema envolve apenas a incógnita

x_n

, a penúltima envolve

x_n

x_{n-1}

e assim por diante. Da última equação obtemos:

x_n = \frac{b_n}{a_{nn}}

Substituíndo na penúltima equação, obtemos:

a_{(n-1)(n-1)}x_{(n-1)} + a_{(n-1)n}x_n = b_{(n-1)} \Rightarrow a_{(n-1)(n-1)}x_{(n-1)} = b_{(n-1)} - a_{(n-1)n} x_n \Rightarrow

\Rightarrow x_{(n-1)} = \frac{b_{(n-1)} - a_{(n-1)n} x_n}{a_{(n-1)(n-1)}}

Agora que encontramos

x_n

x_{n-1}

podemos substituí-los na

(n-2)

-ésima equação e obter

x_{n-2}

e assim por diante obtemos

x_{n-3}, ..., x_2, x_1

. Conhecidas as incógnitas

x_{i+1}, ..., x_{n-1}, x_n

, a incógnita

x_i

é obtida da seguinte forma:

x_i = \frac{b_i - \left( a_{i (i+1)}x_{i+1} + ... + a_{i(n-1)}x_{n-1} + a_{in}x_n \right) }{a_{ii}} \Leftrightarrow

\Leftrightarrow x_i = \frac{b_i - \sum_{j = i+1}^{n}{a_{ij}x_j}}{a_{ii}}

Observe que para a resolução desse sistema estamos sempre dividindo por

a_{ii}

i = 1,2,...,n

e para isso precisamos ter

a_{ii} \neq 0

, mas isso é garantido pois

A

é uma matriz invertível e logo

det(A) \neq 0

, ou seja,

a_{ii} \neq 0

, para

i = 1,2,...,n

.

Exemplo 1: Considere o seguinte sistema triangular superior:

\left\lbrace \begin{array}{rrrrrrr} 2x_1 & + & x_2 & + & 3x_3 & = & 11 \\ & & x_2 & - & x_3 & = & 1 \\ & & & & 2x_3 & = & 4 \end{array} \right.

Da última equação obtemos diretamente que:

x_3 = \frac{4}{2} \Rightarrow x_3 = 2

Substituíndo na segunda equação, obtemos:

x_2 = 1 + x_3 = 1 + 2 \Rightarrow x_2 = 3

E por fim, substituíndo na primeira equação, obtemos:

x_1 = \frac{11 - x_2 - 3x_3}{2} = \frac{11 - (3) - 3(2)}{2} = \frac{2}{2} \Rightarrow x_1 = 1

Portanto, a solução do sistema é

(x_1,x_2,x_3) = (1,3,2)

.

Algoritmo (Resolução de um Sistema Triangular Superior): Considere um sistema triangular superior

Ax = b

, onde

A

é uma matriz

n \times n

com elementos da diagonal não nulos. As variáveis

x_n, x_{n-1}, ..., x_1

podem ser obtidas da seguinte forma:
Algoritmo.

Voltar ao Topo.

Sistema Triangular Inferior

Definição: Um sistema linear

Ax = b

com

n

equações e

n

incógnitas, tal que

A

é uma matriz

n \times n

invertível e triangular inferior, é denominado sistema triangular inferior e pode ser escrito da forma:

\left\lbrace \begin{array}{ccccccccccc} a_{11}x_1 & & & & & & & = & b_1\\ a_{21}x_1 & + & a_{22}x_2 & & & & & = & b_2\\ a_{31}x_1 & + & a_{32}x_2 & + & a_{33}x_3 & & & = & b_3 \\ \vdots & & & & & \ddots & & \vdots &\\ a_{n1}x_1 & + & a_{n2}x_2 & + & \cdots & + & a_{nn}x_n & = & b_n \end{array} \right.

uma vez que

a_{ij} = 0

para

i < j

.

Observe que nesse caso, a primeira equação do sistema envolve apenas a incógnita

x_1

, a segunda equação envolve

x_1

x_2

e assim por diante. Da primeira equação, obtemos facilmente que:

x_1 = \frac{b_1}{a_{11}}

Substituíndo na segunda equação, obtemos:

a_{21}x_1 + a_{22}x_2 = b_2 \Rightarrow a_{22}x_2 = b_2 - a_{21}x_1 \Rightarrow x_2 = \frac{b_2 - a_{21}x_1}{a_{22}}

Agora, podemos substituir os valores de

x_1

x_2

na terceira equação e encontrar

x_3

, e assim por diante encontramos

x_4, ..., x_{n-1}, x_n

. Conhecidas as incógnitas

x_1, x_2, ..., x_{i-1}

, a incógnita

x_i

é obtida da seguinte maneira:

x_i = \frac{b_i - \left( a_{i1}x_1 + a_{i2}x_2 + ... + a_{i(i-1)}x_{i-1}\right) }{a_{ii}} \Leftrightarrow

\Leftrightarrow x_i = \frac{b_i - \sum_{j=1}^{i-1} a_{ij}x_j}{a_{ii}}

Observe que para a resolução desse sistema estamos sempre dividindo por

a_{ii}

i = 1,2,...,n

e para isso precisamos ter

a_{ii} \neq 0

, mas isso é garantido pois

A

é uma matriz invertível e logo

det(A) \neq 0

, ou seja,

a_{ii} \neq 0

, para

i = 1,2,...,n

.

Exemplo 2: Considere o seguinte sistema triangular inferior:

\left\lbrace \begin{array}{rrrrrrr} 3x_1 & & & & & = & 9 \\ x_1 & + & 2x_2 & & & = & 5 \\ 2x_1 & - & 4x_2 & + & x_3 & = & 7 \end{array} \right.

Da primeira equação obtemos que:

x_1 = \frac{9}{3} \Rightarrow x_1 = 3

Substituíndo na segunda equação, temos:

x_2 = \frac{5 - x_1}{2} = \frac{5 - 3}{2} = \frac{2}{2} \Rightarrow x_2 = 1

E finalmente, substituíndo na última equação, obtemos:

x_3 = 7 - 2x_1 + 4x_2 = 7 - 2(3) + 4(1) \Rightarrow x_3 = 5

Portanto, a solução do sistema é

(x_1,x_2,x_3) = (3, 1, 5)

.

Algoritmo (Resolução de um Sistema Triangular Inferior): Considere um sistema triangular inferior

Ax = b

, onde

A

é uma matriz

n \times n

com elementos da diagonal não nulos. As variáveis

x_1, x_2, ..., x_n

podem ser obtidas da seguinte forma:
Algoritmo.

Número de operações: Vamos calcular o número de operações realizadas no algoritmo de resolução de um sistema triangular inferior. O mesmo número vale para o algoritmo de resolução do sistema triangular superior.

No início realizamos uma única divisão:

x_1 = \frac{b_1}{a_{11}}

ou seja, uma única operação. Considerando que para cada valor de

i

, com

i = 2, ..., n

é realizado o cálculo de

x_i

x_i = \frac{(b_i - s)}{a_{ii}}

e este cálculo envolve duas operações (uma subtração e uma divisão), teremos um total de:

2(n-1) = 2n - 2 \;\;\;\; operações

Contabilizando o cálculo das somas

s

: para cada valor de

i

, o laço

j

é repetido

(i-1)

vezes. Logo, este cálculo acontece:

1 + 2 + 3 + ... + (n-1) = \sum_{k = 1}^{n-1} k = \frac{n(n-1)}{2} = \frac{n^2 - n}{2} \;\; vezes

E a cada vez, são realizadas duas operações (uma multiplicação e uma soma). Totalizando este número de operações, teremos:

\frac{2(n^2-n)}{2} = n^2 - n \;\; operações

Portanto, realizamos no total:

1 + 2n - 2 + n^2 -n = n^2 + n - 1 \;\; operações

Logo, o número de operações necessárias para a resolução de um sistema triangular é da ordem de

n^2

.

Voltar ao Topo.

Última Atualização: 02/02/2016.