Solusi Sistem Persamaan Linear Sistem persamaan linear:
a11x1
+ a12x2
+ a13x3 ⋯ + a1n xn
= b1
a21x1 a31x1
+ a22x2 + a32x2
+ a23x3 ⋯ + a2n xn + a33x3 ⋯ + a3n xn
= b2 = b3
⋮
⋮
an1x1
+ an2 x2
⋮
⋱
⋮
+ an3x3 ⋯ + ann xn
⋮ = bn
n buah persamaan dengan n buah unknown
xj
aij dan bi diketahui i, j = 1, 2, …, n
xj = ?
Soal:
Jawab:
2x − 3y + 2z = −6
(1)
− x + 2y − 3z = 2
(2)
x+ y− z =0
(3)
2x −
2x −
3y + 2z = −6
(1)
0.5y − 2z = −1
(2)
2.5y − 2z = 3
(3)
3y + 2z = −6
(1)
0.5y − 2z = −1
(2)
8z = 8
3 persamaan dan 3 unknown
eliminasi x: pers. (2) + 0.5 pers. (1) pers. (3) – 0.5 pers. (1)
eliminasi y: pers. (3) – 5 pers. (2)
(3)
z =1 − 1 + 2z y= =2 0.5 − 6 + 3y − 2z x= = −1 2
substitusi mundur: pers. (3) mencari z pers. (2) mencari y pers. (1) mencari x
Dalam bentuk matriks: Soal:
2 x − 6 2 −3 2 − 3 y = 2 −1 1 1 − 1 z 0
Jawab:
2 x − 6 2 −3 0 0.5 − 2 y = − 1 0 2.5 − 2 z 3 2 x − 6 2 −3 0 0.5 − 2 y = − 1 0 0 8 z 8
z =1 − 1 + 2z y= =2 0.5 − 6 + 3y − 2z x= = −1 2
Eliminasi Gauss Metode Eliminasi Gauss mencari solusi sebuah sistem persamaan linear dengan cara seperti ditunjukkan pada contoh sebelum ini:
a11 a21 a 31 ⋮ a n1
a13 ⋯ a1n x1 b1 a23 ⋯ a2n x2 b2 a33 ⋯ a3n x3 = b3 ⋮ ⋱ ⋮ ⋮ ⋮ an3 ⋯ ann xn bn
a12 a22 a32 ⋮ an2
aij(0) = aij , bi(0) = bi (k) ij
a
(k) i
b
(k -1) ij
aik(k-1) (k-1) − (k-1) akj akk
(k −1) i
aik(k-1) (k −1) − (k-1) bk akk
=a
=b
(k = 1, ..., n − 1;
a 0 0 ⋮ 0
(0) 11
(0) 12 (1) 22
a a
0 ⋮ 0
a
a a
(0) 13 (1) 23 (2) 33
⋮ 0
x1 b x2 b ⋯ a x3 = b ⋱ ⋮ ⋮ ⋮ (n-1) (n-1) x ⋯ ann n bn ⋯ ⋯
(0) 1n (1) 2n (2) 3n
a a
(0) 1 (1) 2 (2) 3
i = k + 1, ..., n; j = k, ..., n)
aij(m) , bi(m) ≡ aij , bi pada langkah ke m halaman berikut
Substitusi mundur:
a11(0) 0 0 ⋮ 0
(0) a12 (1) a22
0 ⋮ 0
a1n(0) x1 b1(0) (1) (1) a2n x2 b2 (2) x3 = b3(2) a3n ⋱ ⋮ ⋮ ⋮ (n-1) (n-1) x ⋯ ann n bn
(0) a13 ⋯ (1) a23 ⋯ (2) ⋯ a33
⋮ 0
bn(n-1) xn = (n-1) ann (n- j-1) n-j
b xn − j =
n
∑a
−
k =n- j+1 (n- j-1) n - j,n - j
a
(n- j-1) n - j,k k
x
(j = 1, ..., n − 1)
A
X = B
atau
AX = B
Jadi, metode Eliminasi Gauss terdiri dari dua tahap: 1. triangulasi: mengubah matriks A menjadi matriks segitiga (matriks B dengan begitu juga berubah)
=
=
2. substitusi mundur: menghitung x mengikuti urutan terbalik, dari yang terakhir ( xn ) sampai yang pertama ( x1 )
LU Decomposition
A
X = B
atau
AX = B
Pada metode LU Decomposition, matriks A ditulis ulang sebagai perkalian matriks L dan U (matriks A diurai menjadi matriks L dan U). Matriks L dan U merupakan matriks segitiga. Matriks B tidak berubah, karena matriks A tidak berubah, melainkan hanya ditulis ulang.
A
X = B
U L
X = B
Langkah: 1. Cari matriks L dan U sehingga A = LU. Matriks B tetap.
A
=
U
U
L
L
X = B
2. Definisikan sebuah matriks kolom baru, misalnya Y, yaitu Y = UX, sehingga LY = B. Lalu hitung y dengan substitusi maju (mulai dari y1 sampai yn ).
U
Y =
X
L
Y = B
3. Hitung x dengan substitusi mundur (mulai dari xn sampai x1 ). U
X = Y
Jelas bahwa metode LU Decomposition pada prinsipnya sama dengan metode Eliminasi Gauss: matriks U merupakan hasil triangulasi matriks A, yang juga mengakibatkan B berubah menjadi Y.
Mencari matriks L dan U:
l11 0 0 l21 l22 0 l l l 31 32 33 ⋮ ⋮ ⋮ ln1 ln2 ln3
⋯ 0 1 u12 u13 ⋯ 0 0 1 u23 1 ⋯ 0 0 0 ⋮ ⋱ ⋮ ⋮ ⋮ ⋯ lnn 0 0 0
⋯ u1n ⋯ u2n ⋯ u3n = ⋱ ⋮ ⋯ 1
a11 a21 a 31 ⋮ an1
a12 a22 a32 ⋮ an2
a13 ⋯ a1n a23 ⋯ a2n a33 ⋯ a3n ⋮ ⋱ ⋮ an3 ⋯ ann
Diperoleh:
ai1 = li1 a1j = l11u1j ai2 = li1u12 + li2 a2j = l21u1j + l22u2j ai3 = li1u13 + li2u23 + li3 a3j = l31u1j + l32u2j + l33u3j …
→ li1 = ai1 a1j → u1j = l11 → li2 = ai2 − li1u12 a2j − l21u1j → u2j = l22 → li3 = ai3 − li1u13 − li2u23 a3j − l31u1j − l32u2j → u3j = l33
(i = 1, ..., n) (j = 2, ..., n) (i = 2, ..., n) (j = 3, ..., n) (i = 3, ..., n) (j = 4, ..., n)
Jadi, elemen matriks L dan U dicari menurut:
li1 = ai1 u1j =
(i = 1, ..., n)
a1j
(j = 2, ..., n)
l11 j−1
lij = aij − ∑ likukj
(i = j, ..., n; j = 2, ..., n)
k =1 i−1
aij − ∑likukj uij =
k =1
lii
(j = i + 1, ..., n; i = 2, ..., n - 1)
secara bergantian: 1. matriks L kolom 1, matriks U baris 1 2. matriks L kolom 2, matriks U baris 2 3. … 4. matriks L kolom (n-1), matriks U baris (n-1) 5. matriks L kolom n
Substitusi maju untuk menghitung y:
l11 0 0 l21 l22 0 l l l 31 32 33 ⋮ ⋮ ⋮ ln1 ln2 ln3
⋯ 0 y1 b1 ⋯ 0 y2 b2 ⋯ 0 y3 = b3 ⋱ ⋮ ⋮ ⋮ ⋯ lnn yn bn
y1 =
b1 l11 i−1
bi − ∑ lij yj yi =
j=1
(i = 2, ..., n)
lii
Substitusi mundur untuk menghitung x:
1 u12 u13 0 1 u23 0 0 1 ⋮ ⋮ ⋮ 0 0 0
⋯ u1n x1 y1 ⋯ u2n x2 y2 ⋯ u3n x3 = y3 ⋱ ⋮ ⋮ ⋮ ⋯ 1 xn yn
xn = yn n
xn-i = yn −i −
∑u
n −i, j
j=n −i+1
xj (i = 1, ..., n − 1)
2 2 −3 − 6 AX = B Kembali ke soal , dengan A = − 1 2 − 3 , B = 2 . 1 0 1 − 1
Jawab:
A = LU
0 1 2 0 1 − 1.5 L = − 1 0.5 0 , U = 0 1 − 4 1 2.5 8 0 0 1
Y = UX, LY = B
UX = Y
−1 X = 2 1
− 3 Y = − 2 1
Kasus Beberapa Sistem Persamaan Linear Pada kasus yang lebih umum bisa saja terdapat beberapa sistem persamaan linear dengan nilai B yang berlainan, namun memiliki nilai A yang sama. Dalam bentuk matriks sistem seperti ini dituliskan sebagai:
A
Keterangan: •
•
X
=
B
atau AX = B
A matriks n x n, X dan B matriks n x m, dengan m = jumlah sistem persamaan linear, n = jumlah persamaan / unknown dalam tiap sistem persamaan tersebut Tiap kolom matriks X merupakan solusi untuk kolom yang sama pada matriks B.
Langkah dan rumus pada metode Eliminasi Gauss dan LU Decomposition berlaku sama untuk kasus ini. Hanya saja, di sini matriks X dan B terdiri dari beberapa kolom, bukan hanya satu.
Contoh dua sistem persamaan linear yang memiliki nilai A sama tapi B berbeda.
a11 a21 a 31 ⋮ a n1
a12 a22 a32 ⋮ an2
a13 ⋯ a1n x11 b11 a23 ⋯ a2n x21 b21 a33 ⋯ a3n x31 = b31 ⋮ ⋱ ⋮ ⋮ ⋮ an3 ⋯ ann xn1 bn1
a11 a21 a 31 ⋮ a n1
a12 a22 a32 ⋮ an2
a11 a21 a 31 ⋮ a n1
a13 ⋯ a1n x11 a23 ⋯ a2n x21 a33 ⋯ a3n x31 ⋮ ⋱ ⋮ ⋮ an3 ⋯ ann xn1
a12 a22 a32 ⋮ an2
a13 ⋯ a1n x12 b12 a23 ⋯ a2n x22 b22 a33 ⋯ a3n x32 = b32 ⋮ ⋱ ⋮ ⋮ ⋮ an3 ⋯ ann xn2 bn2
x12 b11 b12 x22 b21 b22 x32 = b31 b32 ⋮ ⋮ ⋮ xn2 bn1 bn2
Metode Eliminasi Gauss: •
rumus triangulasi:
aij(0) = aij , bir(0) = bir
aij(k) = aij(k-1) − bir(k) •
(k -1) ik (k -1) kk
a a
(i, j = 1, ..., n; r = 1, ..., m)
akj(k-1) (k = 1, ..., n − 1;i = k + 1, ..., n;
(k -1) a = bir(k −1) − ik(k-1) bkr(k −1) akk
aij(m) , bir(m) ≡ aij , bir pada langkah ke m
j = k, ..., n; r = 1, ..., m)
rumus substitusi mundur:
bnr(n-1) xnr = (n-1) ann (n- j-1) n- j,r
b xn − j,r =
(r = 1, ..., m) n
∑a
−
k =n - j+1 (n- j-1) n - j,n - j
a
(n- j-1) n- j,k kr
x
(j = 1, ..., n − 1; r = 1, ..., m)
Metode LU Decomposition: •
rumus substitusi maju untuk menghitung y (kini Y matriks n x m):
y1r =
b1r l11
(r = 1, ..., m) i−1
bir − ∑ lij yjr yir =
•
j=1
(i = 2, ..., n; r = 1, ..., m)
lii
rumus substitusi mundur untuk menghitung x:
xnr = ynr
(r = 1, ..., m) n
xn-i,r = yn −i,r −
∑u
n −i, j
j=n −i+1
xjr (i = 1, ..., n − 1;r = 1, ..., m)
Perhatikan metode LU Decomposition, anggap matriks L dan U telah diperoleh. Jika kemudian terdapat lagi sistem persamaan linear dengan A sama dan B berbeda, maka matriks L dan U yang telah diperoleh itu bisa langsung dipakai untuk sistem persamaan yang baru tersebut. Kini perhatikan metode Eliminasi Gauss, anggap triangulasi matriks A sudah dikerjakan. Jika kemudian terdapat lagi sistem persamaan linear dengan A sama dan B berbeda, maka hasil triangulasi matriks A yang sudah diperoleh tidak dapat dipakai untuk sistem persamaan yang baru. Untuk sistem yang baru tersebut proses triangulasi matriks A harus dilakukan lagi dari awal. Hal ini disebabkan, matriks B harus berubah mengikuti proses triangulasi matriks A, sementara proses penguraian matriks A menjadi matriks L dan U tidak melibatkan matriks B.
Catatan: Dalam rumus-rumus baik pada metode Eliminasi Gauss maupun LU Decomposition terdapat pembagian oleh elemen diagonal matriks yaitu, oleh elemen diagonal matriks A pada metode Eliminasi Gauss, dan elemen diagonal matriks L pada metode LU Decomposition. Jika secara kebetulan elemen diagonal itu nol, maka akan timbul error. Karena itu, pada setiap langkah dalam proses triangulasi matriks A (metode Eliminasi Gauss) atau pencarian matriks L dan U (metode LU Decomposition) perlu dilakukan pemeriksaan, apakah elemen matriks A atau L yang bersangkutan sama dengan nol. Jika bernilai nol, maka baris berisi elemen diagonal nol itu harus ditukar dengan salah satu baris setelahnya, sehingga elemen diagonal menjadi bukan nol. Perubahan baris pada matriks A (metode Eliminasi Gauss) harus disertai perubahan baris yang sama pada matriks B. Perubahan baris pada matriks L (metode LU Decomposition) harus disertai perubahan baris yang sama pada matriks A dan B.
Soal:
Jawab:
1 3 x1 2 2 −4 2 3 − 2 x2 2 −1 = 3 −4 2 1 2 x3 1 − 3 −1 5 x4 2
baris 2 ditukar dengan baris 3
1 3 x1 2 2 − 4 0 3.5 − 0.5 x2 3 0 = 0 −1 2 − 0.5 − 2.5 x3 0 − 1 − 1 .5 x 1 3 . 5 4
1 3 x1 2 2 − 4 2 − 0.5 − 2.5 x2 − 1 0 = 0 0 3.5 − 0.5 x3 3 0 0 0 2 x4 2
x4 = 1 x3 =
3 + 0.5x4 =1 3.5
1 3 x1 2 2 − 4 2 − 0.5 − 2.5 x2 − 1 0 = 0 3 0 3.5 − 0.5 x3 0 − 1 − 1 .5 x 1 3 . 5 4
1 3 x1 2 2 − 4 2 − 0.5 − 2.5 x2 − 1 0 = 0 0 3.5 − 0.5 x3 3 0 0 − 1.75 2.25 x4 0.5
− 1 + 0.5x3 + 2.5x4 =1 2 2 + 4x2 − x3 − 3x4 x1 = =1 2
x2 =
1 3 2 2 −4 2 3 − 2 2 −1 B= A= 2 3 −4 1 2 2 1 − 3 −1 5 1 3 2 −4 1 2 3 −4 A= −1 2 3 − 2 1 − 3 −1 5 2 2 B= 2 2
2 0 0 0 − 1 l22 0 0 L= 3 l32 l33 0 1 l l43 l44 42
2 0 0 0 3 2 0 0 L= − 1 0 l33 0 1 −1 l l44 43
0.5 1.5 1 −2 1 − 0.25 − 1.25 0 U= 0 0 1 u34 0 0 0 1
0 2 0 ¨ 2 0 3 2 s i r 3 L= ba ris − 1 0 3.5 ba 1 − 1 − 1.75
0 0 0 2
1 − 2 0.5 1.5 1 u23 u24 0 U= 0 0 1 u34 0 0 0 1
2 0 0 0 −1 0 0 0 L= 3 2 l33 0 1 −1 l l44 43 0 0 2 0 0 0 3 2 L= − 1 0 3.5 0 1 − 1 − 1.75 l 44
0.5 1.5 1 −2 1 − 0.25 − 1.25 0 U= − 1/7 0 0 1 0 0 0 1