4251

0011 0010

UNIVERSIDADE FEDERAL DE UBERLÂNDIAFACULDADE DE MATEMÁTICA

Unidade II

SISTEMAS LINEARES

4251

0011 0010

Introdução

4251

0011 0010

A resolução de sistemas lineares pode surgir em diversas áreas do conhecimento.

O caso geral, em que o sistema linear envolve m equações com n incógnitas, o sistema pode apresentar uma única solução, infinitas soluções ou não admitir solução.

Neste capítulo vamos analisar esquemas numéricos para soluções de sistemas lineares de n equações com n incógnitas, supondo que este tenha uma única solução:

nnnnnnn

nn

nn

bxaxaxaxa

bxaxaxaxa

bxaxaxaxa

...

....

...

332211

22323222121

11313212111

4251

0011 0010

Os métodos de resolução de equações lineares são classificados em:

Métodos Diretos - fornecem a solução exata de um sistema linear, a menos dos erros de máquina, através da realização de um número finito de operações.

Métodos Iterativos – fornecem uma seqüência de aproximações para a solução X a partir de uma solução inicial X(0).

O sistema é representado por A x = b

onde aij são os coeficientes, xj são as incógnitas e os bj são os termos independentes.

4251

0011 0010

Métodos Iterativos

4251

0011 0010

Métodos IterativosVamos considerar um sistema linear AX = b, onde:

A: matriz de coeficientes, n x n; X =(x1, x2, ..., xn)t: vetor de variáveis, n x 1

b: vetor independente, n x 1 (constantes)

Tal sistema linear pode ser escrito na forma equivalente:

X = CX + d

onde: C: matriz com dimensões n x n;

d: vetor com dimensões n x 1;

4251

0011 0010

Partindo de um vetor X(0) (vetor aproximação inicial), constrói-se uma seqüência iterativa de vetores:

Primeira aproximação

De um modo geral, a aproximação X(k+1) é dada por:

Segunda aproximação

dCXX kk )()1( k = 0, 1, 2, ...

OBSERVAÇÃO: k é chamado de índice de iteração.

Sendo um processo iterativo, necessitamos de um critério de parada. E para isto temos que ter uma medida entre as aproximações X(k+1) e X(k). Para isto vamos usar o conceito de norma de matrizes.

X(1) = CX(0) + d

X(2) = CX(1) + d

4251

0011 0010

Definição:

Uma norma em é uma aplicação que satisfaz as seguintes propriedades:

mnR RR mn:

mn

mn

mn

B,A,BABA

A;,AA

A,AAA

R -

RR -

R -

P.3

P.2

eP.1

000

As normas matriciais mais usadas são:

Euclidiana Norma

linha Norma

coluna Norma

2/1

1 1

2

2

11

111

max

max

n

i

m

jij

m

jij

mi

n

iij

mj

aA

aA

aA

4251

0011 0010

Além disso, as normas satisfazem as seguintes propriedades:

e

21,

BAAB

XAAX

-P.5

-P.4

A norma vetorial pode ser vista como um caso particular da norma matricial, onde um vetor é equivalente a uma matriz de ordem .Com isto temos as normas de vetores dadas por:

nX R1n

Euclidiana Norma

linha) (norma infinita Normamax

coluna) (norma 1 Norma

2/1

1

2

2

1

11

n

ii

ini

n

ii

XX

XX

XX

4251

0011 0010

0lim )(

XX k

k

onde X é a solução do sistema linear.

O conceito de norma nos permite definir convergência de uma

seqüência de vetores {Xk}. Dizemos que X(k)→X se

4251

0011 0010

Com isto podemos definir os critérios de parada: Dado um

iteraçõesdemáximoNúmerokk

AXb

X

XX

XX

k

k

kk

kk

max

Resíduo do Teste

Relativo Erro||||

Absoluto Erro

)(

)1(

)()1(

)()1(

4251

0011 0010

Critério de convergência

4251

0011 0010

Seja ║.║ uma norma qualquer de matriz. Se ║C║<1 o processo

iterativo X(k+1)=CX(k)+d fornecerá uma seqüência {X(k)} convergente

para a solução do sistema AX = b.

Critério de convergência

Sendo o erro em cada iteração dado por e(k) =X(k) – X e usando as

propriedades de norma segue que:

Demonstração:

Seja X solução do sistema. Então: X = CX + d.

Subtraindo membro a membro de X = CX + d e X(k+1)=CX(k)+d tem-se:

dCXdCXXX Kk )()1(

BAAB

XXCXX kk )()1(

4251

0011 0010

)0(1

)1(2

)()1(

eC

eC

eCe

k

k

kk

Logo a seqüência {X(k)} converge para a solução do sistema X se

e isto ocorre se a matriz C satisfaz a

condição

,0limlim )0(1)1(

eCe

k

k

k

k

.1C

Quanto menor || C || mais rápido a convergência do processo.

4251

0011 0010

Método iterativo de Gauss-Jacobi

4251

0011 0010

Seja o sistema linear:

nnnnnnn

nn

nn

bxaxaxaxa

bxaxaxaxa

bxaxaxaxa

...

....

...

332211

22323222121

11313212111

Supondo , isole a coordenada xi do vetor X, na i-ésima equação, da seguinte forma:

niaii ,...,2,1,0

)...(1

)...(1

)...(1

112211

2323121222

2

1313212111

1

nnnnnnnn

n

nn

nn

xaxaxaba

x

xaxaxaba

x

xaxaxaba

x

4251

0011 0010

Desta forma, tem-se o sistema equivalente X = CX + d, onde

nnnnnnnnn

n

n

n

aaaaaa

aaaaaa

aaaaaa

aaaaaa

C

///

///

///

///

321

33333323331

22222232221

11111131112

e

nnn ab

ab

abab

d

/

/

//

333

222

111

Dada uma aproximação inicial: X(0)

o Método de G.Jacobi consiste em obter seqüência: X(1), X(2),..., X(k)

através da relação recursiva: X(k+1)=CX(k)+d.

4251

0011 0010

)...(1

)...(1

)...(1

)(11

)(22

)(11

)1(

)(2

)(323

)(1212

22

)1(2

)(1

)(313

)(2121

11

)1(1

knnn

kn

knn

nn

kn

knn

kkk

knn

kkk

xaxaxaba

x

xaxaxaba

x

xaxaxaba

x

Observe que o processo iterativo utiliza somente estimativas da iteração anterior.

Assim,

4251

0011 0010

Método iterativo de Gauss-Seidel

4251

0011 0010

Observando as equações de iteração no método de Jacobi ou seja

)...(1

)...(1

)...(1

)(11

)(22

)(11

)1(

)(2

)(323

)(1212

22

)1(2

)(1

)(313

)(2121

111

knnn

kn

knn

nn

kn

knn

kkk

knn

kk1)(k

xaxaxaba

x

xaxaxaba

x

xaxaxaba

x

nota-se que na iteração de ordem (k+1) são usadas as

componentes xj(k) da iteração anterior.

4251

0011 0010

No Método de Gauss-Seidel para calcular a

componente xj da iteração (k+1), utiliza-se as componentes já

atualizadas x1(k+1), x2

(k+1), ..., xj-1(k+1) e as componentes ainda não

atualizadas da iteração anterior xj+1(k), xj+2

(k), ..., xn(k).

x1(k+1)= (b1 - a12

x2 (k) - a13

x3 (k) - a13

x3 (k) - ... - a1n

xn (k)

x2(k+1)= (b2 - a21

x1 (k+1) - a23

x3 (k) – a24

x4 (k) - ... - a2n

xn (k)

x3(k+1)= (b3 - a31

x1(k+1) - a32

x2 (k+1) – a34x4

(k) - ... - a3n xn

(k)

.

.

.

xn(k+1)= (bn - an1

x1(k+1) - an2

x2 (k+1) – an3x4

(k+1) - ... - ann-1 xn-1

(k+1)

11

1

a

22

1

a

33

1

a

nna

1

4251

0011 0010

Interpretação Geométrica do Método de Gauss-Seidel

Considere o sistema linear 2x2 dado pelas equações abaixo e geometricamente representados pela retas r1 e r2.

222122

121111

:

:

cxbxar

cxbxar r2

r1

y

x

Temos:

222222

121111

222122

121111

/)(:

/)(:

:

:

axbcxr

axbcxr

cxbxar

cxbxar

4251

0011 0010

Inicie no ponto (x10, x2

0) = (0,0).

Para determinar (x11, x2

0), substitua na reta r1 o valor x20, ou seja mova ao

longo da reta horizontal iniciando no ponto (0, 0) até encontrar a reta r2.

O próximo ponto (x11, x2

1), é determinado movendo-se ao longo de uma reta

vertical iniciando no ponto (x11, x2

0) até encontrar a reta r1.

Continuando desde modo, aproxima-se sucessivamente da solução do

sistema, no caso da seqüência ser convergente.

),( 02

11 xx

r2

r1

y

x),( 02

01 xx

),( 12

11 xx

4251

0011 0010

),( 12

21 xx

y

x),( 02

01 xx

),( 12

11 xx

),( 02

11 xx

),( 22

21 xx

r2

r1),( 22

31 xx

),( 32

31 xx

4251

0011 0010

Critério de Sassenfeld

4251

0011 0010

Seja o sistema linear

11

11413121

.......

a

aaaa n e

jj

jnjjjjjjj

ja

aaaaa ..................... 1112211

para j = 2, 3, ..., n.

nnnnnnn

nn

nn

bxaxaxaxa

bxaxaxaxa

bxaxaxaxa

...

....

...

332211

22323222121

11313212111

definindo:

4251

0011 0010

Define-se jnj

1max

Se β<1, então o Método de Gauss-Seidel gera uma

seqüê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.

4251

0011 0010

Métodos diretos

4251

0011 0010

Os Métodos Diretos são aqueles que após um número finito

de operações fornecem a solução exata do sistema, a menos dos

erros de arredondamentos.

Definição:

Dois sistemas lineares são equivalentes se estes tem a

mesma solução.

Podemos obter um sistema equivalente ao dado, efetuando

as seguintes operações elementares:

Trocar duas equações;

multiplicar uma equação por uma constante;

somar uma equação a outra multiplicada por uma constante;

4251

0011 0010

Sistema Triangular Superior

Denomina-se sistema triangular superior a todo sistema

Ax =bem que aij = 0, para j < i.

nnnn

nn

nn

nn

bxa

bxaxa

bxaxaxa

bxaxaxaxa

33333

22323222

11313212111

....

....

...

4251

0011 0010

Método de Eliminação de Gauss

4251

0011 0010

O Método de Eliminação de Gauss consiste em transformar um

sistema linear Ax= b em um sistema triangular superior equivalente.

Considere o sistema linear:

nnnnnnn

nn

nn

bxaxaxaxa

bxaxaxaxa

bxaxaxaxa

...

....

...

332211

22323222121

11313212111

onde det(A) ≠ 0, isto é, o sistema admite uma única solução.

4251

0011 0010

O sistema linear pode ser representado na forma de matriz estendida [A0 | b0 ], ou seja:

nbaaa

baaa

baaa

nnnn

n

n

)0()0()0(

)0(2

)0()0()0(

)0(1

)0()0()0(

21

22221

11211

onde o índice superior indica a etapa do processo.

Etapa 1

Eliminar a incógnita x1 das equações k = 2, 3, ..., n. Sendo a11(0) ≠0,

subtraímos da linha k a primeira linha multiplicada por:

)0(11

)0(1

1 a

am k

k

4251

0011 0010

Os elementos mk1 são chamados de multiplicadores e o

elemento a11(0) é chamado de pivô da Etapa 1. Indicando a linha k da

matriz por Lk(0), esta etapa se resume em:

nkLmLL

LL

kkk ...,,3,2,)0(11

)0()1(

)0(1

)1(1

)1()1()1(

)1(3

)1()1()1(

)1(2

)1()1()1(

)1(1

)1()1()1()1(

2

33332

22322

1131211

nbaa

baaa

baaa

baaaa

nnn

n

n

n

Ao final desta etapa tem-se:

que representa um sistema linear equivalente ao sistema original, onde a incógnita x1 foi eliminada das equações k = 2, 3,..., n.

4251

0011 0010

Etapa 2

Eliminar a incógnita x2 das equações k = 3, 4, ..., n. Supondo que

a22(1) ≠ 0,vamos tomar este elemento como pivô desta etapa e desta

forma os multiplicadores são dados por

)1(22

)1(2k

2ka

am

A eliminação segue com as seguintes operações sobre as linhas:

nkLmLL

LL

LL

kkk ...,,4,3,)1(22

)1()2(

)1(2

)2(2

)1(1

)2(1

4251

0011 0010

obtendo ao final da etapa a matriz

)2()2()2(

)2(3

)2()2(

)2(2

)2()2()2(

)2(1

)2()2()2()2(

3

333

22322

1131211

nbaa

baa

baaa

baaaa

nnn

n

n

n

Com procedimentos análogos ao das etapas 1 e 2 elimina-se as

incógnitas xk das equações k + 1, k + 2, ..., n e ao final de n -1 etapas

tem-se a matriz:

4251

0011 0010

)1()1(

)1(3

)1()1(

)1(2

)1()1()1(

)1(1

)1()1()1()1(

333

22322

1131211

nn

n

nnn

nnnn

nnnnn

ba

baa

baaa

baaaa

nn

n

n

n

Esta matriz representa um sistema triangular superior equivalente

ao sistema original. Logo a solução deste sistema, obtido pela

Retro-Solução (substituição regressiva), é solução do sistema

original.

4251

0011 0010

)1(

)1(

n

nn

nn

n a

bx

Assim,

)1(11

)1(1

)1(1

1

n

nn

nn

nn

nn a

xabx

n

ijj

niji

iii xab

ax

1

)1(1

4251

0011 0010

Pivotamento Parcial

4251

0011 0010

Em cada etapa k da eliminação temos o cálculo do multiplicador

)1(

)1(

k

kk

kkj

kj a

am

Se o pivô |akk(k-1)| << 1, ou seja, próximo de zero, os erros de

arredondamento se tornam significativos, pois operar números de

grandezas muito diferentes aumenta os erros.

A estratégia de pivotamento parcial é baseada na operação

elementar: Trocar duas equações.

No início de cada etapa k escolhemos como pivô o elemento de

maior módulo entre os coeficientes akk(k-1) para i = k, k + 1, ..., n.

4251

0011 0010

Inversão de matrizespelo método de Gauss

4251

0011 0010

Vamos supor que desejamos resolver os sistemas

lineares Ax = b1, Ax = b2, Ax = bk, onde a matriz A é a mesma para

todos os sistemas. A matriz triangular superior, resultante do

processo de eliminação, não depende do vetor b e portanto será

a mesma em qualquer um dos sistemas.

Assim podemos resolver estes sistemas num único

processo de eliminação usando a matriz estendida (A |b1|b2|...| bk)

e aplicando a Retro-Solução para cada vetor bk.

4251

0011 0010

O Cálculo da inversa de uma matriz é um caso particular do

esquema acima. A inversa de uma matriz ARnxn, denotada por A-1,

é uma matriz nxn tal que

AA-1 = I

Como exemplo vamos considerar uma matriz A de dimensão 3 3

333231

232221

131211

aaa

aaa

aaa

cuja a inversa A-1 é dada por

333231

232221

131211

xxx

xxx

xxx

4251

0011 0010

Logo tem-se:

100

010

001

333231

232221

131211

333231

232221

131211

xxx

xxx

xxx

aaa

aaa

aaa

4251

0011 0010

Portanto cada coluna k da inversa da matriz A é solução de

um sistema linear, onde o vetor dos termos independentes é a

k-ésima coluna da matriz identidade, isto é

0

0

1

31

21

11

333231

232221

131211

x

x

x

aaa

aaa

aaa

1

0

0

33

23

31

333231

232221

131211

x

x

x

aaa

aaa

aaa

0

1

0

32

22

12

333231

232221

131211

x

x

x

aaa

aaa

aaa

4251

0011 0010

Portanto, se temos uma matriz nxn, podemos achar a

inversa resolvendo n sistemas lineares, representados pela matriz

estendida (A | b1| b2 | ... | bk) , onde os vetores bk são os vetores

unitários ( 1 na posição k e zeros nas demais posições).