第4章 线性与非线性最小二乘问题.ppt

第4章 线性与非线性最小二乘问题 §4.1 线性最小二乘问题的解法 定理4.3.1 设 是方程组 对某一给定 的解,则 也是下述信赖域问 题的全局最优解: 其中 。 信赖域型的Levenberg-Marquardt方法 算法5.3.2 (解非线性最小二乘问题的信赖域方法) * * 4.1.1 解线性最小二乘问题 设 为 阶矩阵, 为m维 向量,线性最小二乘问题 。 为求下述最优化问题的最优解: （4.1.1） 其中 为向量的范数.将 按范数 展开得 这是一个以对称矩阵 为二阶Hesse矩阵的 二次函数的无约束极小化问题.由于矩阵 至少 半正定,问题的任何最优解也是问题的全局最优解.设 为问题的最优解,如果 ,则必有 ,如果mn ,则 不一定为零. 当向量b属于矩阵A的像空间 则存在 使 ,否则问题的最优 值不零.由于线性最小二乘问题是一个凸二次函数的无约束极小化,由 约束最优化问题最优解的一阶必要条件, ，根据无 问题（4.1.1）的最优解是方程组 （4.1.2） 的解.方程组（4.1.2）称为法方程组或正规方程组.如果矩阵A列满秩,即A的列线性无关,则矩阵 正定,方程组的解唯一且可表示为 其中 阶矩阵 称为 阶矩阵A的广义逆.对于这样一个线性最 小二乘问题我们可以用解一般凸二次函数的无约束最优化方法求解，例如解方程组 （5.1.2） 的直接解法，或迭代法，如共轭梯度法等。 作为一个二次函数的无约束优化，如果矩阵 正定，对方程组（4.1.2)的求解，一般采用矩阵 的Cholesky分解 ，其中L下三角矩阵 。 然而对于线性最小二乘问题，我们可以利用其问题的特殊结构，设计更为有效的求解方法。对于由线性最小二乘问题形成的矩阵 ，不宜采用 先计算矩阵 再对所得积矩阵进行分解的方 法，这样做既可以避免积矩阵的计算，又可以避免计算过程中舍入误差的影响，因为矩阵 的条件数是矩阵A的条件数的平方。设矩阵 存在误差E，由误差E所引起的解的误差为 则由方程组（4.1.2）和 可得 关于 的相对误差与E与 误差之间有如下关系： 的相对 其中 是矩阵 的条件数， 和 分别是矩阵Ａ的最大和最小奇异值． 下面的例子是Ｇill和Ｍurry（１９９１）出的，它说明矩阵 的条件数是矩阵A的条件数的 平方．设 则矩阵Ａ的条件数为 而相应的矩阵 的条件数为 可见， 的条件数要大大大于矩阵Ａ的条件 数，因此计算积矩阵，再分解后求解的方法不 是一个可取的方法． 为避免计算积矩阵 再进行分解，可以采用 对增广矩阵 作QR正交分解的方法。 我们知道 范数在正交变换下具有不变性,即 设 和 其中Q为m×m阶正交矩阵, 为n×n上三角矩阵。于是由 有 因此最优解x*可由三角方程组 经回代确定,其中 这时由于矩阵 的条件数即为矩阵A的条件数 ,通过上述方程组确定的最优解的相对误差要远 小于通过先计算积矩阵再分解后所求得解的相 对误差,这种情况在A的条件数较大时尤为明显. 求线性最小二乘问题最优解正交分解算法如下: 算法5.1.1 (线性最小二乘的正交分解算法) 步1. 对增广矩阵[A b]作QR正交分解得 和向量 步2. 取 为向量 的前n个分量形成的向量 步3. 用回代解方程组 得解 在上述QR正交分解算法的分析过程中我们假定矩阵A的列线性无关.当矩阵A的列线性相关,即A不是列满秩时,在上述矩阵A的QR正交分解式中, 不再是一个n×n而是r×n阶的上三角 矩阵,而确定最优解的方程组成为 (4.1.3) 其中r=rank(A)＜n表示矩阵A的秩数, 表示由 向量 的前r个分量组成的向量.方程组(4.1.3)有 无穷多组解,我们依矩阵A的奇异值分解算法,从中确定使 范数最小的解 ,即 其中 是最小二乘问题(5.1.1)所有解的集合. 设m×n (m＞n) 阶矩阵A的秩为r＜n,则存在m×m阶正交矩阵U和n×n阶正交矩阵V使得 其中S为m×n阶的块对角矩阵, 为r×r阶对角矩阵, σ1≥σ2≥…≥σr＞0为矩 阵A的奇异值.满足上述要求使用范数取极小的 最优解为 这里A+是矩阵A的广义逆 而 当r=rank(A)=n时,由奇异值分解所确定的矩阵 即为前述定义的广义逆矩阵 4.1.2 解线性等式约束的线性最小二乘问题 下面讨论带有线性约束的线性最小二乘问题,先 考虑线性等式约束的线性最小二乘问题 其中 ,并假定rank(C)=p即约束方程组相容. 求解上式问题最直接的方法是用等式约束消去 部分变量把问题转化为无约束线性最小二乘问题 求解.由于矩阵C行满秩,可