Eigenvalue Decomposition

전체 글

(1)

Eigenvalue

Decomposition

Wanho Choi (wanochoi.com)

(2)

Eigenvalues & Eigenvectors

Av

i

=

λ

i

v

i

A : n by n matrix

v

i

: the i-th eigenvector

λ

i

: the i-th eigenvalue

λ

i

, v

i

(

)

: the i-th eigen-pair

(

i : 1, 2, 3, ! , n

)

(3)

Geometrical Meaning

Av

i

=

λ

i

v

i

The transformed vector (Ax) is a scalar multiple of the vector (x).

Ax is parallel to x.

eigen = characteristic

eigenvector : strectching direction eigenvalue: stretching factor

(4)

https://www.youtube.com/watch?v=8UX82qVJzYI

(5)

When A is a symmetric matrix, …

• Two different eigenvectors are orthogonal each other. viTAv j = viT

( )

Av j = viT

( )

λjvj = vijv j = λjviTv j viTAv j = viTATv j = v

(

iTAT

)

v j = Av

( )

i T v j =

( )

λivi T v j = λiviTv j ⇒ λjviTv j = λiviTv j

(

λi − λj

)

viTv j = 0 ∴viT v j = 0 ∵

(

λi ≠ λj

)

Avi = λivi, Av j = λjv j

(

λi ≠ λj, i ≠ j

)

AT = A

(6)

How to calculate eigenvalues

Av

i

=

λ

i

v

i

⇔ A −

(

λ

i

I

)

v

i

= 0

⇔ det A −

(

λ

i

I

)

= 0

λ

i

: the i-th roots of the n-th order polynomial

(7)

Invertible Matrix Theorem

The matrix A is invertible

if and only if 0 is not an eigenvalue of A.

Avi = λivi If A-1 is exist, then vi = A-1λivi. ∴A-1 vi = 1 λi vi ⇔ A-1 = 1 λ1 0 ! 0 0 1 λ2 ! 0 " " # " 0 0 0 1 λn ⎡ ⎣ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎤ ⎦ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥

(8)

Some Useful Properties

• • • • det(A) = λ1 × λ2 ×!× λn trace(A) = λ1 + λ2 +!+ λn

rank(A) = the number of non-zero eigenvalues

(9)

Eigenvalue(Spectral) Decomposition

AV= − a1 − − a2 − ! − an − ⎡ ⎣ ⎢ ⎢ ⎢ ⎢ ⎢ ⎤ ⎦ ⎥ ⎥ ⎥ ⎥ ⎥ | | | v1 v2 ! vn | | | ⎡ ⎣ ⎢ ⎢ ⎢ ⎤ ⎦ ⎥ ⎥ ⎥= a1⋅v1 a1⋅v2 ! a1⋅vn a2⋅v1 a2⋅v2 ! a2⋅vn ! ! " ! an⋅v1 an⋅v2 ! an⋅vn ⎡ ⎣ ⎢ ⎢ ⎢ ⎢ ⎢ ⎤ ⎦ ⎥ ⎥ ⎥ ⎥ ⎥ = | | | Av1 Av2 ! Avn | | | ⎡ ⎣ ⎢ ⎢ ⎢ ⎤ ⎦ ⎥ ⎥ ⎥= | | | λ1v1 λ2v2 ! λnvn | | | ⎡ ⎣ ⎢ ⎢ ⎢ ⎤ ⎦ ⎥ ⎥ ⎥= | | | v1 v2 ! vn | | | ⎡ ⎣ ⎢ ⎢ ⎢ ⎤ ⎦ ⎥ ⎥ ⎥ λ1 0 ! 0 0 λ2 ! 0 ! ! " ! 0 0 ! λn ⎡ ⎣ ⎢ ⎢ ⎢ ⎢ ⎢ ⎤ ⎦ ⎥ ⎥ ⎥ ⎥ ⎥ = VΛ Avi = λivi ⇔ AV = VΛ ⇔ A = VΛVT ⇔ A = λi i=1 n

viviT V−1= VT V : orthonormal( ) A = | ! | v1 ! vn | ! | ⎡ ⎣ ⎢ ⎢ ⎢ ⎤ ⎦ ⎥ ⎥ ⎥ λ1 ! 0 " # " 0 ! λn ⎡ ⎣ ⎢ ⎢ ⎢ ⎤ ⎦ ⎥ ⎥ ⎥ − v1 − ! " ! − vn − ⎡ ⎣ ⎢ ⎢ ⎢ ⎤ ⎦ ⎥ ⎥ ⎥ a b c d ⎡ ⎣ ⎢ ⎤ ⎦ ⎥⎡ α 00 β ⎣ ⎢ ⎢ ⎤ ⎦ ⎥ ⎥ a c b d ⎡ ⎣ ⎢ ⎤ ⎦ ⎥ =⎡ a bc d ⎣ ⎢ ⎤ ⎦ ⎥⎡ αa αcβb βd ⎣ ⎢ ⎢ ⎤ ⎦ ⎥ ⎥ = αaa + βbb αac + βbd αac + βbd αcc + βdd ⎡ ⎣ ⎢ ⎢ ⎤ ⎦ ⎥ ⎥=α aa acac cc ⎡ ⎣ ⎢ ⎤ ⎦ ⎥ + β⎡ bb bdbd dd ⎣ ⎢ ⎤ ⎦ ⎥ =α a c ⎡ ⎣ ⎢ ⎤ ⎦ ⎥ a c⎦ + βbd ⎣ ⎢ ⎤ ⎦ ⎥ b d rotation inverse rotation stretching

(10)

Eigenspace

n unknowns n equations Ax = b VΛVT

(

)

x = b Λ VT x

( )

= VT b Λy = d VTx = y x = Vy linear system

(globally coupled system) eigenvalue decomposition

decoupled n equations in eigenspace

(11)

Eigenvalue Analysis

• It gives the solution of Ax=b, and simplifies the

solution of a certain problem by reducing a coupled system to a collection of scalar problems.

It gives insight into the behavior of evolving

systems governed by linear equation.

Am = VΛV

(

T

)

m = VΛV

(

T

)

(

VΛVT

)

! VΛV

(

T

)

= VΛVT VΛVT

(

)

! VΛV

(

T

)

= VΛIΛV

(

T

)

! VΛV

(

T

)

= VΛΛV

(

T

)

! VΛV

(

T

)

= VΛ2 VT

(

)

! VΛV

(

T

)

= ! = VΛm VT Ax = b ⇔ VΛV

(

T

)

x = b ⇔ Λ V

( )

Tx = VTb ⇔ Λy = d

(12)

Applications of Eigenvalue Analysis

• Analyzing natural frequency in vibration

• Analyzing stability or convergence in iteration

Approximation with lower computation

(13)

Applications of Eigenvalue Analysis

• Analyzing natural frequency in vibration

Analyzing stability or convergence in iteration

Approximation with lower computation

yn = 1+ Δt( λ)n y0 (λ < 0 in this case) : It converges when 1+ Δtλ ≤ 1. ⇔ −1 < 1+ Δtλ < 1 ⇔ − 2 < Δtλ < 0 ∴Δt < −2 λ yn+1 = yn + Δt ⋅ f (yn) = yn + Δt ⋅Ayn = yn + Δt ⋅ Λyn = I + Δt ⋅ Λ( )yn

(14)

Applications of Eigenvalue Analysis

• Analyzing natural frequency in vibration

Analyzing stability or convergence in iteration

Approximation with lower computation

A = λi i=1 n

viviT ≈ λi i=1 m

viviT m( ≪ n)

(15)

Square-Root Matrix

A−1 = VΛ−1VT ∵ VΛ

(

−1VT

)

(

VΛVT

)

= VΛ−1

( )

VTV ΛVT = VΛ−1IΛVT = VΛ−1ΛVT = VVT = I A1/2 = VΛ1/2VT ∵ VΛ1/2 VT

(

)

(

VΛ1/2VT

)

= VΛ1/2

( )

VTV Λ1/2VT = VΛ1/2IΛ1/2VT = VΛ1/2Λ1/2VT = VΛVT = A ∴A1/2 = VΛ1/2 VT = λi i=1 n

viviT

(16)

Similarity Transformation

A and B are similar, if there exists a non-singular matrix X such as B=XAXT.

A and B shares many properties.

If X is non-singular, then A and B have the same

characteristic polynomial and eigenvalues.

det(B)

= det(XAX

T

)

= det(X)det(A)det(X

T

)

= det(X)det(A)

1

(17)

수치

Updating...

참조

  1. wanochoi.com)
관련 주제 :