bab 2 anum
DESCRIPTION
metnumTRANSCRIPT
BAB 2
SISTIM PERSAMAAN LINEAR DAN NON LINEAR
Sistem persamaan linear banyak dijumpai pada penyelesaian persamaan diferensial parsial eliptik,
parabolik dan hiperbolik yang akan diberikan pada Bab 6, 7, dan 8. Dalam bab ini akan dibahas mengenai
matriks dan penyelesaian sistim persamaan linear dengan metoda eliminasi Gauss dan Iterasi Gauss-Seidel.
2.1. MATRIKS
Matriks ordo m x n adalah jajaraan bilangan persegi empat terdiri dari bars m dan kolom n dlm bentuk :
Setiap bilangan ajk dalam matriks ini disebut suatu elemen. Subskrip j menunjukkan baris dan k menunjukkan
kolom. Matrik yang mempunyai satu baris disebut matriks baris sedangkan yang mempunyai satu kolom
disebut matriks kolom. Matriks bujur sangkar adalah matriks yang mempunyai jumlah baris dan kolom yang
sama. Matriks Nyata adalah matriks yang memiliki bilangan nyata, sedangkan Matriks Kompleks adalah
matriks yang mempunyai bilangan kompleks.
Contoh : Matriks Nyata
Contoh : Matriks Kompleks
Dua buah matriks atau lebih yang berukuran sama dapat dijumlahkan atau dikurangkan. Jumlah dari matriks A
= [aij] dan B = [bij] adalah suatu matriks yang elemen-elemennya merupakan penjumlahan elemen-elemen yang
berhubungan dari matriks A dan B.
C = A + B = [aij] + [bij] = [cij] (2.1.1)
Pengurangan matriks A dan matriks B menghasilkan suatu matriks yang elemen-elemennya merupakan
elemen-elemen yang berhubungan dari matriks A dan B.
C = A - B = [aij] - [bij] = [cij] (2.1.2)
Contoh :
;
Jika matriks A = (nxm) dan matriks B = (mxr) dikalikan akan menghasilkan :
Perkalian antara skalar dengan matriks akan menghasilkan suatu matriks yang elemen-elemennya adalah
perkalian skalar dengan elemen matriks asal :
k A = C, [cij] = k [aij]
Contoh :
;
Sistim persamaan linear dapat didefinisikan sebagai perkalian antara matriks A dengan vektor kolom x
menghasilkan vektor kolom b yang dapat ditulis sebagai :
a11x1 + a12x2 + ………. + a1nxn = b1,
a21x1 + a22x2 + ………. + a2nxn = b2,
.
.an1x1 + an2x2 + ………. + annxn = bn,
atau dapat ditulis sebagai Ax = b, dimana :
, ,
Sistem persamaan linear dapat diselesaikan dengan metoda langsung (direct method) atau dengan metoda iterasi
(iterative method).
2.2. METODA ELIMINASI GAUSS
Metoda Gaussion Elimation merupakan salah satu metoda langsung (direct method). Metoda ini dimulai
dengan membuat augmented matrix, dan selanjutnya dilakukan operasi baris pada augmented matrix untuk
mendapatkan upper triangular matrix. Back subtitution digunakan pada langkah akhir untuk mendapatkan
harga variabel-variabel bebas yang dibutuhkan. Contoh diberikan suatu set persamaan linear :
3 x1 - x2 + 2 x3 = 12
x1 + 2 x2 + 3 x3 = 11
2 x1 - 2 x2 - x3 = 2.
Hitung besarnya x1, x2, dan x3.
Dari set persamaan tersebut dibuat augmented matrix :
3 -1.000 2.000 12.000
Row 2 – (1/3) Row 1 0 2.333 2.334 7.004
Row 3 – (2/3) Row 1 0 -1.334 -2.332 -5.992
3 -1.000 2.000 12.000
0 2.333 2.334 7.004
Row 3 – (-1.334/2.333) Row 2 0 0 -1.000 -1.993
Melalui back substitution yang dimulai dari
persamaan ketiga dan kembali ke persamaan kedua dan pertama didapat :
Algoritma Metoda Eliminasi Gauss
1. Buat augmented matrix dari n x n matriks dengan vector sisi kanan sama dengan
Menjadi matriks n x (n + 1).
2. Pertukarkan baris jika diperlukan agar a11 menjadi koefisien terbesar pada
Kolom pertama.
3. Bentuk nol pada baris ke dua sampai ke n pada kolom pertama dengan
Mengurangkan baris ke I dengan ai1/a11 x baris pertama. Simpan ai1/a11
Dalam ai1, i = 2, …….. , n.
4. Ulangi langkah (2) dan (3) untuk baris kedua sampai dengan baris (n-1) pertama,
Dengan menempatkan koefisien bernilai terbesar pada diagonal melalui pertukaran baris, kemudian
mengurangkan baris ke I dengan aij/ajj x baris ke j untuk membentuk nol pada semua posisi kolom j
dibawah diagonal. Simpan aij/ajj dalam aij, i = j + 1, …, n. Sistem yang diperoleh adalah upper-
triangular.
5. Selesaikan xn dari persamaan ke n melalui persamaan :
xn = an,n+1 / ann,
6. Selesaikan untuk xn-1, xn-2, …., x1 dengan persamaan :
nxi = (ai,n+1 - aij xj) / aii
j=i+1
2.3. METODA GAUSS-SEIDEL
Metoda gauss-seidel merupakan salah satu metoda iterasi (iterative method). Meoda ini lebih banyak
digunakan apabila koefisien matrix dari set persamaan lebih banyak merupakan bilangan nol. Penggunaan
metoda ini akan dijelaskan melalui suatu contoh penyelesaian persamaan linear.
Contoh : Selesaikan set persamaan linear berikut :
8 x1 + x2 - x3 = 8, (2.3.1)
x1 - 7 x2 + 2 x3 = -4. (2.3.2)
2 x1 + x2 + 9 x3 = 12 (2.3.3)
Set persamaan ini ditulis kembali kedalam suatu bentuk persamaan untuk mendapatkan variabel-variabel
dengan koefisien yang besar, yaitu :
x1 = 1 - 0.125 x2 + 0.125 x3 (2.3.4)
x2 = 0.571 + 0.143 x1 + 0.286 x3 (2.3.5)
x3 = 1.333 - 0.222 x1 - 0.111 x2 (2.3.6)
Pada iterasi pertama diberikan harga aproksimasi dari x1, x2, dan x3. Pada iterasi berikutnya harga x1 dihitung
dari persamaan (2.2.4) menggunakan harga aproksimasi x2 dan x3. Harga x2 dihitung dari persamaan (2.2.5)
menggunakan harga x1 yang baru dihitung dan harga approksimasi x3. Harga x3 dihitung dari persamaan (2.2.6)
menggunakan harga x1 dan x2 yang baru.
Persamaan (2.2.4) sampai dengan (2.2.6) dapat ditulis kedalam persamaan :
x1(n+1) = 1 - 0.125 x2
(n) + 0.125 x3(n) (2.3.7)
x2(n+1) = 0.571 + 0.143 x1
(n+1) + 0.286 x3(n) (2.3.8)
x3(n+1) = 1.333 - 0.222 x1
(n+1) - 0.111 x2(n+1) (2.3.9)
Dimana n = nomor iterasi.
Perhitungan dapat dimulai dengan x1 = 0, x2 = 0, dan x3 = 0. Dengan menggunakan persamaan (2.2.7) sampai
dengan persamaan (2.2.9) diperoleh hasil perhitungan sebagaimana yang ditampilkan pada Tabel 2.2.1. Dari
tabel ini dapat dilihat bahwa persen kesalahan antara nomor iterasi 5 dan 6 dapat diabaikan. Harga x1, x2 dan x3
pada kolom keenam merupakan jawaban dari contoh persoalan yang diberikan.
Tabel 2.2.1. Hasil Perhitungan Penyelesaian Set Persamaan
dengan Metoda Gauss - Seidel
Var
Nomor Iterasi
1 2 3 4 5 6
x1 0 1.000 1.041 0.997 1.001 1.000
x2 0 0.714 1.014 0.996 1.000 1.000
x3 0 1.032 0.990 1.002 1.000 1.000
Algoritma Iterasi Gauss – Seidel
Untuk menyelesaikan persamaan linear N, susun kembali baris-baris persamaan sehingga elemen diagonal
memiliki bilangan sebesar mungkin dibandingkan dengan bilangan dari koefisien lain pada baris yang sama.
Definisikan system yang disusun sebagai Ax = b. Dengan memisalkan harga awal x(1), hitung masing-
masing komponen x(n+1) , untuk I = 1, 2, ,,,,,, N, dengan persamaan :
Xi(n+1) = bi/aii - (aij/aii) xj(n+1) - (aij/aii) xj(n), n = 1,2, …….
Kondisi konvergensi diberikan oleh persamaan :
aij > aij, I = 1,2,…., N.
2.4. SISTEM PERSAMAAN NON LINEAR
Sistem persamaan non linear seperti :
(2.4.1)
(2.4.2)
dapat diselesaikan secara grafik dan numerik. Penyelesaian secara grafik didapat melalui perpotongan
lingkaran dengan kurva .
2
(1.8 , 0.8) 1
-2 -1 1 2-1
-2
(1 , -1.7)
2.4.1. Metoda Iterasi
Persamaan (2.4.1) dan persamaan (2.4.2) disusun dalam
bentuk :
x = f (x , y) dan y = g (x , y)
(2.4.3)
(2.4.4)
dimulai dengan y1 = -1,7 diperoleh nilai x dan y dari persamaan (2.4.3) dan (2.4.4), yaitu :
x : 0,993 1,006 1,0038 1,0042 1,0042
y : -1,7 -1,736 -1,7286 -1,7299 -1,7296
Penyelesaian : x = 1,0042
y = -1,7296
Kriteria Kovergensi
Sitem persamaan : x = f (x, y, z, ….)
y = g (x, y, z, ….)
z = h (x, y, z, ….)
akan konvergen jika dalam interval di sekitar akar :
Metoda Newton
Bentuk set persamaan fungsi non linear :
f (x , y) = 0 (2.4.5)
g (x , y) = 0 (2.4.6)
misalkan x = r, y = s adalah akar-akar persamaan (2.4.5) dan persamaan (2.4.6). Persamaan (2.4.5) dan
persamaan (2.4.6) dapat diekspansi menggunakan Deret Taylor di sekitar titik (x1, y1), titik didekat akar
persamaan dalam bentuk (r – x1), (s – y1) :
f (r,s) = 0 = f (x1,y1) + fx (x1,y1) (r – x1) + fy (x1,y1) (s – y1) + ………
g (r,s) = 0 = g (x1,y1) + gx (x1,y1) (r – x1) + gy (x1,y1) (s – y1) + …….
catatan : semua fungsi dihitung pada (x1,y1)
Contoh :
Carilah akar x dan y sehingga :
f (x,y) = 4 – x2 – y2 = 0
g (x,y) = 1 – ex – y = 0
dimulai dengan x1 = 1, y1 = -1,7
fx = -2x fx (1, -1,7) = -2
fy = -2y fy (1, -1,7) = 3,4
gx = -ex gx (1, -1,7) = -e1 = -2,7183
gy = -1 gy (1, -1,7) = -1
f (1,-1,7) = 0,110
g(1,-1,7) = -0,0183
2.5 Program Penyelesaian Sistim Persamaan Linear dengan Metoda Gaussian Elimination
C TUJUAN : PENYELESAIAN SISTIM PERSAMAAN LINEAR MENGGUNAKAN C METODA GAUSSIAN ELIMINATIONC C CONTOH : SELESAIKAN SET PERSAMAANC 3 X1 - X2 + 2 X3 = 12C X1 + 2X2 + 3 X3 = 11C 2 X1 - 2X2 - X3 = 2C -----------------------------------------------------------CC PARAMETER-PARAMETERC AB - KOEFISIEN AUGMENTED MATRIXC N - JUMLAH PERSAMAANC NP - JUMLAH KOLOM DALAM AUGMENTED MATRIXC NDIM - DIMENSI PERTAMA DARI MATRIXC U - KOEFISIEN VEKTOR BERUPA HASIL PERHITUNGANC ----------------------------------------------------------- DIMENSION AB(10,15),U(10) INTEGER N,NP,NDIM,I,J
OPEN (UNIT=6,FILE='ELIM.OUT',STATUS='NEW')C INPUT DATA N = 3 NP = 4 NDIM = 3
AB(1,1) = 3.0 AB(1,2) = -1.0 AB(1,3) = 2.0 AB(1,4) = 12.0 AB(2,1) = 1.0 AB(2,2) = 2.0 AB(2,3) = 3.0 AB(2,4) = 11.0 AB(3,1) = 2.0 AB(3,2) = -2.0 AB(3,3) = -1.0 AB(3,4) = 2.0
NM1 = N – 1 DO 35 I = 1,NM1 IPVT = I IP1 = I + 1 DO 10 J = IP1,N IF (ABS(AB(IPVT,I)).LT.ABS(AB(J,I))) IPVT=J 10 CONTINUE
IF (ABS(AB(IPVT,I)).LT.1.0E-6) THEN WRITE(6,100) GO TO 200 ENDIF
IF (IPVT.NE.I) THEN DO 20 JCOL = 1,NP SAVE = AB(I,JCOL) AB(I,JCOL) = AB(IPVT,JCOL) AB(IPVT,JCOL) = SAVE 20 CONTINUE ENDIF
DO 32 JROW = IP1,N IF (AB(JROW,I).EQ.0.0) GO TO 32 RATIO = AB(JROW,I) / AB(I,I) AB(JROW,I) = RATIO DO 30 KCOL = IP1,NP AB(JROW,KCOL) = AB(JROW,KCOL) - + RATIO*AB(I,KCOL) 30 CONTINUE 32 CONTINUE 35 CONTINUE
IF(ABS(AB(N,N)).LT.1.0E-6) THEN WRITE(6,100) GO TO 200 ENDIF
NP1 = N + 1 DO 50 KCOL = NP1,NP AB(N,KCOL) = AB(N,KCOL) / AB(N,N) DO 45 J = 2,N NVBL =NP1 - J L = NVBL + 1 VALUE = AB(NVBL,KCOL) DO 40 K = L,N VALUE = VALUE - AB(NVBL,K) * AB(K,KCOL) 40 CONTINUE AB(NVBL,KCOL) = VALUE/AB(NVBL,NVBL) 45 CONTINUE 50 CONTINUE
DO 51 I = 1,NDIM U(I) = AB(I,NP) 51 CONTINUE WRITE(6,150) 150 FORMAT(' VEKTOR PENYELESAIAN ADALAH = ') WRITE(6,151) 151 FORMAT(' ')
DO 53 I = 1,NDIM WRITE(6,54)I,U(I) 54 FORMAT(' I =',I5,3X,' X(I) =',F8.3) 53 CONTINUE 100 FORMAT(/'SOLUTION NOT FEASIBLE. A NEAR ZERO PIVOT', $ 'WAS ENCOUNTEREDD.') 200 STOP END
Output Sistim Persamaan Linear dengan Metoda Gaussian Elimination
VEKTOR PENYELESAIAN ADALAH = I = 1 X(I) = 3.000 I = 2 X(I) = 1.000 I = 3 X(I) = 2.000
2.5.1. Program Penyelesaian Sistim Persamaan Linear dengan Metoda Gauss-Seidel
C TUJUAN : PENYELESAIAN SET PERSAMAAN LINEAR MENGGUNAKANC METODA GAUSS-SEIDELC CONTOH : SELESAIKAN PERSAMAANC 8 X1 + X2 - X3 = 8C X1 - 7 X2 + 2 X3 = -4C 2 X1 + X2 + 9 X3 = 12C ----------------------------------------------------------CC PARAMETER - PARAMETERC A - ARRAY DARI KOEFISIEN MATRIX DENGAN BILANGAN
C TERBESAR PADA DIAGONALC B - ARRAY DARI ELEMEN-ELEMEN VEKTORC N - JUMLAH PERSAMAAN C X - HARGA APROKSIMASI AWAL, JUGA SEBAGAI OUPUTC HASIL YANG DIINGINKANC NITER - JUMLAH ITERASI YANG DIIZINKANC TOL - HARGA TOLERANSI YANG DIIZINKANC NDIM - JUMLAH DIMENSI PERTAMAC -----------------------------------------------------------
DIMENSION A(10,10),B(10),X(10) INTEGER N,NDIM,NITER,I,J REAL TOL OPEN(UNIT=6,FILE='SEIDEL.OUT',STATUS='NEW')
C INPUT DATA B(1) = 8 B(2) = -4 B(3) = 12
N = 3 X(1) = 0 X(2) = 0 X(3) = 0 NDIM = 3 NITER = 50 TOL = 0.00001 A(1,1) = 8 A(1,2) = 1 A(1,3) = -1 A(2,1) = 1 A(2,2) = -7 A(2,3) = 2 A(3,1) = 2 A(3,2) = 1 A(3,3) = 9
DO 10 I = 1,N SAVE = A(I,I) B(I) = B(I) / SAVE DO 5 J = 1,N A(I,J) = A(I,J) / SAVEC WRITE(*,*)I,J,A(I,J) 5 CONTINUE 10 CONTINUE
DO 40 ITER = 1,NITER XMAX = 0 DO 30 I = 1,N SAVE = X(I) X(I) = B(I) DO 20 J =1,N IF (J.NE.I) THEN
X(I) = X(I) - A(I,J)*X(J) ENDIF 20 CONTINUE IF (ABS(X(I) - SAVE) .GT. XMAX) THEN XMAX = ABS( X(I) - SAVE ) ENDIF 30 CONTINUE IF (XMAX.LE.TOL) GO TO 50 40 CONTINUE
IF (ITER.GE.NITER) THEN WRITE(*,*)' TOLERANSI TIDAK TERCAPAI SETELAH $ ITERASI ',ITER,'DAN HARGA X TERAKHIR $ YANG DIBERIKAN ' GO TO 60 ENDIF 50 WRITE(6,49)ITER 49 FORMAT(' JUMLAH ITERASI =',I5) WRITE(6,51) 51 FORMAT(' HARGA X YANG DIDAPAT ADALAH = ')
DO 52 I = 1,N WRITE(6,53)I,X(I) 53 FORMAT(' I = ',I5,3X,' X(I) = ',F8.3) 52 CONTINUE 60 STOP END
Output Sistim Persamaan Linear dengan Metoda Gauss-Seidel
JUMLAH ITERASI = 8
HARGA X YANG DIDAPAT ADALAH = I = 1 X(I) = 1.000 I = 2 X(I) = 1.000 I = 3 X(I) = 1.000
2.6. SOAL-SOAL
1. Diberikan matrix A, B dan vektor x, y dimana
a. Carilah A + B , 2 A - 3 B, 5 x - 3 y
b. Carilah Ax, By, xTy
c. Carilah AT, BT
2. Diberikan matriks
,
a. Carilah BA, B2, AAT
b. Carilah det(B)
c. Carilah tr(B)
d. Carilah U dan L sehingga U + L = B
3. Misalkan
,
a. Tunjukkan bahwa AB = BA = I dimana I adalah matriks 3 x 3,
b. Tunjukkan bahwa AI = IA = A.
c. Tunjukkan bahwa AC = CA dan BC = CB.
4. Tulis sebagai sistim persamaan linear
5. Selesaikan sistim persamaan linear dengan metoda Eliminasi Gauss :
3 x1 - 2 x2 + 2 x3 = 10
x1 + 2 x2 - 3 x3 = -1
4 x1 + x2 + 2 x3 = 3
6. Selesaikan sistim persamaan linear dengan metoda Eliminasi Gauss :
2 x1 + 3 x2 - 4 x3 = -3
3 x1 - 2 x2 + 5 x3 = 24
x1 + 4 x2 - 3 x3 = -6
7. Selesaikan sistim persamaan linear dengan metoda Eliminasi Gauss :
x1 + 3 x2 + 2 x3 = 3
2 x1 - x2 - 3 x3 = -8
5 x1 + 2 x2 + x3 = 9
8. a. Selesaikan dengan substitusi mundur :
4 x1 - 2 x2 + x3 = 8
- 3 x2 + 5 x3 = 3
- 2 x3 = 6.
b. Selesaikan dengan substitusi maju :
5 x1 = -10
2 x1 - 3x2 = -13
4 x1 + 3x2 - 6 x3 = 7
9. Selesaikan soal nomor 7a dan 7b dengan iterasi Gauss-Seidel, mulai dengan (2, 2, -1).
10. Selesaikan sistem :
x2 + x + - y2 = 1 dan y – sin x2 = 0
dengan metoda iterasi.
11. Selesaikan sistem :
x2 + y2 + z2 = 9,xyz = 1,x + y - z2 = 0
dengan iterasi untuk memperoleh penyelesaian di dekat (2.5, 0.2, 1.6).
12. Selesaikan soal nomor (9) dengan Metoda Newton.
13. Selesaikan dengan Metoda Newton persamaan berikut :
x3 + 3y2 = 21,x2 + 2y + 2 = 0
Buat sketsa grafik untuk menentukan nilai awal.
13. Selesaikan set persamaan non linear :
f (x,y) = x2 + y2 - 4 = 0, dan
g (x,y) = y + ex - 1 = 0
dengan metoda Hooke – Jeeves Search.
Petunjuk :
Formulasikan fungsi objektif sebagai :
ditentukan x,y dengan meminimumkan nilai F