Lihat sumber Algoritma Gauss-Newton

{{rapikan}}
'''Algoritma Gauss-Newton''' adalah penyelesaian yang digunakan untuk memecahkan masalah-masalah kuadrat terkecil. Algoritma ini merupakan sebuah perubahan 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 adalah hasil penemuannya matematikawan yang bernama [[Carl Friedrich Gauss]].

== Permasalahan ==

Diberikan ''m'' fungsi ''f''<sub>1</sub>, ..., ''f''<sub>''m''</sub> of ''n'' parameters ''p''<sub>1</sub>, ..., ''p''<sub>''n''</sub> with ''m''≥''n'', kita ingin meminimumkan jumlah
:<math> S(p) = \sum_{i=1}^m (f_i(p))^2.</math>
Disini, ''p'' adalah vektor kolom (''p''<sub>1</sub>, ..., ''p''<sub>''n''</sub>)<sup>T</sup>.

== 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 ''p''<sup>0</sup>.

Berikutnya penduga ''p''<sup>''k''</sup> untuk parameter vektor yang kemudian dihasilkan oleh perulangan hubungan
:<math> 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), </math>
di mana ''f''=(''f''<sub>1</sub>, ..., ''f''<sub>''m''</sub>)<sup>T</sup> dan ''J''<sub>f</sub>(''p'') menunjukkan Jacobian dari ''f'' saat ''p''.

Matriks invers tidak pernah dihasilakan secara eksplisit dalam praktiknya. Sebagai pengganti, kita gunakan
:<math> p^{k+1} = p^k + \delta^k, \, </math>
Dan kita hitung perbaikan δ<sup>''k''</sup> dengan menyelesaikan sistem linear

:<math> J_f(p^k)^\top J_f(p^k) \, \delta^k = -J_f(p^k)^\top f(p^k), </math>.

== Penelusuran garis ==

Sebuah implementasi yang baik dari algoritme Gauss-Newton juga menggunakan algoritme penelusuran garis: sebagai pengganti dari formula sebelumnya untuk ''p''<sup>''k''+1</sup>, kita gunakan
:<math> p^{k+1} = p^k + \alpha^k \, \delta^k, </math>
Dimana kita berusaha memilih sebuah nilai optimal untuk bilangan α<sup>''k''</sup>.

== Derivasi dari metode Newton ==

Hubungan perulangan metode Newton untuk meminimumkan sebuah fungsi ''S'' adalah
:<math> p^{k+1} = p^k - [H_S(p^k)]^{-1} \nabla S(p^k), \, </math>
di mana <math>\nabla S</math> dan <math>H_S</math> berarti gradien dan Hessian dari ''S'' .
Sekarang kita misalkan S memiliki bentuk
:<math>S(p) = \sum_{i=1}^m (f_i(p))^2 = f(p)^\top f(p)</math>
di mana <math>f</math> adalah sebuah nilai fungsi vector yang merupakan komponen <math>f_i</math>.

Dalam kasus ini, gradien diberikan oleh
:<math>\nabla S(p) = 2 J_f(p)^\top f(p)</math>
di mana <math>J_f</math> adalah Jacobian dari <math>f</math>, dan Hessian diberikan oleh
:<math>H_S(p) = 2 J_f(p)^\top J_f(p) +  2 \sum_{i=1}^m f_i(p) \, H_{f_i}(p)</math>
di mana <math>H_{f_i}</math> adalah Hessian dari <math>f_i</math>.

Catatan bahwa syarat kedua dalam ekspresi ini untuk v <math>H_S</math> menuju nol sama <math>S(p)</math> 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:

:<math>H_S(p) = 2 J_f(p)^\top J_f(p)</math>

Dengan memasukkan ekspresi ini untuk gradeien dan Hessian kedalam hubungan perulangan sebelumnya kita memiliki
:<math> 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).</math>

== 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 dimana minimum lebih besar dari nol, pengabaian syarat atau 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 ==
* {{cite book
|last       = Nocedal
|first      = Jorge
|coauthors  = Wright, Stephen 
|title      = Numerical optimization
|url       = https://archive.org/details/numericaloptimiz0000noce
|publisher  = New York: Springer
|date       = 1999
|pages      = 
|isbn       = 0387987932
}}

* {{cite book
|last       = Deuflhard
|first      = P.
|coauthors  = Hohmann, Andreas 
|title      = Numerical analysis in modern scientific computing: an introduction
|publisher  = New York: Springer
|date       = 2003
|edition    = 2nd ed
|pages      = 
|isbn       = 0387954104
}}

[[Kategori:Optimization algorithms]]