解线性方程组的直接法省公共课一等奖全国赛课获奖课件.pptx

计计计计算算算算方方方方法法法法课课课课件件件件 第第5 5章章 解线性方程组直接法解线性方程组直接法 在在自自然然科科学学和和工工程程技技术术中中,很很多多问问题题归归结结为为解解线线性性方方程程组组.有有问问题题数数学学模模型型中中虽虽不不直直接接表表现现为为含含线线性性方方程程组组,但但它它数数值值解解法法中中将将问问题题“离离散散化化”或或“线线性性化化”为为线线性性方方程程组组.所以线性方程组求解是数值分析课程中最基本内容之一所以线性方程组求解是数值分析课程中最基本内容之一.线性方程组线性方程组:结束常记为矩阵形式常记为矩阵形式 Ax=b (5.2)1第第1 1页页计计计计算算算算方方方方法法法法课课课课件件件件 此时此时A是一个是一个nn方阵方阵,x和和b是是n维列向量维列向量.依据线性代数知识若依据线性代数知识若|A|0,(5.2)0,(5.2)解存在且唯一解存在且唯一.关关于于线线性性方方程程组组解解法法普普通通分分为为两两大大类类,一一类类是是直直接接法法,即即经经过过有有限限次次算算术术运运算算,能能够够求求得得(5.1)(5.1)准准确确解解(假假定定计计算算过过程程没没有有舍舍入入误误差差).).如如线线性性代代数数课课程程中中提提到到克克莱莱姆姆算算法法就就是是一一个个直直接接法法.但但该该法法对对高高阶阶方方程程组组计计算算量量太太大大,不不是是一一个个实实用用算算法法.实实用用直直接接法法中中含含有有代代表表性性算算法法是是高高斯斯消消元元法法,其其它它算算法都是它变形和应用法都是它变形和应用.另另一一类类是是迭迭代代法法,它它将将(5.1)(5.1)变变形形为为某某种种迭迭代代公公式式,给给出出初初始始解解x0 0,用用迭迭代代公公式式得得到到近近似似解解序序列列xk k,k=0,1,2,=0,1,2,在在一一定定条条件件下下xk kx*(准准确确解解).).迭迭代代法法显显然然有有一一个个收收敛敛条条件件和和收敛速度问题收敛速度问题.这这两两种种解解法法都都有有广广泛泛应应用用,我我们们将将分分别别讨讨论论,本本章章介介绍绍直直接接法法.结束结束 2第第2 2页页计计计计算算算算方方方方法法法法课课课课件件件件 35.1 5.1 消元法消元法5.1.1 5.1.1 三角形方程组解三角形方程组解 下面三种形式线性方程组较轻易求解下面三种形式线性方程组较轻易求解.若若 则则 运算量：运算量：1.对角形方程组对角形方程组第第3 3页页计计计计算算算算方方方方法法法法课课课课件件件件 4 运算量运算量：求：求xi需要需要i-1次乘法和次乘法和1次除法，次除法，i=1,n 2.下三角方程组下三角方程组 若若 则则 代入第代入第2方程，可得方程，可得 共共1+2+n=n(n+1)/2=O(n2)第第4 4页页计计计计算算算算方方方方法法法法课课课课件件件件 5 3.上三角方程组上三角方程组 运算量运算量：求：求xi需要需要n-i次乘法和次乘法和1次除法，次除法，i=n,n-1,1 若若 则则 代入倒数第代入倒数第2方程，可得方程，可得 共共1+2+n=n(n+1)/2=O(n2)第第5 5页页计计计计算算算算方方方方法法法法课课课课件件件件 高高斯斯消消元元法法是是一一个个古古老老方方法法.我我们们在在中中学学学学过过消消元元法法,高高斯斯消消元元法法就就是是它它标标准准化化、适适合合在在计计算算机机上上自自动动计计算算一一个个方方法法.1 1 高斯消元法基本思想高斯消元法基本思想例例1 1 解方程组解方程组 (5.3)(5.3)(5.4)(5.4)(5.5)(5.5)第一步第一步,将将(5.3)(5.3)乘乘-2-2加到加到(5.4)(5.4)；(5.3)(5.3)乘乘-1-1加到加到(5.5),(5.5),得到得到 (5.3)(5.3)(5.6)(5.6)(5.7)(5.7)6结束结束5.1.2 Gauss5.1.2 Gauss消元法与列主元消元法消元法与列主元消元法第第6 6页页计计计计算算算算方方方方法法法法课课课课件件件件第二步第二步,将将(5.6)(5.6)乘乘-2/3-2/3加到加到(5.7),(5.7),得到得到 (5.3)(5.3)(5.6)(5.6)(5.8)(5.8)回回代代:解解(5.8)(5.8)得得x3 3,将将x3 3代代入入(5.6)(5.6)得得x2 2,将将x2 2,x3 3代代入入(5.3)(5.3)得得x1 1,得到解得到解 x*=(2,1,-1)=(2,1,-1)T T 轻轻易易看看出出第第一一步步和和第第二二步步相相当当于于增增广广矩矩阵阵:b在在作作行变换行变换,用用ri表示增广阵表示增广阵A:b第第i行行:结束结束 7第第7 7页页计计计计算算算算方方方方法法法法课课课课件件件件 由由此此看看出出上上述述过过程程是是逐逐次次消消去去未未知知数数系系数数,将将Ax=b化化为为等价三角形方程组等价三角形方程组,然后回代解之然后回代解之,这就是高斯消元法这就是高斯消元法.2 2 高斯消元法公式高斯消元法公式 记记Ax=b为为A(1)x=b(1),A(1)和和b(1)元素记为元素记为 和和 ,i,j=1,2,n.第第一一次次消消元元,目目标标是是消消掉掉第第二二个个方方程程到到第第n个个方方程程中中x1项项,得到得到A(2)x=b(2),这个过程须假定这个过程须假定 0.结束结束 8第第8 8页页计计计计算算算算方方方方法法法法课课课课件件件件 在在A(1):b(1)中中,红红方方框框中中元元素素是是要要化化为为0 0部部分分；A(2):b(2)中中,红红方方框框中中元元素素全全部部已已发发生生改改变变,故故上上标标由由(1)(1)改改(2),(2),计算公式为计算公式为:结束结束 9第第9 9页页计计计计算算算算方方方方法法法法课课课课件件件件 (i=2,3,n)(i,j=2,3,n)(i=2,3,n)(i=2,3,n)第第k次消元次消元(1(1kn-1)-1)设第设第k-1次消元已完成次消元已完成,且且 0,此时增广矩阵以下此时增广矩阵以下:结束结束 10第第1010页页计计计计算算算算方方方方法法法法课课课课件件件件 此此次次消消元元目目标标是是对对框框内内部部分分作作类类似似第第一一次次消消元元处处理理,消消掉掉第第k+1个个方方程程到到第第n个个方方程程中中xk项项,即即把把 到到 化化为为零零.计计算算公公式以下式以下:(i=k+1,n)(i,j=k+1,n)(i=k+1,n)(i=k+1,n)只只要要 0,(k=1,2,n-1)消消元元过过程程就就能能够够进进行行下下去去.当当k=n-1时时,消元过程完成消元过程完成,得得:结束结束 11第第1111页页计计计计算算算算方方方方法法法法课课课课件件件件 它它方方阵阵部部分分A(n)是是一一个个上上三三角角形形矩矩阵阵,它它对对应应方方程程组组是是一一个个上三角形方程组上三角形方程组,只要只要 0,就能够回代求解就能够回代求解,公式为公式为 (i=n-1,n-2,1)综合以上讨论综合以上讨论,高斯消元法解线性方程公式为高斯消元法解线性方程公式为:1 1 消元消元 令令 (i,j=1,2,=1,2,n)结束结束 12第第1212页页计计计计算算算算方方方方法法法法课课课课件件件件(i=k+1,k+2,n)(i,j=k+1,k+2,n)(i=k+1,k+2,n)(5.9)(5.9)2 2 回代回代,若若 0 0 (i=n-1,n-2,1)(5.10)(5.10)结束结束 对对k=1=1到到n-1,-1,若若 0,0,进行进行:13 (i=k+1,k+2,n)第第1313页页计计计计算算算算方方方方法法法法课课课课件件件件3 高斯消元法条件高斯消元法条件 以以上上过过程程中中,消消元元过过程程要要求求 0(i=1,2,n-1),回回代代过过程程则则深深入入要要求求 0,但但就就方方程程组组Ax=b讲讲,是是否否等等于于0是是无无法法事事先看出先看出.注注意意A次次序序主主子子式式Di(i=1,2,n)在在消消元元过过程程中中不不变变.这这是是因因为消元所作变换是为消元所作变换是“将某行若干倍加到另一行将某行若干倍加到另一行”上上,据据线线性性代代数数知知识识,这这类类变变换换不不改改变变行行列列式式值值.若若高高斯斯消消元元过过程程已已进进行行了了k-1步步(此此时时当当然然应应有有 0,ik-1),这这时时计计算算A(k)次次序主子式序主子式:结束结束 14第第1414页页计计计计算算算算方方方方法法法法课课课课件件件件 有递推公式有递推公式(i=2,3,k)显显然然,可可知知,消消元元过过程程能能进进行行到到底底充充要要条条件件是是Di0,(i=1,2,n-1),若若要要回回代代过过程程也也能能完完成成,还还应应加加上上Dn=A0,综合上述有综合上述有:定定理理5.1 高高斯斯消消元元法法消消元元过过程程能能进进行行到到底底充充要要条条件件是是系系数数阵阵A1到到n-1阶阶次次序序主主子子式式不不为为零零；Ax=b能能用用高高斯斯消消元元法法解解充充要要条件是条件是A各阶次序主子式不为零各阶次序主子式不为零.4 高斯消元法计算量预计高斯消元法计算量预计 消消元元过过程程工工作作量量,参参看看公公式式(5.9),k是是消消元元次次数数,k=1,2,n-1,第第 k步步 消消 元元 时时,计计 算算 lik(i=k+1,n)需需 要要 n-k次次 除除 法法；计计 算算 (i,j=k+1,n)需要需要(n-k)2次乘法及次乘法及(n-k)2次次加加减减法法；计计算算 需需要要n-k次次乘乘法法及及n-k次次减减法法,累累计计:结束结束 15第第1515页页计计计计算算算算方方方方法法法法课课课课件件件件 乘除法次数乘除法次数 加减法次数加减法次数 回回代代过过程程工工作作量量,参参见见公公式式(5.10),求求xk需需n-k次次加加减减法法,n-k次次乘法和乘法和1次除法次除法,累计为累计为 乘除法次数乘除法次数 加减法次数加减法次数 总运算次数为总运算次数为 乘除法乘除法 (当当n较大时较大时)结束结束 16第第1616页页计计计计算算算算方方方方法法法法课课课课件件件件 加减法加减法 (当当n较大时较大时)普普通通讲讲乘乘除除法法运运算算比比加加减减法法占占用用机机时时多多得得多多,往往往往只只统统计乘除法次数而称高斯消元法运算量为计乘除法次数而称高斯消元法运算量为 次次.在在上上节节算算法法中中,消消元元时时可可能能出出现现 =0情情况况,高高斯斯消消元元法法将将无无法法继继续续；即即使使 0,但但 =行标行标k时，有时，有得到：得到：(5.22)第第3838页页计计计计算算算算方方方方法法法法课课课课件件件件 394.L第第k列元素：列元素：lk+1,k,lk+2,k,ln,k当行标当行标i=列标列标k时，有时，有得到：得到：(5.23)第第3939页页计计计计算算算算方方方方法法法法课课课课件件件件1.1.解解解解 L y=bL y=b2.2.解解解解 U x=yU x=y结束 40杜利特算法实际上就是高斯消元法另一个形式杜利特算法实际上就是高斯消元法另一个形式杜利特算法实际上就是高斯消元法另一个形式杜利特算法实际上就是高斯消元法另一个形式.它计算量与高它计算量与高它计算量与高它计算量与高斯消元法一样斯消元法一样斯消元法一样斯消元法一样.但它不是逐次对但它不是逐次对但它不是逐次对但它不是逐次对A A进行变换进行变换进行变换进行变换,而是一次性地算出而是一次性地算出而是一次性地算出而是一次性地算出L L和和和和U U元素元素元素元素.L L和和和和U U元素算出后元素算出后元素算出后元素算出后,无须另辟存贮单元存放无须另辟存贮单元存放无须另辟存贮单元存放无须另辟存贮单元存放,可直接存放可直接存放可直接存放可直接存放在在在在A A对应元素位置对应元素位置对应元素位置对应元素位置,节约存贮单元节约存贮单元节约存贮单元节约存贮单元,所以也称为紧凑格式法所以也称为紧凑格式法所以也称为紧凑格式法所以也称为紧凑格式法.AX=b 解：解：第第4040页页计计计计算算算算方方方方法法法法课课课课件件件件杜利特算法可用文字描述以下杜利特算法可用文字描述以下杜利特算法可用文字描述以下杜利特算法可用文字描述以下:将将将将A A元素划分为形如元素划分为形如元素划分为形如元素划分为形如“”n n框框框框,如如如如A A第一行和第一列元素为第一行和第一列元素为第一行和第一列元素为第一行和第一列元素为第第第第一一一一框框框框,紧靠第一框内部第二行和第二列元素为第二框紧靠第一框内部第二行和第二列元素为第二框紧靠第一框内部第二行和第二列元素为第二框紧靠第一框内部第二行和第二列元素为第二框,依这依这依这依这类推类推类推类推,a annnn一个元素为第一个元素为第一个元素为第一个元素为第n n框框框框.为便于描述我们称原为便于描述我们称原为便于描述我们称原为便于描述我们称原A A矩阵中元矩阵中元矩阵中元矩阵中元素为素为素为素为a a元素元素元素元素,计算后每框中每行元素为计算后每框中每行元素为计算后每框中每行元素为计算后每框中每行元素为u u元素元素元素元素(包含对角元素包含对角元素包含对角元素包含对角元素),),每列元素为每列元素为每列元素为每列元素为l l元素元素元素元素(不包含对角元素不包含对角元素不包含对角元素不包含对角元素).).这么我们能够在这么我们能够在这么我们能够在这么我们能够在A A上直接修改计算上直接修改计算上直接修改计算上直接修改计算,作以下操作作以下操作作以下操作作以下操作:(1)(1)第第第第1 1框框框框:u u元素等于对应元素等于对应元素等于对应元素等于对应a a元素元素元素元素;l l元素等于对应元素等于对应元素等于对应元素等于对应a a元素除以本框元素除以本框元素除以本框元素除以本框对角元素对角元素对角元素对角元素;(2)(2)第第第第2 2到到到到n n框框框框:u u元素等于对应元素等于对应元素等于对应元素等于对应a a元素减去已经算过各框中同行元素减去已经算过各框中同行元素减去已经算过各框中同行元素减去已经算过各框中同行同列元素乘积同列元素乘积同列元素乘积同列元素乘积;l l元素除进行以上操作外元素除进行以上操作外元素除进行以上操作外元素除进行以上操作外,还要除以本框对角元还要除以本框对角元还要除以本框对角元还要除以本框对角元素素素素结束 41第第4141页页计计计计算算算算方方方方法法法法课课课课件件件件例例例例 用用用用DoolittleDoolittle分解求解方程组分解求解方程组分解求解方程组分解求解方程组结束 42 得到矩阵由得到矩阵由得到矩阵由得到矩阵由L L和和和和U U元素拼合而成元素拼合而成元素拼合而成元素拼合而成,它上三角部分它上三角部分它上三角部分它上三角部分(包含对角包含对角包含对角包含对角元素元素元素元素)即是即是即是即是LULU分解后分解后分解后分解后U U矩阵矩阵矩阵矩阵;它下三角部分它下三角部分它下三角部分它下三角部分(不包含对角元素不包含对角元素不包含对角元素不包含对角元素)加上一个单位阵加上一个单位阵加上一个单位阵加上一个单位阵(即在对角元处全部写为即在对角元处全部写为即在对角元处全部写为即在对角元处全部写为1),1),就是就是就是就是L L矩阵矩阵矩阵矩阵.第第4242页页计计计计算算算算方方方方法法法法课课课课件件件件 将将LU分分解解换换一一个个提提法法:要要求求L为为普普通通下下三三角角阵阵,U为为单单位位上三角阵上三角阵,就是克劳特分解就是克劳特分解.LT显然是单位上三角阵显然是单位上三角阵,记记结束结束这就是克劳特分解。这就是克劳特分解。有有 43实际上将实际上将A转置为转置为AT,进行进行LU分解分解 AT=LU 则则 A=UTLT显然当显然当A各阶次序主子式非零时各阶次序主子式非零时,它是存在且唯一它是存在且唯一.UT显然是普通下三角阵显然是普通下三角阵,记记5.2.2 克劳特克劳特(Crout)分解分解第第4343页页计计计计算算算算方方方方法法法法课课课课件件件件结束 44 5.2.3 追赶法追赶法追赶法追赶法在很多情况下在很多情况下在很多情况下在很多情况下,如三次样条插值如三次样条插值如三次样条插值如三次样条插值,常微分方程边值问题等都归结常微分方程边值问题等都归结常微分方程边值问题等都归结常微分方程边值问题等都归结为求解系数矩阵为对角占优三对角方程组为求解系数矩阵为对角占优三对角方程组为求解系数矩阵为对角占优三对角方程组为求解系数矩阵为对角占优三对角方程组Ax=fAx=f,即即即即:其中其中其中其中|i-ji-j|1|1时时时时,a aij ij=0,=0,且满足以下对角占优条件且满足以下对角占优条件且满足以下对角占优条件且满足以下对角占优条件:(1)|a(1)|a1 1|b|b1 1|0,|a|0,|an n|c|cn n|0|0(2)|a(2)|ai i|b|bi i|+|+|c ci i|,b|,bi ic ci i0,0,i i=2,3,=2,3,n n-1.-1.第第4444页页计计计计算算算算方方方方法法法法课课课课件件件件 45其系数矩阵其系数矩阵其系数矩阵其系数矩阵A A进行进行进行进行CroutCrout分解分解分解分解,得得得得:比较比较比较比较A A=LULU两边系数两边系数两边系数两边系数,可得可得可得可得:且：且：且：且：第第4545页页计计计计算算算算方方方方法法法法课课课课件件件件结束 46用矩阵乘法比较和用矩阵乘法比较和用矩阵乘法比较和用矩阵乘法比较和CroutCroutCroutCrout分解可推导总结算法步骤以下分解可推导总结算法步骤以下分解可推导总结算法步骤以下分解可推导总结算法步骤以下:1.1.1.1.分解计算分解计算分解计算分解计算2.2.2.2.解解解解Ly=fLy=f3.3.3.3.解解解解Ux=yUx=y第第4646页页计计计计算算算算方方方方法法法法课课课课件件件件结束 47实际计算中实际计算中实际计算中实际计算中Ax=fAx=f阶数往往很高阶数往往很高阶数往往很高阶数往往很高,应注意应注意应注意应注意A A存贮技术存贮技术存贮技术存贮技术.已知数据只已知数据只已知数据只已知数据只用用用用4 4个一维数组就可存完个一维数组就可存完个一维数组就可存完个一维数组就可存完.即即即即 a ai i,b bi i,c ci i,f fi i 各占一个一维数组各占一个一维数组各占一个一维数组各占一个一维数组,u ui i 和和和和 v vi i 可存放在可存放在可存放在可存放在 b bi i,c ci i 位置位置位置位置,y yi i 和和和和 x xi i 则可放在则可放在则可放在则可放在 f fi i 位置位置位置位置,整个运算可在整个运算可在整个运算可在整个运算可在4 4个一维数组中运行个一维数组中运行个一维数组中运行个一维数组中运行.追赶法计算量很小追赶法计算量很小追赶法计算量很小追赶法计算量很小,只是只是只是只是5(5(n n-1)-1)次乘除法次乘除法次乘除法次乘除法.追赶法计算也不要选主元素追赶法计算也不要选主元素追赶法计算也不要选主元素追赶法计算也不要选主元素.例例例例(见教材见教材见教材见教材)第第4747页页计计计计算算算算方方方方法法法法课课课课件件件件其中：其中：结束结束 485.2.4 对称正定矩阵对称正定矩阵LDLT分解分解若若A对称正定矩阵，对对称正定矩阵，对A作作Dolittle分解，可得：分解，可得：第第4848页页