Eliminação gaussiana e retro-substituição

Em diversos problemas da fisica, como na interpolação por Spline cúbicos, resolução de equações diferenciais, etc, envolvem equações do tipo

$b_i^{-}{\varphi }_{i-1}+b_i^0{\varphi }_i+b_i^{+}{\varphi }_{i+1}=f_i.(1)$

ou na forma matricial

$\mathbf{𝐛}\mathit{\varphi }=\mathbf{𝐟}.$

A matriz $\mathbf{𝐛}$ e o vetor $\mathbf{𝐟}$ são dados do problema e $\mathit{\varphi }$ representa a solução procurada. A primeira vista, trata-se de um problema simples, bastanto calcular ${\mathbf{𝐛}}^{-1}$ para se obter:

$\mathit{\varphi }={\mathbf{𝐛}}^{\mathbf{-}\mathbf{𝟏}}\mathbf{𝐟}.$

Contudo, alguns aspectos devem ser levados em consideração. Em primeiro lugar, do ponto de vista numérico, a inversão de matrizes é um problema sutil e muito oneroso do ponto de vista computacional (veja Numerical Recipes, por exemplo). Por isto, é fortemente recomendável que se procure algoritmos numéricos bem estabelecidos para a realização da tarefa. Tendo em vista que tais algoritmos estão implementados e testados há várias décadas, isto leva a crer que não há dificuldades na resolução do problema. Entretanto, o custo em tempo é algo não desprezível e pode comprometer seriamente um estudo no qual esta equação tenha que ser resolvida muitas vezes. Por exemplo, se os coeficientes $b_i^{-}$, $b_i^0$ e $b_i^{+}$, e/ou $f_i$ variam com o tempo, a matriz $\mathbf{𝐛}$ deve ser invertida a cada passo da evolução.

Entretanto, nos casos em que o sistema de equações envolve apenas os termos em ${\varphi }_{i-1}$, ${\varphi }_i$ e ${\varphi }_{i+1}$, a matriz $\mathbf{𝐛}$ é tri-diagonal, isto é, apenas os elementos de suas 3 diagonais principais são não-nulos. Neste caso, a soulção do problema é bastante segura, simples e eficiente do ponto de vista numérico.

De fato, o sistema de equações acima sugere que a solução pode ser escrita da seguinte forma:

${\varphi }_{i+1}={\alpha }_i{\varphi }_i+{\beta }_i(2)$

onde ${\alpha }_i$ e ${\beta }_i$ devem ser determinados a partir do sistema de equações. Substituindo a expressão acima na Eq. (1), temos:

$b_i^{-}{\varphi }_{i-1}+(b_{i+1}^{+}{\alpha }_i+b_i^0){\varphi }_i=f_i-b_i^{+}{\beta }_i$

o que leva a

${\varphi }_i={\gamma }_i{b}_i^{-}{\varphi }_{i-1}+{\gamma }_i(b_i^{+}{\beta }_i-f_i),(3)$

onde

${\gamma }_i\equiv -\frac{1}{b_i^{+}{\alpha }_i+b_i^0}.(4)$

Reescrevendo a Eq. (2) como

${\varphi }_i={\alpha }_{i-1}{\varphi }_{i-1}+{\beta }_{i-1}$

podemos comparar esta expressão com a Eq. (3), o que nos leva, finalmente, a

${\alpha }_{i-1}={\gamma }_i{b}_i^{-}(5)$

e

${\beta }_{i-1}={\gamma }_i(b_i^{+}{\beta }_i-f_i).(6)$

As equações (2) e (4-6) mostram que a solução do problema é bastante simples. Dado o valor de ${\varphi }_N=q$, temos ${\alpha }_{N-1}=0$ e ${\beta }_{N-1}=q$. Uma vez obtidas estas quantidades, calculamos ${\alpha }_i$ e ${\beta }_i$, por meio das equações (4-6), de $i=N-1$ até $i=2$. Após isto, ${\varphi }_{i+1}$ pode ser obtido por meio da equação (2), partindo de $i=1$ até $i=N-2$.

É importante notar que a solução do problema só é possível se forem fornecidos os valores de ${\varphi }_1$ e ${\varphi }_N$. A especificação destes valores está associada às condições de contorno, que são determinadas pela física do problema. Na realidade, também é comum se encontrar problemas onde os valores das derivadas são fixados em uma ou ambas das bordas. Se $\varphi {\text{'}}_1={\sigma }_1$ ou $\varphi {\text{'}}_N={\sigma }_2$ forem impostos, temos:

$\varphi {\text{'}}_1=\frac{{\varphi }_2-{\varphi }_1}{X_2-X_1}={\sigma }_1$

e

$\varphi {\text{'}}_N=\frac{{\varphi }_N-{\varphi }_{N-1}}{X_N-X_{N-1}}={\sigma }_2$

o que leva a

${\varphi }_2={\varphi }_1+{\sigma }_1(X_2-X_1)$

e

${\varphi }_N={\varphi }_{N-1}+{\sigma }_2(X_N-X_{N-1}).$

Usando a equação (2), encontramos:

${\alpha }_{N-1}=1\text{ e }{\beta }_{N-1}={\sigma }_2(X_N-X_{N-1})$

e

${\varphi }_1=\frac{{\beta }_1-{\sigma }_1(X_2-X_1)}{1-{\alpha }_1}.$

A partir destes resultados, as relações de recorrência podem ser aplicadas.

---

Voltar para o índice de Métodos computacionais.