Algoritma Gauss-Newton

Artikel ini perlu dirapikan agar memenuhi standar Wikipedia. Silakan kembangkan artikel ini semampu Anda. Merapikan artikel dapat dilakukan dengan wikifikasi atau membagi artikel ke paragraf-paragraf. Jika sudah dirapikan, silakan hapus templat ini. (Pelajari cara dan kapan saatnya untuk menghapus pesan templat ini)

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.

Masalah

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

S ( p ) = ∑ i = 1 m ( f i ( p ) ) 2 . {\displaystyle S(p)=\sum _{i=1}^{m}(f_{i}(p))^{2}.} $S(p)=\sum _{i=1}^{m}(f_{i}(p))^{2}.$

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

Algoritma

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 − ( J f ( p k ) ⊤ J f ( p k ) ) − 1 J f ( p k ) ⊤ f ( p k ) , {\displaystyle 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}),} $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}),$

di mana f=(f₁, ..., f_m)^T dan J_f(p) menunjukkan Jacobian dari f saat p.

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

p k + 1 = p k + δ k , {\displaystyle p^{k+1}=p^{k}+\delta ^{k},\,} $p^{k+1}=p^{k}+\delta ^{k},\,$

Dan kita hitung perbaikan δ^k dengan menyelesaikan sistem linear

J f ( p k ) ⊤ J f ( p k ) δ k = − J f ( p k ) ⊤ f ( p k ) , {\displaystyle J_{f}(p^{k})^{\top }J_{f}(p^{k})\,\delta ^{k}=-J_{f}(p^{k})^{\top }f(p^{k}),} $J_{f}(p^{k})^{\top }J_{f}(p^{k})\,\delta ^{k}=-J_{f}(p^{k})^{\top }f(p^{k}),$ .

Penelusuran garis

Sebuah implementasi yang baik dari algoritma Gauss-Newton juga menggunakan algoritma penelusuran garis: sebagai pengganti dari formula sebelumnya untuk p^k+1, kita gunakan

p k + 1 = p k + α k δ k , {\displaystyle p^{k+1}=p^{k}+\alpha ^{k}\,\delta ^{k},} $p^{k+1}=p^{k}+\alpha ^{k}\,\delta ^{k},$

Di mana kita berusaha memilih sebuah nilai optimal untuk bilangan α^k.

Derivasi dari metode Newton

Hubungan perulangan metode Newton untuk meminimumkan sebuah fungsi S adalah

p k + 1 = p k − [ H S ( p k ) ] − 1 ∇ S ( p k ) , {\displaystyle p^{k+1}=p^{k}-[H_{S}(p^{k})]^{-1}\nabla S(p^{k}),\,} $p^{k+1}=p^{k}-[H_{S}(p^{k})]^{-1}\nabla S(p^{k}),\,$

di mana ∇ S {\displaystyle \nabla S} $\nabla S$ dan H S {\displaystyle H_{S}} $H_{S}$ berarti gradien dan Hessian dari S . Sekarang kita misalkan S memiliki bentuk

S ( p ) = ∑ i = 1 m ( f i ( p ) ) 2 = f ( p ) ⊤ f ( p ) {\displaystyle S(p)=\sum _{i=1}^{m}(f_{i}(p))^{2}=f(p)^{\top }f(p)} $S(p)=\sum _{i=1}^{m}(f_{i}(p))^{2}=f(p)^{\top }f(p)$

di mana f {\displaystyle f} $f$ adalah sebuah nilai fungsi vector yang merupakan komponen f i {\displaystyle f_{i}} $f_{i}$ .

Dalam kasus ini, gradien diberikan oleh

∇ S ( p ) = 2 J f ( p ) ⊤ f ( p ) {\displaystyle \nabla S(p)=2J_{f}(p)^{\top }f(p)} $\nabla S(p)=2J_{f}(p)^{\top }f(p)$

di mana J f {\displaystyle J_{f}} $J_{f}$ adalah Jacobian dari f {\displaystyle f} $f$ , dan Hessian diberikan oleh

H S ( p ) = 2 J f ( p ) ⊤ J f ( p ) + 2 ∑ i = 1 m f i ( p ) H f i ( p ) {\displaystyle H_{S}(p)=2J_{f}(p)^{\top }J_{f}(p)+2\sum _{i=1}^{m}f_{i}(p)\,H_{f_{i}}(p)} $H_{S}(p)=2J_{f}(p)^{\top }J_{f}(p)+2\sum _{i=1}^{m}f_{i}(p)\,H_{f_{i}}(p)$

di mana H f i {\displaystyle H_{f_{i}}} $H_{f_{i}}$ adalah Hessian dari f i {\displaystyle f_{i}} $f_{i}$ .

Catatan bahwa syarat kedua dalam ekspresi ini untuk v H S {\displaystyle H_{S}} $H_{S}$ menuju nol sama S ( p ) {\displaystyle S(p)} $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 ) ⊤ J f ( p ) {\displaystyle H_{S}(p)=2J_{f}(p)^{\top }J_{f}(p)} $H_{S}(p)=2J_{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 − ( J f ( p k ) ⊤ J f ( p k ) ) − 1 J f ( p k ) ⊤ f ( p k ) . {\displaystyle 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}).} $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

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 atau ketentuan pada Hessian bisa jadi signifikan. Pada kasus ini, salah satunya bisa menggunakan algoritma Levenberg-Marquardt, yang merupakan kombinasi dari Gauss-Newton dan penurunan gradien.

Referensi

Nocedal, Jorge (1999). Numerical optimization. New York: Springer. ISBN 0387987932.{{cite book}}: Parameter tidak dikenal |coauthors= diabaikan (|author= disarankan)Pemeliharaan CS1: Lokasi penerbit (link)

Deuflhard, P. (2003). Numerical analysis in modern scientific computing: an introduction (Edisi 2nd ed). New York: Springer. ISBN 0387954104.{{cite book}}: |edition= memiliki teks tambahan; Parameter tidak dikenal |coauthors= diabaikan (|author= disarankan)Pemeliharaan CS1: Lokasi penerbit (link)