Métodos de Solução de Problemas de Auto-Valor Os métodos de solução em consideração podem ser sub-divididos em quatro grupos, correspondentes à propriedade

Métodos de Solução de Problemas de Auto-Valor

MK

rp

nrMKp

MKp

rr

rrrrr

a associado restrito problema

ésimo- do ticocaracterís polinômio o é onde

1 ..., ,1 ;det

e

det

ticoscaracterís polinômios dos Sturm de

Sequência da ePropriedad a empregam que Métodos D)

MKp

p i

det onde

0

Polinomial Iteração de Métodos C)

iii MK Vetorial Iteração de Métodos A)

, ..., n, iλ

IMK

in

TT

1diag e ..., , onde

e

çãoTransforma de Métodos B)

1

qqq

MK

, ..., ,, autopares primeiros dos cálculo o ,particular em e,

valor-auto de problema do solução a Seja

11

Os métodos de solução em consideração podem ser sub-divididos em quatro grupos, correspondentes à propriedade básica que é usada como base do algorítmo de solução

Métodos de Solução de Problemas de Auto-Valor

iT

iiT

i

ii

i

KM

MK

ii

i

i

;1

usando calculadoser pode conhecido,for Se

0

resolvendo calculadoser pode conhecido,for Se

Todos os métodos de solução têm que ser iterativos por natureza porque, basicamente, a

solução do problema de auto-valor [K]{} = [M]{} é equivalente a calcular as raízes do

polinômio p(), cuja ordem é igual à ordem das matrizes [K] e [M].

Embora iteração seja necessária para a solução de um auto-par (i,{i}), deve ser notado

que uma vez que um dos elementos do auto-par tenha sido calculado, pode-se obter o outro

elemento sem que seja necessária uma iteração adicional:

Métodos de Iteração VetorialIteração Inversa

kX

MX

MX

XMX

XX

, ..., kXMX

X

k

T

k

T

k

kk

kk

quando

que se- tem, 0 seja,ou , a

ortogonalseja não que desde onde,

21, K

dado

Básico Algoritmo

11

111

1

11

11

1

1

a) ITERAÇÃO INVERSA

A técnica de iteração inversa é muito eficaz para calcular um auto-vetor e, ao mesmo tempo, o

auto-valor correspondente. Assume-se que [K] seja positiva definida, enquanto que [M] pode

ser uma matriz diagonal, com ou sem elementos nulos, ou uma matriz de banda. Se [K] é

somente positiva semi-definida, um “shift” deve ser usado antes da iteração.

k

XMY

Y

YX

YY

YX

YXX

XMY

, ..., kYX

XMY

X

kk

T

k

T

k

kk

k

T

k

k

T

kk

kk

kk

quando

, e

0 que desde onde,

21, K

dado

eficiente) (mais Modificado Algoritmo

INVERSA ITERAÇÃO a)

1111

11

11

11

11

11

11

1

11

1

11

11

11

1

21k

1

k1

1k1

11

1

:se- temiteração, última afor Se

maior.ou dígitos,- de será então, vetor,-auto

do precisãoA dígitos.-2 de precisão com requerido é

valor-auto o quando ,10 onde ,

quando assumida é iaconvergênc , Se

l

T

l

l

l

s

kk

YX

X

X

l

s

s

toltol

X


TT l

Tln

lT

lT

ll

Tln

llTl

T

kk

TT

n

kk

kk

eZZ

Z

Z

ZZ

I

ZX

, ..., kXMX

1lim

121111

n21

211

T1

1

21

1

0,...,0,1 ,...,,1

... Se

1,...,1,1

se-obtém (I) Usando.1,...,1,1 agora, Seja,

(I)

se-obtém , M ; K relações as Usando

vetores-auto dos ortormal matriz a é ,...,, onde

;

Seja

21, K

elementos) dos ntoescaloname o iando(negligenc

é inversa iteração na usada lfundamenta equaçãoA


.vetor -auto ao converge iteração devetor

o erápidament quão determina que para de relativa magnitude a é

, se Portanto, adicional. iteração cada em razão a com menos

pelo fazem o assim zero, a tender devem que em elementos Aqueles

.0,...,0,1 ,...,,1

: iteração de vetor mo tambémmostrada é iaconvergênc de razãoA

. é iaconvergênc de razão a e linear, é iaconvergêncA

,1 caso, este para se,- tem,

ia,convergênc de definição a Usando

1

21

2121

1

1lim

121111

1

21

2

1

21

211lim1lim

l

TT l

Tln

lT

lT

ll

l

l

l lp

k

k l

Z

eZZ

Z

eZ

eZcp

XX

XXc


. à igual razão com linear, é tambémiaconvergêncA

quando

múltiplo,ou simplesvalor -auto um para Portanto,

.

, Para

.

:Rayleigh de quociente pelo iterativo, método no obtida, foi para oaproximaçãA

. é iteração de vetor do iaconvergênc de razão a e

,...,,1,...,1,1

que se- tem,... ... múltiplos, valores-auto de caso No

. que assumido Foi

211

11

1

1

21

1

1211

1

11

11

1

11

1111

n1mm21

21

m

l

n

i

li

n

i

li

l

kT

k

kT

kk

m

Tln

lm

T

l

lλZρ

Z

lk

ZZ

ZZZ

λ

Z


kX

X

XX

XX

, ..., kXX

X

nk

nT

k

T

k

kk

kk

quando

0M que desde onde,

K

21, KM

dado

FRENTEPARA ITERAÇÃO b)

1

1

11

11

1

1

nn

ln

l

T

l

ln

T

k

T

k

kk

k

T

k

k

T

kk

kk

kk

c

kXλYX

X

Y

YX

YY

YX

YXX

XY

, ..., kYX

XY

1

1

1

1

11

1

11

1

111

11

1

11

em resulta K1M problema

no iaconvergênc de análise da resultados os Aplicando

quando , e

0 que desde onde,

K

21, M

K

eficiente) (mais oalternativ Algoritmo

Métodos de Iteração VetorialIteração para Frente

ni

η

MMK

MMMMK

MK

i

i

n

,...,2,1 ,

expressão pela original, problema do valores-auto os com osrelacionad são valores

-auto os e original, problema do aqueles iguais são modificado problema do vetores-auto Os

.

ou ,

problema ao aplicado shift"" um Considere

., o e , o não quepar -auto outro para iaconvergênc aobter para b)

ou ia;convergênc aacelerar a)

:para Vetorial Itreração em utilizado é Shifting""

VETORIAL ITERAÇÃO EM SHIFTING"" c)

i

i

n11

Métodos de Iteração Vetorial“Shifting” em Iteração Vetorial

então

21 ,

:absoluto valor em menor, o Seja

.,...,2,1 , 0 hipótese,por onde,

1 ...

1

1

distintos são valores-auto os todosque

assumindo e inversa iteração doConsideran

Seja


222

21

1

r,...,n; i, i

ni

Z

I

MMK

ir

r

i

n

Tl

TT

maior.for que o , ou , ou

i.e. magnitude, emmaior é que

pelo adeterminad é iaconvergênc de razãoA

. para converge iteração de vetor o que

dosignifican ,Z portanto, iteração, Na

.qualquer para ,1 onde

1

11

r

1l

1

1

1

1

r

r

r

r

jr

r

jr

l

n

r

l

r

r

l

r

r

l

r

l

cc

e

rj

Z


. a entecorrespond

espaço-sub no está que vetor

um para ocorre iaconvergênc a e

é iteração de vetor do iaconvergênc de

razão a,... se b)

maior;for que o

,ou ,

é , para converge

de perto mais para que Rayleigh, de

quociente do iaconvergênc de razão a a)

:queconcluir se-pode ente,Adicionalm

max 1,...,1,

1-mr1rr

2

1

2

1

r

j

rmrrrj

r

r

r

r

rr

λ

μλ

μλc

μλ

μλ

μλ

μλ

μλλ

MKp det

1

2

r

1 2 354

6

2

1



shift. o com problema do absolutos) valores

em medidos (ambosvalor -automaior pelo

valor-automaior segundo do razão a é que

por dada é iaconvergênc de razãoA

onde

,K problema do

valor -automaior ao ecorrespond

que vetor o para converge shift com

frente para iteração na iteração, de vetor O

max

max todos

j

μλ

μλ r

μλμλ

MM

μλ

j

p j p

iij

j

FRENTEPARA ITERAÇÃO EM SHIFTING"" c)

MKp det

6

5r

1 2 354

6

5

251

6

Métodos de Iteração Vetorial“Shifting” em Iteração para Frente

k

XMY

YX

YY

XYX

YXX

XMY

,..., , kYXMXK

X

XMYX

ikik

k

T

k

kk

k

k

T

k

k

T

kk

kk

kkk

quando

e

agora, onde,

21

)0 e(usualment dado

dado

11

11

11

11

11

11

1

1

111

RAYLEIGH DE QUOCIENTE DO ITERAÇÃO d)

Cúbica iaConvergênc

1

componente primeira à relação em doNormalizan

1

então se,Obtém

1 e " de ordem da" onde

... 1

3331

1131221

21

11

11

1

ε ... οε οε οZ

λλ

εο ...

λλ

εο

λλ

εο

εοZ

Z

ε

Z

ZZZ

ZZZ

ZZIZ

T

l

n

Tl

l

Tl

k

kT

k

kT

kk

kkk

Métodos de Iteração VetorialIteração do Quociente de Rayleigh

nip

ppP

P

iT

k

nk

k

kk

,...,2 , 0 que se-Necessita

,...,,

. calculadovetor -auto o é coluna

primeira cuja ortogonal matriz uma se-achando

daestabeleciser pode deflação de estável matriz Uma

K

padrão

forma navalor -auto de problema o Considere

iteração. de vetores

osou matrizes asr deflaciona se-necessita

autopar, mesmo o para novamente dê se não

iaconvergênc a queassegurar Para calculado.

sido tenha,autopar o que Suponha

2

MATRICIAL DEFLAÇÃO e)

deflação. de processo no

osintroduzid serão acumulação de erros forma, outra de

pois, precisão alta com calculadosser que têmvetores

-auto os que é matricial deflação da mdesvantageA

e.propriedad esta destrua não que

ação transformuma desejada seria banda, de é Como

ação. transformde apropriada matriz umaconstruir para

utilizadasser podem técnicas váriase única, é não

que se- tem, por de

vetores-auto os denotando disto, Além . exceto

, de sautovalore mesmos os ter deve

ia,consequênc em e, de valores-auto mesmos

os tem que é importante ponto O

0

0

se- tem, 1 hipótese,por Como,

i

1

1

K

P

P

PKP

KK

K

PKP

KPKP

ii

T

k

T

TkT

kT

k

Métodos de Iteração VetorialDeflação Matricial

111

111

1

11

11 x

11

11

11

11

~ K :fica inversa

iteração de método o e calculados já vetores-auto os

varre"" que matriz a Defina

0

se- tem, que notando

e , por ndomultiplicaPré

onde

:vetores-auto estes a ortogonalseja

que tal Ache dado. , Seja .calculados

sido tenham..., , , que Suponha

XMXSMX

MΦIS

XMΦIXX

XMΦ

XMΦXMΦ

IΦMΦ

MΦ

,....,Φ

XXX

M

XX

mk

Tmmm

Tmmm

Tm

Tm

Tm

mmT

m

Tm

mmn

m

m

m

iii

m

SCHMIDT-GRAM DE ZAÇÃOORTOGONALI f)

do.acrescenta

modo cadapor ivosignificat dígito um

menteaproximada de perda há geral, Em

precisão. elconsideráv com calculados

ser que têmvetores-auto Os .

delugar no~

com nte,anteriorme

como escritosser podem métodos Os

M

M

Métodos de Iteração VetorialOrtogonalização de Gram-Schmidt

rrrr

rT

rT

r

r

r

rT

mmT

m

r

m

rrT

mmT

mm

rrmmT

m

r

mnmnr

nmm

Tm

XMXK

XPMPXPKP

XMXK

XPX

XI

MMXX

X

XMMX

XMXM

r

X

XMM

~~

~

~

~~

~~ou

~~~

~ou

~~0

~~como escritaser pode equação Esta

tes.remanescen liberdade de graus os representa onde

0~

~Seja

1

1

x)(x

SCHMIDT-GRAM DE ZAÇÃOORTOGONALI f)

jrjm

jmjr

r

rT

mmT

m

Tr

Tr

P

,

I

MMP

P MPM ; P KPK

como

calculadoser pode o Obtido

.calculados nteanteriorme vetores-auto

dos livre"" está reduzido problema O

com

onde

1

Métodos de Iteração VetorialOrtogonalização de Gram-Schmidt

Métodos de Transformação

l

ll

k

kk

kkT

kkkkT

kk

TT

PPPPΦ

lIMΛK

M

KP

PMPMPKPK

MMKK

MKΦ

IΦ MΦ ΛΦ KΦ

:Φ

...

e , quando , e

terse-necessita correto, toprocedimen um Para

diagonal. forma da próximos mais

e trazer a forma de osselecionad são os onde

e

e

Seja

:iteração

por la-construí tentar se-pode única, é (1) Eq. da

forma na e adiagonaliz que matriz a Como

(1) e

de básicas espropriedad as

empregam grupo neste dosclassifica tosprocedimen Os

321

11

11

11

121

1

1

1

1

1diag ...

;diag

e , diag

e diag

quando

:(1) de forma na mentenecessaria não -

adosdiagonaliz

tesimplesmen são e prática, Na

lr

l

lr

lr

rl

rl

MPPPΦ

M

KΛ

MM

KK

l

MK

Métodos de TransformaçãoMétodo de Jacobi

forma a tême

i.e., ,ortogonais são ação transformde matrizes As

nulos.ou positivos negativos, valores

-autocalcular para utilizadoser pode e simnples,

e estável é método O simétrica. matriz uma com

:padrão forma na problema

o para dodesenvolvi foi Jacobi de básico método O

JACOBI DE MÉTODO O a)

IPP

P

A

λ A

kT

k

k

1

1

cossen

1

1

sencos

1

1

kP

coluna p

coluna q

linha q

linha p

kqq

kpp

kqq

kppk

qqk

pp

kpq

kpq

kqq

kpp

kqq

kpq

kpq

kpp

kpq

kpq

kpq

kpp

kqq

kqq

kppk

qq

kpq

kqq

kpp

kqq

kppk

pp

kqj

kpj

kqj

kqj

kpj

kpj

kij

kij

kkT

kk

k

aa

aaaa

aθ

aaa

aaaaa

a

aaaaa

a

aaaaa

a

qpjaaa

aaa

qpjiaa

P APA

A(p,q)

se 4

se 2

2tan

ou

02cos12cos12sen21

cossencossencossen

Mas

0

2sen2cos22

2sen2cos22

,cossen

sencos

,,

:zero a de elemento oreduzir é metaA

JACOBI DE MÉTODO O a)

221

1

1

1

1

1

1

1

diagonal). da fora elementos os todossobre vez(uma

varredura"" a para usuário pelo fornecido é onde

se executada é çãotransforma

a e cíclica, forma uma de mentesequencial

testadossão elementos os qual no aquele é

,eficiência com usado sido temque toprocedimen Um

cíclica. a,sistemátic

forma deJacoby de ações transformasefetuar

preferível É tempo.muito consumiria ,entretanto

elemento, por tal buscaA módulo. em diagonal, da fora

elementomaior o semprezerar de aser poderia escolha

Umazerados. serem a elementos dos seqüência a

seja,ou zero, areduzir elemento qual a relativa decisão

umahaver que teriaportanto, princípio, Em seguintes.

ações transformas durante nulo não tornaráse

elemento este zero, a diagonal da fora elemento um

reduza ação transforma embora que notadoser Deve

2

m

δaa

am

qqpp

pq



332211

2

2211

22211

22

22211

112222

2211

22

22211

221111

2

1122211

2211

1

33

22

11

20

02

;

100

01

01

como escritaser pode 1,2 elemento o zera que maçãoA transfor

1cos ; sen

esaproximaçõ asusar

se-pode pequenos, são aplicados serem a rotação de ângulos os Como

sejaou pequenos, forem

diagonal da fora elementos os quando Jacobi, de método o Considere

kkkkk

kkkk

kkk

kkkk

kkk

K

PKPKkk

kk

P

kk

k

k

k

k

K

T

kjj

kii

kij

r.Householde

ou Givens de métodos os utilizadosser podem

tanto,Para diagonal.- triforma à matriz areduzir

teinteressanser pode Jacobi, de método oaplicar de

antes ia,conseqüênc Em iterações. de elevado bastante

número umrequerer pode pequenos não diagonal

da fora elementos os com matriz uma ,quadrática

iaconvergênc apresente Jacobi de método o Embora

0

0

, em (2,3) elemento o zerando ,Finalmente

0

0

se-obtém , em (1,3) zerando análoga, forma De

0

0

233

2

222

2

22211

4

3

233

222

2

2211

3

2

33

222

211

2

k

k

k

K

K

k

k

k

K

K

k

k

k

K

Métodos de TransformaçãoTransformação do Problema para a Forma

Padrão

. por dado é , e Obtidos

Jacobi. de método o se-utilizando resolvidoser

pode que padrão, forma na problema-auto um é Este

agora se,-tem

e

Definindo

forma na ainda, ou,

forma na colocadoser pode que

problema o agora, Considere,

21-

2121-21-

212121-2121-21-

ΦMΦΦΦ

ΦΦK

ΦMΦMKMK

ΦMMMΦMMKM

ΦMΦK

MK

T

TT

T

TT

T

ZΩ ZM

MM

Z Ω ZZΩ Z

Z ΩΩ ZM

ΩZMZZZ

IZZ

Z

Ω ZZ M

M

M

1

1

1

1

21

que modo De

Também

e

Então

sejaou ,ortonormal é onde

problema-auto o Considere

:utilizadoser pode toprocedimen seguinte

o cheia,ou banda de matriz uma de caso

No diagonal. é se calculado facilmente

é ação transforma para requerido O

Métodos de TransformaçãoMétodo Generalizado de Jacobi

k

qqk

pp

kk

k

kqq

kpp

k

kqq

kpp

kqq

kkqq

kpp

kqq

kpp

kqq

kpp

kqq

kqq

kpp

k

kqq

k

kqq

kqq

kqq

kpq

kpq

kqq

kqq

kpp

kpq

kpq

kpp

kpp

kqq

kpp

kpq

kpq

kkk

kk

x

kkxkx

kxkxkkxk

x

xkxkkk

mkmkk

kk

m

k

mkmkk

mkmkk

kk

m

k

2

2

2sinal

2

é estável) ( solução cuja 0ou

0 1

como escrita então é , de termosem (IV), equaçãoA

que modo de ,

se- tem(III) De

onde (IV) 0 1

:se- tem,por damultiplica (I) equação

à resultado o somando e -por (II) ndoMultiplica

onde (III) 0

:se- tem,por damultiplica (I) equação

à resultado o somando e -por (II) ndoMultiplica

(II) 0 1

(I) 0 1

:se-tem

0 ; 0

condições as usando e

e operações as Efetuando

1

1

1

1

1

1

mente.simultanea e ar diagonaliz é idéiaA

JACOBI DE DOGENERALIZA MÉTODO b)

11

kqq

kpq

kpp

kqq

kpq

kpp

kpq

kpq

kkT

kkkT

k

k

mmm

kkk

mk

P MPP KP

P

MK

linha p

linha q

coluna p

coluna q

ia.convergênc de a tolerância é 10 e

, ; onde

;, todos;10 ;10

e

,...,2,1 ;10

:iaConvergênc

.0 e positivo

é ntediscrimina o definida, positiva é Quando

1

11

11

21

11

21

1

1

s

lii

liil

ilii

liil

i

sljj

lii

lijs

ljj

lii

lij

sl

i

li

li

m

kλ

m

kλ

jijimm

m

kk

k

niλ

λλ

x

M


2186 varredurauma para Total

2 ...vetor -auto do Cálculo

4 ; elementozerar

para çãoTransforma

;

2sinal

2

12 ação transformde

matriz da Cálculo

6 ; oacoplament de

fatores dos Cálculo

2

11

1

1

2

22

nnn

n PPP

nP MPMPKPK(i,j)

x

k

x

k

kkk

kk

x

kmmkk

kmmkk

kmmkk

mm

m

kk

k

kk

kkT

kkkkT

kk

kjj

kii

kjj

kii

kk

k

kjj

kii

kjj

kjj

k

kij

kjj

kij

kjj

kjj

kij

kii

kij

kii

kii

kjj

kii

kij

kjj

kii

kij

Operação Cálculo Número de Operações


Métodos de TransformaçãoA Redução de Householder

. ordem de entescorrespond

matrizes as se- tem passo do geral caso No .1 ordem de são 0 e , , , onde

0

0

01

partições seguintes as Considere

típico.é que 1, k caso o considere definido, é define que vetor o comomostrar Para

11111

111

1111

11

1

1

(n-k)

k)(n-kwKP

Kk

kkK;

ww;

PP

Pw

TT

kk

plano de reflexão a {w}

{v}

{w}

[P] {v}

k

Tk

Tkkk

kkT

kk

T

T

ww; wwIP

nkPKPK

K

α

ww

v

ww; αwwαIP

2 com

2,...,2,1 ;

ações tranformusando al, tridiagonforma a para matriz

aar transformde ér Householde de método do objetivo O

.por provida é ãonormalizaç a

que vezuma e,irrelevant é de módulo o que Note . a

ortogonal plano no vetor dado um reflete matriz Esta

2

reflexão de matriz a Considere

rHouseholde de ReduçãoA

1


papel.qualquer temnão e eirrelevant é de módulo o que Note

módulo. em possívelmaior a de componente primeira afazer para escolhido foi sinal o onde

sinal

numérica. deestabilidamelhor para

oselecionadser pode -ou sinal o e 0,...,0,1 :1 ordem de unitário vetor um é onde

ou nula, não componente primeira sua a tenhasó que vetor num

vetor orefletir para usada seja reflexão de matriz a que é requerido é que o palavras, Em

;

0

0

00

i.e., al, tridiagonforma da sejam de coluna e linha primeira a que é agora, condição,A

0

01

0

01

1

1

12121111111211111

11

121111

1

1

111

122

11

2

2

11111

1111

1111

1111

1

11

12

1111

1111

1111

11111

w

w

ekkkwwkwθ ek wkwθ k

en-e

ekk wwθ I

k

P

PKPKK

x

xk

K

K

PKPk

Pkk

PKk

Pkk

PPKPK

PKk

Pkk

PKk

kkPK

TT

T

T

T

T

TT

T

TT

TTT


1

1

11

1111111

11111

111

11112

11

1111111111

1111111

1111

11

2 1111111

111111111

12

2 ; ;

ou ;

que também,Note, amente). temporariaumenta matriz da

reduzida não ainda parte da banda de largura (a original matriz bandada a destroir Householde de reduçãoA

reduzida. sendo ntecorrenteme está que matriz na issubdiagona elementos dos abaixo espaços nos armazenado

ser pode 21 lado, outroPor .armazenadaser necessita deinferior parte a somente que

modo de ,simétricas são ... reduzidas matrizes As notados.ser devem numéricos aspectos Alguns

wwwpwθpq

wKθp

wqpwKK

wwwKθ wθwKθwKθwK

wwKw wθwKθKwwθKP KP

,...,n-, kwK

KK

T

T

TT

TTT

TTT T

k

n

Métodos de TransformaçãoIteração QR

. elemento ozerar para aselecionad é onde

...

i.e., Jacobi, de matrizes utilizandosuperior triangular

forma a para reduzir efetivo mais é prática, Na

. de colunas àsSchmidt -Gram de zaçãoortogonali a

se-aplicando obtidaser poderia (I) em ofatorizaçãA

. tipodo ãodecomposiç uma fato,

de efetuando, se está calcular se ao Portanto,

(II)

:se- tem(I) oManipuland superior. triangular

matriz uma é e ortonormal matriz uma é onde

(I)

:forma na decompor é iteração da básico passo O

QR ITERAÇÃOA c)

12131

1

i,jP

RKPPP

K

K

P KPK

Q R

Q RQ R QQQ KQ

Q R QQ K

RQ

R QK

K

i,j

T,

T,

Tn,n

k T

k

T T

.

e , Quando

, se

:(II) e (I) equações pelas

indicado processo do repetição a via

obtido é QR iteração da algorítmo O

por dada é que evidente É

11

1

1

1

11312

ΦQ Q ... Q

ΛKl

Q RK

R QK

KK

P ... P PQ

Q

ll

l

kkk

kkk

n,n,,


, ..., k TT

nQR

T

QRQR

ΦQ Q ... Q ΛKl

IQ RK

R QIK

KK

QR

QR

inversa.iteração

à elacionadoimamente rR está into método QQR

QR

kk

lll

kkkk

kkkk

21 , de elementos os com de elementos os relacionam

que explícitas fórmulas de usofazer possível É valores.-auto os todosde solução a para requeridas

são operações 9 menteaproximada que mostra aexperiênci a i.e., eficiente, muito é processo

o al, tridiagoné matriz a Quando . de chamaremos aqui que diagonal- trimatriz à aplicadaser

deve solução a i.e., r,Householde de redução a após aplicadaser deve iteração a prática, Na

e , Quando

, se

:shifting"de" uso do através obtidaser pode iteração na

iaconvergênc de aceleração uma que sugere simples inversa iteração e método o entre relaçãoA

que se-Conlui . iteração de algorítmo do

iaconvergênc de ticascaracterís as se-estudando observadoser pode Isto distinto. ntecompletame

fato, de é, método o Jacobi, de toprocedimen ao semelhanteparecer possa iteração a Embora

1

2

1

111

1

1


ini

i

ψP P P

ψTK

T

T

QR

...

se- tem, por devetor -auto ésimo-i o denotando i.e., ; matriz da vetores-auto os

se-obter parar Householde de ações transformpelas ormadosser transf que então, têm, de vetores-auto Os

s.suficiente são usualmente scomponente as

todasem unitário vetor um com iniciando inversa iteração de passos Dois entes.correspond valores-auto

aos iguais shifts"" com simples, inversa iteraçãopor , al tridiagonmatriz da vetores-auto os se-calcula

precisão, grande com obtidos sido tenhamvalores-auto os que vez Umarápida. muito é shifting"" com

método do iaconvergênc a porque máquina, da precisão na calculados usualmente são valoresauto Os

VETORES-AUTO DOS CÁLCULO

221

1

1

1

Métodos de TransformaçãoAlgoritmo HQRI

pnnpnp

npn, ..., p ,; ixP ... P P

pn,...,p,,...; i, kxxIKp

n ,..., kQTQT

KTQR

nn,...,n-, kPKPK

KK

ini

ki

kiin

kkT

kk

n

kkT

kk

92

21

3

2 sautovetore e sautovalore os todospara Total

1 21 sautovetore de

çãoTransforma

10 2121; sautovetore

de Cálculo

9 21;

Iterações

2

3

3

2

221;

rHouseholde de

çõesTransforma

23

3211

11

2

1

11

23

1

1

Operação Cálculo Número de Operações

Métodos de Iteração PolinomialIteração Polinomial Implícita

Secante. Iteração da Método como conhecido é que

:em resulta (I) em doSubstituin

:forma na de oaproximaçã uma Seja

(I)

Newton de Método

0

ponto do tornoem

Taylor, de série numa p de expansão a Considere

detdet

0det

IMPLÍCITA POLINOMIAL ITERAÇÃO

11

1

1

1

1

1

kkkk

kkk

kk

kkk

k

k

kkk

k

kk

kkk

k

n

iii

T

T

μpμp

μp

μpμpμp

μp

μp

μp

μp

μp

T.O.S.μμμpμpμp

:μ

d L D L MλK

L D LMλK

MλK λp

p() = det([K] – [M])

k-1 k k+1

. que do

menores ambos forem e se garantida é

Secante Iteração da Método do iaConvergênc

1

1

λ

μμ kk-

Métodos Baseados na Propriedade da Seqüência de Sturm

i.e., problema, ésimo- do

aqueles separam restrito problema ésimo-1 do

valores-auto os que se- tem, especial caso o para e,

det

é associado restrito problema

ésimo- do ticocaracterís polinômio O colunas.

e linhas últimas as se-excluindo obtidas são

e e , ordem de são matrizes as todasonde

é K a entecorrespond associado

restrito problema ésimo- do problema-auto O

detdet

0det

ASSOCIADOS RESTRITOS PROBLEMAS

SEUS DE E KPROBLEMA

-AUTO DO TICOSCARACTERÌS POLINÔMIOS OS

1

r

)(r

MλKλp

r

rM

Kn-r

MλK

M

r

d L D L MλKλp

L D LMλK

MλK λp

M

rrrrr

r

r

rrrrr

n

iii

T

T

. em negativos

elementos exatamente há , se lado, outroPor

.

múltiplos. valores-auto há não

i.e., distintos, sejam valores-auto os todosque assuma

discussão, de desimplicida Para nulo.valor -auto um

temassociados restritos problemas dos nenhum i.e.,

;L D L em matriz afatorizar possa se

que Assuma seguinte. o é valores-auto de separação

de epropriedad da resulta que importante fato Um

...

1

111

122

111

D

iλμλ

s do que res menore auto-valo número deé igual ao

Ds em s negativoe elementoo número d,MμK

de omposição que na decortante é O fato imp

MμK

λλλλλλλ

ii

T

rrn

rrn

rrn

rrrr


. em negativos elementos exatamente

há , em negativo elemento um a ecorrespond

envelope um com de cruzamento cada como e

como ,Entretanto . linhas ascruzar pode

não valores,-auto dos separação de epropriedad

à devido e, , linhas ascruzar que

tem à entecorrespond reta a mente,necessaria

que, se-Observa .associados restritos problemas

dos valores-auto aos nterelativame de posição a

estabelece linha Esta . a entecorrespond vertical

linha a tracee que agora, Considere,

figura. na indicado

como das,estabeleci são curvas

as análoga, forma De . de chjamada seja

resultante curva a e retas linhaspor conectados

sejam , com10 valores

-auto os todosticos,caracterís polinômios

dos esboço no que assuma figura, a Referindo

1

1

21

1

32

1

10

11

Di

D

C

dp

,...,CC

, ...C,CC

λμλ

, ...,, CC

C

λλ,..., ,, rλ

k

rn

iii

r

ni

i

ii

r

15

14

13

12

11

34

33

32

31

43

42

41

1

2

3 4 5

p(

p(1)((1)

p(2)((2)

p(3)((3)

p(4)((4)

1)

2)

3)

4)

25

24

23

22

21

C1 C2

C3 C4 C5


Método da Bissecção

142

23

1 valores;-auto 2 há e entre

6

2

8

BSBS

BSλλ

BS

qq

q

q

L

L

LU

L

U

secante). iteração (e.g., eficiente mais método

umpor osubstituíd e passo neste abandonado é

bisseção da método o e, Usualmentinversa. iteração

por entescorrespond vetores-auto os ache depois e

requerida precisão a até valores-auto os Calcule 4.

isolados. sejam valores-auto

os todosque até realizada é Sturm de seqüência

da ão verificaça e sbissectado entesucessivam são

valor -auto um de maisconter se-sabe quais nos

intervalos os processo, Neste estão. sindividuai

valores-auto os quais nos sintervaloer identifica

para bissecção de simples esquema um Use3.

valores.-auto

portanto, há, e Entre . que do menores são

, valores-auto quantos determine e

em Sturm de seqüência da ão verificaça Aplique .2

; que do menores são valores

-auto quantos determine e Fatorize 1.

BISSECÇÃODA MÉTODO

LU

ULU

UU

LL

L

qq

λλλ

qMλK

λq

MλK

L U

BS1

p(

BS2 BS3

BS4 BS5

BS6

duas raízes no intervalo

etc.

valores;-auto 2 há e entre




56

53

364

451

31

U1

BSBS

BSBS

BSBS

BSBS

BSBS

BS

Documents

Métodos de Solução de Problemas de Auto-Valor Os métodos de solução em consideração podem ser sub-divididos em quatro grupos, correspondentes à propriedade