4.3 Sistemas triangulares

---

Considere um sistema linear onde a matriz é triangular superior, ou seja,

$$\left[\begin{array}{cccc}\hfill a_{11}\hfill & \hfill a_{12}\hfill & \hfill \cdots \hfill & \hfill a_{1n}\hfill \\ \hfill 0\hfill & \hfill a_{22}\hfill & \hfill \cdots \hfill & \hfill a_{2n}\hfill \\ \hfill ⋮\hfill & \hfill ⋮\hfill & \hfill \ddots \hfill & \hfill ⋮\hfill \\ \hfill 0\hfill & \hfill \dots \hfill & \hfill 0\hfill & \hfill a_{nn}\hfill \end{array}\right]\left[\begin{array}{c}\hfill x_1\hfill \\ \hfill x_2\hfill \\ \hfill ⋮\hfill \\ \hfill x_n\hfill \end{array}\right]=\left[\begin{array}{c}\hfill b_1\hfill \\ \hfill b_2\hfill \\ \hfill ⋮\hfill \\ \hfill b_n\hfill \end{array}\right]$$

(4.68)

tal que todos elementos abaixo da diagonal são iguais a zero.

Podemos resolver esse sistema iniciando pela última equação e isolando $x_n$ obtemos

$$x_n=b_n∕a_{nn}$$

(4.69)

Substituindo $x_n$ na penúltima equação

$$a_{n-1,n-1}{x}_{n-1}+a_{n-1,n}{x}_n=b_{n-1}$$

(4.70)

e isolando $x_{n-1}$ obtemos

$$x_{n-1}=\left(b_{n-1}-a_{n-1,n}{x}_n\right)∕a_{n-1,n-1}$$

(4.71)

e continuando desta forma até a primeira equação obteremos

$$x_1=\left(b_1-a_{12}{x}_2\cdots -a_{1n}{x}_n\right)∕a_{11}.$$

(4.72)

De forma geral, temos que

$$x_i=\left(b_i-a_{i,i+1}{x}_{i+1}\cdots -a_{i,n}{x}_n\right)∕a_{i,i},i=2,\dots ,n.$$

(4.73)

4.3.1 Código Scilab: resolução de um sistema triangular superior

---

Para resolver um sistema triangular superior iniciamos da última linha em direção a primeira.

4.3.2 Código Scilab: resolução de um sistema triangular inferior

---

Para resolver um sistema triangular inferior podemos fazer o processo inverso iniciando da primeira equação.

Custo computacional

---

Vamos contar o número total de flops para resolver um sistema triangular inferior. Note que o custo para um sistema triangular superior será o mesmo.

Na linha 3, temos uma divisão, portanto 1 flop.

Na linha 5 quando $i=2$, temos

     x(2)=(b(2)-L(2,1:1)*x(1:1))/L(2,2),

ou seja, 1 subtração+1 multiplicação + 1 divisão $=3$ flops.

Quando $i=3$,

     x(3)=(b(3)-L(3,1:2)*x(1:2))/L(3,3)

temos 1 subtração+(2 multiplicações + 1 soma) +1 divisão $=5$ flops.

Quando $i=4$, temos 1 subtração+(3 multiplicações + 2 somas) +1 divisão $=7$ flops.

Até que para $i=n$, temos

     x(n)=(b(n)-L(n,1:n-1)*x(1:n-1))/L(n,n),

com $1$ subtração+($n-1$ multiplicações + $n-2$ somas) + $1$ divisão, ou seja, $1+\left(n-1+n-2\right)+1=2n-1$ flops.

Somando todos esses custos³ temos que o custo para resolver um sistema triangular inferior é

$$1+3+5+7+...+2n-1=\sum _{k=1}^n\left(2k-1\right)=2\sum _{k=1}^{n}k-\sum _{k=1}^{n}1$$

(4.75)

e utilizando que a soma dos $k$ inteiros é a soma dos termos de uma progressão aritmética⁴

$$2\left(n\left(n+1\right)∕2\right)-n=n^2\text{ flops}.$$

(4.76)