Friday, November 30, 2012

Dekomposisi LU

Dekomposisi matriks LU merupakan salah satu metode numerik untuk menyelesaikan persamaan matriks.
Apabila secara analitik, mungkin akan sangat mudah menyelesaikan persamaan matriks seperti ini AX=B, dimana kita hanya mengetahui nilai matriks A dan matriks B saja, sementara kita tidak tahu nilai dari matriks X. Secara analitik kita dapat tuliskan bahwa matriks X merupakan perkalian dari inverse matriks A dengan matriks B, atau dapat ditulis X=A-1B.

Namun bagaimana jika matriks A merupakan matriks dengan dimensi 100×100 atau 1000×1000, walaupun dikasih uang satu juta saya juga ga bakalan mau ngerjain hal ‘sia-sia’ seperti itu secara analitik. Tetapi dengan metode numerik dan tentu saja dengan bantuan kemampuan programming hal seperti itu akan lebih mudah dikerjakan.

Pertanyaannya, apa sih kegunaan dekomposisi matriks di dunia real? Saya akan menjawab metode ini dapat digunakan untuk melakukan interpolasi polinomial secara numerik tentunya atau dalam bidang yang sedang saya geluti, metode ini dapat membantu saja menyelesaikan persamaan Difusi Netron.

Pada metode LU Decomposition, matriks A ditulis ulang sebagai perkalian matriks L dan U (matriks A diurai menjadi matriks L dan U). Matriks L dan U merupakan matriks segitiga. Matriks B tidak berubah, karena matriks A tidak berubah, melainkan hanya ditulis ulang.


Langkah:
1. Cari matriks L dan U sehingga A = LU. Matriks B tetap.

2. Definisikan sebuah matriks kolom baru, misalnya Y, yaitu Y = UX, sehingga LY = B. Lalu hitung y dengan substitusi maju (mulai dari Y1 sampai Yn ).

3. Hitung x dengan substitusi mundur (mulai dari X1 sampai Xn).
Hmm… pasti masih ga kebayang kan ya?? :bingung
Oke ini contoh sederhananya menggunakan matriks A dengan dimensi 4×4.
 Pada dekomposisi matriks LU , A = LU sehingga didapatkan persamaan


Dari perkalian matriks maka didapatkan
a11 = u11
a12 = u12
a13 = u13
a14 = u14
a21 = l21u11
a22 = l21u12 + u22
a23 = l21u13 + u23
a24 = l21u14 + u24
a31 = l31u11
a32 = l31u12 + l32u22
a33 = l31u13 + l32u23 + u33
a34 = l31u14 + l32u24 + u34
a41 = l41u11
a42 = l41u12 + l42u22
a43 = l41u13 + l42u23 + l43u33
a44 = l41u14 + l42u24 + l43u23 + u44

Sehingga dapat didefinisikan
u1j = a1j (j= 1, … ,n)
dengan (i = 2, …, n) 
dengan (i =2, … ,n; j=i, …, n), kemudian

dengan (i=3, …, n; j=2, …, i-1)
 LY=B, dalam bentuk matriks dapat ditulis


Sehingga dapat didefinisikan
y1 = b1
dengan (i =2, …, n) dan
UX=Y, dalam bentuk matriks dapat dituliskan


sehingga dapat didefiniskan
x = yn
dengan (i =1, … , n-1)
Nah sekarang matriks X sudah kita dapatkan…

Metode Secant part 2

Pada Metode Newton-Raphson memerlukan syarat wajib yaitu fungsi f(x) harus memiliki turunan f’(x). Sehingga syarat wajib ini dianggap sulit karena tidak semua fungsi bisa dengan mudah mencari turunannya. Oleh karena itu muncul ide dari yaitu mencari persamaan yang ekivalen dengan rumus turunan fungsi. Ide ini lebih dikenal dengan nama Metode Secant. Ide dari metode ini yaitu menggunakan gradien garis yang melalui titik (x0, f(x0)) dan (x1, f(x1)). Perhatikan gambar dibawah ini.

Photobucket
Persamaan garis l adalah
\frac{x-x_1}{x_0-x_1} = \frac{y-f(x_1)}{f(x_0)-f(x_1)}

Karena x = x2 maka y = 0, sehingga diperoleh
\frac{x_2-x_1}{x_0-x_1} = \frac{0-f(x_1)}{f(x_0)-f(x_1)}
x2 – x1 = -\frac{f(x_1)[x_0-x_1]}{f(x_0)-f(x_1)}
x2 = x1\frac{f(x_1)[x_0-x_1]}{f(x_0)-f(x_1)}
= x1\frac{f(x_1)[x_1-x_0]}{f(x_1)-f(x_0)}
secara umum rumus Metode Secant ini ditulis

xn+1 = xn\frac{f(x_n)[x_n-x_{n-1}]}{f(x_n)-f(x_{n-1})}

Prosedur Metode Secant :
Ambil dua titik awal, misal x0 dan x1. Ingat bahwa pengambilan titik awal tidak disyaratkan alias pengambilan secara sebarang. Setelah itu hitung x2 menggunakan rumus diatas. Kemudian pada iterasi selanjutnya ambil x1 dan x2 sebagai titik awal dan hitung x3. Kemudian ambil x2 dan x3 sebagai titik awal dan hitung x4. Begitu seterusnya sampai iterasi yang diingankan atau sampai mencapai error yang cukup kecil.

Contoh :
Tentukan salah satu akar dari 4x3 – 15x2 + 17x – 6 = 0 menggunakan Metode Secant sampai 9 iterasi.

Penyelesaian :
f(x) = 4x3 – 15x2 + 17x – 6

iterasi 1 :
ambil x0 = -1 dan x1 = 3 (ngambil titik awal ini sebarang saja, tidak ada syarat apapun)
f(-1) = 4(-1)3 – 15(-1)2 + 17(-1) – 6 = -42
f(3) = 4(3)3 – 15(3)2 + 17(3) – 6 = 18
x2 = (3) – \frac{(18)[3-(-1)]}{18-(-42)} = 1.8

iterasi 2 :
ambil x1 = 3 dan x2 = 1.8
f(1.8) = 4(1.8)3 – 15(1.8)2 + 17(1.8) – 6 = -0.672
x3 = (1.8) – \frac{(-0.672)[1.8-(3)]}{-0.672-18} = 1.84319

iterasi 3 :
ambil x2 = 1.8 dan x3 = 1.84319
f(1.84319) = 4(1.84319)3 – 15(1.84319)2 + 17(1.84319) – 6 = -0.57817
x4 = (1.84319) – \frac{(-0.57817)[1.84319-1.8]}{-0.57817-(0.672)} = 2.10932

iterasi 4 :
ambil x3 = 1.84319 dan x4 = 2.10932
f(2.10932) = 4(2.10932)3 – 15(2.10932)2 + 17(2.10932) – 6 = 0.65939
x5 = (2.10932) – \frac{(0.65939)[2.10932-1.84319]}{0.65939-(-0.57817)} = 1.96752

iterasi 5 :
ambil x4 = 2.10932 dan x5 = 1.96752
f(1.96752) = 4(1.96752)3 – 15(1.96752)2 + 17(1.96752) – 6 = -0.15303
x6 = (1.96752) – \frac{(-0.15303)[1.96752-2.10932]}{-0.15303-0.65939)} = 1.99423

iterasi 6 :
ambil x5 = 1.96752 dan x6 = 1.99423
f(1.99423) = 4(1.99423)3 – 15(1.99423)2 + 17(1.99423) – 6 = -0.02854
x7 = (1.99423) – \frac{(-0.02854)[1.99423-1.96752]}{-0.02854-(-0.15303)} = 2.00036

iterasi 7 :
ambil x6 = 1.99423 dan x7 = 2.00036
f(2.00036) = 4(2.00036)3 – 15(2.00036)2 + 17(2.00036) – 6 = 0.00178
x8 = (2.00036) – \frac{(0.00178)[2.00036-1.99423]}{0.00178-(-0.02854)} = 2.00000

iterasi 8 :
ambil x7 = 2.00036 dan x8 = 1.999996
f(1.999996) = 4(1.999996)3 – 15(1.999996)2 + 17(1.999996) – 6 = -0.0002
x9 = (1.999996) – \frac{(-0.0002)[1.999996-2.00036]}{-0.0002-0.00178} = 2.0000

iterasi 9 :
ambil x8 = 1.999996 dan x9 = 2.00000
f(2.00000) = 4(2.00000)3 – 15(2.00000)2 + 17(2.00000) – 6 = 0.00000
x10 = (2.00000) – \frac{(0.00000)[2.00000-1.999996]}{0.00000-(-0.00002)} = 0.00000

n
xn-1
xn
xn+1
f(xn-1)
f(xn)
f(xn+1)
1
2
3
4
5
6
7
8
9
-1
3
1.8
1.84319
2.10932
1.96752
1.99423
2.00036
2.00000
3
1.8
1.84319
2.10932
1.96752
1.99423
2.00036
2.00000
2.00000
1.8
1.84319
2.10932
1.96752
1.99423
2.00036
2.00000
2.00000
2.00000
-42
18
-0.672
-0.57817
0.65939
-0.15303
-0.02854
0.00178
-0.00002
18
-0.672
-0.57817
0.65939
-0.15303
-0.02854
0.00178
-0.00002
0.00000
-0.672
-0.57817
0.65939
-0.15303
-0.02854
0.00178
-0.00002
0.00000
0.00000

Jadi salah satu akar dari 4x3 – 15x2 + 17x – 6 = 0 adalah 2
 
Selanjutnya dapat di lihat webwww.iaincirebon.ac.id/tmtk

Serba-Serbi Metnum


Pengertian dan Kegunaan Metode Numerik

Beberapa definisi metode numerikdikemukakan ahli matematika, misalnya metode numerik adalah teknik dimana masalah matematika diformulasikan sedemikian rupa sehingga dapat diselesaikan oleh pengoperasian aritmetika (Chapra dan Chanale, 1991); metode numerik adalah teknik -teknik yang digunakan untuk merumuskan masalah matematika agar dapat diselesaikan han ya dengan operasi hitungan, yang terdiri dari operasi tambah, kurang, kali dan bagi (Susila, 1994 ; Ibraheem dan Hisyam, 2003). Terdapat banyak jenis metode numerik, namun pada dasarnya, masing -masing metode tersebut memiliki karakteristik umum, yaitu selalu mencakup sejumlah kalkulasi aritmetika. Jadi metode numerik adalah suatu teknik untuk memformulasikan masalah matematika sehingga dapat diselesaikan dengan operasi aritmetika yang terdiri dari operasi tambah, kurang, kali dan bagi (Rochmad, 2011).

Di samping itu menurut Rochmad (2011) ada sejumlah alasan mengapa orang menggunakan metode numerik untuk memecahkan masalah yang dihadapinya.  Beberapa alasan tersebut sebagai berikut.
  1. Metode numerik merupakan suatu teknik untuk menyelesaikan masalah matematika yang efektif dan efisien. Dengan bantuan komputer ia sanggup menangani masalah yang rumit dan melibatkan perhitungan y ang luas, misalnya untuk memecahkan masalah solusi suatu persamaan tak linear, sistem persamaan yang besar, dan permasalahan lainnya termasuk dalam teknik dan sosial.  Masalah yang sering sulit atau bahkan tidak mungkin dapat diselesaikan secara analitis dapat diselesaikan dengan metode numerik.
  2. Saat ini terdapat berbagai paket program komputer (misalnya exel, maple, matlab, atau program paket lainnya) yang tersedia dan diperdagangkan sehingga mudah didapat yang dalam pengoperasiannya mencakup metode numerik. Dengan demikian, pemecah masalah tinggal menyesuaikan dengan karakteristik program paket tersebut dengan algortima yang digunakan dalam pemecahan masalah.
  3. Apabila masalah yang dihadapi sulit diselesaikan dengan bantuan program paket komputer, maka pemecah masalah dapat menggunakan program komputer (misalnya basic, pascal, fortran, atau  program komputer lainnya). Jika pemecah masalah mahir mendesain program sendiri, maka pemecah masalah dapat lebih leluasa dalam menggunakan metode numerik untuk memecahka n masalah yang dihadapinya.
  4. Di sisi lain, metode numerik merupakan semacam sarana  yang efisien untuk mengenal karakteristik komputer dan mendesain algoritma, diagram alur dan menulis program komputer sendiri.

Thursday, November 29, 2012

Metode Secant

Pengertian Metode Secant
Metode secant merupakan perbaikan dari metode regula-falsi dan newton raphson dimana kemiringan dua titik dinyatakan sacara diskrit, dengan mengambil bentuk garis lurus yang melalui satu titik.

f’ (X) =( f (Xn) – f (Xn-1)) / (Xn – Xn-1)
Xn+1 = Xn – ( (f(Xn) (Xn – Xn-1)) / ( f(Xn) -f(Xn-1) )
Tujuan dan Fungsi
Tujuan metode secant adalah untuk menyelesaikan masalah yang terdapat pada metode Newton-Raphson yang terkadang sulit mendapatkan turunan pertama yaitu f‘ (x).
Fungsi metode secant adalah untuk menaksirkan akar dengan menggunakan diferensi daripada turunan untuk memperkirakan kemiringan/slope.
Algoritma Metode Secant
1.  Definisikan fungsi F(x)
2.  Definisikan torelansi error (e) dan iterasi maksimum (n)
3.  Masukkan dua nilai pendekatan awal yang di antaranya terdapat akar yaitu x0 dan x1,sebaiknya          gunakan metode tabel atau grafis untuk menjamin titik pendakatannya adalah titik pendekatan yang konvergensinya pada akar persamaan yang diharapkan.
4.  Hitung F(x0) dan F(x1) sebagai y0 dan y1
5.  Untuk iterasi I = 1 s/d n atau |F(xn)|
     Xn+1 = Xn – Yn (Xn – Xn-1 / Yn – Yn-1)
6.Akar persamaan adalah nilai x yang terakhir.
 
Contoh Soal
Hitung akar persamaan dari : f(x) = x3 + x2 - 3x -3
dimana  x1 = 1 dan x2 = 2 ?
Jawab :
f(1) = – 4
f(2) = 3
Iterasi I :
x3   = x2 – (f(x2) (x2 – x1) / f(x2)-f(x1))
       = 2 – (3 (2-1) / 3 – (-4))
       = 1,57142
F (1.57142) = -1.36449
Iterasi 2 :
  x4   = x3 – (f(x3)(x3-x2) / f(x3)-f(x2))
         = 1.57142 – (-1,36449) (1.57142 – 2)
                     ———————————
                     -1.36449 – 3
         = 1,70540
  F (1.70540) = -0.24774
Iterasi 3 :
x5   = x4 – (f(x4)(x4-x3) / f(x4)-f(x3))
        = 1.70540 – (-0.24774) (1.71 – 1.57)
                           ————————-
                           (-0.24774)-(-1.36449)
        = 1.73514
F (1.73514) = 0.02925
Iterasi 4 :
x6   = x5 – (f(x5)(x5-x4) / f(x5)- f(x4))
      = 1.73514 – 0.02925 (1.73514 – 1.70540)
                         ————————————
                         0.02925 – (-0.24774)
      = 1.73200
F (1.73200) = -0.00051
Iterasi 5 :
x7  = x6 – (f(x6)(x6-x5) / f(x6) – f(x5))
     = 1.73200 – (-0.00051)(1.73200 – 1.73514)
                       ————————————–
                         – 0.00051 – 0.02925
     = 1.073205
F (1.073205) = 0
  .: maka akarnya adalah 1.073205
n xn f (xn) xn – xn-1 f (xn) – f (xn-1)
1 1 -4 - -
2 2 3 1 7
3 1,57142 -1,36449 -0,42858 -4,36449
4 1,70540 -0,24774 0,13398 1,11675
5 1,73514 0,02925 0,02974 0,27699
6 1,73200 -0,00051 -0,00314 -0,02976
7 1,073205 0 - -
Iterasi dapat dihentikan pada iterasi ke-7
Karena nilai f(x7) = 0, sehingga ditemukan salah satu akarnya = 1,073205
Selanjutnya dapat dilihat di web www.iaincirebon.ac.id/tmtk

Tuesday, November 27, 2012

ELIMINASI GAUSS


1. Pengertian Eliminasi Gauss
Eliminasi Gauss adalah suatu cara mengoperasikan nilai-nilai di dalam matriks sehingga menjadi matriks yang lebih sederhana. Metode Eliminasi Gauss adalah salah satu cara yang paling awal dan banyak digunakan dalam penyelesaian sistem persamaan linier. Cara ini ditemukan oleh Carl Friedrich Gauss. Prosedur penyelesaian dari metode ini adalah dengan melakukan operasi baris sehingga matriks tersebut menjadi matriks yang Eselon-baris. Ini dapat digunakan sebagai salah satu metode penyelesaian persamaan linear dengan menggunakan matriks. Caranya dengan mengubah persamaan linear tersebut ke dalam matriks teraugmentasi dan mengoperasikannya. Setelah menjadi matriks Eselon-baris, lakukan substitusi balik untuk mendapatkan nilai dari variabel-variabel tersebut.
Secara umum, sistem persamaan linier adalah sebagai berikut:
a11x1 + a12x2 + ... + a1nxn = b1
a21x1 + a22x2 + ... + a2nxn = b2
  :       :            :               = :
an1x1 + an2x2 + ... + annxn = bn
     
    Dalam mencari solusi suatu sistem persamaan linear dengan metode eliminasi gauss,bentuk operasi matrik di atas dimanipulasi menjadi matrik augment, yaitu suatu matrik yang berukuran n x (n+1) seperti berikut ini :
  
   Selanjutnya adalah proses triangularisasi dan substitusi-mundur dalam operasi matrik terhadap sistem persamaan linear sebagai contoh yang terdiri dari empat persamaan matematika,yang sudah diubah kedalam bentuk matrik seperti dibawah ini :
  
     Lalu kita dapat membuat matrik augment sebagai berikut :
 
   Kemudian kita lakukan operasi triangularisai terhadap matrik augment, dimulai dari kolom pertama, yaitu :
     Lalu dilanjutkan ke kolom berikutnya:
 
   Sebelum dilanjutkan ke substitusi mundur, perhatikan posisi masing-masing elemen matrik augment berikut:
   
  
2. Ciri-ciri Eliminasi Gauss
      a. Jika suatu baris tidak semua nol, maka bilangan pertama yang tidak nol adalah 1 (1 utama)
      b. Baris nol terletak paling bawah 
          c. 1 utama baris berikutnya berada dikanan 1 utama baris diatasnya
      d. Dibawah 1 utama harus nol
Contoh : 
 
Berikut contoh penyelesaian persamaan linear
Diketahui persamaan linear sebagai berikut:
x + 2y + z = 6
x + 3y + 2z = 9
2x + y + 2z = 12
Tentukan nilai x, y dan z!
Jawab:
Ubah persamaan linear ke dalam bentuk matriks, operasikan matriks tersebut seperti berikut: 
                b1 x 1 untuk merubah a11 menjadi 1
                b2 – b1 untuk merubah a21 menjadi 0
                b3 – 2b1 untuk merubah a31 menjadi 0
                b3 + 3 b2 untuk merubah a32 menjadi 0
                b3 x ½ untuk merubah a33  menjadi 1 ( matriks menjadi Eselon- baris)
Sehingga didapat 3 persamaan linear baru yaitu :
        x + 2y + z = 6
                y + z = 3
                      z = 3                            kemudian lakukan substitusi balik maka didapatkan
                y + z = 3
                y + 3 = 3
                      y = 0
        x+ 2y + z = 6
         x + 0 + 3 = 6
                      x = 3
jadi, nilai x = 3 , y = 0  dan z = 3

3. Algoritma Eliminasi Gauss
Secara umum,sistem persamaan linear adalah sebagai berikut:
a11x1 + a12x2 + ... + a1nxn = b1
a21x1 + a22x2 + ... + a2nxn = b2 
:                :        :         :    =   :
an1x1 + an2x2 + ... + annxn = bn
       Algoritma dasar metode eliminasi gauss adalah sebagai berikut:
a.  Ubahlah sistem persamaan linear tersebut menjadi matrik augment, yaitu suatu matrik yang berukuran n x (n + 1). Jelas terlihat bahwa elemen-elemen yang menempati kolom terakhir matrik augment adalah nilai dari bi; yaitu ai,n+1 = bi dimana i = 1, 2, ..., n. 
b.  Periksalah elemen-elemen pivot. Apakah ada yang bernilai nol? Elemen-elemen pivot adalah elemen-elemen yang menempati diagonal suatu matrik, yaitu a11, a22,..., ann atau disingkat aii. Jika aii _= 0, bisa dilanjutkan ke langkah no.3. Namun, jika ada elemen diagonal yang bernilai nol, aii = 0, maka baris dimana elemen itu berada harus ditukar posisinya dengan baris yang ada dibawahnya, (Pi) (Pj) dimana j = i + 1, i + 2, ..., n, sampai elemen diagonal matrik menjadi tidak nol, aii  0.
c.   Proses triangularisasi. 
d.   Hitunglah nilai xn   
e.   Lakukanlah proses substitusi mundur untuk memperoleh xn-1 , xn-2 , ....,x2 , x
Demikianlah algoritma dasar metode eliminasi gauss. Selanjutnya algoritma dasar tersebut di rinci lagi sebelum dapat diterjemahkan kedalam bahasa pemrograman komputer.

DAFTAR PUSTAKA
Chapra, Steven dkk. 1996. Metode Numerik . Jakarta: Erlangga
Munir, Rinaldi. 2003. Metode Numerik. Bandung: Informatika
Salusu, A. 2008. Metode Numerik. Yogyakarta: Graha Ilmu
webwww,iaincirebon.ac.id/tmtk
dkinantips.blogspot.com 
fitthree16.blogspot.com