SISTEM-SISTEM PERSAMAAN

Bab 3

Solusi Sistem Persamaan Linier

dan Nilai Eigen

3.1.Pendahuluan

Bab ini membahas metode penyelesaian sistem n persamaan linier simultan dengan n nilai yang tidak diketahui x1, x2, , xn yang dinyatakan sebagai berikut:

f1 ( x1, x2, , xn) = 0

f2 ( x1, x2, , xn) = 0

f3 (x1, x2, , xn) = 0

.

.

.

fn ( x1, x2, , xn) = 0 (3-1)

Sistem persamaan linier simultan dapat dituliskan sebagai berikut:

b11 x1 + b12 x2+ + b1n xn = u1b21 x1 + b22 x2+ + b2n xn = u1

b31 x1 + b32 x2+ + b3n xn = u1

.

.

.

bn1 x1 + bn2 x2+ + bnn xn = u1 (3-2)

selanjutnya secara singkat ditulis :

Bx = u atau [B]{x} = {u}

(3-3)

B, x dan u masing-masing adalah matrik koefisien, vektor solusi dan vektor nilai yang diketahui. Berikut ini akan diberikan beberapa metode penyelesaian sistem persamaan linier simultan linier dengan operasi matrik.

3.2.Metoda Eliminasi GAUSS-JORDAN

Untuk membei gambaran tentang metode ini, berikut diberikan contoh sebuah sistem persamaan linier simultan.

2 x1 - 7 x2 + 4 x3 = 9

x1 + 9 x2 - 6 x3 = 1

-3 x1 + 8 x2 + 5 x3 = 6

(3-4)

Untuk itu matrik koefisien, vektor nilai yang diketahui serta matrik satuan ditulis bersama dengan simbol dalam bentuk sebagai berikut:

(3-5)

Langkah-langkah metode eliminasi Gauss-Jordan diberikan sebagai berikut:

( Step 1:normalisasi baris pertama dengan cara membagi elemen-elemen baris pertama dengan nilai pivot (nilai elemen diagonal) baris pertama, yaitu 2.

( Step 2: reduksi elemen baris berikutnya (baris kedua), sehingga nilai elemen baris kedua kolom pertama menjadi nol, dengan cara operasi baris, yaitu mengurangi elemen-elemen baris kedua dengan elemen-elemen baris pertama hasil step 1.

( Step 3:ulangi step 2 untuk elemen-elemen baris berikutnya (baris ketiga) dengan cara operasi baris, yaitu mengurangi elemen-elemen baris ketiga dengan 3 kali elemen-elemen baris pertama hasil step 1. Setelah step ini, maka elemen-elemen matrik menjadi berikut:

(3-6)

( Step 4:ulangi step 1 untuk baris kedua: normalisasi baris kedua dengan cara membagi elemen-elemen baris kedua dengan nilai pivot (nilai elemen diagonal) baris kedua, yaitu 25/2.

( Step 5:reduksi elemen-elemen baris pertama, sehingga nilai elemen baris pertama kolom kedua menjadi nol, dengan cara operasi baris, yaitu mengurangi elemen-elemen baris pertama dengan -7/2 kali elemen-elemen baris kedua yang baru hasil step 4.

( Step 6:ulangi step 2 untuk baris ketiga: reduksi elemen-elemen ketiga, sehingga nilai elemen baris ketiga kolom kedua menjadi nol, dengan cara operasi baris, yaitu mengurangi elemen-elemen baris ketiga dengan -5/2 kali elemen-elemen baris kedua yang baru hasil step 4. Setelah step ini, maka elemen-elemen matrik menjadi berikut:

(3-7)

( Step 7:ulangi step 1 untuk baris ketiga: normalisasi baris ketiga dengan cara membagi elemen-elemen baris ketiga dengan nilai pivot (nilai elemen diagonal) baris ketiga, yaitu 47/5.

( Step 8:ulangi step 5: reduksi elemen-elemen baris pertama, sehingga nilai elemen baris pertama kolom ketiga menjadi nol, dengan cara operasi baris, yaitu mengurangi elemen-elemen baris pertama dengan -6/25 kali elemen-elemen baris ketiga yang baru hasil step 7.

( Step 9:ulangi step 8: reduksi elemen-elemen baris kedua, sehingga nilai elemen baris kedua kolom ketiga menjadi nol, dengan cara operasi baris, yaitu mengurangi elemen-elemen baris kedua dengan -16/25 kali elemen-elemen baris ketiga yang baru hasil step 7. Setelah step ini, maka elemen-elemen matrik menjadi berikut:

(3-8)

B-1, u, x dan I masing-masing adalah matrik koefisien invers, vektor nilai yang diketahui, vektor solusi serta matrik satuan. Secara umum matrik dalam algoritma metoda eliminasi Gauss-Jordan membentuk matrik A dengan orde n x (n+m) yang terdiri dari matrik koefisien n x n ditambah dengan m kolom yang terdiri dari vektor nilai yang diketahui serta matrik satuan yang dituliskan dengan simbo berikut.

(3-9)

Misal k = 1,2, ,n adalah index atau penghitung (counter) pivot, maka algoritma metoda eliminasi Gauss-Jordan dapat dituliskan sebagai berikut:

(3-10)

Catatan :

1. Jika elemen-elemen di sebelah kiri akk sama dengan nol pada baris ke k di awal baris yang akan dinormalkan, maka tidak perlu menormalkan akj untuk j < k.

2. Untuk menghindari modifikasi elemen-elemen terlalu dini pada kolom pivot, maka index atau penghitung kolom j selalu diturunkan dari nilai (n + m) tertinggi sampai dicapai nilai kolom pivot.

3.3.Metoda Iterasi Gauss-Siedel

Persamaan (3-2) dapat dimodifikasi menjadi persamaan berikut:

x1 = (u1 b12x2 b13x3 - - b1nxn) / b11,

x2 = (u2 b21x1 b23x3 - - b2nxn) / b22,

.

.

.

xn = (un bn1x1 bn2x2 - - bn,n-1xn,n-1) / bnn (3-11)

Contoh :

4 x1 + 2 x2 + x3 = 11

- x1 + 2 x2 = 3

2 x1 + x2 + 4 x3 = 16

(3-12)

Sesuai persamaan (3-11), maka persamaan (3-12) dapat dimodifikasi menjadi sebagai berikut:

(3-13)

Untuk iterasi pertama, maka vektor solusi awal ditentukan dengan [x1, x2, x3] = [1, 1, 1]. Proses perhitungan vektor solusi pada iterasi pertama ditunjukkan sebagai berikut:

(3-14)

Jadi setelah iterasi pertama vektor solusi mempunyai nilai:

(3-15)

Selanjutnya setelah iterasi kedua dan ketiga diperoleh vektor solusi sebagai berikut:

(3-16)

(3-17)

Jadi algoritma metoda iterasi Gauss-Siedel secara simbolik dapat dituliskan sebagai berikut:

(3-18)

3.4.Metoda Dekomposisi LU

Sebuah matrik dapat didekomposisi menjadi dua matrik masing-masing matrik L dan matrik U sbb:

A = L . U

(3-19)

dimana :

L: elemen-elemen matrik pada segitiga bagian bawah (mulai dari diagonal ke bawah)

U: elemen-elemen matrik pada segitiga bagian atas (mulai dari diagonal ke atas)

Persamaan (3-19) ditulis dalam bentuk lebih rinci menjadi beikut:

= . (3-20)

Dekomposisi matrik pada persamaan (3-19) dapat dipakai untuk menyelesaikan sistem persamaan linier yang secara simbolik dinyatakan sebagai berikut:

A . x = (L . U) . x = L . (U . x) = b

(3-21)

Keunggulan metoda dekomposisi adalah penyelesaian sistem persamaan menjadi lebih mudah, karena sistem persamaan dapat dipecah (dekomposisi) menjadi 2 buah sistem persamaan yang masing-masing akan dapat disajikan dalam sepasang matrik dengan elemen-elemen yang berupa segitiga (triangular set of equations). Penyelesaian matrik dengan elemen-elemen segitiga ini menjadi lebih sederhana dengan menggunakan cara sudsitusi.

Algoritma umum metoda dekomposisi adalah sebagai berikut:

Step 1: penyelesaian vektor y sedemikian rupa sehingga memenuhi persamaan berikut:

L . y = b

(3-22)

Penyelesaian sistem persamaan ini dapat menggunakan cara substitusi ke depan (forward substitution) yang dinyatakan dengan rumus berikut:

(3-23)

Step 2: penyelesaian vektor x dalam persamaan berikut:

U . x = y

(3-24)

Penyelesaian sistem persamaan ini dapat menggunakan cara substitusi ke belakang (back substitution) yang dinyatakan dengan rumus berikut:

(3-25)

Pelaksanaan Dekomposisi Pelaksanaan dekomposisi didasarkan pada persamaan (3-20), sehingga elemen-elemen dalam matrik A mempunyai harga seperti ditunjukkan dalam rumus berikut:

(3-26)

Bentuk-bentuk penjumlahan tergantung pada hubungan antara harga i dan harga j sebagai berikut:

untuk i < j :

(3-27)untuk i = j :

(3-28)

untuk i > j :

(3-29)

Persamaan (3-27) s.d. (3-29) total berjumlah n2 persamaan untuk n2+n bilangan danyang tidak diketahui (elemen diagonal dihitung dua kali). Jumlah komponen yang tidak diketahui lebih besar dari jumlah persamaannya, sehingga untuk itu n bilangan yang tidak diketahui ditentukan secara coba-coba. Pada kenyataannya, dimungkinkan menentukan harga berikut:

untuk

(3-30)

Penyelesaian n2+n bilangan danyang tidak diketahui didasarkan pada algoritma Crout sebagai berikut:

Algoritma Crout:

Step 1: tentukan untuk (persamaan (3-30))

Step 2: untuk setiap j = 1, 2, 3, , n kerjakan 2 buah step berikut:

Step 21: untuk i = 1, 2, , j berdasar persamaan (3-27), (3-28) dan (3-30) hitung dengan rumus

berikut:

(3-31)

Jika i = 1 dalam rumus berikut ini, berarti penjumlahan menghasilkan harga sama dengan nol.

Step 22: untuk i = j + 1, j + 2, , n berdasar persamaan (3-29) hitung dengan rumus berikut

ini:

(3-32)

Metode Crout akan menghasilkan elemen-elemen matrik yang merupakan kombinasi antaradan berikut:

(3-33)

3.5.Solusi Nilai dan Vektor Eigen dengan Metode Iterasi Balik

Ekspresi S-PL simultan dengan nilai eigen diberikan sebagai berikut:

(3-34)

atau:

(3-35)

(3-36)

Misalkan vektor {y} adalah solusi S-PL berikut:

(3-37)

( mendekati nilai eigen sebenarnya yaitu (. Vektor {y} mendekati vektor eigen sebenarnya yaitu {x}. Solusi nilai dan vektor eigen iteratif: mengganti {b} dengan {y} menghasilkan {y} baru, sehingga {y} akan mendekati {x}. Pada iterasi ke i :

(3-38)

(i dan {xi} adalah perkiraan nilai dan vektor eigen pada iterasi ke i. Nilai dan vektor eigen sesungguhnya akan memenuhi persamaan (3-34). Kombinasi persamaan (3-34) dan (3-38) menghasilkan:

(3-39)

Karena {y} dalam persamaan (3-38) merupakan pendekatan dari {xi}, maka selanjutnya harga {xI+1} dinyatakan sebagai berikut:

(3-40)

Substitusi {xI+1} ke dalam persamaan (3-38) menghasilkan {yI+1}, sedangkan harga (I+1 dapat ditentukan berdasar formula berikut ini:

(3-41)

Kondisi terminasi iterasi

(3-42)

1III-8

_1010991872.unknown

_1074338663.unknown

_1074338814.unknown

_1074338900.unknown

_1074339069.unknown

_1074339071.unknown

_1074339072.unknown

_1074339070.unknown

_1074338959.unknown

_1074338980.unknown

_1074339068.unknown

_1074338954.unknown

_1074338867.unknown

_1074338883.unknown

_1074338849.unknown

_1074338763.unknown

_1074338807.unknown

_1074338811.unknown

_1074338799.unknown

_1074338673.unknown

_1074338703.unknown

_1074338668.unknown

_1010993863.unknown

_1010995069.unknown

_1074338650.unknown

_1010993911.unknown

_1010994006.unknown

_1010993669.unknown

_1010993781.unknown

_1010993649.unknown

_1010993578.unknown

_1010993599.unknown

_1010991890.unknown

_1010991160.unknown

_1010991810.unknown

_1010991848.unknown

_1010991856.unknown

_1010991846.unknown

_1010991801.unknown

_1010991805.unknown

_1010991227.unknown

_1010991110.unknown

_1010991133.unknown

_1010991158.unknown

_1010991125.unknown

_1010991022.unknown

_1010991098.unknown

_1010990951.unknown