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

矩阵的LU分解华南师范大学数学科学学院谢骊玲*一个例子：N阶方阵A有唯一LU分解的充要条件是A的各阶顺序主子式均不为零是否所有的非奇异矩阵A都能作LU分解呢？3.5三角分解法（续1）华南师范大学数学科学学院谢骊玲*Ly=bUx=y利用前代/回代算法求解形如Lx=b或Ux=b的线性方程组是容易的如果对一个给定的矩阵A，能够找到一个下三角矩阵L和一个上三角矩阵U，使A=LU则求解线性方程组Ax=b的问题可以分解成两个简单的问题：易见：Ax=(LU)x=L(Ux)=Ly=b3.5三角分解法（续2）华南师范大学数学科学学院谢骊玲*3检验分解结果:21假设已有矩阵A:对A作LU分解:3.5三角分解法（续3）华南师范大学数学科学学院谢骊玲*构造一系列乘数矩阵M1,M2,M3,M4,…,MN-1使得:(MN-1…M4M3M2M1)A是上三角矩阵，把它重新记成U.对4×4矩阵A，M1可取:3.5三角分解法（续4）华南师范大学数学科学学院谢骊玲*M2可取:01.M3可取：01.3.5三角分解法（续5）华南师范大学数学科学学院谢骊玲*则U=(M3M2M1)A是上三角形矩阵每个M矩阵都是下三角形矩阵如M2的逆为:注意到每个M矩阵的逆只是它自身下三角部分元素取相反数A=(M3M2M1)-1U

=(M1)-1(M2)-1(M3)-1U定义L=(M1)-1(M2)-1(M3)-1，则L就是一个对角元素全为1的下三角矩阵，因为所有的M矩阵的逆都是对角元素全为1的下三角矩阵3.5三角分解法（续6）华南师范大学数学科学学院谢骊玲*04030102计算复杂性：高斯消去法与三角分解法的三角化过程是一样的，都需要次乘法和除法次减法求解LUX=B又需要N2次乘法和除法，以及(N2-N)次减法3.5三角分解法（续7）华南师范大学数学科学学院谢骊玲*04030102每一个M矩阵中都需要计算1/A(i,i)当第i个对角元素为0或者很接近0时就没法计算M，这时A的直接LU分解就没法继续进行可以将第i行与它下面的某一行互换，该行的第i列元素非零带选主元过程的LU分解3.5三角分解法（续8）华南师范大学数学科学学院谢骊玲*之前我们构造了一系列的M矩阵使得是上三角矩阵现在我们构造一系列的M矩阵和P矩阵使得是上三角矩阵(MN-1….M4M3M2M1)A(MN-1PN-1….M4P4M3P3M2P2M1P1)A3.6求解线性方程组的迭代法华南师范大学数学科学学院谢骊玲*考虑线性方程组求解线性方程组的迭代法（续1）高斯消去法–受限于舍入误差和病态性迭代法–另一种求解线性方程组的方法给出初始估计值，通过迭代得到更好的解的近似值迭代法对求解大型线性方程组非常有效Jacobi（雅可比）和Gauss-Seidel（高斯-赛德尔）方法华南师范大学数学科学学院谢骊玲华南师范大学数学科学学院谢骊玲华南师范大学数学科学学院谢骊玲华南师范大学数学科学学院谢骊玲华南师范大学数学科学学院信息与计算科学系谢骊玲*华南师范大学数学科学学院谢骊玲第3章线性方程组AX=B的数值解法引言华南师范大学数学科学学院谢骊玲*在自然科学和工程技术中很多问题的解决常常归结为解线性代数方程组。例如电学中的网络问题，船体数学放样中建立三次样条函数问题，用最小二乘法求实验数据的曲线拟合问题，解非线性方程组问题，用差分法或者有限元法解常微分方程，偏微分方程边值问题等都导致求解线性方程组，而且后面几种情况常常归结为求解大型线性方程组。线性代数方面的计算方法就是研究求解线性方程组的一些数值解法与研究计算矩阵的特征值及特征向量的数值方法。线性方程组求解问题华南师范大学数学科学学院谢骊玲*考虑线性方程组Ax=b01其中A是一个(n×n)的非奇异矩阵,x是要求解的n维未知向量,b是n维常向量02定理3.4设A是N×N方阵，下列命题等价：给定任意N×1矩阵B，线性方程组AX=B有唯一解矩阵A是非奇异的（即A-1存在） 方程组AX=0有唯一解X=0det(A)≠0线性方程组的解的存在性和唯一性线性方程组的解华南师范大学数学科学学院谢骊玲*最常见的求线性方程组Ax=b的解的方法是在方程组两侧同乘以矩阵A的逆Gram法则：01Ax=b02线性方程组的解（