數(shù)值分析15(最小二乘法1)

1、1/4610:56超定方程組超定方程組最小二乘擬合最小二乘擬合模型綜述模型綜述數(shù)值分析 152/4610:56引子引子: 行星運(yùn)動(dòng)定律行星運(yùn)動(dòng)定律(開普勒第三定律開普勒第三定律)繞以太陽為焦點(diǎn)的橢圓軌道運(yùn)行的所有行星繞以太陽為焦點(diǎn)的橢圓軌道運(yùn)行的所有行星, 其各自其各自橢圓軌道半長軸的立方與周期的平方之比是一個(gè)常量。橢圓軌道半長軸的立方與周期的平方之比是一個(gè)常量。3/4610:56 行星行星 半長軸半長軸 (a) 周期周期 (T) T2/a3 海王星海王星 450 165 天王星天王星 287 84 2.99 2.98323245016528784c 行星運(yùn)動(dòng)定律行星運(yùn)動(dòng)定律 繞以太陽為焦點(diǎn)的

2、橢圓軌道運(yùn)行的所有行星繞以太陽為焦點(diǎn)的橢圓軌道運(yùn)行的所有行星, 其各自其各自橢圓軌道半長軸的立方與周期的平方之比是一個(gè)常量。橢圓軌道半長軸的立方與周期的平方之比是一個(gè)常量。4/4610:56 不相容方程組不相容方程組(inconsistent equation)1212122,1,3.xxxxxx 一個(gè)無解的方程組稱為不相容。許多情況下方程一個(gè)無解的方程組稱為不相容。許多情況下方程個(gè)數(shù)大于未知量個(gè)數(shù)使解不大可能滿足所有的方程。個(gè)數(shù)大于未知量個(gè)數(shù)使解不大可能滿足所有的方程。定義定義: 一個(gè)方程組若至少存在一個(gè)解能夠嚴(yán)格滿足該方一個(gè)方程組若至少存在一個(gè)解能夠嚴(yán)格滿足該方程組程組,則稱為相容方程則稱

3、為相容方程(consistent equation)。Axb 定理定理: 線性方程線性方程Ax=b是相容的當(dāng)且僅當(dāng)是相容的當(dāng)且僅當(dāng) rank(A,b)=rank(A) 。5/4610:56 不相容方程組不相容方程組(inconsistent equation) 當(dāng)方程組不相容時(shí)當(dāng)方程組不相容時(shí), 如何尋求如何尋求次佳次佳(next-best)解。解。0rAxb2222minmin( )xxAxbr x 即即 Axb 我們希望殘差我們希望殘差r盡可能小盡可能小,這里小的標(biāo)準(zhǔn)是什么呢？這里小的標(biāo)準(zhǔn)是什么呢？2221 squares()niilreastr 6/4610:56112211211211

4、1111113113xxxx 等等價(jià)價(jià)于于12?bvv如如果果 不不屬屬于于 和和 張張成成的的平平面面7/4610:561212211222,222121212, argargminmin ( )argmin(-2)(-1)(-3)xxxxxxbument of theimumxxxxxx多變量函數(shù)極值點(diǎn)多變量函數(shù)極值點(diǎn):00( ) grad ()0 xf xf x 設(shè)設(shè)是是的的一一個(gè)個(gè)極極值值點(diǎn)點(diǎn)的的必必要要條條件件是是。111222()0TTxxb TTA AxA b 最小二乘解最小二乘解(Least Squares Solution):8/4610:56():TTnormal equa

5、A AxAnbtio 正正規(guī)規(guī)方方程程 121122()0TTnnTnxxxb 9/4610:5612112111113xx 1111131111111311TA A 21116111143TA b 12316134xx 例例11230.5()00.5rresiduals rbAxrr 殘殘差差22221232( )least squrrrrares10/4610:56,m nAxbARmn 超超定定方方程程其其中中 回顧回顧:22 argmin|xAxb 最最小小二二乘乘解解1,()TTTA AxA AA b 進(jìn)進(jìn)一一步步地地如如果果可可逆逆 則則 Axb TTA AxA b 正正規(guī)規(guī)方方程

6、程11/4610:56大數(shù)據(jù)環(huán)境下的數(shù)據(jù)挖掘大數(shù)據(jù)環(huán)境下的數(shù)據(jù)挖掘12/4610:56引子引子: 行星運(yùn)動(dòng)定律行星運(yùn)動(dòng)定律(開普勒第三定律開普勒第三定律)繞以太陽為焦點(diǎn)的橢圓軌道運(yùn)行的所有行星繞以太陽為焦點(diǎn)的橢圓軌道運(yùn)行的所有行星, 其各自其各自橢圓軌道半長軸的立方與周期的平方之比是一個(gè)常量。橢圓軌道半長軸的立方與周期的平方之比是一個(gè)常量。13/4610:56例例2: 研究彈簧伸長的長度跟引起形變的外力的關(guān)系。研究彈簧伸長的長度跟引起形變的外力的關(guān)系。load Hooke.matu=0.08:.0001:0.35; v=interp1(x,y,u,spline);plot(x,y,o,u,v,

7、-)Hookes Law14/4610:56 x 0.0861 0.1720 0.2598 0.2701 0.3015 0.3225 f(x) 0.0197 0.0398 0.0597 0.0647 0.0697 0.0746求擬合函數(shù)求擬合函數(shù):110221111mmyxcxycxy Ac=b01( )f xcc x0111cc xy0122cc xy01mmcc xy112111 mmiiiiTTmmmiiiiiiimxyA AcA bxxx y15/4610:56例例3. 美國人口統(tǒng)計(jì)數(shù)據(jù)美國人口統(tǒng)計(jì)數(shù)據(jù)(censusgui) load census研究美國人口增長的規(guī)律并預(yù)測研究美國人

8、口增長的規(guī)律并預(yù)測2010年的人口。年的人口。求擬合函數(shù)求擬合函數(shù):230123( )f xcc xc xc x16/4610:56 x x1 x2 xm f(x) y1 y2 ym離散數(shù)據(jù)的多項(xiàng)式擬合離散數(shù)據(jù)的多項(xiàng)式擬合求擬合函數(shù)求擬合函數(shù):1011211nnmmnmycxxyxxcy 01( )nnf xcc xc x11101121111 mkmmknkkmkkkkTTkmmmnnnnkkkmkkknkkkymxxcx yA AcA bcxxxx y 17/4610:56例例4. 求最小二乘擬合數(shù)據(jù)點(diǎn)求最小二乘擬合數(shù)據(jù)點(diǎn)(-1,1),(0,0),(1,0),(2,-2)的的直線模型和拋物

9、線模型直線模型和拋物線模型。,yabxab首首先先選選取取模模型型目目標(biāo)標(biāo)是是尋尋求求最最佳佳的的 和和 。1-1110042-10.20.911026-512-2aaytbb 2,yabxcxa bc選選取取模模型型目目標(biāo)標(biāo)是是尋尋求求最最佳佳的的和和 。21-111426-110002680.450.65 -0.25-511106818-7124-2aayxxbbcc 18/4610:56例例5. 線性分類線性分類(Machine Learning) 年齡年齡 相貌相貌 才華才華 財(cái)富財(cái)富 品德品德 http:/ wwyc 或或19/4610:56 x x1 x2 xm f(x) y1 y

10、2 ym離散數(shù)據(jù)的最小二乘線性擬合離散數(shù)據(jù)的最小二乘線性擬合求擬合函數(shù)求擬合函數(shù):1001111201()()()()()()nmmnmnmycxxxyxxxcy 0011( )( )( )( )nnf xcxcxcx01000110110111()()()()()()()()()()()mkkmmkkkknkmkkkkTTkmmnnkknknkmkknkkkxyxxxxcxyA AcA bcxxxxxy 20/4610:56壓縮的概念壓縮的概念: 最小二乘擬合是數(shù)據(jù)壓縮的典型例子最小二乘擬合是數(shù)據(jù)壓縮的典型例子, 輸輸入大量的噪聲觀測數(shù)據(jù)入大量的噪聲觀測數(shù)據(jù), 而輸出是盡可能好地而輸出是盡可

11、能好地?cái)M合數(shù)據(jù)的模型擬合數(shù)據(jù)的模型(相對少的模型參數(shù)相對少的模型參數(shù))。最小二。最小二乘用合理的模型來代替乘用合理的模型來代替大量的噪聲數(shù)據(jù)大量的噪聲數(shù)據(jù)。21/4610:56最小二乘數(shù)據(jù)擬合最小二乘數(shù)據(jù)擬合: 殘差殘差(residuals)是指觀測值與模型預(yù)測值之間的差是指觀測值與模型預(yù)測值之間的差:我們希望殘差盡可能小我們希望殘差盡可能小, 這里小的標(biāo)準(zhǔn)是什么呢？這里小的標(biāo)準(zhǔn)是什么呢？1. .殘差為零殘差為零(插值方法插值方法)2. .最小化殘差的平方和最小化殘差的平方和(最小二乘解最小二乘解)0()niikkikrycxryAc 或或0120011,1argmin()()()nmiiin

12、niccciycxcxcx 22/4610:563. .最小化殘差的絕對值之和最小化殘差的絕對值之和4. .最小化殘差絕對值的最大分量最小化殘差絕對值的最大分量010011,argminmax()()()niiinniicccycxcxcx010011,1argmin()()()nmiiinniccciycxcxcx 23/4610:56最小二乘擬合的步驟最小二乘擬合的步驟:給定的觀測數(shù)據(jù)給定的觀測數(shù)據(jù)(x1,y1), (xm,ym)1. 選取模型選取模型: 確定的模型類型確定的模型類型, 如如y=a+bx。2. 使模型使模型擬合數(shù)據(jù)擬合數(shù)據(jù):將數(shù)據(jù)代入模型將數(shù)據(jù)代入模型, 每個(gè)觀測每個(gè)觀測數(shù)

13、據(jù)對應(yīng)一個(gè)參數(shù)作為未知數(shù)的方程。數(shù)據(jù)對應(yīng)一個(gè)參數(shù)作為未知數(shù)的方程。3. 求解最小二乘解求解最小二乘解(模型的參數(shù)模型的參數(shù))。 24/4610:56最小二乘擬合問題研究包括最小二乘擬合問題研究包括: :模型的選取模型的選取存在唯一性存在唯一性最小二乘解的計(jì)算最小二乘解的計(jì)算25/4610:56 The Law Dominants Our World (ten most important formulas on stamps issued by Nicaragua in 1971)26/4610:56The Law Dominants Our World27/4610:56The Law Do

14、minants Our World28/4610:56模型綜述模型綜述01: ( ) y xaa x直直線線常用模型包括常用模型包括: :01: ( )+nny xaa xa x多多項(xiàng)項(xiàng)式式21: ( )c xy xc e 指指數(shù)數(shù)函函數(shù)數(shù)2(): ( )exy x 高高斯斯函函數(shù)數(shù): ( )cos( )siny xxy xx三三角角函函數(shù)數(shù)或或所有的現(xiàn)象背后都有一個(gè)規(guī)律所有的現(xiàn)象背后都有一個(gè)規(guī)律(函數(shù)函數(shù))嗎？嗎？12: ( )lny xcc x 對對數(shù)數(shù)函函數(shù)數(shù)29/4610:56例例6. . 線性規(guī)律線性規(guī)律 Linear Law牛頓第二定律牛頓第二定律胡克定律胡克定律 (Hookes

15、law) 線性思維線性思維(linear thinking)30/4610:56周期數(shù)據(jù)周期數(shù)據(jù)31/4610:56周期數(shù)據(jù)周期數(shù)據(jù)32/4610:56例例7. . 人體的周期預(yù)測人體的周期預(yù)測t0=datenum(Dec.20,1983)t1=fix(now);t=(t1-28):1:(t1+28);y=100*sin(2*pi*(t-t0)/23); sin(2*pi*(t-t0)/28); sin(2*pi*(t-t0)/33)plot(t,y)legend(生理周期生理周期,情緒周期情緒周期,智力周期智力周期)33/4610:56例例8. . 外部氣溫在不同時(shí)間尺度下服從周期循環(huán)。外部

16、氣溫在不同時(shí)間尺度下服從周期循環(huán)。123: ( )cos2sin2y xccxcx選選擇擇模模型型34/4610:56442233445544332277441cos0sin02.21cossin2.81cossin6.11cossin3.9,1cossin01cossin1.11cossin0.61cossin1.1Ab 12380015.60402.977800410.2376TTcA AcA bcc : ( )-1.95-0.7445cos2-2.559sin2y xxx 最最佳佳模模型型load temperature.matplot(x,y);u=0:0.01:1;v=-1.95-0

17、.7445*cos(2*pi*u)-2.5594*sin(2*pi*u);hold on,plot(u,v,r)35/4610:56例例9. . 指數(shù)函數(shù)指數(shù)函數(shù)( (刻畫增長或衰減的數(shù)據(jù)規(guī)律刻畫增長或衰減的數(shù)據(jù)規(guī)律,如如放射性原子核的衰變規(guī)律和放射性原子核的衰變規(guī)律和Moore定律定律) )我們總是高估在一年或者兩年中能夠做到的我們總是高估在一年或者兩年中能夠做到的,而低估五年或者十年中能夠做到的。而低估五年或者十年中能夠做到的。36/4610:5611ln225012ln2500,14ln5000133ln410000000Ab21: ( )cc xy xe 選選擇擇模模型型12:ln (

18、 )ln+y xcc x 線線性性化化技技術(shù)術(shù)22 13235176.9023559273793.23TTkA AA bckc 0.3596: ( )1335.3xy xe 最最佳佳模模型型Moore 1.9276ln2/ 0.3596 定定律律2122,i=11argmin(e)imxicc ccy 122l,2n=1arg min(ln)miicikckxcy 37/4610:56線性化改變了原最小二乘問題。線性化改變了原最小二乘問題。2122,11argmin(e)imxicic ccy 122l2n,1arg min(ln)kmiiiccyxkc 對于原非線性最小二乘問題可以考慮對于原

19、非線性最小二乘問題可以考慮Gradient Descent和和 Gauss-Newton等優(yōu)化等優(yōu)化方法。方法。38/4610:56摩爾定律已經(jīng)成為工業(yè)界一切呈指數(shù)型增長事摩爾定律已經(jīng)成為工業(yè)界一切呈指數(shù)型增長事物的代名詞。下一個(gè)十年物的代名詞。下一個(gè)十年, 摩爾定律可能還將摩爾定律可能還將有效有效。可以肯定的是可以肯定的是, 創(chuàng)新無止境。創(chuàng)新無止境。 戈登戈登. .摩爾摩爾( (英特爾創(chuàng)始人英特爾創(chuàng)始人) )39/4610:56例例10. . 冪函數(shù)冪函數(shù)( (power law) )21: ( )ccy xx 選選擇擇模模型型40/4610:56例例11. .生物界的牛頓定律生物界的牛頓定

20、律 1998年年Nature的一篇文章的一篇文章Common rules for animals and plants揭示了生物體的一些常見計(jì)揭示了生物體的一些常見計(jì)量值與其質(zhì)量的關(guān)系量值與其質(zhì)量的關(guān)系, 被被Nature編輯喻為生物編輯喻為生物界的牛頓定律。簡單的說就是發(fā)現(xiàn)了界的牛頓定律。簡單的說就是發(fā)現(xiàn)了Y= =Y0Mb ,其中其中M為質(zhì)量為質(zhì)量, Y為生物體的一些計(jì)量值為生物體的一些計(jì)量值, Y0為為常數(shù)關(guān)系中常數(shù)關(guān)系中b值的大小和原因值的大小和原因, 且這一規(guī)律在橫且這一規(guī)律在橫跨質(zhì)量的跨質(zhì)量的21個(gè)數(shù)量級都滿足。個(gè)數(shù)量級都滿足。41/4610:56例例12. . 計(jì)算機(jī)視覺中計(jì)算機(jī)視覺中Gamma校正校正42/4610:56例例13. . 血液中藥物的衰減規(guī)律血液中藥物的衰減規(guī)律21: ( )ccy xx 選選擇擇模