数值计算(九)——线性代数方程组求解(一)高斯消元法
线性方程组求解
许多物理问题的数学模型最终都要归结为一个求解线性代数方程组的问题，如：电学中的网络问题，船体数学放样中建立三次样条函数问题，用最小二乘求实验数据的曲线拟合问题，用差分法或有限元解偏微分方程的边值问题等，因此掌握快速准确的求解线性代数方程组是极具必要性的，线性代数方程组的求解一般分为两大类别，直接求解和迭代求解两种方式，直接法是指在没有舍入误差的情况下经过有限次运算可求得方程组的精确解的方法，迭代法则是采取逐步逼近的方式，即从一个初始近似解出发，按某种迭代格式，逐步地向前推进，使其近似解逐步接近精确解，直到满足精度要求为止。
这时候长得比较帅的读者就会有疑问了，既然有直接求解方式，那为何还有搞一个迭代求解，求出来的结果还不是准确值的方法呢？其实是因为在实际问题的处理当中，经常会遇到运算量极大的高阶线性方程组，比如未知数的个数高达二十个，三十个甚至更多，求解这种问题使用直接法，对应的计算量将是一个天文数字，这时候我们不得已才选择计算近似解。
知识点补充
范数与赋范线性空间
详情请参考我之前的文章：数值计算(五)——函数逼近一致逼近多项式(1)
矩阵及其相关性质
矩阵范数：设
R
n
×
n
\mathbb{R}^{n\times n}
Rn×n表示所有的
n
n
n阶实方阵的集合，利用
R
n
\mathbb{R}^n
Rn上的向量范数，可以定义一种矩阵范数：若
∣
∣
⋅
∣
∣
\mid\mid\cdot\mid\mid
∣∣⋅∣∣是
R
\mathbb{R}
R上的任意范数，则对任一
A
∈
R
n
×
n
A\in\mathbb{R}^{n\times n}
A∈Rn×n,有
∣
∣
A
∣
∣
=
max
x
≠
0
∣
∣
A
x
∣
∣
∣
∣
x
∣
∣
=
max
∣
∣
x
∣
∣
=
1
∣
∣
A
x
∣
∣
\mid\mid A\mid\mid=\max\limits_{x\neq0}\frac{\mid\mid Ax\mid\mid}{\mid\mid x\mid\mid}=\max\limits_{\mid\mid x\mid\mid=1}\mid\mid Ax\mid\mid
∣∣A∣∣=x=0max∣∣x∣∣∣∣Ax∣∣=∣∣x∣∣=1max∣∣Ax∣∣称为A的由向量范数，
∣
∣
⋅
∣
∣
\mid\mid\cdot\mid\mid
∣∣⋅∣∣导出的矩阵范数，简称为A的从属范数。
（1）
∣
∣
A
∣
∣
1
=
max
j
∑
i
=
1
n
∣
a
i
j
∣
\mid\mid A\mid\mid_{1}=\max\limits_{j}\sum\limits_{i=1}^n\mid a_{ij}\mid
∣∣A∣∣1=jmaxi=1∑n∣aij∣称为列和范数
（2）∣
∣
A
∣
∣
∞
=
max
i
∑
j
=
1
n
∣
a
i
j
∣
\mid\mid A\mid\mid_{\infty}=\max\limits_i\sum\limits_{j=1}^n\mid a_{ij}\mid
∣∣A∣∣∞=imaxj=1∑n∣aij∣称为行和范数
（3）∣
∣
A
∣
∣
2
=
λ
m
a
x
\mid\mid A\mid\mid_{2}=\sqrt{\lambda_{max}}
∣∣A∣∣2=λmax称为谱范数
谱半径:设
A
∈
R
n
×
n
A\in\mathbb{R}^{n\times n}
A∈Rn×n,称其特征值的按模最大值
ρ
(
A
)
=
m
a
x
{
∣
λ
∣
:
λ
∈
σ
(
A
)
}
\rho(A)=max \{\mid\lambda\mid: \lambda\in\sigma(A) \}
ρ(A)=max{∣λ∣:λ∈σ(A)}为
A
A
A的谱半径，其中
σ
(
A
)
\sigma(A)
σ(A)表示
A
A
A的特征值全体。
正交矩阵和酉矩阵
设
A
=
[
a
i
j
]
∈
R
n
×
n
A=[a_{ij}]\in\mathbb{R}^{n\times n}
A=[aij]∈Rn×n,如果满足
A
T
A
=
I
A^TA=I
ATA=I，则称
A
A
A为正交矩阵正交矩阵有下列的性质
(1)
A
−
1
=
A
T
,
A
T
也
是
正
交
矩
阵
A^{-1}=A^T,A^T也是正交矩阵
A−1=AT,AT也是正交矩阵
(2)按照(
x
,
y
)
=
∑
i
=
1
n
x
i
y
i
(x,y)=\sum\limits_{i=1}^nx_iy_i
(x,y)=i=1∑nxiyi的向量内积定义，
A
A
A不同的列向量相互正交，且各列向量的
2
−
范
数
2-范数
2−范数都等于
1
1
1
(3)∣
d
e
t
A
∣
=
1
\mid detA\mid = 1
∣detA∣=1
(4)若A
,
B
A,B
A,B都是同阶的正交矩阵，则
A
B
AB
AB和
B
A
BA
BA均为正交矩阵
若
A
=
[
a
i
j
]
∈
R
n
×
n
A=[a_{ij}]\in\mathbb{R}^{n\times n}
A=[aij]∈Rn×n且满足
A
H
A
=
I
A^HA=I
AHA=I，则称
A
A
A为酉矩阵，酉矩阵有以下性质
(1)
A
−
1
=
A
H
,
A
H
A^{-1}=A^H,A^H
A−1=AH,AH也是酉矩阵
(2)按照(
x
,
y
)
=
∑
i
=
1
n
x
i
y
ˉ
i
(x,y)=\sum\limits_{i=1}^nx_i\bar y_i
(x,y)=i=1∑nxiyˉi的向量内积定义，
A
A
A不同的列向量相互正交，且各列向量的
2
−
范
数
2-范数
2−范数都等于
1
1
1
(3)∣
d
e
t
A
∣
=
1
\mid detA\mid = 1
∣detA∣=1
(4)若A
,
B
A,B
A,B都是同阶的酉矩阵，则
A
B
AB
AB和
B
A
BA
BA均为酉矩阵
其他的有关对称矩阵和对称正定矩阵，可约矩阵，对角占优矩阵等相关概念就留给你们思考了哦！
正交分解
条件数
对于方程组
A
x
=
b
Ax=b
Ax=b,当方程组的
A
A
A或
b
b
b有扰动时，引起解的相对误差完全由数
∣
∣
A
−
1
∣
∣
,
∣
∣
A
∣
∣
\mid\mid A^{-1}\mid\mid,\mid\mid A\mid\mid
∣∣A−1∣∣,∣∣A∣∣来决定，称此数为矩阵A的条件数，所以系数矩阵的条件数刻画了解对原始数据的敏感程度，条件数越小，由
A
(
或
b
)
A(或b)
A(或b)引起的解的相对误差就越小，称方程组是良态的，条件数越大，解的相对误差就可能越大，称为方程组是病态。
条件数的性质：
高斯消去法
\qquad
我们直到在高等代数中有个著名的克莱姆法则，使用克莱姆法则可以直接求解其对应的线性方程组，但是由于克莱姆法则计算的时间复杂度极大，为
O
(
n
!
(
n
2
−
1
)
)
O(n!(n^2-1))
O(n!(n2−1)),这是个什么概念呢？加入这是个20阶的线性方程组，使用我们自己个人计算机，也就是算力大约为每秒运算30亿次左右（主频
3.0
G
3.0G
3.0G）的计算机，大约得运行10000年，俗话说得好，一万年太久，我们只争朝夕。那么有没有更快些的直接求解方法呢？显然是有的。也就是我接下来讲的高斯消去法。
\qquad
讲的直白些就是将线性方程组的系数矩阵对应的增广矩阵化为上三角阵，说的low一点就是我们小学解多元一次方程组时所用的消元法。现在来看它高大上的数学表述：
我们要注意，使用高斯消去法时，一定要保证
A
11
A_{11}
A11这个元素是非零的，如果是零，我们要学会交换其中的两行再进行消元。
这种高斯消元法也存在致命的弊端：
将其进行改进得到列主元消去法：核心思想就是计算时要求列主元
a
k
k
(
k
)
a_{kk}^{(k)}
akk(k)尽可能的大些。
（1）每次消元前，选取一列的对角线及以下的元素中绝对值最大的作为主元素
（2）换行使之变到主元位置
（3）用这个主元素作除数，再进行消元计算
方法的优点：不增加求解过程中的运算量，还可以减少误差。