Sistemas Lineares

2 SISTEMAS DE EQUAÇÕES LINEARES

2.1 Introdução

A solução de sistemas lineares é uma ferramenta matemática muito importante na engenharia. Normalmente os problemas não-lineares são solucionados por ferramentas lineares.

As fontes mais comuns de problemas de equações lineares algébricas aplicados à engenharia incluem:

a) aproximação de equações diferenciais ou integrais contínuas através de sistemas discretas e finitos;

b) linearização local de sistemas de equações não lineares;

c) ajuste de curvas em dados.

2.2 Representação do Sistema Linear

Um sistema linear é um conjunto de n equações lineares do tipo:

Este sistema pode ser representado através de uma representação matricial da forma:

x = b

onde:

A – matriz de coeficientes de ordem

x – vetor de incógnitas de ordem

b – vetor independente de ordem

Os tipos de solução do sistema dependem da matriz A:

A não-singular

A singular

2.3 Métodos de Solução

2.3.1 Métodos Diretos – Fornece solução “exata” após um número finito de operações. Solução assegurada para matriz de coeficientes não-singular.

2.3.2 Métodos Iterativos – Processo de aproximação iterativa da solução. A convergência é assegurada sob certas condições.

2.3.3 Regra Cramer

A solução de cada componente do vetor de incógnitas é dado pela relação de dois determinantes:

onde:

= determinante da matriz A

= determinante da matriz A com a iésima coluna substituída pelo vetor independente b.

Exemplo da ordem de grandeza do tempo de solução para um sistema de ordem 20.

Operações necessárias:

a) Cálculo de 21 determinantes, cada um de ordem 20.

O determinante de uma matriz é definido como uma soma de termos ...... onde o símbolo – representa subscritos de permutações de 1 a n. No exemplo a soma tem 20! termos cada qual requerendo 19 multiplicações. Assim, a soluções do sistema requer 21 x 20! x 19 multiplicações, além de um número 21 x 20! de somas que será desconsiderado.

Seja um computador com capacidade de 2000 Mflops.

2.000.000.000 operações por segundo.

Tempo de Solução:

= 15604,55 anos

Strang 1993 - “If world be cvazy to solve equation this way”.

O método de Cramer também possui pouca estabilidade numérica. [Highan]. (erros de arredondamento excessivos). (forward estability)

2.3.4 Inversão da Matriz A

A solução do sistema linear pode ser dada por:

x= b

Entretanto, na grande maioria de problemas práticos é desnecessário e mesmo desaconselháveis o cálculo da matriz inversa .

Veja o que acontece neste exemplo simples com uma equação:

A melhor maneira de obter a solução é por divisão,

O uso da matriz inversa levaria a (precisão 6 dígitos) :

b

A inversa requer mais aritmética (uma divisão e uma multiplicação em vez de uma só divisão), além de produzir uma resposta menos exata.

2.3.5 Eliminação de Gauss

Composta de duas etapas básicas:

1. Eliminação direta de variáveis

2. Substituição inversa

=

Eliminação de variáveis (triangularizações)

U =

Números de operações necessárias para obter soluções, considerando a matriz A cheia.

a) Solução por Inversão

x= b

1. Obtenção da matriz inversa utilizando um algoritmo eficiente de matriz cheia

2. Obtenção de x pelo produto de com b

b) Solução por eliminação de Grauss

1. Redução triângulos

U x = b

= ~ operações de produção

2. Substituição Inversa.

operações de produto

Exemplo Numérico

=

Estágio 1

pivô

Multiplicadores

=

Estágio 2

Pivô

Multiplicador

=

Substituição Inversa

. –8

2.3.6 Estratégia de Pivoteamento

(a) Evitar pivôs nulos

(b) Evitar pivôs próximos de zero (multiplicadores elevado, ampliação de erros de arredondamento)

Exemplo:

Usando aritmética de 3 dígitos

=

pivô 0.2 x 10

multiplicadores

=

Com pivoteamento

=

pivô mult. =

=

Solução de sistema

Resumindo: Pivoteamento parcial consiste em adotar como pivô no passo (K) da eliminação de Grauss o maior elemento (em valor absoluto) na parte não reduzido da coluna. As linhas contendo esses elementos devem ser intercambiadas.

OBS: Seja a solução calculada de Ax=b e x a solução exata (teórica). Como os elementos de x não são números representados numa aritmética de ponto flutuante, deve haver diferença com relação a . Normalmente utiliza-se as seguintes medidas para auferir esta diferença.

Erro: e = x - x

Resíduo: r = || b – A x || (dependente de escala, multiplicando-se A e b por uma constante , o resíduo também vai ser multiplidado por )

Resíduo relativo:

Da teoria de matrizes sabemos que, sendo A não singular e se uma medida acima é nula, a outra também o será, mas ambos não são necessariamente igualmente pequeno.

2.3.7 Fatoração LU

Ax = b A = LU

L – triangular inferior

U – triangular superior

Vamos observar o exemplo introdutório

Observe que a matriz pode ser obtida de pré-multiplicado-a por uma matriz conveniente, no caso:

=

Da mesma forma a matriz é obtida pré-multiplicando-a por:

A matriz L é uma matriz triangular inferior, pois é resultante do produto de matrizes triangulares inferiores elementares.

A decomposição LU não é única..

Seja D uma matriz diagonal não-singular qualquer, então:

= LD é triangular inferior

= é triangular superior

A = LU = L DD U =

De modo que também é uma decomposição LU. Isto sugere a possibilidade de se normalizar as decomposições LU.

Seja a transformação A= LDU

Onde: L é triangular inferior unitário (diagonal)

D é diagonal

U triangular superior unitária (diagonal)

Pode-se mostrar que a decomposição LDU de uma matriz A é única, se suas submatrizes principais guias são todas não-singulares.

isto garante pivôs não nulos.

=

Produto de 2 matrizes triang. sup. unitário resulta matriz triang sup. unitário. Isto força o segundo membro da equação a ser diagonal, já que é triangular inferior Identidade.

da mesma forma pode-se chegar

Diferentes decomposições LU:

onde: é triângular superior unitário – Decomposição de Crout

onde: L é triângular superior unitário – Decomposição de Doolittle

Se A for simétrica:

Algoritmo para Decomposição de Crout

U é triangular superior com diagonal unitária

Como

ou seja a primeira coluna da matriz A é igual a primeira coluna da matriz L.

Além disso:

Assim determinamos 1° linha de U.

Suponha que as primeiras (p –1) colunas de L e as primeiras (p – 1) linhas de U tenham sido calculadas e como .

portanto a coluna de L é dada por:

Da mesma forma

onde

Observe que não há necessidade de calcular-se para j = p, pois, .

OBS: Pode-se verificar que, após ter sido utilizado para calcular , ele não é mais utilizado, assim, os elementos não nulos de L e U podem ser escritos sobre os elementos correspondentes de A.

Algoritmo para Redução de Crout: para p = 1, 2,.....,n:

1.

2.

- Os elementos são pivôs na redução de Grauss e são 0, se as submatrizes principais guias de A são não – singulares.

- Produtos internos devem ser acumulados em precisão dupla.

A utilização de pivôs pequenos podem provocar erros de arredondamento que contaminam significativamente a solução. Uma solução é utilizar o pivoteamento parcial, isto é, fazer uma pesquisa na coluna do pivô de forma a encontrar o elemento de maior valor absoluto. O elemento com maior valor absoluto é utilizado como pivô, para tanto, permuta-se a linha do elemento com a linha do pivô.

É importante observar que, quando forem executadas as etapas de substituição direta e inversa, as permutações realizada no pivotemameto devem ser realizados no vetor independente do sistema de equação linear.

Def. Matriz de Permutação

Matriz quadrada de ordem n obtida da matriz identidade de ordem n pela permutação de suas linhas.

A pré-multiplicação de uma matriz A por uma matriz de permutação P resulta em uma matriz A’, obtida de A com a mesma seqüência de permutações de linhas , realizadas na matriz P.

Seja o sistema linear e sejam os fatores LU obtidos por redução de Crout com pivoteamento parcial. Portanto, LU são fatores de A’.

Onde:

A’= PA

As mesmas permutações devem ser efetuados sobre .

Algoritmo redução de Crout com permutação de linhas.

Para p=1, 2,.........n

1.

2.

3.

4.

OBS: O algoritmo de Crout com pivoteamneto parcial pode ser considerado um algoritmo estável.

Decomposição de Cholesky

Considerando:

A Simétrica e definida positiva

Tem-se

Teorema: Se A é simétrica positiva definida então existe uma única matriz L com elementos diagonais positivos tal que .

OBS 1: A matriz A é positiva definida se para qualquer vetor diferente de zero.

OBS 2: Os elementos diagonais de uma matriz definida positiva são sempre positivos.

– vetor com elemento igual a 1 na posição i e o restante igual a zero.

A prova do teorema é feita por indução.

A matriz particionada pode ser escrito como o produto:

, onde H é simétrica e também positiva definida, pois para qualquer vetor de comprimento n-1, tem-se:

, pois a matriz original é positiva definida por definição.

Por indução H, pode ser fatorado como com elementos diagonais positivos. Portanto, A pode ser dada por:

Para provar a unicidade, tem-se:

De (1) e (3) tem-se:

Como podemos ver, os fatores são únicos para positivo. Este procedimento pode ser estendido por indução aos fatores seguintes.

Computação dos fatores

Suponha a matriz particionado como onde os fatores da submatriz principal M já foram obtidos. Os fatores da matriz A podem se dado por:

Exemplo:

Computado e acessado

Elementos a serem calculados

Elementos não

Calculados

Pela simetria de A, apenas é necessário se trabalhar com sua metade inferior. Além disso, os elementos de L podem ser escritos sobre os de A.

Algoritmo

Para k = 1, 2, ....n

OBS: A decomposição de Cholesky requer multiplicações, isto é, a metade das exigidas pela redução de Crout. Os produtos internos devem ser acumulados em precisão dupla, para se obter exatidão adicional.

O algoritmo de Cholesky é incondicionalmente estável. Como A é positiva definida, não há necessidade de pivoteamento, pois neste caso ela sempre é diagonal dominante.

2.3.8 Solução de Sistemas Lineares

A partir das decomposições de Crout e Cholesky vistas anteriormente, pode-se resolver os sistemas lineares através de substituições.

Seja o sistema Linear:

2.3.8.1 Decomposição LU

Substituição Direta

Atualização por linhas

Substituição Inversa

Atualização por linhas

Substituição Direta

Atualização por colunas:

Coluna n

No final , observe que as atualizações foram feitas por colunas.

Algoritmo para atualização por colunas

As substituições direta e inversa requerem multiplicações.

2.3.8.2 Decomposição de Cholesky

Neste caso não há necessidade de se utilizar permutações, pois a matriz de coeficientes é definida positiva.

Substituições direta

Substituições Inversa