ComputacaoCientifica Cap2 Parte 2

Prévia do material em texto

2.3.9 Métodos Iterativos para a Solução de Sistemas Lineares
Seja os Sistema Linear 
 onde:
 matriz de coeficientes 
 vetor de variáveis 
 vetor independente (constantes) 
Idéia Geral dos Métodos Iterativos
Converter o sistema de equações 
 em um processo iterativo 
, onde:
 matriz com dimensões 
 vetor com dimensões 
 função de iteração matricial
Esquema Iterativo Proposto
Partindo de uma vetor aproximação inicial 
, constrói-se uma seqüência iterativa de vetores:
Forma Geral
Observação
Se a sequência de aproximação 
, 
, 
, ......, 
 é tal que 
, então 
 é a solução do sistema 
.
 
Teste de Parada
Como em todos os processos iterativos, necessita-se de um critério para a parada do processo. 
Máximo desvio absoluto:
Máximo desvio relativo:
Desta forma, dada uma precisão 
, o vetor 
 será escolhido como solução aproximada da solução exata, se 
, ou dependendo da escolha, 
.
Método Iterativo de Gauss-Jacobi
Considere o sistema linear:
Supondo 
, isola-se o vetor 
 mediante a separação pela diagonal da matriz de coeficientes.
Assim, tem-se o sistema iterativo 
, onde:
Dado uma aproximação inicial 
, o Método de Gauss-Jacobi consiste em obter uma seqüência 
, 
, 
, ......, 
, por meio da relação recursiva: 
 
Observe que o processo iterativo utiliza somente estimativas da iteração anterior.
Exemplo: Resolver o sistema de equações lineares, pelo Método de Gauss-Jacobi com solução inicial 
 e tolerância 
.
Separando-se os elementos diagonais, tem-se:
Solução para k=0 
Cálculo de 
:
Para k=1:
Para k=2:
 é solução com erro menor que 0,05.
Condições Suficientes para a Convergência do Método de Gauss-Jacobi
Teorema
Seja o sistema linear
 e seja:
Se 
, então o método G-J gera uma seqüência 
 convergente para a solução do sistema dado, independentemente da escolha da aproximação inicial 
.
Observe que esta é uma condição suficiente, se for satisfeita o método converge, entretanto se não for satisfeita nada se pode afirmar.
Exemplo 1:
Seja a matriz do exemplo dado anteriormente:
Tem-se a convergência garantida para qualquer vetor inicial.
Exemplo 2:
Seja o sistema de equações lineares:
 
As condições de convergência do teorema não são satisfeitas, entretanto o Método de Gauss-Jacobi gera uma seqüência convergente para a solução exata 
. Se as condições de suficiência não são satisfeitas, não significa que o método não possa convergir.
Exemplo 3:
Considere o sistema linear:
As condições do teorema não são satisfeitas. Uma solução possível é permutar as equações. Seja no exemplo permutar a primeira equação com a segunda equação:
As condições passam a ser satisfeitas e a convergência é garantida para qualquer vetor inicial. Este tipo de procedimento nem sempre é possível.
Fórmula Matricial do Método Gauss-Jacobi
Decompõe-se a matriz de coeficientes 
 em:
Onde:
L – Matriz Triangular Inferior
D – Matriz Diagonal
U – Matriz Triangular Superior
Método Iterativo de Gauss-Seidel
Assim como no Método de Gauss-Jacobi o sistema linear 
 é escrito na forma equivalente:
Como no Método Gauss-Jacobi, é realizada uma separação diagonal, e o processo iterativo de atualização é seqüencial, componente por componente. A diferença é que, no momento de realizar-se a atualização das componentes do vetor numa determinada iteração, a formulação utiliza as componentes da iteração já atualizadas na iteração atual, com as restantes não atualizadas da iteração anterior. Por exemplo, ao se calcular a componente 
 da iteração (k+1), utiliza-se no cálculo as componentes já atualizadas 
 com as componentes ainda não atualizadas da iteração anterior 
.
Exemplo: Resolver o sistema linear utilizando o Método Iterativo de Gauss-Seidel, com 
 e tolerância 
.
O processo iterativo é dado por:
Para k=0 e 
Cálculo de 
:
Para k=1 e 
:
Para k=2 e 
:
 é solução com erro menor que 0,05.
Fórmula Matricial do Método Gauss-Seidel
Decompõe-se a matriz de coeficientes 
 em:
Onde:
L – Matriz Triangular Inferior
D – Matriz Diagonal
U – Matriz Triangular Superior
Interpretação Geométrica do Caso 
Considere o Sistema Linear:
O esquema iterativo utilizando o Método de Gauss-Seidel é dado por:
Para k=0 e 
:
Para k=1 e 
:
Para k=2 e 
:
A solução exata é dada por: 
.
Esse processo iterativo até à convergência pode ser interpretado geométricamente num grafico com a componente 
 na abscissa e a componente 
na ordenada.
Observação 1: Verifica-se pelo gráfico acima que a seqüência 
, 
, 
, ......, 
 está convergindo para a solução exata 
.
Observação 2: A sequência gerado pelo Método de Gauss-Seidel depende fortemente da posição das equações. Esta observação pode ser melhor entendida modificando a ordem das equações do exemplo anterior.
Considere o mesmo Sistema Linear anterior, porém modificando a ordem das equações:
O esquema iterativo utilizando o Método de Gauss-Seidel é dado por:
Para k=0 e 
:
Para k=1 e 
:
Estudo da Convergência do Método de Gauss-Seidel
Existem dois critérios de suficiência para a convergência do Método de Gauss-Seidel. O critério de linhas e o critério de Sassenfeld. O critério de linhas é o mesmo da Método de Gauss-Jacobi.
Critério de Linhas
Seja o sistema linear
, com A dimensão 
 e seja:
Se 
, então o método Gauss-Seidel gera uma seqüência 
 convergente para a solução do sistema dado, independentemente da escolha da aproximação inicial 
.
A matriz que satisfizer o critério de linhas é chamada de diagonal dominante estrita.
Critério de Sassenfeld
Seja o sistema linear
, com A dimensão 
 e seja:
e para 
:
Define-se 
.
Se 
, então o Método de Gauss-Seidel gera uma sequência convergente para a solução do sistema, qualquer que seja o vetor inicial. Além disso, quanto menor for o valor de 
 mais rápida é a convergência.
Exemplo: Verificar as condições de convergência do Método de Gauss-Seidel no sistema abaixo:
Critério de Linhas
 não satisfaz.
Critério de Sassenfeld
 não satisfaz.
Como a convergência do Método de Gauss-Seidel é fortemente dependente da posição das equações, pode-se trocar a posição das equações.
Tentativa 1: Troca-se a primeira equação pela terceira equação.
Critério de Linhas
 não satisfaz.
Critério de Sassenfeld
 não satisfaz.
Tentativa 2: Troca-se a primeira coluna pela terceira coluna na equação anterior.
Critério de Linhas
 satisfaz.
 não satisfaz.
Critério de Sassenfeld
 satisfaz.
 satisfaz.
 satisfaz.
Com a última modificação o sistema passa a ser convergente para qualquer vetor inicial. Modificações desse tipo são puramente acadêmicas e são difíceis de serem realizadas em sistemas reais. Principalmente pelas dimensões dos problemas, resultando num grande esforço computacional, e das incertezas quanto a sua eficiência. 
Exemplo : Verifique a convergência do sistema abaixo pelo critério de linhas e Sassenfeld.
Critério de Linhas
 Não satisfaz
Critério de Sassenfeld
 Satisfaz
Exemplo : Verifique a convergência do sistema abaixo pelo critério de linhas e Sassenfeld.
 
Método da Sobrerelaxação Sucessiva
 - Utilizado para aumentar a velocidade de convergência.- Utilizado em sistemas com dificuldades de convergência pelo Método de gauss Seidel.
Condições Necessária e Suficiente para Convergência do Método de Gauss-Jacobi e Gauss-Seidel
Teorema
Seja 
 e 
é não singular. Se M é não-singular e o raio espectral de 
 satisfaça
, então o processo iterativo definido por 
 converge para 
 para qualquer vetor 
.
Para o Método de Gauss-Jacobi:
Para o Método de Gauss-Seildel:
Comparação dos Métodos de Solução de Sistemas Lineares 
Métodos Diretos:
Processos finitos (convergência para qualquer sistema não-singular);
Apresentam problemas com erros de arredondamento;
Utiliza-se técnicas de pivoteamento para amenizar os problemas de arredondamento;
O processo de triangularização destrói a esparsidade da matriz de coeficientes. Técnicas de Esparsidade são utilizadas para amenizar o enchimento da matriz.
Redução de esforço computacional é conseguido em soluções para vetores independentes adicionais com a matriz de coeficientes mantida constante, com a utilização da fatoração LU;
Para matrizes cheias a solução requer 
operações sem considerar o pivoteamento.
Métodos Iterativos:
Provavelmente mais eficientes para sistemas de grande porte, principalmente com a utilização de computação de alto desempenho (vetorial e paralela);
Tem convergência assegurada apenas sob certas condições;
Conserva a esparsidade da matriz de coeficientes;
Os métodos de G-J e G-S requerem 
operações por iterações;
Poucas vantagens adicionais são conseguidas em soluções para vetores independentes adicionais com a matriz de coeficientes mantida constante, como no caso da fatoração LU;
Carregam menos erros de arredondamento no processo, tendo em vista que a convergência uma vez assegurada independe da aproximação inicial. Somente os erros da última iteração afetam a solução.
2.4 Número de condicionamento de uma matriz
 Os elementos da matriz de coeficientes e do vetor independente de um sistema de equações lineares são na grande maioria das aplicações inexatos. Esta falta de exatidão pode ser originada porque os dados são resultantes de experimentos ou computados através de operações que carregam erros de arredondamento, ou mesmo do próprio armazenamento dos elementos em uma aritmética finita. A questão é quando a perturbação introduzida em elementos do sistema podem alterar a resposta.
 O algoritmo de eliminação de Gauss com pivoteamento pode ser considerado numericamente estável, o que pode-se assegurar que, para um sistema bem comportado, produzirá pequenos resíduos, mesmo para pequenas perturbações nos elementos do sistema. Portanto, alterações na resposta do sistema está associada ao comportamento do sistema. Este comportamento é medido pelo número de condição (condicionamento) da matriz.
Para entender o número de condicionamento de uma matriz é preciso relembrar o conceito de norma de vetores e matrizes.
Norma de vetores
 A norma de vetores em 
 é uma função || . || := R
�� EMBED Equation.3 que satisfaz
Embora existem uma infinidade de normas, as mais utilizadas na prática são:
Norma 1: 
Norma 2: 
Norma 
Normas de matrizes
 A norma de uma matriz é definida de forma análogo a norma de vetores. A norma de uma matriz em 
 é uma função || . || 
 que satisfaz:
Propriedade Adicional 
Sempre que o produto A .B é definido. 
OBS: Uma norma de vetor || . ||v é consistente com uma norma de matriz || . ||M se :
As principais normas utilizadas são:
Condição de uma matriz não-singular
 
Seja o sistema linear:
Suponha que o vetor independente 
 sja alterado para 
 e a matriz A permanece inalterada. A solução exata do problema alterado é dado por: 
Como 
, pode-se obter um limite para 
 ;
A relação 
 implica em :
Multiplicando as duas relações anteriores chega-se a relação:
Se perturbarmos a matriz A enquanto 
 é mantido fixo tem-se a solução: 
por um processo similar, chega-se a expressão para o erro relativo:
A quantidade 
 reflete a máxima mudança relativa possível na solução exata para um sistema linear com dados perturbados, portanto:
 
Das relações anteriores pode-se chegar a: 
 Estas relações mostram que, se a mudança relativa é muito grande para uma pequena perturbação em A ou 
, nós sabemos que A é mal condicionada.
Propriedades:
A norma da matriz identidade, para qualquer norma, vale 1. 
Como 
 e 
 conclui-se que 
.
Se a matriz A for multiplicada por um escalar 
, então 
.
Se D for uma matriz diagonal, então 
.
Se A for não-singular e simétrica 
. Se A for não-simétrica 
.
Se A for não-singular , 
, onde 
é o mínimo valor singular e 
é o máximo valor singular.
 
 onde 
.
Observação 1: O
 pode ser uma medida mais eficaz para a verificação da singularidade de uma matriz, que o determinante. Como exemplo, seja uma matriz diagonal de ordem 
, com todos elementos igual a 0,1. O determinante da matriz é 
, que é um número pequeno e pode ser arredondado para zero em computadores digitais. Já a número de condição da matriz é igual a 1.
Observação 2: O pré-condicionamento de uma matriz está associado na redução do raio espectral da mesma.. 
A matriz A é pré-multiplicada por uma matriz P de pré-condicionamento, com o objetivo de que a nova matriz PA tenha uma redução do raio espectral o quê implica na redução do condicionamento.
O mal condicionamento de uma matriz está associado à proximidade da singularidade da matriz. 
Exemplo 2x2.
 Matriz não-singular
 Matriz singular
 Matriz próxima da singularidade
Exemplo
A matriz A é armazenada em uma máquina com unidade de arrendondamento 
.
Para qualquer norma:
Se o algoritmo de solução for numericamente estável:
Condicionamento de Matrizes de Redes Elétricas
Análise Nodal
 A equação matricial de desempenho de uma rede linear na formulação nodal é dada por:
 
onde I – é o vetor das injeções nodais de corrente
 E – vetor das tensões nodais em relação ao nó de referência.
 Y – matriz de admitância nodal
Em sistemas de potência geralmente o nó de referência é o nó terra, sendo os demais nós as barras do sistema:
 IBarra = YBarra ZBarra
Na sua forma inversa tem-se:
 EBarra = YBarra-1 IBarra
 YBarra 
 esparsa
ZBarra 
Cheia
YBarra-1 
ZBarra
 Na ausência de acoplamento mútuo, a matriz YBarra é montada com grande facilidade.
 Elementos diagonais 
 barra vizinha a 
 
admitância da linha i-k
= 
Exemplo
 1 2
 I1 1 - j2 E
 
 -j4
 1 2 – j4
 4 3
 I4 
 
I3
 J1/2 -JCondicionamento da matriz YBarra
 Sistema sem ligação à terra
 Yb
 11
 Ya Yc
YBarra = 
Matriz é singular (colunas combinação linear)
Mau condicionamento: admitância fraca entre a rede e o nó de referência
Bom condicionamento: forte conexão com o nó de referência.
Possibilidades de Mau Condicionamento
Conexão fraca com o nó de referência
Junção entre partes com admitâncias muito grandes e pequenas (perda dominância diagonal, aumento do raio espectral)
Capacitância em série ou em derivação do sistema, enfrequecendo o elemento diagonal.
Melhoria do Condicionamento adotando como referência uma barra do sistema.
 Se a tensão de uma barra for considerada conhecida, pode-se reduzir o n° de equações e variáveis de uma unidade.
 I = Y E referência ao nó terra
Pode-se eliminar uma das equações, já que há apenas n-1 incognitas.
 
 obtida de Y eliminando-se a linha e coluna correspondentes à nova barra de referência. Para obter-se bom condicionamento de 
 escolhe-se como referência uma barra com forte conexão à rede restante.
2.5 Correção Iterativa
Para sistemas de equações lineares que não se conhece a priori se é bem condicionado é importante verificar se a solução é suficientemente exata; e se sua exatidão não for suficiente, pode-se melhorá-la.
Seja o sistema Linear:
A exatidão da solução desse sistema pode ser verificada pelo resíduo:
 
 
 solução computada.
Se os elementos de 
 são pequenos, se comparados aos elementos de 
, normalmente assume-se que a solução é suficientemente exata.
Se a solução não for suficientemente exata, pode-se repetir a solução em dupla precisão ( o que normalmente não acrescente grandes beneficios, principalmente se a matriz de coeficientes for mal condicionada). 
Um procedimento que pode ser adotado para melhorar a exatidão é a correção iterativa, conforme a sequência:
 
Chega-se a um novo sistema linear:
Resolvendo-se esse sistema, uma correção da variável é obtida:
Esse processo pode ser repetido até que se chegue a convergência.
Observações:
 A decomposição da matriz é realizada uma única vez
 Em razão do mal condicionamento do sistema, os arredondamentos de elementos da matriz de coeficientes A podem causar grandes erros na solução, é muito importante que a matriz de coeficientes seja construída em dupla precisão e armazenada em dupla precisão. É também necessário computar o resíduo em dupla precisão, de forma que erros significativos não sejam introduzidos na computação.
É possível que o método não convirja, se a amplificação do erro for muito grande.
 
Observe que: 
Uma saída deve ser prevista a implementação do processo no caso em que 
2.6 Eliminação por Blocos
 Aproveitar estrutura esparsa de matrizes por blocos.
Fluxo de Potência ótimo (Mesma estrutura da matriz admitância, se for feito por blocos)
Fluxo de Potência via Newton Raphson.
 
 são blocos diagonais quadrados de ordem 
 
A maneira mais simples é realizar através de computação recursiva:
 
multiplicadores: 
Explicitando.
A primeira linha de blocos de U é a primeira linha de blocos de A.
A primeira coluna de blocos de L excluindo o bloco identidade diagonal é 
.
Os blocos restantes da decomposição são obtidos por 
A decomposição escalar e a decomposição por blocos normalmente não são iguais.
O número de operações é o mesmo da eliminação escalar: 
Algoritmo
� EMBED Equation.3 ���
� EMBED Equation.3 ���
Saída com Solução Satisfatória
� EMBED Equation.3 ���
Saída com Solução Insatisfatória
� EMBED Equation.3 ���
Teste � EMBED Equation.3 ���
Solucione o Sistema � EMBED Equation.3 ��� (precisão simples)
Corrija a Solução:
� EMBED Equation.3 ���(precisão dupla)
� EMBED Equation.3 ��� (precisão dupla)
� EMBED Equation.3 ���
Copie A em precisão simples
Decomponha a Matriz A em fatores LU
Faça � EMBED Equation.3 ���, � EMBED Equation.3 ��� (precisão dupla), � EMBED Equation.3 ��� (precisão simples) e � EMBED Equation.3 ���
Entre com � EMBED Equation.3 ��� e � EMBED Equation.3 ��� em dupla precisão
Início
~
-J4 E
-J4
EQUIVALENTE NORTON
� EMBED Equation.3 ���
1
3
�PAGE �
�PAGE �26�
_1090051239.unknown
_1111124252.unknown
_1111127379.unknown
_1111405001.unknown
_1111416304.unknown
_1111819731.unknown
_1118493257.unknown
_1118562097.unknown
_1118562875.unknown
_1118563698.unknown
_1118563945.unknown
_1118564670.unknown
_1118564705.unknown
_1118564949.unknown
_1118564550.unknown
_1118563738.unknown
_1118563212.unknown
_1118563625.unknown
_1118563064.unknown
_1118562492.unknown
_1118562658.unknown
_1118562430.unknown
_1118558975.unknown
_1118559486.unknown
_1118559611.unknown
_1118559895.unknown
_1118559148.unknown
_1118493543.unknown
_1118493595.unknown
_1118493414.unknown
_1118491619.unknown
_1118492685.unknown
_1118492829.unknown
_1118493073.unknown
_1118492903.unknown
_1118492741.unknown
_1118492435.unknown
_1118492472.unknown
_1118492552.unknown
_1118492444.unknown
_1118492164.unknown
_1118492174.unknown
_1118491746.unknown
_1113134326.unknown
_1113134810.unknown
_1113134823.unknown
_1113134789.unknown
_1111820094.unknown
_1111820871.unknown
_1113134311.unknown
_1111820672.unknown
_1111819867.unknown
_1111818450.unknown
_1111818892.unknown
_1111819186.unknown
_1111819380.unknown
_1111819682.unknown
_1111819137.unknown
_1111818794.unknown
_1111818847.unknown
_1111818695.unknown
_1111817704.unknown
_1111818252.unknown
_1111818390.unknown
_1111818187.unknown
_1111817501.unknown
_1111817587.unknown
_1111416404.unknown
_1111416907.unknown
_1111413643.unknown
_1111414921.unknown
_1111416020.unknown
_1111416226.unknown
_1111416259.unknown
_1111416178.unknown
_1111415938.unknown
_1111415964.unknown
_1111415161.unknown
_1111415177.unknown
_1111414206.unknown
_1111414493.unknown
_1111414824.unknown
_1111414315.unknown
_1111413766.unknown
_1111414165.unknown
_1111413662.unknown
_1111408429.unknown
_1111410502.unknown
_1111412473.unknown
_1111413609.unknown
_1111412470.unknown
_1111412471.unknown
_1111410710.unknown
_1111408541.unknown
_1111408557.unknown
_1111407415.unknown
_1111408144.unknown
_1111408401.unknown
_1111408409.unknown
_1111408383.unknown
_1111408021.unknown
_1111405036.unknown
_1111405666.unknown
_1111405027.unknown
_1111130367.unknown
_1111222282.unknown
_1111402988.unknown
_1111403281.unknown
_1111404521.unknown
_1111404578.unknown
_1111403772.unknown
_1111404040.unknown
_1111403213.unknown
_1111401543.unknown
_1111402133.unknown
_1111402514.unknown
_1111402619.unknown
_1111402213.unknown
_1111401604.unknown
_1111131668.unknown
_1111131900.unknown
_1111132265.unknown
_1111221188.unknown
_1111221198.unknown
_1111221999.unknown
_1111132550.unknown
_1111132173.unknown
_1111131736.unknown
_1111130781.unknown
_1111131053.unknown
_1111131179.unknown
_1111131253.unknown
_1111131096.unknown
_1111130774.unknown
_1111130558.unknown
_1111130629.unknown_1111130441.unknown
_1111128634.unknown
_1111129832.unknown
_1111129911.unknown
_1111130145.unknown
_1111130046.unknown
_1111129885.unknown
_1111129153.unknown
_1111129269.unknown
_1111128789.unknown
_1111128948.unknown
_1111127668.unknown
_1111128068.unknown
_1111128455.unknown
_1111128022.unknown
_1111127564.unknown
_1111127623.unknown
_1111127415.unknown
_1111124697.unknown
_1111125844.unknown
_1111126367.unknown
_1111126746.unknown
_1111126786.unknown
_1111126558.unknown
_1111125892.unknown
_1111125281.unknown
_1111125601.unknown
_1111125615.unknown
_1111125633.unknown
_1111125371.unknown
_1111125351.unknown
_1111125210.unknown
_1111125244.unknown
_1111125136.unknown
_1111124728.unknown
_1111125109.unknown
_1111124343.unknown
_1111124380.unknown
_1111124516.unknown
_1111124630.unknown
_1111124388.unknown
_1111124372.unknown
_1111124304.unknown
_1111124328.unknown
_1090052253.unknown
_1090053808.unknown
_1090054707.unknown
_1090055185.unknown
_1090056743.unknown
_1090056939.unknown
_1111123997.unknown
_1090056882.unknown
_1090055685.unknown
_1090054789.unknown
_1090054863.unknown
_1090054639.unknown
_1090054679.unknown
_1090054369.unknown
_1090053120.unknown
_1090053669.unknown
_1090053704.unknown
_1090053620.unknown
_1090053168.unknown
_1090052841.unknown
_1090053016.unknown
_1090052810.unknown
_1090051902.unknown
_1090052181.unknown
_1090052203.unknown
_1090052130.unknown
_1090051550.unknown
_1090051795.unknown
_1090051263.unknown
_1057649086.unknown
_1057656325.unknown
_1057671842.unknown
_1058872140.unknown
_1058872916.unknown
_1058873337.unknown
_1058873478.unknown
_1058872643.unknown
_1057733807.unknown
_1057734729.unknown
_1057734882.unknown
_1057737317.unknown
_1057733857.unknown
_1057671957.unknown
_1057665531.unknown
_1057671303.unknown
_1057671658.unknown
_1057669979.unknown
_1057657434.unknown
_1057657590.unknown
_1057656354.unknown
_1057656846.unknown
_1057652442.unknown
_1057655142.unknown
_1057655784.unknown
_1057653366.unknown
_1057649333.unknown
_1057650601.unknown
_1057649131.unknown
_1057580385.unknown
_1057647639.unknown
_1057648167.unknown
_1057648855.unknown
_1057647959.unknown
_1057580678.unknown
_1057647581.unknown
_1057580481.unknown
_1057576795.unknown
_1057577676.unknown
_1057580310.unknown
_1057577043.unknown
_1057576542.unknown
_1057576568.unknown
_1057576449.unknown