BAB 4 Sistem Persamaan Linear
Sistem m persamaan linear dalam n variabel LG=C adalah himpunan persamaan linear berbentuk
Dengan
koefisien
dan
disebut homogen bila semua
adalah
bilangan-bilangan
yang
diberikan.
Sistem
ini
bernilai nol. Dalam bentuk matrik, system persamaan linear
dapat ditulis sebagai AX = C dengan
Penyelesaian sistem linear adalah himpunan bilangan .x1,....,xn yang memenuhi seluruh m persamaan linear tersebut. Sistem persamaan linear yang dibahas disini adalah sistem persamaan linear yang banyak persamaan linearnya ( m ) dengan banyak variabelnya ( n ), sehingga matrik A merupakan matrik sangkar. Secara numerik, sistem persamaan linear dikatakan dapat diselesaikan bila mempunyai penyelesaian yang tunggal (pada kenyataannya ada sistem persamaan linear dengan banyak penyelesaian tak hingga). 4.1
Eliminasi Gauss Metode eliminasi Gauss didasarkan pada kenyataan bahwa operasi-operasi baris
elementer pada sistem persamaan linear akan menghasilkan sistem Baru yang setara. Operasioperasi baris elementer meliputi : 1.
Pertukaran Urutan dua bans dapat ditukar
2.
Penskalaan Perkalian sebuah basis dengan konstanta tak nol
Universitas Gadjah Mada
1
3.
Penggantian Sebuah basis dapat digantikan oleh jumlahan basis itu dengan kelipatan sebarang baris yang lainnya.
Untuk memudahkan proses eliminasi Gauss, semua koefisian sistem persamaan linear AX = C disimpan ke dalam matrik
Operasi-operasi basis elementer dikenakan pada matrik di atas sehingga diperoleh matrik segitiga atas :
Setelah diperoleh matrik ini, penyelesaian sistem persamaan linear adalah
Dengan langkah-langkah tersebut, sistem persamaan linear dapat diselesaikan. Namun diperlukan langkah lain yang disebut penumpuan (pivoting). Langkah ini berupa penukaran basis. Penumpuan bertujuan: I.
Mengatasi terjadinya koefisien
II.
Memperkecil error.
= 0 pada langkah ke k
Kriteria penukaran basis pada langkah ke k : "memilih salah satu basis di bawah baris ke k yang harga mutlak koefisien kolom ke knya terbesar"
Universitas Gadjah Mada
2
Algoritma eliminasi Gauss {Membentuk matrik segitiga atas.} Untuk k=1 sampai n-1 lakukan r=k {pilih baris dengan elemen terbesar pada kolom tersebut) untuk i = k+1 sampai n, lakukan jika | jika
|
|
| maka r = i
= 0, berarti matrik singular. Hentikan komputasi.
{jika terpiiih bukan baris ke k, lakukan penukaran baris) jika r k maka lakukan untuk j = k sampai dengan n+1 s= = =s {elemen kolom ke k pada baris ke k+1 sampai n dibuat nol) untuk i = k+1 sampai dengan n, lakukan p=
/
untuk j = k+1 sampai dengan n+1, lakukan
Jika
adalah nol, diperoleh matrik singular, hentikan komputasi. A
{Mendapatkan penyelesaian, Iangkah substitusi mundur) xn = Untuk k = n-1 sampai dengan 1, lakukan jumlah = 0 untuk j= k+1 sampai dengan n, lakukan jumlah = jumlah xk=(
* xj
- jumlah)
Universitas Gadjah Mada
3
4.2
Pembalikan Matriks Pada metode ini dibuat matrik [A,I] sebagai berikut :
operasi-operasi baris elementer diterapkan pada matrik koefisien sehingga diperoleh matrik [I,A-1]
Selanjutnya penyelesaian AX = C diperoleh dari X = A-1C Algoritma pembalikan matriks dapat dibuat dengan mengacu pada Algoritma Eliminasi Gauss ditambah dengan sedikit modifikasi. 4.3
Faktorisasi LU Suatu matrik tak singular A dapat difaktorisasi menjadi matrik L dan U yang mempunyai
sifat LU = A dengan
Silanjutnya sistem persamaan linear dapat dinyatakan AX
= C
LUX = C tersebut sama dengan penyelesaian dua sistem LG
= C
UX
= G
dengan demikian bila telah dilakukan faktorisasi, penyelesaian dapat dilakukan dengan langkah substitusi maju (menyelesaikan LG = C) dan substitusi mundur (menyelesaikan UX = G ). Universitas Gadjah Mada
4
sebagai ilustrasi faktorisasi LU, perhatikan A
= LU
dengan langkah substitusi maju, dapat diketahui nilai
selanjutnya
dan seterusnya sampai dengan
Sebagai contoh, selesaikan sistem persamaan linear berikut dengan faktorisasi LU
Sistem persamaan linear tersebut mempunyai matrik koefisien :
Universitas Gadjah Mada
5
langkah faktorisasi LU :
Dari kesamaan matrik tersebut diperoleh faktarisasi LU :
Penyelesaian dengan cara ini terdiri dari dua langkah, yakni : a)
Langkah maju (menyelesaikan LG = C )
b)
Langkah mundur (menyelesaikan UX = G )
langkah maiu, menyelesaikan sistem persamaan :
Diperoleh :
Langkah mundur, menyelesaikan sistem persamaan :
Diperoleh :
Universitas Gadjah Mada
6
Metode Iterasi Pada metode ini„ terhadap sistem persamaan linear
dibuat
Selanjutnya diambil sebarang nilai tebakan awal untuk x1, ..., xn. Nilai tersebut dimasukkan kedalam rumus di atas untuk mendapatkan nilai x1, ..., xn yang baru. Pada metode iterasi ini terdapat dua varian, 1.
Metode iterasi Jacobi (penggantian simultan) Setiap tebakan, secara keseluruhan digunakan untuk menebak x1, ..., xn yang baru.
2.
Metode iterasi Gauss-seidel (penggantian berkesinambungan) Tebakan awal hanya digunakan untuk mendapatkan x1 yang baru. Nilai ini langsung digunakan untuk menebak x2 , dan seterusnya.
Umpan balik (i)
Sebutkan langkah-langkah operasi baris elementer.
(ii) Lakukan faktorisasi LU pada matrik berikut ini
Universitas Gadjah Mada
7
