線性及非線性最小二乘問題

第5章線性與非線性最小二乘問題§5.1前言1801年,意大利天文學(xué)家朱賽普·皮亞齊發(fā)現(xiàn)了第一顆小行星谷神星.經(jīng)過40天的跟蹤觀測(cè)后,由于谷神星運(yùn)行至太陽(yáng)背后，使得皮亞齊失去了谷神星的位置。隨后全世界的科學(xué)家利用皮亞齊的觀測(cè)數(shù)據(jù)開始尋找谷神星,但是根據(jù)大多數(shù)人計(jì)算的結(jié)果來尋找谷神星都沒有結(jié)果.時(shí)年24歲的高斯也計(jì)算了谷神星的軌道.奧地利天文學(xué)家海因里?！W爾伯斯根據(jù)高斯計(jì)算出來的軌道重新發(fā)現(xiàn)了谷神星.

高斯使用的最小二乘法的方法發(fā)表于1809年他的著作《天體運(yùn)動(dòng)論》中.而法國(guó)科學(xué)家勒讓德于1806年獨(dú)立發(fā)現(xiàn)“最小二乘法”,但因不為時(shí)人所知而默默無聞.兩人曾為誰最早創(chuàng)立最小二乘法原理發(fā)生爭(zhēng)執(zhí).1829年,高斯提供了最小二乘法的優(yōu)化效果強(qiáng)于其他方法的證明,稱為高斯-馬爾可夫定理.無約束最優(yōu)化問題最小二乘的形式稱為殘量函數(shù)是x的線性函數(shù)線性最小二乘問題§5.2線性最小二乘問題的解法解線性最小二乘問題

設(shè)為階矩陣,

為m維向量,線性最小二乘問題為求的最優(yōu)解.其中為向量的范數(shù).將

按范數(shù)展開得對(duì)稱矩陣

至少半正定

任一最優(yōu)解都是全局最優(yōu)解凸優(yōu)化問題當(dāng)向量b屬于矩陣A的像空間

則存在

使否則問題的最優(yōu)值不為零.設(shè)為問題的最優(yōu)解不一定為零.一階必要條件是問題的最優(yōu)解法方程組A列滿秩正規(guī)方程組正定方程組的解唯一且可表示為

矩陣A的廣義逆作為一個(gè)二次函數(shù)的無約束優(yōu)化對(duì)方程組的求解，一般采用矩陣

的Cholesky分解

，其中L下三角矩陣

如果矩陣正定對(duì)于線性最小二乘問題，我們可以利用其問題的特殊結(jié)構(gòu)，設(shè)計(jì)更為有效的求解方法。對(duì)于線線性最小二乘問題形成的矩陣

不宜采用先計(jì)算矩陣

再對(duì)它進(jìn)行分解的方法的條件數(shù)是矩陣A的條件數(shù)的平方因?yàn)榫仃噷?duì)稱矩陣的三角分解定理設(shè)A為n階對(duì)稱矩陣,且A的所有順序主子式均不為零,則A可唯一分解為其中L為單位下三角矩陣,D為對(duì)角矩陣.對(duì)稱正定矩陣的三角分解或Cholesky分解設(shè)A為n階對(duì)稱正定矩陣,當(dāng)限定L的對(duì)角元素為正時(shí),這種分解是唯一的.則存在一個(gè)實(shí)的非奇異下三角矩陣L使得矩陣的QR分解為避免計(jì)算乘積矩陣

再進(jìn)行分解，可以采用對(duì)增廣矩陣

作QR正交分解的方法。設(shè)A列滿秩其中Q為m×m階正交矩陣為n×n上三角矩陣因此最優(yōu)解x*可由三角方程組經(jīng)回代確定求線性最小二乘問題最優(yōu)解正交分解算法如下:步1.對(duì)增廣矩陣[A

b]作QR正交分解得和向量步2.取為向量的前n個(gè)分量形成的向量步3.用回代解方程組得解在上述QR正交分解算法的分析過程中我們假定矩陣A的列線性無關(guān).當(dāng)矩陣A的列線性相關(guān),即A不是列滿秩時(shí),矩陣A的QR正交分解是一個(gè)r×r非奇異的上三角矩陣r=rank(A)＜n表示矩陣A的秩數(shù)表示由向量的前r個(gè)分量組成的向量這時(shí)確定最優(yōu)解的方程組利用矩陣A的奇異值分解設(shè)A為m×n

(m＞n)階矩陣則存在m×m階正交矩陣U和n×n階正交矩陣V使得其中S為m×n階的塊對(duì)角矩陣為r×r階對(duì)角矩陣為矩陣A的奇異值A(chǔ)的秩為r＜n最小二乘法解不唯一極小范數(shù)最小二乘解規(guī)范最小二乘解范數(shù)最小其中

是最小二乘問題所有解的集合.即在所有最小二乘解中當(dāng)r=n時(shí),最小二乘解唯一由奇異值分解所確定的矩陣§5.3

非線性最小二乘的

Gauss-Newton法考慮非線性最小二乘問題其中為的非線性函數(shù)，稱為殘量函數(shù).如果函數(shù)r(x)二階連續(xù)可微，則f(x)的一階和二階導(dǎo)數(shù)(Hesse矩陣)分別為牛頓法擬牛頓法

算法

(Gauss-Newton法)步1.給定解的初始估計(jì)

置k=1;步2.如果

滿足精度要求,停止迭代;步3.解方程組

步4.置

k:=k+1后轉(zhuǎn)步2;算法

(阻尼Gauss-Newton法)步1.給定解的初始估計(jì)，置k=1;步2.如果

滿足精度要求,停止迭代;步3.解方程組

并置步4.沿方向進(jìn)行線性搜索,確定步長(zhǎng)

置

,k:=k+1后轉(zhuǎn)步2.§5.4

信賴域方法信賴域方法是求解最優(yōu)化問題的另一類有效方法，其最初的設(shè)計(jì)思想可追溯至Levenberg和Marquardt對(duì)Gauss-Newton法的修正。離最優(yōu)解較遠(yuǎn)時(shí)和確定的點(diǎn)滿足比較大,超出了有效的鄰域不能保證而且對(duì)于越大的正數(shù),解向量的長(zhǎng)度越短,因此,必可找到適當(dāng)?shù)闹?使在的一個(gè)較小的鄰域內(nèi),從而有其中是Hesse陣的近似為信賴域半徑．根據(jù)模型函數(shù)對(duì)目標(biāo)函數(shù)的擬合程度來調(diào)整信賴域半徑對(duì)于問題(1)的解定義比值：它衡量模型函數(shù)與目標(biāo)函數(shù)的一致性程度．實(shí)際下降量預(yù)測(cè)下降量注：(1)越接近于１，表明模型函數(shù)與目標(biāo)函數(shù)的一致性程度越好，可以增大以擴(kuò)大信賴域．(2)不接近于１，可以保持不變．(3)接近于零或取負(fù)值，表明模型函數(shù)與目標(biāo)函數(shù)的一致性程度不好，可以減小以縮小信賴域．步1.給定控制迭代的參數(shù)值

,初始點(diǎn)

,以及初始信