数值计算之曲线拟合的最小二乘法

数学系UniversityofScienceandTechnologyofChinaDEPARTMENTOFMATHEMATICS第3章曲线拟合的最小二乘法给出一组离散点，确定一个函数逼近原函数，插值是这样的一种手段。在实际中，数据不可避免的会有误差，插值函数会将这些误差也包括在内。因此，我们需要一种新的逼近原函数的手段：①不要求过所有的点（可以消除误差影响）；②尽可能表现数据的趋势，靠近这些点。数学系UniversityofScienceandTechnologyofChinaDEPARTMENTOFMATHEMATICS有时候，问题本身不要求构造的函数过所有的点。如：5个风景点，要修一条公路S使得S为直线，且到所有风景点的距离和最小。先讲些预备知识对如上2类问题，有一个共同的数学提法：找函数空间上的函数g，使得g到f的距离最小。数学系UniversityofScienceandTechnologyofChinaDEPARTMENTOFMATHEMATICS向量范数映射：满足：}0{:RRn①非负性00,0XXX且②齐次性XaaXRa,③三角不等式YXYX称该映射为向量的一种范数预备知识我们定义两点的距离为：YX定义数学系UniversityofScienceandTechnologyofChinaDEPARTMENTOFMATHEMATICS常见的范数有：nniixxxXxX,,,,)(21122nixxxXxX,,,},max{21nniixxxXxX,,,,2111定理（范数等价性）：设pqxx和为任意两种范数，则存在与x无关的正常数c1和c2，使得12,qpqcxxcxx数学系UniversityofScienceandTechnologyofChinaDEPARTMENTOFMATHEMATICS定义：函数f，g的关于离散点列niix0的离散内积为：niiiDxgxfgf0)()(),(常用范数的等价关系：212xxnx2xxnx1xxnx数学系UniversityofScienceandTechnologyofChinaDEPARTMENTOFMATHEMATICS定义：函数f的离散范数为niiiDxfxff0)()(提示：该种内积，范数的定义与向量的2－范数一致我们还可以定义函数的离散范数为：01010110(),(),,()max(),(),,()(),(),,()()nnDnniDiffxfxfxfxfxfxffxfxfxfx数学系UniversityofScienceandTechnologyofChinaDEPARTMENTOFMATHEMATICSf(x)为定义在区间[a,b]上的函数，为区间上n+1个互不相同的点，为给定的某一函数类。求上的函数g(x)满足f(x)和g(x)的距离最小0niix如果这种距离取为2－范数的话，称为最小二乘问题曲线拟合的最小二乘问题定义数学系UniversityofScienceandTechnologyofChinaDEPARTMENTOFMATHEMATICS下面我们来看看最小二乘问题：求使得最小)(xgniiixfxgR022)()(设},,{10nspan)()()(00xaxaxgnnDnnxaxaxf)()()(00DDxfxxfxg)()(min)()(最小则即关于系数},,{10naaa数学系UniversityofScienceandTechnologyofChinaDEPARTMENTOFMATHEMATICS20020020020,001()()()2(,()())()()2,,(,,,)nnDnnDDnnDnnkkikikDkiknfxaxaxffaxaxaxaxfafaaQaaa由于它关于系数},,{10naaa最小，因此有：niaQi,,0,0即nifainkkik,,0),,(),(0数学系UniversityofScienceandTechnologyofChinaDEPARTMENTOFMATHEMATICS写成矩阵形式有：DnDnDnnDnDnDffaa,,,,,,000000法方程由},,{10n的线性无关性，知道该方程存在唯一解数学系UniversityofScienceandTechnologyofChinaDEPARTMENTOFMATHEMATICS①bxayDDDDDDxffbaxxxx,1,,1,,11,1第一步：函数空间的基x,1，然后列出法方程②baxy2DDDDDDfxfbaxxxx1,,1,1,1,1,22222第一步：函数空间的基1,2x，然后列出法方程例：数学系UniversityofScienceandTechnologyofChinaDEPARTMENTOFMATHEMATICSbaxy23703456334558.3ab3212414.38.34.78.322.7xy第一步：函数空间的基1,2x，然后列出法方程DDDDDDfxfbaxxxx1,,1,1,1,1,222220.8327167.49691ab数学系UniversityofScienceandTechnologyofChinaDEPARTMENTOFMATHEMATICSbxaey由bxaylnln，可以先做bxay**bxayeeey**3212414.38.34.78.322.7ln2.660262.116261.547562.116263.12236xyy1,11,,11,,,DDDDDDxfaxxxfxb5011.56270342.9611ab2.312540.0870912ab数学系UniversityofScienceandTechnologyofChinaDEPARTMENTOFMATHEMATICS求解一个矛盾方程组，计算的是在均方误差22minbAX极小意义下的解也就是最小二乘问题。我们有：矛盾方程组恒有解，且2222minbAYbAXbAAXAnRYTT矛盾方程组的求解数学系UniversityofScienceandTechnologyofChinaDEPARTMENTOFMATHEMATICS定义：矩阵范数AxxAxAxRxxRxnn1,0,supsup矩阵范数，是由向量的范数定义的矩阵范数和条件数矩阵范数也是等价的数学系UniversityofScienceandTechnologyofChinaDEPARTMENTOFMATHEMATICS对应于3种常见的向量范数，有3种矩阵范数niijnjaA111max列和的最大值njijniaA11max行和的最大值12A是ATA的最大特征值，也称为谱半径1矩阵范数的一些性质：①②③④⑤00,&,0AAARAA,nRBABABA,,nRBABAAB,,nRxxAAx,数学系UniversityofScienceandTechnologyofChinaDEPARTMENTOFMATHEMATICS定理：若为A的特征值，则A证：xAxxAxxAxAxxxxAAx为A的特征值#证毕定义：谱半径rnrA1max)(易知：AA)(数学系UniversityofScienceandTechnologyofChinaDEPARTMENTOFMATHEMATICS条件数和病态矩阵定义：条件数pppAAACond1)(p表示某种范数设bAx，A引入误差后A，解引入误差x，则bxxAA))((xAxAAxbxAA)(xAAAx1)(AAAxx1)(AAAAI111)(111)()(AAAAIA数学系UniversityofScienceandTechnologyofChinaDEPARTMENTOFMATHEMATICSAAAAI111)(注意到BBIB11)(11因为：BDDDBIIBID)(1)(1)1(BDDBDAAAAxx1111数学系UniversityofScienceandTechnologyofChinaDEPARTMENTOFMATHEMATICSAAAAAAAAAAAA111111条件数很小AAAA1条件数表示了对误差的放大率同样，类似有bbAAxxbxAbbxxA1)(数学系UniversityofScienceandTechnologyofChinaDEPARTMENTOFMATHEMATICS注：一般判断矩阵是否病态，并不计算A1，而由经验得出。行列式很大或很小（如某些行、列近似相关）；元素间相差大数量级，且无规则；主元消去过程中出现小主元；特征值相差大数量级。精确解为.11x例97.199.1,98.099.099.01bA计算cond(A)2。10000990099009800A1=数学系UniversityofScienceandTechnologyofChinaDEPARTMENTOFMATHEMATICS解：考察A的特征根0)det(AI000050504.0980050504.121212)(Acond392061测试病态程度：给一个扰动b3410106.01097.0b，其相对误差为%01.010513.0||||||||422bb此时精确解为0203.13*x0203.22*xxx22||||||||xx2.0102200%为对称矩阵数学系UniversityofScienceandTechnologyofChinaDEPARTMENTOFMATHEMATICSHomework对数据点110,1,...,65nnxn估计如下两组基函数的法方程的条件数2012()1,(),()xxxxx012()1,()10.5,()(10.3)(10.7)xxxxxx