最小二乘法
最小二乘法（又稱最小平方法）是一種數學優化技術。它通過最小化誤差的平方和尋找資料的最佳函數比對。利用最小二乘法可以簡便地求得未知的資料，并使得這些求得的資料與實際資料之間誤差的平方和為最小。最小二乘法還可用于曲線拟合。數學表示：
其中yi是第i個實際觀測到的值，或叫真實值或者目标值；fi(x)則可以看作是通過x這個參數預測得到的第i個值，是對yi的估計。最小二乘的目标估計未知的參數使得觀測值（真實值）和估計值之間的差距最小。
線性最小二乘
所謂線性，指f(x)是x的線性函數，f(x)=x0+t1*x1+...+tq*xq。線性最小二乘的解法相對簡單。
非線性最小二乘
所謂非線性，就是f(x)無法表示為的線性關系，而是某種非線性關系。考慮一個簡單的非線性最小二乘問題：
上式的f(x)是要拟合的函數，可以是任意标量非線性函數，F(x)是目标函數，我們希望找到一個x(即這裡的x是待優化參數)令目标函數F(x)最小。求解這個問題有幾種方法：
1.直接求導，令dF/dx=0，但這通常難以實作。
2.疊代法：
這讓求解導函數為零的問題變成了一個不斷尋找下降增量 ∆xk 的問題。以下就是尋找增量的方法。
一階和二階梯度法
考慮第k次疊代，想要尋找∆xk，最直接的方法是将目标函數F(x)在xk附近進行泰勒展開：
其中J(xk)是F(x)關于x的一階導數(梯度、雅可比(Jacobian)矩陣)，H(xk)則是二階導數(海塞(Hessian)矩陣)。
如果上式中隻保留一階項，則稱為一階梯度法或最快下降法，取∆x=-J(xk)，即增量的方向為梯度的反方向，通常還設定一個步長λ。
如果保留二階項，則此增量方程為：
求右側關于∆x的導數并令它為0，得：J+H∆x=0，即 H∆x=-J 。求解這個線性方程，就得到了增量，該方法稱為二階梯度法或牛頓法。
一階梯度法過于貪心，容易走出鋸齒路線，反而增加了疊代次數；而二階梯度法則需要計算目标函數的 H 矩陣，這在問題規模較大時非常困難，我們通常傾向于避免 H 的計算。
高斯牛頓法
将要拟合的函數f(x)(不是目标函數F(x)，不然就成了牛頓法)進行一階泰勒展開：
這裡的J(x)是f(x)關于x的導數，為nx1的列向量。我們的目标是尋找增量∆x，使得|f(x+∆x)|2最小。為了求∆x，需要解一個線性最小二乘問題：
将上述目标函數對∆x求導，并令導數等于0。為此，先展開目标函數的平方項：
再對∆x求導，令其為0,得：J(x)f(x) + J(x)JT(x)∆x = 0，即：
J(x)JT(x)∆x = - J(x)f(x)
該式是關于變量∆x的線性方程組，稱之為增量方程，或稱之為高斯牛頓方程(Gauss-Newton equation)或正規方程(Normal equation)。令H=J(x)JT(x)，g=-J(x)f(x)，則高斯牛頓方程變為：
H∆x=g
對比牛頓法中H∆x=-J，高斯牛頓法用J(x)JT(x)作為牛頓法中Hessian矩陣的近似，進而省略了H的計算。求解高斯牛頓方程是整個優化問題的核心所在，如果能解出該方程，則高斯牛頓法的步驟如下：
為了求解增量方程，需要解出H-1，這需要H矩陣可逆。但是實際上H隻有半正定，也就是H可能會是奇異矩陣或ill-condition的情況，此時增量的穩定性較差，導緻算法不收斂。就算H非奇異也非病态，但是如果求出來的步長∆x太大，也無法保證能疊代收斂。
列文伯格—馬誇爾特方法
該方法的收斂速度比高斯牛頓法慢，也被稱為阻尼牛頓法。高斯牛頓法中采用的近似二階泰勒展開隻能在展開點附近有較好的近似效果，是以很自然地想到給 ∆x 添加一個範圍，稱為信賴區域(Trust Region)。這個範圍定義了在什麼情況下二階近似是有效的，這類方法也稱為信賴區域方法(Trust Region Method)。在信賴區域裡邊，我們認為近似是有效的；出了這個區域，近似可能會出問題。
那麼如何确定這個信賴區域的範圍呢？一個比較好的方法是根據我們的近似模型跟實際函數之間的差異來确定：如果差異小，說明近似效果好，我們擴大近似的範圍；反之，如果差異大，就縮小近似的範圍。我們定義一個名額 ρ 來刻畫近似的好壞程度，下式為6.34：
ρ 的分子是實際函數下降的值，分母是近似模型下降的值。如果 ρ 接近于 1，則近似是好的。如果 ρ太小，說明實際減小的值遠少于近似減小的值，則認為近似比較差，需要縮小近似範圍。反之，如果 ρ 比較大，則說明實際下降的比預計的更大，我們可以放大近似範圍。是以新的步驟如下：
這裡近似範圍µ擴大的倍數和門檻值都是經驗值。在式(6.35)中，把增量限定于一個半徑為 µ 的球中，隻在這個球内才是有效的。帶上 D 之後，這個球可以看成一個橢球。在列文伯格提出的優化方法中，把 D 取成機關陣 I，相當于直接把 ∆xk 限制在一個球中。馬誇爾特提出将 D 取成非負數對角陣——實際中通常用 JTJ 的對角元素平方根，使得在梯度小的次元上限制範圍更大一些。
梯度的獲得需要求解式(6.35)，這個子問題是帶不等式限制的優化問題，我們用拉格朗日乘子把限制項放到目标函數中，構成拉格朗日函數：
λ為拉格朗日乘子。類似于高斯牛頓法中的做法，令該拉格朗日函數關于 ∆x 的導數為零，它的核心仍是計算增量的線性方程：(H + λDTD) ∆xk = g 。這裡的增量方程相比于高斯牛頓法多了一項λDTD，若 D=I，則求解的是：
(H + λI) ∆xk = g
當參數 λ 比較小時，H 占主要地位，這說明二次近似模型在該範圍内是比較好的，列文伯格—馬誇爾特方法更接近于高斯牛頓法。當 λ 比較大時，λI 占據主要地位，列文伯格—馬誇爾特方法更接近于一階梯度下降法(即最速下降)，這說明附近的二次近似不夠好。
列文伯格—馬誇爾特方法的求解方式，可在一定程度上避免線性方程組的系數矩陣的非奇異和病态問題，提供更穩定、更準确的增量 ∆x。在實際中，還存在許多其他的方式來求解增量，例如 Dog-Leg 等方法。
曲線拟合
要拟合的曲線：y = exp(ax2 + bx + c) + w，其中a、b、c為曲線參數，w為0均值、σ标準差的高斯噪聲。假設有N個觀測點，則使用高斯牛頓法求解下面的最小二乘問題以估計曲線參數：
定義誤差為：ei = yi - exp(axi2 + bxi + c)，這裡的狀态變量為a,b,c，求出每個誤差項對于狀态變量的導數：
于是雅可比矩陣為：
得高斯牛頓方程：
最小二乘法
最小二乘法（又稱最小平方法）是一種數學優化技術。它通過最小化誤差的平方和尋找資料的最佳函數比對。利用最小二乘法可以簡便地求得未知的資料，并使得這些求得的資料與實際資料之間誤差的平方和為最小。最小二乘法還可用于曲線拟合。數學表示：
其中yi是第i個實際觀測到的值，或叫真實值或者目标值；fi(x)則可以看作是通過x這個參數預測得到的第i個值，是對yi的估計。最小二乘的目标估計未知的參數使得觀測值（真實值）和估計值之間的差距最小。
線性最小二乘
所謂線性，指f(x)是x的線性函數，f(x)=x0+t1*x1+...+tq*xq。線性最小二乘的解法相對簡單。
非線性最小二乘
所謂非線性，就是f(x)無法表示為的線性關系，而是某種非線性關系。考慮一個簡單的非線性最小二乘問題：
上式的f(x)是要拟合的函數，可以是任意标量非線性函數，F(x)是目标函數，我們希望找到一個x(即這裡的x是待優化參數)令目标函數F(x)最小。求解這個問題有幾種方法：
1.直接求導，令dF/dx=0，但這通常難以實作。
2.疊代法：
這讓求解導函數為零的問題變成了一個不斷尋找下降增量 ∆xk 的問題。以下就是尋找增量的方法。
一階和二階梯度法
考慮第k次疊代，想要尋找∆xk，最直接的方法是将目标函數F(x)在xk附近進行泰勒展開：
其中J(xk)是F(x)關于x的一階導數(梯度、雅可比(Jacobian)矩陣)，H(xk)則是二階導數(海塞(Hessian)矩陣)。
如果上式中隻保留一階項，則稱為一階梯度法或最快下降法，取∆x=-J(xk)，即增量的方向為梯度的反方向，通常還設定一個步長λ。
如果保留二階項，則此增量方程為：
求右側關于∆x的導數并令它為0，得：J+H∆x=0，即 H∆x=-J 。求解這個線性方程，就得到了增量，該方法稱為二階梯度法或牛頓法。
一階梯度法過于貪心，容易走出鋸齒路線，反而增加了疊代次數；而二階梯度法則需要計算目标函數的 H 矩陣，這在問題規模較大時非常困難，我們通常傾向于避免 H 的計算。
高斯牛頓法
将要拟合的函數f(x)(不是目标函數F(x)，不然就成了牛頓法)進行一階泰勒展開：
這裡的J(x)是f(x)關于x的導數，為nx1的列向量。我們的目标是尋找增量∆x，使得|f(x+∆x)|2最小。為了求∆x，需要解一個線性最小二乘問題：
将上述目标函數對∆x求導，并令導數等于0。為此，先展開目标函數的平方項：
再對∆x求導，令其為0,得：J(x)f(x) + J(x)JT(x)∆x = 0，即：
J(x)JT(x)∆x = - J(x)f(x)
該式是關于變量∆x的線性方程組，稱之為增量方程，或稱之為高斯牛頓方程(Gauss-Newton equation)或正規方程(Normal equation)。令H=J(x)JT(x)，g=-J(x)f(x)，則高斯牛頓方程變為：
H∆x=g
對比牛頓法中H∆x=-J，高斯牛頓法用J(x)JT(x)作為牛頓法中Hessian矩陣的近似，進而省略了H的計算。求解高斯牛頓方程是整個優化問題的核心所在，如果能解出該方程，則高斯牛頓法的步驟如下：
為了求解增量方程，需要解出H-1，這需要H矩陣可逆。但是實際上H隻有半正定，也就是H可能會是奇異矩陣或ill-condition的情況，此時增量的穩定性較差，導緻算法不收斂。就算H非奇異也非病态，但是如果求出來的步長∆x太大，也無法保證能疊代收斂。
列文伯格—馬誇爾特方法
該方法的收斂速度比高斯牛頓法慢，也被稱為阻尼牛頓法。高斯牛頓法中采用的近似二階泰勒展開隻能在展開點附近有較好的近似效果，是以很自然地想到給 ∆x 添加一個範圍，稱為信賴區域(Trust Region)。這個範圍定義了在什麼情況下二階近似是有效的，這類方法也稱為信賴區域方法(Trust Region Method)。在信賴區域裡邊，我們認為近似是有效的；出了這個區域，近似可能會出問題。
那麼如何确定這個信賴區域的範圍呢？一個比較好的方法是根據我們的近似模型跟實際函數之間的差異來确定：如果差異小，說明近似效果好，我們擴大近似的範圍；反之，如果差異大，就縮小近似的範圍。我們定義一個名額 ρ 來刻畫近似的好壞程度，下式為6.34：
ρ 的分子是實際函數下降的值，分母是近似模型下降的值。如果 ρ 接近于 1，則近似是好的。如果 ρ太小，說明實際減小的值遠少于近似減小的值，則認為近似比較差，需要縮小近似範圍。反之，如果 ρ 比較大，則說明實際下降的比預計的更大，我們可以放大近似範圍。是以新的步驟如下：
這裡近似範圍µ擴大的倍數和門檻值都是經驗值。在式(6.35)中，把增量限定于一個半徑為 µ 的球中，隻在這個球内才是有效的。帶上 D 之後，這個球可以看成一個橢球。在列文伯格提出的優化方法中，把 D 取成機關陣 I，相當于直接把 ∆xk 限制在一個球中。馬誇爾特提出将 D 取成非負數對角陣——實際中通常用 JTJ 的對角元素平方根，使得在梯度小的次元上限制範圍更大一些。
梯度的獲得需要求解式(6.35)，這個子問題是帶不等式限制的優化問題，我們用拉格朗日乘子把限制項放到目标函數中，構成拉格朗日函數：
λ為拉格朗日乘子。類似于高斯牛頓法中的做法，令該拉格朗日函數關于 ∆x 的導數為零，它的核心仍是計算增量的線性方程：(H + λDTD) ∆xk = g 。這裡的增量方程相比于高斯牛頓法多了一項λDTD，若 D=I，則求解的是：
(H + λI) ∆xk = g
當參數 λ 比較小時，H 占主要地位，這說明二次近似模型在該範圍内是比較好的，列文伯格—馬誇爾特方法更接近于高斯牛頓法。當 λ 比較大時，λI 占據主要地位，列文伯格—馬誇爾特方法更接近于一階梯度下降法(即最速下降)，這說明附近的二次近似不夠好。
列文伯格—馬誇爾特方法的求解方式，可在一定程度上避免線性方程組的系數矩陣的非奇異和病态問題，提供更穩定、更準确的增量 ∆x。在實際中，還存在許多其他的方式來求解增量，例如 Dog-Leg 等方法。
曲線拟合
要拟合的曲線：y = exp(ax2 + bx + c) + w，其中a、b、c為曲線參數，w為0均值、σ标準差的高斯噪聲。假設有N個觀測點，則使用高斯牛頓法求解下面的最小二乘問題以估計曲線參數：
定義誤差為：ei = yi - exp(axi2 + bxi + c)，這裡的狀态變量為a,b,c，求出每個誤差項對于狀态變量的導數：
于是雅可比矩陣為：
得高斯牛頓方程：