Chapt-5.解线性代数方程组的直接法

问题描述：$n$阶线性代数方程组 \(AX=b\\ A=\begin{bmatrix} a_{11} & a_{12} & \cdots & a_{1n} \\ a_{21} & a_{22} & \cdots & a_{2n} \\ \vdots & \vdots & \ddots & \vdots \\ a_{n1} & a_{n2} & \cdots & a_{nn} \\ \end{bmatrix} , X=\begin{bmatrix} x_{1} \\ x_{2} \\ \vdots \\ x_{n} \end{bmatrix} , b=\begin{bmatrix} b_{1} \\ b{2} \\ \vdots \\ b_{n} \end{bmatrix}\)

高斯消去法

顺序高斯消去法

• 通过初等变换将方程组转化为等价的三角形方程组

• 消元计算公式归纳（代码填空）

1. 输入A、b和ε
2. 消元
	for k=1 to n-1 do
        for i=k+1 to n do
            T=a[i,k]/a[k,k]
            b[i]-=T*b[k]
            for j=k+1 to n do
            a[i,j]-=T*a[k,j]
3. 回代
	if |a[n,n]<=ε
		求解失败
	else
		x[n]=b[n]/a[n,n]
		for i=n-1 downto 1 do
        	sum=0
            for j=i+1 to n
            	sum+=a[i,j]*x[j]
			x[i]=(b[i]-sum)/a[i,i]

• 高斯消去法计算量

列主元高斯消去法

• 顺序高斯消去法的问题：消元过程中，如果$a_{kk}^{(k)}\rarr0$，作为除数会导致其他元素量级增长和舍入误差的扩散，引起解的失真，小主元是不稳定的根源；列主元法通过交换行的初等变化选择最大的$a_{kk}^{(kk)}$
• 列主元伪代码：

1. 输入A、b和ε
2. 选主元和消元
	for k=1 to n-1 do
		选主元：T=a[i_k,k]
		for i=k to n do
			T=max(T,a[i,k])
		if T<ε
			求解失败
		else
			交换A的第i_k行和第k行，交换b[t]和b[k]

		for i=k+1 to n do
			T=a[i,k]/a[k,k]
			b[i]-=T*b[k]
			for j=k+1 to n do
				a[i,j]-=T*a[k,j]
3. 回代
	if |a[n,n]<=ε
		求解失败
	else
		x[n]=b[n]/a[n,n]
		for i=n-1 downto 1 do
        	sum=0
            for j=i+1 to n
            	sum+=a[i,j]*x[j]
			x[i]=(b[i]-sum)/a[i,i]

• 列主元计算量

全主元高斯消去法

• 全主元和列主元类似，不同的是选取主元的范围不同；全主元在整个$A$中寻找绝对值最大的元素作为主元，将舍入误差控制在一个最小的范围；缺点是找主元和交换行列要花费大量机器时间
• 全主元伪代码

1. 输入A、b和ε
2. for i=1 to n do d[i]=i //记录未知量位置的变换
3. 选主元和消元
	for k=1 to n-1 do
		选主元：T=a[i_k,j_k]
		for i=k to n do
			for j=k to n do
				T=max(T,a[i,j])
		if T<ε
			求解失败
		else
			交换A的第i_k行和第k行，交换b[t]和b[k]
			交换A的第j_k列和第k列，交换d[j_k]和d[k]

		for i=k+1 to n do
			T=a[i,k]/a[k,k]
			b[i]-=T*b[k]
			for j=k+1 to n do
				a[i,j]-=T*a[k,j]
4. 回代
	if |a[n,n]<=ε
		求解失败
	else
		z[n]=b[n]/a[n,n]
		for i=n-1 downto 1 do
        	sum=0
            for j=i+1 to n
            	sum+=a[i,j]*x[j]
			z[i]=(b[i]-sum)/a[i,i]
	for j=1 to n do
		x[d[j]]=z[j]

• 全主元计算量

LU 分解法

• 高斯消去法将方程组 $A^{(1)}X=b^{(1)}$ 通过初等变换等价转换为上三角型方程组$A^{(k)}X=b^{(k)}$，表示为$A^{(n)}=M_{n-1}M_{n-2}…M_{1}A^{(1)}$，则有 $A^{(1)}=M_{1}^{-1}M_{2}^{-1}…M_{n-1}^{-1}A^{(n-1)}$，其中$M^{-1}_{i}$ 均为下三角矩阵且对角线元素为1
• 记 $L=M_{1}^{-1}M_{2}^{-1}…M_{n-1}^{-1}$， $U=A^{(n)}$，只要方程 $AX=b$的所有顺序主子式不为零， $A$一定可以分解成 $A=LU$

上述计算公式有如下的特点：$U$的元素按行逐行求，$L$的元素按列逐列求

• LU分解伪代码

1. 输入A、b和ε
2. 
	for k=1 to n do
		for j=k to n do
			sum[k,j]=0
			for m=1 to k-1 do
            	sum[k,j]+=l[k,m]*u[m,k]
			u[k,j]=a[k,j]-sum[k,j]
        for i=k+1 to n do
        	sum[i,k]=0
        	for m=1 to k-1 do
        		sum[i,k]+=l[i,m]*u[m,k]
        	l[i,k]=(a[i,k]-sum[i,k])/u[k,k]
3. 求解 LY=b
4. 求解 UX=Y

对称正定矩阵的平方根法和LDLT分解法

• 正定矩阵：$n\times n$的实对称矩阵$A$是正定的当且仅当对于所有的非零实系数向量$X$，$X^TAX>0$

• 定理：对于线性代数方程组$AX=b$，$A$是$n$阶堆成矩阵，且A的所有顺序主子式均不为零，$A$可以分解为： \(A=LDL^T \\ \begin{bmatrix} a_{11} & a_{12} & \cdots & a_{1n} \\ a_{12} & a_{22} & \cdots & a_{2n} \\ \vdots & \vdots & \ddots & \vdots \\ a_{n1} & a_{n2} & \cdots & a_{nn} \\ \end{bmatrix}= \begin{bmatrix} 1 & \\ l_{12} & 1 \\ \vdots & \vdots & \ddots \\ l_{n1} & l_{n2} & \cdots & 1 \\ \end{bmatrix} \begin{bmatrix} d_{11} & \\ & d_{22} \\ & & \ddots \\ & & & d_{nn} \\ \end{bmatrix} \begin{bmatrix} 1 & l_{21} & \cdots & l_{n1} \\ & 1 & \cdots & l_{n2} \\ & & \ddots & \vdots \\ & & & 1 \\ \end{bmatrix} \\\)

• 定理：$n$阶对称正定矩阵$A$一定有$Clolesky$分解，是一种特殊的$LU$分解：

• 平方根伪代码

1. 输入A、b和ε
2. 
	for k=1 to n do
		sum_1[k]=0
		for m=1 to k-1 do
        	sum_1[k]+=l[k,m]*l[k,m]
        S[k]=a[k,k]-sum[k]
       	

• 为了避免开方操作，可对$A$做LDLT分解法，LDLT分解法需要借助LU分解法

先利用LU分解法计算出$U$的第$k$行，由$U$的第$k$行得到$D$的第$k$个对角元素和$L$的第$k$列，即 \(\left\{ \begin{aligned} &d_{i}=u_{ii} \\ &l_{ik}=u_{ki}/u_{kk} \end{aligned} \right.\)

向量和矩阵范数

向量范数

• 向量范数是$n$维欧几里得空间中长度概念的推广，一种距离的度量方式

• 向量范数定义：设向量$X\in R^n$，其范数$\vert X\vert $是非负实数，满足三个条件：

  • 非负性：$\vert X\vert =0$当且仅当$X=0$
  • 齐次性：$\vert \alpha X\vert =\vert \alpha\vert \cdot\vert X\vert $
  • 三角不等式：$\vert X+Y\vert \leq\vert X\vert +\vert Y\vert $
  • 常用范数：
    • 1范数：$\vert X\vert 1=\sum\limits{i=1}^n\vert x_i\vert $
    • 2范数：$\vert X\vert 2=(\sum\limits{i=1}^n\vert x_i\vert ^2)^{\frac{1}{2}}$
    • $\infty$范数：$\max\limits_{1\le i\le n}\vert x_i\vert $
    • $p$范数：$\vert X\vert p=(\sum\limits{i=1}^{n}(\vert x_i\vert ^p))^{\frac{1}{p}}$

• 范数等价定义：设$R^n$的两种范数$\vert \cdot\vert _\alpha$和$\vert \cdot\vert _\beta$，如果存在和$X$无关的两个正常数$C_1$和$C_2$，使得不等式$C_1\vert X\vert _\alpha\le \vert X\vert _\beta\le C_2\vert X\vert _\alpha$成立，则称这两个范数等价

  • 定理：有限维空间上任何两种范数均等价（使用哪种范数都可以）

• 向量序列收敛定义：设 $\}$ 是$R^n$中的向量序列，如果有向量 $X^*\in R^n$ ，使得

  \[\lim\limits_{k\rightarrow\infty}\vert X^{(k)}-X^*\vert =0\]

  则称 ${X^{(k)}}$ 收敛于 $X^*$ ，表示为

  \[\lim\limits_{k\rightarrow \infty}X^{(k)}=X^*\]
  • 定理：向量序列 ${X^{(k)}}$ 收敛于 $X^$ 当且仅当 $\lim\limits_{k\rightarrow \infty}x_j^{(k)}=x_j^$ ，下标 $j$ 表示向量的第 $j$ 个分量

矩阵范数

• 矩阵范数定义：设矩阵 $A\in R^{n\times n}$ ，其范数 $\vert A\vert $ 是非负实数，满足四个条件

  • 非负性、齐次性、三角不等式
  • 乘法不等式： $\vert A\cdot B\vert \le \vert A\vert \cdot\vert B\vert $

• 矩阵的算子范数定义：设 $X\in R^n,A\in R^{n\times n}$ ,给定向量范数 $\vert X\vert _v$ ，定义由向量诱导得到的矩阵范数

  \[\vert A\vert _v=\max\limits_{X\ne0}\frac{\vert AX\vert _v}{\vert X\vert _v} =\max\limits_{\vert X\vert =1}\vert AX\vert _v\]
  • 矩阵范数和向量范数相容的定义：满足 $\vert AX\vert \le \vert A\vert \cdot\vert X\vert $
  • 定理：诱导矩阵范数 $\vert A\vert $ 是相容的
  • 定理： $\vert A\vert =\max\limits_{\vert X\vert =1}\vert AX\vert $ 是一种矩阵范数

• 矩阵序列收敛定理：设 ${A^{(k)}}$ 是 $R^{n\times n}$ 的矩阵系列，如果有矩阵 $A\in R^{n\times n}$ ，则

  \[\lim\limits_{k\rightarrow \infty}\vert A^{(k)}-A\vert =0\]

  当且仅当

  \[\lim\limits_{k\rightarrow \infty}a_{ij}^{(k)}=a^{ij}\]

谱半径

• 谱半径定义：$A\in R^{n\times n}$ ，其特征值为 $\lambda_i$ ， $A$ 的谱半径表示为

  \[\rho(A)=\max\limits_{1\le i\le n}\vert \lambda_i\vert\]
  • 定理： $A$ 的谱半径不超过 $A$ 的任意一个矩阵范数， $\rho(A)\le \vert A\vert $
  • 定理： $A$ 的幂收敛于零，即 $\lim\limits_{k\rightarrow \infty}A^k=0$ 当且仅当 $\rho(A)<1$

• Previous
  Chapt-4.数值积分
• Next
  Chapt-6.解线性代数方程组的迭代法