Laporan Analisis Numerik dan
Pemrograman Dinamik
-Eigenvalue dan Eigenvector-
DISUSUN OLEH
Nama : Daniel Kristianto Haryono
NRP : 2216204002
Program : Teknik Elektro
Studi
Bidang : Teknik Elektronika
Keahlian
INSTITUT TEKNOLOGI SEPULUH
NOPEMBER
SURABAYA
2016
DAFTAR ISI
Daftar Isi 2
Bab 1 Pendahuluan 4
Bab 2 Dasar Teori 5
2.1 Power Method 5
Bab 3 Algoritma 17
3.1 Power Method 17
Bab 4 Kode Program 24
4.1 Power Method 24
Bab 5 Tampilan Program 34
5.1Power Method 34
Bab 6 Kesimpulan 39
2
BAB 1
Pendahuluan
1.1 Latar Belakang
Permasalahan sistem persamaan linear (SPL) diangkat dari penyelesaian persamaan non-
homogen seperti di bawah:
[ A ] { X }={ B } (1)
Persamaan tersebut memiliki penyelesaian unik untuk setiap variabel x . Adapun
persamaan homogen dapat diselesaikan dengan metode-metode seperti Gauss
elimination, matrix inverse, Gauss-Seidel, LU factorization, serta Jacobi iteration.
Adapun untuk permasalahan eigenvalue dan eigenvector, diangkat dari penyelesaian
persamaan homogen seperti persamaan 2 berikut:
[ A ] { X }=0 (2)
Persamaan 2 akan terpenuhi pada dua kondisi yaitu:
1. Nilai dari {X} adalah 0 untuk semua elemennya, disebut juga sebagai
penyelesaian non-trivial;
2. Terdapat beberapa nilai elemen { X } yang dapat memenuhi persamaan di atas,
dan tidak semua nilai elemen { X } adalah 0 .
Eigenvalue dan eigenvector berasal dari proses pencarian penyelesaian persamaan
homogen seperti di bawah:
[ A ] { X }= { X }
[ A ] { X } { X }=0
3
( [ A ] [ I ] ) { X }=0 (3)
Untuk solusi non-trivial, maka {X} bukan merupakan vektor kolom 0 sehingga:
det ( [ A ] [ I ] )=0 (4)
Pada matrix dengan dimensi nxn , maka hasil dari persamaan 4 merupakan persamaan
polinomial dengan pangkat n . Eigenvalue dari matrix [A] merupakan nilai dari
akar persamaan polinomial tersebut. Eigenvector merupakan hasil dari perhitungan nilai
x1 , , xn
variabel untuk masing-masing nilai dari eigenvalue.
Sebagai gambaran, berikut adalah contoh penentuan eigenvalue untuk matrix dengan
dimensi 2 x 2 :
[
[ A ] = a11 a12
a21 a22 ]
[ a21 a22 ][ ][
[ A ] [ I ] = a 11 a12 0 = a11
0 a21
a12
a22 ]
det
[ a11
a21
a12
a22 ]
=( a11 ) ( a22 )a12 a 21
det
[ a11
a21
a12
a22 ]
=a 11 a22 a 11 a22+ 2a12 a21
4
a
( 11a22)a12 a21 + a11 a22 (5)
det
[ a11
a21
a12
a22]= 2
Untuk matrix 3 x3 maka persamaan di atas menjadi berpangkat 3 , sehingga
terdapat 3 buah nilai sebagai penyelesaian, demikian seterusnya. Proses
pencarian eigenvalue suatu matrix dengan orde lebih dari 3 x3 akan menjadi sangat
susah untuk dilakukan menggunakan perhitungan manual. Maka dari itu diperlukan
proses perhitungan secara terstruktur agar proses tersebut dapat diaplikasikan ke dalam
bentuk kode program.
Adapun metode-metode yang dapat digunakan untuk menentukan nilai eigenvalue di
antaranya adalah:
1. Power Method;
2. Jacobian;
3. QR Method.
1.2 Rumusan Masalah
Berdasarkan latar belakang masalah di atas, dalam laporan ini akan ditunjukkan
bagaimana menyelesaikan sebuah sistem persamaan homogen dengan banyak variabel,
sehingga ditemukan nilai eigenvaluenya, menggunakan metode yang telah disebutkan
sebelumnya.
1.3 Tujuan
Tujuan dari laporan ini adalah sebagai berikut:
Mengetahui dasar teori dari metode-metode yang telah disebutkan;
Mengetahui algoritma dari metode-metode yang telah disebutkan;
Dapat mengaplikasikan algoritma dari metode-metode yang telah disebutkan ke
dalam bentuk kode program.
5
6
BAB 2
Dasar Teori
2.1 Power Method
Power method merupakan proses iterasi yang dapat digunakan untuk mencari nilai
eigenvalue terbesar dari sebuah matrix dengan dimensi nxn . Adapun power method
digunakan untuk menghindari kerumitan penerapan perhitungan persamaan polynomial
pada proses komputasi.
Persamaan matrix harus dibawa kedalam bentuk persamaan
[ A ] { X }= { X } (6)
Pada awal eksekusi, harus ditentukan terlebih dahulu nilai tebakan awal untuk
eigenvector, di mana umumnya merupakan vektor 1 . Sebagai contoh kita memiliki
matrik [ A ] yang akan dicari nilai eigenvalue terbesarnya, maka kita tentukan terlebih
dahulu vektor kolom {X} yang merupakan tebakan eigenvector (umumnya bernilai 1
untuk setiap elemennya).
{ X 1 } =[ A ] { X 0 }
2
{ X 2 }=[ A ] { X 1 }=[ A ] ( [ A ] { X 0 }) =[ A ] { X 0 }
2 3
{ X 3 }=[ A ] { X 2 }= [ A ] ( [ A ] { X 0 })= [ A ] {X 0 }
3 4
{ X 4 }= [ A ] { X 3 }=[ A ] ( [ A ] { X 0 } )=[ A ] { X 0 }
k1 k
{ X k }=[ A ] { X k1 }= [ A ] ( [ A ] { X 0 } )=[ A ] { X 0 } (7)
7
Dari persamaan 7 di atas dapat disimpulkan bahwa untuk tebakan eigenvector ke- k ,
hasilnya didapatkan dari perkalian antara matrix [A] yang dipangkatkan k kali
dengan vektor kolom {X0 } .
Semakin banyak iterasi yang dilakukan akan membuat nilai tebakan eigenvector semakin
mendekati nilai aslinya, begitu pula dengan tebakan eigenvalue. Hal tersebut ditandai
dengan semakin kecilnya selisih perubahan untuk nilai eigenvalue yaitu .
| |
i i1
=
i
i
100 (8)
Proses iterasi akan dihentikan apabila nilai kurang atau sama dengan batas yang
ditentukan sebelumnya. Sebagai contoh berikut adalah numerical example untuk matrix
dengan orde 2 x 2 :
[
A= 2 12
1 5 ] X0= 1
1 []
1 5 1 [
X 1= A X 0= 2 12 1 = 10
4 ][ ] [ ] 10 [ 1
0.40000 ]
X 2= A X 1= [ 2 12 1
1 5 0.4
=][ ] [
2.80000
1 ] 2.8 [ 1
0.35714 ]
X 3= A X 2= [ 2 12 1
][= ][
2.28568
1 5 0.35714 0.78570 ] 2.28568 [ 1
0.34374 ]
8
X4= A X3= [ 2 12 1
1 5 0.34374][
= ][
2.12488
0.71870 ] 2.12488 [ 1
0.33823 ]
X 5= A X 4 = [ 2 12 1
][
=
2.05876
1 5 0.33823 0.69115 ][ ] 2.05876 [ 1
0.33571 ]
X 6 =A X 5= [ 2 12 1
][
=
2.02852
1 5 0.33571 0.67855 ][ ] 2.02852 [ 1
0.33450 ]
[
X 7 =A X 6= 2 12 1
][
= 2.01400
1 5 0.33450 0.67250 ][ ] 2.01400 [ 1
0.33391 ]
[
X 8 =A X 7= 2 12 1
][
= 2.00692
1 5 0.33391 0.66955 ][ ] 2.00692 [ 1
0.33362 ]
[
X 9 =A X 8= 2 12 1
][
= 2.00344
1 5 0.33362 0.66810 ][ ] 2.00344 [ 1
0.33347 ]
X 10= A X 9= [ 2 12 1
][ = ][
2.00164
1 5 0.33347 0.66735 ] 2.00164 [ 1
0.33340 ]
X 11 =A X 10= [ 2 12
][ 1
= ][
2.00080
1 5 0.33340 0.66700 ] 2.00080 [ 1
0.33336 ]
X 12= A X 11 = [ 2 12 1
][ = ][
2.00032
1 5 0.33336 0.66680 ] 2.00032 [ 1
0.33334 ]
X 1 3= A X 12= [ 2 12 1
][ = ][
2.00008
1 5 0.33334 0.66670 ] 2.00008 [ 1
0.33333 ]
[
X 14= A X 13= 2 12 1
][
= 2.0140
1 5 0.33333 0.6725 ][ ] 1.99996 [ 1
0.33333 ]
[
X 15= A X 14= 2 12 1
][
= 2.0140
1 5 0.33333 0.6725 ][ ] 1.99996 [ 1
0.33333 ]
9
Pada iterasi 15 , proses iterasi dihentikan. Hal tersebut dikarenakan eigenvalue yaitu
1.99996 adalah sama dengan eigenvalue iterasi 14 .
=
15
| | |
15 14
15
100 =
1.99996(1.99996)
1.99996 |
100 =0 ( 9)
Dari numerical example di atas, dapat disimpulkan bahwa nilai eigenvalue adalah
mendekati 2 . Sedangkan nilai dari eigenvector adalah:
{ X }= [ 1
][]
=3
0.3333 3 1
BAB 3
Algoritma
Pada bab ini akan disampaikan langkah jalannya kode program untuk metode-metode yang
disebutkan sebelumnya dalam bentuk flowchart.
3.1 Power Method
10
11
BAB 4
Kode Program
Pada bab ini akan disampaikan kode program untuk masing-masing flowchart yang telah
diberikan pada bab sebelumnya.
4.1 Power Method
int powerMethod(std::string fileName) {
int dimension;
std::string command;
readMatrixParameterXML(fileName, dimension, command);
squareMatrix *matrixA = new squareMatrix(dimension);
singleColumnMatrix *matrixX = new singleColumnMatrix(dimension);
readMatrixValueXML(fileName, dimension, *matrixA);
if (command == "powermethod") {
std::ofstream outputFile;
[Link](fileName + "_result.txt"); //open or create file
outputFile << "Ordo: " << dimension << "\n\n"; //print to file
char randomFlag;
int iteration = 0;
int iterationLimit;
double oldEigenValue = 0;
double calculatedConvergencePercentage = 100;
std::cout << "Fill the matrix X with random numbers? (y/n) ";
std::cin >> randomFlag;
switch (randomFlag) {
case 'y':
for (int i = 0; i < dimension; i++) {
matrixX->setElementValue(i, ((rand() % 100) - (rand() %
100)));
}
break;
case 'n':
for (int i = 0; i < dimension; i++) {
double inputMatrix = 0;
std::cout << "Matrix X (" << i << "): ";
std::cin >> inputMatrix;
matrixX->setElementValue(i, inputMatrix);
getchar();
}
break;
default:
std::cout << "Wrong input";
return 0;
}
std::cout << "Matrix A: \n";
matrixA->printMatrix();
std::cout << "Matrix X: \n";
matrixX->printMatrix();
std::cout << "\nLimit of iteration times: ";
std::cin >> iterationLimit;
12
outputFile << "Matrix A: \n";
outputFile << matrixA->printMatrixString();
outputFile << "Matrix X: \n";
outputFile << matrixX->printMatrixString();
outputFile << "\nLimit of iteration times: ";
outputFile << iterationLimit << std::endl;
do {
double newEigenValue = 0;
matrixX = new singleColumnMatrix
(multiplySquareColumnMatrix(*matrixA, *matrixX, dimension));
for (int i = 0; i < dimension; i++) {
if (abs(newEigenValue) < abs(matrixX->getElementValue(i)))
newEigenValue = matrixX->getElementValue(i);
}
for (int i = 0; i < dimension; i++) {
matrixX->setElementValue(i, matrixX->getElementValue(i) * 1
/ newEigenValue);
}
calculatedConvergencePercentage = double(abs((newEigenValue
oldEigenValue) / newEigenValue) * 100);
std::cout << "\nEpsilon (iteration " << iteration + 1 << "): ";
std::cout << calculatedConvergencePercentage << "%\n";
std::cout << std::setprecision(10) << "Eigenvalue (iteration " <<
iteration + 1 << "): " << newEigenValue << "\n";
std::cout << "Eigenvector (iteration " << iteration + 1 << "):
\n";
matrixX->printMatrix();
outputFile << "\nEpsilon (iteration " << iteration + 1 << "): ";
outputFile << calculatedConvergencePercentage << "%\n";
outputFile << std::setprecision(10) << "Eigenvalue (iteration " <<
iteration + 1 << "): " << newEigenValue << "\n";
outputFile << "Eigenvector (iteration " << iteration + 1 << "):
\n";
outputFile << matrixX->printMatrixString();
oldEigenValue = newEigenValue;
iteration++;
} while (calculatedConvergencePercentage > CONVERGENCE_PERCENTAGE &&
iteration < iterationLimit);
[Link]();
return 1;
}
else {
std::cout << "Wrong file";
return 0;
}
}
13
BAB 5
Tampilan Program
TAMPILAN PROGAM POWER METHOD
File XML input data matrix:
<?xml version="1.0" encoding="UTF-8"?>
<matrix>
<dimension>4</dimension>
<command> powermethod</command>
<A>
<AR0> <AC0>10</AC0><AC1>-1</AC1><AC2>2</AC2><AC3>0</AC3></AR0>
<AR1> <AC0>-1</AC0><AC1>11</AC1><AC2>-1</AC2><AC3>3</AC3></AR1>
<AR2> <AC0>2</AC0><AC1>-1</AC1><AC2>10</AC2><AC3>-1</AC3></AR2>
<AR3> <AC0>0</AC0><AC1>3</AC1><AC2>-1</AC2><AC3>8</AC3></AR3>
</A>
</matrix>
File text output program:
Ordo: 4
Matrix A :
10.0000000000 -1.0000000000 2.0000000000 0.0000000000
-1.0000000000 11.0000000000 -1.0000000000 3.0000000000
2.0000000000 -1.0000000000 10.0000000000 -1.0000000000
0.0000000000 3.0000000000 -1.0000000000 8.0000000000
Matrix X :
63.0000000000
11.0000000000
-76.0000000000
-13.0000000000
Limit of iteration times: 1000
Epsilon(iteration 1) : 100%
14
Eigenvalue(iteration 1) : -632
Eigenvector(iteration 1) :
-0.7389240506
-0.1503164557
1.0000000000
-0.0079113924
Epsilon(iteration 2) : 7380.787459%
Eigenvalue(iteration 2) : 8.680379747
Eigenvector(iteration 2) :
-0.6035362742
-0.2232956617
1.0000000000
-0.1744440394
...
Epsilon(iteration 62) : 9.26438929e-08%
Eigenvalue(iteration 62) : 14.07347771
Eigenvector(iteration 62) :
-0.5784622833
1.0000000000
-0.6781766421
0.6056129314
15
BAB 6
Kesimpulan
Power method dapat digunakan untuk menentukan eigenvalue terbesar dari sebuah matrix,
dengan menghindari proses komputasi manual yang semakin rumit untuk matrix dengan orde
yang tinggi. Adapun power method ini memiliki keterbatasan, yaitu apabila nilai tebakan
eigenvector yang digunakan adalah sama dengan nilai eigenvector dari eigenvalue yang
bukan terbesar, maka nilai dari tebakan eigenvector tidak akan konvergen ke nilai yang
terbesar. Kejadian tersebut akan lebih sering ditemukan untuk matrix dengan orde yang
tinggi.
16