同济大学：《数值分析》课程教学资源（讲义）第四章 特征值的计算方法 Algorithm for Computing Eigenvalue and Eigenvector

Eigenvalue and Eigenvector →Introduction Power method and the variants ·Shifting ·Atekin Acceleration ●Summary Copyright©2011，NA⊙Yin Last Modification:Oct.2011 2

Eigenvalue and Eigenvector ⇒ Introduction • Power method and the variants • Shifting • Atekin Acceleration • Summary Copyright c 2011, NAYin Last Modification: Oct. 2011 2

Introduction ●Given A∈Cmxm,find入∈R and x≠0∈Rm,so that Ax=入x →(A-I)x=0x≠0 →A-λI川=0 One approach for eigenvalue and eigenvector. Copyright©2011，NA⊙Yin Last Modification:Oct.2011 3

Introduction • Given A ∈ C n×n, find λ ∈ R and x 6= 0 ∈ R n, so that Ax = λx → (A − λI)x = 0 x 6= 0 → |A − λI| = 0 One approach for eigenvalue and eigenvector. Copyright c 2011, NAYin Last Modification: Oct. 2011 3

Example Compute all eigenvalues of A 1 Solution 11-λ =(1-)(2-2入+4) .λ1=1λ2=1+V3iλ3=1-V3i How about for huge size? Copyright©2011，NA⊙Yin Last Modification:Oct.2011 4

Example Compute all eigenvalues of A =   1 0 2 0 1 −1 −1 1 1   Solution |A − λI| =   1 − λ 0 2 0 1 − λ −1 −1 1 1 − λ   = (1 − λ)(λ 2 − 2λ + 4) ∴ λ1 = 1 λ2 = 1 + √ 3i λ3 = 1 − √ 3i How about for huge size? Copyright c 2011, NAYin Last Modification: Oct. 2011 4

Properties of Eigens Let A be one of eigenvalues of A and x0 be the corresponding eigenvector, then, ax is also the corresponding eigenvector of A where a0; .A-1 is one of eigenvalues of A-1 with x be the corresponding eigenvector; ·入is one of eigenvalues of AT. Copyright©2011，NA⊙Yin Last Modification:Oct.2011 5

Properties of Eigens Let λ be one of eigenvalues of A and x 6= 0 be the corresponding eigenvector, then, • αx is also the corresponding eigenvector of A where α 6= 0; • λ −1 is one of eigenvalues of A−1 with x be the corresponding eigenvector; • λ is one of eigenvalues of AT . Copyright c 2011, NAYin Last Modification: Oct. 2011 5

Properties of Eigens Let Ai,(i=1,2,...,n)be the eigenvalues of A and zi0 be the corresponding eigenvectors,then, ●∑21Xi=1ai where is the trace of A,denoted by tr(A); ·I1λi=|A where|A is determinant of A. ·A-a≤∑=1aal e.g. 01 1/20-1 Copyright©2011，NA⊙Yin Last Modification:Oct.2011 6

Properties of Eigens Let λi ,(i = 1, 2, . . . , n) be the eigenvalues of A and xi 6= 0 be the corresponding eigenvectors, then, • Pn i=1 λi = Pn i=1 aii where Pn i=1 aii is the trace of A, denoted by tr(A); • Qn i=1 λi = |A| where |A| is determinant of A. • |λ − aii| ≤ Pn j=1,j6=i |aij|. e.g. A =   1 0 −1 1 3 0 1/2 0 −1   Copyright c 2011, NAYin Last Modification: Oct. 2011 6

Similarity If B=P-1AP where P is nonsingular,then A is similar with B,denoted by A B. ●lfA~B,thenλ(A)=入(B);if z is a eigenvector of B,then Pz is that of A. Copyright©2011，NA⊙Yin Last Modification::Oct.2011 7

Similarity If B = P −1AP where P is nonsingular, then A is similar with B, denoted by A ∼ B. • If A ∼ B, then λ(A) = λ(B); if z is a eigenvector of B, then P z is that of A. Copyright c 2011, NAYin Last Modification: Oct. 2011 7

Reilaigh Quotient If A is s.p.d.,and Ai,(i=1,2,...,n)are the eigenvalues of A such that 入1≥2≥..≥入n,then X1≥，4@≥x （x,c) (x,Ax) 入1=max x≠0（x,x) 入n=mih (z,Az) c≠0(x,r) Copyright©2011，NA⊙Yin Last Modification:Oct.2011 8

Reilaigh Quotient If A is s.p.d., and λi ,(i = 1, 2, . . . , n) are the eigenvalues of A such that λ1 ≥ λ2 ≥ . . . ≥ λn, then λ1 ≥ (x, Ax) (x, x) ≥ λn λ1 = max x6=0 (x, Ax) (x, x) λn = min x6=0 (x, Ax) (x, x) Copyright c 2011, NAYin Last Modification: Oct. 2011 8

Power method Let Ai,(i=1,2,...,n)be the eigenvalues of A and xi0 be the corresponding eigenvectors,assume that .xi is linear independent. ●λi satisfyλ1>A2≥·≥入n For any vo∈Rm n 0= ∑a,=a11+a22+…+ann =1 iterating by Uk+1=Auk,then 心 U1=AUo= QiAxi=a1入1c1+a2入2c2+··+an入nxn i三1 Copyright©2011，NA⊙Yin Last Modification:Oct.2011 9

Power method Let λi ,(i = 1, 2, . . . , n) be the eigenvalues of A and xi 6= 0 be the corresponding eigenvectors, assume that • xi is linear independent. • λi satisfy |λ1| > |λ2| ≥ · · · ≥ |λn| For any v0 ∈ Rn v0 = X n i=1 αixi = α1x1 + α2x2 + · · · + αnxn iterating by vk+1 = Avk, then v1 = Av0 = X n i=1 αiAxi = α1λ1x1 + α2λ2x2 + · · · + αnλnxn Copyright c 2011, NAYin Last Modification: Oct. 2011 9

V2 Av1 a1Xiz1+a2X2x2+...+anXicn k=a11十a25a2十…+anXhin 均 a1+g+…+ = anTn) Whenk is sufficiently large,since=2,3,... vk≈1a1x1 is a eigenvector corresponding to A1. Copyright©2011，NA⊙Yin Last Modification:Oct.2011 10

v2 = Av1 = α1λ 2 1x1 + α2λ 2 2x2 + · · · + αnλ 2 nxn ... vk = α1λ k 1x1 + α2λ k 2x2 + · · · + αnλ k nxn = λ k 1 (α1x1 + λ k 2 λ k 1 α2x2 + · · · + λ k n λ k 1 αnxn) When k is sufficiently large, since | λi λ1 | < 1, i = 2, 3, . . . , n vk ≈ λ k 1α1x1 is a eigenvector corresponding to λ1. Copyright c 2011, NAYin Last Modification: Oct. 2011 10

Remarks ●easy to compute suitable for sparse matrix computation .convergence speed depends on Uk could overflow with finite precision in computer,modified by normalize Uk in every step Copyright©2011，NA⊙Yin Last Modification:Oct.2011 11

Remarks • easy to compute • suitable for sparse matrix computation • convergence speed depends on | λ2 λ1 | • vk could overflow with finite precision in computer, modified by normalize vk in every step Copyright c 2011, NAYin Last Modification: Oct. 2011 11