47
Sistema de equações lineares

Sistema de equações lineares

  • Upload
    awena

  • View
    45

  • Download
    1

Embed Size (px)

DESCRIPTION

Sistema de equações lineares. Caracterização. Um sistema de m equações a n variáveis é é chamado sistema de equações lineares. Ele tem a forma genérica seguinte:. Solução. Um conjunto de n valores (x 1 , ..., x n ) verificando as equações do sistema é uma solução do sistema. - PowerPoint PPT Presentation

Citation preview

Page 1: Sistema de equações lineares

Sistema de equações lineares

Page 2: Sistema de equações lineares

Caracterização

Um sistema de m equações a n variáveis é é chamado sistema de equações lineares. Ele tem a forma genérica seguinte:

11 1 12 2 1 1

21 1 22 2 2 2

1 1 2 2

....

....

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

....

n n

n n

m m mn n m

a x a x a x b

a x a x a x b

a x a x a x b

Page 3: Sistema de equações lineares

Solução

Um conjunto de n valores (x1, ..., xn) verificando as equações do sistema é uma solução do sistema.

Um sistema cujo os valores dos coeficientes bn são iguais a 0 é um sistema homogêneo:

11 1 12 2 1

21 1 22 2 2

1 1 2 2

.... 0

.... 0

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

.... 0

n n

n n

m m mn n

a x a x a x

a x a x a x

a x a x a x

Page 4: Sistema de equações lineares

Caracterização matricial

O sistema pode ser escrita sobre a forma de um produto de matrizes:

onde as matrizes são definidas por:

Page 5: Sistema de equações lineares

Combinação linear

A combinação linear de equações é a soma dessas equações multiplicado por coeficientes reais: 1eq1+2eq2+...+neqn onde ii{1,...,n} é

uma combinação linear de eq1, eq2, ..., eqn.

Em relação com as variáveis envolvidas nas equações, uma equação linear, combinação linear entre as outras equações não introduz novas relações entre as variáveis.

Page 6: Sistema de equações lineares

Sistemas equivalentes

Num sistema de equações lineares independentes, se uma equação é trocada por uma combinação linear dela mesma e outras equações do sistema, o novo sistema é equivalente o primeiro. Os dois sistemas têm a mesma solução.

1 1 2 2 11

2 2

. . ... , 0

... ...

n n

n n

eq eq eqeq

eq eq

eq eq

Page 7: Sistema de equações lineares

Sistemas equivalentes

Num sistema, se uma equação é combinação linear das outras, ele é equivalente ao sistema sem essa equação:

2 2 2

32

. ...

... ...

n n

n n

eq eq eq

eqeq

eq eq

Page 8: Sistema de equações lineares

Equações e variáveis

Um sistema de m equações a n variaveis: Tem uma solução unica se ele pode ser reduzido

a um sistema de n equações independentes a n variáveis.

Tem uma infinidade de soluções, se ele é equivalente a um sistema de m’ equações independentes com m’<n

Page 9: Sistema de equações lineares

Determinante

Um determinante é um número associado a um matriz quadrada (mesmo número de linha e coluna).

A definição do determinação envolve a noção de permutação. O determinante de uma matriz A (aij é o coeficiente da i-ésima linha e j-ésima coluna) é, onde n são elementos distintos de (1,...,n) e k é o número de permutações para passar de (1,...,n) para (1,..., n):

1 2

!

1 2( 1) ...n

kn

nA a a a

Page 10: Sistema de equações lineares

O calculo do determinante 2x2:

O calculo do determinante 3x3 é feito da forma seguinte:

Det A= =

Calculo do determinante, caso 2x2 e 3x3

11 22 33 21 32 13 31 12 23

31 22 13 11 32 23 21 12 33

a a a a a a a a a

a a a a a a a a a

11 1211 22 21 12

21 22

a aa a a a

a a

Page 11: Sistema de equações lineares

O desenvolvimento de Laplace permite o calculo do determinante da forma seguinte:

Onde ij é o determinante da submatriz obtido de A retidando-se a i-ésima linha e j-ésima coluna e multiplicado por (-1)i+j. O número i pode ser qualquer número de {1,...,n}. Esse princípio funciona para qualquer linha ou coluna.

Determinante, caso nxn

11 12 1

21 22 2, ,

1 1

1 2

...

..., ( 1)

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

...

n

j n j nn i j

ij ij ji ji ij kp k i p jj j

n n nn

a a a

a a aa a a

a a a

Page 12: Sistema de equações lineares

Determinante, caso nxn

O calculo do determinante pode ser implementado com um procedimento recursivo. O calculo de um determinante nxn é determinado a partir de determinantes (n-1)x(n-1).

O preço do cálculo de um determinante é elevado. Considerando a formula da definição, são necessárias n!(n-1)+(n!-1) ou seja n!n-1 operações para um determinante de dimensão n: (n!-1) somas de n!(n-1) produtos, sem considerar os elementos anexos necessários (posição de memoria, sinal, etc).

Page 13: Sistema de equações lineares

Determinante, um algoritmo

O calculo é feito usando os coeficientes da primeira linha.

Determinante(m) // m: matrizse dim(m)=2 resultado=m[0][0].m[1][1]-m[1][0].m[0][1]se dim(m)=1 resultado=m[0][0]Se dim(m)>2 resultado=0

i de 1 a dim(m) construír a submatriz de m sem a primeira linha e a i-ésima coluna (subm)resultado=resultado+(-1)i.m[0][i].Determinante(subm)

Page 14: Sistema de equações lineares

Determinante e sistema

Se um sistema de n equações lineares a n variáveis tem um determinante diferente de 0: det A0, as equações do sistema são independentes.

Nesse caso, o sistema tem uma solução única. Em caracterização matricial, essa solução escreve-se:

onde A-1 é a matriz inversa da matriz A.

1x A b

Page 15: Sistema de equações lineares

Determinante e matriz inversa

Se o determinante de uma matriz é não nulo, a matriz inversa pode ser calculada.

Onde ij é o determinante da matriz formada a partir da matriz A retirando a i-ésima linha e j-ésima coluna.

11 1 11 11

1 1

... ...1

... ... ... , ... ... ...

... ...

n n

n nn n nn

a a

A AA

a a

Page 16: Sistema de equações lineares

Formula de Cramer

Pela formula de Cramer, se o determinante do sistema é não nulo, o valor solução da variável xi é dado pela formula seguinte:

O numerator da fração é o determinante da matriz formada da matriz A do sistema onde a coluna dos coeficientes de xi são subsituídos pelos termos constantes bi.

11 1 1 1 1 1 1

21 2 1 2 2 1 2

1 1 1

... ...

... ...1... ... ... ... ... ... ...det

... ...

i i n

i i ni

n ni n ni nn

a a b a a

a a b a ax

A

a a b a a

Page 17: Sistema de equações lineares

Exemplo

1 2 3

1 2 3

1 2 3

2 3 0

4 3

8 1

x x x

x x x

x x x

2 3 1

det 1 1 4 2 8 12 3 64 1 64

1 8 1

1

0 3 1

3 1 4

1 8 1 46

64 64x

2

2 0 1

1 3 4

1 1 1 10

64 64x

3

2 3 0

1 1 3

1 8 1 62

64 64x

Page 18: Sistema de equações lineares

Custo da formula de Cramer

Para resolver um sistema de n equações a n variáveis, pela formula de Cramer precisam ser calculados n+1 determinante de ordem n (n linhas, n colunas).

O custo da resolução desse sistema é de:

(n!n-1)(n+1) operações.

Para 10 variaveis: 399167989

Page 19: Sistema de equações lineares

Eliminação Gaussiana

A eliminação Gaussiana usa a propriedade de equivalência de sistema para eliminar progressivamente as variáveis ate chegar a uma equação de uma variável.

11 1 12 2 1 1

22 2 2 2

....

....

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

n n

n n

nn n n

a x a x a x b

a x a x b

a x b

Page 20: Sistema de equações lineares

Sistema triangular

No novo sistema, podemos determinar:

O sistema é chamado sistema triangular e a matriz associada é uma matriz triangular. Se fala também de triangular superior ou inferior para caracterizar a posição dos coeficientes não nulos.

1 11

11 1

1, ,......, ( )

nn n n n n

n n i i ij jj inn n n ii

b b a xx x x b a x

a a a

Page 21: Sistema de equações lineares

Eliminação Gaussiana e determinante

O determinante de um sistema triangular é o produto dos termos da diagonal.

Em um determinante, adicionar os termos (ou os termos multiplicado por um fator) de qualquer linha (resp. coluna) a qualquer outra linha (resp. coluna) não muda o valor do determinante.

11 12 1

22 211 22

...

0 ......

... 0 ... ...

0 ... 0

n

nnn

nn

a a a

a aa a a

a

Page 22: Sistema de equações lineares

Método

Escolhe uma das equações (i-ésima) com o coeficiente (ai1) de x1 não nulo. Esse coeficiente é chamado de pivot (ou pivot de Gauss).

Adicionar a cada uma das equações restantes (j, ji), a primeira equação multiplicada por: -aj1/ai1

Aplicar de novo o algoritmo com o sub-sistema de n-1 variáveis ate chegar a uma equação de uma variável.

Page 23: Sistema de equações lineares

Exemplo

1

2

3

46

6410

6462

64

x

x

x

1 2 3

1 2 3

1 2 3

2 3 0

4 3

8 1

x x x

x x x

x x x

1 2 3

2 3

2 3

2 3 0

5 73

2 219 1

12 2

x x x

x x

x x

1 2 3

2 3

3

2 3 0

5 73

2 2128 62

10 5

x x x

x x

x

Page 24: Sistema de equações lineares

Matriz

O processo pode ser aplicado com matrizes. Nesse caso, se considera a matriz aumentada com as constantes da matriz do sistema:

E as combinações lineares entre as equações são feitas entre as linhas de coeficientes.

11 12 1 1

21 22 2 2

1 2

...

...[ ]

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

...

n

n

n n nn n

a a a b

a a a bA

a a a b

Page 25: Sistema de equações lineares

Exemplo com matriz

2 3 1 0

1 1 4 3

1 8 1 1

2 3 1 0

5 70 3

2 219 1

0 12 2

2 3 1 0

5 70 3

2 2128 62

0 010 5

Page 26: Sistema de equações lineares

Exercício

1 2 3 4

1 2 3 4

2 4

1 2 3 4

3 5 2 10

9 8 4 15

2

2 3

x x x x

x x x x

x x

x x x x

Solução: x1=-1, x2=0, x3=1 e x4=2

Solução: x1=-1, x2=0, x3=1 e x4=2

Page 27: Sistema de equações lineares

Custo da eliminação Gaussiana

Para eliminar o primeiro termo das n-1 equações de um sistema a n equação, precisamos de n-1 divisões, (n-1)(n+1) multiplicações e (n-1)(n+1) adições: 2n2+n-3. Para eliminar os termos ate a ultima equação precisamos de operações, da ordem de 2n3/2.

A resolução do sistema triangular necessita: n divisões, n(n-1)/2 multiplicações e n(n-1)/2 adições.

2

2

2 3i n

i

i i

Page 28: Sistema de equações lineares

Velocidade da resolução

Uma das razões de escolher uma algoritmo no lugar de um outro é em geral baseado sobre a relação entre velocidade e precisão.

No caso da resolução de sistemas lineares, a formula de Cramer precisa de muito mais operações que a eliminação Gaussiana.

Page 29: Sistema de equações lineares

Estratégia de pivoteamento

Resolução do sistema seguinte usando sucessivamente 0.004 e 0.423 como pivot e calculando usando somente 4 algarismos significativos:

A solução do sistema e (10,1). Com 0.004 como pivot achamos (12.5,0.9994) e com 0.423 achamos (10,1).

1 2

1 2

0.004 15.73 15.77

0.423 24.72 20.49

x x

x x

Page 30: Sistema de equações lineares

Estratégia de pivoteamento

No caso geral, para diminuir os erros de arredondamento, é preferível usar como pivot o maior coeficiente em valor absoluto da variável a eliminar nas equações do sistema.

1..( ) max( )i ij

j npivot x a

Page 31: Sistema de equações lineares

Eliminação Gaussiana, algoritmo

n: numero de variáveis, m: matriz aumentada Eliminacao_gauss(n, m)

para i de 1 a npara j de i a n, procure o coeficiente maior em valor

absolute: linha max troca a linha max com a linha i de mpara j de i+1 a n, para k de i a n+1, subtrai m[j][i]/m[i]

[i] de m[j][k]

Page 32: Sistema de equações lineares

Soluções particulares

Certas situações precisam de determinar as soluções de sistemas onde somente os termos constantes (bi) mudam: solução de:

e solução de:

11 1 12 2 1 1

1 1 2 2

....

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

....

n n

n n nn n n

a x a x a x b

a x a x a x b

11 1 12 2 1 1

1 1 2 2

.... '

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

.... '

n n

n n nn n n

a x a x a x b

a x a x a x b

Page 33: Sistema de equações lineares

Soluções particulares

Nesses casos, é mais eficiente de triangular o sistema uma vez e resolve-lo com os diversos valores dos termos constantes (bi). Nesse caso uma segunda matriz é necessária para calcular os termos constantes do sistema triangular em fonções dos coeficientes de origem.

Page 34: Sistema de equações lineares

Soluções particulares

Nesse caso, a matriz coluna dos termos constantes é considerada como o produto da matriz identidade como essa matriz coluna. As transformações operadas pela triangularização serão aplicadas à matriz identidade e não à matriz coluna dos termos constantes.

11 1 1 1

1

... 1 0 0

... ... ... ... 0 1 0 ...

... 0 0 1

n

n nn n n

a a x b

a a x b

Page 35: Sistema de equações lineares

Matriz Inversa

Se o processo de transformação do sistema continua ate obter um sistema cuja matriz é a matriz identidade, a matriz de transformação dos termos constantes é a matriz inversa da matriz do sistema inicial:

1 11

1 0 0

0 1 0 ... ...

0 0 1 n n

x b

A

x b

Page 36: Sistema de equações lineares

Exemplo

1

3 3 3 2

5 6 2 4

4 5 4 3

1 1 1 1

A

2 1 0 0

1 0 1 1

0 1 1 1

1 0 0 3

A

Page 37: Sistema de equações lineares

Erros de aproximação

Os erros de arredondamento têm um papel importante na solução de sistemas de equações lineares, principalmente por conto do grande número de calculo a ser efetuados.

A um efeito de “condensação pivotal” no caso da eliminação gaussiana. Cada calculo depende dos resultados anteriores.

Page 38: Sistema de equações lineares

Avaliação dos erros

Uma forma de avaliar o erro é trocar as variáveis nas equações pelos valores determinados e comparar os resultados com os termos constantes:

Sistema: soluções:

Trocando nas equações:

1 2

1 2

3 4 7

5 2 3

x x

x x

1

1

0.999

1.002

x

x

3(0.999) 4(1.002) 7.005

5(0.999) 2(1.002) 2.991

Page 39: Sistema de equações lineares

Avaliação dos erros

Um pequeno erro sobre os resultados conduz a considerar que os valores das variáveis determinados são boas aproximações dos resultados exatos.

Existem casos nos quais não podemos afirmar isso.

Page 40: Sistema de equações lineares

Sistema mal condicionado

Considerando o sistema seguinte:

Uma solução como x1=100, x2=-98 é uma solução aceitável do ponto de vista do critério precedente, porém ela é longe da solução exata (70,-68).

1 2

1 2

2

1.0001 2.007

x x

x x

Page 41: Sistema de equações lineares

Sistema mal condicionado

Um sistema de equações que pode ser satisfeito por soluções erradas é um sistema mal condicionado.

Do ponto de vista gráfico, no caso da dimensão 2, o sistema é mal condicionado quando as duas retas representando as equações são próximas:

Page 42: Sistema de equações lineares

Sistema mal condicionado

Um sistema é mal condicionado quando seu determinante é próximo de zero.

O que significa, um determinante próximo de zero ? Como multiplicando qualquer equação por um fator não muda a solução do sistema, enquanto multiplica o determinante por esse fator, falar de um valor pequeno do determinante não significa nada.

Page 43: Sistema de equações lineares

Sistema mal condicionado

Para determinar se um sistema é mal condicionado, existem duas possibilidades: O determinante normalizado é próximo de 0: cada

linha é dividida por um fator de proporcionalidade, raiz quadrada da soma dos quadrados dos coeficientes da linha.

Se uma pequena mudança de um termo constante do sistema provoca uma uma mudança importante no resultado, o sistema é mal condicionado.

1

22

1

n

i ijj

k a

Page 44: Sistema de equações lineares

Método iterativo de Gauss-Seidel

O sistema é transformado de tal forma que cada equação pode dar o valor de uma variável (no caso que um dos aii é nulo, o sistema pode ser reordenado para ter a condição: aii, i={1,...,n}):

1 1 12 2 11111 1 12 2 1 1

1 1 2 21 1 1

1( .... )

....

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

.... 1( ....

n n

n n

n n nn n nn n n nn

nn

x b a x a xaa x a x a x b

a x a x a x bx b a x a x

a

1)n

Page 45: Sistema de equações lineares

Método iterativo de Gauss-Seidel

Em seguida, a cada passo e a partir de valor iniciais de (x2, ..., xn), novos valores de (x1, ..., xn) são calculados.

Quando converge, esse processo pode exigir muitas iterações para chegar a um resultado razoável. Ele é aconselhado somente quando o sistema é mal condicionado ou quando muitos coeficientes do sistema são nulos (convergência rápida)

Page 46: Sistema de equações lineares

Método iterativo de Gauss-Seidel

O algoritmo pode ser parado quando: É atingido um número de iteração dado. A diferencia entre dois valores sucessivas dos xi

é menor que um valor limito: . Critério particularmente delicado a manipular (convergência muito lenta).

Page 47: Sistema de equações lineares

Método iterativo de Gauss-Seidel

Se o método não converge, ele pode ser aplicado mudando a ordem das equações (ou seja mudando as equações determinando cada xn).

1

1

, 1,...,

, 1,...,

n

ii ijjj i

n

ii jijj i

a a i n

a a i n

Existe um teorema que garante a convergência: Se o termo da diagonal principal é maior em valor absoluta que a soma dos valores absolutos dos outros termos da linha do coeficiente e que a soma dos valores absolutos dos outros termos da coluna do coeficiente, a convergência é garantida.