第五章 最小二乘问题.ppt

* * 第五章 最小二乘问题 5.1 引言 在数字处理中经常遇到寻求回归方程的问题，即根据一组实验数据建立两个或多个物理量（俗称因素）之间的在统计意义上的依赖关系式。 这类问题的数学模型如下： 设物理量 y 与物理量 t1,t2,…tl 之间的依赖关系式，设其方程为： y=F(t1,…tl,x1…xn) (1) 其中 x1…xn为待定参数。我们的问题是如何通过m(n)个实验点 [t1(i) ,t2(i) ,…tl(i), y(i)]T i=1,2…m 确定（1）中n个参数x1,x2…xn.从而建立回归方程。 对于实际一组参数x1,x2…xn的值，（1）给出l+1维空间中的一个超曲面。第i个实验点（ t1(i) ,t2(i) ,…tl(i) )在（1）中就确定超曲面上一个点即相应的函数值： 这个函数值 与测量值y(i)之差的绝对值 就是第i个实验点到该曲面的一种“距离”。 为计算方便，通常把 作为m个实验点到该曲面“总距离”的度量。 如何选择参数 x1…xn 使（2）达到极小这就是最小二乘法问题。上述问题用向量形式记为： 则 若 i=1~m. 其中 i=1~m 则上面问题可记为:min f(x)Tf(x) (3) (3) 即为最小二乘法问题一般形式。 当f(x)为线性向量值函数时，称（3）为线性最小二乘法问题。 否则，原问题称为非线性最小二乘法问题。 （3）是有n个变量的无约束极小化问题，一般可以用前面介绍的最优化方法求解。考虑到（3）的特殊形式，可以考虑更有效、更简单的方法求解。 f 的Jacobi矩阵： 主要计算量是 Sk 的计算，尽管Sk对称，也包含(1/2)mn(n+1)个二阶偏导数，但Hesse矩阵中第一项只含一阶导数的信息。因此为简化计算，我们或者忽略Sk，或者用一阶导数的信息逼近Sk。 由（4）可知，当 接近0或 fi(x)接近线性从而 接近于0，此时才可以忽略 Sk，因此这类算法又称为最小余量算法。 而称逼近Sk的一类算法为大余量算法。 5.2 线性最小二乘法问题的解法 则（3）为：min||Ax-b||2 (mn) (6) 定理1 x*是（6）的极小点的充要条件是x*满足向量组：ATAx*=ATb (7) 当f(x)取线性形式 即f(x)=Ax-b.A是m×n矩阵， 证： 称形如（7）的方程组为最小二乘问题（6）的法方程组. 可见求解线性最小二乘问题等价于求解它的法方程组. 故 至少是半正定的. 又因为 推论1 当 （8） 为（6）的唯一最小二乘解. 推论3 推论2 定理2 A是m×n矩阵（m≤n)则 但实际中A的秩不可能事先知道,而求rankA与求解线性方程组几乎等价,因而 的正定性也不能事先确定,因此(8)仅具有理论意义,而且即使 正定,也不用(8)去求(6)的解. 在 正定性不能确定时,可用QR分解法求解. 在 已知正定时,一般可用Cholesky分解求线性方程组(7). 下面讨论 (9) 的非线性最小二乘问题的求解. 与Newton法不同的是, 至少半正定的,而当 满秩时, Pk 为一下降方向,但与Newton法一样,并不能保证 ,而且只有当初始点充分接近于极小点 时,才能使算法收敛 在Newton迭代公式中(5)忽略 得: 而(10)称为法方程 (11) 从而构成(9)的Gauss-Newton法: (10) 5.3 Gauss-Newton法 定理3：设