Colabore! Saiba mais screen_rotation

Ao navegar por este site , você concorda com a Política de Uso de Dados.

| | | | |

1 Sistemas Lineares 1 Sistemas Lineares 1.2 Métodos Iterativos

1.1 Matrizes Esparsas

Ajude a manter o site livre, gratuito e sem propagandas. Colabore!

Em revisão

Uma matriz é dita ser esparsa quando ela tem apenas poucos elementos não nulos. A ideia é que os elementos não nulos não precisam ser guardados na memória do computador, gerando um grande benefício na redução da demanda de armazenamento de dados. O desafio está no desenvolvimento de estruturas de dados para a alocação eficiente de tais matrizes, i.e. que sejam suficientemente adequadas para os métodos numéricos conhecidos.

Refer to caption — Figura 1.1: Em cima: exemplo de uma matriz esparsa estruturada. Em baixo: exemplo de uma matriz esparsa não-estruturada.

Matrizes esparsas podem ser classificadas como estruturadas ou não-estruturadas. Uma matriz estruturada é aquela em que as entradas não-nulas formam um padrão regular. Por exemplo, estão dispostas em poucas diagonais ou formam blocos (submatrizes densas) ao longo de sua diagonal principal. No caso de não haver um padrão regular das entradas não-nulas, a matriz esparsa é dita ser não-estruturada. Consulte a Figura 1.1 para exemplos.

A esparsidade de uma matriz é a porcentagem de elementos nulos que ela tem, i.e. para uma matriz quadrada $n\times n$ tem-se que a esparsidade é

\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}% \pgfsys@color@rgb@stroke{0}{0}{1}\pgfsys@color@rgb@fill{0}{0}{1}e:=\frac{n_{% \text{nulos}}}{n^{2}}\times 100\%.

(1.1)

Por exemplo, a matriz identidade de tamanho $n=100$ tem esparsidade

e=\frac{100^{2}-100}{100^{2}}\times 100\%=99\%.

(1.2)

1.1.1 Sistemas Tridiagonais

Em revisão

Um sistema tridiagonal tem a seguinte forma matricial

\begin{bmatrix}a_{1,1}&{\color[rgb]{.5,0,.5}\definecolor[named]{pgfstrokecolor% }{rgb}{.5,0,.5}\pgfsys@color@rgb@stroke{.5}{0}{.5}\pgfsys@color@rgb@fill{.5}{0% }{.5}a_{1,2}}&&&&0\\ {\color[rgb]{0,.5,.5}\definecolor[named]{pgfstrokecolor}{rgb}{0,.5,.5}% \pgfsys@color@rgb@stroke{0}{.5}{.5}\pgfsys@color@rgb@fill{0}{.5}{.5}a_{2,1}}&a% _{2,2}&{\color[rgb]{.5,0,.5}\definecolor[named]{pgfstrokecolor}{rgb}{.5,0,.5}% \pgfsys@color@rgb@stroke{.5}{0}{.5}\pgfsys@color@rgb@fill{.5}{0}{.5}a_{2,3}}&&% &\\ &{\color[rgb]{0,.5,.5}\definecolor[named]{pgfstrokecolor}{rgb}{0,.5,.5}% \pgfsys@color@rgb@stroke{0}{.5}{.5}\pgfsys@color@rgb@fill{0}{.5}{.5}a_{3,2}}&a% _{3,3}&{\color[rgb]{.5,0,.5}\definecolor[named]{pgfstrokecolor}{rgb}{.5,0,.5}% \pgfsys@color@rgb@stroke{.5}{0}{.5}\pgfsys@color@rgb@fill{.5}{0}{.5}a_{3,4}}&&% \\ &&\ddots&\ddots&\ddots&\\ &&&\ddots&\ddots&{\color[rgb]{.5,0,.5}\definecolor[named]{pgfstrokecolor}{rgb}% {.5,0,.5}\pgfsys@color@rgb@stroke{.5}{0}{.5}\pgfsys@color@rgb@fill{.5}{0}{.5}a% _{n-1,n}}\\ 0&&&&{\color[rgb]{0,.5,.5}\definecolor[named]{pgfstrokecolor}{rgb}{0,.5,.5}% \pgfsys@color@rgb@stroke{0}{.5}{.5}\pgfsys@color@rgb@fill{0}{.5}{.5}a_{n,n-1}}% &a_{n,n}\end{bmatrix}\begin{bmatrix}x_{1}\\ x_{2}\\ x_{3}\\ \vdots\\ x_{n-1}\\ x_{n}\end{bmatrix}=\begin{bmatrix}b_{1}\\ b_{2}\\ b_{3}\\ \vdots\\ b_{n-1}\\ b_{n}\end{bmatrix}.

(1.3)

Ou seja, é um sistema cuja a matriz dos coeficientes é tridiagonal.

Uma matriz tridiagonal é uma matriz esparsa estruturada. Mais especificamente, é um caso particular de uma matriz banda, em que os elementos não nulos estão dispostos apenas em algumas de suas diagonais. Para armazenarmos tal matriz precisamos alocar apenas os seguintes três vetores

	$\displaystyle{\color[rgb]{.5,0,.5}\definecolor[named]{pgfstrokecolor}{rgb}{% .5,0,.5}\pgfsys@color@rgb@stroke{.5}{0}{.5}\pgfsys@color@rgb@fill{.5}{0}{.5}d_% {1}=\left(0,a_{1,2},\dotsc,a_{n-1,n}\right)},$		(1.4)
	$\displaystyle d_{0}=\left(a_{1,1},a_{2,2},\dotsc,a_{n,n}\right),$		(1.5)
	$\displaystyle{\color[rgb]{0,.5,.5}\definecolor[named]{pgfstrokecolor}{rgb}{% 0,.5,.5}\pgfsys@color@rgb@stroke{0}{.5}{.5}\pgfsys@color@rgb@fill{0}{.5}{.5}d_% {-1}=\left(a_{2,1},\dotsc,a_{n,n-1},0\right)}.$		(1.6)

Ou seja, precisamos armazenar $3n$ pontos flutuantes em vez de $n^{2}$ , como seria o caso se a matriz dos coeficientes fosse densa. Com isso, podemos alocar a matriz do sistema da seguinte forma

\tilde{A}=\begin{bmatrix}{\color[rgb]{.5,0,.5}\definecolor[named]{% pgfstrokecolor}{rgb}{.5,0,.5}\pgfsys@color@rgb@stroke{.5}{0}{.5}% \pgfsys@color@rgb@fill{.5}{0}{.5}*}&{\color[rgb]{.5,0,.5}\definecolor[named]{% pgfstrokecolor}{rgb}{.5,0,.5}\pgfsys@color@rgb@stroke{.5}{0}{.5}% \pgfsys@color@rgb@fill{.5}{0}{.5}a_{1,2}}&{\color[rgb]{.5,0,.5}\definecolor[% named]{pgfstrokecolor}{rgb}{.5,0,.5}\pgfsys@color@rgb@stroke{.5}{0}{.5}% \pgfsys@color@rgb@fill{.5}{0}{.5}\cdots}&{\color[rgb]{.5,0,.5}\definecolor[% named]{pgfstrokecolor}{rgb}{.5,0,.5}\pgfsys@color@rgb@stroke{.5}{0}{.5}% \pgfsys@color@rgb@fill{.5}{0}{.5}a_{n-1,n}}\\ a_{1,1}&a_{2,2}&\cdots&a_{n,n}\\ {\color[rgb]{0,.5,.5}\definecolor[named]{pgfstrokecolor}{rgb}{0,.5,.5}% \pgfsys@color@rgb@stroke{0}{.5}{.5}\pgfsys@color@rgb@fill{0}{.5}{.5}a_{2,1}}&{% \color[rgb]{0,.5,.5}\definecolor[named]{pgfstrokecolor}{rgb}{0,.5,.5}% \pgfsys@color@rgb@stroke{0}{.5}{.5}\pgfsys@color@rgb@fill{0}{.5}{.5}\dotsc}&{% \color[rgb]{0,.5,.5}\definecolor[named]{pgfstrokecolor}{rgb}{0,.5,.5}% \pgfsys@color@rgb@stroke{0}{.5}{.5}\pgfsys@color@rgb@fill{0}{.5}{.5}a_{n,n-1}}% &{\color[rgb]{0,.5,.5}\definecolor[named]{pgfstrokecolor}{rgb}{0,.5,.5}% \pgfsys@color@rgb@stroke{0}{.5}{.5}\pgfsys@color@rgb@fill{0}{.5}{.5}*}\end{% bmatrix}.

(1.7)

Ou seja, $\tilde{A}=[\tilde{a}_{i,j}]_{i,j=1}^{3,n}$ , sendo

\tilde{a}_{1+i-j,j}=a_{i,j}.

(1.8)

Exemplo 1.1.1.

Seja o seguinte sistema linear

	$\displaystyle 2x_{1}-x_{2}=0$		(1.9)
	$\displaystyle x_{i-1}-6x_{i}+4x_{i+1}=\operatorname{sen}\left(i\frac{\pi}{2(n-% 1)}\right)$		(1.10)
	$\displaystyle x_{n-1}+x_{n}=1$		(1.11)

O seguinte código Python faz a alocação de seu vetor dos termos constantes $b$ e de sua matriz de coeficientes no formato compacto de $\tilde{A}$ .

Código 1: diagSis.py

⬇

1import numpy as np

2n = 100000

4# alocação

5# vetor dos termos constantes

6b = np.empty(n)

7b[0] = 0.

8for i in range(1,n-1):

9 b[i] = np.sin(i*np.pi/(2*(n-1)))

10b[n-1] = 1.

11print(b)

12print(f"b size: {b.size*b.itemsize/1024} Kbytes")

14# matriz compacta

15tA = np.zeros((3,n))

17# indexação

18def ind(i,j):

19return 1+i-j,j

21tA[ind(0,0)] = 2.

22tA[ind(0,1)] = -1.

23for i in range(1,n-1):

24 tA[ind(i,i-1)] = 1.

25 tA[ind(i,i)] = -3.

26 tA[ind(i,i+1)] = 4.

27tA[ind(n-1,n-2)] = 1.

28tA[ind(n-1,n-1)] = 1.

29print(tA)

30print(f"tA size: {tA.size*tA.itemsize/1024**2:1.1f} Mbytes")

Algoritmo de Thomas (TDMA)

Em revisão

O algoritmo de Thomas¹¹endnote: ¹Llewellyn Hilleth Thomas, 1903 - 1992, físico e matemático aplicado britânico. Fonte: Wikipedia. ou TDMA (do inglês, Tridiagonal Matrix Algorithm) é uma forma otimizada do método de eliminação gaussiana²²endnote: ²Johann Carl Friedrich Gauss, 1777 - 1855, matemático alemão. Fonte: Wikipédia: Carl Friedrich Gauss. aplicada a sistemas tridiagonais. Enquanto este requer $O(n^{3})$ operações, esse demanda apenas $O(n)$ .

Eliminando os termos abaixo da diagonal em (1.3), obtemos o sistema equivalente

\begin{bmatrix}a_{1,1}&a_{1,2}&&&0&|&b_{1}\\ &\tilde{a}_{2,2}&a_{2,3}&&&|&\tilde{b}_{2}\\ &&\tilde{a}_{3,3}&\ddots&&|&\vdots\\ &&&\ddots&a_{n-1,n}&|&\tilde{b}_{n-1}\\ 0&&&&\tilde{a}_{n,n}&|&\tilde{b}_{n}\end{bmatrix}

(1.12)

Este é obtido pela seguinte iteração

	$\displaystyle w\leftarrow\frac{a_{i+1,i}}{a_{i,i}}$		(1.13)
	$\displaystyle a_{i,i}\leftarrow a_{i,i}-w\cdot a_{i-1,i}$		(1.14)
	$\displaystyle b_{i}\leftarrow b_{i}-w\cdot b_{i-1}$		(1.15)

onde, o ~ foi esquecido de propósito, indicando a reutilização da matriz $\tilde{A}$ e do vetor $b$ . A solução do sistema é, então, obtida de baixo para cima, i.e.

	$\displaystyle x_{n}\leftarrow\frac{b_{n}}{a_{n,n}}$		(1.16)
	$\displaystyle x_{i}\leftarrow\frac{b_{i}-a_{i,i+1}x_{i+1}}{a_{i,i}},$		(1.17)

com $i=n-1,n-2,\dotsc,1$ .

Código 2: tdma.py

⬇

1def tdma(ta, b):

2 a = ta.copy()

3 x = b.copy()

4 # eliminação

5 for i in range(1,n):

6 w = a[2,i-1]/a[1,i-1]

7 a[1,i] -= w * a[0,i]

8 x[i] -= w * x[i-1]

9 # resolve

10 x[n-1] = x[n-1]/a[1,n-1]

11 for i in range(n-2,-1,-1):

12 x[i] = (x[i] - a[0,i+1]*x[i+1])/a[1,i]

13 return x

1.1.2 Matrizes Banda

Em revisão

Uma matriz banda é aquela em que os elementos não nulos estão dispostos em apenas algumas de suas diagonais. Consulte a Figura 1.2.

Exemplo 1.1.2.

Consideramos o seguinte problema de Poisson³³endnote: ³Siméon Denis Poisson, 1781 - 1840, matemático francês. Fonte: Wikipédia:Siméon Denis Poisson.

	$\displaystyle-\Delta u=f(x,y),\leavevmode\nobreak\ (x,y)\in(0,\pi)\times(0,\pi),$		(1.18)
	$\displaystyle u(0,y)=0,\leavevmode\nobreak\ y\in[0,\pi],$		(1.19)
	$\displaystyle u(\pi,y)=0,\leavevmode\nobreak\ y\in[0,\pi],$		(1.20)
	$\displaystyle u(x,0)=0,\leavevmode\nobreak\ x\in[0,\pi],$		(1.21)
	$\displaystyle u(x,\pi)=0,\leavevmode\nobreak\ x\in[0,\pi],$		(1.22)

onde, $\Delta:=\left(\frac{\partial^{2}}{\partial x^{2}},\frac{\partial^{2}}{\partial y% ^{2}}\right)$ é o operador laplaciano⁴⁴endnote: ⁴Pierre-Simon Laplace, 1749 - 1827, matemático francês. Fonte: Wikipédia: Pierre-Simon Laplace.. Para fixarmos as ideias, vamos assumir

f(x,y)=\operatorname{sen}(x)\operatorname{sen}(y)

(1.23)

Vamos empregar o método de diferenças finitas para computar uma aproximação para a sua solução. Começamos assumindo uma malha uniforme de $n^{2}$ nodos

	$\displaystyle x_{i}=(i-1)h$		(1.24)
	$\displaystyle y_{j}=(j-1)h$		(1.25)

com tamanho de malha $h=\pi/(n-1)$ , $i=1,2,\dotsc,n$ e $j=1,2,\dotsc,n$ . Empregando a fórmula de diferenças central, encontramos o seguinte problema discreto associado

	$\displaystyle u_{i,1}=u_{1,j}=0$		(1.26)
	$\displaystyle-\frac{1}{h^{2}}u_{i-1,j}-\frac{1}{h^{2}}u_{i,j-1}+\frac{4}{h^{2}% }u_{i,j}$
	$\displaystyle\qquad-\frac{1}{h^{2}}u_{i+1,j}-\frac{1}{h^{2}}u_{i,j+1}=f(x_{i},% y_{j})$		(1.27)
	$\displaystyle u_{i,n}=u_{n,j}=0$		(1.28)

Este é um sistema linear $n^{2}\times n^{2}$ . Tomando em conta as condições de contorno, ele pode ser reduzido a um sistema $(n-2)^{2}\times(n-2)^{2}$

Aw=b

(1.29)

usando a enumeração das incógnitas

(i,j)\rightarrow k=i-1+(j-2)(n-2),

(1.30)

i.e.

u_{i,j}=w_{k=i-1+(j-2)(n-2)}

(1.31)

para $i,j=2,\dotsc,n-2$ . Consulte a Figura 1.3 para uma representação da enumeração em relação a malha.

Afim de obtermos uma matriz diagonal dominante, vamos ordenar as equações do sistema discreto como segue

•

$j=2$ , $i=2$ :

$4w_{k}-w_{k+1}-w_{k+n-2}=h^{2}f_{i,j}$ (1.32)
•

$j=2$ , $i=3,\dotsc,n-2$ :

$-w_{k-1}+4w_{k}-w_{k+1}-w_{k+n-2}=h^{2}f_{i,j}$ (1.33)
•

$j=2$ , $i=n-1$ :

$-w_{k-1}+4w_{k}-w_{k+n-2}=h^{2}f_{i,j}$ (1.34)
•

$j=3,\dotsc,n-2$ , $i=2$ :

$-w_{k-(n-2)}+4w_{k}-w_{k+1}-w_{k+n-2}=h^{2}f_{i,j}$ (1.35)
•

$j=3,\dotsc,n-2$ , $i=3,\dotsc,n-2$ :

$-w_{k-1}-w_{k-(n-2)}+4w_{k}-w_{k+1}-w_{k+n-2}=h^{2}f_{i,j}$ (1.36)
•

$j=3,\dotsc,n-2$ , $i=n-1$ :

$-w_{k-1}-w_{k-(n-2)}+4w_{k}-w_{k+n-2}=h^{2}f_{i,j}$ (1.37)
•

$j=n-1$ , $i=2$ :

$-w_{k-(n-2)}+4w_{k}-w_{k+1}=h^{2}f_{i,j}$ (1.38)
•

$j=n-1$ , $i=3,\dotsc,n-2$ :

$-w_{k-1}-w_{k-(n-2)}+4w_{k}-w_{k+1}=h^{2}f_{i,j}$ (1.39)
•

$j=n-1$ , $i=n-1$ :

$-w_{k-1}-w_{k-(n-2)}+4w_{k}=h^{2}f_{i,j}$ (1.40)

Com isso, temos um sistema com matriz com 5 bandas, consulte a Figura 1.4.

1.1.3 Esquemas de Armazenamento

Em revisão

A ideia é armazenar apenas os elementos não-nulos de uma matriz esparsa, de forma a economizar a demanda de armazenamento computacional. Cuidados devem ser tomados para que a estrutura de armazenamento utilizada seja adequada para a computação das operações matriciais mais comuns.

Formato COO

Em revisão

O formato COO (do inglês, COOrdinate format) é o esquema de armazenamento simples de matrizes esparsas. As estrutura de dados consiste em três arranjos:

1.

um arranjo contendo as entradas não-nulas da matriz;
2.

um arranjo contendo seus índices de linha;
3.

um arranjo contendo seus índices de coluna.

O método scipy.sparse.coo_array permite a alocação de matrizes no formato COO.

Exemplo 1.1.3.

O seguinte código armazena a matriz

A=\begin{bmatrix}2.&0.&1.&0.\\ 0.&3.&2.&-1.\\ 0&-1&-2.&0.\\ 0&0&0&1.\end{bmatrix}

(1.41)

no formato COO.

⬇

1import numpy as np

2from scipy.sparse import coo_array

4data = np.array([2.,1.,3.,2.,-1.,-1.,-2.,1.])

5row = np.array([0,0,1,1,1,2,2,3])

6col = np.array([0,2,1,2,3,1,2,3])

7Acoo = coo_array((data, (row, col)), shape=(4,4))

8print("Acoo = \n", Acoo)

9print("A = \n", Acoo.toarray())

Vantagens do formato COO

•

Permite a entrada de dados duplicados (simplicidade).
•

Conversão rápida para os formatos CSR e CSC⁵⁵endnote: ⁵CSR e CSC são formatos de matrizes esparsas mais eficientes para a computação matricial..

Desavantagens do formato COO

•

complexidade em operações aritméticas.
•

complexidade na extração de submatrizes.

Observação 1.1.1.

(Entradas Duplicadas.) O formato COO permite a entrada duplicada de elementos da matriz. Na conversão para outros formatos (por exemplo, CSR ou CSC), as entradas duplicadas são somadas.

Formato CSR

Em revisão

O formato CSR (do inglês, Compressed Sparse Row) é uma variação do COO que busca diminuir a alocação de dados repetidos. Assim como o COO, o formato conta com três arranjos $d$ , $c$ , $p$ :

•

$d$ é o arranjo contendo os elementos não-nulos da matriz, ordenados por linhas (i.e., da esquerda para direita, de cima para baixo);
•

$c$ é o arranjo contendo o índice das colunas das entradas não-nulas da matriz (como no formato COO);
•

$p$ é um arranjo cujos elementos são a posição no arranjo $c$ em que cada linha da matriz começa a ser representada. O número de elementos de $i$ -ésima linha da matriz dado por $p_{j+1}-p_{j}$ .

O método scipy.sparse.csr_array permite a alocação de matrizes no formato CSR.

Exemplo 1.1.4.

No Exemplo 1.1.3, alocamos a matriz

A=\begin{bmatrix}2.&0.&1.&0.\\ 0.&3.&2.&-1.\\ 0&-1&-2.&0.\\ 0&0&0&1.\end{bmatrix}

(1.42)

no formato COO. Aqui, vamos converter a alocação para o formato CSR e, então, verificar seus atributos.

⬇

1from scipy.sparse import csr_array

2Acsr = Acoo.tocsr()

3print(f'd = {Acsr.data}')

4print(f'c = {Acsr.indices}')

5print(f'p = {Acsr.indptr}')

d = [ 2.  1.  3.  2. -1. -1. -2.  1.]
c = [0 2 1 2 3 1 2 3]
p = [0 2 5 7 8]

Por exemplo, o elemento p[i=2] = 5 aponta para o c[k=5] = 1, o que fornece A[i=2,j=1] = d[k] = -1.. Verifique!

Vantagens do formato CSR

•

operações aritméticas eficientes;
•

fatiamento por linhas eficiente;
•

multiplicação matriz vetor eficiente.

Desvantagens do formato CSR

•

fatiamento por colunas não eficiente;
•

custo elevado de realocamento com alteração da esparsidade da matriz.

Formato CSC

Em revisão

O formato CSC (do inglês, Compressed Sparse Column) é uma variação análoga do CSR, mas para armazenamento por colunas. O formato conta com três arranjos $d$ , $l$ , $p$ :

•

$d$ é o arranjo contendo os elementos não-nulos da matriz, ordenados por colunas (i.e., de cima para baixo, da esquerda para direita);
•

$l$ é o arranjo contendo o índice das linhas das entradas não-nulas da matriz;
•

$p$ é um arranjo cujos elementos são a posição no arranjo $l$ em que cada coluna da matriz começa a ser representada. O número de elementos de $j$ -ésima coluna da matriz dado por $p_{j+1}-p_{j}$ .

O método scipy.sparse.csc_array permite a alocação de matrizes no formato CSC.

Exemplo 1.1.5.

No Exemplo 1.1.3, alocamos a matriz

A=\begin{bmatrix}2.&0.&1.&0.\\ 0.&3.&2.&-1.\\ 0&-1&-2.&0.\\ 0&0&0&1.\end{bmatrix}

(1.43)

no formato COO. Aqui, vamos converter a alocação para o formato CSC e, então, verificar seus atributos.

⬇

1 from scipy.sparse import csc_array

2 Acsc = Acoo.tocsc()

3 l = Acsc.indices

4 p = Acsc.indptr

5 print(f'd = {Acsc.date}')

6 print(f'l = {Acsc.indices}')

7 print(f'p = {Acsc.indptr}')

  d = [2.  3. -1.  1.  2. -2. -1.  1.]
  l = [0 1 2 0 1 2 1 3]
  p = [0 1 3 6 8]

Assim sendo, o elemento p[j=2] = 3 aponta para o l[k=3] = 0, o que informa que A[i=0,j=2]=d[k]=1.. Verifique!

Vantagens do formato CSC

•

fatiamento por colunas eficiente;
•

operações aritméticas eficientes;
•

multiplicação matriz vetor eficiente⁶⁶endnote: ⁶CSR é mais eficiente em muitos casos..

Desvantagens do formato CSC

•

fatiamento por linhas não eficiente;
•

custo elevado de realocamento com alteração da esparsidade da matriz.

Observação 1.1.2.

Além dos formatos COO, CSR e CSC, exitem ainda vários outros que podem empregados e que são mais eficientes em determinadas aplicações. Recomendamos a leitura de [9, Seção 3.4] e da documentação do scipy.sparse.

Exercícios

Em revisão

E. 1.1.1.

Considere o problema de Poisson dado no Exemplo 1.1.2.

a)

Armazene a matriz do problema discreto associado usando o formato COO.
b)

Converta a matriz armazenada para o formato CSR⁷⁷endnote: ⁷Use o método coo_matrix.tocsr().. Então, compute a solução do problema discreto com o método spsolve⁸⁸endnote: ⁸scipy.sparse.linalg.spsolve é uma implementação do Método LU otimizado para matrizes esparsas..
c)

Converta a matriz armazenada para o formato CSC⁹⁹endnote: ⁹Use o método coo_matrix.tocsc().. Então, compute a solução do problema discreto com o método spsolve.
d)

Compare a eficiência da computação entre os itens b) e c) para tamanhos de malha $h=10^{-1},10^{-2},10^{-3},10^{-4}$ .

E. 1.1.2.

Considere o seguinte sistema linear

	$\displaystyle 2x_{1}-x_{2}=0$		(1.44)
	$\displaystyle x_{i-1}-6x_{i}+4x_{i+1}=\operatorname{sen}\left(i\frac{\pi}{2(n-% 1)}\right)$		(1.45)
	$\displaystyle x_{n-1}+x_{n}=1$		(1.46)

a)

Compute sua solução usando o Algoritmo de Thomas para $n=3$ .
b)

Compare a solução obtida no item anterior com a gerada pela função scipy.linalg.solve.
c)

Compare a solução com a obtida no item anterior com a gerada pela função scipy.linalg.solve_banded.
d)

Use o módulo Python datetime para comprar a demanda de tempo computacional de cada um dos métodos acima. Compute para $n=10,100,1000,10000$ .

E. 1.1.3.

Considere que o problema de valor de contorno (PVC)

	$\displaystyle-u^{\prime\prime}=\operatorname{sen}\pi x,\quad 0<x<1,$		(1.47)
	$\displaystyle u(0)=0,$		(1.48)
	$\displaystyle u(1)=0$		(1.49)

seja simulado com o Método das Diferenças Finitas¹⁰¹⁰endnote: ¹⁰Consulte mais em Notas de Aula: Matemática Numérica.. Vamos assumir uma discretização espacial uniforme com $n$ nodos e tamanho de malha

h=\frac{1}{n-1}.

(1.50)

Com isso, temos os nodos $x_{i}=(i-1)h$ , $i=1,2,\dotsc,n$ . Nos nodos internos, aplicamos a fórmula de diferenças central

u^{\prime\prime}(x_{i})\approx\frac{u_{i-1}-2u_{i}+u_{i+1}}{h^{2}},

(1.51)

onde, $u_{i}\approx u(x_{i})$ . Com isso, a discretização da EDO fornece

-\frac{1}{h^{2}}u_{i-1}+\frac{2}{h^{2}}u_{i}-\frac{1}{h^{2}}u_{i+1}=% \operatorname{sen}\pi x_{i}

(1.52)

para $i=2,3,\dotsc,n-1$ . Das condições de contorno temos $u_{1}=u_{n}=0$ . Logo, o problema discreto lê-se: encontrar $u=(u_{1},u_{2},\dotsc,u_{n})\in\mathbb{R}^{n}$ tal que

	$\displaystyle u_{1}=0$		(1.53)
	$\displaystyle-\frac{1}{h^{2}}u_{i-1}+\frac{2}{h^{2}}u_{i}-\frac{1}{h^{2}}u_{i+% 1}=\operatorname{sen}\pi x_{i}$		(1.54)
	$\displaystyle u_{n}=0$		(1.55)

a)

Calcule a solução analítica do PVC.
b)

Use a função scipy.linalg.solve_banded para computar a solução do problema discreto associado para diferentes tamanhos de malha $h=10^{-1},10^{-2},10^{-3},10^{-4}$ . Compute o erro da solução discreta em relação à solução analítica.
c)

Compare a demanda de tempo computacional se a função scipy.linalg.solve for empregada na computação da solução discreta.

E. 1.1.4.

Consideremos o problema trabalho no Exemplo 1.1.2.

a)

Use a função scipy.linalg.solve para computar a solução do problema discreto associado para diferentes tamanhos de malha $h=10^{-1},10^{-2},10^{-3},10^{-4}$ . Compute o erro da solução discreta em relação à solução analítica. Compare as aproximações com a solução analítica

$u(x,y)=\frac{1}{2}\operatorname{sen}(x)\operatorname{sen}(y).$ (1.56)
b)

Compare a demanda de tempo e memória computacional se a função scipy.linalg.solve_banded for empregada na computação da solução discreta.
c)

Baseado no Algoritmo de Thomas, implemente o Método de Eliminação Gaussiana otimizado para a matriz banda deste problema. Compare com as abordagens dos itens a) e b).

Envie seu comentário

As informações preenchidas são enviadas por e-mail para o desenvolvedor do site e tratadas de forma privada. Consulte a Política de Uso de Dados para mais informações. Aproveito para agradecer a todas/os que de forma assídua ou esporádica contribuem enviando correções, sugestões e críticas!

| | | |