\[\left\{ \begin{array}{lll} a_{11} x_1 + a_{12} x_2 + \dots a_{1n}x_n & = & b_1\\ a_{21} x_1 + a_{22} x_2 + \dots a_{2n}x_n & = & b_2\\ \dots & & \\ a_{n1} x_1 + a_{n2} x_2 + \dots a_{nn}x_n & = & b_n \end{array}\right., \]
onde \(x_1\), \(x_2\),…, \(x_n\) são as \(n\) incógnitas, \(a_{11}\), \(a_{12}\), etc…, são os \(n^2\) coeficientes das equações, e \(b_1\), …, \(b_n\) são os \(n\) termos constantes.
\[ A = \left[ \begin{array}{llll} a_{11} & a_{12} & \dots & a_{1n}\\ a_{21} & a_{22} & \dots & a_{2n}\\ a_{n1} & a_{n2} & \dots & a_{nn} \end{array} \right] \]
\[ x = \left[ \begin{array}{l} x_1\\ x_2\\ \dots\\ x_n \end{array} \right] \]
\[ b = \left[ \begin{array}{l} b_1\\ b_2\\ \dots\\ b_n \end{array} \right] \]
o sistema pode ser reescrito como:
\[ Ax = b.\]
NOTE: Por simplicidade vamos escrever, daqui para frente, \(x_i\), \(a_{ij}\) e \(b_i\) para indicar qualquer uma dessas quantidades, e usaremos os números apenas quanto nos referirmos a uma componente particular.
Vamos lembrar aqui algumas operações definidas para toda matriz quadrada \(A_{nxn}\), por exemplo:
\[ A = \left[\begin{array}{lll} 2&1&1\\ 3&2&1\\2&1&2\\ \end{array}\right].\]
\[ A^{T} = \left[\begin{array}{lll} 2&3&2\\1&2&1\\1&1&2\\ \end{array}\right] \qquad \rightarrow \qquad a^{T}_{ij} = a_{ji}.\]
\[ c = \mathrm{Tr} A = \Sigma_{i=1}^n a_{ii} = 6.\]
\[ A = \left[\begin{array}{lll} 1&0&0\\ 0&1&0\\ 0&0&1\\ \end{array}\right].\]
Se \(a,b,\dots\in\mathbb R\), temos que:
\[\begin{array}{rcl} \det(a) &=& a,\\ \left| \begin{array}{cc} a&b\\ c&d \end{array}\right|&=&ad-bc,\\ \left| \begin{array}{ccc} a&b&c\\ d&e&f\\ g&h&i\end{array}\right| &=& a\left| \begin{array}{cc} e&f\\ h&i \end{array}\right| - b\left| \begin{array}{cc} d&f\\ g&i \end{array}\right| + c\left| \begin{array}{cc} d&e\\ g&h \end{array}\right| \\ &=& aei+bfg+cdh-ceg-bdi-afh, \end{array}\]e assim sucessivamente. Note que o sinal é alternante (+,-,+,…).
\[ AB = \left(\begin{array}{cc} a&b\\ c&d\end{array}\right) \left(\begin{array}{cc} e&f\\ g&h\end{array}\right) = \left(\begin{array}{cc} ae+bg&af+bh\\ ce+dg&cf+dh\end{array}\right) \]
\[ A^{-1}A = AA^{-1} = I.\]
Nem sempre a matriz \(A\) tem inversa. Para que exista inversa, temos que ter a seguint condição - Aplique o DETERMINANTE na equação acima:
\[ \det\left( A^{-1}A \right) = \det A^{-1} \det A = \det I = 1,\]
ou seja,
\[ |A^{-1}||A| = 1 \rightarrow |A^{-1}| = \frac{1}{|A|},\]
mas pra isso,
\[|A|\ne 0.\]
Prove que $ Ax=B $ é igual a primeira equação da aula.
Prove que:
\[ AI = IA = A.\] Use uma matriz 2x2 para provar.
\[|AB| = |A||B|.\] Use uma matriz 2x2 para provar.
\[\tr (AB) = \tr (BA).\]
\[ Ax=b\quad \rightarrow \quad A^{-1}Ax = A^{-1}b \quad \rightarrow \quad x = A^{-1}b.\]
\[|A| = \det(A)\ne 0.\]
O determinante é definido como:
Para usarmos o python efetivamente, precisamos usar o pacote NumPy. Veja os exemplos:
# Importa Numpy com o nome 'np' (pra ficar curto)
import numpy as np
# Define uma subrotina para fazer vários cálculos e mostrar
def mostra(A):
# Mostra a "dimensionalidade" da matriz (rank) aqui 2
print("Rank de A:", np.linalg.matrix_rank(A));
# Cálcula o Traço (a soma da diagonal) (5)
print("Traço de A:", np.trace(A));
# Cálcula o Determinante (-2)
print("Det de A:", np.linalg.det(A));
# Calcula a Inversa de A
if(np.linalg.det(A)==0):
print('Matriz A é singular.\n');
else:
print("Inversa de A:\n", np.linalg.inv(A));
def main():
# Exemplo 2x2
# Declara a matriz
# A = [1 2]
# [3 4]
# Note que a definição é linha por linha:
A = np.array([[1,2],[3,4]]);
A = np.array([[2,1],[0,3]]);
mostra(A);
# Agora vamos declarar uma matriz que não tem inversa! Seu determinante é zero:
A = np.array([[1, 1],[1, 1]]);
mostra(A);
###############################
# Teste da Inversa:
A = np.array([[1,2],[3,4]]);
# Usando a função np.linalg.inv:
Ainv = np.linalg.inv(A);
# O produto AAinv ou AinvA devem ser a matrix identidade
print('Produto A*Ainv:\n', np.matmul(A,Ainv), '\n')
print('Produto Ainv*A:\n', np.matmul(Ainv,A), '\n')
# A multiplicação matricial pode ser feita de 3 formas:
# matmul(A,B)
# A@B
# A.dot(B)
A = np.array([[1,2],[3,4]]);
B = np.array([[1,1],[0,2]]);
A@B
np.linalg.det(A)
np.linalg.det(B)
np.linalg.det(A@B)
#Considere o sistema abaixo, chamado de Triangular Superior:
\[ \begin{array}{rcl} 2x_1 - x_2 + x_3 & = & 2\\ x_2 + 2x_3 & = & 3\\ x_3 & = & 1 \end{array}. \]
Esse sistema é facilmente resolvido, substituindo de baixo para cima:
\[ x_3 = 1\\ x_2 = 3-2x_3 = 3-2 = 1\\ 2x_1 - 1 + 1 =2 \rightarrow x_1=1. \]
No caso geral:
\[\left\{ \begin{array}{rrrrrcl} a_{11} x_1&+ a_{12} x_2 &+\dots &+a_{1(n-1)}x_{n-1}&+ a_{1n}x_n & = & b_1\\ & a_{22} x_2 &+\dots &+a_{2(n-1)}x_{n-1}&+ a_{2n}x_n & = & b_2\\ &&\dots & & &&\\ & & &a_{(n-1)(n-1)}x_{n-1} &+ a_{n-1,n}x_n & = & b_{n-1}\\ & & & & a_{nn}x_n & = & b_n \end{array}\right., \]
note que sempre a variável \(x_i\) será igual à \((b_i-\textrm{resto})\) dividido por \(a_{ii}\). Logo para haver solução, \(a_{ii}\neq 0\):
\[\left\{ \begin{array}{rcl} x_n & =& b_n/a_{nn}\\ x_{n-1} &=& \underbrace{(b_{n-1}-a_{n-1,n}x_n)}_{\mathrm{soma}}/a_{n-1,n-1}\\ x_{n-2} &=& \underbrace{(b_{n-2}-a_{n-2,n-1}x_{n-1}-a_{n-1,n}x_n)}_{\mathrm{soma}}/a_{n-1,n-1}\\ & \dots &\\ x_1 & = & (b_1-a_{1n}x_n - \dots - a_{13}x_3 - a_{12}x_2)/a_{11}\\ \end{array}\right., \]
Fica mais fácil de pensar usando um número definido para \(n\), digamos \(n=7\):
\[\left\{ \begin{array}{rcl} x_7 & =& b_7/a_{77}\\ x_6 &=& \underbrace{(b_6-a_{67}x_7)}_{\mathrm{soma}}/a_{66}\\ x_5 &=& \underbrace{(b_5-a_{56}x_6-a_{57}x_7)}_{\mathrm{soma}}/a_{55}\\ & \dots &\\ x_1 & = & (b_1-a_{17}x_n - \dots - a_{13}x_3 - a_{12}x_2)/a_{11}\\ \end{array}\right., \]
ou, escrevendo de forma mais operacional:
\[ \underbrace{ \left\{ \begin{array}{rclcl} x_n & =& b_n/a_{nn} &=& \\ x_{n-1} &=& \underbrace{(b_{n-1}-a_{n-1,n}x_n)}_{\mathrm{soma}}/a_{n-1,n-1} &=& \\ x_{n-2} &=& \underbrace{(b_{n-2}-a_{n-2,n-1}x_{n-1}-a_{n-1,n}x_n)}_{\mathrm{soma}}/a_{n-1,n-1} &=& \\ & \dots & &=& \\ x_1 & = & (b_1-a_{1n}x_n - \dots - a_{13}x_3 - a_{12}x_2)/a_{11} &=& \left( b_1 - \Sigma_{i=2}^n a_{1i} x_i\right)\frac{1}{a_{11}}\\ \end{array}\right.}{} \\ x_j = \frac{1}{a_{jj}}\left( b_j - \Sigma_{i=j+1}^n a_{ji}x_i\right). \]
Veja que em cada linha, o termo “soma” é calculado com os valores já obtidos acima. E que cada linha \(j\) pode ser expressa pela fórmula sob o colchete. Esta fórmula é a base do nosso algorítmo (em Python):
# Importa Numpy com o nome 'np' (pra ficar curto)
import numpy as np
# Declara a matrix triangular superior
A = np.array([[2,-1,1],[0,1,2],[0,0,1]]);
# Declara o vetor B
B = np.array([2,3,1]);
# Declara o número de equações
n=B.size()
# Declara o vetor x (com zeros)
x = np.zeros(n);
# Loop nas Equações:
for jj in range(n,0,-1):
# A função range em python é curiosa,
# neste caso ela define a lista: n,n-1,n-2,...,2,1
# O zero fica de fora!
#
# Loop das somatórias internas
s = 0;
for ii in range(jj+1,n+1):
# Aqui range vai de jj+1,jj+2,..., até n.
#
# NOTE: se jj=n (a primeira equação), este loop NÃO EXECUTA!
#
# NOTE: Índices vão de 0 até n-1, então é preciso subtrair de 1.
s = s - A[jj-1,ii-1]*x[ii-1];
#
# Já fora do Loop:
x[jj-1] = (B[jj-1] + s)/A[jj-1,jj-1];
print(x)
e salve em um arquivo sl.py (sistemas lineares).
Desta forma voce pode a rotina no futuro:
import sl
# Declara a matrix triangular superior
A = np.array([[2,-1,1],[0,1,2],[0,0,1]]);
# Declara o vetor B
B = np.array([2,3,1]);
x = sl.ts(A,B)
\[\left\{ \begin{array}{rcl} x_1+x_2+2x_3 &=& 1\\ 2x_2+x_3 &=& -3\\ 5x_3 &=&-5 \end{array} \right. \]
Faça primeiramente a mão, e depois usando o programa.
O método de eliminação gaussiana é um método para transformar um sistema completo
\(\displaystyle \left\{\begin{array}{ c c } a_{11} x_{1} +a_{12} x_{2} +a_{13} x_{3} \ =b_{1} & ,l_{1}\\ a_{21} x_{1} +a_{22} x_{2} +a_{23} x_{3} =b_{2} & ,l_{2}\\ a_{3}{}_{1} x_{1} +a_{3}{}_{2} x_{2} +a_{33} x_{3} =b_{3} & ,l_{3} \end{array}\right. \ \rightarrow \ Ax=b\)
\[\left\{ \begin{array}{lll} a_{11} x_1 + a_{12} x_2 + \dots a_{1n}x_n & = & b_1\\ a_{21} x_1 + a_{22} x_2 + \dots a_{2n}x_n & = & b_2\\ \dots & & \\ a_{n1} x_1 + a_{n2} x_2 + \dots a_{nn}x_n & = & b_n \end{array}\right., \]
em um sistema triangular da forma
\[\left\{ \begin{array}{rrrrrcl} a_{11} x_1&+ a_{12} x_2 &+\dots &+a_{1(n-1)}x_{n-1}&+ a_{1n}x_n & = & b_1\\ & a_{22} x_2 &+\dots &+a_{2(n-1)}x_{n-1}&+ a_{2n}x_n & = & b_2\\ &&\dots & & &&\\ & & &a_{(n-1)(n-1)}x_{n-1} &+ a_{n-1,n}x_n & = & b_{n-1}\\ & & & & a_{nn}x_n & = & b_n \end{array}\right., \]
Para isso são usadas algumas regras. O resultado de um sistema de equações não muda se você fizer:
Trocar a ordem das equações - o resultado não pode depender da ordem das equações que voce vai resolvendo.
Multiplicar uma equação por um número \(\ne 0\) - obviamente, multiplicar ambos os lados de uma equação não muda o resultado.
Somar duas equações, trocuando uma delas pelo resultado da soma - como ambas são verdade, a soma delas também é. Voce tem que descartar uma das originais.
Utilizando as regras acima voce pode transformar um sistema qualquer (quadrado) em um sistema triangular.
Por exemplo:
\[\left\{ \begin{array}{rrrrrclr} x_1& & &+&x_3&=&0 &\qquad l_1=\text{1a eq}\\ x_1&+&x_2 & & &=&1 &\qquad l_2=\text{2a eq}\\ 2x_1&+&3x_2&+&x_3&=&1 &\qquad l_3=\text{3a eq} \end{array} \right. \]
Para transformar em um sistema triangular, pode-se fazer assim:
O que gera:
\[\left\{ \begin{array}{rrrrcl} x_1& & & +&x_3&=&0\\ & &x_2&-&x_3&=&1\\ & & & &x_3&=&-1 \end{array} \right.,\]
cuja solução (via a solução de equação triangular) é: \(x_1=1, x_2=0, x_3=-1\).
Exercício: Prove que as transformações acima transformam um sistema no outro. Encontre a solução.
Algorítmo para transformar um sistema de 3x3 em um sistema triangular superior:
\[\displaystyle \left\{\begin{array}{ c c } x_{1} +a_{12} /a_{11} x_{2} +a_{13} /a_{11} x_{3} \ =\ b_{1} /a_{11} & ,l*_{1} =l_{1} /a_{11}\\ x_{1} +a_{22} /a_{21} x_{2} +a_{23} /a_{21} x_{3} =b_{2} /a_{21} & ,l*_{2} =l_{2} /a_{21}\\ x_{1} +a_{3}{}_{2} /a_{31} x_{2} +a_{33} /a_{31} x_{3} =b_{3} /a_{31} & ,l*_{3} =l_{3} /a_{31} \end{array}\right. \] 2. Subtrair as equações \(\displaystyle l_{2}\)e \(\displaystyle l_{3}\) por \(\displaystyle l_{1}\), e multiplacamos cada uma por \(\displaystyle a_{21}\) e \(\displaystyle a_{31}\) respectivamente (e retornamos primeira equação a sua forma original)
\[\displaystyle \left\{\begin{array}{ r c l l } a_{11} x_{1} +a_{12} x_{2} +a_{13} x_{3} \ & = & \ b_{1} & ,l_{1}\\ ( a_{22} -a_{12}( a_{21} /a_{11})) x_{2} +( a_{23} -a_{13}( a_{21} /a_{11})) x_{3} & = & b_{2} -b_{1}( a_{21} /a_{11}) & ,l''_{2} =( l*_{2} -l*_{1}) a_{21}\\ ( a_{3}{}_{2} -a_{12}( a_{31} /a_{11})) x_{2} +( a_{33} -a_{13}( a_{31} /a_{11})) x_{3} & = & b_{3} -b_{1}( a_{31} /a_{11}) & ,l''_{3} =( l*_{3} -l*_{1}) a_{31} \end{array}\right. \]
Ou, de maneira mais sucinta:
\[\displaystyle \left\{\begin{array}{ r c l l } a_{11} x_{1} +a_{12} x_{2} +a_{13} x_{3} \ & = & \ b_{1} & ,l_{1}\\ a'_{22} x_{2} +a'_{23} x_{3} & = & b'_{2} & ,l'_{2}\\ a'_{3}{}_{2} x_{2} +a'_{33} x_{3} & = & b'_{3} & ,l'_{3} \end{array}\right. \]
Note que agora temos NOVOS Coeficientes \(\displaystyle a'\) e \(\displaystyle b'\).
Subtrair a equação \(\displaystyle l'*_{3}\) por \(\displaystyle l'*_{2}\) , e multiplicamos por \(\displaystyle a'_{32}\) (e retornamos a segunda equação a sua forma original):
\[\displaystyle \left\{\begin{array}{ r l l l } a_{11} x_{1} +a_{12} x_{2} +a_{13} x_{3} \ & = & \ b_{1} & ,l_{1}\\ a'_{22} x_{2} +a'_{23} x_{3} & = & b'_{2} & ,l'_{2}\\ ( a'_{33} -a'_{23}( a'_{32} /a'_{22})) x_{3} & = & b_{3} -b_{2}( a'_{32} /a'_{22}) & ,l''_{3} =l'*_{3} -l'*_{2} \end{array}\right. \]
Ou de maneira mais sucinta:
\[\displaystyle \left\{\begin{array}{ r c l c } a_{11} x_{1} +a_{12} x_{2} +a_{13} x_{3} \ & = & b_{1} & ,l_{1}\\ a'_{22} x_{2} +a'_{23} x_{3} & = & b'_{2} & ,l'_{2}\\ a''_{33} x_{3} & = & b''_{3} & ,l''_{3} \end{array}\right. \]
E agora temos um sistema triangular superior.
Aqui vamos generalizar o procedimento, que será feito linha por linha:
Linhas \(\displaystyle i\), coeficiente \(\displaystyle j\): \(\displaystyle a_{ij}^{3} =\ a_{ij}^{2} -a_{2j}^{2}\frac{a_{i2}^{2}}{a_{22}^{2}}\) e \(\displaystyle b_{i}^{3} =b_{i}^{2} -b_{2}^{2}\frac{a_{i2}^{2}}{a_{22}^{2}}\)
\(\displaystyle a_{ij}^{3} ,b_{i}^{3}\) representam os novos coeficientes apos a segunda iteração.
Os coeficientes \(\displaystyle a_{ii}^{i}\) são chamados de “pivot”, e são os elementos da diagonal principal durante o processo de eliminação. Se, na iteração \(\displaystyle i\)+1, após o passo (b), \(\displaystyle a_{ii}^{i} =0\), então precisamos trocar a equação \(\displaystyle i\) (que tem zero como elemento pivot) por uma outra equação mais abaixo com pivot\(\displaystyle \neq 0\).
O Algorítmos, de forma mais sucinta é:
Dados de entrada: Matrix \(\displaystyle A_{n\times n} =a_{ij} ,\ B_{n\times 1} =b_{i}\).
Para \(\displaystyle i=1\) até \(\displaystyle n-1\), faça: (vai linha por linha \(\displaystyle i\))
—- Encontre \(\displaystyle l\geq i\) tal que \(\displaystyle a_{li} \neq 0\) ( encontre a linha \(\displaystyle l\) abaixo de \(\displaystyle i\) com pivot não nulo
—- Se \(\displaystyle a_{ll} =0\) para todos \(\displaystyle l\geq i\), então \(\displaystyle A\) não tem inversa! FIM.)
——– Troque a linha \(\displaystyle i\) pela linha \(\displaystyle l\). ( Se \(\displaystyle i=l\) essa troca não faz nada.)
—- Para \(\displaystyle k=i+1\) até \(\displaystyle n\), faça: ( Loop nas linhas abaixo de \(\displaystyle i\))
——– \(\displaystyle m=\frac{a_{ki}}{a_{ii}{}}\) ( coeficiente \(m\))
——– \(\displaystyle b_{k} =b_{k} -mb_{i}\) ( novo valor de \(\displaystyle b\) para a linhas \(\displaystyle k\))
——– Para \(\displaystyle j=i+1\) até \(\displaystyle n\), faça ( Loop nos coeficientes da linha \(\displaystyle k\))
———— \(\displaystyle a_{kj} =a_{kj} -ma_{ij}\) ( Novos coeficientes)
(No livro está trocado o \(\displaystyle k\) e o \(\displaystyle i\), porque eu estou usando \(\displaystyle i\) para o índice das iterações.)
O programa está implementado na rotina eg dentro do arquivo sl.py.
Na Eliminação Gassiana, implemente a troca de linhas para escolher o MAIOR pivot -container{a} como principal. Algorítmo 2.3 do livro.
Implemente a Fatoração LU
Implemente a Fatoração de Cholesky
Nem sempre um sistema linear dados por \(A_{mn}x_{n}=b_{m}\) apresentam uma única solução.
NOTE: Aqui estamos denotando explicitamente o tamanho dos vetores e matriz, \(m\) é o número de linhas, e \(n\) é o número de colunas.
Quando o número de incógnitas (dimensão de \(x\), número de colunas de \(A\)) for maior do que o número de equações (dimensão de \(b\), número de linhas de \(A\)) o sistema é sub-determinado - Faltam equações! E assim há infinitas soluções.
Ex. \[ \left[ \begin{array}{lll} a_{11} & a_{12} & a_{13}\\ a_{21} & a_{22} & a_{23} \end{array} \right] \left[ \begin{array}{l} x_1\\ x_2\\ x_3 \end{array} \right] = \left[ \begin{array}{l} b_1\\ b_2 \end{array} \right]. \]
Se a dimensão de \(x\) (número de incógnitas/colunas de \(A\)) for menor que o número de equações, o sistema é super-determinado - Tem equações demais! E assim pode não haver nenhuma solução.
Ex. \[ \left[ \begin{array}{ll} a_{11} & a_{12} \\ a_{21} & a_{22} \\ a_{31} & a_{32} \end{array} \right] \left[ \begin{array}{l} x_1\\ x_2\\ \end{array} \right] = \left[ \begin{array}{l} b_1\\ b_2\\ b_3 \end{array} \right]. \]
Quando o sistema é quadrado, número de incógnitas é igual ao de número de equações, o sistema pode ter uma ou nenhuma solução.
Ex. \[ \left[ \begin{array}{ll} a_{11} & a_{12} \\ a_{21} & a_{22} \end{array} \right] \left[ \begin{array}{l} x_1\\ x_2\\ \end{array} \right] = \left[ \begin{array}{l} b_1\\ b_2\\ \end{array} \right]. \]