ARAH KONJUGAT dibuat guna memenuhi tugas UAS Mata Kuliah Metode Numerik Dosen: Rukmono Budi Utomo M.Sc. 4 juni 2016
Dadang Supriadi 1384202098 6A2
UNIVERSITAS MUHAMMADIYAH TANGERANG FAKULTAS KEGURUAN ILMU DAN PENDIDIKAN PENDIDIKAN MATEMATIKA
1
1 pengertian Arah Konjugasi Metode numerik Arah Konjugasi merupakan salah satu metode numerik yang dapat digunakan untuk menyelesaikan masalah optimisasi, yakni menentukan nilai X = {x1 , x2 } ∈ R2 yang meminimalkan atau memaksimalkan Z = F (X). Metode Arah Konjugasi dapat digunakan untuk menyelesaikan permasalahan optimasi yang memiliki fungsi tujuan dengan banyak variabel (vektor).
2 Algoritma Metode Numerik Arah Konjugasi Berikut ini langkah-langkah Algoritma Metode Numerik Arah Konjugasi : 1. Diberikan fungsi Z = F (x1 , x2 ) dan akan ditentukan nilai X = {x1 , x2 } yang meminimumkan atau memaksimumkan nilai Z = F (x1 , x2 ) tersebut. 2. Ambil sembarang titik awal X 1 = {x1 , x2 } ∈ R2 3. Bentuk Matriks Hessian seperti berikut ini: ∂Z ∂x1 2 ∂Z ∂x2 ∂x1
H=
∂Z ∂x1 ∂x2 ∂Z ∂x2 2
!
4. Tetapkan arah pencarian "
d1 =
−1 2
#
"
, d2 =
a b
#
5. Lalu didapat nilai d2 dengan cara: d2 = d1 t Hd2 dan sama dengankan nol, sehingga diperoleh nilai dk+1 dengan cara: dk+1 = dk t Hdk+1
6. Tentukan λk = min Z X k + λk dk dan X k+1 = X k + λk dk
7. Iterasi berhenti ketika norm X k+1 − X k < ε dengan ε > 0 yang merupakan suatu konstanta positif untuk menunjukkan kesalahan yang ditoleransi
3 Contoh Penerapan Arah Konjugasi Tentukan nilai X = {x1 , x2 } yang meminimalkan Z (x1 , x2 ) = 3x1 2 +3x2 2 −6x1 −6x2 x1 dengan menggunakan metode Arah Konjugasi dengan toleransi kesalahan ε = 0, 01 • Ambil sembarang titik awal X 1 = {−1, 2} ∈ R2
2
• Dibentuk Matriks Hessian ∂Z ∂x1 2 ∂Z ∂x2 ∂x1
H=
∂Z ∂x1 ∂x2 ∂Z ∂x2 2
6 −6 −6 6
H=
!
!
• Tetapkan arah pencarian d1 dan d2 dengan "
d1 =
#
1 0
"
, d2 =
a b
#
#"
a b
d2 = d1 t Hd2 "
0 = [1 0]
6 −6 −6 6
#
0 = 6a + 6b ⇔ a = b • Ambil a=2, b=1, dengan demikian diperoleh "
d2 =
1 1
#
• Nilai λ1 dapat ditentukan sebagai berikut: λ1 = min Z(X 1 + λ1 d1 ) = Z((−1, 2) + λ1 (1, 0)) = Z (−1 + λ1 , 2) Substitusikan x1 dan x2 ke fungsi Z, lalu didapat nilai: Z (−1 + λ1 , 2) = λ1 2 − 8λ1 + 11 • Derivatifkan Z (−1 + λ1 , 2) dan sama dengankan nol, sehingga diperoleh λ1 = 4. Lalu substitusikan nilai λ1 = 4 ke: X 2 = X 1 + λ1 d1 = (3, 2)
• Karena X 2 − X 1 = 4 > 0, 01 = ε maka iterasi dilanjutkan • Dengan langkah yang
sama, diperoleh λ2 = 0 dan X 3 = (3, 2). Berdasarkan hal
tersebut X 3 − X 2 = 0 > 0, 01 = ε maka iterasi berhenti • Dengan demikian iterasi STOP. Jadi X yang meminimumkan fungsi Z dalam soal ini adalah X 3 = (0) CATATAN
Perlu diperhatikan bahwa X 3 − X 2 = 0, hal ini mengindikasikan bahwa kesalahan perhitungan numerik error ε = 0 yang menandakan bahwa solusi numeriknya juga merupakan solusi analitiknya. 3
4 Contoh Penyelesaian Dengan Analitik Tentukan nilai X = {x1 , x2 } yang meminimalkan Z (x1 , x2 ) = 3x1 2 +3x2 2 −6x1 −6x2 x1 dengan menggunakan metode Analitik dengan toleransi kesalahan ε = 0, 01 Solusi ∂Z = 6x1 − 6 − 6x2 ∂x1 ∂Z = 6x2 − 6x1 ∂x2 Karena ∂Z x1 = 0 dan juga karena Selanjutnya
∂Z x2
= 0, maka diperoleh x1 = 1 dan x2 = 1. ∂2Z =6 ∂x1 2 ∂2Z =6 ∂x2 2
2
2
2
∂ Z ∂ Z ∂ Z ∂Z 2 Karena ∂x 2 = 6 > 0 dan ∂x 2 ( ∂x 2 ) − ( ∂x ∂x ) = 0 = 0 maka terbukti bahwa titik 3,2 1 2 1 1 1 merupakan titik yang meminimumkan fungsi Z = x1 , x2 dalam soal ini.
4
Metode Stepest Descent Siti Eliyawati June 10, 2016
1 Pengertian Metode Numerik Stepest Descent merupakan salah satu metode numerik yang dapat digunakan untuk menyelesaikan masalah optimisasi,yakni menentukan nilai X = {x1, x2 } ∈ R2 yang meminimalkan atau memaksimalkan Z = F (X) • Metode untuk menyelesaikan masalah optimisasi ini juga dapat menggunakan metode aksial, Hooke and Jeeve atau Roosenberg • Tentu saja setiap metode numerik memiliki algoritma yang berbeda dengan kecepatan tingkat efektivitas pencarian O (Big Oh)yang berbeda serta tingkat kesalahan yang berbeda pula.
2 Algoritma Stepest Descent Algoritma Stepest Descent dapat dijelaskan sebagai berikut: • Diberikan fungsi Z = F (x1 , x2 )dan akan ditentukan nilai X = {x1 , x2 } yang meminimalkan atau memaksimalkan nilai Z = F (x1 , x2 ) tersebut • Tentukan sebarang titik awal X 1 = {x1 , x2 } dan konstanta ∈> 0 • Bentuk ∇Z(x1 , x2 ) =
∂Z ∂Z x1 , x2
t
dan tentukan ∇Z(X1 ) dan lakukan untuk ∇Z(Xk )
• jika norm k∇Z (xk ) kuarang dari ∈, maka iterasi stop jika tidak lanjutkan • tentukan dk = −∇Z(xk ), λk = minZ(xk + λk dk ) dan xk+1 = xk + λk dk
3 Contoh Penggunaan Stepest Descent Tentukan nilai X = {x1 , x2 } yang meminimlkan Z = (x1 , x2 ) = −12x1 −4x2 +3x1 2 +2x2 2 dengan menggunakan metode Stepest Descent Solusi Iterasi 1
1
• Berdasarkan soal diatas, dapat ditentukan ∇Z(x1 , x2 ) =
−12 + 6x1 −4 + 4x2
!
• Ambil sebarang titik awal X1 = {1, 1} ∈ R2 , berdasarkan hal demikian ∇Z(1, 1) =
!
−6 0
• karena k∇Z (1, 1)k = 6 > 0, 01 =∈, maka berdasarkan hal tersebut iterasi dilanjutkan • Selanjutnya dapat ditentukan −6 0
d1 = −∇Z(1, 1) =
!
dan λ1 = min Z(X1 + λ1 d1‘ ) = Z(1, 1) + (6λ1 , 0) = Z(1 + 6λ1 , 1) dengan Z(1 + 6λ1 , 1) = −12(1 + 6λ1 ) − 4(1) + 3(1 + 6λ1 )2 + 2(1)2 = −12 − 72λ1 − 4 + 3 + 36λ1 + 108λ1 2 + 2 = 108λ1 2 − 36λ1 − 11 • Untuk memperoleh nilai λ1 , derivatifkan Z(1 + 6λ1 , 1) dan sama dengankan nol, sehingga diperoleh Z 0 = (1 + 6λ1 ) = 216λ1 − 36 ↔ 216λ1 − 36 = 0 ↔ λ1 = 16 Iterasi II • selanjutnya X2 dapat dicari dengan X2 = X1 + λ1 d1 = (1, 1) + 16 (6.0) = (1, 1) + (1, 0) = (2, 1) dengan ∇Z(2, 1) = dan k∇Z (2, 1)k = 0 < 0, 01 =∈
2
0 0
• Berdasarkan hal tersebut karena k∇Z (2, 1)k = 0 < 0, 01 =∈, maka iterasi berhenti sehingga solusi numerik nilai {X1 , X2 } yang meminimalkan Z{X1 , X2 } dalam soal ini adalah X2 = 2, 1 catatan Perlu di ingat bahwa, karena k∇Z (2, 1)k = 0 hal ini mengindikasikan masalah kesalahan perhitungan numerik error ∈= 0 yang mengindikasikan bahwa solusi numerik juga merupakan solusi analitiknya.
3
METODE NUMERIK HOOKE AND JEEVES Disusun untuk memenuhi Tugas Ujian Akhir Semester Metodi Numerik June 8, 2016
Disusun Oleh : Febri Eka Putra S. 1384202095
FAKULTAS KEGURUAN DAN ILMU PENDIDIKAN PENDIDIKAN MATEMATIKA UNIVERSITAS MUHAMMADIYAH TANGERANG Jln. Perintis Kemerdekaan I/33 Cikokol – Kota Tangerang Tahun Ajaran 2015-2016 1
BAB I PENDAHULUAN A. Latar Belakang Metode Numerik adalah teknik untuk menyelesaikan permasalahan-permasalahan yang diformulasikan secara matematik dengan cara operasi hitung. Terdapat banyak jenis metode numerik, namun pada dasarnya masing-masing metode tersebut memiliki karakteristik umum, yaitu selalu mencangkup sejumlah kalkulasi aritmatika. Menurut Chapra dan Chanale, metode numerik adalah teknik dimana masalah matematika diformulasikan sedemikian rupa sehingga dapat diselesaikan oleh pengoprasian aritmatika. Menurut Rochmad, metode numerik adalah suatu teknik untuk memformulasikan masalah matematika sehingga dapat diselesaikan dengan operasi aritmatika yang terdiri dari operasi tambah, kurang, kali, dan bagi. Menurut Drs. Heri Sutarno, metode numerik merupakan alat untuk memecahkan masalah matematika yang sangat handal. Banyak permasalahan teknik yang mustahil dapat diselesaikan secara analitik, karena kita sering dihadapkan pada sistem-sistem persamaan yang besar, tidak linear dan cakupan yang kompleks, dapat diselesaikan dengan metode numerik. Alasan memakai Metode Numerik ini karena tidak semua permasalahan matematis atau perhitungan matematis dapat diselesaikan dengan mudah. Bahkan dalam prinsip matematik, suatu persoalan matematik yang paling pertama dilihat adalah apakah persoalan itu memiliki penyelesaian atau tidak. Jadi, jika suatu persoalan sudah sangat sulit atau tidak mungkin diselesaikan dengan metode matematis (analitik) maka kita dapat menggunkan metode numerik sebagai alternativ penyelesaian persoalan tersebut. B. Rumusan Masalah • Definisi Metode Numerik Hooke and Jeeves ? • Apa algoritma Metode Numerik Hooke and Jeeves ? • Bagaimana contoh soal dari Metode Numerik Hooke and Jeeves ?
2
C. Tujuan • Mengetahui definisi dari Metode Numerik Hooke and Jeeves • Mengetahui algoritma Metode Numerik Hooke and Jeeves • Mengetahui cara penyelesaian soal dari Metode Numerik Hooke and Jeeves
D. Manfaat Adapun tujuan dari penulisan makalah ini adalah untuk memenuhi tugas Ujian Akhir Semester dari mata kuliah Metode Numerik di Semester 6. Manfaat yang dapat di ambil adalah kita dapat menambah wawasan sebagai bekal ilmu sebagai seorang pendidik, bagi pembaca khususnya Mahasiswa/i Universitas Muhammadiyah Tangerang dan juga agar dapat sebagai referensi bacaan tentang Metode Numerik Hooke and Jeeves.
3
BAB II PEMBAHASAN Secara umum, fungsi yang akan dimaksimumkan atau diminimumkan disebut fungsi objektif. Sedangkan, harga-harga yang berpengaruh dan bisa dipilih disebut variabel. Secara analitik, nilai maksimum dan minimum dari suatu persamaan: y = f(x) dapat diperoleh harga x yang memenuhi : dy dx
= 0 atau
df dx
=0
Untuk fungsi yang sulit digunakan diturunkan atau mempunyai turunan yang sulit dicari akarnya, proses optimasi ini dapat dilakukan secara numerik.
1 Definisi Metode Numerik Hooke and Jeeves Metode Hooke and Jeeves atau sering ditulis metode Hooke and Jeeves merupakan metode lanjutan dari Metode Numerik Aksial. Metode Hooke and Jeeves digunakan untuk menemuan minimum atau maksimum dari suatu fungsi. metode ini dapat digunakan untuk menyelesaikan masalh optimisasi linear maupun non linear. Metode Numerik Hooke and Jeeves merupakan suatu metode numerik untuk mencari lokasi minimum dari fungsi Z, adalah metode pencarian langsung (direct search) yang diajukan oleh Hooke dan Jeeves. Metode ini memanfaatkan dua langkah, yaitu langkah penjelajahan untuk menentukan arah pencarian yang tepat dan langkah pola untuk mempercepat pencarian. Pencarian langsung belum tentu menemukan minimum yang merupakan global minimum. Untuk memperbesar peluang itu, digunakan kombinasi berupa pencarian langsung dan secara acak yang memanfaatkan parameter-parameter tersebut. Berbeda dengan metode numerik Aksial yang hanya digunakan untuk menyelesaikan masalah optimisasi 1 variabel. Metode Numerik Hooke and Jeeves dapat digunakan untuk menyelesaikan masalah optimisasi yang melibatkan n (misal dibatasi hanya untuk n = 2, artinya hanya untuk R2 ) variabel bebas.
2 Algoritma Metode Numerik Hooke and Jeeves 1. Diberikan fungsi f (x1 , x2 ) dan diminta untuk menentukan (x1 , x2 ) yang memaksimalkan atau meminimalkan fungsi f (x1 , x2 ). 2. Tentukan titik awal x = (x1 , x2 ) R2 yang merupakan selang sembarang. 3. Tentukan > 0 yang dimana merupakan suatu kostanta toleransi kesalahan. 4
4. Tentukan d1 = (1, 0); d2 = (0, 1) dimana d1 dan d2 merupakan arah pencarian. 5. Iterasi berhenti ketika ||(xk − xk − 1)|| < .
3 Contoh Soal Tentukan nilai x = x1 , x2 yang meminimalkan f (x1 , x2 ) = 4x21 + 3x22 − 2x1 − 2x2 dengan toleransi kesalahan = 0, 1. penyelesaian. Ambil sembarang titik x = 0, 1 d1 = (1, 0) dan d2 = (0, 1) Iterasi 1 λ1 = minf (x1 + λ1 d1 ) λ1 = minf ((0, 1) + λ1 (1, 0)) λ1 = minf ((0, 1) + λ1 , 0)) λ1 = minf (λ1 , 1) Selanjutnya, substitusikan kedalam fungsi f (x) f (λ1 , 1) = 4λ21 + 3(1)2 − 2λ1 − 2(1) f (λ1 , 1) = 4λ21 + 3 − 2λ1 − 2 Akan dicari λ1 dan disama dengankan nol f 0 (λ1 , 1) = 0 8λ1 − 2 = 0 8λ1 = 2 λ1 =
2 8
=
1 4
5
Selanjutnya, dicari nilai x2 x2 = x1 + λ1 d1 x2 = (0, 1) + 14 (1, 0) x2 = (0, 1) + ( 14 , 0) x2 = ( 41 , 1) Akan dicek d = ||x2 − x1 || d = ||( 14 , 1 − (0, 1)|| d=
p 1 ( 4 − 0)2 + (1 − 1)2
d=
p 1 2 (4) + 0
d=
q
1 16
=
1 4
= 0, 25 > 0, 1 (iterasi dilanjutkan)
Iterasi 2 λ2 = minf (x2 + λ2 d2 ) λ2 = minf (( 14 , 1) + λ2 (0, 1)) λ2 = minf (( 41 , 1) + (0, λ2 )) λ2 = minf ( 41 , 1 + λ2 ) Selanjutnya, substitusikan kedalam fungsi f (x) 1 f ( 14 , 1 + λ2 ) = 4( 16 ) + 3(1 + λ2 )2 − 2 14 − 2(1 + λ2 )
f ( 41 , 1 + λ2 ) =
1 4
+ 3(1 + 2λ2 + λ22 ) −
f ( 14 , 1 + λ2 ) =
1 4
+ 3 + 6λ2 + 3λ22 −
1 2
1 2
− 2 − 2λ2
− 2 − 2λ2
6
Akan dicari λ2 dan disama dengankan nol f 0 ( 14 , 1 + λ2 ) = 0 6λ2 + 4 = 0 6λ2 = −4 λ2 =
−4 6
=
−2 3
Selanjutnya, dicari nilai x3 x3 = x2 + λ2 d2 x3 = ( 41 , 1) +
−2 3 (0, 1)
x3 = ( 41 , 1) + (0, −2 3 ) x3 = ( 41 , 13 ) Akan dicek d = ||x3 − x2 || d = ||( 14 , 31 ) − ( 14 , 1)|| d= d= d=
p 1 ( 4 − 14 )2 + ( 13 − 1)2 q 2 0 + ( −2 3 )
q
2 3
= 0, 67 > 0, 1 (iterasi dilanjutkan)
Iterasi 3 λ3 = minf (x3 + λ3 d3 ) λ3 = minf (( 14 , 31 ) + λ3 (1, 0)) λ3 = minf (( 14 , 31 ) + (λ3 , 0)) λ3 = minf ( 41 + λ3 , 31 )
7
Selanjutnya, substitusikan kedalam fungsi f (x) f ( 14 + λ3 , 13 ) = 4( 41 + λ3 )2 + 3( 13 ) − 2( 14 + λ3 ) − 2( 23 ) 1 f 0 ( 23 + λ3 , 34 ) = 4( 16 + 12 λ3 + λ23 ) +
f 0 ( 23 + λ3 , 34 ) =
1 4
+ 2λ3 + 4λ23 +
1 3
1 3
−
− 1 2
1 2
− 2λ3 −
− 2λ3 −
Akan dicari λ3 dan disama dengankan nol f 0 ( 14 + λ3 , 13 ) = 0 8λ3 = 0 λ3 = 0 Selanjutnya, dicari nilai x4 x4 = x3 + λ3 d3 x4 = ( 41 , 13 ) + 0(1, 0) x4 = ( 41 , 13 ) + (0, 0) x4 = ( 41 , 13 ) Akan dicek d = ||x4 − x3 || d = ||( 14 , 31 ) − ( 14 , 31 )|| d= d= d=
p 1 1 2 ( 4 , 3 ) − ( 14 , 31 )2
√ √
0+0 0 = 0 < 0, 1 (iterasi dihentikan)
8
2 3
2 3
Akan dibuktikan dengan Cara Analitik ∂f ∂x1
∂f ∂x2
= 8x1 − 2 ;
= 6x2 − 2
untuk mencari titik kritis maka ∂f ∂x1
∂f ∂x1
= 0 dan
∂f ∂x2
=0
=0
8x1 − 2 = 0 8x1 = 2 x1 =
2 8
=
1 4
sedangkan ∂f ∂x2
=0
6x2 − 2 = 0 6x2 = 2 x2 =
2 6
=
1 3
Jadi, titik kritisnya adalah ( 14 , 13 ) Akan dicek ( 14 , 13 ) memninimalkan fungsi f (x) = (x1 , x2 ) ∂2f ∂x21
=8
∂2f ∂x22
=6
∂2f ∂x1 ∂x2 ∂2f ∂x21
=0 2
2
f ( ∂∂xf2 ) - ( ∂x∂1 ∂x ) = 8.6 − 0 = 48 > 0 2 2
Maka terukti bahwa titik kritis dari ( 41 , 13 ) merupakan suatu fungsi yang meminimalkan fungsi f (x).
9
BAB III PENUTUP A. Kesimpulan Dengan mempelajari metode numerik diharapkan mahasiswa mampu menangani sistem persamaan besar ketaklinieran dan geometri yang rumit yang dalam masalah rekayasa tidak mungkin dipecahkan secara analitis. Selain itu, mahasiswa diharapkan mengetahui secara singkat dan jelas teori matematika yang mendasari paket program, mampu merancang program sendiri sesuai permasalahan dihadapi pada masalah rekayasa dan dapat menangani masalah rekayasa yang tidak dapat ditangani secara analitis. Di samping itu, metode numerik cocok untuk menggambarkan ketangguhan dan keterbatasan komputer menangani error. Suatu nilai hampiran (aproksimasi) dari masalah serta menyediakan sarana memperkuat pengertian matematika mahasiswa. Karena salah satu kegunaannya adalah menyederhanakan matematika yang lebih tinggi menjadi operasi-operasi matematika yang mendasar. Pada metode numerik, kita hanya memperoleh solusi yang mendekati solusi sejati sehingga solusi numerik dinamakan juga solusi hampiran atau solusi pendekatan, namun solusi hampiran dapat dibuat seteliti yang kita inginkan. Solusi hampiran jelas tidak tepat sama dengan solusi sejati, sehingga ada selisih antara keduanya. Selisih inilah yang disebut dengan error. Semakin kecil galat yang diperoleh berarti semakin dekat solusi hampiran yang diperoleh dengan solusi sejatinya.
10
Metode Numerik Roosenberg Ika Komala Sari 1384202072 6A2 June 9, 2016
1 Pengertian Metode Numerik Roosenberg Salah satu metode pencarian titik minimum dengan cara numerik adalah menggunakan Metode Numerik Roosenberg. Metode Numerik Roosenberg adalah salah satu metode numerik yang digunakan untuk menyelesaikan masalah optimisasi, yakni menentukan nilai x = (x1 , x2 ) ∈ R2 yang meminimumkan atau memaksimumkan Z = F(x). Optimasi ini diperkenalkan oleh Howard H. Rosenbrock pada tahun 1960.
2 Algoritma Metode Numerik Roosenberg 1. Diberikan fungsi Z = F(x1 , x2 ) dan akan ditentukan nilai x = (x1 , x2 ) yang meminimumkan atau memaksimumkan nilai Z = F(x1 , x2 ) tersebut 2. Ambil sebarang titik awal x1 = (x1 , x2 ) 3. Tetapkan > 0 suatu konstanta positif yang menunjukkan kesalahan yang ditoleransi 4. Tentukan arah pencarian direction d1 = (1,0) dan d2 = (0,1) 5. Cari λk dengan cara λk = xk + λk dk 6. Nilai xk+1 ditentukan dengan cara xk+1 = xk + λk dk 7. Iterasi berhenti ketika norm ||xk+1 − xk || < Catatan Untuk arah pencarian direction dk • Untuk arah k ganjil d1 = (1, 0) d2k+1 = ||bbkk || 1
• Untuk arah k genap d2 = (0, 1) d2k = ||bbkk || • bk = λk dk + λk+1 dk+1
3 Contoh Soal dan Penyelesaiannya Tentukan nilai x = (x1 , x2 ) yang meminimumkan Z(x1 , x2 ) = 6x21 + 9x22 − 4x1 − 24x2 dengan Metode Roosenberg dengan toleransi kesalahan = 0, 01 ! Solusi : Penyelesaian dengan Metode Roosenberg Ambil sembarang titik awal x = (0, 2) ∈ R2 Arah pencarian d1 = (1, 0) dan d2 = (0, 1) serta = 0, 01 Iterasi 1 • Nilai λ1 dapat dicari sebagai berikut: λ1 = min Z (x1 + λ1 d1 ) λ1 = min Z ((0, 2) + λ1 (1, 0)) λ1 = min Z ((0, 2) + λ1 , 0) λ1 = min Z (λ1 , 2) • Derivatkan Z (λ1 , 2) dan sama dengankan 0. Z (λ1 , 2) = 6(λ1 )2 + 9(2)2 − 4(λ1 ) − 24(2) Z (λ1 , 2) = 6λ21 + 36 − 4λ1 − 48 Z (λ1 , 2) = 6λ21 − 4λ1 − 12 Z’ (λ1 , 2) = 12λ1 − 4 4 12λ1 − 4 = 0 , maka λ1 = 12 = 13 • Berdasarkan hal tersebut, cari nilai x2 . x2 = x1 + λ1 d1 x2 = (0, 2) + 13 (1, 0) x2 = (0, 2) + ( 13 , 0) x2 = ( 13 , 2) • Akan norm ||x2 − x1 || < p 1 di cek ( 3 − 0)2 + (2 − 2)2 > 0, 01 1 3 > 0, 01, maka (iterasi di lanjutkan). Iterasi 2
2
• Nilai λ2 dapat dicari sebagai berikut: λ2 = min Z (x2 + λ2 d2 ) λ2 = min Z (( 13 , 2)) + λ2 (0, 1)) λ2 = min Z (( 31 , 2)) + 0, λ2 ) λ2 = min Z ( 13 , 2 + λ2 ) • Derivatkan Z ( 13 , 2 + λ2 ) dan sama dengankan 0. Z ( 13 , 2 + λ2 ) = 6( 13 )2 + 9(2 + λ2 )2 − 4( 13 ) − 24(2 + λ2 ) Z ( 13 , 2 + λ2 ) = 96 + 36 + 36λ2 + 9λ22 − 43 − 48 − 24λ2 Z ( 13 , 2 + λ2 ) = 9λ22 + 12λ2 − 114 9 Z’ ( 13 , 2 + λ2 ) = 18λ2 + 12 12 18λ2 + 12 = 0 , maka λ2 = − 18 =− 23 • Berdasarkan hal tersebut, cari nilai x3 . x3 = x2 + λ2 d2 x3 = ( 13 , 2) + (− 23 )(0, 1) x3 = ( 13 , 2) + (0, − 23 ) x3 = ( 13 , 43 ) • p Akan di cek norm ||x3 − x2 || < ( 13 − 13 )2 + ( 34 − 2)2 > 0, 01 2 3 > 0, 01, maka (iterasi di lanjutkan). Iterasi 3 • Tentukan d3 untuk k=1 (arah ganjil) dengan cara sebagai berikut: d2k+1 = ||bbkk || b1 b1 b1 b1
= λ1 d1 + λ2 d2 = 13 (1, 0) + (− 32 )(0, 1) = ( 13 , 0) + (0, − 32 ) = ( 13 , − 23 )
||b1 || = ||b1 || = ||b1 || = d3 = d3 =
p 1 2 ( ) + (− 23 )2 q 3 1 √9 5 3
+
4 9
b1 ||b1 || ( 31 ,− 23 ) √ 5 3
3
√
d3 =
√ 5 −2 5 , 5 5
• Nilai λ3 dapat dicari sebagai berikut: λ3 = min Z (x3 + λ3 d3 ) √ √ λ3 = min Z ( 13 , 34 ) + λ3 ( 55 , −25 5 )
√ 5 −2 5 λ , λ3 ) 3 5 √ √ 5 5 2 5 4 5 λ3 , 3 − 5 λ3 )
λ3 = min Z (( 13 , 43 )) + ( λ3 = min Z ( 13 +
√
√ 5 λ3 , 43 − 2 5 5 λ3 ) dan sama dengankan 0. 5 √ √ Z ( 13 + 55 λ3 , 43 − 2 5 5 λ3 ) √ √ √ √ = 6( 31 + 55 λ3 )2 + 9( 43 − 2 5 5 λ3 )2 − 4( 31 + 55 λ3 ) − 24( 43 − 2 5 5 λ3 ) 50 2 = 42 5 λ3 − √ 3 √ Z’ ( 13 + 55 λ3 , 43 − 2 5 5 λ3 ) = 84 5 λ3 84 λ = 0, maka λ = 0 3 5 3
• Derivatkan Z ( 31 +
√
• Berdasarkan hal tersebut, cari nilai x4 . x4 = x3 + λ3 d3 √ √ x4 = ( 13 , 43 ) + 0( 55 , −25 5 ) x4 = ( 13 , 43 ) + (0, 0) x4 = ( 13 , 43 ) • p Akan di cek norm ||x4 − x3 || < ( 13 − 13 )2 + ( 34 ) − 43 )2 > 0, 01 0 < 0, 01, maka iterasi berhenti Dengan demikian iterasi berhenti, sehingga nilai x yang meminimumkan fungsi Z dalam soal ini adalah x4 = ( 31 , 34 ). Penyelesaian dengan Analitik Z(x1 , x2 ) = 6x21 + 9x22 − 4x1 − 24x2 •
∂Z ∂x1
∂Z = 12x1 − 4 ; ∂x = 18x2 − 24 2 ∂Z ∂Z = 0, maka Karena ∂x1 = 0 dan juga karena ∂x 2 4 12x1 − 4 = 0, x1 = 12 = 13 24 4 =3 18x2 − 24 = 0, x2 = 18
•
∂2f ∂x21
= 12 ;
Karena
∂2f ∂x21
∂2f ∂x22
= 18 ;
= 12 > 0
∂2f ∂x1 ∂x2 = 0 2 2 dan ∂∂xf2 ( ∂∂xf2 ) 1 2
2
f - ( ∂x∂1 ∂x ) = 12.18−0 = 216 > 0, maka terbukti 2
bahwa titik ( 13 , 43 ) merupakan titik yang meminimumkan fungsi Z = (x1 , x2 ) dalam soal ini. 4
METODE STEEPEST DESCENT Dosen Pengampu: Rukmono Budi Utomo M.Sc.
Disusun Oleh : Linna Tri Lestari (6A1) 1384202140
Diajukan sebagai tugas Ujian Akhir Semester (UAS) Metode Numerik
UNIVERSITAS MUHAMMADIYAH TANGERANG FAKULTAS KEGURUAN DAN ILMU PENDIDIKAN MATEMATIKA June 5, 2016
1
KATA PENGANTAR Alhamdulillah, segala puji dan syukur kami panjatkan kepada Allah SWT. atas rahmat dan karunia yang telah diberikan-Nya, sehingga penulis dapat menyelesaikan makalah ini dengan baik. Dalam penulisan makalah ini dibuat dalam format latex document untuk memenuhi tugas ujian akhir semester mata kuliah metode numerik semester 6 di Universitas Muhammadiyah Tangerang. Selain itu saya juga berharap makalah ini mampu memberikan kontribusi, memberi gambaran ataupun menjadi referensi kita dalam mengenal dan mempelajari materi yang akan dibahas. Saya menyadari bahwa masih jauh dari kesempurnaan, oleh karena itu kritik dan saran yang membangun sangat saya harapkan demi kesempurnaan di masa yang akan datang. Tangerang, 05 Juni 2016 Linna Tri Lestari
2
1 PENDAHULUAN 1.1 Latar Belakang Metode numerik adalah teknik untuk menyelesaikan permasalahan-permasalahan yang diformulasikan secara metematik dengan cara operasi hitungan (arithmetic). Penggunaan metode numerik dilakukan karena tidak semua permasalahan matematis atau perhitungan matematis dapat diselesaikan dengan mudah. Bahkan dalam prinsip matematik suatu persoalan matematik yang paling pertama dilihat adalah apakah persoalan itu memiliki penyelesaian atau tidak. Jadi, jika suatu persoalan sudah sangat sulit atau tidak mungkin diselesaikan dengan metode matematis (analitik) maka kita dapat menggunakan metode nmerik sebagai alternative penyelesaian persoalan tersebut. Dalam perkuliahan metode numerik di semester 6 lalu kita telah membahas berbagai macam metode numerik mulai dari metode golden ratio, metode bisection,metode fibonacci, metode newton, metode aksial, dichotomus, secant, hooke and jeeves, arah konjugasi, roosenberg. Dalam makalah ini yang akan dibahas adalah metode steepest descent, yang erat kaitannya dengan metode aksial, hooke and jeeves, arah konjugasi serta roosenberg.
1.2 Rumusan Masalah • Menjelaskan pengertian dari metode numerik steepest descent • Menjelaskan algoritma metode steepest descent • Menjelaskan contoh penyelesaian metode steepest descent
1.3 Tujuan dan Manfaat Adapun tujuan dari penulisan makalah ini adalah untuk memenuhi tugas ujian akhir semester mata kuliah metode numerik di semester 6, serta berbagi pengetahuan kepada para pembaca mengenai materi yang akan dibahas yaitu metode steepest descent. Manfaat yang dapat petik dari tujuan tersebut yaitu diharapkan dapat menambah wawasan para pembaca dan khususnya untuk mahasiswa-mahasiswi Universitas Muhammadiyah Tangerang.
3
2 PEMBAHASAN 2.1 Pengertian Metode Steepest Descent Metode steepest descent juga dikenal dengan nama metode gradient. Metode steepest descent merupakan prosedur paling mendasar yang diperkenalkan oleh Cauchy pada tahun 1847. Metode ini adalah metode gradien sederhana yang menggunakan vektor gradien untuk menentukan arah pencarian pada setiap iterasi. Kemudian, dari arah tersebut akan ditentukan besar ukuran langkahnya. Metode Steepest Descent digunakan untuk mencari minimum suatu fungsi, yakni dengan menggunakan nilai negatif dari gradient fungsi disuatu titik. Digunakan nilai negatif dari gradient karena gradien memberikan nilai kenaikan yang semakin besar. Dengan nilai negatif dari gradient maka akan diperoleh nilai penurunan yang semakin besar. Metode Steepest Descent digunakan untuk mencari minimum suatu fungsi, yakni dngan menggunakan nilai negatif dari gradient fungsi disuatu titik. Digunakan nilai negatif dari gradient karena gradien memberikan nilai kenaikan yang semakin besar. Dengan nilai negatif dari gradient maka akan diperoleh nilai penurunan yang semakin besar. Pada beberapa kasus, metode steepest descent ini memiliki kekonvergenan yang lambat menuju solusi optimum karena langkahnya berbentuk zig-zag. Metode ini dapat digunakan untuk optimasi tanpa kendala maupun dengan kendala.
2.2 Algoritma Metode Steepest Descent 1. Diberikan fungsi Z = f (x) untuk mencari nilai (x1 , x2 ), XR2 yang meminimumkan fungsi tersebut 2. Tentukan titik awal x ¯k = (x1 , x2 ), ε atau error yang ditentukan dan ambil k = 0 3. Dihitung gradient dari f (x) pada titik xk ,yaitu ∇f (¯ xk ). 4. Kemudian dihitung ∇f (¯ xk ). Jika ||∇f (¯ xk )|| < ε, iterasi dihentikan dan pilih xk sebagai titik minimum. Jika sebaliknya, lanjutkan ke langkah selanjutnya. 5. Misalkan arah pencarian pada titik x ¯k adalah dk = −∇f (xk ). 6. Dihitung λk = minZ(¯ xk + λk dk ) 7. Derivatifkan Z(¯ xk + λk dk ) dan sama dengankan nol untuk menentukan nilai λk 8. Dihitung x ¯k+1 dimana x ¯k+1 = x ¯k + λk dk 9. Iterasi terhenti ketika ||∇f (¯ xk )|| < Kondisi ∇f (¯ xk ) = 0 kerapkali tidak dapat dengan tetap dipenuhi karena perhitungan secara numerik dari gradient akan jarang tetap sama dengan nol. Dalam kasus demikian maka sebagai kriteria penghentian adalah dengan mengecek norma gradient, yakni jika norma ||∇f (¯ xk )|| dari gradient adalah tidak lebih besar dari suatu toleransi yang diberikan maka iterasi dihentikan sebagai alternatif dapat juga dilakukan dengan menghitung perbedaan nilai mutlak ||f (¯ xk+1 − (¯ xk )|| diantara nilai objektif untuk setiap dua iterasi brturut-turut. Jika perbedaannya tidak lebih besar dari suatu toleransi yang diberikan maka perhitungan diberikan. Agar lebih mudah dalam memahami algoritma metode Stepeest Descent,dibawah ini diberikan diagram alir metode Stepeest Descent. 4
Figure 1: Diagram alir algoritma Steepest Descent
2.3 Contoh Soal 1. Diberikan suatu fungsi f (X) = 6x21 + 2x22 + 2x1 x2 − 12x1 − 2x2 + 6, dengan menggunakan metode steepest descent, tentukan pembuat minimum jika diberikan titik awal (0, 1) dan ε = 0.2 Penyelesaian: ITERASI I • Dari soal diketahui fungsi awal f (X) = 6x21 + 2x22 + 2x1 x2 − 12x1 − 2x2 + 6 dengan titik awal x0 = (0, 1) dan ε = 0.2 • Untuk mencari ∇f (¯ x0 ), terlebih dahulu turunan dari x1 terhadap fungsi f(X) dan turunan x2 terhadap fungsi f(X) yaitu sebagai berikut: ∂F ∂x1 = 12x1 + 2x2 − 12 ∂F ∂x2 = 4x2 + 2x1 − 2 maka : ∇f (¯ x0 ) = ∇f (x1 , x2 ) = ∇f (0, 1) ! ! 12(0) + 2(1) − 12 −10 ∇f (¯ x0 ) = = 4(1) + 2(0) − 2 2 • Kemudian cek apakah ||∇f (¯ x0 )|| < ! ε atau > ε yaitu dengan cara :
−10 q √
2 2 k∇f (x0 )k = k∇f (0, 1)k =
= (−10) + (2) = 104 = 10.2
2 Karena ||∇f (¯ x0 )|| = 10.2 > ε maka memenuhi syarat bahwa iterasi dilanjutkan.
5
• Mencari arah pencarian d0 ! −10 d0 = −∇f (¯ x0 ) = − = 2
10 −2
!
• Mencari nilai λ0 yaitu dengan cara sebagai berikut : λ0 = min Z(¯ x0 + λ0 d0 ) λ0 = min Z((0, 1) + λ0 (10, −2)) λ0 = min Z((0, 1) + (10λ0 , −2λ0 )) λ0 = min Z(10λ0 , −2λ0 + 1) Subtitusikan Z(10λ0 , −2λ0 + 1) ke persamaan awal: Z(10λ0 , −2λ0 +1) = 6(10λ0 )2 +2(−2λ0 +1)2 +2((10λ0 )(−2λ0 +1))−12(10λ0 )−2(−2λ0 +1)+6
Z(10λ0 , −2λ0 + 1) = 600λ20 + 8λ20 − 8λ0 + 2 − 40λ20 + 20λ0 − 120λ0 + 4λ0 − 2 + 6 Z(10λ0 , −2λ0 + 1) = 568λ20 − 104λ0 + 6 Kemudian turunkan fungsi Z diatas dan sama dengankan nol untuk memperoleh λ0 : dZ ⇔ dλ =0 0 ⇔ 1136λ0 − 104 = 0 ⇔ 1136λ0 = 104 104 ⇔ λ0 = 1136 = 0.091549295 ⇔ λ0 ≈ 0.092 • Mencari nilai x ¯1 x ¯1 = x ¯0 + λ0 d0 x ¯1 = (0, 1) + 0.092(10, −2) x ¯1 = (0, 1) + (0.92, −0.184) x ¯1 = (0.92, 0.816) ITERASI II • Dari iterasi 1 diperoleh x ¯1 = (0.92, 0.816) • Mencari ∇f (¯ x1 ): ∇f (¯ x1 ) = ∇f (0.92, 0.816) ! 12(0.92) + 2(0.816) − 12 ∇f (¯ x1 ) = = 4(0.816) + 2(0.92) − 2
11.04 + 1.632 − 12 3.264 + 1.84 − 2
!
=
0.672 3.104
!
• Kemudian cek apakah x1 )||
||∇f (¯ ! < ε atau > ε yaitu dengan cara :
0.672 q √
2 2 k∇f (0.92, 0.816)k =
= (0.672) + (3.104) = 0.451584 + 9.634816 =
3.104 √ 10.0864 = 3.176 Karena ||∇f (¯ x1 )|| = 3.176 > ε maka memenuhi syarat bahwa iterasi dilanjutkan. • Mencari arah pencarian d1 ! 0.672 d1 = −∇f (¯ x1 ) = − = 3.104
−0.672 −3.104
!
• Mencari nilai λ1 yaitu dengan cara sebagai berikut : λ1 = min Z(¯ x1 + λ1 d1 ) λ1 = min Z((0.92, 0.816) + λ1 (−0.672, −3.104)) 6
λ1 = min Z((0.92, 0.816) + (−0.672λ1 , −3.104λ1 )) λ1 = min Z(−0.672λ1 + 0.92, −3.104λ1 + 0.816) Subtitusikan Z(−0.672λ1 + 0.92, −3.104λ1 + 0.816) ke persamaan awal: Z(−0.672λ1 + 0.92, −3.104λ1 + 0.816) = 6(−0.672λ1 + 0.92)2 + 2(−3.104λ1 + 0.816)2 + 2(−0.672λ1 + 0.92)(−3.104λ1 + 0.816)) − 12(−0.672λ1 + 0.92) − 2(−3.104λ1 + 0.816) + 6
= 26.150912λ21 − 10.0864λ1 + 1.239552 Kemudian turunkan fungsi Z diatas dan sama dengankan nol untuk memperoleh λ1 : dZ ⇔ dλ =0 1 ⇔ 52.301824λ1 − 10.0864 = 0 ⇔ 52.301824λ1 = 10.0864 10.0864 ⇔ λ1 = 52.301824 = 0.1928498708 ⇔ λ1 ≈ 0.193 • Mencari nilai x ¯2 x ¯2 = x ¯1 + λ1 d1 x ¯2 = (0.92, 0.816) + 0.193(−0.672, −3.104) x ¯2 = (0.92, 0.816) + (−0.129696, −0.599072)) x ¯2 = (0.790304, 0.216928) x ¯2 ≈ (0.79, 0.217) ITERASI III • Dari iterasi 2 diperoleh x ¯2 = (0.79, 0.217) • Mencari ∇f (¯ x2 ): ∇f (¯ x2 ) = ∇f (0.79, 0.217) ! 12(0.79) + 2(0.217) − 12 = ∇f (¯ x2 ) = 4(0.217) + 2(0.79) − 2
2.48 + 0.434 − 12 0.868 + 1.58 − 2
!
=
−2.086 0.448
!
• Kemudian cek apakah x2 )||! < ε atau > ε yaitu dengan cara :
||∇f (¯
−2.086 q √
2 2 k∇f (0.92, 0.816)k =
= (−2.086) + (0.448) = 4.351396 + 0.200704 =
0.448 √ 4.5521 = 2.136 Karena ||∇f (¯ x2 )|| = 2.136 > ε maka memenuhi syarat bahwa iterasi dilanjutkan. • Mencari arah pencarian d2 ! −2.086 d2 = −∇f (¯ x2 ) = − = 0.448
2.086 −0.448
!
• Mencari nilai λ2 yaitu dengan cara sebagai berikut : λ2 = min Z(¯ x2 + λ2 d2 ) λ2 = min Z((0.79, 0.217) + λ2 (2.086, −0.448)) λ2 = min Z((0.79, 0.217) + (2.086λ2 , −0.448λ2 )) λ2 = min Z(2.086λ2 + 0.79, −0.448λ2 + 0.217) Subtitusikan Z(2.086λ2 + 0.79, −0.448λ2 + 0.217) ke persamaan awal : Z(2.086λ2 + 0.79, −0.448λ2 + 0.217) 7
= 6(2.086λ2 + 0.79)2 + 2(−0.448λ2 + 0.217)2 + 2(2.086λ2 + 0.79)(−0.448λ2 + 0.217)) − 12(2.086λ2 + 0.79) − 2(−0.448λ2 + 0.217) + 6
= 28.37884λ22 − 4.5521λ2 + 0.267638 Kemudian turunkan fungsi Z diatas dan sama dengankan nol untuk memperoleh λ2 dZ =0 ⇔ dλ 2 ⇔ 56.75768λ2 − 4.5521 = 0 ⇔ 56.75768λ2 = 4.5521 4.5521 ⇔ λ2 = 56.75768 = 0.080202362 ⇔ λ2 ≈ 0.08 • Mencari nilai x ¯3 x ¯3 = x ¯2 + λ2 d2 x ¯3 = (0.79, 0.217) + 0.08(2.086, −0.448) x ¯3 = (0.79, 0.217) + (0.16688, −0.03584)) x ¯3 = (0.95688, 0.18116) x ¯3 ≈ (0.96, 0.18) ITERASI IV • Dari iterasi 3 diperoleh x ¯3 = (0.96, 0.18) • Mencari ∇f (¯ x3 ): ∇f (¯ x3 ) = ∇f (0.96, 0.18) ! 12(0.96) + 2(0.18) − 12 = ∇f (¯ x3 ) = 4(0.18) + 2(0.96) − 2
11.52 + 0.36 − 12 0.72 + 1.92 − 2
!
=
−0.12 0.64
!
• Kemudian cek apakah x3 )|| > ε yaitu dengan cara :
||∇f (¯ ! < ε atau q
−0.12 √
k∇f (0.96, 0.18)k = (−0.12)2 + (0.64)2 = 0.0144 + 0.4096 =
=
0.64 √ 0.424 = 0.651 Karena ||∇f (¯ x3 )|| = 0.651 > ε maka memenuhi syarat bahwa iterasi dilanjutkan. • Mencari arah pencarian d3 ! −0.12 d3 = −∇f (¯ x2 ) = − = 0.64
0.12 −0.64
!
• Mencari nilai λ3 yaitu dengan cara sebagai berikut : λ3 = min Z(¯ x3 + λ3 d3 ) λ3 = min Z((0.96, 0.18) + λ3 (0.12, −0.64)) λ3 = min Z((0.96, 0.18) + (0.12λ3 , −0.64λ3 )) λ3 = min Z(0.12λ3 + 0.96, −0.64λ3 + 0.18) Subtitusikan Z(0.12λ3 + 0.96, −0.64λ3 + 0.18) ke persamaan awal : Z(0.12λ3 + 0.96, −0.64λ3 + 0.18) = 6(0.12λ3 + 0.96)2 + 2(−0.64λ3 + 0.18)2 + 2(0.12λ3 + 0.96)(−0.64λ3 + 0.18)) − 12(0.12λ3 + 0.96) − 2(−0.64λ3 + 0.18) + 6
= 0.752λ23 − 0.424λ3 + 0.06 Kemudian turunkan fungsi Z diatas dan sama dengankan nol untuk memperoleh λ3 dZ ⇔ dλ =0 3 8
⇔ 1.504λ3 − 0.424 = 0 ⇔ 1.504λ3 = 0.424 ⇔ λ3 = 0.424 1.504 = 0.28191489 ⇔ λ3 ≈ 0.282 • Mencari nilai x ¯4 x ¯4 = x ¯3 + λ3 d3 x ¯4 = (0.96, 0.18) + 0.282(0.12, −0.64) x ¯4 = (0.96, 0.18) + (0.033, −0.18048)) x ¯4 = (0.99384, 0.00048) x ¯4 ≈ (0.994, 0.0005) ITERASI V • Dari iterasi 4 diperoleh x ¯4 = (0.994, 0.0005) • Mencari ∇f (¯ x4 ): ∇f (¯ x4 ) = ∇f (0.79, 0.217) ! 12(0.994) + 2(0.0005) − 12 ∇f (¯ x4 ) = = 4(0.0005) + 2(0.994) − 2
11.928 + 0.001 − 12 0.002 + 1.988 − 2
!
=
−0.071 −0.01
!
• Kemudian cek apakah ||∇f (¯ x4 )|| ε yaitu dengan cara :
−0.071 q √
2 2 k∇f (0.994, 0.0005)k =
= (−0.071) + (−0.01) = 0.005041 + 0.0001 =
−0.01 √ 0.015041 = 0.123 Karena ||∇f (¯ x4 )|| = 0.123 < ε maka telah memenuhi syarat bahwa iterasi terhenti. TABEL ITERASI Dengan konsep Metode Numerik Steepest Descent maka perhitungan yang diperoleh disajikan dalam tabel dibawah ini: Iterasi I II III IV V
xk (0,1) (0.92, 0.816) (0.79, 0.217) (0.96, 0.18) (0.994, 0.0005)
∇f (xk ) (-10, 2) (0.672, 3.104) (-2.086, 0.448) (-0.12, 0.64) (-0.071, -0.01)
||∇f (xk )|| 10.2 > ε 3.176 > ε 2.136 > ε 0.651 > ε 0.123 < ε
9
dk (10, -2) (-0.672, -3.104) (2.086, -0.448) (0.12, -0.64)
.....
λk 0.092 0.193 0.08 0.282 .....
x¯k (0.92, 0.816) (0.79, 0.217) (0.96, 0.18) (0.994, 0.0005)
.......
Pembuktian dengan Cara Analitik • Dalam soal diberikan fungsi f (X) = 6x21 + 2x22 + 2x1 x2 − 12x1 − 2x2 + 6, kemudian dicari turunan-turunan sebagai berikut: ∂f = 12x1 + 2x2 − 12..............(1) ⇔ ∂x 1 ∂f ⇔ ∂x = 4x2 + 2x1 − 2..............(2) 2 ⇔ ⇔ ⇔
∂2f = ∂x21 2 ∂ f = ∂x22 2 ∂ f ∂x1 ∂x2
12 4 =2
• Dicari nilai δ yaitu : 2
2
2
f δ = ( ∂∂xf2 )( ∂∂xf2 ) − ( ∂x∂1 ∂x )2 = 12(4) − 22 = 48 − 4 = 44 > 0 2 1
2
• Kemudian untuk mencari nilai (x1 , x2 ) menggunakan cara sebagai berikut : Eliminasi Persamaan (1) dan (2) 12x1 + 2x2 − 12 = 0| × 2| → 24x1 + 4x2 − 24 = 0 4x2 + 2x1 − 2 = 0| × 1| → 4x2 + 2x1 − 2 = 0 diperoleh nilai : 22x1 − 22 = 0 x1 = 1 Subtitusi nilai x1 = 1 ke persamaan (2): 4x2 + 2x1 − 2 = 0 4x2 + 2(1) − 2 = 0 4x2 = 0 x2 = 0 • Karena δ > 0 maka terbukti bahwa (x1 , x2 ) = (1, 0) meminimumkan fungsi Z = f (x) tersebut.
10
3 PENUTUP 3.1 Kesimpulan Metode steepest descent merupakan metode numerik untuk menyelesaikan persoalan optimasi dalam mencari nilai nilai (x1 , x2 ) yang meminimumkan fungsi Z=f(X) dengan x ¯R2 (dalam perkuliahan ini dibatasi sampai R2 ). Penyelesaian optimasinya berkaitan dengan metode aksial, hook and jeeves, arah konjugasi serta roosenberg. Hanya saja metode steepest descent ini dalam mencari arah pencariannya berbeda dari pada yang lainnya.
3.2 Saran Setelah membahas materi mengenai metode steepest descent, penulis mengharapkan agar selanjutnya materi ini dapat dikembangkan lebih jauh terutama mengenai penyelesaian optimasinya. Karena belajar mengenai metode ini tidaklah mudah, dibutuhkan pemahaman yang mendalam untuk dapat menyelesaikannnya. Penulis berharap agar makalah ini dapat memberikan manfaat kepada setiap orang yang membacanya. Kritik dan saran yang membangun sangat penulis perlukan demi kesempurnaan di masa yang akan datang.
11
Metode Numerik Stepest Descent LUPINIA FITIA 1384202145 6A2 Pendidikan Matematika Universitas Muhammadiyah Tangerang June 8, 2016
BAB I PENDAHULUAN Metode Numerik adalah teknik-teknik yang digunakan untuk memformulasikan masalah matematis agar dapat dipecahkan dengan operasi perhitungan. Metode Numerik cocok untuk menggambarkan ketangguhan dan keterbatasan komputer menangani galat (error) suatu nilai hampiran (aproksimasi) dari masalah. Beberapa definisi Metode Numerik yang dikemukakan oleh para ahli matematika, diantaranya : • Metode Numerik adalah teknik-teknik yang digunakan untuk merumuskan masalah matematika agar dapat diselesaikan hanya dengan operasi hitungan, yang terdiri dari operasi tambah, kurang, kali, dan bagi (Ibraheem dan Hisyam) • Metode Numerik adalah suatu teknik untuk memformulasikan masalah matematika sehingga dapat diselesaikan dengan operasi tambah, kurang, kali, dan bagi (Rochmad) • Metode Numerik adalah teknik dimana masalah matematika diformulasikan sedemikian rupa sehingga dapat diselesaikan oleh pengoperasian matematika (Chapra dan Chanale) Dalam Metode Numerik terdapat beberapa metode untuk menyelesaikan persamaan karakteristik seperti Polinomial Tinggi, Sinusioda, Eksponensial, Logaritmik, atau Kombinasi dari persamaan-persamaan tersebut. Ada beberapa macam Metode Numerik seperti Metode Biseksi, Metode Newton-Raphson, Metode Secant, Metode Aksial, Arah Konjugant, dan lainnya lagi masih banyak metode-metode dalam mengerjakan suatu permasalahan. Yang akan dibahas pada artikel ini adalah Metode Steepest Ascent/Descent. Pada artikel ini, kita akan mengetahui definisi dari Metode Steepest Ascent/Descent,
1
Perbedaan dari Metode tersebut, Algoritma. Penulis juga akan memberikan suatu contoh serta cara penyelesaian soal menggunakan Metode Steepest Ascent/Descent
• Rumusan Masalah • Definisi Metode Numerik Steepest Ascent/Descent • Algoritma pada Metode Numerik Steepest Ascent/Descent • Soal dan Pembahasannya • Tujuan Penulisan • Mengetahui Definisi Metode Numerik Steepest Ascent/Descent • Mengetahui Algoritma Metode Numerik Metode Numerik Steepest Ascent/Descent • Memahami Soal dan Pembahasannya BAB II PEMBAHASAN
1 Definisi Metode Numerik Steepest Ascent/Descent Metode Numerik Steepest Ascent/Descent merupakan jenis metode gradien yang paling sederhana. Terminologi : Steepest Ascent (untuk pencarian maksimum fungsi) Steepest Descent (untuk pencarian minimum fungsi). Prinsip pencarian optimum yaitu dilakukan serangkaian proses transformasi untuk mengubah sebuah fungsi dengan banyak variabel (multidimensional function) menjadi sebuah fungsi dengan variabel tunggal (one-dimensional function), berdasarkan gradien arah pencarian. Langkah pencarian optimum ini selanjutnya dilakukan secara berulang-ulang (iteratif).
2 Algoritma Metode Numerik Steepest Ascent/Descent • Tentukan sebarang titik awal X = {x1 , x2 } • Tentukan konstanta > 0 ∂z t • Bentuk ∇Z(x1 , x2 )=( ∂z x1 , x2 ) dan tentukan ∇Z(X 1 ) dan lakukan untuk ∇Z(X k )
• Jika normk ∇Z(X k )kkurang dari , maka iterasi berhenti • Tentukan dk =-∇Z(X k ),λk =min Z (X k + λk dk ) dan X ( k + 1) = X k + λk dk
2
3 Bentuk Soal dan Pembahasannya Pertanyaan Tentukan nilai X = {x1 , x2 } yang meminimalkan Z = (x1 , x2 ) = 2x21 + 3x22 − 6x1 − 4x2 dengan menggunakan Metode Numerik Steepest Descent jika diketahui nilai > 0, 01 solusi iterasi 1 • Berdasarkan soal tersebut ! dapat ditentukan : 4x1 − 6 ∇Z(x1 , x2 )= 6x2 − 4 • Ambil sebarang titik! misalnya X k = −1, 23 dengan demikian : −10 ∇Z(X 1 ) = 0 √ CEK! : k ∇Z(X 1 )k = −102 + 02 = 10 > epsilon • Selanjutnya ditentukan : ! 10 dan d1 = -∇Z (X 1 ) = 0 λ1 = min Z (X 1 + λ1 d1 ) λ1 = min Z (−1, 32 + 10λ1 0) λ1 = min Z (10λ1 −1, 32 ) Derivatifkan Z (10λ1 −1, 23 ) = 2x21 + 3x22 − 6x1 − 4x2 ) dapat dicari dengan : (X 2 ) = (X k + λk dk ) (X 2 ) = (−1, 32 + ( 14 )(-10,0) (X 2 ) = (−1, 32 ) + ( 10 4 , 0) (X 2 ) = ( 64 , 32 ) CEK! : Dengan memasukkan nilai (X 2 ) = nilai (X 2 ) =
0 0
( 46 , 23 )
kedalam
4x1 − 6 6x2 − 4
!
diperoleh
!
Selanjutnya nilai k ∇Z( 46 , 23 )k =
√
02 + 02 = 0 < maka ITERASI BERHENTI
3
4 SOLUSI ANALITIK Tentukan nilai X = {x1 , x2 } yang meminimalkan Z = (x1 , x2 ) = 2x21 + 3x22 − 6x1 − 4x2 dengan menggunakan Metode Numerik Steepest Descent jika diketahui nilai > 0, 01
PENYELESAIAN ∂z ∂z ( ∂x ) = 4x1 − 6, ( ∂x ) = 6x2 − 4 1 2 ∂z ∂z Karena ( ∂x ) = 0 dan ( ∂x ) = 0 maka nilai x1 = ( 46 ) dan x2 = ( 23 ) 1 2
Lebih Lanjut 2
2
2
∂ z ∂ z 2 ∂ z ( ∂x 2 ) = 4 dan ( x2 x2 ) = 6 dan nilai ( ∂x ∂x ) = 0 1 2 1
sehingga (
2
∂2z x21 2
)(
∂2z x22
2
z )2 = 4 (6) - 0 = 24 ) - ( ∂x∂1 ∂x 2 2
2
2
∂ z ∂ z ∂ z ∂ z 2 = 24 > 0, maka terbukti Karena ( ∂x 2 ) = 4 > 0 dan ( ∂x2 ) ( ∂x2 ) - ( ∂x ∂x ) 1 2 1
1
2
bahwa titik ( 46 , 32 ) merupakan titik yang meminimumkan fungsi Z = (x1 , x2 )
4
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
METODE ARAH KONJUGAT Nur Ukhti Salamah 1384202147 8 Juni 2016
PENDAHULUAN 1 Latar Belakang Matematika merupakan ilmu yang banyak dibutuhkan dalam kehidupan seharihari. Matematika juga menjadi sumber untuk pengembangan ilmu pengetahuan yang lain. Matematika memiliki daya abstraksi yang mampu mengabstraksikan permasalahan-permasalahan yang sering muncul baik dalam matematika itu sendiri maupun dalam kehidupan nyata sehingga mampu menyelesaikan permasalahan dengan tepat dan cepat. Dalam sejarah perkembangan ilmu pengetahuan dan teknologi, matematika memegang peranan yang sangat penting untuk memecahkan berbagai permasalahan secara kuantitatif. Para ahli menciptakan berbagai metode atau cara untuk menyelesaikan permasalahan manusia yang menyangkut persamaan multivariabel. Dengan berbagai metode tersebut, maka hasil perhitungan akan mendekati atau konvergen dengan nilai (solusi ) aslinya. Optimasi sebagai salah satu cabang dalam matematika sering digunakan sebagai acuan untuk menyelesaikan permasalahan-permasalahan di bidang ekonomi, teknik, dan lainnya. Dengan optimasi maka permasalahan-permasalahan 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 tahapan-tahapan 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 1
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 gradien sekawan (conjugate gradient). Metode gradien sekawan merupakan metode untuk meminimalkan suatu fungsi dimana arah pencarian pertamanya diambil arah penurunan tercuram (steepest descent). Untuk mendapatkan kekonvergenan yang lebih cepat, maka selain menggunakan arah penurunan tercuram juga menggunakan arah yang saling konjugat. Metode gradien sekawan menggunakan arah pencarian yang saling ortogonal serta gradien yang selalu diperbaharui pada setiap langkah iterasi, sehingga pada setiap iterasi akan bergerak maju menuju penyelesaian yang optimal. 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.
1.1 Rumusan Masalah 1. Apa yang dimaksud dengan metode numerik arah konjugasi? 2. Bagaimana algoritma dalam arah konjugasi? 3. Bagaimana cara menyelesaikan persoalan numerik dengan menggunakan arah konjugasi?
1.2 Tujuan 1. Untuk menambah pengetahuan mengenai berbagai metode yang dapat digunakan dalam persoalan numerik
2
2. Dapat melatih mahasiswa dalam menganalisis permasalahan-permasalahan numerik 3. Untuk menyelesaikan tugas mata kuliah metode numerik
3
PEMBAHASAN 2 Pengertian Arah Konjugat Metode arah konjugasi (Conjugate Direction) telah diakui secara luas karena kegunaanya yang begitu besar. Manfaat paling utama dari metode yakni dalam memecahkan permasalahan skala besar di bidang ekonomi dalam proses hitungmenghitung dan meminimalkan simpanan kebutuhan. Selain itu, mengakumulasi batas toleransi keslahan mencapai 10−10 . Metode Arah Konjugasi telah diusulkan selama kurang lebih 50-60 tahun. Selama 10 tahun terakhir metode ini terus diperbaiki dan berbagai macam program telah ditambahkan (diperluas). Arah konjugasi adalah metode iteratif yang sangat popular untuk memecahkan permasalahan sistem linier berskala besar. Pada umumnya arah konjugasi dapat dinyatakan sebagai metode langsung (direct method) atau metode iteratif (Iteratif Method). Akan tetapi biasany aarah konjugasi digunakan sebagai metode iteratif supaya dapat diaplikasikan pada sistem jarang (Sparse System) yang terlalu besar jika dipecahkan dengan metode langsung. Sistem seperti ini biasanya muncul saat memecahkan persamaan diferensial parsial. Metode gradien konjugat termasuk pada metode Subruang Krylov yang merujuk pada pemecahan iterasi dari persamaan linear dengan bentuk Ax = y. Topiknya adalah untuk membuat persamaan dari solusi perkiraan vektor kombinasi linear dengan tipe u, Au, A2u, Anu dalam metode ini matriks A adalah matriks simetris dan matriks positif definit. Conjugate Directiont (CD) digunakan untuk menentukan approximasi atau pendekatan persamaan dari solusi persamaan Ax = y dengan minimisasi fungsi. Algoritma arah konjugat dapat ditentukan dengan cara : 1. Diberikan Z = F (x1 , x2 ) dan akan ditentukan¯ x = (x1 , x2 ) yang meminimalkan atau memaksimalkan Z = F (x1 , x2 ) 2. Ambil sembarang titik awal x¯1 = (x1 , x2 )R2 3. Dibentuk suatu matriks H (Hessian) "
H=
∂z ∂x1 2 ∂z ∂x2 x1
∂z ∂x1 x2 ∂z ∂x2 2
#
4. Tetapkan arah pencarian "
d1 =
1 0 4
#
"
, d2 =
a b
#
5. dengan d2 = dT1 Hd1 dan d2 =0 lakukan untuk dk = dTk−1 Hdk atau dk+1 = dTk Hdk+1 dengan dTk = Transpos dk Contoh: a1 a T 2 dk = ;d = [ a1 a2 : an ] : k an 6. Tentukan λk = M in z(xk + λk dk ) dan xk+1 = xk + λk dk 7. Berhenti ketika k xk − xk−1 k
0 sembarang konstanta Contoh : k(a1 , b1 ) − (a2 , b2 )k = (a1 − a2 )2 + (b1 − b2 )2 Contoh Soal 1: Max Z = x1 2 + x2 2 − 3x1 x2 + 2x1 , dengan arah konjugasi dimulai dari titik (0,0) dengan toleransi kesalahan 0,01! Jawab : • Ambil x¯ = (0, 0), dengan toleransi kesalahan ε = 0,01 • Dibentuk suatu matriks H (Hessian) "
2 −3 −3 2
#
1 0
#
a b
H= • Dimana arah pencariannya : "
d1 =
"
; d2 =
#
• dengan d2 = d1 T .H.d2 h
i
"
1 0 . h
2 −3 −3 2 i
2 −3 .
"
a b
5
.
#
2a − 3b = 0 2a = 3b 3 a= b 2
# "
=0
a b
#
• Misal ambil a = 1, 5 maka nilai b = 1 • Dicari λ1 dengan = Max z(x1 + λ1 d1 ) = Max z (0,0) + λ1 (1,0) = Max z (0,0) + (λ1 , 0) = Max z (λ1 , 0) • Dengan z (λ1 , 0) maka = (λ1 )2 + (0)2 - 3(λ1 ).0 + 2(λ1 ) = (λ1 )2 + 2(λ1 ) • λ1 dicari dengan
dz dλ1
= 2λ1 + 2 = 0 ⇔ λ1 = −1
ITERASI 2 • x2 = (x1 + λ1 d1 ) x2 = (0,0) + -1 (1,0) x2 = (0,0) +(-1,0) x2 =(-1,0) • kita cek x2 = (−1, 0) ⇔k xk − xk−1 q k<ε √ dengan = k (−1, 0) − (0, 0) k = (−1)2 + (0)2 = 1 = 1 > ε • Dicari λ2 dengan = Max z(x2 + λ2 d2 ) = Max z (-1,0) + λ2 (1,5;1) = Max z (-1,0) + (1, 5λ2 , λ2 ) = Max z (1, 5λ2 − 1, λ2 ) • Dengan z (1, 5λ2 −1, λ2 ) = (1, 5λ2 −1)2 + (λ2 )2 - 3(1, 5λ2 −1).(λ2 ) + 2(1, 5λ2 − 1) = (2, 25λ2 )2 − 3λ2 + 1 + (λ2 )2 + (−4, 5λ2 + 3)(λ2 ) + (3λ2 − 2) = (2, 25λ2 )2 − 3λ2 + 1 + (λ2 )2 − (4, 5λ2 )2 + 3λ2 + 3λ2 − 2 = (−1, 25λ2 )2 + 3λ2 − 1 = 0 • λ2 dicari dengan
dz dλ2
= −2, 5λ2 + 3 = 0 ⇔ λ2 = 1, 2
ITERASI 3 • x3 = (x2 + λ2 d2 ) x3 = (-1,0) + 1,2 (1,5;1) x3 = (-1,0) +(1,8;1,2) x3 = (0,8 ; 1,2) 6
• kita cek x3 = (0, 8; 1, 2) ⇔k xk − xk−1 q k<ε √ dengan = k (0, 8; 1, 2) − (−1, 0) k = (1, 8)2 + (1, 2)2 = 4, 68 = 2, 16 > ε(iterasi belum berhenti sebab masih lebih dari ε) • Dicari λ3 dengan = Max z(x3 + λ3 d3 ) = Max z (0,8 ; 1,2) + λ3 (1,0) = Max z (0,8 ; 1,2) + (λ3 , 0) = Max z (0, 8 + λ3 ; 1, 2) • Dengan z (0, 8+λ3 ; 1, 2) = (0, 8+λ3 )2 + (1, 2)2 - 3(0, 8+λ3 ).(1, 2) + 2(0, 8+λ3 ) = 0, 64 + 1, 6λ3 + (λ3 )2 + 1, 44 + (−2, 4 − 3λ3 )(1, 2) + 1, 6 + 2λ3 = (0, 64 + 1, 6λ3 + (λ3 )2 + 1, 44 − 2, 88 − 3, 6λ3 + 1, 6 + 2λ3 = (λ3 )2 + 0, 8 • λ3 dicari dengan
dz dλ3
= 2λ3 = 0 ⇔ λ3 = 0
ITERASI 4 • x4 = (x3 + λ3 d3 ) x4 = (0,8 ; 1,2) + 0 (1,0) x4 = (0,8 ; 1,2) +(0,0) x4 = (0,8 ; 1,2) • kita cek x4 = (0, 8; 1, 2) ⇔k xk − xk−1 k < qε √ dengan = k (0, 8; 1, 2) − (0, 8; 1, 2) k = (0)2 + (0)2 = 0 = 0 < ε(iterasi berhenti sebab kurang dari ε) NOTE: Karena k∇Z = 0, 8; 1, 2k = 0 maka hal ini bisa dikatakan bahwa kesalahan perhitungan atau error adalah 0, sehingga mengakibatkan jawaban yang didapat dengan menggunakan metode numerik (arah konjugasi) adalah sama dengan solusi analitiknya.
7
SOLUSI ANALITIK Contoh Soal : Max z = x1 2 + x2 2 − 3x1 x2 + 2x1 , dengan arah konjugasi dimulai dari titik (0,0) dengan toleransi kesalahan 0,01! Jawab •
dz dx1
= 2x1 − 3x2 + 2 ⇔ 2x1 = 3x2 − 2 = x1 =
•
d2 z dx1
=2
•
dz dx2
= 2x2 − 3x1 ⇔ 2x2 = 3( 3x22−2 )
2x2 =
3x2 −2 2
9x2 −6 2
4x2 = 9x2 − 6 ⇔ x2 = 1, 2 ∗x1 =
•
3x2 −2 2
x1 =
3(1,2)−2 2
x1 =
3,6−2 2
d2 z dλ2
⇔ x1 = 0, 8
=2
Sekarang kita buktikan nilai x1 = 0, 8 dan x2 = 1, 2 benar memaksimalkan fungsi Z = x1 2 + x2 2 − 3x1 x2 + 2x1
8
CEK !! ∂2z ∂2z . ∂x1 ∂x2
−
∂2z ∂x1 x2
= 2.2 − (−3)2 = −5 < 0 (terbukti memaksimalkan )
Contoh Soal 2: Min Z = 2x1 x2 + x1 2 + 2x2 2 − 4x1 , dengan arah konjugasi dimulai dari titik (0,0) dengan toleransi kesalahan 0,01! Jawab : • Ambil x¯ = (0, 0), dengan toleransi kesalahan ε = 0,01 • Dibentuk suatu matriks H (Hessian) "
2 2 2 4
H=
#
• Dimana arah pencariannya : "
1 0
d1 =
#
"
; d2 =
a b
#
• dengan d2 = d1 T .H.d2 h
i
"
1 0 .
2 2 2 4
# "
2a + 2b = 0 2a = −2b a = −b • Misal ambil a = −1 maka nilai b = 1 • Dicari λ1 dengan = Min Z(x1 + λ1 d1 ) = Min Z (0,0) + λ1 (1,0) = Min Z (0,0) + (λ1 , 0) = Min Z (λ1 , 0) 9
.
a b
#
• Dengan Z (λ1 , 0) maka = 2(λ1 ).(0) + (λ1 )2 + 0 −4(λ1 ) = (λ1 )2 − 4(λ1 ) • λ1 dicari dengan
dz dλ1
= 2λ1 − 4 = 0 ⇔ λ1 = 2
ITERASI 2 • x2 x2 x2 x2
= (x1 + λ1 d1 ) = (0,0) + 2 (1,0) = (0,0) +(2,0) = (2,0)
• kita cek x2 = (2, 0) ⇔k xk − xq k−1 k < ε √ dengan = k (2, 0) − (0, 0) k = (2)2 + (0)2 = 4 = 2 > ε • Dicari λ2 dengan = Min Z(x2 + λ2 d2 ) = Min Z (2,0) + λ2 (-1;1) = Min Z (2,0) + (−λ2 , λ2 ) = Min Z (2 − λ2 ; λ2 ) • Dengan Z (2 − λ2 ; λ2 ) = 2(2 − λ2 )(λ2 ) + (2 − λ2 )2 + 2(λ2 )2 - 4(2 − λ2 ) = (4 − 2λ2 )(λ2 ) + 4 − 4λ2 + (λ2 )2 + (2λ2 )2 − 8 + 4λ2 = 4λ2 − 2(λ2 )2 + 4 − 4λ2 + (λ2 )2 + 2(λ2 )2 − 8 + 4λ2 = (λ2 )2 + 4λ2 − 4 = 0 • λ2 dicari dengan
dz dλ2
= 2λ2 + 4 = 0 ⇔ λ2 = −2
ITERASI 3 • x3 x3 x3 x3
= (x2 + λ2 d2 ) = (2,0) + -2 (-1;1) = (2,0) +(2;-2) = (4 ; -2)
• kita cek x3 = (4; −2) ⇔k xk − xk−1qk < ε √ dengan = k (4; −2) − (2, 0) k = (2)2 + (−2)2 = 8 = 2, 82 > ε(iterasi belum berhenti sebab masih lebih dari ε) • Dicari λ3 dengan = Min Z(x3 + λ3 d3 )
10
= Min Z (4 , -2) + λ3 (1,0) = Min Z (4 , -2) + (λ3 , 0) = Min Z (4 + λ3 ; −2) • Dengan Z (4 + λ3 ; −2) = 2(4 + λ3 )(−2) + (4 + λ3 )2 + 2(−2)2 - 4(4 + λ3 ) = (8 + 2λ3 )(−2) + (16 + 8λ3 + (λ3 )2 ) + 8 − 16 − 4λ3 = −16 − 4λ3 + 16 + 8λ3 + (λ3 )2 + 8 − 16 − 4λ3 = (λ3 )2 − 12 • λ3 dicari dengan
dz dλ3
= 2λ3 = 0 ⇔ λ3 = 0
ITERASI 4 • x4 x4 x4 x4
= (x3 + λ3 d3 ) = (4, -2) + 0 (1,0) = (4, -2) +(0,0) = (4, -2)
• kita cek x4 = (4, −2) ⇔k xk − xk−1qk < ε √ dengan = k (4, −2) − (4, −2) k = (0)2 + (0)2 = 0 = 0 < ε (iterasi berhenti sebab kurang dari ε) NOTE: Karena k∇Z = 4, −2k = 0 maka hal ini bisa dikatakan bahwa kesalahan perhitungan atau error adalah 0, sehingga mengakibatkan jawaban yang didapat dengan menggunakan metode numerik (arah konjugasi) adalah sama dengan solusi analitiknya
11
SOLUSI ANALITIK Contoh Soal 2 : Min Z = 2x1 x2 + x1 2 + 2x2 2 − 4x1 , dengan arah konjugasi dimulai dari titik (0,0) dengan toleransi kesalahan 0,01! Jawab •
dz dx1
= 2x2 + 2x1 − 4 ⇔ −2x1 = 2x2 − 4 = x1 =
•
d2 z dx1
=2
•
dz dx2
= 2x1 + 4x2 ⇔ 4x2 = −2(−x2 + 2)
2x2 −4 −2
= −x2 + 2
4x2 = 2x2 − 4 2x2 = −4 x2 = −2 •
d2 z dλ2
=4
Sekarang kita buktikan nilai x1 = 0, 8 dan x2 = 1, 2 benar meminimalkan fungsi Z = 2x1 x2 + x1 2 + 2x2 2 − 4x1 CEK !! ∂2z ∂2z . ∂x1 ∂x2
−
∂2z ∂x1 x2
= 2.4 − (2)2 = 4 > 0 (terbukti meminimalkan )
12
13
METODE NUMERIK ROSENBERG Mata Kuliah : Metode Numerik Dosen Pengampu : Rukmono Budi Utomo, M.Sc
Disusun Oleh : Rizka Apriyanti 6 A1 1384202080
PROGRAM STUDI PENDIDIKAN MATEMATIKA FAKULTAS KEGURUAN DAN ILMU PENDIDIKAN UNIVERSITAS MUHAMMADIYAH TANGERANG Jl. Perintis kemerdekaan I/33 Cikokol, Tangerang Tahun Ajaran 2015/2016
1
KATA PENGANTAR
Puji syukur kehadirat Allah SWT atas rahmat dan karunia yang telah diberikanNya, sehingga saya dapat menyelesaikan Makalah Metode Numerik ini dengan baik. Makalah ini saya sajikan dalam bentuk yang sederhana. Makalah ini dibuat untuk memenuhi tugas UAS mata kuliah Metode Numerik di Universitas Muhammadiyah Tangerang. Selain itu saya juga berharap makalah ini mampu memberikan kontribusi dalam menunjang pengetahuan para mahasiswa dan pihak lain pada umumnya. Saya menyadari bahwa makalah ini masih jauh dari kesempurnaan. Oleh karena itu saran dan kritik yang membangun sangat saya harapkan demi kesempurnaan di masa yang akan datang.
Tangerang, 07 Juni 2016
Rizka Apriyanti
2
DAFTAR ISI
KATA PENGANTAR ...................................................................................... 2 DAFTAR ISI .................................................................................................... 3 BAB I. PENDAHULUAN ................................................................................ 4 A. Latar Belakang ....................................................................................... 4 B. Rumusan Masalah .................................................................................. 4 C. Tujuan .................................................................................................... 4 D. Manfaat .................................................................................................. 5 BAB II. PEMBAHASAN ................................................................................. 6 A. Pengertian Metode Numerik .................................................................. 6 B. Pengertian Metode Numerik Roosenberg ............................................... 7 C. Algoritma Metode Numerik Roosenberg ................................................ 7 D. Contoh Penyelesaian Soal dengan Metode Numerik Roosenberg ........... 8 E. Contoh Pembuktian dengan Metode Analitik ........................................ 12 BAB III. PENUTUP ........................................................................................ 13 DAFTAR PUSTAKA ....................................................................................... 14
3
BAB I PENDAHULUAN
A. Latar Belakang Metode Numerik adalah teknik-teknik yang digunakan untuk memformulasikan masalah matematis agar dapat dipecahkan dengan operasi perhitungan biasa (tambah, kurang, kali dan bagi). 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). Metode numerik terbagi kepada beberapa macam metode dan salah satunnya adalah metode yang akan kita bahas dalam makalah ini yaitu Metode Numerik Roosenberg. Alasan penggunaan metode numerik ini karena tidak semua permasalahan matematis atau perhitungan matematis dapat diselesaikan dengan mudah. bahkan dalam prinsip matematika, suatu persoalan matematika yang paling pertama dilihat adalah apakah persoalan itu memiliki penyelesaian atau tidak. Jadi, jika suatu persoalan sudah sangat sulit atau tidak mungkin digunakan dengan metodematematis (analitik) maka kita dapat menggunakan metode numerik sebagai alternative penyelesaian persoalan tersebut. B. Rumusan Masalah a. Apa pengertian dari Metode Numerik ? b. Apa pengertian dari Metode Numerik Roosenberg ? c. Bagaimanakah Algoritma dari Metode Numerik Roosenberg ? d. Bagaimana Contoh Soal dan Penyelesaiannya dengan menggunakan Metode Numerik Roosenberg ? e. Bagaimanakah pembuktian dengan cara analitik ? C. Tujuan a. Untuk mengetahui Pengertian dari Metode Numerik b. Untuk mengetahui Pengertian dari Metode Numerik Roosenberg 4
c. Untuk mengetahui Algoritma dari Metode Numerik Roosenberg d. Untuk mengetahui Contoh Soal dan Penyelesaiannya dengan menggunakan Metode Numerik Roosenberg ? e. Untuk mengetahui contoh pembuktian dengan cara analitik D. Tujuan dan Manfaat Adapun tujuan dari penulisan makalah ini adalah untuk memenuhi tugas UAS mata kuliah Metode Numerik di semester 6, serta berbagi pengetahuan ke mahasiswa lainnya mengenai materi yang akan dibahas yaitu Metode Numerik Roosenberg. Manfaat yang dapat di petik dari tujuan tersebut yaitu diharapkan dapat menambah wawasan sebagai bekal menjadi seorang pendidik bagi pembaca dan khususnya untuk mahasiswa-mahasiswi Universitas Muhammadiyah Tangerang.
5
BAB II PEMBAHASAN
A. Pengertian Metode Numerik Menurut bahasa, Metode adalah cara yang sistematis untuk menyelesaikan persoalan guna mencapai tujuan yang ditentukan. Sedangkan, Numerik adalah yang berhubungan dengan angka. Jadi, Metode Numerik adalah teknik atau cara sistematis untuk menyelesaikan persoalan matematika dengan operasi angka. Metode Numerik adalah teknik-teknik yang digunakan untuk memformulasikan masalah matematis agar dapat dipecahkan dengan operasi perhitungan biasa seperti tambah, kurang, kali dan bagi. Metode artinya cara, sedangkan numerik artinya angka. Jadi, Metode Numerik secara harfiah berarti cara berhitung dengan menggunakan angka-angka. Beberapa definisi metode numerik dikemukakan oleh ahli matematika, diantaranya : Metode Numerik adalah teknik dimana masalah matematika diformulasikan sedemikian rupa sehingga dapat diselesaikan oleh pengoperasian aritmetika (Chapra dan Chanale, 1991). Menurut Susila (1994) ; Ibraheem dan Hisyam (2003) 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. 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). a. Prinsip-Prinsip Metode Numerik : • Metode Numerik merupaan pendekatan untuk mendapatkan pemecahan masalah yang dapat dipertanggung jawabkan secara analitik. • Pendekatannya merupakan analisis matematis. • Metode Numerik terdiri atas algoritma-algoritma yang dapat dihitung secara cepat dan mudah. • Karena berasal dari algoritma pendekatan, maka Metode Numerik ini akan memakai iterasi (pengulangan).
6
• Nilai kesalahan merupakan hal paling utama untuk mengetahui seberapa baik metode yang digunakan. b. Penggunaan Metode Numerik : Penggunaan metode numerik biasanya digunakan untuk menyelesaikan persoalan matematis yang penyelesaiannya sulit didapatkan dengan menggunakan metode analitik, yaitu : a. Menyelesaikan persamaan non linear b. Menyelesaikan persamaan simultan c. Menyelesaikan differensial dan integral d. Menyelesaikan persamaan differensial e. Interpolasi dan Regresi f. Masalah multivariabel untuk menentukan nilai optimal yang tak bersyarat B. Pengertian Metode Numerik Rosenberg Metode Numerik Roosenberg diusulkan oleh Rosenbrock pada tahun 1960. Ia menekan sejumlah kesamaan dengan pencarian garis dan juga mencari beberapa arah tegak lurus dalam ruang. Metode numerik Rosenberg ini merupakan salah satu metode numerik yang dapat digunakan untuk menyelesaikan masalah optimisasi, yakni menentukan nilai x¯1 = {x1 , x2 } ∈ R2 yang meminimumkan atau memaksimumkan fungsi Z = f (¯ x). Metode untuk menyelesaikan masalah optimisasi ini juga dapat menggunakan metode Aksial, Steepest Descant, Hooke and Jeeves, Arah Konjugasi atau Newton 2. Namun, tentu saja setiap metode numerik masing-masing memiliki algoritma yang berbeda dengan kecepatan tingkat efektifitas pencarian yang berbeda serta tingkat kesalahan yang berbeda pula. Dalam metode numerik Rosenberg ini kita dapat menggunakan direction 1 dan direction 2 yang sama dengan metode numerik lainnya. Akan tetapi, untuk direction ke-3 dan seterusnya kita tidak kembali ke direction 1 melainkan perlu dicari dengan menggunakan rumus d3 seperti yang akan dipaparkan pada point berikut. C. Algoritma Metode Numerik Roosenberg Algoritma Metode Numerik Roosenberg adalah sebagai berikut : 1. Ditentukan fungsi Z = f (¯ x) = f (x1 ,x2 ) dan akan dicari nilai yang memini7
mumkan atau memaksimumkan nilai Z = f (x1 ,x2 ) tersebut 2. Tentukan sebarang titik awal x¯1 = {x1 , x2 } ∈ R2 (yang mengapit nilai (x1 , x2 ) yang sebenarnya) 3. Tentukan ε > 0 suatu konstanta positif yang menunjukkan kesalahan yang ditoleransi 4. Tentukan arah pencarian direction d1 = (1, 0) dan d2 = (0, 1) 5. Menentukan λk dengan cara λk = min Z (x¯k + λk dk ) 6. Menentukan x¯k+1 dengan cara x¯k+1 = x¯k + λk dk 7. Menentukan d3 dengan rumus d2k+1 = kbbkk k , dengan bk = λk dk + λk+1 dk+1 8. Iterasi berhenti ketika k x¯k − x¯k+1 k< ε 9. Lakukan pengecekan dengan cara analitik atau dengan cara menentukan turunan pertama dari tiap variabel dan disamadengankan nol untuk memperoleh titik kritisnya D. Contoh Penyelesaian Soal dengan Metode Numerik Roosenberg Soal : Diberikan fungsi Z = f (x1 , x2 ) = x21 − 3x1 + 2x22 − 8x2 dengan ε = 0, 1 dan x¯1 = {1, 3}. Tentukan nilai x¯1 = {x1 , x2 } yang meminimumkan fungsi tersebut! Penyelesaian : Diketahui : Z = f (x1 , x2 ) = x21 − 3x1 + 2x22 − 8x2 ε = 0, 1 x¯1 = {1, 3} d1 = 1, 0 d2 = 0, 1 d3 = kbb11 k • ITERASI 1 : λ1 λ1 λ1 λ1
= = = =
min Z(¯ x1 + λ1 d1 ) min Z((1, 3) + λ1 (1, 0)) min Z((1, 3) + (λ1 ,0)) min Z (1 + λ1 ,3)
Z(x1 , x2 ) = x21 − 3x1 + 2x22 − 8x2 Z(1 + λ1 , 3) = (1 + λ1 )2 − 3(1 + λ1 ) + 2(3)2 − 8(3) Z(1 + λ1 , 3) = 12 + 2λ1 + λ21 − 3 − 3λ1 + 18 − 24 Z(1 + λ1 , 3) = λ21 − λ1 − 8
8
Z0 = 0 2λ1 − 1 = 0 2λ1 = 1 λ1 = 21 mencari x¯2 : x¯2 = x¯1 + λ1 d1 x¯2 = (1, 3) + 12 (1, 0) x¯2 = (1, 3) + ( 12 , 0) x¯2 = ( 23 , 3) Pengecekan: k x¯k − x¯k−1 k< ε k ( 32 , 3) − (1, 3) k< ε q
( 32 − 1)2 + (3 − 3)2
q
1 4
=
1 2
= 0, 5 > ε
Karena k x¯k - x¯k−1 k > ε maka iterasi dilanjutkan • ITERASI 2 : λ2 λ2 λ2 λ2
= = = =
min Z(¯ x2 + λ2 d2 ) min Z(( 32 , 3) + λ2 (0, 1)) min Z(( 23 , 3) + (0, λ2 )) min Z ( 32 , 3 + λ2 )
Z(x1 , x2 ) = x21 − 3x1 + 2x22 − 8x2 Z( 23 , 3 + λ2 ) = ( 32 )2 − 3( 32 ) + 2(3 + λ2 )2 − 8(3 + λ2 ) Z( 23 , 3 + λ2 ) = 49 − 92 + 18 + 12λ2 + 2λ22 − 24 − 8λ2 Z( 32 , 3 + λ2 ) = 2λ22 + 4λ2 − 33 4 Z0 = 0 4λ2 + 4 = 0 4λ2 = −4 λ2 = −1 mencari x¯3 : 9
x¯3 = x¯2 + λ2 d2 x¯3 = ( 32 , 3) + (−1)(0, 1) x¯3 = ( 32 , 3) + (0, −1) x¯3 = ( 32 , 2) Pengecekan: k x¯k − x¯k−1 k< ε k ( 32 , 2) − ( 23 , 3) k< ε q
( 32 − 32 )2 + (2 − 3)2 √ 1=1>ε
Karena k x¯k - x¯k−1 k > ε maka iterasi dilanjutkan • ITERASI 3 : mencari d3 : d3 =
b1 kb1 k
menentukan b1 : b1 = λ1 d1 + λ2 d2 b1 = 12 (1, 0) + (−1)(0, 1) b1 = ( 21 , 0) + (0, −1) b1 = ( 21 , −1) menentukan √ k b1 k : k b1 k = qa2 + b2 2 k b1 k = 12 + −12 k b1 k =
q
k b1 k =
5 √4 5 2
k b1 k =
1
q4
Maka, d3 =
+1
b1 kb1 k
=
( 21 ,−1) √ 5 2
=( 12 x √25 , −1x √25 ) = ( √15 , − √25 )
λ3 = min Z(¯ x3 + λ3 d3 ) λ2 = min Z(( 32 , 2) + λ2 ( √15 , − √25 ) λ2 = min Z(( 23 , 2) + ( √15 λ3 , − √25 λ3 )) 10
λ2 = min Z ( 32 +
√1 λ3 , 2 5
−
√2 λ3 ) 5
Z(x1 , x2 ) = x21 − 3x1 + 2x22 − 8x2 Z( 23 + √15 λ3 , 2− √25 λ3 ) = ( 23 + √15 λ3 )2 −3( 32 + √15 λ3 )+2(2− √25 λ3 )2 −8(2− √25 λ3 ) Z( 32 + √15 λ3 , 2 − √25 λ3 ) = √
16 + 165 5 λ3 Z( 23 + √15 λ3 , 2 −
√2 λ3 ) 5
9 4
√
√
√
+ 3 5 5 λ3 + 15 λ23 − 92 − 3 5 5 λ3 + 8 − 165 5 λ3 + 85 λ23 −
= 59 λ23 −
41 4
Z0 = 0 18 λ =0 5 3 λ3 = 0 mencari x¯4 : x¯4 = x¯3 + λ3 d3 x¯4 = ( 32 , 2) + (0)( √15 , − √25 ) x¯4 = ( 32 , 2) Pengecekan: k x¯k − x¯k−1 k< ε k ( 32 , 2) − ( 23 , 2) k< ε q
( 32 − 32 )2 + (2 − 2)2 √ 0=0<ε
Karena k x¯k - x¯k−1 k < ε maka iterasi berhenti • TABEL ITERASI : Dari perhitungan diatas, maka diperoleh tabel iterasi sebagai berikut : Iterasi I II III
x¯k dj 1,3 1,0 ( 32 , 3) 0,1 ( 32 , 2) ( √15 , − √25 )
λj 1 2
-1 0
x¯j+1 k x¯k − x¯k−1 k< ε ( 32 , 3) 0, 5 > ε 3 ( 2 , 2) 1>ε ( 33 , 2) 0<ε
Jadi diperoleh nilai x¯1 = {x1 , x2 } yang meminimumkan fungsi tersebut adalah x¯ = ( 23 , 2)
11
E. Contoh Pembuktian dengan Metode Analitik Soal : Diberikan fungsi Z = f (x1 , x2 ) = x21 − 3x1 + 2x22 − 8x2 dengan ε = 0, 1 dan x¯1 = {1, 3}. Tentukan nilai x¯1 = {x1 , x2 } yang meminimumkan fungsi tersebut! Penyelesaian : Z = f (x1 , x2 ) = x21 − 3x1 + 2x22 − 8x2 • Menentukan turunan x1 dan x2 : ∂f = 2x1 - 3 ∂x1 ∂f = 4x2 - 8 ∂x2 • Mencari titik kritisnya : ∂f =0 ∂x1 2x1 − 3 = 0 2x1 = 3 x1 = 23 ∂f ∂x2
=0 4x2 − 8 = 0 4x2 = 8 x2 = 2 • Pengecekan : ∂2f =2 ∂x2 1
∂2f = ∂x22 2 ∂ f ∂x1 ∂x2
4 =0 2
2
2
f Maka ( ∂∂xf2 ) ( ∂∂xf2 ) - ( ∂x∂1 ∂x )2 = 2(4) - 02 = 8 > 0 2 1
2
Jadi, terbukti bahwa nilai x¯ = ( 32 , 2) meminimumkan fungsi tersebut.
12
BAB III PENUTUP A. Kesimpulan Metode numerik Rosenberg dapat mengatasi berbagai kelemahan-kelemahan pada metode yang ada sebelumnya. Dapat dipahami pula bahwa pada umumnya permasalahan dalam sains dan teknologi digambarkan dalam persamaan matematika. Persamaan ini sulit diselesaikan dengan metode analitik sehingga diperlukan penyelesaian pendekatan numerik. Dengan metode numerik Rosenberg, kita dapat menyelesaikan permasalahan optimasi yang menggunakan n variabel bebas. Namun contoh dimakalah ini dibatasi hanya sampai 2 variabel. Metode numerik Rosenberg ini memiliki beberapa kesamaan dengan metodemetode numerik lainnya seperti Metode numerik Aksial, Dichotomus, Secant, Hooke and Jeeves, Steepest Descant dan Arah Konjugasi yaitu dapat digunakan untuk menyelesaikan permasalahan optimasi yang menggunakan n variabel bebas. Metode ini hampir sama dengan Metode numerik Hooke and Jeeves. Hanya saja bedanya, dalam metode ini direction ketiganya dan seterusnya memiliki rumus sendiri.
13
DAFTAR PUSTAKA
http://fkip-umt.ac.id/downloads http://viet5pusvitasarry.blogspot.ae/2012/12/definisi-prinsip-dan-pemakaian-or.html https://fairuzelsaid.wordpress.com/2010/10/13/metode-numerik-01-pengantar-metodenumerik http://dewamahardika.blogspot.ae/2012/11/pengertian-dan-prinsip-metode-numerik.html
14
METODE NUMERIK STEEPEST DESCENT 1 Juni 2016
Ujian Akhir Semester Untuk memenuhi ujian alhir semester mata kuliah metode numerik
Selvi Kusdwi Lestari (1384202138)
6A1 Pendidikan Matematika Fakultas Keguruan dan Ilmu Pendidikan Universitas Muhammadiyah Tangerang 2016 1
KATA PENGANTAR
Puji syukur kehadirat Allah SWT atas rahmat dan karunia yang telah diberikanNya, sehingga kami dapat menyelesaikan makalah dengan baik. Makalah ini dibuat untuk memenuhi tugas makalah Metode Numerik Steepest Descent di Universitas Muhammadiyah Tangerang. Selain itu kami berharap juga makalah ini mampu memberikan konstribusi dalam menunjang pengetahuan para mahasiswa/mahasiswi dan pihak lain pada umumnya.Dalam penulisan makalah ini. Penulis menyadari bahwa masih jauh dari kesempurnan. Oleh karena itu, saran dan kritik yang membangun sangat Penulis harapkan demi kesempurnaan dimasa yang akan datang.
Tangerang, 1 Juni 2016
Penulis
2
PEMBAHASAN
1
Pengertian Metode Steepest Descent
Metode Steepest Descent ini adalah metode gradien sederhana yang menggunakan vektor gradien untuk menentukan arah pencarian pada setiap iterasi. Dari arah pencarian yang telah ditetapkan tersebut maka akan ditentukan ukuran langkahnya. Metode Steepest Descent digunakan untuk mencari nila x yang minimum suatu fungsi. Metode steepest descent ini memiliki perbedaan dengan metode numerik lainnya. Perbedaan tersebut dapat dilihat dari cara menentuka arah pencarian (d). Dimana metode ini menggunakan nilai negatif dari hasil ∇f (X k ) dimana X k = (x1 , x2 ).
2
Algoritma Steepest Descent
Seperti metode-metode yang sebelumnya, dalam menentukan optimasi maka metode steepest descent juga memiliki algoritma yang harus dipenuhi. setiap metode memiliki algoritma yang berbeda, adapun algoritma dari metode numerik steepest descent adalah sebagai berikut ; • Diberikan fungsi minimum Z = f (X), dimana X ∈ R2 • Tentukanlah titik awal yaitu X k = (x1 ,x2 ), lalu tentukan nilai toleransi kesalahan ε dan ambilah k = 1, • Hitunglah turunan dari f (X),yaitu dengan persamaan ∇f (X k ) • Kemudian hitunglah || ∇f (X k ) || , jika perhitungan || ∇f (X k ) || < ε interasi dihentikan. Jika || ∇f (X k ) || > ε, maka lanjutkan kelangkah selanjutnya • Carilah arah pencarian pada titik xk dengan cara dk = -∇f (X k ). • Akan dihitung λk = min Z (X k + λk dk ) • Carilah nilai turunan dari f (λk ) dan sama dengankan nol, untuk mencari nilai λk • Hitunglah X k+1 dengan persamaan X k+1 = X k + λk dk • Iterasi dihentikan pada kondisi [[ ∇f (X k ) ]] < ε
3
3
Contoh Soal
Diberika suatu fungsi minimum f (X) = 5x1 2 +2x2 2 +2x1 x2 - 20x1 - 4x2 + 18 dengan titik awal x1 = (0,3) dan ε = 0, 1. Dengan menggunakan metode steepest descent, maka tentukanlah nilai x1 dan x2 yang membuat minimum fungsi tersebut. Penyelesaian : Diketahui fungsi f (X) = 5x1 2 +2x2 2 +2x1 x2 - 20x1 - 4x2 + 18 ∂f = 10x1 + 2x2 − 20 ∂(x1 ) ∂f = 4x2 + 2x1 − 4 ∂(x2 ) Iterasi 1 Diketahui x1 = (0,3) ∇f (X1 ) = ∇f (x1 , x2 ) ∇f (X1 ) = ∇f (0, 3) 10 (0) + 2 (3) − 20 ∇f (X1 ) = 4 (3)+ 2 (0) − 4 −14 ∇f (X1 ) = 8 Cek apakah || ∇f (X 1 ) || <, =, atau > ε q √ 2 2 [[∇f (X1 )]] = (−14) + (8) = 260 = 16, 125 > ε Tentukan arah pencarian d1 = -∇f (X 1 ) ∇f (X1 ) = (−14, 8)t ⇒ d1 = −∇f (X1 ) = (14, −8)t Dihitung λk = min f (X k + λk dk ) λ1 λ1 λ1 λ1
= min f (X1 + λ1 d1 ) = min f ((0, 3) + λ1 (14, −8)t ) = min f ((0, 3) + (14λ1 , −8λ1 )) = min f (14λ1 , 3 − 8λ1 )
Subtitusikan f (14λ1 , 3 - 8λ1 ) pada persamaan awal, sehingga menjadi ; f (λ1 ) = 5(14λ1 )2 + 2(3 − 8λ1 )2 + 2(14λ1 )(3 − 8λ1 ) − 20(14λ1 ) − 4(3 − 8λ1 ) + 18 f (λ1 ) = 980λ1 2 + 18 − 96λ1 + 128λ1 2 + 84λ1 − 224λ1 2 − 280λ1 − 12 + 32λ1 + 18 f (λ1 ) = 884λ1 2 − 260λ1 + 24
4
Carilah turunan ∇f (λ1 ), dan sama dengankan 0 agar diperoleh nilai dari λ1 df (λ1 ) =0 d(λ1 ) ⇔ 1768λ1 − 260 = 0 ⇔ 1768λ1 = 260 260 ≈ 0, 147 1768 Telah diketahui bahwa λ1 = 0,147 maka akan dicari nilai X 2 ⇔ λ1 =
X2 = X1 + λ1 d1 X2 = (0, 3) + 0, 147(14, −8)t X2 = (2, 058, 1, 824) Iterasi 2 Diketahui X 2 = (2,058 , 1,824) ∇f (X2 ) = ∇f (x1 , x2 ) ∇f (X2 ) = ∇f (2, 058, 1, 824) 10 (2, 058) + 2 (1, 824) − 20 ∇f (X2 ) = 4 (1, 824) + 2 (2, 058) − 4 4, 228 ∇f (X2 ) = 7, 412 Cek apakah || ∇f (X 2 ) || <, =, atau > ε q p 2 2 [[∇f (X2 )]] = (4, 228) + (7, 412) = 72, 813728 = 8, 533 > ε Tentukan arah pencarian d2 = -∇f (X 2 ) ∇f (X2 ) = (4, 228, 7, 412)t ⇒ d2 = −∇f (X2 ) = (−4, 228, −7, 412)t Dihitung λk = min f (X k + λk dk ) λ2 λ2 λ2 λ2
= min f (X2 + λ2 d2 ) = min f ((2, 058, 1, 824) + λ2 ((−4, 228, −7, 412))t ) = min f ((2, 058, 1, 824) + (−4, 228λ2 , −7, 412λ2 )) = min f (2, 058 − 4, 228λ2 , 1.824 − 7, 412λ2 )
Subtitusikan f (2,058-4,228λ2 , 1.824-7,412λ2 ) pada persamaan awal f (λ2 ) = 5(2, 058 − 4, 228λ2 )2 + 2(1, 824 − 7, 412λ2 )2 + 2(2, 058 − 4, 228λ2 )(1, 824 − 7, 412λ2 ) − 20(2, 058 − 4, 228λ2 ) − 4(1, 824 − 7, 412λ2 ) + 18 f (λ2 ) = 5(4, 235364 − 17, 402448λ2 + 17, 875984λ22 ) + 2(3, 326976 − 27, 038976λ2 + 54, 937744λ22 ) + 2(3, 753792 − 22, 965768λ2 + 31, 337936λ22 ) − 41, 16 + 84, 56λ2 − 7, 296 + 29, 648λ2 + 18 f (λ2 ) = 261, 93128λ2 2 − 72, 813178λ2 + 4, 882356 5
Carilah turunan ∇f (λ2 ), dan sama dengankan 0 agar diperoleh nilai dari λ2 df (λ2 ) =0 d(λ2 ) ⇔ 523, 86256λ2 − 72, 813178 = 0 ⇔ 523, 86256λ2 = 72, 813178 ⇔ λ2 =
72, 813178 ≈ 0, 139 523, 86256
Telah diketahui bahwa λ2 = 0,139 maka akan dicari nilai X 3 X3 = X2 + λ2 d2 X3 = (2, 058, 1, 824) + 0, 139(−4, 228, −7, 412)t X3 = (1, 470, 0, 794) Iterasi 3 Diketahui X 3 = (1,470 , 0,794) ∇f (X3 ) = ∇f (x1 , x2 ) ∇f (X3 ) = ∇f (1, 470, 0, 749) 10 (1, 470) + 2 (0, 749) − 20 ∇f (X3 ) = 4 (0, 749) + 2 (1, 470) − 4 −3, 712 ∇f (X3 ) = 2, 116 Cek apakah || ∇f (X 3 ) || <, =, atau > ε q p 2 2 [[∇f (X3 )]] = (−3, 712) + (2, 116) = 18, 2564 = 4, 273 > ε Tentukan arah pencarian d3 = -∇f (X 3 ) ∇f (X3 ) = (−3, 712, 2, 116)t ⇒ d3 = −∇f (X3 ) = (3, 712, −2, 116)t Dihitung λk = min f (X k + λk dk ) λ3 λ3 λ3 λ3
= min f (X3 + λ3 d3 ) = min f ((1, 470, 0, 794) + λ3 ((3, 712, −2, 116))t ) = min f ((1, 470, 0, 794) + (3, 712λ3 , −2, 116λ3 )) = min f (1, 470 + 3, 712λ3 , 0.794 − 2, 116λ3 )
Subtitusikan f (1,470 + 3,712λ3 , 0.794 - 2,116λ3 ) ke persamaan awal f (λ3 ) = 5(1, 470 + 3, 712λ3 )2 + 2(0, 794 − 2, 116λ3 )2 + 2(1, 470 + 3, 712λ3 )(0, 794 − 2, 116λ3 ) − 20(1, 470 + 3, 712λ3 ) − 4(0, 794 − 2, 116λ3 ) + 18 f (λ3 ) = 5(2, 1609 + 10, 91328λ3 + 13, 778944λ23 ) + 2(0, 630436 − 3, 360208λ3 + 4, 47745623 ) + 2(1, 16718 − 0, 163192λ3 − 7, 854592λ23 ) − 29, 4 − 74, 24λ3 − 3, 176 + 8, 464λ3 + 18 f (λ3 ) = 62, 140448λ3 2 − 18, 2564λ3 − 0, 176268 6
Carilah turunan ∇f (λ3 ), dan sama dengankan 0 agar diperoleh nilai dari λ3 df (λ3 ) =0 d(λ3 ) ⇔ 124, 280896λ3 − 18, 2564 = 0 ⇔ 124, 280896λ3 = 18, 2564 ⇔ λ3 =
18, 2564 ≈ 0, 147 124, 280896
Telah diketahui bahwa λ3 = 0,147 maka akan dicari nilai X 4 X4 = X3 + λ3 d3 X4 = (1, 470, 0, 794) + 0, 147(3, 712, −2, 116)t X4 = (2, 016, 0, 483) Iterasi 4 Diketahui X 4 = (2,016 , 0,483) ∇f (X4 ) = ∇f (x1 , x2 ) ∇f (X4 ) = ∇f (2, 016, 0, 483) 10 (2, 016) + 2 (0, 483) − 20 ∇f (X4 ) = 4 (0, 483) + 2 (2, 016) − 4 1.126 ∇f (X4 ) = 1, 964 Cek apakah || ∇f (X 4 ) || <, =, atau > ε q p 2 2 [[∇f (X4 )]] = (1, 126) + (1, 964) = 5, 125172 = 2, 264 > ε Tentukan arah pencarian d4 = -∇f (X 4 ) ∇f (X4 ) = (1, 126, 1, 964)t ⇒ d4 = −∇f (X4 ) = (−1, 126, −1, 964)t Dihitung λk = min f (X k + λk dk ) λ4 λ4 λ4 λ4
= min f (X4 + λ4 d4 ) = min f ((2, 016, 0, 483) + λ4 ((−1, 126, −1, 964))t ) = min f ((2, 016, 0, 483) + (−1, 126λ4 , −1, 964λ4 )) = min f (2, 016 − 1, 126λ4 , 0, 483 − 1, 964λ4 )
Subtitusikan f (2,016 -1,126λ4 , 0,483 - 1,964λ4 ) ke persamaan awal f (λ4 ) = 5(2, 016 − 1, 126λ4 )2 + 2(0, 483 − 1, 964λ4 )2 + 2(2, 016 − 1, 126λ4 )(0, 483 − 1, 964λ4 ) − 20(2, 016 − 1, 126λ4 ) − 4(0, 483 − 1, 964λ4 ) + 18 f (λ4 ) = 5(4, 064256 − 4, 540032λ4 + 1, 2667876λ24 ) + 2(0, 233289 − 1, 897224λ4 + 3, 85729624 ) + 2(0, 973728 − 4, 503282λ4 + 2, 211464λ24 ) − 40, 32 + 22, 52λ4 − 1, 932 + 7, 856λ4 + 18 f (λ4 ) = 18, 471458λ4 2 − 5, 125172λ4 − 1, 51668 7
Carilah turunan ∇f (λ4 ), dan sama dengankan 0 agar diperoleh nilai dari λ4 df (λ4 ) =0 d(λ4 ) ⇔ 36, 942916λ4 − 5, 125172 = 0 ⇔ 36, 942916λ4 = 5, 125172 ⇔ λ4 =
5, 125172 ≈ 0, 139 36, 942916
Telah diketahui bahwa λ4 = 0,139 maka akan dicari nilai X 5 X5 = X4 + λ4 d4 X5 = (2, 016, 0, 443) + 0, 139(−1, 126, −1, 964)t X5 = (1, 859, 0, 17) Iterasi 5 Diketahui X 5 = (1,859 , 0,17) ∇f (X5 ) = ∇f (x1 , x2 ) ∇f (X5 ) = ∇f (1, 859, 0, 17) 10 (1, 859) + 2 (0, 17) − 20 ∇f (X5 ) = 4 (0, 17) + 2 (1, 859) − 4 −0, 97 ∇f (X5 ) = 0, 398 Cek apakah || ∇f (X 5 ) || <, =, atau > ε q p 2 2 [[∇f (X5 )]] = (−0, 97) + (0, 398) = 1, 099304 = 1, 048 > ε Tentukan arah pencarian d5 = -∇f (X 5 ) ∇f (X5 ) = (−0, 97, 0, 398)t ⇒ d5 = −∇f (X5 ) = (0, 97, −0, 398)t Dihitung λk = min f (X k + λk dk ) λ5 λ5 λ5 λ5
= min f (X5 + λ5 d5 ) = min f ((1, 859, 0, 17) + λ5 ((0, 97, −0, 398))t ) = min f ((1, 859, 0, 17) + (0, 97λ5 , −0, 398λ5 )) = min f (1, 859 + 0, 97λ5 , 0, 17 − 0, 398λ5 )
Subtitusikan f (1,859 + 0,97 λ5 , 0,17 - 0,398λ5 ) ke persamaan awal f (λ5 ) = 5(1, 859 + 0, 97λ5 )2 + 2(0, 17 − 0, 398λ5 )2 + 2(1, 859 + 0, 97λ5 )(0, 17 − 0, 398λ5 ) − 20(1, 859 + 0, 97λ5 ) − 4(0, 17 − 0, 398λ5 ) + 18 f (λ5 ) = 5(3, 455881 + 3, 60646λ5 + 0, 9409λ25 ) + 2(0, 0289 − 0, 13532λ5 + 0, 15840425 ) + 2(0, 31603 − 0, 574982λ5 − 0, 38606λ25 ) − 37, 18 − 19, 4λ5 − 0, 68 + 1, 592λ5 + 18 f (λ5 ) = 4, 249188λ5 2 − 1, 196304λ5 − 78, 571295 8
Carilah turunan ∇f (λ5 ), dan sama dengankan 0 agar diperoleh nilai dari λ5 df (λ5 ) =0 d(λ5 ) ⇔ 8, 498376λ5 − 1.196304 = 0 ⇔ 8, 498376λ5 = 1.196304 ⇔ λ5 =
1.196304 ≈ 0, 141 8, 498376
Telah diketahui bahwa λ5 = 0,141 maka akan dicari nilai X 6 X6 = X5 + λ5 d5 X6 = (1, 859, 0, 17) + 0, 141(0, 97, −0, 398)t X6 = (1, 996, 0, 114) Iterasi 6 Diketahui X 6 = (1,996 , 0,114) ∇f (X6 ) = ∇f (x1 , x2 ) ∇f (X6 ) = ∇f (1, 996, 0, 114) 10 (1, 996) + 2 (0, 114) − 20 ∇f (X6 ) = 4 (0, 114) + 2 (1, 996) − 4 0, 188 ∇f (X6 ) = 0, 424 Cek apakah || ∇f (X 6 ) || <, =, atau > ε q p 2 2 [[∇f (X6 )]] = (0, 188) + (0, 424) = 0, 21512 = 0, 464 > ε Tentukan arah pencarian d6 = -∇f (X 6 ) ∇f (X6 ) = (0, 188, 0, 424)t ⇒ d6 = −∇f (X6 ) = (−0, 188, −0, 424)t Dihitung λk = min f (X k + λk dk ) λ6 λ6 λ6 λ6
= min f (X6 + λ6 d6 ) = min f ((1, 996, 0, 114) + λ6 ((−0, 188, −0, 424))t ) = min f ((1, 996, 0, 114) + (−0, 188λ6 , −0, 424λ6 )) = min f (1, 996 − 0, 188λ6 , 0, 114 − 0, 424λ6 )
Subtitusikan f (1,996 - 0,188 λ6 , 0,114 - 0,424λ6 ) ke persamaan awal f (λ6 ) = 5(1, 996 − 0, 188λ6 )2 + 2(0, 114 − 0, 424λ6 )2 + 2(1, 996 − 0, 188λ6 )(0, 114 − 0, 424λ6 ) − 20(1, 996 − 0, 188λ6 ) − 4(0, 114 − 0, 424λ6 ) + 18 f (λ6 ) = 5(3, 984016 − 0, 750496λ6 + 0, 035344λ26 ) + 2(0, 012996 − 0, 096672λ6 + 0, 17977626 ) + 2(0, 227544 − 0, 867736λ6 + 0, 079712λ26 ) − 39, 92 + 3, 76λ6 − 0, 456 + 1, 696λ6 + 18 f (λ6 ) = 0, 695696λ6 2 − 0, 225696λ6 − 1, 97484 9
Carilah turunan ∇f (λ6 ), dan sama dengankan 0 agar diperoleh nilai dari λ6 df (λ6 ) =0 d(λ6 ) ⇔ 1, 391392λ6 − 0, 225696 = 0 ⇔ 1, 391392λ6 = 0, 225696 ⇔ λ6 =
0, 225696 ≈ 0, 162 1, 391392
Telah diketahui bahwa λ6 = 0,162 maka akan dicari nilai X 7 X7 = X6 + λ6 d6 X7 = (1, 996, 0, 114) + 0, 162(−0, 188, −0, 424)t X7 = (1, 966, 0, 093) Iterasi 7 Diketahui X 7 = (1,966 , 0,093) ∇f (X7 ) = ∇f (x1 , x2 ) ∇f (X7 ) = ∇f (1, 966, 0, 093) 10 (1, 966) + 2 (0, 093) − 20 ∇f (X7 ) = 4 (0, 093) + 2 (1, 966) − 4 −0, 154 ∇f (X7 ) = 0, 304 Cek apakah || ∇f (X 7 ) || <, =, atau > ε q p 2 2 [[∇f (X7 )]] = (−0, 154) + (0, 304) = 0, 116132 = 0, 341 > ε Tentukan arah pencarian d7 = -∇f (X 7 ) ∇f (X7 ) = (−0, 154, 0, 304)t ⇒ d7 = −∇f (X7 ) = (0, 154, −0, 304)t Dihitung λk = min f (X k + λk dk ) λ7 λ7 λ7 λ7
= min f (X7 + λ7 d7 ) = min f ((1, 966, 0, 093) + λ7 ((0, 154, −0, 304))t ) = min f ((1, 966, 0, 093) + (0, 154λ7 , −0, 304λ7 )) = min f (1, 966 + 0, 154λ7 , 0, 093 − 0, 304λ7 )
Subtitusikan f (1,966 + 0,154 λ7 , 0,093 - 0,304λ7 ) ke persamaan awal f (λ7 ) = 5(1, 966 + 0, 154λ7 )2 + 2(0, 093 − 0, 304λ7 )2 + 2(1, 966 + 0, 154λ7 )(0, 093 − 0, 304λ7 ) − 20(1, 966 + 0, 154λ7 ) − 4(0, 093 − 0, 304λ7 ) + 18 f (λ7 ) = 5(3, 865156 + 0, 605528λ7 + 0, 023716λ27 ) + 2(0, 008649 − 0, 056544λ7 + 0, 09241627 ) + 2(0, 182838 − 0, 583342λ7 − 0, 046816λ27 ) − 39, 32 − 3, 08λ7 − 0, 372 + 1, 216λ7 + 18 f (λ7 ) = 0, 20978λ7 2 − 0, 116132λ7 − 1, 983246 10
Carilah turunan ∇f (λ7 ), dan sama dengankan 0 agar diperoleh nilai dari λ7 df (λ7 ) =0 d(λ7 ) ⇔ 0, 41926λ7 − 0, 116132 = 0 ⇔ 0, 41926λ7 = 0, 116132 ⇔ λ7 =
0, 116132 ≈ 0, 277 0, 41926
Telah diketahui bahwa λ7 = 0,277 maka akan dicari nilai X 8 X8 = X7 + λ7 d7 X8 = (1, 966, 0, 093) + 0, 277(0, 154, −0, 304)t X8 = (2, 009, 0, 009) Iterasi 8 Diketahui X 8 = (2,009 , 0,009) ∇f (X8 ) = ∇f (x1 , x2 ) ∇f (X8 ) = ∇f (2, 009, 0, 009) 18 (2, 009) + 4 (0, 009) − 18 ∇f (X8 ) = 8 (0, 009) + 4 (2, 009) − 4 0, 108 ∇f (X8 ) = 0, 054 Cek apakah [[ ∇f (X 8 ) ]] <, =, atau > ε q p 2 2 [[∇f (X8 )]] = (0, 108) + (0, 054) = 0, 01458 = 0, 121 > ε Tentukan arah pencarian d8 = -∇f (X 8 ) ∇f (X8 ) = (0, 108, 0, 054)t ⇒ d8 = −∇f (X8 ) = (−0, 108, −0, 054)t Dihitung λk = min f (X k + λk dk ) λ8 λ8 λ8 λ8
= min f (X8 + λ8 d8 ) = min f ((2, 009, 0, 009) + λ8 ((−0, 105, −0, 054))t ) = min f ((2, 009, 0, 009) + (−0, 105λ8 , −0, 054λ8 )) = min f (2, 009 − 0, 105λ8 , 0, 009 − 0, 054λ8 )
Subtitusikan f (2,009 - 0,105 λ7 , 0,009 - 0,054λ8 ) ke persamaan awal f (λ8 ) = 5(2, 009 − 0, 108λ8 )2 + 2(0, 009 − 0, 054λ8 )2 + 2(2, 009 − 0, 108λ8 )(0, 009 − 0, 054λ8 ) − 20(2, 009 − 0, 108λ8 ) − 4(0, 009 − 0, 054λ8 ) + 18 f (λ8 ) = 5(4, 036081 − 0, 433944λ8 + 0, 011664λ28 ) + 2(0, 000081 − 0, 000972λ8 + 0, 00291628 ) + 2(0, 018081 − 0, 109458λ8 + 0, 005832λ28 ) − 40, 18 + 2, 16λ8 − 0, 036 + 0, 216λ8 + 18 f (λ8 ) = 0, 075816λ8 2 − 0, 01458λ8 − 1, 999271 11
Carilah turunan ∇f (λ7 ), dan sama dengankan 0 agar diperoleh nilai dari λ7 df (λ8 ) =0 d(λ8 ) ⇔ 0, 151632λ8 − 0, 01458 = 0 ⇔ 0, 151632λ8 = 0, 01458 ⇔ λ8 =
0, 01458 ≈ 0, 096 0, 151632
Telah diketahui bahwa λ8 = 0,096 maka akan dicari nilai X 9 X9 = X8 + λ8 d8 X9 = (2, 009, 0, 009) + 0, 096(−0, 108, −0, 054)t X9 = (1, 999, 0, 004) Iterasi 9 Diketahui X 9 = (1,999 , 0,004) ∇f (X9 ) = ∇f (x1 , x2 ) ∇f (X9 ) = ∇f (1, 999, 0, 004) 18 (1, 999) + 4 (0, 004) − 18 ∇f (X9 ) = 8 (0, 004) + 4 (1, 999) − 4 −0, 002 ∇f (X9 ) = 0, 014 Cek apakah [[ ∇f (X 8 ) ]] <, =, atau > ε q p 2 2 [[∇f (X9 )]] = (−0, 002) + (0, 014) = 0, 0002 = 0, 014 > ε Terlihat Bahwa || ∇f (X 9 ) ]] = 0,014 < ε = 0, 1 sehingga, iterasi berhenti. Dengan konsep algoritma steepest descent yang telah dijelaskan di atas, maka perhitungan disajikan dalam tabel di bawah ini ; Iterasi 1 2 3 4 5 6 7 8
xk (0,3) (2,058, 1,824) (1,470 , 0,794) (2,016 , 0.483) (1,859 , 0,17) (1,996 , 0,114) (1,966 , 0,093) (2,009 , 0,009)
∇f (xk ) (-14, 8) (4,228 , 7,412) (-3,712 , 2,116) (1,126 , 1,964) (-0,97 , 0,398) (0,188 , 0,424) (-0,154 , 0,304) (0,108 , 0,054)
||∇f (xk )|| 16,125 8,533 4,273 2,264 1,048 0,464 0,341 0,121
dk (14, - 8) (-4,228 , -7,412) (3,712 , -2,116) (-1,126 , -1,964) (0,97 , -0,398) (-0,188 , -0,424) (0,154 , -0,304) ...
λk 0,147 0,0,139 0,147 0,139 0,141 0,162 0,277 ...
Berdasarkan perhitungan pada tabel, nilai hampiran (x1 , x2 ) yang akan membuat minimal fungsi f (x1 , x2 ) , adalah ∗ [1,999 , 0,004] 12
xk+1 (2,058 , 1,824) (1,470 , 0,794) (2,016 , 0.483) (1,859 , 0,17) (1,996 , 0,114) (1,966 , 0,093) (2,009 , 0,009) ...
4
Metode Analitik
diketahui bahwa dierikan suatu fungsi minimum f (X) = 5x1 2 +2x2 2 +2x1 x2 20x1 - 4x2 + 18 maka cara menentukan nilai x1 dan x2 dengan cara analitik adalah sebagai berikut : carilah turunan dari fungsi f (X) terhadap x1 : ∂f = 10x1 + 2x2 − 20 ∂(x1 ) Hasil dari turunan pertama fungsi terhadap x1 sama dengankan 0 agar memperoleh persamaan baru ∂f =0 ∂(x1 ) ⇔ 10x1 + 2x2 − 20 = 0 ⇔ 2x2 = −10x1 + 20 ⇔ x2 = −5x1 + 10 .....(persamaan1) carilah turunan dari fungsi f (X) terhadap x2 : ∂f = 4x2 + 2x1 − 4 ∂(x2 ) Subtitusikan persamaan 1 ke hasil dari turunan pertama fungsi terhadap x2 dan sama dengankan 0 agar memperoleh nilai x1 ∂f =0 ∂(x1 ) ⇔ 4x2 + 2x1 − 4 = 0 ⇔ 4(−5x1 + 10) + 2x1 − 4 = 0 ⇔ −20x1 + 40 + 2x1 − 4 = 0 ⇔ −18x1 + 36 = 0 ⇔ −18x1 = −36 ⇔ x1 = 2 Telah didapatkan nilai dari x1 adalah 2, maka subtitusikan x1 =2 ke persamaan x2 = -5x1 + 10 , maka akan didapatkan nilai x2 , yaitu : ⇔ x2 = −5x1 + 10 ⇔ x2 = −5(2) + 10 ⇔ x2 = 0
13
Telah diketahui bahwa x1 =2 dan x2 =0 . Sekarang akan dibuktikan mahwa nilai x1 =2 dan x2 =0 adalah pembuat minilal fungsi f (X) = 5x1 2 +2x2 2 +2x1 x2 - 20x1 - 4x2 + 18. ! ! 2 ∂2f ∂2f ∂2f >0 − 2 2 ∂(x1 )(x2 ) ∂(x1 ) ∂(x2 ) ⇔ (10)(4) − (2)2 > 0 ⇔ 40 − 4 > 0 ⇔ 36 > 0 Dari perhitungan di atas terbukti bahwa x1 =2 dan x2 =0 adalah pembuat miniman fungsi.
14
METODE ARAH KONJUGASI VINNA ANDIANY 1384202060 June 10, 2016
1
Metode Arah Konjugasi 1 Pengertian Metode Numerik Arah Konjugasi adalah sebuah metode yang dapat digunakan untuk menyelesaikan masalah optimisasi, yakni menentukan nilai x ¯ = x1 , x2 ε R2 . Jika dulu kita kenal program linier itu hanya penjumlahan variabel saja seperti biasa, misal x1 + x2 . Untuk program Nonlinier semisal x1 2 + x1 x2 + x2 2 , dapat diselesaikan dengan metode arah konjugasi. Masalah yang bisa diselesaikan dengan arah konjugasi adalah masalah optimisasi tanpa batas. Jadi hanya diberikan fungsi lalu dicari berapa nilai minimumnya, tidak dibatasi sedikitpun.
2 Algoritma 1. Diberikan fungsi z = f (x1 , x2 ) dan diminta menentukan x ¯ = (x1 , x2 ) yang meminimumkan fungsi z = f (x1 , x2 ) tersebut. 2. Mencari solusi dengan cara analitik sebagai acuan untuk solusi numerik, yakni dapat dilakukan dengan menghitung turunan dari x1 dan x2 , lalu mencari titik kritisnya dengan menyamadengankan turunan dari x1 dan x2 dengan 0. 3. Mengecek nilai x ¯ tersebut apakah benar meminimalkan fungsi z = f (x1 , x2 ), jika: (∂ 2 f /∂x1 2 )(∂ 2 f /∂x2 2 ) − (∂ 2 f /∂x1 x2 )> (0) maka nilai x ¯ benar meminimalkan fungsi z = f (x1 , x2 ) 4. Mencari solusi dengan Arah Konjugasi, yang pertama adalah dengan mengambil sembarang titik awal x ¯1 = (−1/2, 1) ε R2 5. Lalu, membentuk matriks Hessian 6. Setelah itu, tentukan arah pencarian (direction) dengan rumus : d = kxk+1 − xk k < 0 7. Ambil sembarang nilai a sehingga dapat menentukan nilai b , maka nilai b2 pun akan diperoleh x + λk dk ) 8. Memulai iterasi pertama dengan mencari nilai λk dengan rumus : λk = min → z(¯ Lalu, mencari nilai fungsi dengan memasukkan nilai x1 dan x2 yang didapat dari penyelesaian rumus sebelumnya. Setelah menghasilkan rumus fungsi baru, fungsi tersebut diturunkan sebanyak 1 kali agar nilai λk tersebut dapat diperoleh. 9. Kemudian, mencari nilai xk+1 dengan rumus : xk+1 =xk +λk dk
2
10. Lalu, mengecek jarakeuclid dengan menggunakan rumus : d=k(xk+1 − xk )k 11. Lanjutkan iterasi berikutnya dengan langkah yang sama
3 Contoh Soal dan Pembahasan Metode Arah Konjugasi Contoh soal: Diberikan sebuah fungsi z = f (¯ x) = −30x2 + 2x1 2 + 2x2 2 − x1 x2 , tentukan nilai x ¯ = (x1 , x2 ) yang meminimumkan fungsi z tersebut dengan nilai ε = 0, 01! Pembahasan: Terlebih dahulu kita akan menentukan nilai sebenarnya dengan metode analitik, kemudian dilanjutkan dengan metode Arah Konjugasi. Menentukan Nilai Asli menggunakan Metode Analitik • Mencari turunan x1 dan x2 untuk mendapatkan titik kritis (∂ 2 f /∂x1 2 )=4x1 -x2 ........(1) (∂ 2 f /∂x2 2 )=−30+4x2 -x1 ........(2)
persamaan 1 4x1 -x2 =0 4x1 =x2 ...........(3)
Substitusikan persamaan 3 ke persamaan 2 −30+4x2 -x1 =0........(2) −30+4(4x1 )-x1 =0 −30-15x1 =0 x1 =2 x2 =4x1 x2 =4(2) x2 =8
3
Jadi x ¯ = (2, 8) • Mengecek nilai x ¯
δ=
∂2f ∂x1 2
!
∂2f ∂x2 2
!
−
∂ ∂2f = 2 ∂x1 ∂x1
∂2f ∂ = 2 ∂x2 ∂x2
∂2f ∂ = ∂x1 ∂x2 ∂x1
∂2f ∂ = ∂x2 ∂x1 ∂x2
∂2z ∂x1 x2
∂f ∂x1
∂f ∂x2
=4
=4
∂f ∂x2
∂f ∂x1
= −1
= −1
!2
δ = (4)(4) − (−1)2 δ = 15 karena nilai δ > 0, maka (2, 8) meminimumkan fungsi f . Menentukan Nilai Asli dengan Metode Numerik Arah Konjugasi • H=
4; −1 −1; 4
!
• Direction d1 =
1 0
!
d2 =
a b
!
• Definisikan d2 sebagai : d2 =dT1 Hd2 dengan d2 =0 0=
1 0
!
4; −1 −1; 4
!
a b
!
4
0=
4 −1
!
a b
!
4a=b misal : a=1, b=4 jadi, d2 =
1 4
!
• Ambil sembarang nilai awal x ¯ = ( −1 2 , 1) • Iterasi I Selanjutnya mencari nilai λ1 dengan cara, λ1 = M in → f (x¯1 + λ1 d1 )
λ1 = M in → f ( −1 2 , 0) + λ1 (1, 0)
λ1 = M in → f ( −1 2 , 0) + (λ1 , 0)
f ( −1 2 + λ1 ), 0
Dengan, −1 −1 2 f ( −1 2 + λ1 ), 0 = −30(0) + 2( 2 + λ1 ) + 2(0) − ( 2 + λ1 )(0)
1 2 f ( −1 2 + λ1 ), 0 = 2( 4 + λ1 + (λ1 ) )
f ( −1 2 + λ1 ), 0 =
1 2
+ 2λ1 + 2(λ1 )2 )
Untuk mendapatkan nilai λ1 , hasil dari fungsi di atas diturunkan sebanyak 1 kali dan disamadengankan dengan 0 2+4λ1 =0 4λ1 =-2 λ1 = −1 2 Mencari nilai x2 x2 =x1 +λ1 d1 x2 =( −1 2 , 1) + (−2)(1, 0) x2 =( −1 2 , 1) + (−2, 0) −5 x2 =( 2 , 1)
5
Menghitung nilai d −1 2 2 d=k(x2 − x1 )k=k( −5 2 , 1) − ( 2 , 1)k= (−2) + 0 =2
p
iterasi berlanjut karena 2 > 0.01 • Iterasi II mencari nilai λ2 dengan cara, λ2 = M in → f (x¯2 + λ2 d2 )
λ2 = M in → f ( −5 2 , 1) + λ2 (1, 4)
λ2 = M in → f ( −5 2 , 1) + (λ2 , 4λ2 )
f ( −5 2 + (λ2 ), (1 + 4λ2 )
Dengan, −5 2 2 f ( −5 + (λ ), (1 + 4λ ) = −30(1 + 4λ2 ) + 2( −5 2 2 2 2 + λ2 ) + 2(1 + 4λ2 ) − ( 2 + λ2)(1 + 4λ2 ) 2 2 f ( −5 + (λ ), (1 + 4λ ) = −30−120λ2 +2( 25 2 2 2 4 −5λ2 +(λ2 ) )+2(1+8λ2 +16(λ2 ) )− 2 ( −5 2 − 20λ2 + λ2 + 4(λ2 ) )
2 f ( −5 2 + (λ2 ), (1 + 4λ2 ) = 30(λ2 ) − 95λ2 − 13
Untuk mendapatkan nilai λ2 , hasil dari fungsi di atas diturunkan sebanyak 1 kali dan disamadengankan dengan 0 60λ2 − 95 = 0 60λ2 = 95 λ2 = 1.58 Mencari nilai x3 x3 =x2 +λ2 d2 −1 x3 =( −5 2 , 1) + ( 2 )(1, 4) −1 x3 =( −5 2 , 1) + ( 2 , −2) x3 =(−3, −1) Menghitung nilai d
6
q
−1 2 2 d=k(x3 − x2 )k=k(−3, −1) − ( −5 2 , 1)k= ( 2 ) + (−2) =2.06
iterasi berlanjut karena 2.06 > 0.01 • Iterasi 7 mencari nilai λ7 dengan cara, λ7 = M in → f (x¯7 + λ7 d7 )
dengan f (x1 , x2 ) = 15(λ7 )2 − 12 Untuk mendapatkan nilai λ7 , hasil dari fungsi di atas diturunkan sebanyak 1 kali dan disamadengankan dengan 0 30λ7 = 0 λ7 = 0 Mencari nilai x8 x8 =x7 +λ7 d7 x8 =(2, 8) + (2, 8)(0) x8 =(2, 8) Menghitung nilai d p
d=k(x8 − x7 )k=k(2, 8) − (2, 8)k= (0)2 + (0)2 =0 ITERASI DISTOP pada nilai x8 = (2, 8) karena 0 < 0.01 Jadi, solusi numerik sama dengan solusi analitik yaitu x ¯ = (2, 8)
7
