Metode Numerik Arah Konjugasi

Metode Numerik Arah Konjugasi Algoritma Arah Konjugasi Contoh Penyelesaian Masalah Optimisasi dengan Arah Konjugasi Penyelesaian Dengan Analitik Biografi Author

Metode Numerik Arah Konjugasi Rukmono Budi Utomo, M.Sc. Prodi S1 Pendikan Matematika UMT email: [email protected]

May 2, 2016

Rukmono Budi Utomo, M.Sc. Prodi S1 Pendikan Matematika UMT Metode email:Numerik [email protected] Arah Konjugasi


Metode Numerik Arah Konjugasi

1

Metode Numerik Arah Konjugasi

2

Algoritma Arah Konjugasi

3

Contoh Penyelesaian Masalah Optimisasi dengan Arah Konjugasi

4

Penyelesaian Dengan Analitik

5

Biografi Author



Metode Numerik Arah Konjugasi Metode Numerik Arah Konjugasi merupakan salah satu metode numerik yang dapat digunakan untuk menyelesaikan masalah optimisasi, yakni menentukan nilai X = {x1 , x2 } ∈ R 2 yang meminimalkan atau memaksimalkan Z = F (X )



Metode Numerik Arah Konjugasi Metode Numerik Arah Konjugasi merupakan salah satu metode numerik yang dapat digunakan untuk menyelesaikan masalah optimisasi, yakni menentukan nilai X = {x1 , x2 } ∈ R 2 yang meminimalkan atau memaksimalkan Z = F (X ) Metode untuk menyelesaikan masalah optimisasi ini juga dapat menggunakan metode aksial , Stepest Descent, Hooke and Jeeve atau Roosenberg



Metode Numerik Arah Konjugasi Metode Numerik Arah Konjugasi merupakan salah satu metode numerik yang dapat digunakan untuk menyelesaikan masalah optimisasi, yakni menentukan nilai X = {x1 , x2 } ∈ R 2 yang meminimalkan atau memaksimalkan Z = F (X ) Metode untuk menyelesaikan masalah optimisasi ini juga dapat menggunakan metode aksial , Stepest Descent, Hooke and Jeeve atau Roosenberg Tentu saja setiap metode numerik memilki algoritma yang berbeda dengan kecepatan tingkat efektivitas pencarian O (Big Oh)yang berbeda serta tingkat kesalahan yang berbeda pula Rukmono Budi Utomo, M.Sc. Prodi S1 Pendikan Matematika UMT Metode email:Numerik [email protected] Arah Konjugasi


Algoritma Arah Konjugasi Algoritma Arah Konjugasi dapat dijelaskan sebagai berikut: Diberikan fungsi Z = F (x1 , x2 ) dan akan ditentukan nilai X = {x1 .x2 } yang meminimalkan atau memaksimumkan nilai Z = F (x1 , x2 ) tersebut



Algoritma Arah Konjugasi Algoritma Arah Konjugasi dapat dijelaskan sebagai berikut: Diberikan fungsi Z = F (x1 , x2 ) dan akan ditentukan nilai X = {x1 .x2 } yang meminimalkan atau memaksimumkan nilai Z = F (x1 , x2 ) tersebut Ambil sembarang titik awal X1 = {x1 , x2 } ∈ R 2



Algoritma Arah Konjugasi Algoritma Arah Konjugasi dapat dijelaskan sebagai berikut: Diberikan fungsi Z = F (x1 , x2 ) dan akan ditentukan nilai X = {x1 .x2 } yang meminimalkan atau memaksimumkan nilai Z = F (x1 , x2 ) tersebut Ambil sembarang titik awal X1 = {x1 , x2 } ∈ R 2 Bentuk Metrik Hessian yakni # " H=

∂Z ∂x1 2 ∂Z ∂x2 ∂x1

∂Z ∂x1 ∂x2 ∂Z ∂x2 2



Algoritma Arah Konjugasi Algoritma Arah Konjugasi dapat dijelaskan sebagai berikut: Diberikan fungsi Z = F (x1 , x2 ) dan akan ditentukan nilai X = {x1 .x2 } yang meminimalkan atau memaksimumkan nilai Z = F (x1 , x2 ) tersebut Ambil sembarang titik awal X1 = {x1 , x2 } ∈ R 2 Bentuk Metrik Hessian yakni # " H=

∂Z ∂x1 2 ∂Z ∂x2 ∂x1

∂Z ∂x1 ∂x2 ∂Z ∂x2 2

Tetapkan arah pencarian 1 a d1 = , d2 = 0 b Rukmono Budi Utomo, M.Sc. Prodi S1 Pendikan Matematika UMT Metode email:Numerik [email protected] Arah Konjugasi


lanjutan dengan d2 = d1t Hd2 dan sama denankan nol, serta bentuk dk+1 = dkt Hdk+1



lanjutan dengan d2 = d1t Hd2 dan sama denankan nol, serta bentuk dk+1 = dkt Hdk+1 tentukan λk = minZ (Xk + λk dk ) dan Xk+1 = Xk + λk dk



lanjutan dengan d2 = d1t Hd2 dan sama denankan nol, serta bentuk dk+1 = dkt Hdk+1 tentukan λk = minZ (Xk + λk dk ) dan Xk+1 = Xk + λk dk Iterasi berhenti ketika norm ||Xk+1 − xk || < dengan > 0 merupakan suatu konstanta positif yang menunjukkan kesalahan yang ditolerasnsi



Contoh Penggunaan Arah Konjugasi Tentukan nilai X = {x1 , x2 } yang meminimalkan Z (x1 , x2 ) = −12x2 + 4x12 + 4x22 − 4x1 x2 dengan menggunakan metode Arah Konjugasi



Contoh Penggunaan Arah Konjugasi Tentukan nilai X = {x1 , x2 } yang meminimalkan Z (x1 , x2 ) = −12x2 + 4x12 + 4x22 − 4x1 x2 dengan menggunakan metode Arah Konjugasi solusi Ambil sembarang titik awal X1 = {− 12 , 1} ∈ R 2



Contoh Penggunaan Arah Konjugasi Tentukan nilai X = {x1 , x2 } yang meminimalkan Z (x1 , x2 ) = −12x2 + 4x12 + 4x22 − 4x1 x2 dengan menggunakan metode Arah Konjugasi solusi Ambil sembarang titik awal X1 = {− 12 , 1} ∈ R 2 Dibentuk metriks Hessian " H=

∂Z ∂x1 2 ∂Z ∂x2 ∂x1

∂Z ∂x1 ∂x2 ∂Z ∂x2 2

#

=

8 −4

−4 8



Contoh Penggunaan Arah Konjugasi Tentukan nilai X = {x1 , x2 } yang meminimalkan Z (x1 , x2 ) = −12x2 + 4x12 + 4x22 − 4x1 x2 dengan menggunakan metode Arah Konjugasi solusi Ambil sembarang titik awal X1 = {− 12 , 1} ∈ R 2 Dibentuk metriks Hessian " H=

∂Z ∂x1 2 ∂Z ∂x2 ∂x1

∂Z ∂x1 ∂x2 ∂Z ∂x2 2

#

=

8 −4

−4 8

arah pencarian d1 dan d2 dengan Rukmono Budi Utomo, M.Sc. Prodi S1 Pendikan Matematika UMT Metode email:Numerik [email protected] Arah Konjugasi


lanjutan

1 d1 = 0 d2 = d1 t Hd2 8 −4 a 0= 1 0 −4 8 b 0 = 8a − 4b ⇔ 2a = b ambil a = 1, b = 2, dengan demikian diperoleh 1 d2 = 2



lanjutan Nilai λ1 dapat ditentukan sebagai berikut λ1 = min Z X1 + λ1 d1 = Z 12 , 1 + λ1 (1,0) = Z − 21 + λ1 , 1 dengan Z

1 + λ1 , 1 = 4λ1 2 − 8λ1 − 5 2



lanjutan Nilai λ1 dapat ditentukan sebagai berikut λ1 = min Z X1 + λ1 d1 = Z 12 , 1 + λ1 (1,0) = Z − 21 + λ1 , 1 dengan Z

1 + λ1 , 1 = 4λ1 2 − 8λ1 − 5 2

Derivatifkan Z ( 12 , 1) dan sama dengankan nol, sehingga diperoleh λ1 = 1. Berdasarkan hal tersebut X2 = X1 + λ1 d1 = 12 , 1 Rukmono Budi Utomo, M.Sc. Prodi S1 Pendikan Matematika UMT Metode email:Numerik [email protected] Arah Konjugasi


kanjutan Karena ||X2 − X1 || = 1 > 0.01 = , maka iterasi dilanjutkan Dengan langkah yang sama, diperoleh λ2 = 12 dan X3 = (1, 2). Berdasarkan hal tersebut ||X3 − X2 || => 0.01 = ., dengan demikian iterasi dilanjutkan



kanjutan Karena ||X2 − X1 || = 1 > 0.01 = , maka iterasi dilanjutkan Dengan langkah yang sama, diperoleh λ2 = 12 dan X3 = (1, 2). Berdasarkan hal tersebut ||X3 − X2 || => 0.01 = ., dengan demikian iterasi dilanjutkan Apabila iterasi diteruskan akan diperoleh nilai X4 = {1, 2} dengan ||X4 − X3 || = 0 < 0.01 = , Dengan demikian iterasi berhenti, sehingga nilai X yang meminimalkan fungsi Z dalam soal ini adalah X4 = {1, 2}



kanjutan Karena ||X2 − X1 || = 1 > 0.01 = , maka iterasi dilanjutkan Dengan langkah yang sama, diperoleh λ2 = 12 dan X3 = (1, 2). Berdasarkan hal tersebut ||X3 − X2 || => 0.01 = ., dengan demikian iterasi dilanjutkan Apabila iterasi diteruskan akan diperoleh nilai X4 = {1, 2} dengan ||X4 − X3 || = 0 < 0.01 = , Dengan demikian iterasi berhenti, sehingga nilai X yang meminimalkan fungsi Z dalam soal ini adalah X4 = {1, 2} Catatan Perlu diperhatikan bahwa, karena ||∇Z ( 43 , 12 )|| = 0 hal ini mengindikasikan kesalahan perhitungan numerik eror = 0 yang mengindikasikan bahwa solusi numerik juga merupakan solusi analitiknya. Rukmono Budi Utomo, M.Sc. Prodi S1 Pendikan Matematika UMT Metode email:Numerik [email protected] Arah Konjugasi


Penyelesaian Dengan Analitik Diketahu Z (x1 , x2 ) = −12x2 + 4x12 + 4x22 − 4x1 x2 dan akan ditentukan nilai X = {x1 , x2 } yang meminimumkan fungsi Z = F (x1 , x2 ) tersebut



Penyelesaian Dengan Analitik Diketahu Z (x1 , x2 ) = −12x2 + 4x12 + 4x22 − 4x1 x2 dan akan ditentukan nilai X = {x1 , x2 } yang meminimumkan fungsi Z = F (x1 , x2 ) tersebut Solusi

∂Z ∂Z = 8x1 − 4x2 ; = −12 + 8x2 − 4x1 ∂x1 ∂x2




∂Z ∂Z = 8x1 − 4x2 ; = −12 + 8x2 − 4x1 ∂x1 ∂x2

Karena ∂Z X1 = 0 dan juga kerena dan x2 = 2

∂Z X2

= 0, maka diperoleh x1 = 1




∂Z ∂Z = 8x1 − 4x2 ; = −12 + 8x2 − 4x1 ∂x1 ∂x2

Karena ∂Z X1 = 0 dan juga kerena dan x2 = 2 lebih lanjut

∂Z X2


∂2Z ∂2Z = 4; =2 ∂x1 2 ∂x2 2 Rukmono Budi Utomo, M.Sc. Prodi S1 Pendikan Matematika UMT Metode email:Numerik [email protected] Arah Konjugasi



∂Z ∂Z = 8x1 − 4x2 ; = −12 + 8x2 − 4x1 ∂x1 ∂x2

Karena ∂Z X1 = 0 dan juga kerena dan x2 = 2 lebih lanjut

∂Z X2


∂2Z ∂2Z = 4; =2 ∂x1 2 ∂x2 2 Rukmono Budi Utomo, M.Sc. Prodi S1 Pendikan Matematika UMT Metode email:Numerik [email protected] Arah Konjugasi


lanjutan 2 karena ∂∂xZ2 = 8 > 0 dan 1

∂2Z ∂2Z ( ) ∂x12 ∂x12

2

Z 2 ) = 48 > 0, maka − ( ∂x∂1 ∂x 2

terbukti bahwa titik {1, 2} merupakan titik yang meminimumkan fungsi Z = {x1 , x2 } dalam soal ini.



Sekilas Tentang Penulis Rukmono Budi Utomo lahir di Tangerang, 26 September 1991 dan merupakan anak ke-2 dari 2 bersaudara. Penulis menamatkan sekolah antara lain: S1 Matematika Undip (2013) S2 Matematika UGM (2015) Saat ini penulis merupakan dosen di prodi pendidikan matematika Universitas Muhammadiyah Tangerang (UMT) sekaligus mahasiswa program Doktoral Matematika ITB. Kontak : 085741511571, email:[email protected]


Metode Numerik Arah Konjugasi

Recommend Documents