Untuk mencari akar (solusi) persamaan linier simultan, metode numerik yang digunakan adalah :
• Eliminasi Gauss
• Eliminasi Gauss-Jourdan
• Iterasi Gauss-Seidel
n SPL dengan m persamaan dan n variabel:
a11x1 + a12x2 + … + a1nxn = b1
a21x1 + a22x2 + … + a2nxn = b2
: : :
am1x1 + am2x2 + … + amnxn = bm
atau dalam bentuk matriks: Ax = b
a11 a12 … a1n x1 b1
a21 a22 … a2n x2 b2
: : :
am1 am2 … amn xn bm
A x b
Solusi dari SPL Ax = b adalah nilai-nilai dari x1, x2, …, xn Э memenuhi persamaan ke -1 s/d ke –m
¨ Metode Eliminasi Gauss
Misalkan: A(n x n), sehingga SPL: Ax = b dengan A(n x n), x(n x 1) dan B(n x 1). Untuk menentukan solusi SPL tersebut dilakukan dalam 2 langkah utama :
Langkah 1:
Mengeliminir x1 s/d x2 atau dpl membuat Ax = b menjadi bentuk A*x = b* dengan A* adalah matriks segitiga atas
Langkah 2:
Melakukan substitusi mundur (“back substitutions”) sehingga di peroleh Xn, xn-1, xn-2,…,x2, x1
Contoh:
a11x1 + a12x2 + a13x3 = a14
a21x1 + a22x2 + a23x3 = a24
a31x1 + a32x2 + a33x3 = a34
n Eliminasi x1 pada baris ke dua dpl. Membuat koefisien x1 pada baris ke dua menjadi nol (manfaatkan operasi elementer baris/kolom)
FOR j = 1 to 4
a2j = a2j – a21/a11 x a1j
NEXT j
n Eliminir x1 pada baris ke tiga
FOR j = 1 to 4
a3j = a3j – a31/a11 x a1j
NEXT j
n Secara umum untuk mengeliminir x1:
FOR i = 2 to 3
FOR j = 1 to 4
aij = aij – ai1/a11 x a1j
NEXT j
NEXT I
n Secara umum untuk mengeliminir: xk
FOR i = k + 1, n
FOR j = k, n + 1
aij = aij – aik/akk x akj
NEXT j
NEXT i
n Setelah dieliminir x1 dan x2 maka diperoleh
a11 x1 + a12 x2 + a13 x3 = a14
a22 x2 + a23 x3 = a24
a33 x3 = a34
n Langkah utama ke dua: substitusi mundur dari persamaan ke 3 diperoleh:
x3 = a34/a33
Substitusi x3 ke persamaan ke 2, sehingga diperoleh:
x2 = (a24 – a23 x3) / a22
Substitusi x3 dan x2 ke persamaan ke 1, sehingga diperoleh: x1. Dengan demikian diperoleh x1, x2, x3 Э Ax = b
ALGORITMA ELIMINASI GAUSS
FOR i = 1 to n
FOR j = 1 to n + 1
INPUT (aij)
NEXT j
NEXT I
FOR k = 1 to n – 1
FOR i = k + 1 to n
u = aik/akk
FOR j = k to n + 1
aij = aij – u * akj
NEXT j
NEXT I
NEXT k
xn = an n+1/ann
FOR i = n – 1 DOWNTO 1
sum = 0
FOR j = i + 1 to n
sum = sum + aij * xj
NEXT j
xi = (ai n+1 – sum)/aii
NEXT i
FOR i = 1 to n
OUTPUT (xi)
NEXT i
Perhatian !
n Dalam mengeliminir xk, selalu dihitung aik/akk, selanjutnya dinyatakan dengan variabel u. Bila |akk| ® 0 maka “berbahaya” karena u bisa mengandung error yang besar
n Untuk menghindarinya, susun kembali SPL nya Э |akk| selalu yang terbesar dalam kolom ke k, akk disebut elemen PIVOT
Algoritma Pivoting
FOR k = 1 to n-1
max = abs(akk)
p = k
FOR m = k + 1 to n
IF abs(amk) > max THEN
max = abs(amk)
p = m
ENDIF
NEXT m
IF max ≤ e THEN
OUTPUT (“ILL-CONDITION”)
STOP
ENDIF
IF p ≠ k THEN
FOR i = k TO n+1
temp = akl
akl = apl
apl = temp
NEXT i
ENDIF
FOR i = k+1 TO n
u = aik/akk
FOR j = k TO n+1
aij = aij – u * akj
NEXT j
NEXT i
NEXT k
¨ Metode Eliminasi Gauss Jordan
Untuk mencari solusi SPL, dilakukan
dalam 3 langkah utama :
1. Transformasikan A dari Ax = b Э menjadi A* (segitiga atas) dari A*x = b*
2. Transformasikan A* (hasil dari langkah 1) Э menjadi A** (matriks diagonal) dari A**x = b**
3. Tentukan xi " i = 1,2, …,n berdasarkan hasil langkah 2. xi = b**i/a**i " i = 1,2,..,n
Metode ini jarang digunakan karena sangat mahal o(n3)
¨ Metode Iterasi Gauss Seidel
Bila diketahui SPL dengan n persamaan dan n variabel, sebagai berikut :
a11x1 + a12x2 + … + a1nxn = a1(n+1) .. (1)
a21x1 + a22x2 + … + a2nxn = a2(n+1) .. (2)
:
an1x1 + an2x2 + … + annxn = an(n+1) .. (n)
Maka solusinya dapat diperoleh dengan cara :
n Langkah ke-1 :
Tebak sebarang nilai awal untuk variabel x2 , x3 , ... , xn . Namakan nilai awal tersebut x20 , x30 , … , xn0 .
n Langkah ke-2 :
Substitusikan x20 , x30 , … , xn0 ke SPL (1) untuk memperoleh nilai x1 lalu namakan dengan x11 .
n Langkah ke-3 :
Substitusikan x11 , x30 , x40 , … , xn0 ke SPL (2) untuk memperoleh nilai x2 lalu namakan dengan x21 .
n Langkah ke-4 :
Substitusikan x11 , x21 , x40 , x50 , … , xn0 ke SPL (3) untuk memperoleh nilai x3 lalu namakan dengan x31 .
n Langkah ke-5 :
dan seterusnya, sampai diperoleh x11 , x21 , x31 , … , xn-11 , selanjutnya substitusika ke SPL (n) untuk memperoleh nilai xn lalu namakan dengan xn1 .
( Iterasi ke-1 selesai dengan diperolehnya nilai : x11 , x21 , x31 , … , xn-11 , xn1 . )
n Langkah ke-6 :
Ulangi langkah ke-2 s/d ke-5 (substitusikan x21 , x31 , … , xn1 ke SPL (1) untuk memperoleh nilai x1 lalu namakan dengan x12 ). Sampai nanti diperoleh nilai x12 , x22 , x32 , … , xn-12 , xn2 .
n Langkah ke-7 :
Iterasi berakhir pada iterasi ke-k, bila :
| xjk – xjk+1 | < T
dengan T nilai toleransi kesalahan yang sudah ditetapkan sebelumnya.
n Algoritma tersebut BELUM TENTU KONVERGEN !!!
n Syarat Konvergensi :
Matriks koefisiennya (A) harus bersifat DIAGONALLY DOMINANT
DAN
Contoh Soal
n Diketahui SPL sebagai berikut :
3x1 – 10x2 = 3
x1 + x2 = 2
n Carilah nilai x1 dan x2 dengan menggunakan metode iterasi Gauss-Seidel dengan Toleransinya 0,005 !
Jawab:
n Periksa tingkat konvergensinya.
Diperoleh bahwa :
|a11|=3 ; |a12|=10 ; |a21|=1 ; |a22|= 1
à 3 ³ 10
à 1 ³ 1
n Jadi SPL tersebut TIDAK DIAGONALLY DOMINANT. Sehingga tidak akan konvergen bila dipecahkan dengan metode Iterasi Gauss-Seidel.
n Untuk itu, ubah penyajian SPL nya menjadi :
x1 + x2 = 2
3x1 – 10x2 = 3
n Periksa tingkat konvergensinya.
Diperoleh bahwa :
|a11|= 1 ; |a12|= 1 ; |a21|= 3 ; |a22|= 10
à 1 ³ 1
à 10 ³ 3
n Jadi SPL hasil perubahannya bersifat DIAGONALLY DOMINANT à konvergen
n Selanjutnya jalankan algoritmanya terhadap SPL : !
x1 + x2 = 2 … (1)
3x1 – 10x2 = 3 … (2)
n Iterasi ke-1 :
1. Tebak nilai awal x20 = 0
2. Substitusikan x20 = 0 ke SPL (1) :
x1 + x2 = 2 à x1 + 0 = 2 à x1 = 2
didapat x11 = 2
3. Substitusikan x11 = 2 ke SPL (2) :
3x1 – 10x2 = 3 à 3.(2) – 10x2 = 3
à 6 – 10x2 = 3 à x2 = 0,3
didapat x21 = 0,3
n Iterasi ke-2 :
2. Substitusikan x21 = 0,3 ke SPL (1) :
x1 + x2 = 2 à x1 + 0,3 = 2 à x1 = 1,7
didapat x12 = 1,7
3. Substitusikan x12 = 1,7 ke SPL (2) :
3x1 – 10x2 = 3 à 3.(1,7) – 10x2 = 3
à 5,1 – 10x2 = 3 à x2 = 0,21
didapat x22 = 0,21
n Iterasi ke-3 :
2. Substitusikan x22 = 0,21 ke SPL (1) :
x1 + x2 = 2 à x1 + 0,21 = 2 à x1 = 1,79
didapat x13 = 1,79
3. Substitusikan x12 = 1,79 ke SPL (2) :
3x1 – 10x2 = 3 à 3.(1,79) – 10x2 = 3
à 5,37 – 10x2 = 3 à x2 = 0,237
didapat x23 = 0,237
n Iterasi ke-4, ke-5 dst
n Lanjutkan sendiri, sebagai latihan !!
n Ingat, proses iterasi akan berhenti bila kondisi
| xjk – xjk+1 | < 0,005 Terpenuhi !!
n Rangkuman Proses Iterasinya :
Iterasi ke- | x1 | x2 |
1 2 3 4 5 6 | 2,000 1,700 1,790 1,763 1,771 1,769 | 0,300 0,210 0,237 0,229 0,231 0,231 |
Algoritma IGS
INPUT A(n,n+1), e, maxit
INPUT xi (nilai awal)
k ¬ 1 ; big ¬ 1
WHILE (k ≤ maxit and big > e) DO
big ¬ 0
FOR i = 1 TO n
sum ¬ 0
FOR j = 1 TO n
IF j ≠ i THEN
sum ¬ sum + aij
NEXT j
temp ¬ (ai n+1 – sum) / aii
relerror ¬ abs((xi – temp) / temp)
IF relerror > big THEN
big ¬ relerror
xi ¬ temp
NEXT I
k ¬ k + 1
ENDWHILE
IF k > maxit THEN
OUTPUT(“TDK KONVERGEN”)
ELSE OUTPUT (“KONVERGEN”)
ENDIF
OUTPUT(xi)
Tidak ada komentar:
Posting Komentar