• 欢迎光临~

第四章 线性方程组的直接法

开发技术 开发技术 2022-11-30 次浏览

4.2 LU分解

4.2.1 高斯消去法

例1. 用高斯消去法求解:(begin{bmatrix}2&-4&6\4&-9&2\1&-1&3 end{bmatrix}begin{bmatrix}x_1\x_2\x_3 end{bmatrix}=begin{bmatrix}3\5\4 end{bmatrix})

首先写出增广矩阵 (begin{bmatrix}2&-4&6&3\4&-9&2&5\1&-1&3&4end{bmatrix})

然后对第二行第三行首元进行处理 (begin{bmatrix}2&-4&6&3\0&-1&-10&-1\0&1&0&frac{5}{2}end{bmatrix})

再处理得到上三角 (begin{bmatrix}2&-4&6&3\0&-1&-10&-1\0&0&-10&frac{3}{2}end{bmatrix})

最终解出(x_3,x_2,x_1)

4.2.2 基本消去矩阵

定义:设有一(n)维列向量(begin{pmatrix}a_1,cdots,a_k,a_{k+1},cdots,a_nend{pmatrix}^T),其中(a_kne0),把它作为主元,令(m_i=frac{a_i}{a_k})称他们为消去因子,矩阵

(M_k=begin{bmatrix}1&cdots&0&0&cdots&0\ vdots&ddots&vdots&vdots&ddots&vdots\0&cdots&1&0&cdots&0\0&cdots&-m_{k+1}&1&cdots&0\vdots&ddots&vdots&vdots&ddots&vdots\ 0&cdots&-m_{n}&0&cdots&1end{bmatrix})

称为基本消去矩阵,满足

(begin{bmatrix}1&cdots&0&0&cdots&0\ vdots&ddots&vdots&vdots&ddots&vdots\0&cdots&1&0&cdots&0\0&cdots&-m_{k+1}&1&cdots&0\vdots&ddots&vdots&vdots&ddots&vdots\ 0&cdots&-m_{n}&0&cdots&1end{bmatrix}begin{bmatrix}a_1\vdots \a_k\a_{k+1}\vdots\a_nend{bmatrix}=begin{bmatrix}a_1\vdots \a_k\0\vdots\0end{bmatrix})

小指标在前,大指标在后,可以并起来,如

(M_1=begin{bmatrix}1&0&0\-2&1&0\1&0&1 end{bmatrix}) (M_2=begin{bmatrix}1&0&0\0&1&0\0&frac{1}{2}&1 end{bmatrix})

(M_1M_2=begin{bmatrix}1&0&0\-2&1&0\1&frac{1}{2}&1 end{bmatrix})

4.2.3 LU分解

借助基本消去矩阵,高斯消去法可以按照如下方式描述:

(M_{n-1}cdots M_2M_1Ax=Ux=M_{n-1}cdots M_2M_1b),其中(U)是一个上三角矩阵。

由于大指标在前,(M_{n-1}cdots M_2M_1)无法直接计算,因此令(M=M_{n-1}cdots M_2M_1)

(MA=U,A=M^{-1}U=M_1^{-1}M_2^{-1}cdots M_{n-1}^{-1}U=L_1L_{2}cdots L_{n-1}U=LU)

(U=M_{n-1}cdots M_2M_1A) (L=L_1L_{2}cdots L_{n-1})

例3. 写出矩阵(A=begin{bmatrix}1&3&2&1\2&4&7&4\4&8&3&1\9&9&6&4 end{bmatrix})(LU)分解。

(M_1=begin{bmatrix}1&0&0&0\-2&1&0&0\-4&0&1&0\-9&0&0&1 end{bmatrix},M_1A=begin{bmatrix}1&3&2&1\0&-2&3&2\0&-4&-5&-3\0&-18&-12&-5 end{bmatrix})

(M_2=begin{bmatrix}1&0&0&0\0&1&0&0\0&-2&1&0\0&-9&0&1 end{bmatrix},M_2M_1A=begin{bmatrix}1&3&2&1\0&-2&3&2\0&0&-11&-7\0&0&-39&-23 end{bmatrix})

(M_3=begin{bmatrix}1&0&0&0\0&1&0&0\0&0&1&0\0&0&-frac{39}{11}&1 end{bmatrix},M_3M_2M_1A=begin{bmatrix}1&3&2&1\0&-2&3&2\0&0&-11&-7\0&0&0&frac{20}{11} end{bmatrix})

(L=begin{bmatrix}1&0&0&0\2&1&0&0\4&2&1&0\9&9&frac{39}{11}&1 end{bmatrix},U=begin{bmatrix}1&3&2&1\0&-2&3&2\0&0&-11&-7\0&0&0&frac{20}{11} end{bmatrix})

4.3 列主元高斯消去法

考察第1列,将绝对值最大的元素换到(a_{11})的位置,

考察第2列,将绝对值最大的元素换到(a_{22})的位置,(cdots)

最后得到(M_{n-1}P_{n-1}cdots M_1P_1Ax=Ux=M_{n-1}P_{n-1}cdots M_1P_1b)

(M=M_{n-1}P_{n-1}cdots M_1P_1),则(MA=URightarrow A=widetilde{L}U,widetilde{L}=M^{-1})

其中(widetilde{L})不一定是下三角矩阵

若令(P=P_{n-1}cdots P_1),则(PA=PM^{-1}U=LU)

(L=PM^{-1}),此时(L)是一个下三角矩阵。

这种分解称为(PLU)分解。

例5. 写出求解(begin{bmatrix}2&-4&6\4&-9&2\1&-1&3 end{bmatrix}begin{bmatrix}x_1\x_2\x_3 end{bmatrix}=begin{bmatrix}3\5\4 end{bmatrix})时的(P,L,U)

(P_1=begin{bmatrix}0&1&0\1&0&0\0&0&1 end{bmatrix})

(P_1Ax=begin{bmatrix}4&-9&2\2&-4&6\1&-1&3 end{bmatrix}begin{bmatrix}x_1\x_2\x_3 end{bmatrix}=begin{bmatrix}5\3\4 end{bmatrix}=P_1b)

(M_1=begin{bmatrix}1&0&0\-frac{1}{2}&1&0\-frac{1}{4}&0&1 end{bmatrix})

(M_1P_1Ax=begin{bmatrix}4&-9&2\0&frac{1}{2}&5\0&frac{5}{4}&frac{5}{2} end{bmatrix}begin{bmatrix}x_1\x_2\x_3 end{bmatrix}=begin{bmatrix}5\frac{1}{2}\ frac{11}{4} end{bmatrix})

(P_2=begin{bmatrix}1&0&0\0&0&1\0&1&0 end{bmatrix})

(P_2M_1P_1Ax=begin{bmatrix}4&-9&2\0&frac{5}{4}&frac{5}{2}\0&frac{1}{2}&5 end{bmatrix}begin{bmatrix}x_1\x_2\x_3 end{bmatrix}=begin{bmatrix}5\frac{11}{4}\frac{1}{2} end{bmatrix})

(M_2=begin{bmatrix}1&0&0\0&1&0\0&-frac{2}{5}&1 end{bmatrix})

(M_2P_2M_1P_1Ax=begin{bmatrix}4&-9&2\0&frac{5}{4}&frac{5}{2}\0&0&4 end{bmatrix}begin{bmatrix}x_1\x_2\x_3 end{bmatrix}=begin{bmatrix}5\frac{11}{4}\-frac{3}{5} end{bmatrix})

(M=M_2P_2M_1P_1=begin{bmatrix}0&1&0\0&-frac{1}{4}&1\1&-frac{2}{5}&-frac{2}{5} end{bmatrix}) (M^{-1}=begin{bmatrix}frac{1}{2}&frac{2}{5}&1\1&0&0\frac{1}{4}&1&0end{bmatrix})

(P=P_2P_1=begin{bmatrix}1&0&0\0&0&1\0&1&0end{bmatrix}begin{bmatrix}0&1&0\1&0&0\0&0&1end{bmatrix}=begin{bmatrix}0&1&0\0&0&1\1&0&0end{bmatrix})

(L=PM^{-1}=begin{bmatrix}1&0&0\frac{1}{4}&1&0\frac{1}{2}&frac{2}{5}&1end{bmatrix}) (U=begin{bmatrix}4&-9&2\0&frac{5}{4}&frac{5}{2}\0&0&4 end{bmatrix})

4.3.7 无需选主元的系统

1)对角占优矩阵

如果矩阵A的元素满足(sumlimits_{i=1,ine j}^{n}|a_{ij}|<|a_{jj}|,j=1,2,cdots,n)称矩阵A是严格对角占优。

严格对角占优矩阵一定是非奇异的。

2)对称正定矩阵

满足下列条件的矩阵是对称正定矩阵(SPD):(A=A^T,x^TAx>0,forall x)

一个矩阵是正定的,当且仅当它的顺序主子式都大于0。

如果矩阵(A)是严格对角占优或者对称正定矩阵,则对(Ax=b)使用高斯消去法使无需选主元,算法本身就是数值稳定的。

4.4.2 三对角矩阵与追赶法

假设三对角系统为

(begin{bmatrix}b_1&c_1\a_2&b_2&c_2\&a_3&b_3&c_3\&&ddots&ddots&ddots\&&&a_{n-1}&b_{n-1}&c_{n-1}\&&&&a_{n}&b_{n}end{bmatrix})

若不需要选主元来保证数值稳定性,此时的高斯消去法非常简单。

A的LU分解为

(L=begin{bmatrix}1&0&cdots&cdots&0\m_2&1&ddots&ddots&vdots\0&ddots&ddots&ddots&vdots\vdots&ddots& m_{n-1}&1&0\0&cdots&0&m_n&1end{bmatrix}) (U=begin{bmatrix}d_1&c_1&cdots&cdots&0\0&d_2&c_2&ddots&vdots\0&ddots&ddots&ddots&vdots\vdots&ddots&ddots&d_{n-1}&c_{n-1}\0&cdots&0&0&d_nend{bmatrix})

(Ly=b,Ux=y),消去时下标从小到大,回代求解时下标从大到小,因此形象地称此时的高斯消去法为追赶法。

4.5 逆矩阵相关

4.5.1

一般情况下,不推荐直接使用(A^{-1})进行计算。

几乎所有需要(A^{-1})的运算都可以通过间接法来实现,比如:

(A^{-1}brightarrow x=A^{-1}b,Ax=b)

1)三角阵的逆矩阵

2)利用LU分解求一般矩阵的逆

方法一、 通过解线性方程组实现,计算流程如下

  • (A=LU)
  • (LUX=I_n,LUx_{j}=e_j,j=1:n)
  • (Ly_j=e_j,j=1:n)
  • (Ux_j=y_j)

方法二、通过逆矩阵的乘积实现,计算流程如下

  • (A=LU)
  • (L^{-1})
  • (U^{-1})
  • (A^{-1}=(LU)^{-1}=U^{-1}L^{-1})

4.6 误差分析

4.6.2 向量范数

现代数学中最重要的概念非极限莫属,而极限描述的关键则是距离

所谓的向量范数,就是为了把三维空间中距离的概念推广到n维空间。

在向量空间(R^n)中,定义映射

(f=||cdot||:R^nrightarrow R)

如果该映射满足:

  • (||x||ge0,||x||=0Leftrightarrow x=0)
  • (||alpha x||=|alpha|cdot ||x||,alphain R)
  • (||x+y||le||x||+||y||)

这个映射就称为(R^n) 空间的向量范数。

1)常用范数

  • 1-范数:(||x||_1=sumlimits_{i=1}^{n}|x_i|)
  • 2-范数:(||x||_2=(sumlimits_{i=1}^{n}|x_i|^2)^frac{1}{2})
  • (infty)-范数:(||x||_{infty}=maxlimits_{i}|x_i|)

2)常用范数间的大小关系

简单的不等关系,如(||x||_1>||x||_2>||x||_infty)

几个反向的不等关系:

  • (||x||_1lesqrt{n}||x||_2)
  • (||x||_2lesqrt{n}||x||_infty)
  • (||x||_1le n||x||_infty)

给定线性空间(X)上的范数(||cdot||_p,||cdot||_q),他们等价当且仅当(exist c_1,c_2>0),使得(c_1||x||_qle||x||_ple c_2||x||_q)成立。

4.6.3 矩阵范数

1)矩阵的诱导范数

矩阵A的诱导范数(||A||)定义为

(||A||=maxlimits_{xne0}frac{||Ax||}{||x||}=maxlimits_{||x||=1}||Ax||)

矩阵范数度量的是矩阵对向量的最大拉伸。

  • (||Ax||le||A||cdot||x||)
  • (||AB||le||A||cdot||B||)

2)矩阵的常见诱导范数及其计算

(1) 1-范数的计算公式

(||A||_1=maxlimits_{j}sumlimits_{i=1}^{n}|a_{ij}|) 它是一个列范数。

(2) (infty)-范数的计算公式

(||A||_{infty}=maxlimits_{j}sumlimits_{i=1}^{n}|a_{ij}|) 它是一个行范数。

(3) 2-范数的计算公式

(||A||_{2}=maxlimits_{xne0}frac{||Ax||_2}{||x||_2}=sqrt{rho(A^TA)})

(rho(A))是矩阵A的谱半径,其定义为(rho(A)=maxlimits_{lambdainsigma(A)}|lambda|),其中(sigma(A))表示A的特征值全体。由于特征值可能是复数,因此(|cdot|)指的是模。

4.6.5 条件数

(mbox{cond}(A)=||A||cdot||A^{-1}||)为矩阵A的条件数,若A是奇异矩阵,则令(mbox{cond}(A)=infty)

条件数刻画了矩阵的奇异程度。

  • 对恒等矩阵,(mbox{cond}(I_n)=1)
  • 对任意矩阵A,(mbox{cond}(A)ge1)
  • 对任意常数(gammane0)(mbox{cond}(gamma A)=mbox{cond}(A))
  • 对对角阵(D=mbox{diag}(d_1,d_2,cdots,d_n)),条件数计算公式为(mbox{cond}(D)=frac{maxlimits_{1le ile n}|d_i|}{minlimits_{1le ile n}|d_i|})
  • 2-范数条件数计算公式为(mbox{cond}(A)_2=sqrt{frac{lambda_{max}(A^TA)}{lambda_{min}(A^TA)}})
  • 如果A是对称矩阵,则2-范数条件数计算公式为(mbox{cond}(A)_2=frac{lambda_{max}}{lambda_{min}})

如果条件数太大,就称矩阵是病态矩阵,病态矩阵对应的线性系统在求解时会放大这些误差。

希尔伯特矩阵是著名的病态矩阵,其条件数大概是(e^{3.5n})

(begin{bmatrix}1&frac{1}{2}&cdots&frac{1}{n}\frac{1}{2}&frac{1}{3}&cdots&frac{1}{n+1}\vdots&vdots&ddots&vdots\frac{1}{n}&frac{1}{n+1}&cdots&frac{1}{2n-1}end{bmatrix})

方程组近似解可靠性的判例

方程组近似解的相对误差估计式的实用方法是将方程组(Ax=b)的一个近似解(tilde{x})回代到原方程组去求余量r

(r=b-Ax)

定理:(frac{||x^*-tilde{x}||}{||x^*||}lembox{cond}(A)frac{||r||}{||b||})

由定理可知,使用余量r的大小来检验近似解的准确程度的办法仅对良态方程组适用。

几个常见的迭代格式

(1) Jacobi迭代格式

将线性方程组(Ax=b)写成分量的形式

(begin{cases}a_{11}x_1+a_{12}x_2+cdots+a_{1n}x_n=b_1,\a_{21}x_1+a_{22}x_2+cdots+a_{2n}x_n=b_2,\vdots\a_{n1}x_1+a_{n2}x_2+cdots+a_{nn}x_n=b_n,end{cases})

建立相应迭代格式

(begin{cases}x_{1}^{(k+1)}=(b_1-a_{12}x_2^{(k)}-a_{13}x_3^{(k)}-cdots-a_{1n}x_n^{(k)})/a_{11}\x_{2}^{(k+1)}=(b_2-a_{21}x_1^{(k)}-a_{23}x_3^{(k)}-cdots-a_{2n}x_n^{(k)})/a_{22}\vdots\x_{n}^{(k+1)}=(b_n-a_{n1}x_1^{(k)}-a_{n2}x_2^{(k)}-cdots-a_{nn-1}x_{n-1}^{(k)})/a_{nn}end{cases})

(J=-D^{-1}(L+U)),称J为Jacobi迭代矩阵。

Jacobi迭代格式收敛的充要条件是(rho(J)<1)

严格对角占优矩阵Jacobi迭代格式收敛。

(2) Gauss-Seidel迭代格式

(begin{cases}x_{1}^{(k+1)}=(b_1-a_{12}x_2^{(k)}-a_{13}x_3^{(k)}-cdots-a_{1n}x_n^{(k)})/a_{11}\x_{2}^{(k+1)}=(b_2-a_{21}x_1^{(k+1)}-a_{23}x_3^{(k)}-cdots-a_{2n}x_n^{(k)})/a_{22}\vdots\x_{n}^{(k+1)}=(b_n-a_{n1}x_1^{(k+1)}-a_{n2}x_2^{(k+1)}-cdots-a_{nn-1}x_{n-1}^{(k+1)})/a_{nn}end{cases})

(G=-(D+L)^{-1}U),称G为Gauss-Seidel迭代矩阵。

Gauss-Seidel迭代格式收敛的充要条件是(rho(G)<1)

严格对角占优矩阵Gauss-Seidel迭代格式收敛。

(3) 逐次超松弛法(SOR方法)

(begin{cases}x_{1}^{(k+1)}=(1-omega)x_1^{(k)}+omega(b_1-a_{12}x_2^{(k)}-a_{13}x_3^{(k)}-cdots-a_{1n}x_n^{(k)})/a_{11}\x_{2}^{(k+1)}=(1-omega)x_2^{(k)}+omega(b_2-a_{21}x_1^{(k+1)}-a_{23}x_3^{(k)}-cdots-a_{2n}x_n^{(k)})/a_{22}\vdots\x_{n}^{(k+1)}=(1-omega)x_n^{k}+omega(b_n-a_{n1}x_1^{(k+1)}-a_{n2}x_2^{(k+1)}-cdots-a_{nn-1}x_{n-1}^{(k+1)})/a_{nn}end{cases})

(S_omega=(D+omega L)^{-1}[(1-omega)D-omega U])

Gauss-Seidel迭代格式收敛的充要条件是(rho(S_omega)<1)

若A是对称正定矩阵,且(omegain(0,2)),则SOR方法收敛。

程序员灯塔
转载请注明原文链接:第四章 线性方程组的直接法
喜欢 (0)
违法和不良信息举报电话:022-22558618 举报邮箱:dljd@tidljd.com