基本问题
数值线性代数主要包括以下三个问题
- 解线性方程组的问题。给定 $Ax=b$，求 x
- 线性最小二乘问题。$\arg\min\limits_{x\in R^n} \mid\mid Ax-b \mid\mid_2$
- 求A的部分或全部 特征值、对应的 特征向量
数值线性代数的 必要性：线性代数的一些定理，证明过程非常漂亮，但对应的计算量大的惊人
设计算法的 主要技巧：矩阵分解。
敏度分析与误差分析，误差两个来源：原始数据本身的误差（可能来自测量）、计算过程产生的误差。所以需要两个理论
- 敏度分析
- 误差分析
算法复杂度和收敛速度。
- 复杂度分析：90年代之前只考虑乘除，90年代后的计算机加减乘除速度相差无几，所以都考虑
- 不能完全依据运算量来评价算法快慢，现代计算机运算速度远高于数据传输数独，所以算法的速度很大程度上取决于数据传输两。
- 对于迭代算法，还需要分析收敛速度。$\mid\mid x_k-x \mid\mid \leq c\mid\mid x_{k-1}-x \mid\mid^n$ 称为n次收敛，显然n越大越好
线性方程组消元法
Gauss消元法，适用于
- 中小规模的线性方程组，阶数不超过1000
- 系数矩阵稠密
- 没有任何特殊结构
思路：解方程 $Ax=b$，
- 把A分解为 $A=P^{-1}LU$,其中P是排列矩阵，L是下三角矩阵，U是上三角矩阵，
- 就可以把问题分解为：$Ly=Pb,Ux=y$，
- 三角矩阵对应的解法大为简化。
上面算法的问题：如果某主元不为0但很小，在计算机精度下的计算结果差很多。 解决：$PAQ=LU$
对于正定矩阵，有更好的办法：
若 A 正定，那么纯在下三角矩阵 L，使得 $A=LL^T$（Cholesky分解定理）
分块矩阵：可以分块处理，大大节省内存和计算量
参考文献
《数值线性代数》北京大学出版社，徐高方
