消元法（上三角阵）

Gauss消元法

以\(3\times3\)为例, \[ \left\{\begin{matrix} a_{11}^{(1)}x_1 & +a_{12}^{(1)}x_2 & +a_{13}^{(1)}x_3 &= b_{1}^{(1)}\\ a_{21}^{(1)}x_1 & + a_{22}^{(1)}x_2 & + a_{23}^{(1)}x_3 &= b_{2}^{(1)} \\ a_{31}^{(1)}x_1 & +a_{32}^{(1)}x_2 & +a_{33}^{(1)}x_3 &= b_{3}^{(1)} \end{matrix}\right. \] 第一次消元 \[ \left\{\begin{matrix} a_{11}^{(1)}x_1 & +a_{12}^{(1)}x_2 & +a_{13}^{(1)}x_3 &= b_{1}^{(1)}\\ 0& a_{22}^{(2)}x_2 & + a_{23}^{(2)}x_3 &= b_{2}^{(2)} \\ 0& a_{32}^{(2)}x_2 & +a_{33}^{(2)}x_3 &= b_{3}^{(2)} \end{matrix}\right. \] 第二次消元 \[ \left\{\begin{matrix} a_{11}^{(1)}x_1 & +a_{12}^{(1)}x_2 & +a_{13}^{(1)}x_3 &= b_{1}^{(1)}\\ 0& a_{22}^{(2)}x_2 & + a_{23}^{(2)}x_3 &= b_{2}^{(2)} \\ 0& 0 & a_{33}^{(3)}x_3 &= b_{3}^{(3)} \end{matrix}\right. \]

总结算法:!!!!!!!!!!!!!!!!! \[ \left\{\begin{matrix} \\ \\ \end{matrix}\right. \]

定理: \(A\)可以进行Gauss消元,即\(a_{ii}^i\neq 0,i=1,\cdots,k\Leftrightarrow A\)的各阶顺序主子式不为0.

证明: \(\Leftarrow\) 当\(k=1\)时,\(D_1=a_{11}^{(1)}\neq 0\),显然成立. 若充分性对\(k-1\)成立,即当\(D_i\neq 0,i=1,\cdots,k-1\),有\(a_{ii}^{(i)}\neq 0,i=1,\cdots,k-1\). 往证,当\(D_k\neq 0\)时,有\(a_{kk}^{(k)}\neq 0\).

推论: 如果\(A\)的各阶顺序主子式\(D_k\neq 0\),则 \[ a_{11}^{(1)}=D_1,\cdots,a_{kk}^{(k)}=\frac{D_k}{D_{k-1}},\cdots \]

Gauss列主元

若有\(a_{kk}^{(k)}\approx 0\)会把舍入误差放大,引起解的失真.为了避免Gauss消元法的这种局限性,我们选取列主元后再进行消元,精确度就有不错的提高.

Gauss全主元

一般情况下,选取列主元再消元的列主元消元法已经可以满足精度需求,但是再一些情况下,我们需要更高的精度,我们可以尝试全主元消元法提高精度和稳定性.

消元法和矩阵分解的关系

初等矩阵: 由单位矩阵经过一次初等变换得到的矩阵.

用得到的说明 \[ l_{i1}=\frac{a^{(1)}_{i1}}{a_{11}^{(1)}},\quad L_{1}^{-1}A=A^{(2)}\\ l_{ik}=\frac{a^{(k)}_{ik}}{a_{kk}^{(k)}},\quad L_{k}^{-1}A^{(k)}=A^{(k+1)}\\ \vdots\\ A^{(k+1)}=L_{k}^{-1}L_{k-1}^{-1}\cdots L_{1}^{-1}A^{(1)}=L_{k}^{-1}L_{k-1}^{-1}\cdots L_{1}^{-1}A \] 若\(A\)为\(n\)阶方阵,则需要进行\(n-1\)次消元于是有 \[ A^{(n)}=L_{n-1}^{-1}L_{n-2}^{-1}\cdots L_{1}^{-1}A^{(1)} \] 记, \[ L=L_1L_2\cdots L_{n-1}\\ L^{-1}=L_{n-1}^{-1}L_{n-2}^{-1}\cdots L_{1}^{-1}\\ U=A^{(n)} \] 于是就有, \[ U=L^{-1}A,\quad A=LU \]

\[ L_{1}=\left(\begin{array}{cccc} 1 & & & \\ l_{21} & 1 & & \\ l_{31} && 1 & & \\ \vdots & && \ddots & \\ l_{n 1} & && & 1 \end{array}\right) L_{k}=\left(\begin{array}{cccccc} 1 & & & & & \\ & 1 & & & & \\ & & \ddots & & & \\ & & &1 & & \\ & & &l_{k+1,k} & 1 & & \\ & && \vdots & & \ddots & \\ & && l_{n k} && & 1 \end{array}\right) \] \[ L_{1}^{-1}=\left(\begin{array}{cccc} 1 & & & \\ -l_{21} & 1 & & \\ -l_{31} && 1 & & \\ \vdots & && \ddots & \\ -l_{n 1} & && & 1 \end{array}\right) L_{k}^{-1}=\left(\begin{array}{cccccc} 1 & & & & & \\ & 1 & & & & \\ & & \ddots & & & \\ & & &1 & & \\ & & &-l_{k+1,k} & 1 & & \\ & && \vdots & & \ddots & \\ & && -l_{n k} && & 1 \end{array}\right) \]

定理: 若\(A\)的各阶顺序主子式不为0,则\(A\)必可以分解成一个下三角阵与一个上三角阵的乘积. \[ A=LU \] 下三角的对角线元素全为\(1\),上三角的对角线元素不为\(0\).

Proof: (存在性)显然. (唯一性)用反证法.若不然,有\(A=LU=L'U'\)！！！！！！！！！！ 则有 \[ L^{-1}L'=U(U')^{-1} \]

矩阵的三角分解

Doolittle 三角分解

计算流程！！！！

计算流程(自己算一下) \[ A=\left(\begin{array}{rrrr} 2 & 4 & 2 & 0 \\ 2 & 3 & 6 & 0 \\ 0 & 4 & 2 & 24 \\ 0 & 0 & 5 & 1 \end{array}\right) \] ## Crout 分解

定理: 若\(A\)的各阶主子式不为0,则\(A\)必可以分解成一个下三角阵与一个上三角阵的乘积. \[ A=LU \] 其中\(L\)为下三角阵,\(U\)为单位上三角阵.

Proof: \(A^{T}\)也有LU分解,即, \[ A^{T}=LU \] 其中\(L\)为单位下三角阵,则, \[ A=U^{T}L^{T} \] 得证.

(用这分解算算上面的A)

三对角阵的追赶法

设方程组\(AX=d\),其中, \[ \left(\begin{array}{l} a_{1} & b_{1} & & & & \\ c_{2} & a_{2} & b_{2} & & & \\ & c_{3} & a_{3} & b_{3} & \\ & & \ddots & \ddots & \ddots & \\ && & \ddots & \ddots & b_{n-1}\\ &&&&c_n&a_n \end{array}\right) \]

主对角线严格占优

10.21

对称正交阵的平方根法

对称阵的\(LDL^T\)分解

定理: 若\(A\)为\(n\)阶方阵,且其各阶顺序主子式不为零,则当\(A\)对称时,可唯一分解为\(LDL^T\),其中\(L\)为单位下三角阵,\(D\)为对角阵.

Proof: 显然,由定理条件可知,\(A\)可以进行LU分解. \[ A=LU \] 其中, \[ L=\left(\begin{array}{cccc} 1 & & & \\ l_{21} & 1 & & \\ l_{31} &l_{32}& 1 & & \\ \vdots & \vdots&& \ddots & \\ l_{n 1} &l_{n2} &\cdots&l_{n,(n-1)} & 1 \end{array}\right) \] !!!!!!!!!!!!!!

对称正定阵的平方根法(\(LL^T\)分解、Cholesky分解)

定理: 若\(A\)为\(n\)阶对称正定阵,则存在一个实非奇异下三角阵\(L\),使得 \[A=LL^T\] 当限定\(L\)的对角元为正时,分解唯一.

Proof: !!!!!!!!!!!!!!!!!!

计算流程

Gauss-Jordan 求逆矩阵

内容

\((A\ |\ I)\Rightarrow(I\ |\ A^{-1})\)

思想

Gauss消元法+对角线全消+对角元归一化

计算例题

矩阵的正交三角化及应用

初等反射阵与 Household 变换

基本内容

定义:

定理: 设\(w^Tw=1,H(w)=I-2ww^T\)为初等反射阵,则:

• \(H\)为对称阵
• \(H\)为正交阵
• 若\(A\)为对称阵,则\(A_1=H^{-1}AH=HAH\)也对称

Proof:

• 因

任意向量构造初等反射阵

初等反射阵的几何意义

• \(w\) 与 \(X-HX\) 平行
• \(||X||_2=||HX||_2\)

初等反射阵计算意义

通过选取合适的\(w\),使得对任意的\(X\neq 0\),存在一个\(H(w)\),满足 \[ HX=-\sigma e_1,\quad where\ \sigma=\pm||X||_2,e_1=(1,0,\cdots) \] 即 \[ X=, HX= \]

引理:\(\forall x,y\in \R^n,x\neq y\),且\(||X||_2=||Y||_2\),则存在初等反射矩阵\(H\),使得 \[ X=HY \]

proof:

令\(w=\frac{X-Y}{||X-Y||_2}\)，显然\(||w||_2=1\)于是有,

\[ H(w)=I-2ww^T=I-2\frac{(X-Y)(X-Y)^T}{||X-Y||_2^2} \]

那么,

\[ HX=(I-2\frac{(X-Y)(X-Y)^T}{||X-Y||_2})X \]

注意到,

\[ X^TX=(X,X)=||X||_2^2=||Y||_2^2=(Y,Y)=Y^TY\\ X^TY=Y^TX\\ \]

有,

\[ \begin{split} ||X-Y||_2^2&=(X-Y,X-Y)=(X-Y)^T(X-Y)\\&=X^TX-X^TY-Y^TX+Y^TY\\ &=2(X-Y)^TX \end{split} \]

故,

\[HX=X-(X-Y)=Y\]

注: 正交变换不改变向量的2范数,即若\(P\)为正交阵,则 \[||PX||_2=||X||_2 \] 因为,\(||PX||_2^2=(PX,PX)=(X,P^TPX)=(X,IX)=||X||_2^2\)

定理: (约化定理)设\(X=(x_1,x_2,\cdots,x_n)^T\neq 0\),则存在初等反射阵\(H\),使得,

\[ HX=-\sigma e_1 \]

其中,

\[\begin{cases} e_1=(1,0,\cdots,0)^T\\ H=I-\beta^{-1}uu^T\\ \sigma =sign(x_1)||X||_2\\ u=X+\sigma e_1\\ \beta=\sigma(\sigma+x_1) \end{cases}\]

proof: 令\(Y=-\sigma e_1\),取\(\sigma=\pm||X||_2\) 此时,\(||Y||_2=|\sigma|=||X||_2\) 由上面的引理知, \[\exists H=I-2ww^T\ ,s.t.HX=-\sigma e_1\] 其中, \[ w=\frac{X-Y}{||X-Y||_2}=\frac{X+\sigma e_1}{||X+\sigma e_1||_2}:=\frac{u}{||u||_2}\] 且, \[H=I-2ww^T=I-2\frac{uu^T}{||u||_2^2}:=I-\beta^{-1}uu^T\\ \beta=\frac{1}{2}||u||_2\] 显然, \[\begin{split} \beta&=\frac{1}{2}||u||_2=\frac{1}{2}||X+\sigma e_1||_2^2\\ &=\frac{1}{2}((X_1+\sigma)^2+X_2^2+\cdots+X_n^2)\\ &=\frac{1}{2}(\sigma^2+2\sigma X_1+X_1^2+X_2^2+\cdots+X_n^2)\\ &=\frac{1}{2}(\sigma^2+2\sigma X_1+\sigma^2)\\ &=\sigma(\sigma+X_1) \end{split}\]

为避免有效数字损失,\(\sigma\)应该与\(X_1\)同号.

计算上,当\(X\)的分量太大时,可考虑归一化, 令\(d=||X||_{\infty},X'=\frac{X}{d}\), \[\begin{cases} \sigma' =sign(X_1')||X'||_2=\frac{\sigma}{d}\\ u'=X'+\sigma' e_1=\frac{u}{d}\\ \beta'=\sigma'(\sigma'+X_1')=\frac{\beta}{d^2}\\ H=I-(\beta')^{-1}(u')(u')^T=H \end{cases}\]

平面旋转矩阵和Givens变换

对于\(\R^2\)上的旋转变换(向量逆时针) \[ \begin{pmatrix} x'\\ y' \end{pmatrix} =\begin{pmatrix} \cos\theta&-\sin\theta\\ \sin\theta&\cos\theta \end{pmatrix}\begin{pmatrix} x\\ y \end{pmatrix} \]

而坐标系逆时针(向量顺时针)的旋转矩阵为 \[P^{-1}=P^T= \begin{pmatrix} \cos\theta&\sin\theta\\ -\sin\theta&\cos\theta \end{pmatrix} \]

一般地,对于\(\R_n\)也有旋转变换,\(y=Px,\quad x,y\in \R^n\)

\[ P(i,j,\theta)=P(i,j)= =\left(\begin{array}{cccc} 1 & & & &&\\ &1& & &&\\ &&\ddots & & & &&\\ &&&\cos \theta & & &\sin \theta \leftarrow i \text { 行 } &&\\ &&&&1& & &&\\ &&&&& \ddots & &&\\ &&&-\sin \theta & & &\cos \theta \leftarrow j \text { 行 }&&\\ &&&&&&&\ddots&\\ &&&&&&&&1 \end{array} \right). \]

称为平面\(\{x_i,y_i\}\)的旋转变换,或称为Givens变换.

定理: (约化定理)对\(\forall X=(x_1,\cdots,x_n)\neq 0\),则可选取Givens变换\(P(i,j,\theta)\)使得, \[PX=(x_1,\cdots,x_i',x_{i+1},\cdots,0,x_{j+1},\cdots,x_n)^T\] 其中\(x_i'=\sqrt{x_i^2+x_j^2},\theta=\arctan\frac{x_j}{x_i}\)

Proof:

矩阵的QR分解

Household变换下的QR分解

目的: 对矩阵\(A\in\R^{m\times n},(m\leq n),s=\min(m-1,n)\),则存在初等反射阵\(H_1,H_2,\cdots,H_s\),使得, \[ H_s\cdots H_1=\begin{cases} R,m=n\\ (R,\theta)^T,m>n \end{cases} \]

引理：若 \(A\in\R^{m\times n}\) 且 \(A\) 列满秩。\(s=\min(m-1,n)\),则有初等反射阵， \(H_1,H_2,\cdots,H_s\),使得, \[ H_s\cdots H_1=\begin{cases} R,m=n\\ (R,\theta)^T,m>n \end{cases} \]

Proof：设 \[A=\begin{pmatrix} a_{11} & \cdots & a_{1n} \\ \vdots & \ddots & \vdots \\ a_{m1} & \cdots & a_{mn} \end{pmatrix} =A^{(1)}=(a_1,a_2,\cdots,a_n)\]

第一步：（约化）\(a_1\neq \vec{0}\)

由前面的定理，可以知道存在初等反射阵， \[H_1=I-\beta^{-1}_1u_1u_1^T\] 使得，\(H_1a_1=-\sigma_1 e_1,\sigma =sign(a_{11})||a_1||_2\),于是， \[H_1A^{(1)}=(H_1a_1,H_1a_2,\cdots,H_1a_n)\\=\begin{pmatrix} -\sigma_1 &a_{12}^{(2)}& \cdots & a_{1n}^{(2)} \\ 0 &a_{22}^{(2)}& \ddots & \vdots \\ \vdots &\vdots& \ddots & \vdots \\ 0 &a_{m2}^{(2)}& \cdots & a_{mn}^{(2)} \end{pmatrix} \]

定理：(矩阵的QR分解) - \(m>n\),设\(A\in\R^{m\times n},A\)列满秩.\(s=\min(m-1,n)\),则存在初等反射阵\(H_1,H_2,\cdots,H_s\),使得, \[H_s\cdots H_1A=(R,\theta)^T\] 其中\(R\)为非奇异的\(n\)阶上三角阵.\(\theta\)为零矩阵.

• \(m=n\),设\(A\in\R^{n\times n},A\)非奇异,则 \[A=QR\] 其中\(R\)为非奇异的\(n\)阶上三角阵.\(Q\)为正交矩阵.且当\(R\)的对角线元素均为正值,分解唯一.

Proof: (1)第一条证明同上一条引理. (2)第二条,当\(m=n\)时,\(s=\min(m-1,n)=n-1\),则存在初等反射阵,\(H_1,H_2,\cdots,H_{n-1}\),使得, \[H_{n-1}\cdots H_1A=\begin{pmatrix} r_{11}& r_{12}& \cdots & r_{1n} \\ 0& r_{22}& \cdots & r_{2n} \\ \vdots & \vdots & \ddots & \vdots \\ 0& 0& \cdots & r_{nn} \end{pmatrix} :=R\] 记\(Q^{-1}=Q^T=H_{n-1}\cdots H_1\),则 \[Q^{-1}A=R\] 即,\(A=QR\),Q为正交阵. 下证唯一性, 若\(A=Q_1R_1=Q_2R_2\),且\(R_1,R_2\)为非奇异上三角阵,有正的对角元,\(Q_1,Q_2\)为正交阵. 考虑\(A^TA\),因\(A^TA\)对称正定.则 \[A^TA=(Q_1R_1)^TQ_1R_1=R_1^TR_1\] \[A^TA=(Q_2R_2)^TQ_2R_2=R_2^TR_2\] 由于\(A^TA\)的cholesky分解的唯一性,知, \[Q_1=Q_2,R_1=R_2\]

注解: (1)若\(A\in\R^{n\times n}\)非奇异,则\(A^TA\)是对称正定的; 证明:对称是显然的, 任给一个非零向量\(X\),因为\(A\)非奇异,所以有\(AX\neq 0\),要验证\(A^TA\)为正定阵, 有正定定义, \[X^TA^TAX=(AX)^TAX=(AX,AX)=||AX||_2^2>0,\forall X\neq 0\] (2)QR分解的计算意义: \(AX=b\Rightarrow QRX=b\Rightarrow RX=Q^Tb\) 转置基本没有计算量,\(R\)是上三角阵解出\(X\)是容易的.

Givens变换下的QR分解

定理:若\(A\in\R^{n\times n},A\)非奇异,则存在平面旋转矩阵\(P_1,P_2,\cdots,P_{n-1}\),使得, \[ P_{n-1}\cdots P_1A=R=\begin{pmatrix} r_{11}& r_{12}& \cdots & r_{1n} \\ 0& r_{22}& \cdots & r_{2n} \\ \vdots & \vdots & \ddots & \vdots \\ 0& 0& \cdots & r_{nn} \end{pmatrix} \] \(A\)有QR分解,其中\(R\)为非奇异的\(n\)阶上三角阵.\(Q\)为正交矩阵.且当\(R\)的对角线元素均为正值,分解唯一.

Proof: 第一步约化,不妨设第一列元素都不为0. 可以选取\(n-1\)个Givens变换,\(P(1,2),\cdots,P(1,n)\)作用再\(A\)上,使得, \[ P(1,n)\cdots P(1,2)A=\begin{pmatrix} r_{11}& r_{12}& \cdots & r_{1n} \\ 0& a_{22}^{(2)}& \cdots & a^{(2)}_{2n} \\ \vdots & \vdots & \ddots & \vdots \\ 0& a_{n2}^{(2)}& \cdots & a^{(2)}_{nn} \end{pmatrix} :=A^{(2)} \] 其中\(r_{11}^2=a_{11}^2+a_{21}^2+\cdots+a_{n1}^2\),记 \[P_1=P(1,n)\cdots P(1,2)\] \(\big|\Big| |\bigg|\Bigg|\)\(\big|\Big| |\bigg|\Bigg|\)\(\big|\Big| |\bigg|\Bigg|\)\(\big|\Big| |\bigg|\Bigg|\)\(\big|\Big| |\bigg|\Bigg|\)\(\big|\Big| |\bigg|\Bigg|\)\(\big|\Big| |\bigg|\Bigg|\)\(\big|\Big| |\bigg|\Bigg|\)\(\big|\Big| |\bigg|\Bigg|\)\(\big|\Big| |\bigg|\Bigg|\)\(\big|\Big| |\bigg|\Bigg|\)\(\big|\Big| |\bigg|\Bigg|\)\(\big|\Big| |\bigg|\Bigg|\)\(\big|\Big| |\bigg|\Bigg|\)

第k步约化:设已经完成\(k-1\)步约化,即 \[ P_{k-1}\cdots P_1A=\left(\begin{array}{cccccc} r_{11} & r_{12} & \cdots & r_{1 k} & \cdots & r_{1 n} \\ & r_{22} & \cdots & r_{2 k} & \cdots & r_{2 n} \\ & & \ddots & \vdots& & \vdots \\ & & & a_{k k}^{(k)}& \cdots & a_{k n}^{(k)} \\ & & & \vdots& & \vdots \\ & & & a_{n k}^{(k)} & \cdots & a_{n n}^{(k)} \end{array}\right):=A^{(k)} \] 现进行第\(k\)步约化,不妨设\(a_{jk}^{(k)}\neq 0,(j=k+1,\cdots,n)\),则可以选择Givens变换, \[P(k,j)\] 使得, \[A^{(k+1)}=P(k,n)\cdots P(k,k+1)A^{(k)}=P_kA^{(k)}\] 此时,就把\(a_{k k}^{(k)}\)更新成\(r_{kk}\)且其下方元素为0. 故得到\(k+1\)阶上三角阵\(A^{(k+1)}\), 继续以上约化过程,最后就有, \[ P_{n-1}\cdots P_1A=A^{(n)}:=R\] 记\(Q^T=Q^{-1}=P_{n-1}\cdots P_1\),有\(Q^{-1}A=R\),即有 \[A=QR\] 其中\(Q\)为正交阵,\(R\)为非奇异上三角阵(唯一性,Cholesky分解).

---

例题:用反射阵对 \[ A=\left(\begin{array}{lll} 0 & 2 & 0 \\ 2 & 1 & 2 \\ 0 & 2 & 1 \end{array}\right) \] 进行QR分解.

求解超定方程组

设\(AX=b,A\in \R^{m\times n},(m>n)\),\(A\)列满秩,一般而言没有通常意义下的解. 线性最小二乘问题:对超定方程组,找到\(X^*\in \R^n\),使得 \[ \min_{X^*\in \R^n}||b-AX||_2^2=||b-AX^*||_2^2\neq 0 \] 记 \[r=b-AX\] 为残差向量,于是我们只要让\(||r||_2^2\)最小即可. 可以利用正交约化求最小二乘解. 有正交约化定理,可选择初等反射阵\(H_1,\cdots H_n\),使得, 左边 \[ H_n,\cdots H_1A=\left.\left(\frac{R}{\theta}\right)\right. \] \(R\)为\(n\times n\)的矩阵,\(\theta\)为\((m-n)\times n\)的矩阵 右边 \[ H_n,\cdots H_1b=\left.\left(\frac{c}{d}\right)\right. \] 记\(Q=H_n,\cdots H_1\),于是 \[Qr=Q(b-AX)=Qb-QAX\] \[=\left.\left(\frac{c}{d}\right)\right.-\left.\left(\frac{R}{\theta}\right)\right.X=\left.\left(\frac{c-RX}{d}\right)\right.\] 注意到\(Q\)为正交阵, \[||r||_2^2=(r,r)=(Q^TQr,r)=(Qr,Qr)=||Qr||_2^2\] \[=||c-RX||_2^2+||d||_2^2\geq ||d||_2^2\] 取等条件为 \[c=RX,X\in \R^n\] 即有,当\(X^*\)为\(RX=c\)的解时,有 \[\min_{X^*\in \R^n}||r||_2^2=||r^*||_2^2=||d||_2^2\neq 0\] \[\min_{X^*\in \R^n}||b-AX||_2^2=||b-AX^*||_2^2=||d||_2^2\neq 0\]