《数值计算方法》课件4线性方程组的直接解法

直接法（第4章）思想：对系数矩阵进行分解、变换，经有限次算术运算，求出精确解特点：准确、可靠、无方法误差适用：中、小规模问题，尤其是稠密系数矩阵问题：舍入误差对病态方程组的影响，算法可能不稳定

常见的线性方程组数值方法分类4.1消去法

4.1.1高斯消去法用高斯消去法求解线性方程组，分为消元过程和回代过程。

消元过程将原始方程组记作。经过n-1步消元后，得到记作其中注意：必须确保

回代过程对于上三角方程组，容易得到

可行性与计算量1、系数矩阵A的各阶顺序阶主子式均不为零。2、系数矩阵A对称正定。3、系数矩阵A严格对角占优。消元和回代的乘除及加减法总次数如下：高斯消元法的消去过程和回代过程均要求，否则溢出停机。但在如下情况下，对原方程组不作任何处理，确保上述条件成立，使高斯消去法在计算机上顺利执行。由于在此不予证明，仅列出一下三个条件：相比克莱姆法则的乘除法次数不在一个数量级上，减少了很多。4.1.2高斯列主元消去法为拟制舍入误差的传播，在消元过程中希望主元的绝对值最大，就要在每步消元过程前选主元。通常有列主元和全主元两种方法。列主元消去法是第k步消元时，选取作为主元素，进行消元。全主元消去法是选取作为第k步的主元素进行消元。列主元往往需要行的交换，而全主元不仅需要行的交换，而且可能需要列的交换。列的交换实质上是未知量的交换。列主元素消去法步骤及流程框图（p63-65）选主元的思想是消除零主元和小主元，策略是对方称组进行行或列的交换。4.2三角分解法

矩阵的初等（行）变换与初等方阵矩阵的初等变换：三种形式初等方阵：三种形式类型，p(I,j),p(i(k)),p(i(k),j)，与初等变换一一对应初等变换与初等方阵的关系：初等方阵的逆阵、行列式、乘法此处主要使用第三种形式的初等方阵4.2.1LU分解法高斯消去法的消元过程是通过对增广矩阵的初等行变换来完成的。例4-2P67用LU分解法求解线性方程组的步骤

（1）对A进行LU分解，即A=LU；公式见p69（4-5）-（4-8）

（2）求解Ly=b；公式见p69（4-9）

（3）求解Ux=y；公式见p70（4-10）例4-3

p70用LU分解法求解线性方程组的数据结构

存储空间仅需一个n阶的二维数组和一个n阶的一维数组（向量）公式思考：如何利用矩阵的LU分解求解矩阵方程Ax=B。4.2.1LU分解法

直接三角分解

可以不经过高斯消去过程，直接利用公式得到矩阵的LU分解。令如上的LU分解成为杜利特尔（Doolittle）分解。还有另一种分解法称为克劳特（Crout）分解，它是将A分解为一个下三角阵L与一个单位上三角阵U的乘积的形式。可以自己推导L和U的计算公式。LU分解的唯一性定理

定理4-1

设A为n阶方阵，若A的各阶顺序主子式不为零，则A可分解为单位下三角阵L与一个上三角阵U的乘积，且这种分解是唯一的。

证明：反证法。见p67

LDU分解将LU分解中上三角阵U的对角线元素提出来，令D=diag（u11,u22,...unn）,则有A=LDU’，其中U’=D-1U是单位上三角阵。这种分解成为LDU分解。

列主元LU分解的矩阵描述

列主元LU分解计算步骤和公式

P73-744.2.2

列主元LU分解法4.2.3三对角方程组的追赶法

三对角矩阵与三对角方程组

三对角矩阵的克劳特分解的唯一性

直接进行克劳特分解可得到计算公式

追赶法计算步骤及流程图（P76）

追赶法计算时的存储结构定理4-2

设A为三对角矩阵，且对角占优，则对A可以进行克劳特分解，且分解是唯一的。例用追赶法求解三对角方程组4.2.4对称正定矩阵的平方根法定理4-3

设A为对称正定矩阵，则存在一个下三角阵L使得A=LLT

若限定L的主对角线元素取正值，则这种分解是唯一的。例P84习题7

4.3直接法的误差分析

4.3.1病态方程组

对于线性方程组Ax=b，如果A或者b有很小的扰动（误差），但其解会有很大的扰动（误差），则称该方程组为病态方程组。原问题4.3.2矩阵的条件数

通常用条件数的大小来度量方程组病态的程度。

矩阵A的条件数定义为计算3阶希尔伯特矩阵的条件数（例4-6）4.4近似解的精度改善基本思想：对右端项b的误差反复迭代，直至误差满足要求；用直接法求解方程组。算法步骤：（1）对A进行LU分解，A=LU;令k=1，求解Ly=b及Ux(k)=y得x(k)；（2）计算r(k)=b-Ax(k)，求解L