第3章线性方程组的迭代精选PPT.ppt

《第3章线性方程组的迭代精选PPT.ppt》由会员分享，可在线阅读，更多相关《第3章线性方程组的迭代精选PPT.ppt（58页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第3章线性方程组的迭代第1页，本讲稿共58页3.1 问题的提出问题的提出n化工设计和计算中常常要用到线性方程组。n在精馏塔计算中，根据物料平衡、能量平衡、相平衡等建立了MESH方程后，首先要解决的是根据ME方程，计算出各塔板上的各组分的浓度。根据建立的ME方程，经过处理，我们可以得到以下线性方程组：Bi,1 xi,1+Ci,1 xi,2=D1Ai,2 xi,1+Bi,2 xi,2+C2 xi,3=D2Ai,3 xi,2+Bi,3xi3+Ci,3xi,4=D3Ai,jxi,j-1+Bi,jxij+Ci,jxi,j+1=DjAi,N-1 xi,N-2+Bi,N-1 xi,N-1 +Ci,N-1 x

2、i,N=DN-1AiN xi,N-1+Bi,N xiN =DN本章目录本章目录总目录总目录3.13.23.33.43.53.63.7第2页，本讲稿共58页3.1 问题的提出问题的提出n对方程组AX=t 进行等价变换，构造同解方程组X=MX+y，以此构造迭代关系式：任取初始向量，代入迭代式中，经计算得到迭代序列X(1)X(2),。n若迭代序列X(k+1)收敛，设X(k)的极限为X*,对迭代两边取极限即X*=MX*+y，X*是方程组AX=t的解，此时称迭代法收敛，否则称迭代法发散。n线性方程组迭代收敛的充分必要条件是迭代谱半径：本章目录本章目录总目录总目录3.13.23.33.43.53.63.7

3、第3页，本讲稿共58页3.2 简单迭代简单迭代本章目录本章目录总目录总目录3.13.23.33.43.53.63.7n3.2.1 简单迭代公式简单迭代公式n3.2.2 简单迭代计算机算法简单迭代计算机算法n3.2.3 程序实例程序实例 第4页，本讲稿共58页3.2.1 简单迭代公式简单迭代公式n设有N元线性方程组:写成矩阵形式为AX=t。得到下面同解方程组：(3-1)本章目录本章目录总目录总目录3.13.23.33.43.53.63.7第5页，本讲稿共58页3.2.1 简单迭代公式简单迭代公式n记 ，构造迭代公式：收敛的充分必要条件:迭代矩阵B 的谱半径迭代矩阵的某范数 时，迭代收敛。范数小于

4、1只是判断迭代矩阵收敛的充分条件.本章目录本章目录总目录总目录3.13.23.33.43.53.63.7第6页，本讲稿共58页3.2.1 简单迭代公式简单迭代公式 当方程组的系数矩阵具有某些性质时，可直接判定由它生成的简单迭代矩阵是收敛的。其条件如下：n（1）为行对角优阵，即 ，。n（2）为列对角优阵，即 ,。以上两个条件只要满足一个，简单迭代过程就收敛。本章目录本章目录总目录总目录3.13.23.33.43.53.63.7第7页，本讲稿共58页3.2.2 简单迭代计算机算法简单迭代计算机算法为了简单起见，在算法中假定矩阵满足简单迭代要求，即，设系数矩阵满足迭代收敛条件：n1、进行变量定义工作

5、，一般需要系数矩阵变量a()、迭代计算变量x1()、初值变量x0()、方程数n、收敛精度及其它一些可能要用到的中间变量。n2、利用循环语句和Inputbox()语句输入方程数、系数矩阵与常数项向量的元素及收敛精度要求。精度要求也可直接在程序中体现而不进行输入。本章目录本章目录总目录总目录3.13.23.33.43.53.63.7第8页，本讲稿共58页3.2.2 简单迭代计算机算法简单迭代计算机算法n3、根据公式（3-2）计算bij和yi，并置 n4、利用DOLoop Until 语句进行迭代循环计算及偏差计算，当偏差符合要求时，停止计算，若偏差不符合要求则将向量X0和X1互换，继续进行迭代循环

6、计算。n5、输出方程组的解，。本章目录本章目录总目录总目录3.13.23.33.43.53.63.7第9页，本讲稿共58页3.2.2 简单迭代计算机算法简单迭代计算机算法 实例实例n例 3.1：用简单迭代格式解下列方程组：n解：方程的迭代格式：简单迭代收敛。本章目录本章目录总目录总目录3.13.23.33.43.53.63.7第10页，本讲稿共58页n取初始值 ，计算结果由表3-1所示。012345671-1.5-1.25-0.915-0.9575-1.01445-1.00722-0.99754311.62.082.0681.98641.988442.002312.0019710.91.091

7、.0170.98470.997111.00261.000490.60.480.3550.04250.056950.007230.0013.2.2 简单迭代计算机算法简单迭代计算机算法 实例实例方程组的准确解是-1，2，1 表3-1 计算结果本章目录本章目录总目录总目录3.13.23.33.43.53.63.7第11页，本讲稿共58页3.2.3 程序实例程序实例 n（1）求解方程组启动VB程序依次输入2，2，1，5，3，7，10，就可以得到方程的解。方程的解为：本章目录本章目录总目录总目录3.13.23.33.43.53.63.7第12页，本讲稿共58页3.2.3 程序实例程序实例n（2）求解方

8、程组 启动上面的VB程序依次输入3，5，1，3，5，2，7，-1，10，1，3，10，9，就可以得到方程的解。方程的解为：本章目录本章目录总目录总目录3.13.23.33.43.53.63.7第13页，本讲稿共58页3.3 紧凑迭代紧凑迭代本章目录本章目录总目录总目录3.13.23.33.43.53.63.7n3.3.1 紧凑迭代公式紧凑迭代公式n3.3.2 紧凑迭代计算机算法紧凑迭代计算机算法第14页，本讲稿共58页3.3.1 紧凑迭代公式紧凑迭代公式n在简单迭代中，我们用 的值代入方程(3-2)中计算出 的值，计算公式是：已算出的分量直接代入迭代式中，及时使用最新计算出的分量值。因此 的计

9、算 公式可改为：本章目录本章目录总目录总目录3.13.23.33.43.53.63.7第15页，本讲稿共58页3.3.1 紧凑迭代公式紧凑迭代公式n构造 方程组的紧凑迭代格式的步骤与简单迭代类似，设 ；n将式(3-1)中每个方程的 留在方程的左边，其余各项都移到方程的右边；方程两边除以 ，得到下面同解方程组：本章目录本章目录总目录总目录3.13.23.33.43.53.63.7第16页，本讲稿共58页3.3.1 紧凑迭代公式紧凑迭代公式n记，对方程组对角线以上的取第步迭代的数值，对角线以下的取第步迭代的数值，构造紧凑迭代形式：(3-3)本章目录本章目录总目录总目录3.13.23.33.43.5

10、3.63.7第17页，本讲稿共58页3.3.1 紧凑迭代公式紧凑迭代公式 实例实例n例3.2：用紧凑迭代格式解方程组n解：方程的迭代格式：取初始值 有 时，时，本章目录本章目录总目录总目录3.13.23.33.43.53.63.7第18页，本讲稿共58页3.3.1 紧凑迭代公式紧凑迭代公式 实例实例计算结果由表3.2所示。012340-2.5-0.93-1.0062-0.99970802.11.9941.99962.000701.040.99360.9999640.9999641.50.570.070.006本章目录本章目录总目录总目录3.13.23.33.43.53.63.7第19页，本讲稿

11、共58页3.3.2 紧凑迭代计算机算法紧凑迭代计算机算法 比较两者的程序，可以发现，紧凑迭代格式程序上所作的修改：n1、是在进行第一轮计算时，需将变量x1(i)赋值为x0（i），在第一次迭代计算的时候认为前后两次计算值相同，通过迭代计算不断修改x1（i）的值，这种结构安排可以减少计算机内存。n2、在迭代计算公式中直接用了x1(j)，而不是x0(j)，这样可以保证在同一轮计算中不断用新计算得到的值代入到迭代公式中，而保证此项工作有效的前提是必须首先作第一项修改工作。本章目录本章目录总目录总目录3.13.23.33.43.53.63.7第20页，本讲稿共58页3.3.2 紧凑迭代计算机算法紧凑迭代

12、计算机算法对于紧凑迭代方法收敛的条件有：n1:若方程组系数矩阵为列或行对角优阵时，则迭代收敛。n 2:若方程组系数矩阵为正定阵，则迭代收敛。本章目录本章目录总目录总目录3.13.23.33.43.53.63.7第21页，本讲稿共58页3.3.2 紧凑迭代计算机算法紧凑迭代计算机算法n利用已有的程序，我们进行下面两组方程的计算，并和直接迭代法进行比较（精度和初值均相同）:方程组方法迭代次数X1X21直接120.999810.999811紧凑70.999520.999812直接40.2828000.1717002紧凑30.282830.17172本章目录本章目录总目录总目录3.13.23.33.4

13、3.53.63.7第22页，本讲稿共58页3.4 松弛迭代松弛迭代本章目录本章目录总目录总目录3.13.23.33.43.53.63.7n3.4.1 松弛迭代公式松弛迭代公式n3.4.2 松弛迭代计算机算法松弛迭代计算机算法n3.4.3 松弛迭代松弛迭代VB程序程序n3.4.4 三种迭代方法混合程序示例三种迭代方法混合程序示例 第23页，本讲稿共58页3.4.1 松弛迭代公式松弛迭代公式(3-5)式(3-5)称为松弛迭代的计算格式。本章目录本章目录总目录总目录3.13.23.33.43.53.63.7第24页，本讲稿共58页3.4.1 松弛迭代公式松弛迭代公式 实例实例例3.3 请用松弛迭代法

14、求解下面线性方程组，松弛因子为1.1解：方程的迭代格式：取初始值 。本章目录本章目录总目录总目录3.13.23.33.43.53.63.7第25页，本讲稿共58页3.4.1 松弛迭代公式松弛迭代公式 实例实例 k=2，3，4的迭代计算请读者仿照前面的示例，自己完成，并判断按此迭代格式，方程组的收敛趋势。时本章目录本章目录总目录总目录3.13.23.33.43.53.63.7第26页，本讲稿共58页3.4.2 松弛迭代计算机算法松弛迭代计算机算法n该法的计算机迭代算法，和紧凑格式基本相同，所不同的是在计算x1(i)时作一修改即可，即只需将紧凑格式中的：x1(i)=s+t(i)改为：s=s+t(i

15、)x1(i)=(1-omiga)*x0(i)+omiga*s同时在初始化时增加omiga的定义及赋值工作即可。本章目录本章目录总目录总目录3.13.23.33.43.53.63.7第27页，本讲稿共58页3.4.3 松弛迭代松弛迭代VB程序程序VB程序只需按上面所述将紧凑格式的程序略作修改即可，不再列出，松弛迭代的收敛条件如下：n1、松弛迭代收敛的必要条件 02。n2、若A为正定矩阵，则当0p时，,而 ，所以 从而可得：即得到了计算上三角阵U的第p行元素。同理，可确定L的第p列元素。本章目录本章目录总目录总目录3.13.23.33.43.53.63.7第42页，本讲稿共58页3.6.1 三角分

16、解法计算公式三角分解法计算公式n注意，当rp时，则n从而有 即得到了计算L的第p列元素。计算A=LU分解的公式为：对p=1,2,3,，n,计算上述这种矩阵A的LU分解计算顺序也可按下图所示一框一框的逐步进行。（3-15）本章目录本章目录总目录总目录3.13.23.33.43.53.63.7第43页，本讲稿共58页3.6.1 三角分解法计算公式三角分解法计算公式n公式（3-15）中不含消去法的中间结果，是可直接逐框计算的，所以称为紧凑格式。n现在把矩阵的三角分解方法用来求解方程组AX=t，当系数矩阵A完成了A=LU分解后，这时，方程组AX=t就化为L(UX)=t它等价于求解方程组：本章目录本章目

17、录总目录总目录3.13.23.33.43.53.63.7第44页，本讲稿共58页3.6.1 三角分解法计算公式三角分解法计算公式n方程组的求解可分两步完成：第一步：先解下三角方程组LX=tL是单位下三角阵，则有若令则得统一的计算公式为（3-16）（3-17）本章目录本章目录总目录总目录3.13.23.33.43.53.63.7第45页，本讲稿共58页3.6.1 三角分解法计算公式三角分解法计算公式n第二步：再解上三角方程组UX=Y从下往上回代，即得递推公式：（3-18）本章目录本章目录总目录总目录3.13.23.33.43.53.63.7第46页，本讲稿共58页3.6.1 三角分解法计算公式三

18、角分解法计算公式n例3.4:用三角分解法求解方程组解：（1）分解 A=LU由公式（3-15）得 即（2）求解LY=t （2）求解UX=Y 得到得到本章目录本章目录总目录总目录3.13.23.33.43.53.63.7第47页，本讲稿共58页3.7 带状方程组的三角分解法带状方程组的三角分解法本章目录本章目录总目录总目录3.13.23.33.43.53.63.7n3.7.1 基本原理基本原理n3.7.2 等带宽方程组的求解等带宽方程组的求解n3.7.3 带宽为带宽为1的三对角方程组求解的三对角方程组求解第48页，本讲稿共58页3.7.1 基本原理基本原理n设 ,对于小于n的正整数p和q,当 或

19、时,则称A是具有上带宽q和下带宽p的带状矩阵,以带状矩阵为系数矩阵的方程组AX=t,称为带状方程组.特别,当p=q=s时,称s为A的半带宽,2s+1称为A的总带宽.本章目录本章目录总目录总目录3.13.23.33.43.53.63.7第49页，本讲稿共58页3.7.1 基本原理基本原理nn较大,且p,qn,带状矩阵的LU分解只需计算非零元素,且可证明L和U仍保持A的带状结构,即有 A=LU只需计算第k+1至k+p行的元，对U的第k行只需计算第k+1到k+q列的元,从而,当p和q都不大时,其乘除法的计算工作量比小得多.本章目录本章目录总目录总目录3.13.23.33.43.53.63.7第50页

20、，本讲稿共58页3.7.2 等带宽方程组的求解等带宽方程组的求解该公式可分为以下几步：n(1)分解：A=LU，对k=1，2，n，计算其中（）n（2）求解下三角方程：LY=t本章目录本章目录总目录总目录3.13.23.33.43.53.63.7第51页，本讲稿共58页3.7.2 等带宽方程组的求解等带宽方程组的求解n（3）求解上三角方程：UX=Y 本章目录本章目录总目录总目录3.13.23.33.43.53.63.7第52页，本讲稿共58页3.7.3 带宽为带宽为1的三对角方程组求解的三对角方程组求解n当带宽p=q=1时，该等带宽矩阵称为三对角矩阵n求解这样的线性代数方程组AX=t，它的系数方阵

21、A是一个阶数较高的三对角线方阵。简记为，右端项。现在我们也从矩阵的三角分解来讨论三对角线性方程组的求解。假定系数矩阵存在下式分解：（3-19）本章目录本章目录总目录总目录3.13.23.33.43.53.63.7第53页，本讲稿共58页3.7.3 带宽为带宽为1的三对角方程组求解的三对角方程组求解nA是带宽为1的三对角阵，所以，也具有特殊的形式,均为二对角阵，即 在（3-19）等式右端利用矩阵乘法，然后与左端比较，便可得如下确定 的元素 的计算公式：（3-20）本章目录本章目录总目录总目录3.13.23.33.43.53.63.7第54页，本讲稿共58页3.7.3 带宽为带宽为1的三对角方程组

22、求解的三对角方程组求解n三对角线性方程组的系数矩阵A有了分解式以后，求解AX=t的问题就转化为求解两个特殊的三角形方程组：（1）（2）得到其递推的计算式为 及（3-22）（3-21）本章目录本章目录总目录总目录3.13.23.33.43.53.63.7第55页，本讲稿共58页3.7 3.7 带状方程组的三角分解法带状方程组的三角分解法求解三对角线性方程组的追赶法的计算步骤归结为：n（1）由公式（3-20）确定三角分解 中 的元素；n（2）由公式(3-21)求出中间向量Y；n（3）由公式(3-22)求出解向量X。本章目录本章目录总目录总目录3.13.23.33.43.53.63.7第56页，本讲稿共58页3.7 3.7 带状方程组的三角分解法带状方程组的三角分解法 n例3.5:用追赶法求解三对角线性代数方程组解由公式(3.20)得分解式的元素为本章目录本章目录总目录总目录3.13.23.33.43.53.63.7第57页，本讲稿共58页3.7 3.7 带状方程组的三角分解法带状方程组的三角分解法 追的过程:赶的方程:方程组的解为:本章目录本章目录总目录总目录3.13.23.33.43.53.63.7第58页，本讲稿共58页