【计算方法】线性方程组的数值解法

Posted by ShawnD on December 15, 2020

线性方程组的性态和条件数

最常用的条件数有以下两种:

  • $cond(A)\infty = | A |{\infty} |A^{-1}|_{\infty}$
  • $cond(A)2 = |A|_2|A^{-1}|_2 = \sqrt{\frac{\lambda{max}(A^TA)}{\lambda_{min}(A^TA)}}$

$cond(A)\infty = | A |{\infty} |A^{-1}|_{\infty}$

当A为对称矩阵时:

\[cond(A)_2 = \frac{\mid \lambda_1 \mid}{\mid \lambda_n \mid}\]

当$cond(A) » 1$时,原始数据即使有很小的扰动, 解的误差可能很大。

条件数的性质如下:

  • 对任何非奇异矩阵都有$cond(A) \geq 1$, 事实上:
\[cond(A) = \|A\|\|A^{-1}\| \geq \|AA^{-1}\| = 1\]
  • 设A为非奇异矩阵且$c \neq 0$(常数), 则:
\[cond(cA) = cond(A)\]
  • 如果A为正交矩阵, 则$cond(A)_2 = 1$; 如果A为非奇异阵矩阵, R为正交矩阵, 则:
\[cond(RA)_2 = cond(AR)_2 = cond(A)_2\]

正交矩阵:

\[A^TA = E\]

基于矩阵三角分解的方法

LU分解

矩阵LU分解的存在唯一性: 对$n$阶矩阵$A$, 如果它的各项顺序主子式$D_i \neq 0, i=1, 2, …, n$, 则A可分解为一个单位下三角矩阵$L$和一个上三角矩阵$U$的乘积, 且这种分解是唯一的。

追赶法

**追赶法实际上就是把LU分解用到求解三对角线性方程组上去的结果。 **

迭代法

雅克比迭代法(Jacobi)迭代法

高斯-赛德尔(Gauss-Seidel)迭代法

收敛

按行严格对角占优: 矩阵A的每一行对角元素的绝对值都严格大于该行非对角元素绝对值之和。

  • 如果雅克比迭代法和高斯-赛德尔迭代法的迭代矩阵的任何一种算子范数小于1, 则这两种迭代法必定收敛。
  • 系数矩阵按行严格对角占优, Jacobi和Gauss-Seidel收敛
  • 系数矩阵是正定矩阵, Gauss-Seldel收敛

超松弛迭代法

对称正定矩阵 超松弛迭代收敛的充分必要条件: 松弛因子 $\omega$ 满足 $0 < \omega < 2$