7
【数值计算】数值线性代数
source link: https://www.guofei.site/2021/06/12/numerical_linear_algebra.html
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
【数值计算】数值线性代数
2021年06月12日Author: Guofei
文章归类: 5-5-数值计算 ，文章编号: 5502
版权声明：本文作者是郭飞。转载随意，但需要标明原文链接，并通知本人
原文链接：https://www.guofei.site/2021/06/12/numerical_linear_algebra.html
基本问题
数值线性代数主要包括以下三个问题
- 解线性方程组的问题。给定 Ax=bAx=b，求 x
- 线性最小二乘问题。argminx∈Rn∣∣Ax−b∣∣2argminx∈Rn∣∣Ax−b∣∣2
- 求A的部分或全部 特征值、对应的 特征向量
数值线性代数的 必要性：线性代数的一些定理，证明过程非常漂亮，但对应的计算量大的惊人
设计算法的 主要技巧：矩阵分解。
敏度分析与误差分析，误差两个来源：原始数据本身的误差（可能来自测量）、计算过程产生的误差。所以需要两个理论
算法复杂度和收敛速度。
- 复杂度分析：90年代之前只考虑乘除，90年代后的计算机加减乘除速度相差无几，所以都考虑
- 不能完全依据运算量来评价算法快慢，现代计算机运算速度远高于数据传输数独，所以算法的速度很大程度上取决于数据传输两。
- 对于迭代算法，还需要分析收敛速度。∣∣xk−x∣∣≤c∣∣xk−1−x∣∣n∣∣xk−x∣∣≤c∣∣xk−1−x∣∣n 称为n次收敛，显然n越大越好
线性方程组消元法
Gauss消元法，适用于
- 中小规模的线性方程组，阶数不超过1000
- 系数矩阵稠密
- 没有任何特殊结构
思路：解方程 Ax=bAx=b，
- 把A分解为 A=P−1LUA=P−1LU,其中P是排列矩阵，L是下三角矩阵，U是上三角矩阵，
- 就可以把问题分解为：Ly=Pb,Ux=yLy=Pb,Ux=y，
- 三角矩阵对应的解法大为简化。
上面算法的问题：如果某主元不为0但很小，在计算机精度下的计算结果差很多。 解决：PAQ=LUPAQ=LU
对于正定矩阵，有更好的办法：
若 A 正定，那么纯在下三角矩阵 L，使得 A=LLTA=LLT（Cholesky分解定理）
分块矩阵：可以分块处理，大大节省内存和计算量
参考文献
《数值线性代数》北京大学出版社，徐高方
您的支持将鼓励我继续创作！
Recommend
About Joyk
Aggregate valuable and interesting links.
Joyk means Joy of geeK