Métodos Iterativos: Introdução e Gauss-Seidel

Metodos Iterativos Referˆencias Modelagem Numerica Sistemas de Equac oes Lineares O Metodo Iterativo de GaussSeidel Docente William R P Conti DCMar IMarUnifesp 2º semestre letivo Docente William R P Conti Metodos Iterativos Referˆencias Sumario desta Aula 1 Metodos Iterativos 2 Referˆencias Docente William R P Conti Metodos Iterativos Referˆencias Introduc ao Testes de Parada O Metodo Iterativo de GaussSeidel 1 Metodos Iterativos Introduc ao Testes de Parada O Metodo Iterativo de GaussSeidel 2 Referˆencias Docente William R P Conti Metodos Iterativos Referˆencias Introduc ao Testes de Parada O Metodo Iterativo de GaussSeidel Seja o sistema linear escrito como uma equac ao matricial da forma AX B em que A e uma matriz n n matriz dos coeficientes X e uma matriz n 1 vetor das variaveis e B e uma matriz n 1 vetor dos termos constantes Este sistema sera convertido de alguma forma num sistema do tipo X CX G em que C e uma matriz n n e G uma matriz n 1 vetor Observamos que φX CX G e uma func ao de iterac ao dada na forma matricial Partimos de X 0 vetor aproximac ao inicial e entao construımos consecutivamente os vetores X 1 φX 0 CX 0 G primeira aproximac ao X 2 φX 1 CX 1 G segunda aproximac ao X k φX k1 CX k1 G kesima aproximac ao E importante observar que se a sequˆencia X k e tal que lim k X k S entao S CS G isto e S e soluc ao do sistema linear AX B Docente William R P Conti At Testes de Parada tole atelty O Método Iterativo de GaussSeidel O processo iterativo é repetido até que o vetor X esteja suficientemente préximo do vetor X Sendo X1 x9 xf XM Xl x medimos a distancia entre x e X1 por d maxdl of a em que di x x1 Assim dada uma precisdo 0 0 vetor X sera escolhido como X solugdo aproximada da solugao exata se d Podemos também efetuar o teste da variagao relativa conforme é feito para a solugao refinada do Método de Eliminagao de Gauss Var maxvi vb Ley vy em que k k1 XTX k se x 40 yi k k1 j 0 se x 0x 1 se x oe xt 0 O processo iterativo sera interrompido quando Var e Como 0 processo iterativo pode nao convergir devemos estipular um numero maximo de iteragdes a serem feitas Metodos Iterativos Referˆencias Introduc ao Testes de Parada O Metodo Iterativo de GaussSeidel O Metodo Iterativo de GaussSeidel Da mesma forma que no Metodo de GaussJacobi no Metodo de GaussSeidel o sistema linear AX B e escrito na forma equivalente X CX G por separac ao da diagonal O processo iterativo consiste em dado X 0 aproximac ao inicial obter X 1 X 2 X k atraves da seguinte relac ao recursiva xk 1 1 a11 b1 a12xk1 2 a13xk1 3 a14xk1 4 a1nxk1 n xk 2 1 a22 b2 a21xk 1 a23xk1 3 a24xk1 4 a2nxk1 n xk 3 1 a33 b3 a31xk 1 a32xk 2 a34xk1 4 a3nxk1 n xk n 1 ann bn an1xk 1 an2xk 2 an3xk 3 ann1xk n1 Portanto nesse processo iterativo no momento de se calcular xk i usamos todos os valores xk 1 xk i1 que ja foram calculados e os valores xk1 i1 xk1 n restantes Docente William R P Conti Metodos Iterativos Referˆencias Introduc ao Testes de Parada O Metodo Iterativo de GaussSeidel Exemplo 1 Resolva o sistema linear 5x1 x2 x3 5 3x1 4x2 x3 6 3x1 3x2 6x3 0 pelo Metodo de GaussSeidel com X 0 0 0 0 e ε 005 Soluc ao Para esse problema a relac ao recursiva X k CX k1 G e dada por xk 1 1 5 5 xk1 2 xk1 3 xk 2 1 4 6 3xk 1 xk1 3 xk 3 1 6 3xk 1 3xk 2 sendo que X 0 0 0 0 x0 1 0 x0 2 0 x0 3 0 Docente William R P Conti oo Testes de Parada Referéncias 7 O Método Iterativo de GaussSeidel Para a primeira iteragao temos 1 x 55 x x 1 46 3x x 075 1 xs g 3 3x 0875 Calculemos a variagao relativa 1 75 0875 Var max 5 0875 1 075 0875 max11116 oo Testes de Parada tole atelty 7 O Método Iterativo de GaussSeidel Para a segunda iteragao temos 1 x2 g5 x xX 1025 1 x 46 3x x 095 1 x2 g 3 3x 09875 Calculemos a variagao relativa 2 1025 1 a7 09875 0875 Var max 4 1025 095 09875 max00244 02105 01139 02105 Testes de Parada tole atelty 7 O Método Iterativo de GaussSeidel Para a terceira iteragao temos 1 x9 g5 x x 10075 1 x8 g6 3x x 09912 1 x9 g 3x 3x 09993 Calculemos a variagao relativa Var 10075 1025 09912 095 09993 09875 max 10075 09912 09993 max00174 00416 00118 00416 e Entdo a solucao X do sistema linear dado com erro menor que 005 obtida pelo Método de GaussSeidel é 10075 XX9 ogg 09993 ae Testes de Parada tole atelty O Método Iterativo de GaussSeidel Enunciaremos agora um resultado que estabelece uma condigao suficiente para a convergéncia do Método de GaussSeidel Teorema Critério de Sassenfeld Seja o sistema linear AX B A ajnxn com aj 4 0 parai 12n Sejam 1 n 1 i1 n B Dolajl B dC lailG do lal 7 230 lan lai ir iz iei Se B maxf B2 Bn 1 entao o Método de GaussSeidel gera uma seqtiéncia X Ky convergente para a soluao do sistema dado independentemente da escolha da aproximagao inicial X 0 Além disso quanto menor for 8 mais rapida sera a convergéncia Métodos Iterativos Litt Testes de Parada O Método Iterativo de GaussSeidel Enunciaremos agora outro resultado que estabelece uma condicao suficiente para a convergéncia do Método de GaussSeidel Teorema Critério das Linhas Seja o sistema linear AX B A ajnxn com aj 0 parai12n Seja 1 n a lal 120 ai j1 ii Se a maxaya2an 1 entao o Método de GaussSeidel gera uma seqtiéncia X Ky convergente para a soluao do sistema dado independentemente da escolha da aproximagao inicial X 0 OOO Observagao Devemos chamar atengao ao fato de que se o critério das linhas for satisfeito automaticamente o critério de Sassenteld é satisfeito no entanto o critério de Sassenfeld pode ser satisfeito mesmo que o critério das linhas nao o seja a oo Testes de Parada tole atelty 7 O Método Iterativo de GaussSeidel Exemplo 2 Considere um sistema linear cuja matriz A seja dada por 10 2 1 A 1 5 1 2 3 10 Temos que oo 4 1 aa a max gs 10 5 10 max030405 05 1 de onde pelo critério das linhas temos garantia de convergéncia da seqtiéncia x gerada pelo Método de GaussSeidel oo Testes de Parada tole atelty 7 O Método Iterativo de GaussSeidel Exemplo 3 Considere o sistema linear Xi X 3 Se A 1 1 Xt 8X2 3 1 3 Nesse caso temos i i a max 4 max103 1 1 1 3 de modo que nao podemos usar 0 critério das linhas para tirar qualquer conclusao sobre a convergéncia da seqiiéncia X gerada pelo Método de GaussSeidel Por outro lado a relagao recursiva xX Cxk G neste caso escrita 1 WO Tea 39 Leg x pet 2 3 1 31 gera uma seqliéncia convergente para a solugdo exata S 15 15 oa 0 1 1 1 2 16666667 2 13333333 14444444 3 15555556 15185185 4 14814815 14938272 5 15061728 15020576 Metodos Iterativos Referˆencias Introduc ao Testes de Parada O Metodo Iterativo de GaussSeidel Exemplo 4 Considere o sistema linear x1 3x2 x3 2 5x1 2x2 2x3 3 6x2 8x3 6 A 1 3 1 5 2 2 0 6 8 A matriz A nao satisfaz o criterio das linhas Contudo se permutarmos a primeira equac ao com a segunda L1 L2 temos o sistema equivalente 5x1 2x2 2x3 3 x1 3x2 x3 2 6x2 8x3 6 A 5 2 2 1 3 1 0 6 8 e a matriz A satisfaz o criterio das linhas Assim e conveniente aplicarmos o Metodo de GaussSeidel a esta nova disposic ao do sistema pois desta forma a convergˆencia esta assegurada Deste exemplo aprendemos que sempre que o criterio das linhas nao for satisfeito devemos tentar uma permutac ao de linhas de forma a obtermos uma disposic ao para a qual a matriz dos coeficientes satisfaca o criterio das linhas No entanto nem sempre e possıvel obter tal disposic ao como facilmente verificamos com o sistema linear do exemplo 3 Docente William R P Conti Metodos Iterativos Referˆencias Introduc ao Testes de Parada O Metodo Iterativo de GaussSeidel Como os criterios das linhas e de Sassenfeld sao apenas condic oes suficientes para a convergˆencia o Metodo de GaussSeidel pode ser utilizado para resolver sistemas lineares que nao satisfacam a nenhum destes criterios Entretanto nestes casos deve ser feita uma analise cuidadosa da sequˆencia de aproximac oes obtida ja que o Metodo de GaussSeidel nao detecta se o sistema e determinado ou nao Veremos nos proximos trˆes exemplos a aplicac ao do Metodo de GaussSeidel a sistemas lineares com determinante nulo Os dois primeiros sao sistemas indeterminados e o terceiro um sistema impossıvel Docente William R P Conti Metodos Iterativos Referˆencias Introduc ao Testes de Parada O Metodo Iterativo de GaussSeidel Exemplo 5 Resolva o sistema linear abaixo pelo Metodo de GaussSeidel x1 x2 x3 1 2x1 2x2 2x3 2 5x1 5x2 5x3 5 xk 1 1 xk1 2 xk1 3 xk 2 1 2 2 2xk 1 2xk1 3 xk 3 1 5 5 5xk 1 5xk 2 Escolhendo X 0 0 0 0 temos a seguinte sequˆencia de aproximac oes k xk 1 xk 2 xk 3 Var k 0 0 0 0 1 1 0 0 1 2 1 0 0 0 Assim X 1 1 0 0 e uma soluc ao exata do sistema Docente William R P Conti Metodos Iterativos Referˆencias Introduc ao Testes de Parada O Metodo Iterativo de GaussSeidel Escolhendo X 0 1 1 1 temos a seguinte sequˆencia de aproximac oes k xk 1 xk 2 xk 3 Var k 0 1 1 1 1 1 1 1 2 2 1 1 1 0 Assim X 1 1 1 1 e uma soluc ao exata do sistema Isto se deve ao fato das equac oes corresponderem a trˆes planos coincidentes Docente William R P Conti Metodos Iterativos Referˆencias Introduc ao Testes de Parada O Metodo Iterativo de GaussSeidel Exemplo 6 Resolva o sistema linear abaixo pelo Metodo de GaussSeidel x1 x2 x3 1 2x1 2x2 2x3 2 2x1 x2 x3 0 xk 1 1 xk1 2 xk1 3 xk 2 1 2 2 2xk 1 2xk1 3 xk 3 2xk 1 xk 2 Escolhendo X 0 0 0 0 temos a seguinte sequˆencia de aproximac oes k xk 1 xk 2 xk 3 Var k 0 0 0 0 1 1 0 2 1 2 3 0 6 23 3 7 0 14 47 4 15 0 30 815 5 31 0 62 1631 n 2n 1 0 2 2n1 2n12n 1 Docente William R P Conti Metodos Iterativos Referˆencias Introduc ao Testes de Parada O Metodo Iterativo de GaussSeidel Escolhendo X 0 0 2 0 temos a seguinte sequˆencia de aproximac oes k xk 1 xk 2 xk 3 Var k 0 0 2 0 1 1 2 0 1 2 1 2 0 0 Assim X 1 1 2 0 e uma soluc ao exata do sistema Escolhendo X 0 0 1 1 temos a seguinte sequˆencia de aproximac oes k xk 1 xk 2 xk 3 Var k 0 0 1 1 1 1 1 1 1 2 1 1 1 0 Assim X 1 1 1 1 e uma soluc ao exata do sistema Para este sistema a intersecc ao dos trˆes planos e dada pela reta que passa pelos pontos 1 2 0 e 1 1 1 Docente William R P Conti Metodos Iterativos Referˆencias Introduc ao Testes de Parada O Metodo Iterativo de GaussSeidel Exemplo 7 Resolva o sistema linear abaixo pelo Metodo de GaussSeidel x1 x2 x3 1 2x1 2x2 2x3 2 x1 x2 x3 2 xk 1 1 xk1 2 xk1 3 xk 2 1 2 2 2xk 1 2xk1 3 xk 3 2 xk 1 xk 2 Escolhendo X 0 0 0 0 temos a seguinte sequˆencia de aproximac oes k xk 1 xk 2 xk 3 Var k 0 0 0 0 1 1 0 1 1 2 0 0 2 1 3 1 0 3 1 4 2 0 4 12 5 3 0 5 13 n n 2 0 n 1n 2 Docente William R P Conti Metodos Iterativos Referˆencias 1 Metodos Iterativos 2 Referˆencias Docente William R P Conti Metodos Iterativos Referˆencias Referˆencias 1 M A G Ruggiero V L R Lopes Calculo Numerico Aspectos Teoricos e Computacionais 2ª edic ao Sao Paulo Makron 1997 2 A F P C Humes I S H Melo L K Yoshida W T Martins Noc oes de Calculo Numerico Sao Paulo McGrawHill do Brasil 1984 v 1 201 p 3 J Kiusalaas Numerical Methods in Engineering with Python 3 Cambridge University Press 2013 4 C Moler Numerical Computing with MATLAB A Web edition esta disponıvel no site httpwwwmathworkscommolerchaptershtml Docente William R P Conti