Algoritma Gauss-Newton | Wiki eduNitas, Kumpulan Tulisan Umum

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

Diberikan m fungsi f₁, ..., f_m of n parameters p₁, ..., p_n with m≥n, kita ingin meminimumkan jumlah

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

Disini, p adalah vektor kolom (p₁, ..., p_n)^T.

The algorithm

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

Berikutnya penduga p^k untuk parameter vektor yang kemudian dihasilkan oleh perulangan hubungan

$p^{k+1} = p^k - Big(J_f(p^k)^op J_f(p^k)Big)^{-1} J_f(p^k)^op f(p^k),$

dimana f=(f₁, ..., f_m)^T dan J_f(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)^op J_f(p^k) , delta^k = -J_f(p^k)^op f(p^k),$ .

Line search

Sebuah implementasi yang baik dari algoritma Gauss-Newton juga menggunakan algoritma line search: sebagai pengganti dari formula sebelumnya untuk p^k+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

Hubungan perulangan metode Newton untuk meminimumkan sebuah fungsi S adalah

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

dimana $abla 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)^op f(p)$

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

Dalam kasus ini, gradien diberikan oleh

$abla S(p) = 2 J_f(p)^op f(p)$

dimana $J_f$ adalah Jacobian dari $f$ , dan Hessian diberikan oleh

$H_S(p) = 2 J_f(p)^op 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)^op 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)^op J_f(p^k) ight)^{-1} J_f(p^k)^op f(p^k).$

Algoritma lainnya

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

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 (2nd ed ed.). New York: Springer. ISBN 0387954104.

Sumber :
ensiklopedia.web.id, wiki.program-reguler.co.id, id.wikipedia.org, dsb.