课程主页：https://graphics.stanford.edu/courses/cs205a-13-fall/schedule.html

这次回顾第四讲，这一讲结束了LU分解的内容，介绍敏感性和病态性。

Chapter 3 设计和分析线性系统

回归

假设我们的函数有如下形式

如果我们有$m$个观测值，那么可以得到如下线性系统：

我们的任务是求解$(a_1,…,a_m)^T$，在继续之前，来看两个具体例子：

多项式回归

如果

那么此时称为多项式回归，对应的线性系统为：

Mini-Fourier

另一种常见的形式为

最小二乘法

考虑上述问题，我们自然希望

这等价于

最小化上述问题等价于最小化

化简可得

对上式关于$\vec x ​$求梯度可得

令上式为$0$可得

该方程被称为正规方程，下面对$A^TA​$这个矩阵做更多的讨论。

(半)正定矩阵和Cholesky分解

讨论之前先介绍一些基本概念：

对称性

显然$A^TA$是对称矩阵。

(半)正定性

注意到

所以$A^TA$是半正定矩阵，事实上，如果$A$可逆，那么$A^TA$是正定矩阵。

有了这些准备工作，考虑正定对称系统$C\vec x = \vec d$的求解，假设$C\in \mathbb R^{n\times n}$且$C$是对称矩阵，将$C$写为分块形式：

其中$\vec v \in \mathbb R^{n-1}, \tilde C \in\mathbb R^{(n-1)\times (n-1)} $。由$C​$的定义，不难得到：

其中最后一个不等号是因为正定性。回顾高斯消元法，这说明我们不需要对第一列选主元，那么使用高斯消元法，我们可以找到forward substitution矩阵$E​$，其中

使得

其中$ D \in\mathbb R^{(n-1)\times (n-1)} $。接着，由$C$的对称性，考虑使用列变换：

不难发现$D$也是正定对称矩阵，对$D$重复这个过程，最终不难得到

记

那么

注意到上述$L$并不唯一——对于正交矩阵$Q$，我们有

所以上述分解有无数种形式，特别的，如果我们取$L$为下三角矩阵，那么

被称为Cholesky分解，下面推导Cholesky分解的具体形式。

由定义，我们有

考虑$C_{ij}$，我们有

所以

以及

所以，对$i,j​$做循环即可计算得到$L_{ij}​$，伪代码如下：

// Takes as input an n-by -n matrix A[i,j]
// Edits A in place to obtain the Cholesky factorization in its lower triangle
for i from 1 to n {
    // Back - substitute to find l_i
    for j from 1 to i -1 { // element j of l_i
        sum = 0;
        for k from 1 to j -1
    		sum += A[i,k]*A[j,k];
    	A[i,j] = (A[i,j]-sum )/A[j,j];
    }
    // Apply the formula for l_kk
    normSquared = 0
    for k from 1 to i -1
    	normSquared += A[i,k ]^2;
    A[i,i] = sqrt (A[i,i] - normSquared );
}