CS计算机代考程序代写 Eigenvalues and Eigenvectors

Eigenvalues and Eigenvectors
CS/SE 4X03
Ned Nedialkov McMaster University March 30, 2021

Outline
Introduction Power method Rayleigh quotient

Introduction Power method Rayleigh quotient Introduction
• Given an n × n matrix A, a nonzero vector v is an eigenvector of A if
Av = λv, λ is scalar (1) That is, v does not change direction under the transformation
Av
• We can write (1) as
Av = λv ⇔ Av = λIv ⇔ (A − λI)v = 0
I is the n × n identity matrix
• (A − λI)v = 0 has a nonzero solution v when
det(A − λI) = 0
• det(A − λI) is characteristic polynomial, det(A − λI) = 0 is characteristic equation
Copyright © 2021 N. Nedialkov. All rights reserved. 3/15

Introduction Power method Rayleigh quotient Introduction cont.
Example 1. Consider
Then
􏰇1 2􏰈 A= 3 −4
􏰇1−λ 2 􏰈 A − λI = 3 −4 − λ
det(A−λI) = (−4−λ)(1−λ)+6 = −4+4λ−λ+λ2 −6 =λ2 +3λ−10=0
hasrootsλ1 =2andλ2 =−5.
Copyright © 2021 N. Nedialkov. All rights reserved. 4/15

Introduction Power method Rayleigh quotient Introduction cont.
Example 1. cont. For λ1 = 2,
􏰇1−2 2 􏰈 􏰇−1 2􏰈 (A−2I)v= 3 −4−2 v= 3 −6 v=0
has solution v1 = [2, 1]T , and
􏰇1 2 􏰈􏰇2􏰈 􏰇4􏰈 􏰇2􏰈
Av1 = 3 −4 1 = 2 = 2 1 􏰇1+5 2 􏰈 􏰇6 2􏰈
For λ1 = −5,
(A+5I)v= 3 −4+5 v= 3 1 v=0
has solution v2 = [1, −3]T , and
􏰇1 2 􏰈􏰇 1 􏰈 􏰇−5􏰈 􏰇 1 􏰈
Av1 = 3 −4 −3 = 15 = −5 −3
Copyright © 2021 N. Nedialkov. All rights reserved. 5/15

Introduction Power method Rayleigh quotient Introduction cont.
Example 2. Example form p. 223–225 of U. Ascher and C. Greig, A First Course in Numerical Methods
• Graph with n nodes, 1, 2, . . . , n, each node corresponds to a webpage
• If node i links to node j, directed edge from i to j 13
4
2
5
6
• Assume j points to Nj pages
E.g. page j = 3 points to N3 = 3 pages 1, 4, 6
Copyright © 2021 N. Nedialkov. All rights reserved. 6/15

Introduction Power method Rayleigh quotient Introduction cont.
Example 2. cont.
• Denote the importance of node (page) i by xi
• j contributes 1 xj to the importance of each page it points to Nj
E.g. page j = 3 contributes 1×3 to each of 1,4, and 6 3
page j = 1 contributes 1×1 to each of 2 and 4 2
• Can be represented as a matrix
123456
1
2
1
3 111
222
3 1
1 a blank denotes 0
4 5 6
2 11
23
1
2 111
232
• Column: out links, row: in links
Copyright © 2021 N. Nedialkov. All rights reserved. 7/15

Introduction Power method Rayleigh quotient Introduction cont.
Example 2. cont. • Then
E.g.
xi=􏰊 1xj, i=1,…,n j:j→i Nj
x4= 1×1+ 1×3=1×1+1×3 N1 N3 2 3
• We have n equations. As a system: Ax = x
• Eigenvalue problem!
Copyright © 2021 N. Nedialkov. All rights reserved. 8/15

Introduction Power method Rayleigh quotient Introduction cont.
Example 2. cont.
• Given page i, the number of links to it is << n, total number of pages. n can be in the billions • A is very large and sparse • The sum in each column is 1 • This matrix is column stochastic • There is a unique largest eigenvalue 1 • Entries in the corresponding eigenvector are positive • How to find this eigenvector? Copyright © 2021 N. Nedialkov. All rights reserved. 9/15 Introduction Power method Rayleigh quotient Power method • Method for finding the largest eigenvalue and corresponding eigenvector • Denote an eigen pair by (λi, xi) • Assume λ1 real and |λ1| > |λi| for all i = 2,…,n
• Assume A has n linearly independent eigenvectors
• Anyv∈Rn canbewrittenas
n
v = 􏰊αjxj, αj scalar
j=1
• Compute Av, A2v, …, Akv
Copyright © 2021 N. Nedialkov. All rights reserved.
10/15

Introduction Power method Rayleigh quotient Power method cont.
We have
nnn
Av = A􏰊αjxj = 􏰊αj(Axj) = 􏰊αjλjxj
j=1 j=1 j=1 nnn
A2v = A(Av) = A􏰊αjλjxj = 􏰊αjλj(Axj) = 􏰊αjλ2jxj j=1 j=1 j=1
.
nn
Akv = A(Ak−1v) = A􏰊αjλk−1xj = 􏰊αjλk−1(Axj) jj
n
= 􏰊 α j λ kj x j
j=1
j=1 j=1
Copyright © 2021 N. Nedialkov. All rights reserved.
11/15

Introduction Power method Rayleigh quotient Power method cont.
A k v = λ k1 α 1 x 1 + λ k2 α 2 x 2 + · · · + λ kn α n x n
􏰒 􏰅λ2􏰆k 􏰅λn􏰆k 􏰓
= λ k1 α 1 x 1 + λ α 2 x 2 + · · · + λ α n x n 11
• Since|λ1|>|λj|,􏰐λj􏰑k →0ask→∞forallj≥2 λ1
• Then
• Akv converges to a multiple of x1, the eigenvector
corresponding to λ1
Copyright © 2021 N. Nedialkov. All rights reserved.
Akv → (λk1α1)x1
12/15

Introduction Power method Rayleigh quotient Power method cont.
• Rate of convergence depends on |λ2|/|λ1| • If |λ1| > 1, Akv ≈ (λk1α1)x1 can overflow • If |λ1| < 1, Akv ≈ (λk1α1)x1 can underflow • How to avoid over/underflow? Normalize • Compute ◦ start with any v ◦ for k = 1,2,..., until convergence 􏰕 v􏰔=Av 􏰕 v=v􏰔/∥v􏰔∥ Copyright © 2021 N. Nedialkov. All rights reserved. 13/15 Introduction Power method Rayleigh quotient Rayleigh quotient • Rayleigh quotient μ(v) = vT Av vTv • If v is an eigenvector μ(v)= vTAv = vTλv =λ vTv vTv • If v is an approximation to an eigenvector μ(v) ≈ λ Power method v0 initial guess for k = 1, 2, . . . until termination v􏰔 = Avk−1 v k = v􏰔 / ∥ v􏰔 ∥ λ(k) =vTAv 1kk Copyright © 2021 N. Nedialkov. All rights reserved. 14/15 Introduction Power method Rayleigh quotient Example 2. cont. • Start with v = (1/6, 1/6, 1/6, 1/6, 1/6, 1/6)T , ∥v∥1 = 1 • v􏰔 = Av, ∥v􏰔∥1 = 1, need to normalize • The x for the PageRank example is • Ranking is 0.2174 page 1 2 3 4 5 6 rank 5 3 1 4 6 2 0.0994 0.1615 0.2981 x ≈ 0.1491 0.0745 Copyright © 2021 N. Nedialkov. All rights reserved. 15/15