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

第5章 线性与非线性最小二乘问题 §5.1 前言 1801年,意大利天文学家朱赛普·皮亚齐发现了第一颗小行星谷神星.经过40天的跟踪观测后,由于谷神星运行至太阳背后，使得皮亚齐失去了谷神星的位置。随后全世界的科学家利用皮亚齐的观测数据开始寻找谷神星,但是根据大多数人计算的结果来寻找谷神星都没有结果.时年24岁的高斯也计算了谷神星的轨道.奥地利天文学家海因里希·奥尔伯斯根据高斯计算出来的轨道重新发现了谷神星. 高斯使用的最小二乘法的方法发表于1809年他的著作《天体运动论》中. 而法国科学家勒让德于1806年独立发现“最小二乘法”,但因不为时人所知而默默无闻.两人曾为谁最早创立最小二乘法原理发生争执. 1829年,高斯提供了最小二乘法的优化效果强于其他方法的证明,称为高斯-马尔可夫定理. 无约束最优化问题最小二乘的形式 称为残量函数 是x的线性函数 线性最小二乘问题 §5.2 线性最小二乘问题的解法 解线性最小二乘问题 设 为 阶矩阵, 为m维 向量,线性最小二乘问题为求 的最优解. 其中 为向量的范数.将 按范数 展开得 对称矩阵 至少半正定 任一最优解都是全局最优解 凸优化问题 当向量b属于矩阵A的像空间 则存在 使 否则问题的最优 值不为零. 设 为问题的最优解 不一定为零. 一阶必要条件 是问题的最优解 法方程组 A列满秩 正规方程组 正定 方程组的解唯一且可表示为 矩阵A的广义逆 作为一个二次函数的无约束优化 对方程组的求解，一般采用矩阵 的Cholesky分解 ，其中L下三角矩阵 如果矩阵 正定 对于线性最小二乘问题，我们可以利用其问题的特殊结构，设计更为有效的求解方法。对于线线性最小二乘问题形成的矩阵 不宜采用 先计算矩阵 再对它进行分解的方法 的条件数是矩阵A的条件数的平方 因为矩阵 对称矩阵的三角分解定理 设A为n阶对称矩阵,且A的所有顺序主子式均不为零, 则A可唯一分解为 其中L为单位下三角矩阵,D为对角矩阵. 对称正定矩阵的三角分解或Cholesky分解 设A为n阶对称正定矩阵, 当限定L的对角元素为正时,这种分解是唯一的. 则存在一个实的非奇异下三角 矩阵L使得 矩阵的QR分解 为避免计算乘积矩阵 再进行分解，可以采用 对增广矩阵 作QR正交分解的方法。 设A列满秩 其中Q为m×m阶正交矩阵 为n×n上三角矩阵 因此最优解x*可由三角方程组 经回代确定 求线性最小二乘问题最优解正交分解算法如下: 步1. 对增广矩阵[A b]作QR正交分解得 和向量 步2. 取 为向量 的前n个分量形成的向量 步3. 用回代解方程组 得解 在上述QR正交分解算法的分析过程中我们假定矩阵A的列线性无关. 当矩阵A的列线性相关,即A不是列满秩时, 矩阵A的QR正交分解 是一个r×r非奇异的上三角矩阵 r=rank(A)＜n表示矩阵A的秩数 表示由 向量 的前r个分量组成的向量 这时确定最优解的方程组 利用矩阵A的奇异值分解 设A为m×n (m＞n) 阶矩阵 则存在m×m阶正交矩阵U和n×n阶正交矩阵V 使得 其中S为m×n阶的块对角矩阵 为r×r阶对角矩阵 为矩阵A的奇异值 A的秩为r＜n 最小二乘法解不唯一 极小范数最小二乘解 规范最小二乘解 范数最小 其中 是最小二乘问题所有解的集合. 即在所有最小二乘解中 当r=n时,最小二乘解唯一 由奇异值分解所确定的矩阵 §5.3 非线性最小二乘的 Gauss- Newton法 考虑非线性最小二乘问题 其中 为 的非线性函数，称为残量函数. 如果函数r(x)二阶连续可微，则f(x)的一阶和二阶导数(Hesse矩阵)分别为 牛顿法 拟牛顿法 算法 (Gauss-Newton法) 步1. 给定解的初始估计 置k=1; 步2. 如果 满足精度要求,停止迭代; 步3. 解方程组 步4. 置 k:=k+1后转步2;