12211032-sesi-2-laporan 2
TRANSCRIPT
MA3072
METODE NUMERIK
LAPORAN II
Nama : Andy Hidayatullah Rosman 12211032
Sesi : 2
Dosen : Novriana Sumarti, Ph.D
Nama Asisten : Muizzuddin Shidqi 12210008
William Suhartono 12210068
Tanggal Penyerahan : Kamis, 7 Maret 2013
PROGRAM STUDI MATEMATIKA
FAKULTAS MATEMATIKA DAN ILMU PENGETAHUAN ALAM
INSTITUT TEKNOLOGI BANDUNG
2013
I. Teori Singkat
Salah satu kegunaan dari metode numeric adalah untuk menyelesaikan Sistem Persamaan Linear (SPL) dengan variable yang sangat banyak. Dalam menyelesaikan SPL dengan menggunakan metode numeric SPL diubah kedalam bentuk matriks. Lalu dari bentuk matriks itu terdapat beberapa macam metode untuk menyelesaikan SPL tersebut.
Metode Eliminasi GaussEliminasi Gauss adalah suatu metode untuk mengoperasikan nilai-nilai di dalam matriks sehingga menjadi matriks yang lebih sederhana lagi. Dengan melakukan operasi baris sehingga matriks tersebut menjadi matriks yang baris. Ini dapat digunakan sebagai salah satu metode penyelesaian persamaan linear dengan menggunakan matriks. Caranya dengan mengubah persamaan linear tersebut ke dalam matriks teraugmentasi dan mengoperasikannya. Setelah menjadi matriks baris, lakukan substitusi balik untuk mendapatkan nilai dari variabel-variabel tersebut.
Metode Faktorisasi / Dekomposisi Segitiga
Pada metode ini matriks A difaktorkan menjadi factor segitiga bawah (L) dan segitiga atas (U).
A=LUSalah satu kegunaan dari faktorisasi segitiga ini adalah untuk menyelesaikan suatu SPL yang matriks koefisiennya sama tetapi nilai SPL-nya (ruas kanan SPL) berbeda-beda. Misalkan kita mempunyai SPL : Ax=b dan matriks A telah difaktorkan menjadi A=LU. Langkah untuk mencari penyelesaiannya adalah
Ax=bLUx=bLy=b
Dengan Ux=b. Langkah pertaa selesaikan SPL segitiga bawah Ly=b dengan substitusi maju. Setelah y diperoleh selanjutnya x dapat dicari dari persamaan Ux=y memakai substitusi mundur. Untuk memudahkan faktorisasi dikenal beberapa faktorisasi yaitu :1. Dekomposisi Doolitle, dimana elemen diagonal dari matriks L bernilai 12. Dekomposisi Crout, dimana elemen diagonal dari matriks U bernilai 13. Dekomposisi Cholesky, Bila matriks A bersifat simetri, matriks U dibuat sama
dengan Lt.
Metode JacobiMetode Jacobi adalah salah satu metode iterasi yang dapat digunakan untuk menyelesaikan sistem persamaan linier Ax = b dengan syarat matriks A yang bersifat dominan diagonal secara tepat. Dalam penelitian ini metode Jacobi dikembangkan menjadi metode Jacobi Diperumum, yaitu dengan memperumum matriks-matriks yang terlibat dalam persamaan metode Jacobi menurut suatu parameter. Berdasarkan alur analisis konvergensi metode Jacobi, dapat dibuktikan bahwa metode Jacobi Diperumum juga selalu konvergen ke solusi sejati sistem persamaan linier Ax = b.
Metode Gauss SeidelMetode interasi Gauss-Seidel adalah metode yang menggunakan proses iterasi hingga diperoleh nilai-nilai yang berubah-ubah. Metode iterasi Gauss-Seidel dikembangkan dari gagasan metode iterasi pada solusi persamaan tak linier .
II. Algoritma Penyelesaian Masalah
Metode Eliminasi Gauss :Masukkan : n Ukuran SPL
a[i,j] i =1,2,3,…,n j = 1,2,3,…,n+1Keluaran : x[i] i = 1,2,3,…,n Solusi SPLLangkah-Langkah :
// Tahap Eliminasi1. Untuk k=1,2,3,…, n-1
Jika |a[k,k]| < eps maka “Proses Gagal”,stopUntuk i = k+1,k+2,…,n
P = a[i,k]/a[k][k]Untuk j =k+1,k+2,…,n+1
a[i,j] = a[i,j] – P*a[k,j] a[i,k] = 0
// Tahap Substitusi Mundur2. Jika |a[k,k]| < eps maka “Proses Gagal”,stop
x[n] = a[n,n+1]/a[n,n]Untuk k = n-1,n-2,…,1
S=0Untuk i = k+1,k+2,…,n
S = S + a[k][i]*X[i]x[k] = (a[k][n+1] – S)/a[k][k]
Stop.
Metode Faktorisasi / Dekomposisi Segitiga:
Masukkan : n Ukuran SPLa[i,j] i =1,2,3,…,n j = 1,2,3,…,n+1
Keluaran : x[i] i = 1,2,3,…,n Solusi SPL Langkah-Langkah :
Metode Jacobi
Masukkan : n Ukuran SPlA[i][j] i = 1,2,3,…,n j=1,2,3,…,nB[i] i = 1,2,3,…,nX[i] i = 1,2,3,…,nepsmaxiter
Keluaran : x[i] i=1,2,3,…,nLangkah-Langkah :
1. Iter = 02. Galat = 03. Untuk i=1,2,3,…,n
S=0Untuk j=1,2,3,…,n
Jika j <> i maka s = s + a[i,j]*x[j]Xbaru[i] = (b[i] – s)/ a[i][i]S = abs((xbaru[i] – x[i] )/xbaru[i])Jika s > galat maka galat = s
4. Untuk i=1,2,3…,nX[i] = xbaru[i]
5. Jika galat < eps maka “Selesai”, Stop6. Iter = iter + 17. Jika iter > maxiter maka “Proses Belum Konvergen”, Stop8. Kembali ke langkah 2.
Metode Gauss Seidel
Masukkan : n Ukuran SPlA[i][j] i = 1,2,3,…,n j=1,2,3,…,nB[i] i = 1,2,3,…,nX[i] i = 1,2,3,…,nepsmaxiter
Keluaran : x[i] i=1,2,3,…,nLangkah-Langkah :
1. Iter = 02. Galat = 03. Untuk i=1,2,3,…,n
S=0Untuk j=1,2,3,…,n
Jika j <> i maka s = s + a[i,j]*x[j]Xbaru = (b[i] – s)/ a[i][i]S = abs((xbaru – x[i] )/xbaru)Jika s > galat maka galat = sX[i]=xbaru
4. Jika galat < eps maka “Selesai”, Stop5. Iter = iter + 16. Jika iter > maxiter maka “Proses Belum Konvergen”, Stop7. Kembali ke langkah 2.
III. Source Program C
Metode Eliminasi Gauss
#include<stdio.h>#define n 5
void isimatrix(float A[10][10]){ A[1][1]=1;A[1][2]=-2;A[1][3]=1;A[1][4]=-1;A[1][5]=1;A[1][6]=5; A[2][1]=-4;A[2][2]=3;A[2][3]=2;A[2][4]=1;A[2][5]=1;A[2][6]=-10; A[3][1]=4;A[3][2]=-5;A[3][3]=1;A[3][4]=5;A[3][5]=-1;A[3][6]=-7; A[4][1]=-2;A[4][2]=1;A[4][3]=-4;A[4][4]=4;A[4][5]=3;A[4][6]=0; A[5][1]=1;A[5][2]=1;A[5][3]=3;A[5][4]=-1;A[5][5]=3;A[5][6]=12;}
void printmatrix(float A[10][10]){ printf("\n"); int i,j; for(i=1;i<=n;i++) { for(j=1;j<=n+1;j++) { if(j==n+1) printf("|%f ",A[i][j]); else printf("%f ",A[i][j]); } printf("\n"); }}
void eliminasi(float A[10][10])
{ printf("\n"); printf(" Matriks Persamaan: "); printf("\n\n"); printmatrix(A); int i,j,k; float c; for(i=1;i<=n;i++) { for(j=i+1;j<=n;j++) { c=A[j][i]/A[i][i]; for(k=i;k<=n+1;k++) { A[j][k]=A[j][k]-c*A[i][k]; } } }
printf("\n"); printf(" Matriks Segitiga Atas: "); printf("\n\n"); printmatrix(A);}
void SubstitusiMundur(float A[10][10]){ int i,j; float s; A[n][n+2]=A[n][n+1]/A[n][n]; for(i=n-1;i>=1;i--) { s=0; for(j=n;j>i;j--) s=s+A[i][j]*A[j][n+2]; A[i][n+2]=(A[i][n+1]-s)/A[i][i]; }}
void Solusi(float A[10][10]){ int i; printf("\nMaka Solusi Dari SPL tersebut adalah:\n"); for(i=1;i<=5;i++) { printf("\nx%i = %f",i,A[i][n+2]); }}
int main(){ float A[10][10]; printf("\n"); printf("Metode Eliminasi Gauss "); printf("\n"); printf("\n"); printf("\nDiketahui SPL :\n\n"); printf("x1 - x2 + x3 - x4 + x5 = 5 \n-4x1 + 3x2 + 2x3 + x4 + x5 = -10 \n4x1 - 5x2 + x3 + 5x4 - x5 = -7 \n-2x1 + x2 - 4x3 + 4x4 + 3x5 = 0 \nx1 + x2 + 3x3 - x4 + 3x5 = 12 \n"); isimatrix(A); eliminasi(A); SubstitusiMundur(A); Solusi(A); getch();}
Hasil Kompilasi Metode Eliminasi Gauss :
Metode Faktorisasi / Dekomposisi Segitiga
#include<stdio.h>
#include<math.h>#define n 5
void isimatrix(float A[n+1][n+1],float B[n+1]){ A[1][1]=1;A[1][2]=-2;A[1][3]=1;A[1][4]=-1;A[1][5]=1;B[1]=5; A[2][1]=-4;A[2][2]=3;A[2][3]=2;A[2][4]=1;A[2][5]=1;B[2]=-10; A[3][1]=4;A[3][2]=-5;A[3][3]=1;A[3][4]=5;A[3][5]=-1;B[3]=-7; A[4][1]=-2;A[4][2]=1;A[4][3]=-4;A[4][4]=4;A[4][5]=3;B[4]=0; A[5][1]=1;A[5][2]=1;A[5][3]=3;A[5][4]=-1;A[5][5]=3;B[5]=12;}
void printmatrix(float A[n+1][n+1],float B[n+1]){ int i,j; for(i=1;i<=n;i++) { for(j=1;j<=n+1;j++) { if(j==n+1) printf("|%f\t",B[i]); else printf("%f\t",A[i][j]); } printf("\n"); }
}
void DekomposisiLU(float A[n+1][n+1],float B[n+1]){ int i,j,k; float s;
for(i=1;i<=n;i++) { for(j=i+1;j<=n;j++) { s=A[j][i]/A[i][i]; for(k=i;k<=n;k++) { A[j][k]=A[j][k]-s*A[i][k]; } A[j][i]=s; } } printf("\n"); printf("Matriks Segitiga Bawah (Lower)(Ly=b) "); printf("\n"); for(i=1;i<=n;i++) { for(j=1;j<=n+1;j++) {
if(i==j) printf("1\t"); else if(j<i) printf("%f\t",A[i][j]); else{ if(j==n+1) printf("\t|%f",B[i]); else printf("\t0\t");} } printf("\n"); }
for(i=1;i<=n;i++) { s=0; for(j=1;j<i;j++) { s=s+A[i][j]*B[j]; } B[i]=(B[i]-s); } printf("\nNilai Y Adalah:"); printf("\ny1=%f\ny2=%f\ny3=%f\ny4=%f\n",B[1],B[2],B[3],B[4]);
printf("\n"); printf(" Matriks Segitiga Atas(Ux=y) "); printf("\n"); for(i=1;i<=n;i++) { for(j=1;j<=n+1;j++) { if(j<i) printf("0\t "); else{ if(j==n+1) printf(" |%f",B[i]); else printf("%.4f ",A[i][j]);} } printf("\n"); }
B[n]=B[n]/A[n][n]; for(i=n-1;i>=1;i--) { s=0; for(j=n;j>i;j--) s=s+A[i][j]*B[j]; B[i]=(B[i]-s)/A[i][i]; } printf("\nNilai X (akar) adalah:"); printf("\nx1 = %f\nx2 = %f\nx3 = %f\nx4 = %f\nx5 = %f",B[1],B[2],B[3],B[4],B[5]);}
int main(){ float A[n+1][n+1], B[n+1];
printf("\n"); printf("Metode Faktorisasi LU "); printf("\n\n"); printf("\n"); printf("\n\n"); isimatrix(A,B); printf("\n========================== Matriks Awal (Ax=b):============================\n\n"); printmatrix(A,B); printf("\n\nMisal A = LU\nMaka (LU)x = b dan L(Ux)= b\n"); printf("1. y = Ux, Selesaikan SPL segitiga bawah Ly = b, didapat vektor y\n"); printf("2. Selanjutnya vektor x dapat dicari dari persamaan Ux = y\n"); DekomposisiLU(A,B); getch();}
Hasil Kompilasi Metode Dekomposisi / Faktorisasi LU :
Metode Jacobi dan Gauss-Sceidel
#include<stdio.h>
#define n 5
#define epsilon 1e-8
void print()
{
printf("\nSistem Persamaan Linier:\n");
printf("x1 - x2 + x3 - x4 + x5 = 5 \n-4x1 + 3x2 + 2x3 + x4 + x5 = -10 \n4x1 - 5x2 +
x3 + 5x4 - x5 = -7 \n-2x1 + x2 - 4x3 + 4x4 + 3x5 = 0 \nx1 + x2 + 3x3 - x4 + 3x5 = 12
\n");
}
void matrix(float A[n+1][n+1],float B[n+1],float P[n+1],float Q[n+1])
{
A[1][1]=1;A[1][2]=-2;A[1][3]=1;A[1][4]=-1;A[1][5]=1;B[1]=5;P[1]=0;Q[1]=0;
A[2][1]=-4;A[2][2]=3;A[2][3]=2;A[2][4]=1;A[2][5]=1;B[2]=-10;P[2]=0;Q[2]=0;
A[3][1]=4;A[3][2]=-5;A[3][3]=1;A[3][4]=5;A[3][5]=-1;B[3]=-7;P[3]=0;Q[3]=0;
A[4][1]=-2;A[4][2]=1;A[4][3]=-4;A[4][4]=4;A[4][5]=3;B[4]=0;P[4]=0;Q[4]=0;
A[5][1]=1;A[5][2]=1;A[5][3]=3;A[5][4]=-1;A[5][5]=3;B[5]=12;P[5]=0;Q[5]=0;
}
int main()
{
printf("---------------------------PROGRAM ITERASI JACOBI DAN GAUSS-
SEIDEL-----------------------------\n");
float A[n+1][n+1], B[n+1], P[n+1], Q[n+1];
float sP, sQ, galatP, galatQ, Pi[n+1], Qi[n+1];
int i,j,k;
print(A);
matrix(A,B,P,Q);
printf("\n----------------------------METODE
JACOBI--------------------------------------------------\n");
printf("I=\t x1\t\tx2\t x3\t x4\tx5\tGalat\n");
printf("-------------------------------------------------------------------\n");
for(i=1;i<=100;i++)
{
for(j=1;j<=n;j++)
{
sP=0; sQ=0;
for(k=1;k<=n;k++)
{
if(k!=j) sP=sP+A[j][k]*P[k];
if(k!=j) sQ=sQ+A[j][k]*Q[k];
}
Pi[j]=(B[j]-sP)/A[j][j];
Qi[j]=(B[j]-sQ)/A[j][j];
sP=fabs((Pi[j]-P[j])/Pi[j]);
sQ=fabs((Qi[j]-Q[j])/Qi[j]);
if(galatP>sP) galatP=sP;
if(galatQ>sQ) galatQ=sQ;
Q[j]=Qi[j];
}
for(j=1;j<=n;j++) P[j]=Pi[j];
if(galatP<=epsilon) break;
printf("\n%i\t %f %f %f %f %f ",i,P[1],P[2],P[3],P[4],P[5],galatP);
}
printf("\n");
printf("\n---------------------------METODE GAUSS-
SEIDEL---------------------------------\n");
printf("I=\t x1\t\tx2\t x3\t x4\tx5\tGalat\n");
printf("-------------------------------------------------------------------\n");
for(i=1;i<=100;i++)
{
for(j=1;j<=n;j++)
{
sP=0; sQ=0;
for(k=1;k<=n;k++)
{
if(k!=j) sP=sP+A[j][k]*P[k];
if(k!=j) sQ=sQ+A[j][k]*Q[k];
}
Pi[j]=(B[j]-sP)/A[j][j];
Qi[j]=(B[j]-sQ)/A[j][j];
sP=fabs((Pi[j]-P[j])/Pi[j]);
sQ=fabs((Qi[j]-Q[j])/Qi[j]);
if(galatP>sP) galatP=sP;
if(galatQ>sQ) galatQ=sQ;
Q[j]=Qi[j];
}
for(j=1;j<=n;j++) P[j]=Pi[j];
if(galatP<=epsilon) break;
printf("\n%i\t %f %f %f %f %f ",i,Q[1],Q[2],Q[3],Q[4],Q[5],galatQ);
}
printf("\n");
getch();
}
Hasil Kompilasi Metode dan Gauss-Sceidel:
IV. Analisis
Metode eliminasi Gauss digunakan dalam analisis numerik untuk meminimalkan
mengisi selama eliminasi, dengan beberapa tahap. Keuntungan dari system ini
adalah menentukan apakah sistem konsisten, menghilangkan kebutuhan untuk
menulis ulang variabel setiap langka, lebih mudah untuk memecahkan. Kelema-
han dari system ini adalah memiliki masalah akurasi saat pembulatan desimal.
Kelebihan dari metode dekomposisi LU adalah sangat efektif untuk menyele-
saikan persamaan linier serentak yang berordo tinggi, dengan hasil yang
mendekati nilai eksaknya, namun memerlukan cara yangcukup kompleks.
Metode eliminasi Gauss-Seidel digunakan untuk menyelesaikan SPL yg beruku-
ran kecil karena metode ini lebih efisien disbanding metode Jacobi. Dengan
metode iterasi Gauss-Seidel sesatan pembulatan dapat diperkecil karena dapat
meneruskan iterasi sampai solusinya seteliti mungkin sesuai dengan batas sesatan
yang diperbolehkan. Kelemahan dari metode ini adalah masalah pivot (titik ten-
gah) yang harus benar–benar diperhatikan, karena penyusun yang salah akan
menyebabkan iterasi menjadi divergen dan tidak diperoleh hasil yang benar.
V. Kesimpulan
- Keuntungan dari metode eliminasi Gauss lebih mudah untuk memecahkan
- Keuntungan dari metode dekomposisi LU adalah sangat efektif untuk menye-
lesaikan persamaan linier serentak yang berordo tinggi
- Metode Gauss-Seidel lebih efisien disbanding metode Jacobi