Algoritma Gauss-Newton

Dari Wikipedia bahasa Indonesia, ensiklopedia bebas
Langsung ke: navigasi, cari

Di dalam Ilmu Matematika, algoritma Gauss-Newton digunakan untuk memecahkan masalah-masalah kuadrat terkecil. Algoritma ini merupakan sebuah modifikasi dari metode Newton untuk mengoptimalkan sebuah fungsi. Tidak seperti metode Newton, algoritma Gauss-Newton hanya bisa digunakan untuk mengoptimumkan jumlah dari nilai fungsi kuadrat.

Metode ini merupakan kemahsyuran dari matematikawan Carl Friedrich Gauss.

The problem[sunting | sunting sumber]

Diberikan m fungsi f1, ..., fm of n parameters p1, ..., pn with mn, kita ingin meminimumkan jumlah

 S(p) = \sum_{i=1}^m (f_i(p))^2.

Disini, p adalah vektor kolom (p1, ..., pn)T.

The algorithm[sunting | sunting sumber]

Algoritma Gauss-Newton merupakan prosedur iterasi. Ini berarti bahwa pengguna harus menetapkan sebuah penduga pertama untuk parameter vektor p, yang mana akan kita sebut p0.

Berikutnya penduga pk untuk parameter vektor yang kemudian dihasilkan oleh perulangan hubungan

 p^{k+1} = p^k - \Big(J_f(p^k)^\top J_f(p^k)\Big)^{-1} J_f(p^k)^\top f(p^k),

dimana f=(f1, ..., fm)T dan Jf(p) menunjukkan Jacobian dari f saat p.

Matriks invers tidak pernah dihasilakan secara eksplisit dalam prakteknya. Sebagai pengganti, kita gunakan

 p^{k+1} = p^k + \delta^k, \,

Dan kita hitung perbaikan δk dengan menyelesaikan sistem linear

 J_f(p^k)^\top J_f(p^k) \, \delta^k = -J_f(p^k)^\top f(p^k), .


Line search[sunting | sunting sumber]

Sebuah implementasi yang baik dari algoritma Gauss-Newton juga menggunakan algoritma line search: sebagai pengganti dari formula sebelumnya untuk pk+1, kita gunakan

 p^{k+1} = p^k + \alpha^k \, \delta^k,

Dimana kita berusaha memilih sebuah nilai optimal untuk bilangan αk.


Derivation from Newton's method[sunting | sunting sumber]

Hubungan perulangan metode Newton untuk meminimumkan sebuah fungsi S adalah

 p^{k+1} = p^k - [H_S(p^k)]^{-1} \nabla S(p^k), \,

dimana \nabla S dan H_S berarti gradien dan Hessian dari S . Sekarang kita misalkan S memiliki bentuk

S(p) = \sum_{i=1}^m (f_i(p))^2 = f(p)^\top f(p)

dimana f adalah sebuah nilai fungsi vector yang merupakan komponen f_i.

Dalam kasus ini, gradien diberikan oleh

\nabla S(p) = 2 J_f(p)^\top f(p)

dimana J_f adalah Jacobian dari f, dan Hessian diberikan oleh

H_S(p) = 2 J_f(p)^\top J_f(p) +  2 \sum_{i=1}^m f_i(p) \, H_{f_i}(p)

dimana H_{f_i} adalah Hessian dari f_i.

Catatan bahwa syarat kedua dalam ekspresi ini untuk v H_S menuju nol sama S(p) menuju nol. Jadi jika nilai minimum dari S(p) tertutup untuk nol, dan nilai percobaan dari p adalah tertutup untuk minimum, kemudian kita bisa mengira Hessian dengan:

H_S(p) = 2 J_f(p)^\top J_f(p)

Dengan memasukkan ekspresi ini untuk gradeien dan Hessian kedalam hubungan perulangan sebelumnya kita memiliki

 p^{k+1} = p^k - \left( J_f(p^k)^\top J_f(p^k) \right)^{-1} J_f(p^k)^\top f(p^k).

Algoritma lainnya[sunting | sunting sumber]

Metode lain untuk menyelesaikan masalah kuadrat terkecil hanya menggunakan derivative pertama adalah gradient descent. Bagaimanapun, metode ini tidak memasukkan nilai/perhitungan derivative kedua dengan perkiraan yang sama. Karenanya, metode ini terlalu in-efisien untuk fungsi-fungsi tertentu, seperti fungsi Rosenbrock.

Pada kasus dimana minimum lebih besar dari nol, pengabaian syarat/ketentuan pada Hessian bisa jadi signifikan. Pada kasus ini, salah satunya bisa menggunakan algoritma Levenberg-Marquardt, yang merupakan kombinasi dari Gauss-Newton dan gradient descent.

References[sunting | sunting sumber]

  • Nocedal, Jorge; Wright, Stephen (1999). Numerical optimization. New York: Springer. ISBN 0387987932. 
  • Deuflhard, P.; Hohmann, Andreas (2003). Numerical analysis in modern scientific computing: an introduction (ed. 2nd ed). New York: Springer. ISBN 0387954104.