Algoritma Gauss-Newton

Di dalam ilmu matematika, algoritme Gauss-Newton digunakan untuk memecahkan masalah-masalah kuadrat terkecil. Algoritme ini merupakan sebuah modifikasi dari metode Newton untuk mengoptimalkan sebuah fungsi. Tidak seperti metode Newton, algoritme Gauss-Newton hanya bisa digunakan untuk mengoptimumkan jumlah dari nilai fungsi kuadrat. Metode ini merupakan hasil penemuan dari matematikawan bernama Carl Friedrich Gauss.

Permasalahan 

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

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

Algoritme 

Algoritme 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

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

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

Dan kita hitung perbaikan δk dengan menyelesaikan sistem linear

.

Penelusuran garis 

Sebuah implementasi yang baik dari algoritme Gauss-Newton juga menggunakan algoritme penelusuran garis: sebagai pengganti dari formula sebelumnya untuk pk+1, kita gunakan

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

Derivasi dari metode Newton 

Hubungan perulangan metode Newton untuk meminimumkan sebuah fungsi S adalah

di mana  dan  berarti gradien dan Hessian dari S .
Sekarang kita misalkan S memiliki bentuk

di mana  adalah sebuah nilai fungsi vector yang merupakan komponen .

Dalam kasus ini, gradien diberikan oleh

di mana  adalah Jacobian dari , dan Hessian diberikan oleh

di mana  adalah Hessian dari .

Catatan bahwa syarat kedua dalam ekspresi ini untuk v  menuju nol sama  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:

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

Algoritme lainnya 

Metode lain untuk menyelesaikan masalah kuadrat terkecil hanya menggunakan derivatif pertama adalah penurunan gradien. Bagaimanapun, metode ini tidak memasukkan nilai maupun perhitungan derivatif kedua dengan perkiraan yang sama. Karenanya, metode ini tidak efisien untuk fungsi-fungsi tertentu, seperti fungsi Rosenbrock.

Pada kasus di mana minimum lebih besar dari nol, pengabaian syarat/ketentuan pada Hessian bisa jadi signifikan. Pada kasus ini, salah satunya bisa menggunakan algoritme Levenberg-Marquardt, yang merupakan kombinasi dari Gauss-Newton dan penurunan gradien.

Referensi 
 

 

Optimization algorithms