1

APOSTILA DE LGEBRA LINEAR COMPUTACIONAL Aluno: Rodrigo Neves Figueiredo dos Santos Professor: Paulo Parga 200119044-0

1-Particionamento de matrizes Uma matriz pode ser dividida em submatrizes atravs de linhas horizontais e verticais, como ilustrado no seguinte exemplo particular:

a11 A = a 21 a 31

a12 a 22 a32

a13 a 23 a33

a14 a 24 a34

a15 a 25 a35

a16 a 26 a 36

Podemos escrever isso usando a seguinte notao: A= onde A11 =

A11 A21

A12 A22

A13 A23

a11 a 21

a12 a 22

a13 , A12 = a 23

a16 a a14 , A21 = (a31 , A13 = 15 a a 24 25 a 26 A22 = (a34 ) e A23 = (a35 a36 ) .

a32

a33 ) ,

Esta tcnica empregada freqentemente para facilitar manipulaes matriciais, j que em muitas operaes as submatrizes podem ser tratadas como elementos. A principal vantagem do particionamento para a lgebra Linear Computacional no mbito da diminuio de contas, j que se uma ou mais das submatrizes que particionam a matriz original forem nulas ou (se no caso de submatrizes quadradas) correspondentes identidade. Exemplo 1.1:

1 2 3 4 Seja A = 4 3 2 1 e B = 1 0 1 0

1 1 0 1 1 1 , logo teremos que A x B = 0 1

2 8 2 2 0 0

Se pensarmos em particionar as matrizes acima, da maneira que se encontram sublinhadas, para facilitarmos as contas, poderemos adotar a seguinte notao:

A11 A 21

A12 B11 * A22 B21

B12 A11 B11 + A12 B21 = B22 A21 B11 + A22 B21

A11 B12 + A12 B22 A21 B12 + A22 B22

2

Teorema 1.2: Seja A uma matriz mxn, as seguintes afirmaes so equivalentes: i) A-1 ; ii) det 0; ii) AX = 0 admite apenas soluo trivial; iv) As linhas da matriz A so linearmente independentes; v) As colunas da matriz A so linearmente independentes; vi) O sistema AX = b possvel e determinado para todo b.

2-Sistemas Triangulares Um sistema linear dito ser triangular inferior se tiver forma:

a x = b1 11 1 = b2 a 21 x1 + a 22 x 2 L L M a x + a x + ....... + a x = b n2 2 nn n n n1 1ou matricialmente:

a11 a 21 M a n1

0 a 22 an 2

0 x b1 1 L 0 x2 b2 = M M M L a nn xn bn L

onde det = a11 a 22 ... a nn , e o sistema dito ser triangular superior se o mesmo tiver a forma:

a11 x1 ou matricialmente:

+ a12 x2 a22 x2

+ a13 x3 L +

a1n xn

= b1 = b2 = b3 M = bn

+ a23 x3 L + a2 n xn

a33 x3 L + a3n xn LL LL ann

a11 0 M 0

a12 a220

L a1n x1 b1 L a2 n x2 b2 M = M L ann xn bn

3

onde assumimos que aii 0, para que o sistema tenha uma nica soluo e o determinante det = a11 a 22 ... a nn . Observe que a soluo tanto de um sistema triangular inferior quanto de um triangular superior pode ser calculada imediatamente por substituio direta no primeiro caso comeando pela primeira equao e substituindo a soluo encontrada na segunda equao e assim sucessivamente at chegar ltima equao, e por substituio inversa no segundo comeando pela ltima equao e substituindo a soluo encontrada na penltima equao e assim sucessivamente at chegar primeira equao. 2.1-Substituio de cima para baixo e de cima para baixo Vejamos agora um mtodo de resoluo de sistemas triangulares, quando os mesmos forem triangulares inferiores: x1 =

b1 a11 (b2 a 21 x1 ) a 22. . .

x2 =

xi =

bi j =1 aij x ji i

aii

, i = 2,3,.....,n.

Agora quando o sistema for triangular superior, iremos utilizar o mtodo da substituio de baixo para cima. xn =

bn a nn. . .

xi =

bi j =i +1 aij x jn

aii

, i = n-1,........,1.

Apresentemos agora um algoritmo computacional para realizar as operaes acima. Algoritmo da substituio de cima para baixo For i = 1,....,n If aii = 0, erro, fim For j =1,.....,i-1(no executado para i = 1) bi bi aijbj; end; bi bi/aii end.

4

Clculo do nmero de flops gastos pela execuo do algoritmo 1 + 2 + 3 +.......+ n-1 = Nmero total de flops =

(n - 1)(n - 1 + 1) (n 1)n n2 n = = 2 2 2 2

n2 . 2

2.2-Eliminao Gaussiana Dado um sistema de n equaes e de n incgnitas

Ax = beste mtodo consiste em reduzir o sistema a uma forma equivalente, tal que a matriz A se escreva como uma matriz triangular superior ou inferior, embora a superior seja mais freqentemente a escolhida na prtica. Neste caso, a triangulao do sistema faz-se coluna a coluna, mantendo fixa a linha correspondente coluna a ser eliminada. As principais operaes com linhas num sistema ( A b ) so:

Lj *Li cLj , c 0 * Li Li Lj* Li

-a troca da posio relativa de duas linhas; -a multiplicao de uma linha por uma constante; -a substituio de uma linha pela sua soma com outra linha qualquer. No caso de um sistema genrico,

a11 a21 M a n1

a12 a22 an 2

L a1n x1 b1 L a2 n x2 b2 M = M L ann xn bn

no primeiro passo da triangulao o coeficiente a11 designado ``piv''. A primeira linha fica intacta (``linha piv''), a todas as outras se subtrai o produto do seu primeiro termo pela linha piv, dividido pelo piv. Estes produtos so denominados m1 j e podem ser descritos da seguinte maneira: - Quando zerarmos o primeiro elemento da segunda linha, m21 =

a 21 a31

a11 a11

- Quando zerarmos o primeiro elemento da terceira linha,

m31 =

e assim sucessivamente, at que toda a primeira coluna esteja nula com exceo do piv. O sistema aps estas interaes se torna como ilustrado abaixo:

5

a11 0 M 0

a12 a a 22 a12 21 a11 a n 2 a12 a n1 a11

b1 a 21 x1 a 21 b b L a 2 n a1n a11 x 2 2 1 a11 M = M a n1 a n1 x n bn b1 L a nn a1n a11 a11 L

a1n

Como o objetivo principal desta disciplina a otimizao dos gastos das operaes computacionais, o que faremos para no perder espao de memria inutilmente, ser armazenar os coeficientes mi1 nas suas respectivas coordenadas da matriz triagularizada, pois agora seus valores se tornaram nulos, desta maneira o sistema ir tomar o seguinte aspecto:

a11 m21 M m n1

a12 a 22 a12 m21 a n 2 a12 mn1

b1 x1 L a 2 n a1n m21 x 2 b2 b1 m21 M = M L a nn a1n mn1 x n bn b1 mn1

L

a1n

Seguidamente, toma-se a ' 22 = a 22 a12 m21 como novo piv e repetem-se as operaes anteriores para a segunda coluna, deixando intactas as linhas 1 e 2. Assim o processo deve se repetir para todas as colunas, at que a matriz tenha se tornado triangular superior. O algoritmo escreve-se: Algoritmo da Eliminao Gaussiana For k = 1,.......,n For i = k+1,.......,n For j = k,......,n

aij aij bi bi end; end.

aik a kj ; a kk

aik bk ; a kk

Clculo do nmero de flops gastos pela execuo do algoritmo

2 2 + 3 2 + ... + (n 1) 2 + n 2 =

(2n 1)(n 1)n n3 = flops. 6 3

Inicialmente, e para facilitar a compreenso, vamos restringir a apresentao do mtodo a matrizes 2 x 2 como a do exemplo. Seja o sistema de equaes a seguir:

x1 4 x2 = 52 x1 x2 = 4

6

Deseja-se obter o conjunto de valores x = [x1 x2] que soluciona as duas equaes simultaneamente. Usando a notao matricial, este problema pode ser reescrito na forma:

1 4 x1 5 2 1 x = 4 2 A X b ou seja, AX = b. Existem vrias formas de resolver esta equao. Em particular, quando a inversa da matriz A existe, o problema tem soluo nica dada por: X = A-1b. Estamos interessados em uma soluo mais geral, que possa ser implementada em qualquer linguagem, mesmo aquelas que no tem suporte para funes pr-definidas agindo sobre matrizes. Para facilitar a manipulao dos sistemas de equaes lineares, reescrevemos o sistema acima como uma combinao da matriz A e o vetor de elementos independentes b: A =

2 1 4 1 4 5

Seja o sistema de equaes a seguir: x1 + 2x2 - 2x3 = -1 x1 - x2 + x3 = 2 - 2x1 - x2 + 2x3 = 1 A diferena bsica deste problema para o anterior que mais de uma iterao com pivs diferentes sero realizadas . Isto porque, como se tem trs linhas, preciso zerar os elementos da 1 coluna abaixo do elemento (1,1) (com o primeiro piv) e depois, deve-se zerar os elementos da 2 coluna, abaixo do elemento (2,2). Assim, a ltima linha da matriz fica sendo [0 0 a33], permitindo a soluo para a varivel x3. Em geral, tm-se (n-1) redues pivotais para levar a matriz at a forma triangular superior. Isto implica em mais laos de iteraes no algoritmo visto anteriormente. Usando a notao A para a matriz estendida, os passos do algoritmo aplicados na matriz do exe-mplo so:

2 2 1 1 A = 1 1 1 2 2 1 2 1 1.Comear pela linha 1. 2. Fazer iteraes para linhas desde 1 at n (n = nmero de linhas): 3. Realizar trocas de linhas at que o elemento de maior mdulo da coluna de ndice j aparea na posio (``j'',``j''). No exemplo, e para o primeiro passo da iterao (j = 1), isto significa trocar as linhas 1 e 3 da matriz A, resultando em:

7

1 2 1 2 A = 1 1 1 2 1 2 2 1 O elemento que se encontra na posio (``j'',``j''), ou A (1,1) = -2 no exemplo, chamado de piv. A partir do ponto em que se descobriu o piv, faz-se a reduo pivotal, operando-se com as linhas abaixo de ``j'' da seguinte forma:

1 2 1 2 0 3 / 2 2 5 / 2 ; A = 1 2 2 1 Para obter a soluo do sistema, repete este processo fazendo iteraes at encontrar

xn , xn1 ,....., x1 .No caso 2x2, este passo j resulta na triangularizao da matriz A. O passo seguinte a substituio para trs para obter a soluo do sistema.

2.3-Decomposio LU

a b Seja A = d e g h

c f i

Se A for no singular, ento A admite uma decomposio denominada LU, onde L uma matriz triangular inferior e U uma matriz triangular superior. Vamos agora tentar entender como possvel garantirmos o que foi dito acima e como determinar esta decomposio. Em primeiro lugar teremos nos lembrar de o que significa uma operao elementar em uma matriz. Se a operao for do tipo entre linhas, como exemplo abaixo L3 L3 + kL1 ela pode ser representada por uma matriz, que denotaremos por E, ou seja, existe uma matriz denotada elementar, que quando operada com A realiza a operao acima. No nosso caso ela ser:

1 0 0 a b E A = B 0 1 0 d e k 0 1 g h e a inversa de E dada pela matriz abaixo

c a b c f = d e f i g + ka h + kb i + kc

E

1

1 = 0 k

0 0 1 0 0 1

8

Agora pelo que vimos sobre eliminao gaussiana, para transformar uma matriz em triangular superior necessrio apenas realizar operaes elementares sobre as linhas da matriz A, que transformamos a matriz A em U. Desta forma,

U = E p E( p 1) .....E 2 E1 A A = E11 E 2 1 .....E p 1U

e

E mais, se analisarmos com cuidado, perceberemos que como estamos desejando transformar a matriz inicial em triangular superior,teremos que anular valores da semi-banda inferior, o que implica em todas as matrizes elementares possurem elementos apenas na semibanda inferior.Logo o produto das inversas das matrizes relacionadas s operaes elementares ser no final triangular inferior, ou seja, a matriz L. A = E11 E2 1 .....E p 1U 14 244 4 3 L

Algoritmo para decomposio LU For k = 1, 2, ..., (n-1) amax 0 imax 0 for i = k, ..., n if ( aik > amax) then amax imax i

(determinar o maior piv)

aik

if (imax=0) then set flag intch(k) 0 else if (imax k) then for j = 1, ..., n temp akj akj aimax.j aimax.j temp intch(k) imax for i = (k+1), ..., n akj -aik/akk for i = (k+1), ..., n for i = (k+1), ..., n aij aij + aikakj

(se a matriz for singular)

(realiza a troca de linha)

(calcula os multiplicadores) (executa as operaes elementares nas linhas)

if (ann = 0) then set flag (A singular) intch(n)0 else intch(n)n exit. O nmero de flops gastos nesta decomposio da ordem de n 3 3 , o mesmo gasto na eliminao gaussiana.

9

No se esquecendo de que a decomposia LU nica. Exemplo de decomposio LU:

3 2 4 Seja = 1 1 2 4 3 2 3 2 4 1 2 A = 1 3 4 3 13 22 3 3 3 3 2 4 1 2 A = 1 3 3 4 3 1 8 3

Piv = a11 = 3

mult. m 21 = 1 m31 = 4

3

3

Piv = a 22 ' = 1

3

mult. m32 = 1

1 0 0 3 L = 1 1 0 e U = 0 4 3 0 3 1 1 2.4-Decomposio de Cholesky

2 1 3 0

4 2 3 8

Quando possumos uma matriz simtrica, ou seja, que ela igual a sua transposta, existe um mtodo de decomposio muito utilizado: o de Cholesky ou da Raiz. Este mtodo consiste em decompor a matriz inicial no produto de duas novas matrizes; uma triangular superior e a outra triangular inferior. O curioso que a relao existente entre as mesmas, uma a transposta da outra. Vamos tentar entender porque isto possvel. Seja A uma matriz simtrica A = A t , da lgebra Linear sabemos que se ela no singular existe uma decomposio LDU para ela: Sabemos que A = A t = ( LDU ) t = U t DLt , mas como a decomposio LDU nica, logoG 678 U = L e L = U , assim, U t DLt = LDLt = ( L D )( D Lt ) = GG t . 123t t

Gt

Exemplo 2.4.1:

1 2 0 2 8 4 Seja A = 0 4 5 1 10 12

1 10 12 46

A decomposio LU desta matriz :

10

1 2 A = LU = 0 1

0 1 1 3

0 0 1 0

0 1 0 0 0 0 1 0

2 4 0 0

0 1 4 12 1 0 0 9

Depois continuamos e determinamos a decomposio LDU, para enfim determinar a Cholesky:

1 2 A = LDU = 0 1

0 1 1 3

0 0 1 0

0 1 0 0 0 0 1 0

0 4 0 0

0 0 1 0 0 2 0 0

0 1 0 0 0 0 9 0 0 0 1 0

2 1 0 0

0 1 1 3 1 0 0 1 0 2 0 0 0 0 1 0 0 1 0 0 0 0 3 0 2 1 0 0 0 1 1 3 1 0 0 1

1 0 0 0 1 2 1 0 0 0 A = L d dU = 0 1 1 0 0 1 3 0 1 0 t 644 G 44 644G 44 7 8 7 8 1 0 0 0 1 2 0 1 2 2 0 0 0 2 2 6 A= 0 2 1 0 0 0 1 0 1 6 0 3 0 0 0 3

0 1 0 0 0 0 3 0

Algoritmo de Cholesky ou da Raiz For j = 1,......,n For k = 1,.....,j-1 ajj ajj ajk2 (no executa para j = 1) If ajj 0 , erro, fim ajj sqrt(ajj) For i = j + 1,......,n (no executa para j = n) For k = 1,.........,j-1 (no executa para j = 1) aij aij - aikajk aij aij / ajj end. Clculo do nmero total de flops

1 = ( j 1 ) = ( j 1)(n j ) = ( jn n jj =1 i = j +1 k =1 j =1 i = j +1 j =1 j =n

n

n

j 1

n

n

n

n

2

+ j)

11

=

n (n + 1) n n (n + 1)(2n + 1) n (n + 1) n 3 n 3 n 3 n2 + = 2 6 2 2 3 6

Obs: Se analisarmos bem, veremos que o nmero total de flops gastos por este algoritmo bem menor do que o gasto pelo algoritmo da decomposio LU , ou seja, este mais eficiente. Nas contas gerais este algoritmo duas vezes mais eficaz na reduo das operaes computacionais.

2.5-Decomposio de Matrizes no Quadradas Seja A uma matriz no quadrada pertencente a Rmxn, logo existe uma transformao linear, que leva um vetor n-dimensional em outro m-dimensional, dada por:

T : Rn Rm x a Axem que a matriz A = [T ]cann . mcan

Sejem, uma base qualquer do Rn e uma base qualquer do Rm , desta maneira podemos reescrever A assim:

A = [T ]cann = [I ]canm [T ] n [I ] mcan

cann

Se m = n e A for uma matriz simtrica, ento uma de autovetores ortonormal. Se m n, faremos uma decomposio da seguinte forma:

Amxn = Q V tonde uma matriz quase diagonal e Q , V t so matrizes ortonormais. Antes de continuarmos com a decomposio, vamos ver algumas proposies que iro nos auxiliar no seu desenvolvimento. Proposio 2.5.1: Seja A uma matriz qualquer (no precisa ser quadrada), ento AtA simtrica. Dem: (AtA)t = At(At)t = AtA. Exemplo da proposio:

1 1 Seja A = 1 0 1 1

1 1 1 AA = 1 0 1 t

1 1 1 0 = 1 1

3 0 0 2

12

1 1 AA = 1 0 1 1 t

2 1 0 1 1 1 1 0 1 = 1 1 1 0 1 2

Vemos que as duas matrizes obtidas so realmente simtricas. Proposio 2.5.2: Os autovalores de AtA so no-negativos. Dem: Seja autovalor de AtA associado a v unitrio. vt(AtA)v = vt( )v = (vtv) = . Mas vt(AtA)v = (Av)t(Av) que a definio de produto interno, e tem a propriedade de ser sempre positivo. vt(AtA)v > 0 > 0. Proposio 2.5.3 (Teorema Espectral): Se A simtrica Existe uma base = { v1, v2, ..., vr, vr+1, ..., vn } ortonormal do Rn formada por autovetores de AtA tal que

1 , 2 , K , r > 0 r +1 , K , n = 0Proposio 2.5.4: Seja a base = { Av1, Av2, ..., Avr } , com v1, v2, ..., vr da proposio anterior ento ortogonal com vetores no-nulos. Dem: Se Avi = 0 ento (AtA)vi = 0 vi seria autovetor associado a um autovalor nonulo Avi 0.

0 se i j < Avi , Avj > = (Avi)t (Avj) = (vi)t At Avj = (vi)t j vj = j (vi)t vj = j se i = j pois vi e vj , que ortonormal.Definio 2.5.5: Seja a matriz A e o vetor vi , os mesmos tratados nas duas proposies anteriores, denotaremos de valores singulares os i obtidos da seguinte forma:

Avi =Proposio 2.5.6:

i = i

Av A base = 1

1

Av 2

Av r geradora do espao Rn. 2 ... r

Desta maneira basta tomarmos agora a transformao abaixo:

13

T:

Rn vi i

Rm a Avi i

e associarmos a matriz a composio das transformaes a seguir:

A = [T ]can = [I ]can [T ] [I ]can

can

onde - [I ]can a matriz formada com os vetores da base =

Av1

1

Av 2

Av r 2 ... r

distribudos como colunas, quadrada de ordem m. - [T ] uma matriz que possui mais linhas do que colunas (na verdade ela mxn), e na diagonal principal da sua submatriz quadrada de ordem n, esto distribudos os valores singulares. - [I ] a matriz formada com os vetores da base = can

v1 1

v2

v r distri 2 ... r

budos em linha, quadrada e possui ordem n. Estas matrizes de transformaes descritas acima so as matrizes que desejvamos obter no comeo, e elas representam Q , e V t , respectivamente.

Exemplo 2.5.7:

1 1 Seja A = 1 0 e AtA = 1 1

3 0 0 2 como foi visto no exemplo anterior.

Quando determinarmos os autovalores teremos:

1 = 3 e v1 = (1 0)t

2 = 2 e v 2 = (0 1)t = { (1 0 ) , (0 1) } (1 1 0 ) = Av1 , Av 2 , w3 = , 1 2 3

(1

0 1) 2

,

(1

2 1) onde w3 o 6

complementar para que a base gere o espao tridimensional , e determinado pelo processo de Gram-Schimidt.

2 2 1 3 3 1 0 A = 1 0 = 3 3 1 1 3 3 2 2 Exemplo 2.5.8:

6 6 3 6 3 0 6 6 0

0 2 0

1 0 t 0 1 = Q V

14

18 5 24 5 Seja A = 4 3 e AtA = 24 5 32 5

52 36 36 73

1 = 100 e v1 = ( 3 5 4 5)t 2 = 25 e v 2 = (4 5 3 5)t ( 6 0 8) , = Av1 , Av 2 , w3 = 1 2 10

(0

1 0) , 5

( 4

0 3) onde w3 o 5

complementar para que a base gere o espao tridimensional , e determinado pelo processo de Gram-Schimidt.

18 5 24 A= 4 24 5 32

5 3 5 0 4 5 3 = 0 1 0 5 4 5 0 3 5

10 0 3 5 4 5 t 0 5 4 5 3 5 = Q V 0 0

3-Matriz Definida Positiva

Uma matriz A de ordem n n definida positiva se para qualquer vetor x 0 tem-se a relao:

x Ax > 0T

Teorema 3.1: Seja A uma matriz simtrica, isto , aij = a ji . Dizemos que A positiva definida se e somente se todos os autovalores so positivos. Dem:

"" Como A PD ento XtAX = Xt X = (XtX) > 0 "" Se autovalor de A ento AX = X XtAX = Xt X = XtX > 0

Teorema 3.2: Se A simtrica positiva definida ento existe uma nica matriz L com elementos diagonais positivos tal que A = LLt . Dem: A prova do teorema feita por induo. Observaes: T i) A matriz A positiva definida se x A x > 0 para qualquer vetor x diferente de zero. ii) Os elementos diagonais de uma matriz definida positiva so sempre positivos, ou seja,

eiT A ei = a ii > 0

15

sendo ei vetor com elemento igual a 1 na posio i e o restante igual a zero. iii) A matriz semidefinida positiva se pelo menos um autovalor zero e os demais so positivos. Exemplo 3.3: Seja A =

2 2 1 , temos que det( A I ) = 1 1 2

1 = 2 4 + 3 = 0 2

Segue-se: 1 = 3 e 2 = 1 . Portanto, a matriz A positiva definida. Exemplo 3.4: Seja B =

1 2 1 2 2 , temos que det(B- I) = 2 1 = 2 3 = 0 2 1 Logo: 1=3 e 2 = -1 e v = (1 1) autovetor de B .Logo, B no positiva definida.

Teorema 3.5: Seja A uma matriz simtrica.Toda transformao : R n R n tem uma base de ortogonal formada por autovetores de . Dem:

"" xtAx > 0 x n ; x 0. Logo vale para os autovetores, e pelo teorema 1, A positiva definida. "" Seja = {x1,x2,........,xn} uma base de autovetores de A. Seja X 0 tal que X = a1x1+.....+anxn AX = a1Ax1+.....+anAxn = a1 1 x1+.....+an n xnt XtAX = (a1x 1 +.....+anx tn )( a1 1 x1+.....+an n xn)2 = a 1 1 +.....+a 2 n > 0 n

Definio 3.6: Uma submatriz principal de A de ordem n uma matriz quadrada de ordem i, onde i < n, onde so consideradas as primeiras i-simas linhas e i-simas colunas de A. Teorema 3.6.1: Toda submatriz principal de uma matriz positiva definida positiva definida. Dem: XtAiX com X R i e Y R n tal que Y = 0. Como Y R n YtAY > 0 0 Portanto YtAY = XtAiX > 0

x

Teorema 3.6.2: Se A P.D. e retira-se a K-sima linha e a K- sima coluna continua PD.

16

Teorema 3.6.3: Se A P.D. ento a diagonal tem que ser positiva. Teorema 3.6.4: Se A P.D. , A pode ser reduzida forma triangular superior usando-se somente a terceira operao elementar com todos os pivs positivos. Teorema 3.6.5: Se A P.D. ento A tem decomposio LU, LDU e cholesky. Teorema 3.6.6: Uma matriz A admite a decomposio de cholesky se e somente se A P.D. Definio 3.7: Dizemos que uma matriz A uma matriz banda quando, aij = 0 se i - j > s, e aij = 0 se j - i > s com s < n. Quando A uma matriz banda e admite decomposio LU, L uma matriz semi-banda inferior do mesmo tamanho que A, e U semi-banda superior tambm do mes-mo tamanho que A. Se G uma matriz n x n triangular inferior (superior) com semi-banda de tamanho s, o custo para resolver GY = b por substituio de baixo para cima n s flops. Definio 3.4 8: O Envelope de uma matriz (simtrica) o conjunto dos pares ( i , j ) ; i > j tais que aik 0 para algum k < j.4-Norma de Vetores e Matrizes

Chama-se norma de um vetor x, em smbolo, x , qualquer funo definida num espao vetorial E, com valores em R, satisfazendo as seguintes condies: 1) x 0 e x = 0 e somente se x = 0; 2) x = x para todo escalar

;

3) x + y x + y (desigualdade triangular). Um espao vetorial E, onde est definida uma norma chamado espao vetorial normado. Tipos de Normas de Vetores: Seja = R n , e seja x = ( x1 , x2 ,...., xn ) t . Definimos ento: a) b)

x

= max xi ; norma do mximo.1i n

x 1 = xi ; norma da soma.i =1

n

c) x = d) x p

( x, x) ; norma usual ou euclidiana.

= ( ( x i ) p )1 / p ;i =1

n

como normas no R n .

17

O conjunto das matrizes n x n, com as operaes de soma de matrizes e produto de um escalar por uma matriz forma um espao vetorial E de dimenso n 2. Podemos ento falar em norma de uma matriz A E. Chama-se norma de uma matriz A, em smbolo, A , qualquer funo definida num espao vetorial E, com valores reais, satisfazendo as seguintes condies:

1)

A 0 e A = 0 e somente se A = 0;

2) A = A para todo escalar ; 3) A + B A + B (desigualdade triangular); 4) AB A B . Observe ento que no caso de matrizes, vale a mesma definio de norma de vetor. Tipos de Normas de Matrizes: Seja A uma matriz de ordem n. Ento, definimos: 1) 2)

A = max aij ; norma de linha.1i n j =1

n

A 1 = max aij ; norma de coluna.1 j n n i =1

n

3) A

F

=

ai, j

2 ij

; norma de Frobenius.

Exemplo 4.1:

3 2 1 Seja A = 6 3 4 . 1 2 1 Calculemos as normas A , A 1 , A F . Usando cada uma das definies dadas anteriormente, obtemos: a) A = max{ 3 + 2 + 1 , 6 + 3 + 4 , 1 + 2 + 1 } = 13 b) A 1 = max{ 3 + 6 + 1 , 2 + 3 + 2 , 1 + 4 + 1 } = 10 c) A F = (9 + 4 + 1 + 36 + 9 + 16 + 1 + 4 + 1)1 / 2 = 9 Exemplo 4.2:

0 .5 0 .2 0 .5 Seja B = 0.1 0 .6 0 .4 . 0 .3 0 .1 0 .0

18

Calculemos as respectivas normas B anteriormente, obtemos: a) B

, B 1 , B 2 . Usando cada uma das definies dadas

= max{ 0.5 + 0.2 + 0.5 , 0.1 + 0.6 + 0.4 = = 0.3 + 0.1 + 0.0 } = 1.2

b) B 1 = max{ 0.5 + 0.1 + 0.3 , 0.2 + 0.6 + 0.1 = 0.5 + 0.4 + 0.0 } = 0.9 c) B2

= (0.25 + 0.04 + 0.25 + 0.01 + 0.36 + 0.16 + 0.09 + 0.01 + 0.0)1 / 2 1.2083

Observe que nesse exemplo a soma de cada coluna possui o mesmo valor. Definio 4.3 (Norma Induzida de Matrizes): Seja ||.|| uma norma vetorial em Rn. A norma de uma matriz A induzida pela norma vetorial :

A = max Ax = maxx =1 x 0

Ax x

Proposio 4.4: Para quaisquer matrizes A, B quadradas e qualquer vetor x, temos: i) || Ax || < || A || || x || ii) || AB || < || A || || B || Dem: (i) imediato. Caso x 0, temos || A || > || A x || / ||x|| || A x || < || A || || x ||, se x = 0 temos 0 < 0. (ii) semelhante, basta ver que de i), para qualquer x 0, || ABx || / ||x|| < || A || || Bx || / || x || e portanto || AB || = max || ABx || / || x || < || A || max || Bx || / || x || = || A || || B || . Definio 4.5: Designamos por raio espectral de uma matriz A o valor :

( A) = max ionde 1, ..., n so os valores prprios de A.

i =1, 2 ,.....,n

Teorema 4.6: Seja A uma matriz quadrada. Para qualquer norma matricial ||.|| , temos : r(A) < || A || Para qualquer e > 0 existe sempre uma norma induzida ||.|| tal que: || A || < r(A) + e Ou seja, o raio espectral o nfimo do conjunto das normas induzidas de uma matriz.

19

5-Nmero de Condicionamento de uma Matriz

Seja o sistema linear Ax = b onde A irredutvel e b 0 .Suponha que o vetor independente b alterado por b + b e A permanece inalterado. A soluo exata do problema alterado dado por: A(x + x)=b+ b e como Ax = b pode-se obter um limite para x:

x 1 bA relao x = b implica em

b xMultiplicando as duas relaes anteriores chega-se a relao:

x b 1 x bSe perturbarmos a matriz A enquanto b mantido fixo tem-se a soluo:

( + )(x + x ) = bpor um processo similar chega-se expresso para o erro relativo.

x 1 x + x A quantidade

1 reflete a mxima mudana relativa possvel na soluo exata

para um sistema na soluo exata para um sistema linear com dados perturbados, portanto K ( ) = 1 onde K(A) o nmero de condicionamento de A. Das relaes anteriores pode-se chegar a:

x K ( ) || x ||

x e K ( )

b|| b ||

x + x

Estas relaes mostram que, se a mudana relativa muito grande para uma pequena perturbao em A ou b , ns sabemos que A mal condicionada. Propriedades sobre o nmero de condicionamento: (i) Sabemos que a norma da matriz identidade, para qualquer norma, vale 1. Logo I = AA1 e AA1 A1 A conclui-se que K ( A) 1 . (ii) Se a matriz A for multiplicada por um escalar , ento K (A) = K ( A) . (iii) K ( A) = K ( A 1 )

20

Observaes: O K ( A) uma medida mais eficaz para a verificao da singularidade de uma matriz que o determinante.Como exemplo,seja uma matriz diagonal de ordem 100 100 ,com todos elementos igual a 0,1. O determinante da matriz 10 100 , que um nmero pequeno e pode ser arredondado para zero em computadores digitais. J o nmero de condio da matriz igual a 1. O mal-condicionamento de uma matriz est associado proximidade da singularidade da matriz. Exemplo: Considere o sistema

ax1 + bx2 = c dx1 + cx2 = f

Uma matriz nada significa seno uma representao de um sistema de equaes lineares, como visto acima, o qual cada linha pode ser representada por um seguimento de reta em seu devido espao. A disposio destas retas que vai nos dizer se a matriz singular ou no, se um seguimento for mltiplo de outro, ou combinao linear dos demais a matriz ser singular, ou seja, ter variveis a mais que equaes e conseqentemente, no existir soluo para ele. Consideremos o caso bidimensional a que se refere o sistema acima, sua interpretao geomtrica pode ser dos seguintes tipos:

Matriz no-singular

Matriz singular

Matriz prxima singularidade

21

Definio 5.1: Magnificao Mxima para A

max mag ( A) = maxx 0

Ax = A induzida. x

Magnificao Mnima para A

min mag ( A) = minx0

Ax induzida x

Agora iremos definir algumas proposies sobre minmag e maxmag, para percebermos as interligaes que existem entre si e o que podemos aproveitar a obteno do nmero de condicionamento Proposio 5.2:

max mag ( A) =Dem:

1 min mag ( A 1 )Ax x = max y A y1

max mag ( A) = maxx0

= max

1 = A y / y1

min

1 1 = 1 min mag ( A1 ) A y y

Proposio 5.3 K(A) =

max mag ( A) min mag ( A) max mag ( A) = A max mag ( A 1 ) = A A 1 = K ( A) min mag ( A)

Dem: Exemplo 5.4: Seja A =

1000 999 , se calcularmos veremos que Det A = -1 999 998 998 999 , e Det A-1 = -1 1000

A inversa da matriz A 1 = 999

K1(A) = K (A) = (1999)2 3,99 x 106

Seja X = (1 1)

t

Logo Ax = A = 1 1997 A 1

1

1999

1

= 1999 = A

1 1997 A 1 = 1999, A 1 = 1 1999

22

A 1 x x

= 1999 mx

A 1 x x

1 ocorre para X = = mxA 1 1

. 6-Os Problemas que implicam em mal condicionamento6.1-Problema de Escala

O Problema de escala ocorre quando a matriz especifica possui uma discrepncia muito grande nas escalas de duas ou mais linhas diferentes, por exemplo se tomamos uma matriz que possui uma linha com os coeficientes muito grandes e a outra linha possui coeficientes muito pequenos, e precisamos trabalhar nela algum mtodo que necessite que exista interaes entre estas linhas (eliminao gaussiana, decomposio LU, ou Cholesky, etc...). No meio das interaes quando precisarmos realizar o pivoteamento, pode acontecer termos a diviso de um nmero muito grande p r muito pequeno e o valor em si explodir para um valor imenso (fora dos limites da mquina que realizar os clculos). Vejamos matematicamente como isto pode ocorrer.

1 0 x1 1 1 Seja A = 0 x = x = 1 2 Com A 1 = 0 1 / , logo teremos K 1 ( A) = K 2 ( A) = K ( A) = (1 / ) >> 1

1

0

1 0 Se b + b = b = 2 O erro relativo para este caso ser

b b

=

= 1 0 A x = b x 1

Vamos agora determinar a perturbao em X,

x

1 = =1 1 x

Como m. Ento existe uma matriz Q Rnxn e R Rnxm tal que Q

ortogonal e R = com R uma matriz triangular superior e A = QR.Dem:

R 0

~ ~ nxn nx(n-m) A um complemento qualquer para que a { R sendo A R nm matriz A se torne quadrada. Como A uma matriz quadrada ento pelo teorema 4 existem Q, R com Q ortogonal n-dimensional e R triangular superior n-dimensional, tal que A = Q RSeja

A = { A m

40

~ ~ A = Q R = Q R R = QR QR = { A m

(

) (

)

~ A { nm

Como conseqncia do teorema acima temos que o posto de A igual ao posto de R, ou seja, A e R possuem a mesma quantidade de linhas linearmente independentes. Se formos utilizar a decomposio por refletores sero gastos aproximadamente um nmero da ordem de n m 2 m 3 3 flops. Se m tender a ser muito maior que n ento o nmero de flops ser

n m2 .Continuando a desenvolver o mtodo dos mnimos quadrados para sistemas sem soluo nica: AX = b QRX = b QtQRX = Qtb RX = Q t b

{C

E ento denotaremos o vetor Qtb por C e escreveremos o mesmo do seguinte modo:

C m linhas C = d (n m) linhas Logo C RX ser um resduo ou uma diferena que deve ser minimizada. onde C RX = X =

C R d 0

C RX d 2 2

e

.C RX

2 2

= .C RX

2 2

+ .d2

2 2

Assim para encontrar o min AX b

basta descobrir o min C RX

2

= d

2 2

Exemplo 7.3.1: Resolva o problema de mnimos quadrados do sistema sem soluo abaixo.

3 2 Seja A = 0 3 e b = 4 4

1 2 4

Primeiramente temos que decidir qual o tipo de decomposio que iremos utilizar para obter a matriz R. Optaremos pela decomposio por reflexo porque neste tpico s se foi apresentado um exemplo.

3 Encontremos Q1 tal que Q1 0 = 4 X

1 0 0 Y

1 = X

2

= (3 + 0 + 4 ) = 5 Y = ( 5 02 2 2

0) t

41

1=

1

1 (a11 + 1 )

=

1 1 = 5 (3 + 5) 40 64 0 32 0 0 0 = 32 0 16

u (1) = X Y =

(3

0 4 ) - ( 5 0 0 ) = (8 0 4 )

1 0 0 1 (8 0 4) (8 0 4) t = 0 1 0 - 1 Q1 = I - 1(u (1)u (1)t ) = I 40 0 0 1 40 24 0 32 1 40 0 0 40 24 32 0 Encontrando Q1 aplicamos em A para descobrirmos A 2. 2 24 0 1 Q1 3 = 40 0 40 4 32 0 5 2 Q1 A = 0 3 e A2 = 0 4 32 2 80 2 1 0 3 = 120 = 3 40 24 4 160 4

3 4

Agora vamos zerar a segunda coluna desta nova matriz.

3 2 Q2 = 4 0 X Y2

2 = X

= (3 2 + 4 2 ) = 5 Y = ( 5 0 ) t

2=u(2)t

1 2 (a 22 + 2 )

=

1 1 = 5 (3 + 5) 401 0 1 0 1 - 40 64 32 1 24 32 32 16 = 40 32 24

=XY=

(3

4 ) t - ( 5 0 ) t = (8 4 ) t

1 Q2 = I - 2(u (2)u (2)t ) = I (8 4) (8 4) t = 40

0 0 1 0 0 40 1 Q2 = 0 = 0 24 32 40 0 Q2 0 32 24 0 0 40 24 0 32 3 2 5 2 1 1 R = Q2Q1A = 40 0 0 3 = 0 5 0 24 32 0 40 40 32 0 24 4 4 0 0 0 32 24 lgico que no preciso realizar esta ltima conta, pois quando encontramos 2 determinamos a matriz R, mas quem quiser tirar a prova real ver que a igualdade acima verdadeira.

42

5 2 5 2 Se R = 0 5 R = 0 5 0 0 Calculemos agora, que a matriz j esta decomposta, o mnimo erro para a soluo do sistema. C = Qtb = Q2Q1b

24 1 Q1b = 0 40 32 40 1 Q2Q1b = 0 40 0

32 1 152 19 5 1 40 0 2 = 80 = 2 40 0 24 4 64 8 5 0 0 19 5 1 0 0 19 5 19 5 24 32 2 = 0 3 5 4 5 2 = 62 25 32 24 8 5 0 4 5 3 5 8 5 16 25 0

Como C = , onde C um vetor bidimensional, ns temos 19 C = 62

C d

5 e d = ( 16 25) 5

Resolvendo o sistema RX = C por eliminao Gaussiana de baixo para cima:

5 2 x1 = 19 5 R= 0 5 x 62 5 2 x 2 = 62 25 ; x1 = 351 625Finalizando d2

= 16 25 o que no nos estabelece uma expectativa muito boa para a

resoluo de um sistema.

8-Autovalores e Autovetores

Seja T : R n R n uma transformao linear, se v 0 um vetor n-dimensional e Tv = v , ou seja, a aplicao desta transformao no vetor v desempenha o mesmo papel de uma constante multiplicada pelo vetor, ento diremos que v um autovetor associado ao autovalor . Agora se T uma transformao linear como faremos para determinar seus autovalores. Vamos desenvolver o seguinte raciocnio: Considere T : R n R n

X AX

Sabemos que

Tv = v TX = AX AX = X AX X = 0

43

AX (I ) X = 0 ( A I ) X = 0Como X um vetor no nulo, para a igualdade acima ser satisfeita necessrio que a matriz ( A I ) seja singular, ou seja,

det( A I ) = 0Proposio 8.1: Os autovalores de A e de At so iguais. Dem: Sabemos que det( A I ) = 0

( A I ) t = A t I t = A t I Mas det( A I ) = det( A I ) t det( A I ) t = 0 = det( A t I ) tambm autovalor de At.Proposio 8.2: Seja A uma matriz complexa e A *= ( A ) t . Se autovalor de A ento autovalor de A *. Dem:pela . proposio ..anterior

Av = v

6 74 4 8 A t u = u

( A t u ) = (u ) A * u = u autovalor de A*.

Corolrio: (Provm das duas proposies anteriores) Suponha A uma matriz real. Assim A* = ( A ) t = A t . Se A possui algum autovalor complexo, segue que um autovalor de At e portanto autovalor de A. Proposio 8.3: Se 1 2 ento v1 e v 2 , autovetores associados a 1 , 2 respectivamente, so linearmente independentes. Dem:

a1v1 + a 2 v 2 = 0 a1v1 = a 2 v 2 (1) a1T1v1 + a 2Tv 2 = 0 a11v1 + a 2 2 v 2 = 0 1 (a1v1 ) + 2 a 2 v 2 = 0 1 (a 2 v 2 ) + 2 a 2 v 2 = 0 ( 2 1 )a 2 v 2 = 0 Como 1 2 , segue que ( 2 1 ) 0 a 2 v 2 = 0 a 2 = 0 Substituindo em (1) temos a1v1 = a 2 v 2 a1v1 = (0) v 2 a1v1 = 0 a1 = 0 Logo v1 e v 2 linearmente independentes.Definio 8.4: Seja A uma matriz pertencente ao Rnxn da forma abaixo:

44

A11 0 A = ... 0

A12 A22 ...

A1n ... A2 n ... ... 0 Ann ...

Com A11 , A22 ,..., Ann sendo blocos ou sub-matrizes de A, diremos que A triangular superior por blocos e definimos det A = det A11 det A22 ... det Ann . A definio anloga para triangular inferior por blocos. Exemplo para a definio 8.4:

1 1 1 1 Seja A = 0 0 0 0 1 1 A11 = 1 1 e det A11 = 2 1 1 A22 = 1 1 e det A22 = 2

1 2 3 7 1 1 1 1 1 2 A12 = 3 7 e det A12 = 1 0 0 A21 = 0 0 e det A21 = 0

Assim teremos que det A = det A11 det A22 = (-2) x (-2) = 4. Definio 8.5.1: Seja A uma matriz pertencente ao Rnxn ,dizemos que A simples se existir uma base {v1 , v 2 ,..., v n } do Rn formada por autovetores de A. Caso contrrio diremos que A defectiva. Exemplos: a) A =

0 1 0 0

Se calcularmos o det( A I ) = 0 teremos

det 0

1 = 2 = 0 = 0 x y=0 y t

0 1 x Av = v 0 0 y = 0

Assim a matriz A s possui um nico autovetor que v = (1 0 ) , e ele sozinho no gera o espao bidimensional. Logo A defectiva.

45

b) A =

0 0 =0 0 0

= {(1 0)

(0 1)}

A uma matriz simples. Definio 8.5.2: Dizemos que se A simples ento A digonalizvel. Proposio 8.6: Se A tm n autovalores distintos ento A simples. Dem: Decorre diretamente da proposio 8.3. Definio 8.7: Um polinmio dito ser mnico se o coeficiente do elemento do maior grau 1, ou seja, o polinmio possui o seguinte formato:

P ( ) = a n n + a n 1n 1 + ... + a11 + a 0 {1

Definimos juntamente a matriz companheira de P, que a matriz:

0 0 0 A= M 0 a 0

1 0 0 M 0 a1

0 1 0 M 0 a2

0 0 L 0 M 1 O 0 1 a n 1 L 0 K

A matriz companheira tem uma particularidade muito curiosa e especial, que acaba por interligar a matriz com o polinmio mnico: det( A I ) = (1) n P ( ) . Dem: A demonstrao ser feita atravs de induo em n, para n 2.

Se n = 2 ento a matriz companheira ser A=

0 a0

1 a1 = [( )( a1 ) a 0 1] = 2 + a1 + a0 = P( ) a1 1

det( A I ) = a 0

Suponha verdadeiro para n = k -1, provemos que vale para n = k.

46

0 0 det( A I ) = det M 0 a 0

1 0 M 0 a1

0 1 M 0 a2

0 L 0 M 1 O 0 1 a k 1 L 0 K 0

Iremos agora fazer com que a ltima linha da matriz acima receba ela menos a penltima.

Lk Lk Lk 1 0 0 det M 0 a 0 1 0 M 0 a1 0 1 M 0 a2 1 M = O 0 1 L 1 a k 1 0 0 K L 0 0

Aplicaremos Laplace na ltima coluna. = (1) n + ( n 1) 1 (n 1 + a n 2 n 2 + ... + a1 + a 0 ) + (1) n + n (1 a n 1 ) n 1 mpar = (1)} 2 n 1

par}

1 (n 1 + a n 2 n 2 + ... + a1 + a0 ) + (1) 2 n (1 a n 1 ) n 1

= (1) n (n + a n 1n 1 + a n 2 n 2 + ... + a1 + a 0 ) = (1) n P ( ) Exemplo 8.8: Dado o polinmio mnico P( ) = 4 33 + 22 7 + 10 encontre sua matriz companheira e prove que det( A I ) = (1) n P( ) . A matriz companheira fcil,

0 0 A= 0 10

1 0 1 0 0 0 7 2

1 0 det( A I ) = det 0 0 10 7

0 0 1 3

0 0 0 0 1 2 3

47

primeiro vamos repetir os passos dados na demonstrao anterior, vamos efetuar uma soma de linhas L4 L4 + L3 e depois vamos aplicar Laplace na ltima coluna.

1 0 det 0 0 10 7 1 = (1) 3+ 4 1 det 0 { a 34 10 7 0

0 0 2

0 0 1 4 1 0 0 1

1 + (1) 4+ 4 (4 ) det 0 0 2

[10 + 2 (2 ) + 7 ] + (3 )(4 ) = 4 33 + 22 7 + 10 .Fazendo uma observao, todos os autovetores associados a matriz companheira so da forma v = 1 2 K n 1 sendo seu respectivo autovalor associado.

(

)

Agora que o bsico sobre a teoria dos autovetores e dos autovalores j foi exposto, va mos apresentar realmente a parte que mais nos interessa e faz parte do desenvolvimento primordial do curso. Como podemos determinar os autovalores e seus respectivos autove tores por mtodos computacionais? Nosso prximo tpico ir apresentar justamente estes mtodos.

8.1-Obteno de autovalores por Mtodos Computacionais 8.1.1-Mtodo da Potncia

Seja A Rnxn, suponhamos que A seje simples existe uma base = {v1 , v 2 ,..., v n } que gera o Rn, de autovetores associados a 1 , 2 ,..., n respectivamente. Suponhamos que 1 2 ... n , ou seja, que os autovalores estejam distribudos em ordem decrescente em mdulo. Se 1 2 diz-se que 1 dominante em relao a 2 e que v1 vetor dominante em A. Tome q Rn qualquer (pode-se chutar qualquer vetor n-dimensional) e defina a seguinte seqncia: q1 = Aq k = 1,

q 2 = Aq1...

q n +1 = Aq n

k = 2, ... k = n.

Coloquemos a seqncia (q n ) = A n q ,garantimos que dependendo do chute est seqncia ir convergir para um mltiplo do autovetor dominante v1 . Este mtodo conhecido como mtodo da Potncia e um mtodo interativo, ou seja, no se encontra o valor exato do que se procura, mas faz-se o valor convergir para ele. Surge-nos agora uma nova questo. Como ou porque esta seqncia converge justo para este autovetor? Vamos ver o motivo.

48

Por hiptese, existe uma base = {v1 , v 2 ,..., v n } de autovetores de A que gera o Rn. Desta forma o nosso vetor q poder ser escrito da seguinte maneira:

q = a1v1 + a 2 v 2 + ... + a n v nSe aplicarmos a matriz A no vetor q teremos que

Aq = a1 Av1 + a 2 Av 2 + ... + a n Av nComo {v1 , v 2 ,..., v n } so autovetores associados a 1 , 2 ,..., n ento

Aq = a11v1 + a 2 2 v 2 + ... + a n n v nSe ns analisarmos o ensimo termo da nossa seqncia veremos que

(q n ) = A n q = a1 (1 ) n v1 + a 2 ( 2 ) n v 2 + ... + a n ( n ) n v nComo por hiptese 1 dominante vamos colocar este termo em evidncia e tender nossa seqncia para o infinito

A n q = (1 ) n [a1v1 + a 2Se n

( ) n ( 2 ) n v 2 + ... + a n n n v n ] (1 ) n (1 )( n ) n ( 2 ) n v 2 + ... + a n vn ] (1 ) n (1 ) n 13 2 13 2tende.. a .. zero

A n q = (1 ) n [a1v1 + a 2A q = (1 ) [a1v1 ]n n

tende..a .. zero

Finalmente v1 =

( A n q) . a1 (1 ) n

O nico problema agora descobrir o termo do denominador, pois ns ainda no sabemos quem o autovalor dominante. O que vamos fazer o seguinte, a cada interao que obtemos um novo termo da seqncia digamos q j , que um vetor, tomemos a coordenada de maior valor absoluto e dividiremos nosso vetor por ele. Esta coordenada ns denominaremos de j . Quando j tender ao infinito teremos que j tender a ser o autovalor dominante de A e q j

j =1

j

tender a ser um mltiplo do autovetor dominante.

O custo de cada interao em flops de n 2 , que provm da multiplicao de uma matriz quadrada de ordem n por um vetor n-dimensional, o custo final depois de m interaes ser da ordem de m n 2 . Exemplo 8.9: Seja A =

9 1 1 2

49

Primeiramente vamos calcular os autovalores da forma tradicional, que aprendemos em lgebra Linear II.

1 9 = 0 (9 )(2 ) 1 = 0 2 11 + 17 = 0 det( A I ) = 0 det 1 2 1 = 9,140055..., 2 = 1,859945...(para encontrar estes valores basta utilizar algum mtodo interativo de obteno de razes de um polinmio, vistos em Clculo Numrico: Mtodo de Newton, Mtodo da secante, Mtodo Regula Falsi, etc...). Agora vamos usar o mtodo da potncia para ver se o que encontramos mesmo o maior autovalor. vamos tomar como nosso chute inicial q = 1

1

9 Aq = 1 9 Aq1 = 1 M

1 1 10 1 = 1 = 10 e q1 = Aq = 1 0,3 2 1 3 1 1 9,3 1 = 2 = 9,3 e q 2 = Aq = 2 0,172 2 0,3 1,6 Aq9

10 = 9,140055 e q10 =Exemplo 8.10:

10

1 = 0,140055

3 1 0 Seja A = 1 3 0 0 0 2 Analogamente ao exemplo anterior vamos calcular os autovalores da forma tradicional, para depois utilizarmos o mtodo interativo da potncia.

0 3 1 det( A I ) = 0 det 1 3 0 = 0 (3 ) 2 (2 ) (2 ) = 0 (2 ) 0 0 2 2 2 [(3 ) 1] = 0 (2 ) [ 6 + 8] = 0 1 = 2, 2 = 4, 3 = 2 . 1 vamos tomar como nosso chute inicial q = 1 1 3 1 0 1 Aq = 1 3 0 1 = 0 0 2 1 2 1 Aq = 1 2 1 = 2 e q1 = 1 2 1

50

3 1 0 1 Aq1 = 1 3 0 1 = 0 0 2 1

2 1 Aq1 = 1 2 2 = 2 e q2 = 2 2 1

Percebemos que voltamos ao nosso chute inicial o que significa entramos em um ciclo vicioso que no nos levar em lugar algum,isso se d, pois o vetor que pegamos combinao linear dos outros dois autovetores que no so dominantes. Com isso ns vimos que o sucesso da nossa interao depende do vetor tomado no inicio, que est fora da nossa capacidade predizer se foi bom antes das interaes efetuadas. Precisamos agora tomar outro vetor inicial e comear tudo novamente.

2 vamos tomar dessa vez q = 2 1 3 1 0 2 Aq = 1 3 0 2 = 0 0 2 1 8 1 Aq = 1 8 1 = 8 e q1 = 1 2 1 2 4 1 Aq1 = 1 4 2 = 4 e q2 = 2 1 1 4

3 1 0 1 Aq1 = 1 3 0 1 = 0 0 2 1 2 3 1 0 1 Aq 2 = 1 3 0 1 = 0 0 2 1 4 1 n n 4, q n 1 0

4 1 Aq 2 = 1 4 3 = 4 e q3 = 3 1 2 1 8

8.1.2-Mtodo da Potncia Inverso

O mtodo anterior cria uma seqncia de vetores que converge para o autovetor dominante, que est associado ao autovalor de maior valor em mdulo. Este prximo mtodo ir nos dar justamente o contrrio, o autovalor com o menor valor absoluto. Vamos raciocinar juntos:

Av = v v = A 1 v 1 v = A 1v 1 v = A 1v

51

Se aplicarmos o mesmo mtodo anterior criando uma seqncia, s que usando agora a matriz inversa, isso far com que o coeficiente 1 se torne o maior possvel e assim o denominador tender a ser o menor possvel, logo ser o menor autovalor de A. O custo final em flops de m n 2 para encontrar o autovalor pelo mtodo interativo mais n 3 para a inverso da matriz (dependendo do algoritmo utilizado). Exemplo 8.11: Seja A, a matriz do exemplo anterior que ns j sabemos seus autovalores.

3 1 0 A = 1 3 0 com 1 = 2, 2 = 4, 3 = 2 . 0 0 2 Vamos agora calcular a inversa de A.

0 3 1 0 1 0 0 1 1 3 0 1 3 0 L3 L3 3 0 0 1 0 1 3 0 0 1 0 L2 L2 L1 1 3 L L1 (2) 0 0 0 2 0 0 1 1 0 1 0 0 1 2

0 0 1 1 3 0 1 3 0 1 1 3 0 1 3 0 L L2 0 1 0 18 38 0 L1 L1 + 2 0 L2 0 8 3 0 1 3 1 83 3 0 0 0 1 0 0 1 2 0 1 0 0 1 2 0 1 0 0 3 8 1 8 0 1 0 1 8 3 8 0 0 0 1 0 0 1 2 0 3 8 1 8 A = 1 8 3 8 0 0 0 1 2 1

0 vamos tomar como nosso chute inicial q = 1 1 0 0 3 8 1 8 A q = 1 8 3 8 0 1 = 0 0 1 2 1 1

18 1 16 Aq = 3 16 3 8 1 = 1 2 e q1 = 1 1 2 1 6 128 3 256 Aq1 = 9 512 9 128 2 = 1 2 e q 2 = 2 1 2 1

0 1 16 3 8 1 8 A q1 = 1 8 3 8 0 3 16 = 0 0 1 2 1 1

M

52

0 0 1 n n , q n 0 3 = 2, v3 = 0 . 2 1 1 O problema agora o seguinte, com os dois mtodos apresentados anteriormente conseguimos encontrar o maior e o menor autovalor da matriz A. Mas e os outros? Como faremos para determinar os autovalores que faltam? As perguntas anteriores podem ser esclarecidas assim que definirmos algumas proposies sobre autovalores e matrizes. Proposio 8.12: Se autovalor de A e p um nmero real ento p autovalor de A pI. Dem: Provemos que det(( A pI ) ( p) I ) = 0

det(( A pI ) ( p) I ) = det( A pI I + pI ) = det( A I ) = 0Teorema do Disco de Gersh Gorin: Cada autovalor da matriz A, pertence a pelo menos um disco aii ri . Dem: Seja um autovalor de A e v t = ( x1

x2

... x n ) o autovetor associado a . E seja

xi = mx.1 j n. x j .Como Av = v xi = ai.1 x1 + ai.2 x 2 + ... + ai .n x n (ou seja, o autovalor operado com a i-sima coordenada do autovetor v , que foi determinada acima, igual i-sima linha da matriz A operada com o autovetor v ).

j =1; j i

(a

n

ij

x j ) = xi (aii xi ) = ( aii ) xin n

aii xi aij x j ( aij ) x jj =1 j =1

a ii aij = ri .j =1

n

Em palavras o que este teorema nos diz que para cada linha, a distancia entre algum autovalor e o elemento de interseo entre a diagonal principal e a linha,deve ser menor que a soma dos mdulos dos outros elementos da linha. Veja bem que para cada linha existe um intervalo que pode ou no conter algum autovalor, mas a unio dos n -intervalos obtidos ter que conter, obrigatoriamente, todos os autovalores da matriz A. Exemplo do teorema:

3 2 1 3 .2 . + .1 = 2 + 1 = 3 0 6 Seja A = 0 6 3 6 0 + 3 = 0 + 3 = 3 3 9 1 1 0 0 .1 + .1 = 1 + 1 = 2 2 2

53

Por fim tiramos a concluso de que 3 9 . Agora vejamos um artifcio que nos d uma maneira de determinar os outros autovalores. Depois que tivermos aplicado o mtodo da Potncia ou mtodo da Potncia Inverso e obti vermos o maior ou o menor autovalor da matriz A, respectivamente, escolheremos ao acaso um nmero P pertencente aos reais (mas lgico, como temos conhecimento do teorema anterior no vamos escolher um nmero que saia do disco de restrio final) e vamos utilizar a proposio 8.12 da seguinte maneira: Definamos a seqncia,

(q n ) = ( A pI ) n qE vamos fazer com que a seqncia tenda ao infinito, desta maneira encontraremos o ~ ~ maior autovalor de ( A PI ) digamos mas pela proposio 2.12, = P para algum autovalor de A. Este processo repetido at que se determine todos os autovalores da matriz A.

Exemplo 8.13:

3 1 0 Seja A = 1 3 0 0 0 2 Ns j sabemos pelo mtodo da Potncia que o maior autovalor da matriz acima = 4 . (exemplo 8.10) E sabemos mais, pelo mtodo da Potncia Inverso que o menor autovalor = 2 . (exemplo 8.11) Por fim pelo Teorema do Disco de Gersh Gorin aproveitamos que = { 2} 2 4. Vamos tomar P = 4 e aplicar a teoria.

3 1 0 1 0 0 1 1 0 0 - 4 0 1 0 = 1 1 0 A -PI = 1 3 0 0 2 0 0 1 0 0 6 1 Vamos chutar o vetor inicial como v = 3 0 1 1 0 ( A pI )q = 1 1 0 0 0 6 1 3 = 0 4 1 ( A pI )q = 1 4 1 = 4 q1 = 1 0 0

54

1 1 0 ( A pI )q1 = 1 1 0 0 0 6

1 1 = 0

2 1 ( A pI )q1 = 1 2 2 = 2 e q 2 = 2 0 0

1 n n 2, q n 1 p = 2 4 = 2 = 2 . 0 O que acabamos de fazer o mesmo mtodo da Potncia utilizado anteriormente s que agora com uma translao da matriz A. Agora iremos definir o que uma matriz diagonal dominante e o que esta teoria nos traz de bom. Definio 8.14: Diremos que a matriz A diagonal dominante se todos os elementos da diagonal principal so maiores em mdulo que a soma dos mdulos de sua respectiva linha. Teorema 8.15: Toda matriz diagonal dominante inversvel. Dem: ( ) aii

M

aj =1

n

ij

= ri (pelo Teorema do Disco de Gersh Gorin)

ri aii ri aii ri aii + riSe aii > 0, como A diagonal dominante segue que aii >

aj =1

n

ij

= ri aii ri > 0

> 0.Se aii < 0, como A diagonal dominante segue que aii >

aj =1

n

ij

= ri ri < 0

aii + ri < 0 < 0.Logo temos que 0 , autovalor de A A inversvel.

8.1.3-Quociente Radial

Seja A pertencente ao R nn e q R n . Se q um autovetor de A ento Aq = q para algum R (definio de autovalor), caso contrrio, seja r = Aq q o resduo da diferena para que a igualdade seje satisfeita. Pretende-se encontrar o mnimo deste resduo, utilizando-se do mtodo dos mnimos quadrados associado norma Euclidiana usual (norma 2). Vejamos como podemos proceder em nossos clculos.

55

r ( ) = { q Aq r ( ) = Y qMinimizando r ( ) min( r ( ) 2 ) 2 = minY

(y

qi ) 2 i =1 14 244 4 3i f ( x)

n

Pelos procedimentos do clculo devemos derivar a funo f(x) e igual-la a zero.

f ( x) = 0 2qi ( y i qi ) = 0i 1

n

/ 2[(qi y i ) ( qi qi )] = 0

n

(qi y i ) (qi qi ) = 0 (qi y i ) = (qi qi )i 1 i =1 i 1 n i =1 n

i 1 n

n

=

(q y ) (q q )i =1 i i i 1 n i i

n

=

q t Aq qt q

denominado quociente radial associado a q e a A, se q um autovetor e o autovalor associado a q temos que r ( ) = 0, seno quando aplicamos o quociente radial , nsiremos minimizar o resduo e assim nos aproximamos cada vez mais do autovalor. Iterao do Quociente Radial Este mtodo uma variante do mtodo da Potncia Inverso. Toda vez que calculado q j , o quociente radial usado como translao na interao seguinte, da seguinte forma:

j +1 =E definimos a translao abaixo:

q j Aq j qj qjt

t

( A j +1 I )q j +1 = q j Pode-se simplificar tomando j +1 = q j +1e tomando-se q 0 tal que q 0 2 = 1 tem-se que

2

q j q j = 1 logo:t

j +1 = q j t Aq jNo garantida a convergncia da deste mtodo mas a experincia nos diz que quando ele converge, isto se d rapidamente.