《线性方程组的直接解法.ppt》由会员分享，可在线阅读，更多相关《线性方程组的直接解法.ppt（36页珍藏版）》请在金锄头文库上搜索。
1、线性方程组的直接解法线性方程组的直接解法v概述概述v高斯消去法高斯消去法v矩阵分解及其在解线性方程组中的应用矩阵分解及其在解线性方程组中的应用v矩阵的条件数和方程组的性态矩阵的条件数和方程组的性态1.1 数值解法的必要性数值解法的必要性求：的解 的值，根据克莱姆(Gramer)法则可表示为两个行列式之比：1 概述概述7/25/如： ,若用每秒万亿次（1012）浮点乘法运算的计算机（当前国内运算速度最快）全天工作，完成这些计算约需30年。若使用一般的个人电脑，每秒完成十亿次（109）浮点乘法运算，则完成这些计算约需3万年。 计算一个 阶行列式需要做 个乘法，求解上述方程共做 次乘除法。研究数值方
2、法的必要性7/25/ 1、直接法、直接法：只包含有限次四则运算。只包含有限次四则运算。假定假定在计算过程中在计算过程中不产生舍入误差，计算结果是原方程组的不产生舍入误差，计算结果是原方程组的精确解精确解。 2、迭代法、迭代法： 基于一定的递推公式建立逼近方程组近似解的基于一定的递推公式建立逼近方程组近似解的序序列列。收敛性是其前提，然后还有。收敛性是其前提，然后还有收敛收敛速度以及速度以及误差误差估计等问题。估计等问题。Remark：由于运算过程中舍入误差的确存在，由于运算过程中舍入误差的确存在，实际上直接方法得到的解也是方程组的近似解。实际上直接方法得到的解也是方程组的近似解。1.2 线性代
3、数方程组的解法分类线性代数方程组的解法分类7/25/设有线性方程组为非奇异矩阵.或写为矩阵形式 ，其中2 高斯消去法高斯消去法7/25/2.1 高斯顺序消去法高斯顺序消去法 若 令 ,用 乘 第一个方程加到第 个方程 ，并保留第一式，得Step1Step1：7/25/ Gauss顺序消去法（续）顺序消去法（续）乘除法运算次数 若 令 ，乘第二个方程加到第i个方程 ，得用Step2Step2: :7/25/Gauss顺序消去法记为（续（续2）乘除法运算次数7/25/设为第k-1步消元完成后，有（续（续3）用- 来乘以第k个方程，加到第i个方程，并保留第k个方程， 得：（i=k+1,k+2,n）若
4、 ,令 ,（i=k+1,k+2,n)Step Step k：7/25/Step K（续（续4）(i,j=k+1,n)（i=k+1,n）乘除法运算次数7/25/做完n-1步，原方程可化为同解的上三角方程组。Gauss顺序消去法（续（续5）回代过程： （i=n-1,n-2,2，1）回代乘除运算次数：回代乘除运算次数：7/25/ 在在Gauss顺序消去法的消去过程中，若将右端列向量顺序消去法的消去过程中，若将右端列向量视为方程组视为方程组A的第的第n1列，直接对该增广矩阵列，直接对该增广矩阵A进行行进行行初等变换，将其变换为上三角矩阵，从而回代求解得初等变换，将其变换为上三角矩阵，从而回代求解得原方
5、程组的解。原方程组的解。 计算量计算量 Gauss顺序消去法消去过程所需的乘除运算次数为顺序消去法消去过程所需的乘除运算次数为总的乘除运算次数总的乘除运算次数：取n20，则N30607/25/ 在消去过程中采用在消去过程中采用Gauss-Jordan消去法，消去法，即将方程组化为对角形方程组，进而化为即将方程组化为对角形方程组，进而化为单位阵，则右端列向量就化为方程组的解单位阵，则右端列向量就化为方程组的解向量。向量。 该方法不需回代过程，但总的计算量为该方法不需回代过程，但总的计算量为 n n3 3/2+n/2+n2 2-n/2-n/2， 比比GaussGauss顺序消去法有所增加。顺序消去
6、法有所增加。 GaussJordan消去法消去法7/25/消去过程能够实施的条件是消去过程能够实施的条件是 回代过程条件增加条件回代过程条件增加条件命题命题1 1定义定义 Gauss顺序消去法的消元条件顺序消去法的消元条件7/25/高斯顺序消去法仅对原增广矩阵作行初等变换，故命题证明命题证明7/25/续续定理定理2 2： 若系数矩阵若系数矩阵A的的各阶各阶顺序主子式均不为零则可顺序主子式均不为零则可以用高斯顺序消去法以用高斯顺序消去法求解求解方程组方程组A X=b。定理定理1 1：高斯顺序消去法求解方程组：高斯顺序消去法求解方程组A X=b的的消元过程消元过程能够实施的能够实施的充要条件充要条
7、件是系数矩阵是系数矩阵A的前的前n-1n-1个顺序主子个顺序主子式均不为零。式均不为零。7/25/用Gauss顺序消去法求解线性方程组的条件强于解的存在唯一性条件斯顺序消去法能进行下去，但 或相对于 比较小时，计算产生的舍入误差将导致计算结果误差急剧增大，计算解与真解相差甚远，即该方法不稳定。 Gauss顺序消去法的不足顺序消去法的不足 ，所有主元不为零时高小主元是不稳定的根源，需要采用“选主元”技术，即选取绝对值较大的元素作为主元。7/25/2.2 选主元的高斯消去法选主元的高斯消去法 列主元消去法列主元消去法 增广矩阵在第一列中选取绝对值最大的元素,设 = 调换第一行与第p行，这时的 再执
8、行消去法的第一步就是原来的 ,然后7/25/再考虑 右下角矩阵，在第二列选取绝对值最大的元素作为主元素,将其所在行与第二行交换，消元。依此类推直至将方程组化成上三角方程组，再进行回代就可求得解。 列主元消去法（续）列主元消去法（续）优点：只要系数矩阵非奇异，消元过程就能进行，优点：只要系数矩阵非奇异，消元过程就能进行，并且主元相对较大，方法稳定好。并且主元相对较大，方法稳定好。7/25/在系数矩阵中选取绝对值最大的元素作为主元素，如 然后交换增广矩阵的第一行与第i1行，第一列与第j1列，这时 全主元消去法全主元消去法实施第一次消元。7/25/换把主元素移到再消元。,消元结束后回代求解。再考虑
9、右下角系数矩阵，选取绝对值最大的元素作为主元素,经过行对换和列对 的位置, 全主元消去法（续）全主元消去法（续）7/25/评注1：全主元消去法每一步所选取的主元的绝对值不低于列主元消去法的同一步所选主元的绝对值，因而计算结果更加可靠。评注2：全主元消去法每一步选主元要花费更多的机时，并且对增广矩阵做了列交换，从而未知量的次序发生了变化，对编程带来了麻烦。而列主元消去法的计算结果已比较可靠，故实用中常用列主元消去法。特点特点7/25/3.1 3.1 Gauss顺序消去法的矩阵形式顺序消去法的矩阵形式 设方程组Ax=b的系数矩阵各阶顺序主子式均不为零3 矩阵三角分解法矩阵三角分解法定义符号：定义符
10、号：7/25/3.1 Gauss顺序消去法的矩阵表示顺序消去法的矩阵表示7/25/Gauss顺序消去法的矩阵表示（续）（续）L是一系列单位下是一系列单位下三角矩阵逆的乘三角矩阵逆的乘积，积，U是上三角阵是上三角阵引理：单位下三角引理：单位下三角矩阵对求逆和乘积矩阵对求逆和乘积是封闭的。是封闭的。L也是单位下三角阵也是单位下三角阵7/25/A=LU Gauss顺序消去法的矩阵表示（续（续2）7/25/定定义义1.设设A为为n阶阶矩矩阵阵（n 2）,称称A=LU为为矩矩阵阵的的三三角分解，其中角分解，其中L是下三角矩阵，是下三角矩阵，U是上三角矩阵。是上三角矩阵。定定义义2.如如果果L是是单单位位
11、下下三三角角矩矩阵阵，U是是上上三三角角矩矩阵阵，则则称称三三角角分分解解A=LU为为Doolittle分分解解；如如果果L是是下下三三角角矩矩阵阵，U是是单单位位上上三三角角矩矩阵阵，则则称称A=LU为为Crout分解分解。高斯顺序消去法对应。高斯顺序消去法对应A的的Doolittle分解。分解。 定定理理3 3：设设A为为n阶阶(n1)(n1)矩矩阵阵，若若A的的前前n1个个顺顺序序主子式不为零，则主子式不为零，则A有唯一的有唯一的Doolittle(Crout)分解。分解。3.2 矩阵的三角分解矩阵的三角分解7/25/证明1 对Doolittle分解进行证明。存在性： A的顺序主子式 ，
12、根据Gauss顺序消去法的消元过程有 记得A=LU。 A=LU的唯一唯一性证明:三角分解条件三角分解条件设A有两个Doolittle分解 为单位下三角矩阵, 为上三角矩阵。将矩阵进行分块如下：将矩阵进行分块如下：7/25/矩阵的三角分解条件证明续证明续唯一性得证唯一性得证7/25/存在性存在性： 所以 A=Crout分解证明分解证明7/25/ 唯一性可类似唯一性可类似Doolittle分解分解的方法可证的方法可证。Remark：实际中对实际中对A进行三角分解并不是按上进行三角分解并不是按上述过程进行的，而是直接使用矩阵乘法得到。述过程进行的，而是直接使用矩阵乘法得到。（下面以（下面以Doolittle型三角分解为例。）型三角分解为例。）Crout分解证明续分解证明续7/25/设A=LU Step1：比较第一行元素比较第一列元素： 直接三角分解法直接三角分解法7/25/三角分解（2）Step2：比较第二行元素比较第二列的元素： 7/25/设U的前k-1行以及L的前k-1列已求出。比较第k行元素直接三角分解法Step k： 续续7/25/续续2比较第k列元素7/25/紧凑格式7/25/
