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 dalam bentuk : a13 ........ a1n a11 a12 a a 22 a 23 ........ a 2 n A = 21 ..... ..... ..... ........ ...... a m1 a m2 a m3 ........ a mn 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 2 1 − 1 A = 1 − 2 3 − 2 1 2 Contoh : Matriks Kompleks 0 − i A = 0 i 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 elemenelemennya merupakan elemen-elemen yang berhubungan dari matriks A dan B. = A - B = [aij] - [bij] = [cij] C Contoh : − 1 4 2 A = 3 0 5 − 2 1 6
− 2 A + B = C = 4 − 3
9 4 3
− 4 A − B = C = 2 − 1
−1 −4 −1
(2.1.2)
;
3 B = 1 − 1
5 4 2
0 − 3 − 4
2 2 2 2 8 10
Jika matriks A = (nxm) dan matriks B = (mxr) dikalikan akan menghasilkan : (a11 b11 + ... + a1m b m1 )... (a11 b1r + ... + a1m b mr ) (a b + ... + a b )... (a b + ... + a b ) 2m m1 21 1r 2m mr 21 11 a ij bij = cij = . . (a n1 b11 + ... + a nm b m1 )... (a n1 b1r + ... + a nm b mr ) Perkalian antara skalar dengan matriks akan menghasilkan suatu matriks yang elemenelemennya adalah perkalian skalar dengan elemen matriks asal :
[ ][ ] [ ]
k A = C, Contoh :
2 A= − 1
4 2
[cij] = k [aij]
2 − 1 B = 0 1 4 − 1
0 3
− 4 B . A = − 1 9
0 2 14
6 3 − 3
8 − 2 A. B = 13 − 3 ; 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 : a12 ... a1n a11 x1 b1 a x b a . . . a 22 2n A = 21 x = 2 b = 2 . an2 ... a nn a n1 , xn , bn 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 : −1 2 : 12 3 1 2 3 : 11 2 −2 −2 : 2
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
Row 3 – (-1.334/2.333) Row 2
7.004
0
0
-1.000 -1.993
Melalui back substitution yang dimulai dari persamaan ketiga dan kembali ke persamaan kedua dan pertama didapat : − 1.993 x3 = = 1.993 − 1.000
x1 =
7.004 − 2.334 x3 = 1.008 2.3333
x2 =
12 − (− 1 x2 + 2 x3 ) = 3.007 3
Algoritma Metoda Eliminasi Gauss Buat augmented matrix dari n x n matriks dengan vector sisi kanan sama dengan 1. Menjadi matriks n x (n + 1). Pertukarkan baris jika diperlukan agar a11 menjadi koefisien terbesar pada 2. Kolom pertama. Bentuk nol pada baris ke dua sampai ke n pada kolom pertama dengan 3. Mengurangkan baris ke I dengan ai1/a11 x baris pertama. Simpan ai1/a11 Dalam ai1, i = 2, …….. , n. Ulangi langkah (2) dan (3) untuk baris kedua sampai dengan baris (n-1) pertama, 4. 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. Selesaikan xn dari persamaan ke n melalui persamaan : 5. xn = an,n+1 / ann, Selesaikan untuk xn-1, xn-2, …., x1 dengan persamaan : 6. n
x = (a i
i,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 x
1
+ x2 -
(2.3.1) (2.3.2) (2.3.3)
x3 = 8,
x1 - 7 x2 + 2 x3 = -4.
2 x1 + x2 + 9 x3 = 12 Set persamaan ini ditulis kembali kedalam suatu bentuk persamaan untuk mendapatkan variabel-variabel dengan koefisien yang besar, yaitu : x
=1
x
= 0.571 + 0.143 x1
1 2
(2.3.4) (2.3.5)
- 0.125 x2 + 0.125 x3 + 0.286 x3
x
= 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. 3
Persamaan (2.2.4) sampai dengan (2.2.6) dapat ditulis kedalam persamaan :
(n+1)
x1
= 1
-
(n)
0.125 x2
(n)
+ 0.125 x3
(2.3.7) x
(n+1)
x
(n+1)
2 3
(n+1)
= 0.571 + 0.143 x1 = 1.333 - 0.222 x1
(n+1)
(n)
+ 0.286 x3 - 0.111 x2
(n+1)
(2.3.8) (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 Nomor Iterasi Var 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 : x2 + y2 = 4 x
(2.4.1)
(2.4.2) dapat diselesaikan secara grafik dan numerik. Penyelesaian secara grafik didapat melalui 2 2 x perpotongan lingkaran x + y = 4 dengan kurva y = 1 − e . e
y
+
= 1
2 (1.8
1
, 0.8)
-2
-1
1
-1 -2 (1
, -1.7)
2
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) x2 + y2 = 4 y2 = 4 − x2 y = ± 4 − x2 ex + y = 1 ex = 1 − y ln (e x ) = ln (1 − x = ln (1 − y)
(2.4.3)
y)
(2.4.4)
dimulai dengan y1 = -1,7 diperoleh nilai x dan y dari persamaan (2.4.3) dan (2.4.4), yaitu :
0,993
x:
-1,7
y:
1,006 -1,736
1,0038 1 ,0042 -1,7286 -1,7299 - 1,7296
1,0042
Penyelesaian : x = 1,0042
y = -1,7296 Kriteria Kovergensi
x = f (x, y, z, ….)
Sitem persamaan :
y = g (x, y, z, ….) z = h (x, y, z, ….) akan konvergen jika dalam interval di sekitar akar : fx
+
fy
+
fz
+ ......... < 1,
gx
+
gy
+
gz
+ ......... < 1,
hx
+
hy
+
hz
+ ......... < 1,
Metoda Newton Bentuk set persamaan fungsi non linear :
f (x , y) = 0 g (x , y) = 0
(2.4.5)
(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) + ………
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) + …….
r − x1
=
− f −g
fy gy
fx gx
fy gy
s − y1
=
− f −g
fy gy
fx gx
fy gy
catatan : semua fungsi dihitung pada (x1,y1)
Contoh :
Carilah akar x dan y sehingga : f (x,y) = 4 – x
2
2
–y =0
g (x,y) = 1 – e
x
–y=0 dimulai dengan x1 = 1, y1 = -1,7
f
x
= -2x
f
x
(1, -1,7) = -2
f
y
= -2y
f
y
(1, -1,7) = 3,4
g
= -e
g
= -1
g
x
x y
r = x1
1
x
g +
− f −g
fy gy
fx gx
fy gy
y
(1, -1,7) = -e = -2,7183
(1, -1,7) = -1
f (1,-1,7) = 0,110
g(1,-1,7) = -0,0183
r= 1 +
− 0,110 + 0,0183 −2
3,4 −1 3,4
= 1,0042
− 2,7183 − 1
s
=
− 1,7
+
−2 − 0,110 − 2,7183 0,0183 11,2422
=
− 1,7298
2.5 Program Penyelesaian Sistim Persamaan Linear dengan Metoda Gaussian Elimination
C TUJUAN : PENYELESAIAN SISTIM PERSAMAAN LINEAR MENGGUNAKAN C METODA GAUSSIAN ELIMINATION C C CONTOH : SELESAIKAN SET PERSAMAAN
C 3 X1 X2 + 2 X3 = 12 C X1 + 2X2 + 3 X3 = 11 C 2 X1 2X2 X3 = 2 C C C PARAMETERPARAMETER C AB KOEFISIEN AUGMENTED MATRIX C N JUMLAH PERSAMAAN C NP JUMLAH KOLOM DALAM AUGMENTED MATRIX C NDIM DIMENSI PERTAMA DARI MATRIX C U KOEFISIEN VEKTOR BERUPA HASIL PERHITUNGAN C 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.0E6) 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.0E6) 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= I= I=
1 2 3
X(I) = 3.000 X(I) = 1.000 X(I) = 2.000
2.5.1. Program Penyelesaian Sistim Persamaan Linear dengan Metoda Gauss-Seidel C TUJUAN : PENYELESAIAN SET PERSAMAAN LINEAR MENGGUNAKAN C METODA GAUSSSEIDEL C CONTOH : SELESAIKAN PERSAMAAN C 8 X1 + X2 X3 = 8 C X1 7 X2 + 2 X3 = 4 C 2 X1 + X2 + 9 X3 = 12 C
C C PARAMETER PARAMETER C A ARRAY DARI KOEFISIEN MATRIX DENGAN BILANGAN C TERBESAR PADA DIAGONAL C B ARRAY DARI ELEMENELEMEN VEKTOR C N JUMLAH PERSAMAAN C X HARGA APROKSIMASI AWAL, JUGA SEBAGAI OUPUT C HASIL YANG DIINGINKAN C NITER JUMLAH ITERASI YANG DIIZINKAN C TOL HARGA TOLERANSI YANG DIIZINKAN C NDIM JUMLAH DIMENSI PERTAMA C
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) / SAVE C 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 Diberikan matrix A, B dan vektor x, y dimana 1.
1 A = 4 − 1
−3 5 9
2 6 7
1 3 0
− 3 B = 6 13
2
1
1 4
9 1
4 − 2 2
Carilah A + B , 2 A - 3 B, 5 x - 3 y a. T By, x y b. Carilah Ax, T T c. Carilah A , B 2.
Diberikan matriks
− 1 2 x = 3 − 2 4 1 y = 5 − 3
2.
− 2 A = 2 1
3
1
0 6
−4 −3 2
5 − 1 2
,
4 B = 1 2
−2 −3 5
1 − 4 7
T
a. Carilah BA, B , AA Carilah det(B) b. Carilah tr(B) c. Carilah U dan L sehingga U + L = B d.
Misalkan 1 A = 3 2
3.
−1 C = 0 − 1 a.
−2 1
2 1 1
0 1 1
,
−1 B = 1 2
−2 3 4
4 − 5 − 7
2 3 1
0
Tunjukkan bahwa AB = BA = I dimana I adalah matriks 3 x 3,
1 I = 0 0
0 1 0
0 0 1
Tunjukkan bahwa AI = IA = A. b. Tunjukkan bahwa AC = CA dan BC = CB. c. Tulis sebagai sistim persamaan linear 3 1 − 1 x1 3 x 1 0 1 1 2 = x 3 6 −1 4 1 1 1 − 5 16 x 4 Selesaikan sistim persamaan linear dengan metoda Eliminasi Gauss : 5. 3 x1 - 2 x2 + 2 x3 = 10 x1 + 2 x2 - 3 x3 = -1 4 x1 + x2 + 2 x3 = 3 Selesaikan sistim persamaan linear dengan metoda Eliminasi Gauss : 6. 2 x1 + 3 x2 - 4 x3 = -3 3 x1 - 2 x2 + 5 x3 = 24 x1 + 4 x2 - 3 x3 = -6 4. 1 2 0 0
Selesaikan sistim persamaan linear dengan metoda Eliminasi Gauss :
7.
x1 + 3 x2 + 2 x3 = 3 2 x1 - x2 - 3 x3 = -8 5 x1 + 2 x2 + x3 = 9 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
8.
9. 10.
Selesaikan soal nomor 7a dan 7b dengan iterasi Gauss-Seidel, mulai dengan (2, 2, -1). Selesaikan sistem :
x
2
2
+ x + - y = 1 dan
y – sin x
2
=0
dengan metoda iterasi.
11.
Selesaikan sistem :
x
2
2
2
+ y + z = 9,
xyz = 1, x + y - z
2
=0 dengan iterasi untuk memperoleh penyelesaian di dekat (2.5, 0.2, 1.6). Selesaikan soal nomor (9) dengan Metoda Newton. 12. Selesaikan dengan Metoda Newton persamaan berikut : 13. x3 + 3y2 = 21,
x
2
+ 2y + 2 = 0
Buat sketsa grafik untuk menentukan nilai awal. 13. Selesaikan set persamaan non linear : f (x,y) = x
2
2
+ y - 4 = 0, dan
g (x,y) = y + e
x
-1=0
dengan metoda Hooke – Jeeves Search.
Petunjuk : Formulasikan fungsi objektif sebagai : F F
= =
[f (x, y)]2 (y
+
e
x
+
[g2(x, y)]2
− 1)
+
( x2
+
y2
ditentukan x,y dengan meminimumkan nilai F
− 4)2
