秦 5 线性最小二乘问题的求解方法 5.1正规方程法 5.2QR分解法 5.3奇异值分解法 http://math.ecnu.edu.cn/~jypan 11/38
5 线性最小二乘问题的求解方法 5.1 正规方程法 5.2 QR 分解法 5.3 奇异值分解法 http://math.ecnu.edu.cn/~jypan 11/38
秦 5.1 正规方程法 定理设A∈Rmxn(m≥n),则x*∈R”是线性最小二乘问题的解当且仅当 残量r=b-Az*与Ran(A)正交，即x*是下面的正规方程的解 AT(b-Ax)=0AT Ax =ATb. (板书) http://math.ecnu.edu.cn/~jypan 12/38
5.1 正规方程法 定理 设 A ∈ R m×n (m ≥ n), 则 x∗ ∈ R n 是线性最小二乘问题的解当且仅当 残量 r = b − Ax∗ 与 Ran(A) 正交, 即 x∗ 是下面的正规方程的解 A ⊺ (b − Ax) = 0 或 A ⊺Ax = A ⊺ b. (板书) http://math.ecnu.edu.cn/~jypan 12/38
由于 秦 ATbE Ran(AT)=Ran(AT A) 因此正规方程ATAx=ATb总是相容的，即最小二乘解总是存在的，且当A满 秩时，这个解也是唯一的 定理设A∈Rmxm(m>n).则ATA对称正定当且仅当A是列满秩的，即 rank(A)=n.此时，线性最小二乘问题存在唯一解： x=(ATA)-1AT6 当A列满秩时，可以使用Cholesky分解来求解正规方程，总运算量大约 为mn2+5n3+O(n2),其中大部分(mn2)是用来计算A「A. 3 http://math.ecnu.edu.cn/~jypan 13/38
由于 A ⊺ b ∈ Ran(A ⊺ ) = Ran(A ⊺A) 因此正规方程 A ⊺Ax = A ⊺ b 总是相容的, 即最小二乘解总是存在的，且当 A 满 秩时, 这个解也是唯一的. 定理 设 A ∈ R m×n (m > n). 则 A ⊺A 对称正定当且仅当 A 是列满秩的, 即 rank(A) = n. 此时, 线性最小二乘问题存在唯一解: x = (A ⊺A) −1A ⊺ b ✍ 当 A 列满秩时, 可以使用 Cholesky 分解来求解正规方程, 总运算量大约 为 mn2 + 1 3 n 3 + O(n 2 ), 其中大部分 (mn2 ) 是用来计算 A ⊺A. http://math.ecnu.edu.cn/~jypan 13/38