UNIJUÍ - Universidade  Regional do Noroeste do Estado do Rio Grande do Sul

 Professora: Tânia Michel Pereira

Apostila de  Cálculo Numérico

 

Sistemas de Equações - Métodos Diretos e Iterativos

Soluções  

Método de Gauss

Método  de  Jordan  

Resíduo e Refinamento

Método de Jacobi  

Método Gauss-Seidel

 Sair  

2. Sistemas Lineares

2.1 Considerações Iniciais

         Um sistema de equações lineares com n equações e n incógnitas é um conjunto de equações do tipo:

            Uma solução de um sistema de n equações  de n variáveis é uma seqüência de números que satisfaz as n equações simultaneamente.

 O sistema acima pode ser escrito na forma matricial  A.X=B onde

     

2.1.1 Soluções de um sistema de equações lineares  

Sistema é possível e determinado 

         Um sistema é possível e determinado quando este possuir uma única solução. Neste caso, dado um sistema  AX=B  (1)existe um único vetor  X que satisfaz a equação matricial (1).  Esta solução pode ser encontrada do seguinte modo, caso for utilizando  algum instrumento para encontrar a matriz inversa:

a)encontra-se a  matriz inversa de A,  que será representada por A-1 e que, por definição satisfaz a igualdade      A-1  A  = I .  

b)multiplica-se  cada membro da equação (1)  pela matriz   A-1. Desta forma o vetor X estará conhecido.

As equações ficam do seguinte modo considerando o sistema (1)

AX=B              multiplicando cada membro por   A-1  tem-se

 A-1AX = A-1B ,       como  A-1  A  = I  pela  própria definição de matriz inversa tem-se

 I X  =A-1B            mas I é o elemento neutro da multiplicação de matrizes, tem-se 

X  =A-1B.

         Para que um sistema  seja  possível e determinado é necessário que  o a matriz tenha posto completo e além disto o determinante  da matriz A não seja nulo.

        Clique aqui para ver como como é rápido resolver sistemas lineares  possíveis e determinados, utilizando  o método de resolução de sistemas que usa  matriz inversa  e produto de matrizes com auxílio da planilha eletrônica  Excel da Microsoft.

Sistema é possível e indeterminado 

        Um sistema é possível e indeterminado quando este possuir infinitas soluções. 
        Para que um sistema  seja  possível e indeterminado é necessário que  o a matriz seja singular ( determinante de A=0) e a matriz ampliada do sistema tenham o mesmo posto  A .

Sistema é Impossível 

    Um sistema é impossível quando este não tem solução. Para que um sistema  seja  impossível basta que  a  matriz ampliada do sistema  não tenham o mesmo posto  .

2.1.2 Sistemas Lineares Homogêneos

            O sistema:

é dito homogêneo pois os termos independentes de todas as equações são nulos. 

Solução:  A n-úpla (0,0,0,...,0) é sempre solução de um sistema de n incógnitas e recebe o nome de solução trivial, quando existem as demais são chamadas não-triviais. 

            Um sistema linear homogêneo é sempre possível .

2.1.3 Sistemas Triangulares

Um Sistema Triangular  Superior  tem a forma: 

 

Para obter a solução de um sistema triangular Superior calcula-se  em primeiro lugar o valor de xn  que é facilmente encontrado a partir da última linha do sistema  e  depois substitui-se  o valor xn, na  penúltima linha para encontrar o valor da variável que se encontra na penúltima coluna, e  continuando a retro-substituição encontra-se os valores das demais incógnitas.  

Um Sistema Triangular  Inferior tem a forma: 

 

Para obter a solução de um sistema triangular inferior calcula-se  em primeiro lugar o valor de x1  que é encontrado a partir da primeira linha do sistema  e  depois substitui-se  o valor  encontrado na  segunda  linha para encontrar o valor da variável que se encontra na segunda coluna, e  continuando a substituição encontra-se os valores das demais incógnitas. 

         Aqui você pode copiar um  programa fonte ou executável escrito em  Pascal que resolve somente sistemas triangulares.

2.2 Método de Eliminação de Gauss (Simples) 

O método  Método de eliminação de Gauss Simples, consiste em transformar o sistema dado num sistema triangular equivalente, através de uma seqüência de operações:

elementares sobre as linhas do sistema original dado:

  1. Coloca-se como primeira equação, aquela em que o coeficiente da primeira  incógnita  seja diferente de zero.

2.      Utiliza-se as propriedades de sistemas equivalentes, a fim de que,  se tornem nulos,  todos os coeficientes da primeira incógnita das demais equações, ou seja, substitui-se cada uma das equações das  linhas seguintes pela  diferença entre essa mesma equação e primeira  equação deste sistema multiplicada a por uma constante.

  1. Repete-se o processo 1 e 2  para a  segunda incógnita a partir a partir da segunda linha.
  2. Repetimos o processo com as demais incógnitas até que o sistema se torne triangular. 

 Aqui você pode copiar um  programa fonte ou executável escrito em  Pascal que transforma sistemas  "completos"  em sistemas triangulares.

Exercícios

     Resolver os sistemas pelo método de Gauss .

  

   

Faça um algoritmo ou  programa   para resolver sistemas pelo método de Gauss simples.

2.2.2 Método de  Gauss com Pivoteamento

A técnica de pivoteamento parcial, que consiste na escolha do maior elemento em módulo de uma coluna entre os candidatos a pivô. O que ocasiona a troca de linhas do sistema. Com esta técnica os multiplicadores em módulo estarão entre zero e um, diminuindo os erros de arredondamento e possíveis divisões por zero.

Aqui você pode copiar um  programa fonte ou executável  escrito em  Pascal que  transforma sistemas  com n variáveis  em outros sistemas equivalentes baseado no pivoteamento parcial, do seguinte modo: o sistema equivalente retornado possui   como valores de  aii, (i=1,2,... , n )  o maior módulo dos termos da coluna i, porém, que ficam nas linhas de  i  até n.

A técnica de pivoteamento total, que consiste na escolha do maior elemento em módulo de de qualquer  coluna entre as linhas candidatos a pivô. O que ocasiona a troca de linhas e colunas do sistema. 

Aqui você pode copiar um  programa fonte ou executável  escrito em  Pascal que  transforma sistemas  com n variáveis  em outros sistemas equivalentes baseado no pivoteamento total, do seguinte modo: o sistema equivalente retornado possui   como valores de  aii, (i=1,2,... , n )  o maior módulo dos termos da coluna i até n bem como da  linha i  até n.

Exercício:  Faça um algoritmo ou um programa, ou um procedimento que resolve sistemas lineares de ordem n pelo método de Gauss, com pivoteamento parcial ou total. Sugestão: estude o código fonte dos programas em pascal disponíveis para cópia, nesta página para obter subsídios que podem facilitar a elaboração do algoritmo ou programa solicitado.

2.2.3 Método de Gauss - Jordan

O método de Jordan consiste em transformar o sistema linear dado, em um sistema   equivalente, de forma que a matriz principal fique na forma de matriz diagonal ou matriz identidade diagonal. Para isto pode-se  seguir os seguintes passos:

1) transformar o sistema dado num  sistema triangular, da mesma forma como se  faz no método de eliminação de Gauss.

2) eliminam-se os coeficientes que não pertencem à diagonal principal, utilizando procedimentos idênticos ao do passo 1.

     Exercício: 

 Faça um algoritmo ou um programa que resolve qualquer sistema pelo método de Gauss - Jordan Sugestão: para programa em pascal, aproveite parte co código dos programas disponíveis, nesta página.

Ir  para o Topo

2.3 Cálculo do Resíduo e Refinamento de Soluções 

2.3.1Cálculo do Resíduo

O  erro residual  R associado a uma solução aproximada  ~X  é definido como R=A(~X) – b onde  A é a matriz dos coeficientes do sistema, b é a matriz dos termos independente e ~X a matriz dos valores de xi calculados por um método direto, mas com erro devido aos arredondamentos. Ou seja

   

; ;

Ir  para o Topo

2.3.2 Refinamento  de Soluções

O refinamento de soluções aproximadas de sistemas lineares, é utilizada para melhorar exatidão dos resultados.

O Refinamento de soluções é obtido a partir de uma solução inicial, obtida através do método direto se solução de sistemas lineares, por exemplo: pelo Método de Gauss, com pivotação (ou pivotiamento).

Início do processo de refinamento

Considerando X1= ~X  a solução aproximada encontrada através de um método direto, R1  a matriz  coluna dos resíduos, A a matriz dos coeficientes e b a matriz coluna dos termos independentes do sistema dado, e C1 a matriz com as parcelas de correção para cada um dos componentes de X1 tal que

X = X1 + C1 ou seja, C1= X - X1. 

Multiplicando ambos os membros da última equação pela matriz A tem-se:

AC1 = AX – AX1 . Como   AX=b  pode-se reescrever a   última equação, escrevendo b em vez de AX e tem-se:

AC1=b –AX1 = R1 .     Mas b-AX1=R1, portanto,  b-AX1 pode ser substituído por R1, onde R1 é o resíduo da solução aproximada X1. desta forma tem-se

AC1 = R1 .

Resumindo: para o primeiro refinamento  determina-se a matriz R1 da equação R1=b –AX1, em seguida C1  da equação  AC1 = R1.

=

Após a obtenção de C1, encontra-se X2  , a partir da igualdade

X2=X1+C1, pelo fato de poderem encontrar erros de arredondamento no processo utilizado  para obter C1.   Calcula-se em seguida R2 .

Se R2 satisfaz a condição da  tolerância predefinida, então a solução será dada por X2. Senão inicia-se o processo do cálculo de C2, para obter X3 , verificar  se R3 satisfaz a a condição de tolerância.  De forma genérica se pode dizer que: a cada etapa  refina-se a solução obtida a  partir de Xk, gerando uma aproximação Xk+1

Ir  para o Topo

Alguns links relacionados com o assunto:

http://www.dc.uel.br/disciplinas/3cop002/aula01.html

http://intranet.inf.ufes.br/~galarda/sistemaslin.htm

www.unijui.tche.br/defem/materialalunos/TaniaMP/matlab/index.html

http://www.dmi.ubi.pt/~crocker/anumerica1/algoritmos/jacobi.html

http://www-di.inf.puc-rio.br/~tcosta/cap32.htm

http://www.math.ist.utl.pt/~calves/cursos/SisLin-Iter.htm                         http://www.ime.usp.br/~trodrigo/maple.br/downloadworksheet.php   

Ir  para o Topo

    2.4 Resolução de Sistema de Equações por Métodos Iterativos 

Seja o sistema S da forma

Supondo que  S  tenha sido  reordenada de modo que todos os seus elementos da diagonal sejam não-nulos. Como será assumido  que aii é não nulo, pode-se escrever o sistema em que a primeira incógnita fique isolada na primeira linha, a segunda incógnita,  na segunda linha e assim por diante, tem-se então o sistema  com a seguinte forma:

2.4.1 Método de Jacobi

Considerando o lado esquerdo do sistema como os elementos de um novo passo de iteração (k+1) e os elementos do lado direito como elementos do passo anterior (k), tem-se:

...........................

Exemplo

Para o sistema :

 

separa-se as incógnitas x1 e x2 da seguinte forma:

escolhe-se os índices da iteração k e k+1 onde  k=0,1,2,3...M. onde M é o número máximo de iterações consideradas.

Agora faz-se o seguinte:

1.       Chama-se de x1(0) e x2(0)  as aproximações iniciais, as quais são tomadas de forma arbitrária (chute) .

Usando para o passo K=0 o chute inicial x1(0) =0 e x2(0)=0. .Assim  a primeira aproximação de x1=0  e x2=0  > se for utilizado X(0)  o vetor cujos componentes são x1(0) e x2(0)   tem-se  para K=0:

 

2.       Aplica-se x1(0)  do lado direito do sistema  obtendo um novo valor para x11  e  x21  tem-se  para K=1: 

    portanto  

3. Usa-se estes valores x11  e  x21 novamente no sistema  obtendo os valores  de x12  e  x22. Para K=2 tem-se:

    portanto

4. O próximo passo será  encontrar x13  e  x23. Para K=3 tem-se: 

    portanto

5. Para os demais x1k  e  x2k  procede-se da mesma forma.

Veja  um Procedimento para determinar  a solução  de um sistema pelo método iterativo de Jacobi  utilizando o programa MapleV  R3 .

Veja  uma Planilha do Excel  para determinar  a solução  de um sistema pelo método iterativo de Jacobi 

  Ir  para o Topo

2 .4. 2 Método Iterativo de Gauss-Seidel

Nesse caso, substitui-se diretamente os valores que vão sendo calculados, isto é, depois do cálculo de x1(1) substitui-se esse valor na avaliação de x2(1); em seguida, na avaliação de x3(1) já pode-se usar esses valores que já foram atualizados, x1(1) e x2(1).. Atualiza-se os valores  de xik+1 obtidos durante o próprio passo k, da iteração. Isso significa que não se dá um passo completo com os valores (k) do passo anterior, como no Método de Jacobi e sim, vamos usando as modificações feitas imediatamente.

Para um sistema de n variáveis o processo de iteração pelo método de Gauss-Seidel  pode ser representado da seguinte forma:

...........................

 

Exemplo:

Tomando o mesmo exemplo utilizado no método iterativo de Jacobi

 

separa-se as variáveis x1 e x2 .

escolhe-se os índices da iteração k e k+1:

          Agora faz-se o seguinte:

1.        Chama-se de x1(0) e x2(0)  as aproximações iniciais, as quais são tomadas de forma arbitrária (chute) .

Usando para o passo K=0 o chute inicial x1(0) =0 e x2(0)=0. .Assim  a primeira aproximação de x1=0  e x2=0  > se for utilizado X(0)  o vetor cujos componentes são x1(0) e x2(0)   tem-se  para K=0:

 

2 .      Aplica-se x1(0)  do lado direito do sistema  obtendo um novo valor para x11  e  x21  tem-se  para K=1: 

    portanto  

3.Usa-se estes valores x11  e  x21 novamente no sistema  obtendo os valores  de x12  e  x22. Para K=2 tem-se:

    portanto

4. O próximo passo será  encontrar x13  e  x23. Para K=3 tem-se: 

    portanto

5. Para os demais x1k  e  x2k  procede-se da mesma forma.

Veja  um Procedimento para determinar  a solução  de um sistema pelo método iterativo de Gauss-Seidel  utilizando o programa Maple .  

Veja  uma Planilha do Excel  para determinar  a solução  de um sistema pelo método iterativo de Gauss-Seidel

                                      Ir  para o Topo

2.4.3 Condição Suficiente Convergência

É possível provar que sobre certas condições, para k tendendo a infinito, a seqüência de vetores X(k) converge para a solução exata das equações.

Uma condição suficiente  para que o método iterativo de Jacobi ou de Gauss-Seidel convirja, é que cada elemento diagonal principal da matriz de coeficientes satisfaça acondição:

Critérios para Parada

Os critérios de parada do processo de iteração são normalmente os seguintes:

O número de iterações excedeu um limite máximo predeterminado K. 

A diferença entre valores sucessivos de todos xi’s são menores que alguma tolerância predeterminada, ou seja Max{|xi(k+1) –xi(k)|} < erro , i=1, 2, ...n  erro= tolerância predeterminada.  Veja também: http://www.dmi.ubi.pt/~crocker/anumerica1/algoritmos/jacobi.html    

Ir  para o Topo

Exercícios 

A) Resolva cada um dos sistema de 1 a 7 utilizando os métodos iterativos de Jacobi,   Gauss-Seidel e encontre os resíduos até que

   

i=1,2     ou   k > 10 , onde k é o número da iteração.

                    

   

B) Dado o sistema

calcular o resíduo para cada caso

X0=( 2 ,  0,001);

X0=( 1000 ,  998); 

Resolva os sistemas  que seguem da forma que você achar conveniente 

       

Ir  para o Topo

Sumário

   Sair