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