Universidade Federal do Rio Grande do
Norte
Métodos Computacionais
Marcelo Nogueira
Sistemas Lineares
Comuns na engenharia (calculo de estruturas, redes elétricas,
solução de equações diferenciais)
Forma geral
: coeficientes
Ex:
: incógnitas
: termos independentes
2 3 5
4 4 3 3
2 3 1
Resolver significa achar que satisfaça o conjunto de equações
Forma Matricial
Onde
Ex
Classificação
Incompatível: não possui solução
Ex:
 x1 + x2 = 3

2 x1 + 2 x2 = 8
Compatível: possui solução (1 ou mais)
Determinado: solução única
 x1 + x2 = 3

 x1 − 2 x2 = −3
Indeterminado: várias soluções
Ex:
 x1 + x2 = 3

2 x1 + 2 x2 = 6
x 1 x 2
x 1 x 2
x 1 x 4
x 10 x 7
Sistema triangular
Superior
Inferior
Podem ser solucionados com Resolução Retroativa
Resolução Retroativa
Ex: Resolva o seguinte sistema utilizando resolução
retroativa
Quadro
Solução:
Algoritmo Resolução Retroativa
Entrada: matriz de coeficientes A e vetor de termos independentes b
[l,c] = tamanho(A);
x = zeros(c,1); //alocacao de memoria para maior velocidade
para i=l:-1:1
soma = 0;
para j=c:-1:i
soma = soma + x(j)*A(i,j);
fim_para
x(i) = (b(i) - soma)/A(i,i);
fim_para
saída(“a solução do sistema é “ x);
Exercício: Classifique os seguintes sistemas:
3 6
4 5
4
2 3 4
3 3
2
1
1
1
2 3 0
1
3
Métodos de solução numéricos
Diretos: número finito de passos
Método de Gauss
• Método do Pivotação Parcial/Total
• Método da Eliminação de Jordan
Iterativos: seqüência de aproximações para o valor
do vetor solução x até uma precisão préestabelecida
• Método de Jacobi
• Método de Gauss - Seidel
•
Método de Gauss
Consiste em transformar o sistema linear a ser
resolvido em um sistema linear triangular, o qual
pode ser resolvido por Resolução Retroativa
Para se transformar o sistema linear, utiliza-se
transformações elementares
• Trocar a ordem das equações
• Multiplicar uma equação por um número real
não nulo
• Substituir uma equação por uma combinação
linear dela mesma com outra equação
Passos
Construir a matriz aumentada Ab
Eliminar os coeficientes de 1 nas linhas 2,3,...,n (fazer
21 31 1 0) sendo 11 chamado de
pivô da coluna
Substituir a linha 2 2 pela combinação linear
L2 + m12 ⋅ L1
onde
a12
m12 = −
a11
Substituir a linha 3 3 pela combinação linear
L3 + m13 ⋅ L1
onde
a13
m13 = −
a11
Continuar a substituição até a linha n
Caso algum elemento 0, achar outra linha
!" # 0 e trocar tais linhas.
Eliminar os coeficientes de nas linhas 3,4,...,n (fazer
$ 0)
Eliminar os coeficientes de nas linhas 4,5,...,n (fazer
$ 0) e assim sucessivamente
onde
Ex: Resolver o sistema utilizando o método de Gauss
2 3 5
4 4 3 3
2 3 1
Quadro
• Solução:
2 3 5
4 4 3 3
2 3 1
2 3
4 4
2 3
Matriz aumentada Ab
1 5
3 3
1 1
Substituindo a linha 2 por % onde % 2
4
2
3 1 5
2 3
4 3 3 ) 0 2
3 1 1
2 3
&'(
&''
2
1 5
1 7
1 1
Substituindo a linha 3 por % onde % 2 3 1
0 2 1
2 3 1
1
&*(
&((
3
5
2 3 1
7 ) 0 2 1
1
0 6 2
Substituindo a linha 3 por % onde % 2 3 1
0 2 1
0 6 2
&'*
&''
5
2 3 1
7 ) 0 2 1
6
0 0
5
Utilizando resolução retroativa
5 x3 = 15 ⇒ x3 = 3
5
7
6
5
7
15
− 2 x2 − x3 = −7 ⇒ −2 x2 − 3 = 7 ⇒ x2 = 2
2 x1 + 3 ⋅ x2 − x3 = 5 ⇒ 2 x1 +6 − 3 = 5 ⇒ 2 x1 = 2 ⇒ x1 = 2
Obs: caso o atual pivô seja nulo, devemos tentar
reordenar as linhas do sistema de forma que o novo
pivô seja não nulo
Ex: Resolva o sistema
0
3 0
3 2
Quadro
Solução
Matriz aumentada
1 1 1 0
1 1 3 0
1 3 0 2
Eliminando elementos abaixo odo pivô
1 1 1
0
Pivô nulo
0 0 2
0
0 2 1 2
Reordenando as linhas
1 1 1
0
0 2 1 2
0 0 2
0
Matriz triangular: aplicar resolução retroativa
Resíduo
Durante a solução, geralmente cometemos erros de
arredondamento, o que causa um erro na solução
obtida
O resíduo indica a qualidade da resposta obtida
Se a solução encontrada para o sistema foi +, o resíduo
, é dado por:
, +
onde o vetor e a matriz são o vetor e a matriz
original fornecidos pelo problema
Ex: Resolva o seguinte sistema, retendo durante os
cálculos 2 casas decimais, e em seguida calcule o
resíduo da solução obtida:
3 2 1
11 5
Quadro
Solução
3 2 1
1 11 5
%
0,33, % 0,99 0,66 0,33
1
11
5
0
10,34 4,67
4,67
0,45
10,34
Por resolução retroativa
1 0,9
0,03
3
0,01
1
1 0,99
3 2 0,03
,
0,02
5
5 4,98
1 11 0,45
Resíduo
Algoritmo do Método de Gauss
Entrada: matriz de coeficientes A e vetor de termos independentes b
[l,c] = tamanho(A);
Aa = [A | b];
//matriz aumentada
para i=1 ate l
pivo=Aa(i,i);
para j=i+1 ate l
m = -Aa(j,i)/pivo;
Aa(j,:) = Aa(j,:) + m* Aa(i,:);
fim_para
fim_para
x = resolucaoretroativa(Aa(1:l,1:l), Aa(:,l));
saída(“a solução do sistema é “ x);
Método do Pivotação Parcial
Semelhante ao método de Gauss
Minimiza a amplificação de erros de arredondamento
durante as eliminações
Consiste em escolher o elemento de maior módulo em
cada coluna para ser o pivô
Evita termos % muito grandes
Evita coeficientes "" muito pequenos (resolução retroativa)
Ex: Resolver o sistema com precisão de 3 casas
decimais
2 8
2 3 1
3 7 4 10
Solução
Matriz aumentada
1,00
1,00
3,00
3,00
1,00
1,00
1,00
2,00
7,00
7,00
2,00
1,00
Trocando as linhas L1 e L3
3,00
0
0
7,00
4,31
3,31
Eliminando coeficientes abaixo
2,00
3,00
4,00
4,00
3,00
2,00
8,00
1,00
10,00
4,00
4,32
0,68
10,00
1,00
8,00
10,00
4,30
4,70
O elemento de maior modulo é -4,31, de forma que este será
o pivô e não é necessário trocar linhas
3,00
0
0
7,00
4,31
0
Eliminando coeficientes abaixo
4,00
4,32
4,01
3,02
1,01
2
10,00
4,30
8,01
Utilizando resolução retroativa
8
1
, 1 1
10
3
Resíduo
1
2 3,02
0.03
2 3 1,01 0.04
7 4
0.01
2
Exercícoi: Resolva o sistema utilizando o método de
Gauss utilizando 4 algarismos, e em seguida compara a
solução obtida com a solução exata 10 1 2 . Em
seguida utilize a Pivotação Parcial e compare
novamente o resultado obtido com o exato. Qual
método obteve um melhor resultado?
0,003 59,14 59,17
5,291 6,130 46,78
Algoritmo Pivotação Parcial
Entrada: matriz de coeficientes A e vetor de termos independentes b
[l,c] = tamanho(A);
Aa = [A | b];
//matriz aumentada
para i=1 ate l
Aa = ordenalinha(Aa,i);
pivo=Aa(i,i);
para j=i+1 ate l
m = -Aa(j,i)/pivo;
Aa(j,:) = Aa(j,:) + m* Aa(i,:);
fim_para
fim_para
x = resolucaoretroativa(Aa(1:l,1:l),b);
saída(“a solução do sistema é “ x);
Algoritmo Ordena Linha
Entrada: matriz de coeficientes A e indice i
[l,c] = tamanho(A);
maximo = vabsoluto(A(i,i));
trocarcomlinha = i;
para j=i+1 ate l
se vabsoluto(A(j,i)) > maximo
maximo = vabsoluto(A(j,i))
trocarcomlinha = j;
fim_se
fim_para
linhatemp = A(i,:);
A(i,:) = A(trocacomlinha,:);
A(trocacomlinha,:) = A(i,:);
saída(A);
Método do Pivotação Total
Semelhante ao método da Pivotação Parcial
• Ao invés de escolher o maior elemento apenas da
coluna, agora iremos escolher o maior elemento
(em modulo) da matriz inteira para ser o pivô
Ex: Resolver o sistema com precisão de 2 casas
decimais
2 8
2 3 1
3 7 4 10
•
Solução
1,00
1,00
3,00
1,00
2,00
7,00
2,00
3,00
4,00
8,00
1,00
10,00
Trocando as linhas L1 e L3
3,00
1,00
1,00
7,00
2,00
1,00
4,00
3,00
2,00
10,00
1,00
8,00
3,00
1,87
1,42
7,00
0
0
4,00
1,84
2,56
10,00
1,9
9,4
Matriz aumentada
Eliminando coeficientes abaixo do pivô
3,00
1,42
1,87
Trocando as linhas L1 e L3
3,00
1,42
2,89
7,00
0
0
7,00
0
0
Eliminando coeficientes abaixo do pivô
Por resolução retroativa
4,00
2,56
1,84
4,00
2,56
0
10,00
9,4
1,9
10,00
9,4
8,67
8,67
9,4 1,42 3 3
3,00 2,00
2,89
2,56
10 3 3 3 4 3 2
1,00
7
O resíduo será 0 0 0 2 , ou seja, utilizando o mesmo número de dígitos
que no exemplo resolvido com Pivotação Parcial, já obtivemos a
solução exata
Exercício: Resolver o sistema utilizando o método da
Pivotação Completa com 3 casas decimais e depois
calcule o resíduo
2,11 4,21 0,921 2,01
4,01 10,2 1,21 3,09
1,09 0,987 0,832 4,21
Método de Jordan
Semelhante ao métodos de Gauss, consiste em
transformar o sistema dado não apenas em um sistema
triangular, mas sim em um sistema diagonal
equivalente
Sistema diagonal
0
0
0
0
4
0
0
55
Elimina a necessidade de resolução retroativa
No método de Jordan, o pivô é utilizado para zerar
todos os elementos de sua coluna (acima e abaixo de
pivô)
Ex: Resolva o sistema abaixo utilizando o método de
Jordan
2 3 5
4 4 3 3
2 3 1
Quadro
Solução
2
4
2
Matriz aumentada Ab
2
0
0
3 1 5
4 3 3
3 1 1
3 1 5
2 1 7
6 2 6
Zerando os dois elementos abaixo teremos
2
0
0
0 2,5 5,5
2 1
7
0
5
15
Zerando os dois elementos abaixo e acima teremos
2 0
0 2
0 0
0 2
0 4
5 15
Zerando os dois elementos abaixo e acima teremos
A partir da matriz diagonal, podemos calcular a solução
2
1
2
15
3
5
4
2
2
O método de Jordan pode ser utilizado para se calcular o
determinante de uma matriz
Uma vez que a matriz seja convertida em uma matriz
diagonal pelo método
0 0
0 0
4
0
0 55
o determinante desta será dado por
det 9 55
Ex: Utilizando Jordan, calcule o determinante da matriz
1 2
5 1