线性方程组AX=B的数值解法(j)

第3章线性方程组AX=B的数值解法2/6/2023华南师范大学数学科学学院谢骊玲引言在自然科学和工程技术中很多问题的解决常常归结为解线性代数方程组。例如电学中的网络问题，船体数学放样中建立三次样条函数问题，用最小二乘法求实验数据的曲线拟合问题，解非线性方程组问题，用差分法或者有限元法解常微分方程，偏微分方程边值问题等都导致求解线性方程组，而且后面几种情况常常归结为求解大型线性方程组。线性代数方面的计算方法就是研究求解线性方程组的一些数值解法与研究计算矩阵的特征值及特征向量的数值方法。2/6/2023华南师范大学数学科学学院谢骊玲线性方程组求解问题考虑线性方程组Ax=b其中A是一个(n

×n)的非奇异矩阵,x是要求解的n维未知向量,b是n维常向量2/6/2023华南师范大学数学科学学院谢骊玲线性方程组的解的存在性和唯一性定理3.4设A是N×N方阵，下列命题等价：给定任意N×1矩阵B，线性方程组AX=B有唯一解矩阵A是非奇异的（即A-1存在） 方程组AX=0有唯一解X=0det(A)≠02/6/2023华南师范大学数学科学学院谢骊玲线性方程组的解最常见的求线性方程组Ax=b的解的方法是在方程组两侧同乘以矩阵A的逆Gram法则：Ax=b2/6/2023华南师范大学数学科学学院谢骊玲线性方程组的解（续1）求逆运算和行列式计算由于运算量大，实际求解过程中基本不使用，仅作为理论上的定性讨论克莱姆法则在理论上有着重大意义，但在实际应用中存在很大的困难，在线性代数中，为解决这一困难给出了高斯消元法还有三角分解法和迭代求解法2/6/2023华南师范大学数学科学学院谢骊玲解法分类关于线性方程组的数值解法一般有两类直接法：若在计算过程中没有舍入误差，经过有限步算术运算，可求得方程组的精确解的方法迭代法：用某种极限过程去逐步逼近线性方程组精确解的方法迭代法具有占存储单元少，程序设计简单，原始系数矩阵在迭代过程中不变等优点，但存在收敛性及收敛速度等问题2/6/2023华南师范大学数学科学学院谢骊玲3.3上三角线性方程组定义3.2N×N矩阵A=[aij]中的元素满足对所有i>j，有aij=0，则称矩阵A为上三角矩阵；如果A中的元素满足对所有i<j，有aij=0，则称矩阵A为下三角矩阵。定理3.5（回代）设AX=B是上三角线性方程组，如果akk≠0，其中k=1,2,…,N，则该方程组存在唯一解。2/6/2023华南师范大学数学科学学院谢骊玲3.3上三角线性方程组（续1）定理3.6如果N×N矩阵A=[aij]是上三角矩阵或下三角矩阵，则条件akk≠0很重要，因为回代算法中包含对akk的除法。如果条件不满足，则可能无解或有无穷解联系定理3.4，可知要条件akk≠0成立才能保证方程组存在唯一解2/6/2023华南师范大学数学科学学院谢骊玲3.3上三角线性方程组（续2）求解上三角线性方程组的回代算法最后2/6/2023华南师范大学数学科学学院谢骊玲上三角线性方程组的求解基本算法：

2/6/2023华南师范大学数学科学学院谢骊玲上三角线性方程组的求解（续1）2/6/2023华南师范大学数学科学学院谢骊玲3.4高斯消去法和选主元求解有N个方程和N个未知数的一般方程组AX=B的一般做法：构造一个等价的上三角方程组UX=Y，并利用回代法求解如果两个N×N线性方程组的解相同，则称二者等价对一个给定方程组进行初等变换，不会改变它的解2/6/2023华南师范大学数学科学学院谢骊玲3.4高斯消去法和选主元（续1）考虑一个简单的例子：求解第二个方程，得第二个方程减去第一个方程除以3再乘以4得到的新方程，得到新的方程组：回代到第一个方程，得2/6/2023华南师范大学数学科学学院谢骊玲3.4高斯消去法和选主元（续2）考虑包含n个未知数的方程组or作如下行变换之后方程组的解向量x不变对调方程组的两行用非零常数乘以方程组的某一行将方程组的某一行乘以一个非零常数，再加到另一行上

通过对增广矩阵[A|B]进行如上的行变换求解2/6/2023华南师范大学数学科学学院谢骊玲3.4高斯消去法和选主元（续3）2/6/2023华南师范大学数学科学学院谢骊玲3.4高斯消去法和选主元（续4）2/6/2023华南师范大学数学科学学院谢骊玲3.4高斯消去法和选主元（续5）2/6/2023华南师范大学数学科学学院谢骊玲3.4高斯消去法和选主元（续6）利用3.3节的回代法求解上述上三角方程组2/6/2023华南师范大学数学科学学院谢骊玲3.4高斯消去法和选主元（续7）消去过程2/6/2023华南师范大学数学科学学院谢骊玲3.4高斯消去法和选主元（续8）回代过程2/6/2023华南师范大学数学科学学院谢骊玲3.4高斯消去法和选主元（续9）上述消去过程中，如果akk=0，则不能使用第k行消除第k列的元素，而需要将第k行与对角线下的某行进行交换，以得到一个非零主元。如果不能找到非零主元，则线性方程组的系数矩阵是奇异的，因此线性方程组不存在唯一解选主元以避免，如果此主元非零，则不换行；如果此主元为零，则寻找第p行下满足的第1行，将此行与第p行互换，使新主元非零。平凡选主元策略2/6/2023华南师范大学数学科学学院谢骊玲3.4高斯消去法和选主元（续10）选主元以减少误差：把元素中的最大绝对值移到主对角线上例3.17和3.18偏序选主元策略|akp|=max{|app|,|app+1|,…,|aN-1p|,|aNp|}按比例偏序选主元（平衡）策略sr=max{|arp|,|arp+1|,…,|arN|}其中r=p,p+1,…,N2/6/2023华南师范大学数学科学学院谢骊玲3.4高斯消去法和选主元（续11）病态问题：矩阵A中元素的微小变化引起解的很大变化cond(A)=207.0122/6/2023华南师范大学数学科学学院谢骊玲图形解释2/6/2023华南师范大学数学科学学院谢骊玲3.4高斯消去法和选主元（续12）一个线性方程组称为是病态的，如果其系数矩阵接近奇异且它的行列式接近0矩阵条件数

cond(A)=||A||||A-1||2/6/2023华南师范大学数学科学学院谢骊玲3.5三角分解法A=LU:下三角矩阵L的主对角线为1，上三角矩阵U的对角线元素非零定义3.4如果非奇异矩阵A可表示为下三角矩阵L和上三角矩阵U的乘积：A=LU，则A存在一个三角分解A非奇异蕴含着对所有的k有ukk≠0，k=1,2,3,4.2/6/2023华南师范大学数学科学学院谢骊玲矩阵的LU分解是否所有的非奇异矩阵A都能作LU分解呢？一个例子：N阶方阵A有唯一LU分解的充要条件是A的各阶顺序主子式均不为零2/6/2023华南师范大学数学科学学院谢骊玲3.5三角分解法（续1）

利用前代/回代算法求解形如Lx=b或Ux=b的线性方程组是容易的如果对一个给定的矩阵A，能够找到一个下三角矩阵L和一个上三角矩阵U，使A=LU则求解线性方程组Ax=b的问题可以分解成两个简单的问题：

Ly=b

Ux=y易见：Ax=(LU)x=L(Ux)=Ly=b2/6/2023华南师范大学数学科学学院谢骊玲3.5三角分解法（续2）

假设已有矩阵A:

对A作LU分解:

检验分解结果:2/6/2023华南师范大学数学科学学院谢骊玲3.5三角分解法（续3）

构造一系列乘数矩阵M1,M2,M3,M4,…,MN-1使得:(MN-1…M4M3M2M1)A是上三角矩阵，把它重新记成U.对4×4矩阵A，M1可取:2/6/2023华南师范大学数学科学学院谢骊玲3.5三角分解法（续4）M2可取:M3可取：2/6/2023华南师范大学数学科学学院谢骊玲3.5三角分解法（续5）

则U=(M3M2M1)A是上三角形矩阵每个M矩阵都是下三角形矩阵

如M2的逆为:

注意到每个M矩阵的逆只是它自身下三角部分元素取相反数

A=(M3M2M1)-1

U

=(M1)-1(M2)-1(M3)-1

U

定义L=(M1)-1(M2)-1(M3)-1，则L就是一个对角元素全为1的下三角矩阵，因为所有的M矩阵的逆都是对角元素全为1的下三角矩阵2/6/2023华南师范大学数学科学学院谢骊玲3.5三角分解法（续6）计算复杂性：高斯消去法与三角分解法的三角化过程是一样的，都需要次乘法和除法次减法求解LUX=B又需要N2次乘法和除法，以及(N2-N)次减法2/6/2023华南师范大学数学科学学院谢骊玲3.5三角分解法（续7）每一个M矩阵中都需要计算1/A(i,i)

当第i个对角元素为0或者很接近0时就没法计算M，这时A的直接LU分解就没法继续进行

可以将第i行与它下面的某一行互换，该行的第i列元素非零

带选主元过程的LU分解2/6/2023华南师范大学数学科学学院谢骊玲3.5三角分解法（续8）之前我们构造了一系列的M矩阵使得

是上三角矩阵现在我们构造一系列的M矩阵和P矩阵使得是上三角矩阵(MN-1….M4

M3

M2

M1)A(MN-1

PN-1

….M4

P4M3

P3M2

P2M1P1)A2/6/2023华南师范大学数学科学学院谢骊玲3.6求解线性方程组的迭代法考虑线性方程组2/6/2023华南师范大学数学科学学院谢骊玲3.6求解线性方程组的迭代法（续1）

高斯消去法

–受限于舍入误差和病态性

迭代法

–另一种求解线性方程组的方法

给出初始估计值，通过迭代得到更好的解的近似值迭代法对求解大型线性方程组非常有效

Jacobi（雅可比）和Gauss-Seidel（高斯-赛德尔）方法2/6/2023华南师范大学数学科学学院谢骊玲3.6求解线性方程组的迭代法（续2）将方程组改写成每个方程的左边只有一个未知数的形式：给出初始估计值和迭代规则2/6/2023华南师范大学数学科学学院谢骊玲Jacobi迭代法初始估计值迭代一步后的结果：2/6/2023华南师范大学数学科学学院谢骊玲Jacobi迭代法（续1）k步迭代后的结果：2/6/2023华南师范大学数学科学学院谢骊玲Jacobi迭代法（续2）例：Jacobi迭代公式：2/6/2023华南师范大学数学科学学院谢骊玲Jacobi迭代法（续3）初始迭代值20步迭代后2/6/2023华南师范大学数学科学学院谢骊玲Jacobi迭代法（续4）迭代会不会收敛到方程组的解？迭代到何时会终止？终止的判断条件是什么？两个必须考虑的问题：2/6/2023华南师范大学数学科学学院谢骊玲3.6求解线性方程组的迭代法（续3）定义3.6设有N×N维矩阵A，如果其中k＝1,2,…,N则称A具有严格对角优势（严格对角占优）。定理3.15（雅可比迭代）设矩阵A具有严格对角优势，则AX=B有唯一解X=P。利用雅可比迭代可产生一个向量序列{Pk}，而且对于任意初始向量P0，向量序列都将收敛到P。2/6/2023华南师范大学数学科学学院谢骊玲3.6求解线性方程组的迭代法（续4）向量之间的距离可以用来判断{Pk}是否收敛到P。因为两个向量P=(x1,x2,…,xN)和Q=(y1,y2,…,yN)之间的欧几里德距离计算复杂；而1－范数具有度量的数学结构，也适合作为一个一般化的“距离公式”。而且根据线性代数的理论可知，如果两个向量的||＊||1范数接近，则它们的欧几里德范数||＊||2也接近。所以定义两个N维向量的距离为||＊||1范数，用来确定N维空间中的收敛性2/6/2023华南师范大学数学科学学院谢骊玲3.6求解线性方程组的迭代法（续5）1-范数：满足一般向量范数的性质定理3.16设X和Y是N维向量，c是一个标量。则函数||X||有如下性质：正定性：||X||≥0，||X||=0当且仅当X=0齐次性：||cX||=|c|·