Jumat, 26 November 2010

Solusi Persamaan Linier Simultan


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