Nilai Eigen dan

Singular Value
MATA KULIAH : METODE NUMERIK
FILKOM – UNIVERSITAS BRAWIJAYA

Disusun oleh Tim Ajar Mata Kuliah Metode Numerik 2019/2020

 Outline

• Nilai Eigen
• Metode Power
• Algoritma QR
• Singular Value
 Nilai eigen dan vektor eigen

• Definisi : Jika terdapat matriks A dengan ukuran 𝑛 x 𝑛 dan

vektor taknol 𝑥 berukuran 𝑛 x 1, maka dapat dituliskan
𝑨𝒙 = 𝝀𝒙
• Dimana :
– A : Matriks berukuran 𝑛 x 𝑛
– 𝜆 : Nilai eigen (eigenvalue)
– 𝑥 : Vektor eigen (eigenvector) yang bersesuaian dengan nilai
eigen 𝜆
 Nilai eigen dan vektor eigen

• Nilai eigen dapat diperoleh dengan menyelesaikan persamaan :

𝐴𝑥 = 𝜆𝑥
𝐴𝑥 − 𝜆𝑥 = 0
𝐴𝑥 − 𝜆𝐼𝑥 = 0
𝐴 − 𝜆𝐼 𝑥 = 0 (i)

• Persamaan (i) hanya dapat diselesaikan bila 𝐴 − 𝜆𝐼 tidak

mempunyai inverse
• Dengan kata lain, nilai 𝜆 diperoleh dengan menghitung
determinan(𝐴 − 𝜆𝐼) = 0
 Nilai eigen dan vektor eigen

• Langkah menghitung nilai eigen dan nilai vektor eigen:

1. Hitung nilai 𝐴 − 𝜆𝐼, dimana 𝐼 adalah matriks identitas
2. Hitung nilai det(𝐴 − 𝜆𝐼) = 0. Hasil dari perhitungan ini adalah
nilai-nilai eigen
3. Hitung nilai vektor eigen yang bersesuaian dengan masing-
masing nilai eigen.
 Nilai eigen dan vektor eigen
• Contoh : Hitunglah nilai-nilai eigen dan vektor eigen dari matriks berikut :
5 −2
𝐴=
7 −4
Jawab :
5 −2 𝜆 0 5−𝜆 −2
• Nilai 𝐴 − 𝜆𝐼 : − =
7 −4 0 𝜆 7 −4 − 𝜆
• Nilai determinan 𝐴 − 𝜆𝐼 = (5 − 𝜆)(−4 − 𝜆)-(-2*7)
• 5 − 𝜆 −4 − 𝜆 + 2 ∗ 7 = 0
𝜆2 − 𝜆 − 6 = 0
𝜆−3 𝜆+2 =0
• Nilai eigen adalah 𝜆 = 3 dan 𝜆 = −2
 Nilai eigen dan vektor eigen
• Vektor eigen yang bersesuaian dengan 𝜆 = −2
𝐴 − 𝜆𝐼 𝑥 = 0
5−𝜆 −2 𝑥1 0
=
7 −4 − 𝜆 𝑥2 0
7 −2 𝑥1 0
=
7 −2 𝑥2 0
• Dari SPL diatas diperoleh persamaan 7𝑥1 − 2𝑥2 = 0 sehingga dapat diperoleh
7
relasi 𝑥2 = 2 𝑥1 .
• Sehingga vektor eigen yang bersesuaian dengan nilai eigen 𝜆 = −2 adalah
𝑥1
semua vektor yang memenuhi 𝑥 = 7 𝑥 .
2 1
2 1 4
• Contoh vektor eigen , 7 ,
7 2 14
 Nilai eigen dan vektor eigen
• Vektor eigen yang bersesuaian dengan 𝜆 = 3
𝐴 − 𝜆𝐼 𝑥 = 0
5−𝜆 −2 𝑥1 0
=
7 −4 − 𝜆 𝑥2 0
2 −2 𝑥1 0
=
7 −7 𝑥2 0
• Dari SPL diatas diperoleh persamaan 2𝑥1 − 2𝑥2 = 0 dan 7𝑥1 − 7𝑥2 = 0 sehingga dapat
diperoleh relasi 𝑥2 = 𝑥1 .
• Sehingga vektor eigen yang bersesuaian dengan nilai eigen 𝜆 = −2 adalah semua vektor
𝑥1
yang memenuhi 𝑥 = 𝑥 .
1
1 3 14
• Contoh vektor eigen , ,
1 3 14
 Metode Power

• Power method merupakan metode iterasi untuk mencari nilai

eigen dan vektor eigen yang bersesuain
• Power method tidak bisa mencari semua nilai eigen, hanya bisa
menemukan nilai eigen dominan
Jika 𝜆1 , 𝜆2 , ⋯ , 𝜆1 merupakan nilai eigen dari matriks A berukuran n x n, 𝜆1
merupakan nilai eigen dominan jika :
𝜆1 > 𝜆𝑖 , 𝑖 = 2 ⋯ 𝑛

• Contoh :
– [-2,3,7,-5] -> Nilai dominannya = 7
– [-3,9,-13,8] -> Nilai dominannya = -13
 Metode Power

• Algoritma power method

1. Tentukan sebuah vektor taknol 𝑥0 berukuran 𝑛 x 1 sebagai perkiraan
vektor eigen.
2. Ulangi langkah a sampai c sampai kondisi berhenti dipenuhi
a. Hitung nilai 𝑦 = 𝐴𝑥𝑖
b. Carilah 𝑑 = 𝑛𝑖𝑙𝑎𝑖 𝑑𝑜𝑚𝑖𝑛𝑎𝑛 𝑑𝑎𝑟𝑖 𝑦
𝑦1
𝑑
c. Hitung nilai 𝑥𝑖 = ⋮
𝑦𝑛
𝑑
3. Nilai d merupakan pendekatan nilai eigen dominan sedangkan vektor
𝑥𝑖 merupakan vektor eigen yang bersesuaian
 Metode Power
• Contoh : Hitung nilai eigen dominan beserta vektor eigen dari matriks berikut :
5 −2
𝐴=
7 −4
Jawab :
1
5 −2 1 −1
• 𝑦1 = 𝐴𝑥0 = = → 𝑑 = −5 → 𝑥1 = 5
7 −4 3 −5 1
1
5 −2 −1 0.385
• 𝑦2 = 𝐴𝑥1 = 5 = → 𝑑 = −2.6 → 𝑥2 =
7 −4 1 −2.6 1
5 −2 0.385 −0.075 0.0575
• 𝑦3 = 𝐴𝑥2 = = → 𝑑 = −1.305 → 𝑥3 =
7 −4 1 −1.305 1
5 −2 1 3.5807 0.86046
• 𝑦10 = 𝐴𝑥9 = = → 𝑑 = 4.1613 → 𝑥10 =
7 −4 0.70967 4.1613 1
5 −2 1 3.0090 0.99701
• 𝑦20 = 𝐴𝑥19 = = → 𝑑 = 3.0181 → 𝑥20 =
7 −4 0.99548 3.0181 1
5 −2 1 3.0004 𝟎. 𝟗𝟗𝟗𝟗𝟎
• 𝑦28 = 𝐴𝑥27 = = → 𝑑 = 𝟑. 𝟎𝟎𝟎𝟕 → 𝑥20 =
7 −4 0.99982 3.0007 𝟏
0.99990
Setelah iterasi 28, diperoleh pendekata nilai eigen 𝜆 = 3.00007 dan vektor eigen 𝑥 =
1
 Dekomposisi QR untuk
Pencarian Nilai Eigen
• Dekomposisi QR dapat digunakan untuk mencari nilai-nilai eigen dari
suatu matriks
• Dekomposisi QR menguraikan matriks A menjadi matriks Q dan R.
𝐴 = 𝑄𝑅
Dimana :
A = matriks m x n
Q = matriks orthogonal m x m, dimana QTQ = I
R = matriks segitiga atas berukuran m x n

• Komponan Q dan R dapat diperoleh menggunakan proses Gram-

Schmidt
 Dekomposisi QR untuk
Pencarian Nilai Eigen
• Menggunakan komponen QR dari matriks A dapat didekati oleh
diagonal matriks Ak yang diperoleh dari Rk-1 * Qk-1
• Algoritma pencarian nilai eigen menggunakan QR :
1. Hitung komponen nilai QR dari matriks A. Gunakan proses Gram-Schmidt
𝑄0 𝑅0 = 𝐴
2. Set k=1
3. Ulangi langkah a dan b sampai kondisi berhenti dipenuhi
a. Hitung nilai 𝐴𝑘 = 𝑅𝑘−1 𝑄𝑘−1
b. Hitung ulang komponen Q dan R. 𝑄𝑘 𝑅𝑘 = 𝐴𝑘
4. Nilai-nilai eigen diperoleh dari diagonal matriks Ak
 Dekomposisi QR untuk Pencarian
Nilai Eigen
• Contoh : Hitung nilai eigen dari matriks berikut :
5 −2
𝐴=
7 −4
• k=1
−0.58124 −0.81373 −8.60233 4.41741 1.40541 9.56757
𝑄0 = ; 𝑅0 = ; 𝐴1 = 𝑅0 𝑄0 =
−0.81373 0.58124 0.00000 −0.69749 0.56757 −0.40541
• k=2
−0.92724 −0.37446 −1.51568 −8.71964 4.6706 −7.5176
𝑄1 = ; 𝑅1 = ; 𝐴2 = 𝑅1 𝑄1 =
−0.37446 0.92724 0.00000 −3.95861 1.4824 −3.6706
• k=10
−0.999881 −0.0154 −2.91770 −9.01433 3.056171 −8.968332
𝑄9 = ; 𝑅9 = ; 𝐴10 = 𝑅9 𝑄9 =
−0.015400 0.999881 0.00000 −2.05641 0.031668 −2.056171
• k=20
𝑄19 = −1 −2.6848𝑥10−4 ; 𝑅 = −2.99855 −9.00027 ; 𝐴 = 𝑅 𝑄 = 𝟑. 𝟎𝟎𝟏𝟎 −8.9995
19 20 19 19
−2.6848𝑥10−4 −1 0.00000 −2.00097 5.3722𝑥10−4 −𝟐. 𝟎𝟎𝟏𝟎
Singular Value Decomposition (SVD)

Metode SVD membagi sebuah matriks A menjadi 3 komponen, yaitu U,S,V,

dimana :
𝐴 = 𝑈𝑆𝑉 𝑇
– Keterangan :
A = matriks berukuran m x n
U = matriks berukuran m x m yang merupakan vektor eigen orthonormal dari AAT.
S = matriks berukuran m x n yang diagonalnya merupakan akar kuadrat dari nilai eigen dari
U atau V yang disusun menurun.
V = matriks berukuran n x n yang merupakan vektor eigen orthonormal dari ATA
 Singular Value Decomposition (SVD)

• Algoritma SVD
1. Hitung nilai AAT
2. Hitung nilai eigen dan vektor eigen dari AAT
3. Buatlah matriks y1 yang kolomnya berisi vektor eigen dari AAT
4. Hitung matriks U yang merupakan bentuk orthonormal dari y1. Gunakan proses Gram-schmidt
5. Hitung nilai ATA
6. Hitung nilai eigen dan vektor eigen dari ATA
7. Buatlah matriks y2 yang kolomnya berisi vektor eigen dari ATA
8. Hitung matriks V yang merupakan bentuk orthonormal dari y2. Gunakan proses Gram-schmidt
9. Diagonal matriks S merupakn nilai eigen taknol dari matriks U dan V yang dirutkan menurun. Elemen
selain diagonal bernilai 0
Singular Value Decomposition (SVD)

A = [Link]
Singular Value Decomposition (SVD)

• Contoh : Hitung nilai SVD dari matriks berikut :

3 1 1
𝐴=
−1 3 1

Jawab :
1. Hitung nilai AAT
3 −1
3 1 1 11 1
𝐴𝐴𝑇 = 1 3 =
−1 3 1 1 11
1 1
2. Hitung nilai eigen dan vektor eigen dari AAT
𝜆 = 10, 𝜆 = 12
𝑥1 1
Untuk 𝜆 = 10 vektor eigen yang bersesuaian adalah 𝑥 = −𝑥 , kita ambil
1 −1
𝑥1 1
Untuk 𝜆 = 12 vektor eigen yang bersesuaian adalah 𝑥 = 𝑥 , kita ambil
1 1
Singular Value Decomposition (SVD)

3. Buatlah matriks y1 yang kolomnya berisi vektor eigen dari AAT

1 1
𝑦1 =
1 −1
4. Hitung matriks U yang merupakan bentuk orthonormal dari y1
1 1
2 2
𝑈=
1 −1
2 2
5. Hitung nilai ATA
10 0 2
𝐴𝑇 𝐴 = 0 10 4
2 4 2
Singular Value Decomposition (SVD)
6. Hitung nilai eigen dan vektor eigen dari ATA
𝜆 = 0, 𝜆 = 10, 𝜆 = 12
1
Untuk 𝜆 = 12 vektor eigen yang bersesuaian adalah 𝑥 = 2
1
2
Untuk 𝜆 = 10 vektor eigen yang bersesuaian adalah 𝑥 = −1
0
1
Untuk 𝜆 = 0 vektor eigen yang bersesuaian adalah 𝑥 = 2
−5
Singular Value Decomposition (SVD)

7. Buatlah matriks y2 yang kolomnya berisi vektor eigen dari ATA

1 2 1
𝑦2 = 2 −1 2
1 0 −5
8. Hitung matriks V yang merupakan bentuk orthonormal dari y2
1 2 1
6 6 6
2 −1
𝑉= 0
5 5
−1 2 −5
30 30 30
Singular Value Decomposition (SVD)

9. Diagonal matriks S merupakan nilai eigen dari matriks U

atau V yang dirutkan menurun. Elemen selain diagonal
bernilai 0
12 0 0
𝑆=
0 10 0
Singular Value Decomposition (SVD)

Jadi, hasil dari dekomposisi matriks SVD adalah

1 2 1
1 1 6 6 6
2 2 12 0 0 2 −1
𝑈= 𝑆= 𝑉= 0
1 −1 0 10 0 5 5
2 2 −1 2 −5
30 30 30

A = [Link]