SISTEM PERSAMAAN LINEAR (BAGIAN III)

Referensi:
- Steven C. Chapra, 1988, Raymond P. Canale, Numerical Methods for Engineers , McGraw-Hill.
- Amrinsyah N & Hasaballah Z, 2001, Metode Numerik dalam Ilmu Rekayasa Sipil, Penerbit ITB, Bandung.
- Bambang Triatmojo, 1996, Metode Numerik, Beta Offset, Yogyakarta.
- Suprajitno Munadi, 1990, Perhitungan Matriks dengan Fortran, Andi Offset, Yogyakarta.
METODE CRAMER
Definisi
Jika Ax = b adalah sistem yang terdiri dari n persamaan linear dengan n bilangan tak diketahui sehingga det (A) ? 0, maka sistem tersebut mempunyai pemecahan yang tunggal. Pemecahan ini adalah:
, , , dimana Aj adalah matriks yang didapatkan dengan menggantikan elemen-elemen dari kolom ke-j dari A dengan elemen-elemen dari vektor b, yaitu

contoh: misal suatu persamaan
Maka determinannya adalah

Untuk mencari X dibuat bentuk determinan dengan sisi kiri dan sisi kanan persamaan di tambah kolom yang berisi selain kolom yang mengandung unsur X, sehingga menjadi :

maka:
sehingga
Untuk mencari unsur yang lain (Y dan Z), maka:

ALGORITMA
1. Algoritma penyelesaian persamaan linear simultan dengan aturan Cramer:
2. Masukkan nilai matriks [A] dan {b}.
3. Hitung determinan matriks [A].
4. Untuk i = 1 sampai n (jumlah persamaan) lakukan perhitungan sebagai berikut Bentuk matriks [Aj], yaitu matriks [A] yang kolom ke-i, gantikan dengan matriks {b}.
5. Hitung determinan matriks [Aj].
6. Hitung Xi = |Aj| / |A|
METODE ITERASI
ITERASI JACOBI
Iterasi Jacobi menggunakan rumusan rekursif untuk menghitung nilai pendekatan solusi persamaan. Proses iterasi dilakukan sampai dicapai suatu nilai yang konvergen dengan toleransi yang diberikan. Contoh:
a11X1+a12X2+a13X3=b1
a21X1+a22X2+a23X3=b1
a31X1+a32X2+a33X3=b1
Persamaan ini dapat dinyatakan dalam bentuk berikut:



dengan syarat a11, a22, a33 tidak sama dengan nol, apabila ditetapkan nilai awal x1, x2, x3 sebagai maka untuk mendapatkan pendekatan pertama dilakukan proses
Pendekatan kedua dengan nilai , mendapatkan koreksi perhitungan dari iterasi

Untuk iterasi ke-I, perhitungan secara umum dinyatakan sebagai

Penetapan nilai variabel menurut proses ini disebut Iterasi Jacobi. Dengan nilai awal sembarang , ada kemungkinan konvergensi tercapai secara lambat, sehingga perlu ditetapkan syarat terjadinya konvergensi dalam perhitungan iterasi, yaitu :maksimum

Algoritma penyelesaian persamaan simultan dengan iterasi Jacobi:
1. Masukkan nilai matriks [A] dan (b) yang membentuk persamaan simultan linear, serta toleransi perhitungan.
2. Inisialisasi nilai x(0).
3. Hitung harga x(1) dengan rumusan iterasi Jacobi.
4. Periksa basil perhitungan; jika telah memenuhi toleransi yang diberikan cetak, nilai x(1) sebagai hasil akhir perhitungan dan hentikan program. Jika tidak, lanjutkan ke langkah berikutnya.
5. Gantikan nilai x(0) dengan x(1), dan ulangi langkah (3).
Contoh.
Selesaikan sistem persamaan berikut dengan metode iterasi Jacobi.
3x+ y- z =5
4x+7y-3z=20
2x-2y+5z=10
Sistem persamaan dapat ditulis dalam bentuk:
, ,
Langkah 1. dimasukkan nilai x=0, y=0, z=0,
Maka: X(1)=(5-0+0)/3=1.66667, Y(1)=(20-0+0)/7=2.857714, Z(1)=(10-0+0)/5=2

Langkah 2. dimasukkan nilai x=1.66667, y= 2.857714, z= 2,
Maka:
X(2)=(5-2.857714+2)/3=1.38095,
Y(2)=(20-+3x2)/7=2.76190,
Z(2)=(10-2x1.66667+2x2.857714)/5=2.47619,
Dalam bentuk tabel.

Iterasi X Y Z X' Y' Z' Pros(x) Pros(y) Pros(z)
1 0.000000 0.000000 0.000000 1.666667 2.857143 2.000000
2 1.666667 2.857143 2.000000 1.380952 2.761905 2.476190 20.69% 3.45% 19.23%
3 1.380952 2.761905 2.476190 1.571429 3.129252 2.552381 12.12% 11.74% 2.99%
4 1.571429 3.129252 2.552381 1.474376 3.053061 2.623129 6.58% 2.50% 2.70%
5 1.474376 3.053061 2.623129 1.523356 3.138840 2.631474 3.22% 2.73% 0.32%
6 1.523356 3.138840 2.631474 1.497545 3.114428 2.646194 1.72% 0.78% 0.56%
7 1.497545 3.114428 2.646194 1.510588 3.135486 2.646753 0.86% 0.67% 0.02%
8 1.510588 3.135486 2.646753 1.503756 3.128272 2.649959 0.45% 0.23% 0.12%
9 1.503756 3.128272 2.649959 1.507229 3.133551 2.649807 0.23% 0.17% 0.01%
10 1.507229 3.133551 2.649807 1.505419 3.131501 2.650529 0.12% 0.07% 0.03%
Maka X= 1.505419, Y= 3.131501, Z= 2.650529
ITERASI GAUSS-SEIDEL
Iterasi Gauss-Seidel sebagai cara penyelesaian persamaan linear simultan tidak jauh berbeda dengan iterasi Jacobi. Pada iterasi Gauss-Seidel, nilai hasil perhitungan pada baris awal langsung digunakan untuk perhitungan nilai selanjutnya di dalam iterasi. Dengan metode ini konvergensi akan tercapai lebih cepat. Bentuk iteratif persamaan iterasi adalah sebagai berikut:


MATRIK DEKOMPOSISI
METODE DEKOMPOSISI LU
Jika suatu matrik [A] bukan singular (determinan bukan nol), maka matrik tersebut dapat diuraikan menjadi: matrik triangular [L] dan [U]

Dimana [L] merupakan matrik triangular bawah, dan [U] : matrik triangular atas.
Sehingga [A]= [L]. [U]
Bila persamaan linear: [A]{x} ={b), maka mengisikan matriks [A] dengan [L] [U] menghasilkan[L][U]{x} ={b}
Beiaiti terdapat dua sistem:
[L] {z} = {b} untuk mencari {z}, dan
(U] {x} = {z} untuk memperoleh {x}.
Matriks [U] sama dengan matriks triangulasi yang diperoleh dari metode Gauss.
Algoritma proses dekomposisi LU:
a). Mendapatkan matriks [L] dan [U].
b). Menyelesaikan [L]{z) = {b}.
c). Menyelesaikan [U]{x} = {z}
Sebagai contoh, ditinjau proses dekomposisi LU untuk menyelesaikan persamaan
5X1 - 2X2 +3X3 =5
X1 +4X2 -2X3 =9
3X1 +2X2 -5X3 =8
Dalam bentuk matriks : untuk proses dekomposisi menggunakan:
Proses membentuk matrik [U] secara simultan diikuti dengan pembentukan matrik [L] pengali mik=aik/akk


menjadi

menjadi
maka dan

penyelesaian persamaan:
a) [L}.{z}={b}
menghasilkan

b) [U}.{x}={z}
menghasilkan

METODE THOMAS
Algoritma Thomas sangat cocok untuk menyelesaikan persamaan linier simultan yang dapat dibentuk menjadi matriks tridiagonal. Persamaan semacam ini banyak dijumpai dalam perhitungan numerik persamaan differensial parsiil dengan metoda beda berhingga ataupun elemen berhingga.
Algoritma proses dekomposisi Thomas:
a). Mendapatkan matriks [L] dan [U].
b). Menyelesaikan [L]{Y) = {b}.
c). Menyelesaikan [U]{x} = {z}
Misalkan persamaan matriks sebagai berikut:
[A].{X}={B}

Matriks yang paling kiri hanya mempunyai harga ditiga diagonal, sedangkan elemen-elemen di luar itu bernilai nol. Vektor kolom X(X1, X2, X3, X4) diketahui. Penyelesaian persamaan linier simultan dapat dilakukan dengan cara men-dekomposisi matriks tridiagonal A menjadi:
A = LU

Apabila kedua matriks diruas kanan persamaan dikalikan, akan didapat:



a11=L11
a12=L11xU12 a21=L21
a22= L21.U12+L22
a23= L22.U23 a32= L32
a33= L32.U23+L33
a34= L33.U34 a43= L43
a44= L44.U34+L44
atau

L11= a11
U12= a12/L11 L21=a21
L22= a22-L21.U12
U23= a23 /L22 L32=a32
L33=a33 -L32.U23
U34=a34/L33 L43=a43
L44=a44- L43.xU34
dalam bentuk umum
Lij=A11
Lij=Aji , untuk i=2,n; j=1,n-1
Lii=Aii-Lijx Uji , untuk i=2,n; j=i-1,n-1
Uij=Aij/Lii , untuk i=1, n-1; j=i+1,n
Jadi elemen-elemen dari matrik L dan U dapat dihitung dari persamaan dengan cara rekursi. Untuk menyelesaikan persamaan terlebih dahulu didefinisikan vektor kolom.
yang memenuhi persyaratan L.Y=B -->

akan didapat
L11 Y1=b1
L21 .Y1+L22.Y2=b2
L32 .Y2+L33.Y3=b3
L43 .Y3+L44.Y4=b4 atau L11 Y1=b1
atau Y2=(b2 - L21 .Y1)/ L22.
atau Y3=(b3 - L32 .Y2)/ L33.
atau Y4=(b2 - L43 .Y3)/ L44.
Dalam bentuk umum ditulis
Y1=b1/L11
Yi=(bi-Lij.Yj)/Lii untuk y i=2,n; j=i-1,n-1

Karena B=L.Y
A.X=B=L.Y
L.U.X=L.Y
U.X=Y
Artinya bilangan yang dicari X(X1, X2, X3, dan X4) dalam persamaan dengan matrik tridiagonal dapat diselesaikan secara bertahap
=


dalam bentuk umum
Xn=Yn
Xi=Yi-Uij.Xj untuk i=n-1,1; j=i+1,2
METODE CHOLESKY
Dalam ilmu rekayasa, persamaan linear simultan yang diperoleh dari rumusan matematika berdasarkan teori elastis umumnya mempunyai unsur koefisien variabel yang simetris. Persamaan linear simultan itu dapat dinyatakan sebagai


atau [A]{X}={B}
Matriks [A] disebut matriks simetri apabila di luar unsur diagonal, unsur matriks baris sama dengan unsur matriks kolom pada indeks baris dan kolom yang sama. Dengan demikiau unsur matriks simetri dirumuskan sebagai aij =aji;i? j;
i= 1,2,3,...n; J= 1,2,3,...n.
Matriks simetri dapat dinyatakan dalam produk matriks triangulasi bawah dengan matrik triangulasi atas, dengan kedua matriks satu sama lain adalah matriks transpose. Faktorisasi matrik [A]=[U]T[U]



hubungan unsur aij dan uij pada baris pertama
a11=(u11)2; a12=(u11.u12); a13=(u11.u13);;…; a1n=(u11.u1n)
nyatakan unsur u1j dalam aij.
u11= ; u12= a12 / ; u13=a13/ ;;…; u1n =a1n /
baris kedua
a22=(u12)2+=(u22)2 ; a23=(u12.u13)+(u22.u23);
nyatakan unsur u2j dalam aij.

U22= , U23= (a23-(u12.u13))/u22=
U2n= (a2n-(u12.u1n))/u22=
Baris ketiga:
a33=(u12)2+(u23)2 +(u33)2; …a3n=(u13.u1n)+(u23.u23) +(u33.u3n)
nyatakan unsur u3j dalam aij.
u33= =
u3n= dengan nilai uij didapat dari perhitungan sebelumnya
Secara umum :



uij=0 (i>j)



contoh:
Tentukan matrik
solusi