最小二乘解的几何含义 根据最小二乘问题与正规方程的关系，我们可以把b 6 写成 b-Ax Ran(A) b=Ax+r,其中r⊥Ran(A): Ax. 所以Ax*就是b在Ran(A)上的正交投影，见右图 多需要指出的是，最小二乘解可能并不唯一，但上述分解是唯一的， http://math.ecnu.edu.cn/-jypan 5/20
最小二乘解的几何含义 根据最小二乘问题与正规方程的关系, 我们可以把 b 写成 b = Ax∗ + r, 其中 r⊥Ran(A). 所以 Ax∗ 就是 b 在 Ran(A) 上的正交投影, 见右图. 需要指出的是, 最小二乘解可能并不唯一, 但上述分解是唯一的. http://math.ecnu.edu.cn/~jypan 5/20
3-5-2 Cholesky分解法 多当A列满秩时，我们就可以使用Cholesky分解来求解正规方程 http://nath.ecnu.edu.cn/-jypan 6/20
3-5-2 Cholesky 分解法 当 A 列满秩时, 我们就可以使用 Cholesky 分解来求解正规方程. 计算复杂度 计算 A ⊺A: → mn 2 % 只需计算下三角或上三角部分 计算 Cholesky 分解: → 1 3 n 3 回代求解: → O(n 2 ) 总的运算量大约为 mn 2 + 1 3 n 3 + O(n 2 ) http://math.ecnu.edu.cn/~jypan 6/20
3-5-2 Cholesky分解法 多当A列满秩时，我们就可以使用Cholesky分解来求解正规方程. 计算复杂度 O计算ATA: mn2%只需计算下三角或上三角部分 )计算Cholesky分解： → ⑦回代求解：→ 0(m2) 总的运算大的为m2+行+0问 http://math.ecnu.edu.cn/-jypan 6/20
3-5-2 Cholesky 分解法 当 A 列满秩时, 我们就可以使用 Cholesky 分解来求解正规方程. 计算复杂度 计算 A ⊺A: → mn2 % 只需计算下三角或上三角部分 计算 Cholesky 分解: → 1 3 n 3 回代求解: → O(n 2 ) 总的运算量大约为 mn2 + 1 3 n 3 + O(n 2 ) http://math.ecnu.edu.cn/~jypan 6/20
Cholesky分解求解正规方程的优缺点 优点：运算量最小，简单直观 缺点：A「A的条件数是A的平方，对于病态问题，不建议使用 http://math.ecnu.edu.cn/-jypan 7/20
Cholesky 分解求解正规方程的优缺点 优点: 运算量最小, 简单直观. 缺点: A ⊺A 的条件数是 A 的平方, 对于病态问题, 不建议使用. 例 设 A = 1 1 1 ε ε ε , 则 A ⊺A = 1 + ε 2 1 1 1 1 + ε 2 1 1 1 1 + ε 2 . 记 εu 为机器精度, 则当 εu < ε < √ εu 时有 ε 2 < εu, 由于舍入误差的原因, 通过浮点 运算计算得到的 A ⊺A 是奇异的. 但我们注意到 A 是满秩的. http://math.ecnu.edu.cn/~jypan 7/20
Cholesky分解求解正规方程的优缺点 ⊙优点：运算量最小，简单直观 缺点：A「A的条件数是A的平方，对于病态问题，不建议使用 111 1+e2 1 例 设A= 1+e2 都记em为机器精度，则当eu<e<VE时有e2<eu,由于舍入误差的原因，通过浮点 运算计算得到的A「A是奇异的.但我们注意到A是满秩的 http://math.ecnu.edu.cn/-jypan 7/20
Cholesky 分解求解正规方程的优缺点 优点: 运算量最小, 简单直观. 缺点: A ⊺A 的条件数是 A 的平方, 对于病态问题, 不建议使用. 例 设 A = 1 1 1 ε ε ε , 则 A ⊺A = 1 + ε 2 1 1 1 1 + ε 2 1 1 1 1 + ε 2 . 记 εu 为机器精度, 则当 εu < ε < √ εu 时有 ε 2 < εu, 由于舍入误差的原因, 通过浮点 运算计算得到的 A ⊺A 是奇异的. 但我们注意到 A 是满秩的. http://math.ecnu.edu.cn/~jypan 7/20