Use o botão abaixo para reportar erros ou dar sugestões.

Cálculo Numérico - Versão Python

4.5 Método da matriz tridiagonal


O método da matriz tridiagonal ou algoritmo de Thomas6 ou ainda TDMA (do inglês tridiagonal matrix algorithm) é o caso particular da eliminação gaussiana aplicada a matrizes tridiagonais.

Uma matriz tridiagonal é uma matriz quadrada cujos únicos elementos não nulos estão na diagonal principal e nas diagonais imediatamente acima e abaixo da principal. Um sistema tridiagonal é um sistema de equações lineares cuja matriz associada é tridiagonal, conforme a seguir: b1 c1 a2 b2 c2 a3 b3 c n-1 an bn x1 x2 x3 x n = d1 d2 d3 d n . (4.88)

Observamos que não é necessário armazenar todos os n2 elementos da matriz em memória, sendo suficiente armazenar os vetores an, bn e cn. Por conveniência, a partir daqui, definiremos os elementos inexistentes na matriz a1 e cn como zero:

a1 = cn = 0. (4.89)

Para resolver o sistema tridiagonal (4.88) pelo algoritmo de Thomas são utilizadas as seguintes expressões: ci = ci bi, i = 1 ci bi-aici-1,i = 2, 3,,n - 1 (4.90) e di = di bi , i = 1 di-aidi-1 bi-aici-1,i = 2, 3,,n. (4.91)

Finalmente, a solução final é obtida por substituição reversa: xn = dn (4.92) xi = di - c ix i+1,i = n - 1,n - 2,, 1. (4.93)

Teorema 4.5.1. A aplicação da eliminação gaussiana sem pivotamento ao sistema (4.88) produz o algoritmo dado em (4.90) e (4.92).

Demonstração. O primeiro passo consiste em dividir todos os elementos da primeira linha de (4.88) por b1: 1 c1 a2 b2 c2 a3 b3 c n-1 an bn x1 x2 x3 x n = d1 d2 d3 d n , (4.94)

onde c1 = c1 b1 e d1 = d1 b1 .

O segundo passo consiste em substituir a segunda linha por ela mesma subtraída da linha 1 multiplicada por a2 (l2 l2 - a2l1): 1 c1 0 b2 - a2c1 c 2 a3 b3 c n-1 an bn x1 x2 x3 x n = d1 d2 - a2d1 d3 d n . (4.95)

Em seguida, dividimos a segunda linha por b2 - a2c1, a fim de normalizar a diagonal principal: 1 c1 0 1 c2 a3 b3 c n-1 an bn x1 x2 x3 x n = d1 d2 d3 d n . (4.96)

onde c2 = c2 b2-a2c1 e d2 = d2-a2d1 b2-a2c1.

O próximo passo consiste em substituir a terceira linha por ela mesma subtraída da linha 2 multiplicada por a3 (l3 l3 - a3l2): 1 c1 0 1 c2 0 b3 - a3c2 cn-1 an bn x1 x2 x3 x n = d1 d2 d3 - a3d2 d n . (4.97)

A fim de normalizar o elemento da diagonal da terceira linha, dividimos toda a linha por d3 - a3d2: 1 c1 0 1 c2 0 1 c n-1 an bn x1 x2 x3 x n = d1 d2 d3 d n . (4.98)

Este procedimento é realizado até que se atinja a última linha e temos o seguinte sistema: 1 c1 0 1 c2 0 1 cn-1 0 1 x1 x2 x3 x n = d1 d2 d3 dn . (4.99)

Neste estágio, podemos encontrar os xn através de substituição reversa, isto é: a última linha diz

xn = dn. (4.100)

A penúltima linha diz

xn-1 + cn-1x n = dn-1x n-1 = dn-1 - c n-1x n. (4.101)

Esse mesmo procedimento aplicado à linha i = 1,n - 1, nos dá

xi = di - c ix i+1. (4.102)

Exemplo 4.5.1. Considere a resolução do seguinte sistema tridiagonal pelo algoritmo de Thomas: 2 1 0 0 0 1 2 1 0 0 0 1 2 1 0 0 0 1 2 1 0 0 0 1 2 x1 x2 x3 x4 x5 = 4 4 0 0 2 . (4.103)

Primeiramente identificamos os vetores a, b, c e d: a = (0, 1, 1, 1, 1) (4.104) b = (2, 2, 2, 2, 2) (4.105) c = (1, 1, 1, 1, 0) (4.106) d = (4, 4, 0, 0, 2) (4.107)

Agora, calculamos os vetores c e d: c1 = c1 b1 = 1 2 (4.108) c2 = c2 b2 - a2c1 = 1 2 - 1 1 2 = 2 3 (4.109) c3 = c3 b3 - a3c2 = 1 2 - 1 2 3 = 3 4 (4.110) c4 = c4 b4 - a4c3 = 1 2 - 1 3 4 = 4 5 (4.111) d1 = d1 b1 = 4 2 = 2 (4.112) d2 = d2 - a2d1 b2 - a2c1 = 4 - 1 2 2 - 1 1 2 = 4 3 (4.113) d3 = d3 - a3d2 b3 - a3c2 = 0 - 1 4 3 2 - 1 2 3 = -1 (4.114) d4 = d4 - a4d3 b4 - a4c3 = 0 - 1 (-1) 2 - 1 3 4 = 4 5 (4.115) d5 = d5 - a5d4 b5 - a5c4 = 2 - 1 4 5 2 - 1 4 5 = 1 (4.116)

Finalmente, calculamos o vetor x: x5 = d5 = 1 (4.117) x4 = d4 - c 4 x 5 = 4 5 - 4 5 1 = 0 (4.118) x3 = d3 - c 3 x 4 = -1 - 3 4 0 = -1 (4.119) x2 = d2 - c 2 x 3 = 4 3 - 2 3 (-1) = 2 (4.120) x1 = d1 - c 1 x 2 = 2 - 1 2 2 = 1 (4.121)

E assim, obtemos o vetor x = [1, 2,-1, 0, 1].

Código Python: Método da matriz tridiagonal

import numpy as np  
 
def TDMA(a,b,c,d):  
    #preliminares  
    a = a.astype(double)  
    b = b.astype(double)  
    c = c.astype(double)  
    d = d.astype(double)  
 
    #recupera ordem do sistema  
    n=np.shape(a)[0]  
 
    #inicializa vetores auxiliares  
    cl=np.zeros(n)  
    dl=np.zeros(n)  
    x=np.zeros(n)  
 
    #calcula cl e dl  
    cl[0]=c[0]/b[0]  
    for i in np.arange(1,n-1,1):  
       cl[i]=c[i]/(b[i]-a[i]*cl[i-1])  
 
    dl[0]=d[0]/b[0]  
    for i in np.arange(1,n,1):  
       dl[i]=(d[i]-a[i]*dl[i-1])/(b[i]-a[i]*cl[i-1])  
 
    #faz substituicao reversa para obter a solucao x  
    x[n-1]=dl[n-1]  
    for i in np.arange(n-2,-1,-1):  
       x[i]=dl[i]-cl[i]*x[i+1]  
 
    return x  
 
 

Nesse código, usou-se cl e dl para denotar c e d. Observe que se for desnecessário preservar os valores originais dos vetores c e d, eles podem, com economia de memória e simplicidade de código, ser sobrescritos pelos vetores c e d, respectivamente. Eis uma nova implementação:

import numpy as np  
 
def TDMA(a,b,c,d):  
    #preliminares  
    a = a.astype(double)  
    b = b.astype(double)  
    c = c.astype(double)  
    d = d.astype(double)  
 
    #recupera ordem do sistema  
    n=np.shape(a)[0]  
 
    #inicializa vetor x  
    x=np.zeros(n)  
 
    #calcula cl e dl sobrescrevendo-os em c e d  
    c[0]=c[0]/b[0]  
    for i in np.arange(1,n-1,1):  
       c[i]=c[i]/(b[i]-a[i]*c[i-1])  
 
    d[0]=d[0]/b[0]  
    for i in np.arange(1,n,1):  
       d[i]=(d[i]-a[i]*d[i-1])/(b[i]-a[i]*c[i-1])  
 
    #faz substituicao reversa para obter a solucao x  
    x[n-1]=d[n-1]  
    for i in np.arange(n-2,-1,-1):  
       x[i]=d[i]-c[i]*x[i+1]  
 
    return x  
 

A solução do sistema do Exemplo 4.5.1 pode ser obtida através dos seguintes comandos:

>>>a=np.array([1,1,1,1,1])  
>>>b=np.array([2,2,2,2,2])  
>>>c=np.array([1,1,1,1,1])  
>>>d=np.array([4,4,0,0,2])  
>>>TDMA(a,b,c,d)

E 4.5.1. Considere o problema linear tridiagonal dado por 5 4 0 0 0 0 1 3 1 0 0 0 0 2 4 1 0 0 0 0 1 2 1 0 0 0 0 2 3 2 0 0 0 0 1 2 x1 x2 x3 x4 x5 x6 = 13 10 20 16 35 17 . (4.122)

Identifique os vetores a, b, c e d relativos ao algoritmo da matriz tridiagonal. Depois resolva o sistema usando o computador.

Resposta. a = (0, 1, 2, 1, 2, 1) (4.123) b = (5, 3, 4, 2, 3, 2) (4.124) c = (4, 1, 1, 1, 2, 0) (4.125) d = (13, 10, 20, 16, 35, 17) (4.126) x = (1, 2, 3, 4, 5, 6) (4.127)

E 4.5.2. Considere o seguinte sistema de equações lineares: x1 - x2 = 0 -xj-1 + 5xj - xj+1 = cos(j10),2 j 10 x11 = x102 (4.128)

Identifique os vetores a, b, c e d relativos ao algoritmo da matriz tridiagonal no sistema linear dado. Depois resolva o sistema usando o computador. Veja também Exercício 4.7.4

Resposta. a = (0,-1,-1,-1,-1,-1,-1,-1,-1,-1,-12) (4.129) b = (1, 5, 5, 5, 5, 5, 5, 5, 5, 5, 1) (4.130) c = (-1,-1,-1,-1,-1,-1,-1,-1,-1,-1, 0) (4.131) d = (0, cos(210), cos(310), cos(410), cos(510), (4.132) cos(610), cos(710), cos(810), cos(910), cos(1),0) (4.133) x = (0,324295, 0,324295, 0,317115, 0,305943, 0,291539, (4.134) 0,274169, 0,253971, 0,230846, 0,20355, 0,165301, 0,082650) (4.135)

Creative Commons License Este texto é disponibilizado nos termos da licença Creative Commons Atribuição-CompartilhaIgual 3.0 Não Adaptada (CC-BY-SA 3.0). Página gerada em 15/5/2019 às 15:24:50.

Informe erros ou edite você mesmo!