Algoritmo de Thomas

Muitos problemas de engenharia, após a aplicação de técnicas de discretização, recaem em sistemas que apresentam uma estrutura bem particular, a saber, tridiagonais, conforme ilustrado a seguir:

\[\begin{gathered} \label{CapLinearThomas01} \left[ {\begin{array}{*{20}c} {b_1 } & {c_1 } & 0 & \cdots & 0 & 0 & 0 \\ {a_2 } & {b_2 } & {c_2 } & \cdots & 0 & 0 & 0 \\ 0 & {a_3 } & {b_3 } & \cdots & 0 & 0 & 0 \\ \vdots & \vdots & \vdots & \ddots & \vdots & \vdots & \vdots \\ 0 & 0 & 0 & {a_{n - 2} } & {b_{n - 2} } & {c_{n - 2} } & 0 \\ 0 & 0 & 0 & 0 & {a_{n - 1} } & {b_{n - 1} } & {c_{n - 1} } \\ 0 & 0 & 0 & 0 & 0 & {a_n } & {b_n } \\ \end{array}} \right]\left[ {\begin{array}{*{20}c} {x_1 } \\ {x_2 } \\ {x_3 } \\ \vdots \\ {x_{n - 2} } \\ {x_{n - 1} } \\ {x_n } \\ \end{array}} \right] = \left[ {\begin{array}{*{20}c} {d_1 } \\ {d_2 } \\ {d_3 } \\ \vdots \\ {d_{n - 2} } \\ {d_{n - 1} } \\ {d_n } \\ \end{array}} \right]\end{gathered}\]

A resolução deste sistema via aplicação, por exemplo, do Método de Eliminação de Gauss torna-ne, computacionalmente, muito onerosa devido à quantidade de operações realizadas com elementos nulos para a obtenção do vetor de incógnitas \(x\). Além disso, para este tipo de sistema, o armazenamento e a realização de operações matemáticas com elementos nulos é desnecessário. Neste contexto, a avaliação da esparsidade tem como objetivo o tratamento de elementos não nulos, de forma a reduzir a memória e o número de operações necessárias para a resolução deste tipo de sistema.

Com o objetivo de reduzir o custo computacional necessário para a resolução deste tipo de sistema, isto é; trabalhar apenas com elementos não nulos, Llewellyn Thomas propôs em 1949 uma estratégia que, a partir do conhecimento desta estrutura, reduz drasticamente o número de operações requeridas.

O sistema definido anteriormente tem os termos \(a_1\) (primeira linha) e \(c_n\) (\(n\)-ésima linha) iguais a zero. Neste cenário, a estratégia proposta por Thomas apresenta a concepção conceitual descrita a seguir.

Resolvendo a primeira linha para \(x_1\) obtem-se:

\[\begin{gathered} \label{CapLinearThomas02} x_1 = \frac{{d_1 }}{{b_1 }} - \frac{{c_1 }}{{b_1 }}x_2\end{gathered}\]

Definindo \(k_1=d_1/b_1\) e \(t_1=c_1/b_1\), a expressão acima reduz-se a \(x_1 = k_1 - t_1 x_2\).

A segunda equação pode ser resolvida para \(x_2\):

\[\begin{gathered} \label{CapLinearThomas03} x_2 = \frac{{d_2 }}{{b_2 }} - \frac{{\left( {a_2 x_1 + c_2 x_3 } \right)}}{{b_2 }}\end{gathered}\]

Substituindo o valor de \(x_1\) encontrado anteriormente pode-se reescrever \(x_2\) como sendo:

\[\begin{gathered} \label{CapLinearThomas04} x_2 = \frac{{d_2 - a_2 k_1 }}{{b_2 - a_2 t_1 }} - \frac{{c_2 }}{{b_2 - a_2 t_1 }}x_3\end{gathered}\]

Definindo-se \(k_2\) como sendo igual a primeira parcela e \(t_2\) como sendo o coeficiente relacionado a variável \(x_3\), tem-se \(x_2 = k_2 - t_2 x_3\).

Assim, pode-se generalizar para a \(i\)-ésima equação:

\[\begin{gathered} \label{CapLinearThomas05} x_i = k_i - t_i x_{i + 1}\end{gathered}\] onde \[\begin{gathered} \label{CapLinearThomas06} k_i = \frac{{d_i - a_i k_{i - 1} }}{{b_i - a_i t_{i - 1} }} \\ \label{CapLinearThomas07} t_i = \frac{{c_i }}{{b_i - a_i t_{i - 1} }}\end{gathered}\]

Neste sentido pode-se obter a solução do sistema tridiagonal a partir do conhecimento da variável \(x_n\), que é igual a \(k_n\). Recursivamente, pode-se obter as outras variáveis.