METODE NUMERIK ARAH KONJUGASI 14 Mei 2016 Diajukan untuk Memenuh Tugas Ujian Akhir Semester Mata kuliah Metode Numerik Dosen Pengampu Bapak Rukmono Budi Utomo,M.Sc
Nur Aliyah 1384202043
6A1 Fakultas Keguruan dan Ilmu Pendidikan Universitas Muhammadiyah Tangerang 2016
1
KATA PENGANTAR
Puji syukur kita panjatkan kehadirat Allah SWT karena atas limpahan rahmat serta petunjuk-Nya, maka pembuatan Makalah Metode Numerik tentang Arah Konjugasi ini bisa terselesaikan dengan ketentuan waktu yang diberikan. Disamping itu juga, saya selaku penulis mengucapkan terima kasih kepada Bapak Rukmono Budi Utomo,M.Sc selaku pembimbing kami serta teman-teman yang berpartisipasi dan memberikan dorongan sehingga makalah ini bisa selesai. Saya selaku penulis menyadari bahwa makalah ini masih banyak kekurangannya atau belum sesuai dengan apa yang kita inginkan bersama, namun saya sudah berusaha semaksimal mungkin agar makalah ini bisa terselaikan. Untuk itu, dengan masih banyaknya kekurangan terhadap isi makalah ini, saya dari penulis atau penyusun makalah ini sangat mengharapakan saran dan kritikan yang besifat membangun untuk penyempurnaan makalah ini agar bisa sesuai keinginan kita bersama dan dapat bermanfaat untuk kita semua serta bisa dijadikan sebagai pedoman untuk kedepannya.
Tangerang, 14 Mei 2016
Penulis
2
DAFTAR ISI Kata Pengantar ...................................................................................... 2 Daftar Isi ................................................................................................ 3 BAB I PENDAHULUAN ....................................................................... 4 1. Latar Belakang.................................................................................... 4 2. Rumusan Masalah .............................................................................. 5 3. Tujuan ................................................................................................ 5 BAB II PEMBAHASAN ........................................................................ 6 4. Pengertian Metode Arah Konjugasi ................................................... 6 5. Algoritma Arah Konjugasi ................................................................. 6 6. Contoh Soal ........................................................................................ 7 7. Menggunakan Metode Analitik .......................................................... 13 BAB III PENUTUP ............................................................................... 15 8. Kesimpulan ........................................................................................ 15 9. Saran .................................................................................................. 15 DAFTAR PUSTAKA ............................................................................. 16
3
BAB I PENDAHULUAN
1
Latar Belakang
Dalam sejarah perkembangan ilmu pengetahuan dan teknologi, matematika memegang peranan yang sangat penting untuk memecahkan berbagai permasalahan secara kuantitatif. Optimasi sebagai salah satu cabang dalam matematika sering digunakan sebagai acuan untuk menyelesaikan permasalahan-permasalahan di bidang ekonomi, teknik, dan lainnya. Dengan optimasi maka permasalahanpermasalahan yang ada dapat di prediksi dan dicari permasalahannya yang optimal. Secara umum optimasi dikategorikan menjadi 2 bagian, yaitu optimasi dengan kendala dan optimasi tanpa kendala. Optimasi dengan kendala adalah penyelesaian permasalahan untuk mendapatkan penyelesaian yang optimal dengan memperhatikan faktor-faktor pembatas yang harus dipenuhi, melalui tahapantahapan perhitungan tertentu. Sedangkan optimasi tanpa kendala adalah penyelesaian masalah tanpa adanya faktor pembatas yang mempengaruhi proses perhitungan sampai penyelesaian optimal tercapai. Penyelesaian optimal dapat diartikan sebagai penyelesaian yang minimal maupun penyelesaian yang maksimal. Pada prinsipnya mencari nilai maksimal suatu fungsi f(x) sama artinya dengan mencari nilai maksimal dari negatif fungsi f(x). Pada makalah ini akan dibahas permasalahan optimasi tanpa kendala (untuk kasus dengan kendala diubah menjadi permasalahan tanpa kendala), dan untuk kasus meminimalkan serta fungsinya merupakan fungsi konveks. Dalam meminimalkan fungsi nonlinier multivariable f(x) tanpa kendala yaitu dengan mencari vektor x = (x1 , x2 , ..., xn ) sehingga fungsi f(x) minimal. Apabila penyelesaiannya dapat di usahakan secara analitik tentu akan mempermudah memperoleh penyelesaiannya yang optimal, karena penyelesaian eksaknya didapatkan. Tetapi untuk berbagai persoalan hal ini tidak selalu mudah dilakukan sehingga perlu diupayakan penyelesaian secara numerik yang mendekati penyelesaian eksak. Ada beberapa pendekatan secara numerik untuk mencari nilai minimum suatu fungsi nonlinier multivariable f(x). Pada makalah ini akan dibahas pendekatan secara numerik menggunakan metode arah konjugasi. Metode arah konjugasi merupakan metode untuk meminimumkan atau memaksimumkan suatu fungsi . Untuk mendapatkan kekonvergenan yang lebih cepat, maka selain menggunakan arah penurunan tercuram juga menggunakan arah yang saling konjugat. Metode arah konjugasi menggunakan arah pencarian yang saling ortogonal serta selalu diperbaharui pada setiap langkah iterasi, sehingga pada setiap iterasi akan bergerak maju menuju penyelesaian yang optimal. 4
Sebagian besar pembahasan melibatkan operasi vektor dalam bentuk matriks sehingga diasumsikan operasi matriks yang meliputi jumlah dua matriks, hasil kali matriks dengan suatu skalar dan perkalian dua matriks terdefinisi.
2
Rumusan Masalah • Apa yang dimaksud dengan metode numerik arah konjugasi ? • Bagaimana algoritma dalam arah konjugasi ? • Bagaimana cara menyelesaikan persoalan numerik dengan menggunakan arah konjugasi ? • Bagaimana cara menyelesaikan persoalan numerik dengan analitik dalam menggunakan arah konjugasi ?
3
Tujuan • Untuk menambah pengetahuan mengenai berbagai metode yang dapat digunakan dalam persoalan numerik • Dapat melatih mahasiswa dalam menganalisis permasalahan-permasalahan numerik • Untuk menyelesaikan tugas pengganti UAS pada mata kuliah metode numerik
5
BAB I PEMBAHASAN
4
Pengertian Metode Arah Konjugasi
Metode Numerik Arah Konjugasi Merupakan salah satu metode numerik yang digunakan untuk menyelesaikan masalah optimisasi. Dan langkah-langkah dalam menyelesaikan masalah optmisasi tersebut berbeda dengan metode numerik lainnya, yaitu Diberikan Z=F (x1 ,x2 ),kemudian menentukan nilai X = (x1 ,x2 )∈R2 yang meminimalkan atau memaksimalkan Z=F {X} atau Z=F (x1 ,x2 ) Kemudian Metode Arah Konjugasi lebih baik dari pada metode Steepest Descent, tetapi tidak juga dengan metode Newton. Seperti yang dilihat dari metode Steepest Descent dan metode Newton, faktor penting dalam efisiensi suatu metode pencarian berulang adalah arah pencarian pada setiap iterasi.Untuk fungsi kuadrat n variabel f (x) =
1 T x Qx − xT b, x ∈ Rn , Q = QT > 0, 2
Arah pencarian terbaik disebut dengan arah Q-Konjugat. Pada dasarnya dua arah d(1) dan d(2) di Rn dikatakan Q- Konjugat jika d(1)T Qd(2) =0 Metode arah konjugasi dapat dilihat sebagai penengah antara metode Steepest Descent dan metode Newton. Metode Arah konjugasi memiliki sifat sebagai berikut. • Memecahkan persamaan kuadrat dari n variabel dalam n langkah • Dalam algoritma arah konjugasi, memerlukan matriks Hessian • Tidak ada matriks invers dan tidak ada penyimpanan n x n matriks diperlukan
5
Algoritma Arah konjugasi • Diberikan fungsi Z=F (x1 ,x2 ), kemudianakan ditentukan nilai X = (x1 ,x2 ) yang akan meminimalkan atau memaksimumkan nilai Z=F (x1 ,x2 ) • Kemudian ambil Sembarang titik awal X 1 = (x1 ,x2 )∈R2 • Kemudaian Bentuk Matriks Hessian yakni " ∂z ∂z H=
∂x21 ∂z ∂x2 ∂x1
6
∂x1 ∂x2 ∂z ∂x22
#
dengan ∂2f ∂2f ∂ ∂f = = ∂x21 ∂x1 ∂x2 ∂x1 ∂x1 ∂2f ∂ ∂f = ∂x1 ∂x2 ∂x1 ∂x2 ∂2f ∂ ∂f = ∂x2 ∂x1 ∂x2 ∂x1 • Kemudian tetapkan arah pencarian 1 a d1 = , d2 = 0 b • kemudian dengan d2 =d1 T Hd2 dan d2 =0 lalu lakukan untuk dk T −1 Hdk atau dk+1 =dk T Hdk+1 Dengan dk T = Transpos dk Contoh :
dk =
a1 a2 .. .
h T ; dk = a1
.. . an
a2
i
an • kemudian tentukan λk = min Z (X k + λk dk ) dan Xk+1 = X k + λk dk • Iterasi berhenti ketika norm
Xk − Xk−1 < ε, ε > 0 sembarang konstanta. Contoh : k( a1 , b1 ) − (a2 , b2 )k =
6
q
2
2
(a1 , a2 ) − (b1 − b2 )
Contoh Soal
Diberikan suatu fungsi f (x) = 3x1 2 +2x2 2 +4x1 x2 - 6x1 - 8x2 + 6 dengan titik awal X 1 = (1,1) dan ε = 0, 01. Dengan menggunakan metode Arah Konjugasi, tentukan pembuat minimum fungsi tersebut. Penyelesaian Iterasi 1 • Diketahui f (x) = 3x1 2 +2x2 2 +4x1 x2 - 6x1 - 8x2 + 6 • Ambil sembarang titik awal X 1 = (x1 ,x2 )∈R2 yaitu X 1 = (1,1) dengan toleransi kesalahan ε = 0, 01 7
• Kemudian dibentuk matriks Hessian " ∂z H=
∂z ∂x1 ∂x2 ∂z ∂x22
∂x21 ∂z ∂x2 ∂x1
H=
6 4
4 4
#
• Kemudian Tentukan arah pencarian pada d1 dan d2 , sebagai berikut a 1 d1 = , d2 = 0 b d2 = dT1 .H.d2 =
1
0
6
4
6
4
4
=
a b
4
a b
=0
= 6a + 4b = 0 = 6a = −4b 3a = −2b Ambil a=2 dan b=-3 dengan demikian diperoleh 2 d2 = −3 • Kemudian hitung λ1 = min Z (X 1 + λ1 d1 ) sebagai berikut: λ1 = min Z(x1 + λ1 d1 ) λ1 = min Z((1, 1) + λ1 (1, 0)) λ1 = min Z((1, 1) + (λ1 , 0) λ1 = min Z(λ1 + 1, 1)
8
Subtitusikan Z(λ1 + 1,1) pada persamaan awal, sehingga menjadi : Z(λ1 + 1, 1) = 3x21 + 2x22 + 4x1 x2 − 6x1 − 8x2 + 6 = 3(λ1 + 1)2 + 2(1)2 + 4(λ1 + 1)(1) − 6(λ1 + 1) − 8(1) + 6 = 3(λ1 2 + 2λ1 + 1) + 2 + 4(λ1 + 1) − 6λ1 − 6 − 8 + 6 = 3λ1 2 + 6λ1 + 3 + 2 + 4λ1 + 4 − 6λ1 − 6 − 8 + 6 = 3λ1 2 + 4λ1 + 1 Carilah turunan dari persamaan yang diperoleh dan samadenganka nol , agar diperoleh λ1 dz dλ1 = 6λ1 + 4 = 0 6λ1 = −4 λ1 = − 32 • Telah diperoleh λ1 = - 23 . maka akan dicari nilai X 2 X2 = X1 + λ1 d1 = ( 1, 1 ) + − 32
1 3,
1,
− 23 , 0
= ( 1, 1 ) + =
0
1
Diperoleh X2 =
1 ,1 3
Kemudian di subtitusikan, sebagai beriku :
X2 − X1 = 1 , 1 − (1, 1) 3 = = = =
q q q 2 3
1 3
−1
− 23
2
2
+ (1 − 1)
+ 02
4 9
= 0, 67
9
2
Iterasi Dilanjutkan karena 0, 67 > ε ⇒ 0, 67 > 0, 01 Iterasi 2 Diketahui :
X2 =
1 ,1 3
• Kemudian hitung λ2 = min Z (X 2 + λ2 d2 ) sebagai berikut: λ2 = min Z(X2 + λ2 d2 ) λ2 = min Z((1/3, 1) + λ2 (2, −3)) λ2 = min Z((1/3, 1) + (2λ2 , −3λ2 ) λ2 = min Z(2λ2 + 1/3, 1 − 3λ2 ) Subtitusikan Z(2λ2 +1/3,1−3λ2 ) pada persamaan awal, sehingga menjadi: Z = 2λ2 + 1/3, 1 − 3λ2 = 3x1 2 + 2x2 2 + 4x1 x2 − 6x1 − 8x2 + 6 = 3(2λ2 + 1/3)2 + 2(1 − 3λ2 )2 + 4(2λ2 + 1/3)(1 − 3λ2 ) − 6(2λ2 + 1/3) − 8(1 − 3λ2 ) + 6 = 3(4λ2 2 + 4/3λ2 + 1/9) + 2(1 − 6λ2 + 9λ2 2 ) + 4(2λ2 − 6λ2 2 + 1/3 − λ2 ) − 6(2λ2 + 1/3) −8(1 − 3λ2 ) + 6 = (12λ2 2 + 4λ2 + 1/3) + (2 − 12λ2 + 18λ2 2 ) + (8λ2 − 24λ2 2 + 4/3 − 4λ2 ) − (12λ2 + 2) −(8 − 24λ2 ) + 6 = 12λ2 2 + 4λ2 + 1/3 + 2 − 12λ2 + 18λ2 2 + 8λ2 − 24λ2 2 + 4/3 − 4λ2 − 12λ2 − 2 − 8 + 24λ2 + 6 = 6λ2 2 + 8λ2 − 1/3 Carilah turunan dari persamaan yang diperoleh dan samadengankan nol, agar diperoleh nilai λ2 dz dλ2
= 12λ2 + 8 = 0
12λ2 = −8 λ2 = −2/3
10
• Telah diperoleh λ2 = - 32 . maka akan dicari nilai X 3 X3 = X2 + λ2 d2 =
1 3, 1
+ − 32 (2, −3)
=
1 3, 1
+ − 34 , 2
= ( −1, 3) Diperoleh X3 = (−1, 3) Kemudian Di subtitusikan, sebagai berikut :
X2 − X1 = (−1, 3) − = = = =
q q
−1 − − 43
2
1 2 3
+ (3 − 1)
1 3, 1
2
+ 22
q
16 9
+4
q
52 9
= 2, 4
Iterasi Dilanjutkan karena 2, 4 > ε ⇒ 2, 4 > 0, 01
Iterasi 3 Diketahui : X3 = (−1, 3) • Kemudian hitung λ3 = min Z (X 3 + λ3 d3 ) sebagai berikut: λ3 = min Z(X3 + λ3 d3 ) λ3 = min Z((−1, 3) + λ3 (1, 0)) λ3 = min Z((−1, 3) + (λ3 , 0) λ3 = min Z(λ3 − 1, 3) 11
Subtitusikan Z(λ3−1 , 3) pada persamaan awal, sehingga menjadi: Z λ3−1 , 3 = 3x1 2 + 2x2 2 + 4x1 x2 − 6x1 − 8x2 + 6 = 3(λ3−1 )2 + 2(3)2 + 4(λ3−1 )(3) − 6(λ3−1 ) − 8(3) + 6 = 3(λ3 2 − 2λ3 + 1) + 18 + 4(3λ3 − 3) − (6λ3 − 6) − 24 + 6 = 3λ3 2 − 6λ3 + 3 + 18 + 12λ3 − 12 − 6λ3 + 6 − 24 + 6 = 3λ3 2 − 3 Carilah turunan dari persamaan yang diperoleh dan samadengankan nol, agar diperoleh nilai λ3 . dz dλ3 = 6λ3 = 0 λ3 = 0 • Telah diperoleh λ3 = 0. maka akan dicari nilai X 4 X4 = X3 + λ3 d3 = ((−1, 3) + 0(4, 0)) = ((−1, 3) + (0, 0)) = (−1, 3) Diperoleh X4 = (−1, 3) Kemudian di subtitusikan sehingga menjadi
X4 − X3 = k(−1, 3) − (−1, 3)k = = =
q √ √
2
(−1 + 1) + (3 − 3)
2
02 + 02 0
=0 Terlihat bahwa 0 < ε ⇒ 0 < 0, 01. Sehingga iterasi berhenti.
12
7
Menggunakan Metode Analitik • Dengan konsep Arah Konjugasi yang telah dijelaskan di atas, maka perhitungan dapat diselesaikan dengan Metode Analitik Diketahui suatu fungsi f (x) = 3x1 2 +2x2 2 +4x1 x2 - 6x1 - 8x2 + 6 • Carilah turunan pertama terhadap x1 ∂f dx1
= 6x1 + 4x2 − 6 = 0
→ 6x1 = 6 − 4x2 → x1 =
6−4x2 6
→ x1 = 1 − 32 x2 Sehingga ⇒
∂2f =6 dx1
• Carilah turunan pertama terhadap x2 ∂f dx2
= 4x2 + 4x1 − 8 = 0
→ 4x2 + 4 1 − 32 x2 − 8 = 0 → 4x2 − 83 x2 − 4 = 0 → 34 x2 = 4 x2 = 3 Sehingga ⇒
∂2f =4 dx2
• Kemudian kita cari x1 Karena x2 telah diketahui x2 =3, maka kita sibtitusikan terhadap 2 x1 = 1 − x2 3 sehingga x1 x1 x1 x1
= 1 − 32 x2 = 1 − 23 (3) =1−2 = −1
Dengan demikian didapat x1 =−1 dan x2 =3 13
• Kemudian Cek apakah terbukti nila x1 =−1 dan x2 =3 meminimumkan fungsi f (x) = 3x1 2 +2x2 2 +4x1 x2 - 6x1 - 8x2 + 6 atau tidak. 2 ∂2f ∂2f ∂ f ∂f ∂f dx1 × dx2 − dx1 dx2 > dx1 × dx2 = 6 × 4 − (4)2 = 24 − 16 =8 =8>0 Terlihat bahwa terbukti nila x1 =−1 dan x2 =3 meminumumkan fungsi f (x) = 3x1 2 +2x2 2 +4x1 x2 - 6x1 - 8x2 + 6
14
BAB III PENUTUP
8
Kesimpulan
Metode Numerik Arah Konjugasi Merupakan salah satu metode numerik yang digunakan untuk menyelesaikan masalah optimisasi. Dan langkah-langkah dalam menyelesaikan masalah optmisasi tersebut berbeda dengan metode numerik lainnya, yaitu Diberikan Z=F (x1 ,x2 ),kemudian menentukan nilai X = (x1 ,x2 )∈R2 yang meminimalkan atau memaksimalkan Z=F {X} atau Z=F (x1 ,x2 ) Kemudian Metode Arah Konjugasi lebih baik dari pada metode Steepest Descent, tetapi tidak juga dengan metode Newton. Seperti yang dilihat dari metode Steepest Descent dan metode Newton, faktor penting dalam efisiensi suatu metode pencarian berulang adalah arah pencarian pada setiap iterasi.Untuk fungsi kuadrat n variabel f (x) =
1 T x Qx − xT b, x ∈ Rn , Q = QT > 0, 2
Arah pencarian terbaik disebut dengan arah Q-Konjugat. Pada dasarnya dua arah d(1) dan d(2) di Rn dikatakan Q- Konjugat jika d(1)T Qd(2) =0
9
Saran
sebaiknya sebelum menyelesaikan permasalahan numerik menggunakan metode arah konjugat kita harus lebih dulu memahami metode numerik Steepest Descent karena algoritma arah konjugasi turunan dari metode Steepest Descent.
15
DAFTAR PUSTAKA
Chong, Edwin. kChong, Edwin. K.P. 2001.Chong, Edwin. K.P. 2001. An Introduction To Optimization. A Wiley Interscience Publication, John Wiley end Sons INC: Newyork
16
