6
Sistem Persamaan Linear
Pada bab 2, kita diminta untuk mencari suatu nilai x yang memenuhi persamaan f (x) = 0. → Pada bab ini, masalah tersebut diperumum dengan mencari − x = (x1 , x2 , ..., xn ) yang secara sekaligus memenuhi beberapa persamaan berikut f1 (x1 , x2 , ..., xn ) =0 f2 (x1 , x2 , ..., xn ) =0 .. .. . .
denganf1 , f2 , ..., fn fungsi linear
fn (x1 , x2 , ..., xn ) =0 Atau dapat ditulis dalam bentuk sebagai berikut a11 x1 + a12 x2 + ... + a1n xn = b1 a21 x1 + a22 x2 + ... + a2n xn = b2 .. .. . . am1 x1 + am2 x2 + ... + amn xn = bn Untuk menyelesaikan sistem persamaan linear seperti ini, akan digunakan 3 metode, yakni: Sistem Linear segitiga atas, eliminasi Gauss dan pivoting dan faktorisasi LU.
6.1
Sistem Linear Segitiga Atas
Metode ini pernah dipelajari pada tingkat yang lebih awal. Caranya adalah mengeliminasi sistem persamaan sehingga didapatkan sistem linear dalam bentuk segitiga atas. Bentuk seperti ini memudahkan kita untuk melakukan substitusi balik dan mendapatkan solusi bagi sistem persamaan linear yang dimaksud. Contoh: Selesaikan sistem persamaan linear berikut x1 − 2x2 + 4x3 = 1 3x1 − x2 + 2x3 = 7 2x1 + 3x2 − 5x3 = −7 Solusi: Eliminasi Gauss akan dikenakan pada matriks lengkap linear di atas sebagai berikut. 1 −2 4 | 1 1 1 −2 4 | 1 3 −1 2 | 7 → 0 5 → 0 10 | 4 0 0 7 −13 | −9 2 3 −5 | −7
dari sistem persamaan −2 4 | 1 5 10 | 4 0 −27 | − 73 5
Yang diberi tanda kotak adalah baris yang menjadi tumpuan (pivot row ). Sistem persamaan linear di atas telah menjadi bentuk matriks segitiga atas. Dengan menggunakan substitusi balik, diperoleh solusi bagi sistem persamaan linear di atas adalah −73/5 = 0.540741 −27 4 − 5.407407 5x2 + 10(0.540741) = 4 → x2 = = −0.281481 5 x1 − 2(−0.281481) + 4(0.540741) = 1 → x1 = 3.725926 x3 =
22
Latihan : Selesaikan sistem persamaan linear berikut dengan menggunakan substitusi balik 4x1 − x2 + 2x3 + 3x4 = 20 −2x2 + 7x3 − 4x4 = = −7 6x3 + 5x4 = 4 3x4 = 6 Latihan : Tunjukkan bahwa sistem persamaan linear berikut tidak memiliki solusi 4x1 − x2 + 2x3 + 3x4 = 20 0x2 + 7x3 − 4x4 = −7 6x3 + 5x4 = 4 3x4 = 6 Contoh : Tunjukkan bahwa sistem persamaan linear berikut memiliki solusi tak hingga banyak. 4x1 − x2 + 2x3 + 3x4 = 20 0x2 + 7x3 + 0x4 = −7 6x3 + 5x4 = 4 3x4 = 6
6.2
Eliminasi Gauss dan Pivoting
Eliminasi Gauss yang biasa kadang tidak memberikan hasil sesuai kenyataan, terutama dimana elemen tumpuan nol. Untuk lebih jelasnya, perhatikan kasus berikut. Ini adalah matriks lengkap dari suatu sistem persamaan linear Ax = b. � 0.0001 0.5 | 0.5 0.4 −0.3 | 0.1 Solusi dari sistem ini adalah [0.9999; 0.9998]. Periksalah bahwa nilai-nilai ini memenuhi kedua persamaa tersebut secara sekaligus. Selanjutnya dengan menggunakan cara yang diberikan pada subbab sebelumnya akan diperiksa bahwa hasil yang diperoleh ternyata berbeda. Gunakan baris 1 sebagai tumpuan. Dengan demikian entri-21 akan berisi nol dan entri-22 = −0.3 − 0.4/0.0001 = −2000 dan entri-23 = 0.1 − 0.4/0.0001 = −2000. � 0.0001 0.5 | 0.5 0 −2000 | −2000 Dengan menggunakan substitusi balik, diperoleh bahwa x2 =
−2000 =1 −2000
x1 =
0.5 − 0.5 =0 −.0001
Ini jelas jauh berbeda dari solusi sebenarnya. Hal ini disebabkan oleh pemilihan elemen tumpuan yang sangat kecil. Hal ini ditanggulangi dengan mencari elemen pada kolom 23
tumpuan dan mengubah entri terbesar menjadi elemen tumpuan. Pada soal ini, karena 0.4 > 0.0001, kedua baris dipertukarkan sehingga baris kedua menjadi baris tumpuan sebagai berikut � � 0.4 −0.3 | 0.1 0.4 −0.3 | 0.1 → 0 0.5 | 0.5 0.0001 0.5 | 0.5 Dengan substitusi balik diperoleh x2 =
0.5 =1 0.5
x1 =
1 (0.1 + (0.3)1) = 1 0.4
Solusi ini mendekati solusi yang sebenarnya. Proses eliminasi Gauss dengan cara seperti ini dinamakan eliminasi Gauss dengan strategi penumpuan parsial. Sementara jika strategi ini dilakukan dengan mencari nilai terbesar dari suatu submatriks maka dinamakan dengan eliminasi Gauss dengan penumpuan total. Teknik lain dengan menggunakan penumpuan adalah dengan eliminasi Gauss dengan pivot parsial terskala. Misalkan urutan persamaan yang digunakan dinotasikan dengan vektor baris {l1 , l2 , ..., ln } . Sebut l = [l1 , l2 , ..., ln ] vektor indeks. Definisikan si = max |aij | dengan 1 ≤ i ≤ n 1≤j≤n
sehingga s = [s1 , s2 , ..., sn−1 ] disebut vektor skala. Pada awal proses, kita tidak langsung menggunakan persamaan (1) sebagai persamaan pivot tetapi menggunakan persamaan yang rasio antara |ai,1 | dengan si untuk 1 ≤ i ≤ n−1 terbesar. Cara yang terbaik adalah: 1. Definisikan vektor indeks l = [l1 , l2 , ..., ln ] = [1, 2, ..., n] 2. Pilih j indeks yang mempunyai rasio terbesar dalam himpunan |ali 1 | :1≤i≤n sl i 3. Tukar lj menjadi l1 vektor indeks l 4. Kalikan baris l1 dengan konstanta
ali 1 al1 1 dan kurangkan dengan baris li dengan 2 ≤ i ≤ n
5. Ulangi langkah (2) − (4) Tentukan solusi dari SPL 3 −6 6 12
berikut ini: −13 4 −2 −8
9 3 x1 x2 1 −18 2 4 x3 6 10 x4 24
−19 −34 = 16 26
Mula-mula vektor indeks l = [1, 2, 3, 4] dan vektor skala s = [13, 18, 6, 12] Perhatikan rasio berikut: 3 6 6 12 |ali 1 | : i = 1, 2, 3, 4 = max =1 , , , max sli 13 18 6 12 Nilai maksimumnya muncul pada indeks j = 3. pivot. Diperoleh: 6 −2 2 4 x3 0 2 3 −14 x2 0 −12 8 1 x1 0 −4 2 2 x4
Sehingga baris (3) menjadi persamaan
16 −18 = −27 −6
sehingga vektor indeks yang baru l = [3, 2, 1, 4]. Langkah selanjutnya perhatikan rasio berikut: 12 2 12 4 |ali 2 | = : i = 2, 3, 4 = max , , max sl i 18 13 12 13
maka pilih j = 3 dan vektor indeks yang baru l = [3, 1, 2, 4] dan 6 −2 2 4 x3 16 0 −12 8 x1 −27 1 = 45 13 83 0 0 − x − 2 3 6 2 5 2 x4 0 0 −3 3 3 Perhatikan rasio berikut: 13 13/3 2/3 |ali 2 | = : i = 3, 4 = max , max sl i 18 12 54 maka pilih j = 3 dan vektor indeks yang baru tetap l = [3, 1, 2, 4] dan 6 −2 2 4 x3 16 0 −12 8 1 x1 = −27 83 13 45 0 0 − 6 x2 − 2 3 6 6 0 0 0 − 13 − 13 x4 Jadi solusi SPL tersebut adalah x4 = x2 =
6 − 13 6 = 1 − 13
+ − 45 2 13 3
83 6
= −2
−27 − 8(−2) − 1(1) =1 −12 16 + 2(1) − 2(−2) − 4(1) =3 x3 = 6 x1 =
Tugas Mandiri: Untuk tiap soal berikut, kecuali yang soalnya diberikan, selesaikan dengan menggunakan eliminasi Gauss baik dengan tanpa penumpuan maupan dengan penumpuan (parsial dan total). Bandingkan hasil yang diperoleh. 25
1. 3x1 + 4x2 + 3x3 = 16 x1 + 5x2 − x3 = −12 6x1 + 3x2 + 7x3 = 102
2.
1 −1 2 1 x1 3 2 1 4 x2 5 8 6 3 x3 4 2 5 3 x4
1 1 = 1 −1
3. Tunjukkan bahwa SPL berikut mempunyai solusi tunggal jika α = 0, tidak ada solusi jika α = −1 dan mempunyai banyak solusi jika α = 1. x1 + 4x2 + αx3 = 6 2x1 − x2 + 2αx3 = 3 αx1 + 3x2 + x3 = 5
4.
x1 + 2x2 = 7 2x1 + 3x2 − x3 = 9 4x2 + 2x3 + 3x4 = 10 2x3 − 4x4 = 12 5. Tentukan parabola y = A + Bx + Cx2 yang melalui (1,4), (2,7), dan (3,14). 6. Analogi soal nomor 5 melalui titik (1,6),(2,5), dan (3,2) 7. Tentukan persamaan kubik y = A + Bx + Cx2 + Dx3 yang melalui (0,0),(1,1),(2,2) dan (3,2). 8. Selesaikan dengan menggunakan pembulatan 4 digit di belakan koma. Gunakan eliminasi Gauss dengan pivot parsial dan eliminasi Gauss dengan pivot parsial terskala. (a) (b)
2x1 − 3x2 + 100x3 = 1 x1 + 10x2 − 0.001x3 = 0 3x1 − 100x2 + 0.01x3 = 0 x1 + 20x2 − x3 + 0.001x4 = 0 2x1 − 5x2 + 30x3 − 0.1x4 = 1 5x1 + x2 − 100x3 − 10x4 = 0 2x1 − 100x2 − x3 + x4 = 0 26
6.3
Faktorisasi LU
Sistem Persamaan Linear n × n dapat ditulis dalam bentuk matriks: Ax = b dengan A merupakan matriks koefisien a11 a21 A = a31 .. . an1
(22)
yang berbentuk: a12 a13 a22 a23 a32 a33 .. ... . an2 an3
··· ··· ··· ...
a1n a2n a3n .. .
···
ann
Akan ditunjukkan bahwa algoritma Gauss sederhana yang diterapkan pada A dapat memfaktorkan A menjadi hasil kali dua matriks sederhana yaitu matriks diagonal bawah 1 l21 1 l31 l32 1 L= .. .. .. . . . . . . ln1 ln2 ln3 · · · 1 dan matriks diagonal atas
u11 u12 u13 · · · u22 u23 · · · u33 · · · U = .. .
u1n u2n u3n .. . unn
Dengan kata lain, dapat diperoleh A = LU Contoh: Misalkan diberikan SPL 6 −2 12 −8 3 −13 −6 4
sebagai berikut: 2 4 x1 6 10 x2 = 9 3 x3 1 −18 x4
16 26 −19 −34
Setelah dilakukan eliminasi Gauss sederhana diperoleh SPL sebagai berikut: x1 6 −2 2 4 16 0 −4 2 2 x2 −6 0 0 2 −5 x3 = −9 0 0 0 −3 −3 x4
(23)
Eliminasi ini dapat diinterpretasikan bahwa dari persamaan (22) dapat diperoleh: M Ax = M b 27
(24)
dengan matriks M dipilih sedemikian sehingga M A adalah matriks koefisien untuk SPL pada persamaan (23). Sehingga diperoleh 6 −2 2 4 0 −4 2 2 MA = 0 0 2 −5 = U 0 0 0 −3 Langkah pertama pada eliminasi Gauss sederhana menghasilkan SPL: x1 6 −2 2 4 16 0 −4 2 2 x2 −6 0 −12 8 1 x3 = −27 0 2 3 −14 −18 x4
Langkah ini dapat diinterpretasikan dari persamaan (22) dapat diperoleh: M1 Ax = M1 b dengan
1 −2 M1 = −1 2 1
0 1 0 0
0 0 1 0
0 0 0 1
Perhatikan bahwa matriks M1 merupakan matriks dengan diagonal utamanya bernilai 1, dan hanya kolom pertama yang berisi elemen tak nol dan bilangan ini merupakan negatif dari koefisien pengali masing-masing baris. Langkah kedua pada eliminasi Gauss sederhana menghasilkan SPL: 6 −2 2 4 x1 16 0 −4 2 2 x2 −6 0 0 2 −5 x3 = −9 0 0 4 −13 x4 −21 yang ekivalen dengan M2 M1 Ax = M2 M1 b dengan
1 0 0 0 1 0 M2 = 0 −3 1 0 12 0
0 0 0 1
Begitu juga dengan langkah ketiga ekivalen dengan
M3 M2 M1 Ax = M3 M2 M1 b dengan
1 0 M3 = 0 0
0 0 1 0 0 1 0 −2 28
0 0 0 1
Secara lengkap diperoleh: M = M3 M2 M 1
(25)
Sehingga dari persamaan (24) dan (25) diperoleh A = M −1 U = (M3 M2 M1 )−1 U = M1−1 M2−1 M3−1 U = LU Karena Mk adalah matriks spesial maka Mk−1 dapat diperoleh dengan mengubah tanda pada elemen negatif pengali Sehingga diperoleh L = M1−1 M2−1 M3−1 1 0 0 0 2 1 0 0 = 1 0 1 0 2 −1 0 0 1 1 0 0 2 1 0 = 1 3 1 2 −1 − 12 2
1 0 0 1 0 3 0 − 21 0 0 0 1
0 0 1 0
1 0 0 0 0 1 0 0 0 1 0 0
0 0 1 2
0 0 0 1
Penyelesaian sistem persamaan linear ini adalah sebagai berikut. Bentuk di atas dapat dituliskan sebagai berikut (LU )x = b 1 0 2 1 1 3 2 −1 − 12 LY = b
0 0 1 2
6 −2 2 4 0 0 0 −4 2 2 0 0 0 2 −5 0 0 0 −3 1
dengan Y = U x
16 −6 = −27 −18
Selesaikan sistem persamaan LY = b untuk nilai - nilai Y . Kemudian dari Y yang diperoleh, selesaikan untuk nilai- nilai x, yakni solusi sistem persamaan linear yang dikehendaki. Matriks Permutasi Pada contoh yang dikerjakan di atas, diasumsikan tidak terdapat pertukaran baris pada saat melakukan eliminasi Gauss. Akan tetapi hal ini tidak dapat selalu terjadi. Sebagai contoh, perhatikan contoh berikut. 1 2 6 A = 4 8 −1 (26) −2 3 5
29
Misalkan matriks A di 1 4 −2
atas memiliki faktorisasi LU , yakni 2 6 1 0 0 u11 u12 u13 8 −1 = m21 1 0 0 u22 u23 3 5 m31 m32 1 0 0 u33
Periksalah bahwa kita akan mendapatkan hal - hal yang bertentangan, sehingga matriks A di atas tidak dapat dibuat faktorisasi LU . Akan tetapi, hal ini dapat diatasi dengan mengalikan matriks A dengan matriks permutasi. Matriks Permutasi Matriks Permutasi N × N adalah matriks yang mempunyai tepat satu buah elemen pada setiap baris dan kolom, yakni 1 dan 0 selain itu. Dengan demikian, baris-baris pada P adalah permutasi baris-baris dari matriks identitas. Sebagai contoh, matriks berikut adalah matriks permutasi 0 1 0 0 baris 2 I4 1 0 0 0 baris 1 I4 P = 0 0 0 1 = baris 4 I4 0 0 1 0 baris 3 I4 Mengalikan sebarang matriks A4×4 dari kiri dengan matriks permutasi di atas akan menghasilkan matriks A dengan baris 1 bertukar dengan baris 2 serta baris 3 bertukar dengan baris 4. Verifikasilah hal ini. Pada masalah semula, faktorisasi LU atas matriks pada persamaan (26) tidak dapat dikerjakan. Hal ini dapat ditanggulangai dengan mengalikan A pada persamaan tersebut dengan matriks permutasi P sehingga diperoleh 1 0 0 1 2 6 1 2 6 P A = 0 0 1 4 8 −1 = −2 3 5 0 1 0 −2 3 5 4 8 −1 Verifikasilah bahwa matriks tersebut dapat difaktorisasi LU Tugas Mandiri: Tentukan faktorisasi LU dari matriks - matriks berikut. 1.
2.
3.
4.
−5 2 −1 1 0 3 3 1 6
1 −2 7 4 2 1 2 5 −2
1 0 3 3 1 6 −5 2 −1
5. 1 1 0 4 2 −1 5 0 5 2 1 2 −3 0 2 6
4 2 −1 2 5 −2 1 −2 7
30
