Cálculo Numérico- UFABC
Antes de analisarmos um sistema linear é importante definir o conceito de equação linear. Toda a equação que puder ser escrita da seguinte maneira:
a1x1+a2x2+a3x3+.....+anxn=c
(com a1, a2, a3, an coeficientes reais , e o termo real independente c),
será linear.
Quando existe um conjunto finito de m equações lineares com variáveis x1, x2….,xn, então temos um sistema linear.
Sistema linear com duas equações e
duas variáveis.
Sistema linear com três equações e
quatro variáveis.
A solução de um sistema linear será uma dupla ordenada (x,y), um trio ordenado (x,y,z), ou qualquer sequência ordenada correspondente ao número de variáveis apresentadas no sistema.
Em outras palavras, uma solução é uma atribuiçaõ de números às variáveis que satisfaça simultaneamente todas as equações do sistema.
A teoria dos sistemas lineares é base da algebra linear. Já os algoritimos computacionais são capazes de encontrar solução de sistemas e tornam as soluções mais rápidas e eficientes.
O que ocorre muitas vezes é a aproximação de um sistema de equações não lineares a um sistema linear. Trata-se, nesse caso, de um mecanismo muito útil para modelos matemáticos e simulações computacionais.
Formas de Representação
Um sistema linear pode ser reprezentado na forma matricial, com uma Matriz do sistema e um vetor como termo independente.
Suponha o sistema linear genérico com m equações e n variáveis.
Sua Matriz seria:
E o termo independente: (b1, b2,.......,bn)
Soluções de um Sistema Linear
Dizemos que um sistema é :possível e determinado quando apresenta uma solução única.
possível e indeterminado quando existem infinitas soluções;
impossível quando não há solução.
Obs: É impossível que um sistema linear tenha um número finito de soluções diferente de uma. Ou seja, um sistema linear não pode ter duas, sete, nem vinte soluções. Se tiver mais de uma, necessáriamente serão infinitas.
Cramer
O método é utilizado quando o número de equações e o número de incógnitas forem iguais.
Como um sistema linear pode ser representado matricialmente, Cramer desenvolveu um método que envolve propriedades de matrizes e determinantes.
O valor das incógnitas são dados por frações:
O denominador é o determinante da matriz que representa os coeficientes das incógnitas (Mx).
O numerador é o determinante da matriz dos coeficientes das incógnitas (M), após uma substituição de uma das colunas pelos termos independentes do sistema.
Eliminação de Gauss
O método é a parte principal de um procedimento para a resolução sistemática de sistemas de equações lineares. Seu objetivo é o de escalonar uma matriz, utilizando operações nas linhas até obtermos sua forma escalonada reduzida. O resultado, ou a solução do problema pode ser facilmente identificada uma vez encontrada a forma reduzida. É um método muito interessante e fácil para a percepção do tipo de solução- possível determinada/indeterminada ou impossível.
Para entender o funcionamento do método é necessário entender como ocorre o processo de escalonamento de uma matriz. Para isso, algumas definições:
- LINHA NULA é qualquer linha de uma matriz com todas as entradas zero.
-PIVÔ de uma linha é o primeiro elemento não nulo, da esquerda para a direita, na linha.
A matriz escalonada será então uma matriz onde:
- as linhas nulas ficam na parte inferior da matriz
- a partir da segunda linha, o pivô de cada linha não nula fica à direita do pivô da linha acima.
A matriz ESCALONADA REDUZIDA, será:
-escalonada
-os pivôs são todos iguais a 1
-nas colunas com pivô, todas as entradas, exceto o pivô, são nulas
Qual o objetivo do escalonamento?
Transformar o sistema em um sistema equivalente, com mesmo conjunto solução, mas com um formato mais simples (escalonado).
Como fazer o escalonamento?
Ele é realizado através de operações entre linhas. Entre elas, podemos, trocar de posição as linhas da matriz, multiplicar uma das linhas por uma constante, e trocar linha por ela mais múltiplo de outra linha.
Método em 5 passos:
Dada a seguinte matriz:
1-) Encontrar a primeira coluna não nula da esquerda para a direita- esta será uma coluna pivô.
2-) Se necessário, troque linhas para ter um pivô não nulo.
3-) Multiplique a linha que contém o pivô, de modo que ele se torne 1.
4-) Zere os elementos acima e abaixo do pivô.
5-) Esqueça a linha que tem o pivô e repita os passos.
O valor de cada uma das incógnitas é calculado fazendo a divisão dos resultados de dois determiantes. Divide-se o determinante de M pelo determinante de Mx, My para qualquer que seja a incógnita calculada.
6
Agora fica fácil estender esse mecanismo para a solução de um sistema linear. Nesse caso, o que se faz é adicionar na própria matriz que iremos escalonar uma coluna com os termos independentes do sistema. Ela passa a ser chamada de matriz aumentada.
O procedimento deve ser realizado até a coluna que antecede à dos termos independentes e a solução será obtida da seguinte maneira:
Chama matriz aumentada aquela que contém também uma coluna com os "resultados" das linhas do sistema.
A soluçaõ do sistema linear será:
x=5
y=-1
z=-1
Decomposição A=LU
Esse método irá utilizar a fatoração de matrizes. Quando temos um sistema, ao escrevê-lo na forma matricial, já vimos que se dará na forma: Ax=b, sendo A a matriz dos coeficiente, x o vetor das incógnitas e b o vetor dos resultados de cada linha do sitema.
A ideia de fatorar matrizes, transformará a matriz A em uma multiplicação de outras duas matrizes:
A=LU. A matriz L, do inglês lower, será da forma triangular inferior. Já U, do inglês upper, será uma matriz triangular superior.
Motivação para o uso do método
Imaginemos os seguintes sistemas: Ax=b, Ay=c, Az=d...
Podemos encontrar as soluções calculando a matriz inversa de A, de modo que:
x=A¹b, y=A¹c, z=A¹d.
Quando temos um número muito grande de sistemas para resolver, a maneira mais fácil é utilizar um algoritimo no computador. Cada máquina terá uma determinada capacidade de processamento. Para que o tempo de resolução de muitos sistema seja o menor possível, o computador deve fazer o menor número de operações.
Realizando o médoto A=LU, o número de operações é menor e ganhamos tempo e capacidade de processamento.
Procedimento
De maneira simplificada, deveremos aplicar o método de Gauss à matriz A, ou seja escalonaremos a matriz A até encontrar U.
As colunas de L são encontradas durante o escalonamento.
Obs: se A possui mais colunas do que linhas, as colunas de L são a matriz identidade.
Exemplo- passo a passo
Consideremos o seguinte sistema:
1-) Escrever o sistema na forma matricial
2-) Escalonamento em A para encontar a matriz U: devemos prestar atenção aos multiplicadores que iremos usar para zerar os elementos abaixo dos pivôs. Nesse caso, 3 será o primeiro pivô. O numero 1 da segunda linha deve ser subtraido de 1/3 do número 3 da primeira linha para que se torne zero. Logo, o multiplicador nesse caso será 1/3.
O sistema possui três incognitas, e portanto 3 pivôs. A matriz escalonada resultante, se analisarmos, já estará na forma desejada- triangular superior.
A matriz L, como sabemos será triangular inferior. Ela será composta por uma diagonal de números 1, e pelos multiplicadores utilizados durante o escalonamento de A.
O primeiro elemento da segunda linha era preenchido, em A pelo número 1. Tivemos que multiplicar o pivô por 1/3, logo, este é o multiplicador. O primeiro elemento da terceira linha era o 4, e para zerálo, multiplicamos o pivô por 4/3 e realizamos uma operação de linhas. O multiplicador foi o 4/3. Por último, segundo elemento da terceira linha, era originalmente o 3, para elimina-lo, multiplicamos o pivô da segunda coluna por 1.
3-)Depois disso, podemos, efetivamente calcular o valor das incógnitas do sistema. No entanto, esse processo será realizado em 2 passos, e uma consideração deve ser feita.
a-) L.y=b
b-) U.x=y
Assim, chegamos à solução de que x1=-3; x2=5 e x3=0.
É notável que o método é o mais trabalhoso dos três comentados no exercício.
Criando-se a matriz aumentada A relativa ao sistema em questão, temos:
É com base nessa matriz que trabalharemos com os métodos de Cramer (i), eliminação de Gauss (ii) e decomposição A=LU (iii).
A teoria de cada método não será explicitada novamente, entretanto serão apresentadas as resoluções e os resultados obitidos, além de comentários finais e conclusões.
(i) Método de Cramer
(ii) Método da Eliminação de Gauss
Partindo da matriz aumentada A do sistema e fazendo a simplificação das linhas, temos:
E o sistema final se torna:
(iii) Decomposição A=LU
Primeiramente, verificamos a condição de que para ser decomposta, a matriz A precisa possuir determinante diferente de zero, incluindo os determinantes de suas "submatrizes" a partir da diagonal principal.
Obteremos agora as matrizes L e U
- Primeira linha de U:
- Primeira coluna de L:
- Elementos faltantes a partir da fórmula dos elementos gerais:
- Finalmente as matrizes L e U e a matriz b que já conhecemos:
O restante dos cálculos será realizado conforme o método propõe: Ly=b e Ux=y.
Como pode ser observado, chegamos a uma solução diferente daquela dada no enunciado, porém, como nossa solução foi igual para os três métodos utilizados, acreditamos que a solução final encontrada através dos métodos diretos está correta. Todos os métodos utilizados na resolução deste exercício fornecem a solução exata do sistema linear, sendo melhor utilizados em cálculos manuais, pois são contas simples e rápidas.
JACOBI:
-
Para resolução de sistemas lineares de pequena dimensão é ineficiente, já que demanda um tempo maior do que a maioria dos métodos, mas por outro lado, para sistemas lineares de grandes dimensões e com muitas entradas nulas, mostra-se muito eficiente.
Dada uma matriz quadrada nxn, de determinante não nulo, formada por equações lineares Ax = b
Decompõe-se A em sua diagonal principal - matriz cuja diagonal principal é igual à da matriz A e todas as outras entradas são nulas.
E o resto - matriz em que a digonal principal é composta apenas de entradas nulas e as outras entradas são os coeficientes da matriz A, respeitando suas devidas posições.
Então, por definição, A = D+R.
É possível, dessa forma, reescrever a forma do sistema linear como:
Dx = b - Rx.
Isolando x, x = 1/D . (b - R), as linhas dos sistema ficam na forma:
x(k+1)= 1/D . (b - Rx(k)) (forma iterativa)
Tipicamente uma forma iterativa, em que o valor calculado para x - x(k+1) - só é obtido calculando o valor da iteração anterior - x(k).
Critério de convergência (Critério de Sassenfeld):
-
Critério de linhas:
Isto é,
-
Critério das colunas:
Isto é,
Se a matriz for unicamente a diagonal dominante - em cada linha o elemento da diagonal é maior que a soma dos outros elementos da linha - o critério de convergência é automaticamente atendido.
Pode-se notar que o critério independe de x(0). E geralmente a aproximação usada para x(0)é o vetor independente b.
Critério de parada:
[ || X(k+1) - X(k) || / || X(k+1) ] < ε
GAUSS-SEIDEL:
Método semelhante ao anterior, obedece ao mesmo critério de convergência, Sassenfeld.
Apesar de usar o mesmo critério de convergência, devido ao tipo de iteração, é um método que converge mais rápido.
Nesse método, são usados os resultados mais recentes, é calculada a iteração e logo em seguida o vetor é atualizado.
Sua iteração é dada por:
O processo é definido por:
Para calcular o erro:
O maior valor entre as reízes da iteração (k-1) e (k) deve ser dividido pelo valor máximo de x da iteração atual.
Introduziremos aqui os critérios de convergência, mais especificamente o critério das linhas, que melhor se relaciona com o método de Jacobi, e o critério de Sassenfeld, que melhor se relaciona com o método de Gauss-Seidel.
CRITÉRIO DAS LINHAS
O critério das linhas pede que, para todo i = 1, 2, ..., n:
Em palavras: "o valor absoluto do termo diagonal na linha i é maior do que a soma dos valores absolutos de todos os outros termos na mesma linha".
É importante observar que o critério das linhas pode deixar de ser satisfeito se houver troca na ordem das equações, e vice-versa: uma troca cuidadosa pode fazer com que o sistema passe a satisfazer o critério.
- Teorema: se o sistema linear satisfaz o critério das linhas, então o método de Jacobi converge.
Para o sistema linear do exercício em questão, temos:
Verificando o critério para as linhas da matriz A, temos:
Visto que para cada linha o somatório está de acordo com a condição acima citada (<1), então o teorema é satisfeito, ou seja, o método de Jacobi converge.
CRITÉRIO DE SASSENFELD
Dado o sistema linear A.x=b. Seja os βk de tal forma que:
Onde:
- Teorema: se o sitema linear satisfaz o critério de Sassenfeld, então o método de Gauss-Seidel gera uma sequência {x(k)} que converge para a solução do sistema.
Para o sistema linear em questão, temos:
Como todo βk<1, então o método de Gauss-Seidel converge para a solução do sistema linear.
Pode-se perceber que não foi necessário rearranjar quaisquer linhas ou colunas da matriz A relativa ao sistema linear do exercício. Caso fosse necessário, uma condição que pode ser facilmente visualizada é a de que os elementos das diagonais devem ser os maiores números de cada linha e/ou coluna.
Vamos agora à resolução do sistema linear através dos métodos iterativos de Jacobi (i) e Gauss-Seidel(ii). Nesse exercício foi utilizado o software MATLAB, para que não fossem feitas cada uma das possíveis iterações manualmente.
(i) Método de Jacobi
- Código utilizado no MATLAB
function [x,iter]=Jacobi(A,b,x0,tol)
format long
A = [5 2 1; -1 4 2; 2 -3 10];
b = [7 3 -1]';
x0 = [-2.4 5 0.3]';
tol = 1e-2;
L = -tril(A,-1); % extrai a parte triangular inferior da matriz
U = -triu(A,1); % extrai a parte triangular superior da matriz
D = diag(diag(A)); % extrai os elementos da diagonal principal da matriz
N = L + U;
C = D \ N;
G = D \ b;
iter = 1;
x = C*x0 + G;
while norm(x - x0) > tol*norm(x0)
x0 = x
x = C*x0 + G
iter = iter + 1
end
- Resultado final obtido na janela de comandos
iter =
10
ans =
0.995534297240000
0.999676858700000
0.003638876770000
(ii) Método de Gauss-Seidel
- Código utilizado no MATLAB
function [x,iter]=gauss(A,b,x0,tol)
format long
A = [5 2 1; -1 4 2; 2 -3 10];
b = [7 3 -1]';
x0 = [-2.4 5 0.3]';
tol = 1e-2;
L = tril(A,-1); % extrai a parte triangular inferior da matriz
U = -triu(A,1); % extrai a parte triangular superior da matriz
D = diag(diag(A)); % extrai os elementos da diagonal principal da matriz
M = D + L;
C = M \ U;
G = M \ b;
iter = 1;
x = C*x0 + G;
while norm(x - x0) > tol*norm(x0)
x0 = x
x = C*x0 + G
iter = iter + 1
end
- Resultado final obtido na janela de comandos
iter =
6
ans =
1.000068869335937
1.000212232470703
0.000049895874023
A solução do sistema linear por meio de métodos iterativos se aproxima da solução exata S=(1, 1, 0), mas não a alcança. A solução exata pode ser calculada através dos métodos diretos já citados aqui nesta página.
O que é legal observar nesses dois últimos métodos é o número de iterações utilizadas para se chegar na resposta e, também, aquele que mais se aproxima da mesma baseando-se no mesmo valor de tolerância (dado no enunciado). A partir disso, percebe-se que o método de Gauss-Seidel, além de mais preciso, necessitou de menos iterações para convergir para a solução do sistema linear, ou seja, é mais eficiente, tanto em termos de aproximação quanto de velocidade, que o método de Jacobi.
Finalmente, é importante ressaltar que assim como previsto pelos critérios das linhas e de Sassenfeld, os dois métodos convergiram para a solução "desejada" do sistema linear.
REFERÊNCIAS
[1] http://www1.univap.br/spilling/CN/apostila4.pdf
[2] http://www.ime.usp.br/~colli/cursos/NumericoIAG-2005/LivroNumericoCapitulo4.pdf
[3] http://www.abenge.org.br/CobengeAnteriores/2003/artigos/CBE103.pdf
[4] http://docslide.com.br/documents/metodo-de-jacobi-e-o-metodo-de-gauss-seidel-matlab.html
