线性方程组的迭代省公共课一等奖全国赛课获奖课件.pptx

第第3章章 线性方程组迭代求解法线性方程组迭代求解法 n3.1 问题提出问题提出 n3.2 简单迭代简单迭代 n3.3 紧凑迭代紧凑迭代 n3.4 松弛迭代松弛迭代 n3.5 高斯消去法高斯消去法 n3.6 三角分解法三角分解法 n3.7 带状方程组三角分解法带状方程组三角分解法 总目录总目录第1页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 xi,N=DN-1AiN xi,N-1+Bi,N xiN =DN本章目录本章目录总目录总目录3.13.23.33.43.53.63.7第2页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.2 简单迭代简单迭代本章目录本章目录总目录总目录3.13.23.33.43.53.63.7n3.2.1 简单迭代公式简单迭代公式n3.2.2 简单迭代计算机算法简单迭代计算机算法n3.2.3 程序实例程序实例 第4页3.2.1 简单迭代公式简单迭代公式n设有N元线性方程组:写成矩阵形式为AX=t。得到下面同解方程组：(3-1)本章目录本章目录总目录总目录3.13.23.33.43.53.63.7第5页3.2.1 简单迭代公式简单迭代公式n记 ，结构迭代公式：收敛充分必要条件:迭代矩阵B 谱半径迭代矩阵某范数 时，迭代收敛。范数小于1只是判断迭代矩阵收敛充分条件.本章目录本章目录总目录总目录3.13.23.33.43.53.63.7第6页3.2.1 简单迭代公式简单迭代公式 当方程组系数矩阵含有一些性质时，可直接判定由它生成简单迭代矩阵是收敛。其条件以下：n（1）为行对角优阵，即 ，。n（2）为列对角优阵，即 ,。以上两个条件只要满足一个，简单迭代过程就收敛。本章目录本章目录总目录总目录3.13.23.33.43.53.63.7第7页3.2.2 简单迭代计算机算法简单迭代计算机算法为了简单起见，在算法中假定矩阵满足简单迭代要求，即，设系数矩阵满足迭代收敛条件：n1、进行变量定义工作，普通需要系数矩阵变量a()、迭代计算变量x1()、初值变量x0()、方程数n、收敛精度及其它一些可能要用到中间变量。n2、利用循环语句和Inputbox()语句输入方程数、系数矩阵与常数项向量元素及收敛精度要求。精度要求也可直接在程序中表达而不进行输入。本章目录本章目录总目录总目录3.13.23.33.43.53.63.7第8页3.2.2 简单迭代计算机算法简单迭代计算机算法n3、依据公式（3-2）计算bij和yi，并置 n4、利用DOLoop Until 语句进行迭代循环计算及偏差计算，当偏差符合要求时，停顿计算，若偏差不符合要求则将向量X0和X1交换，继续进行迭代循环计算。n5、输出方程组解，。本章目录本章目录总目录总目录3.13.23.33.43.53.63.7第9页3.2.2 简单迭代计算机算法简单迭代计算机算法 实例实例n例 3.1：用简单迭代格式解以下方程组：n解：方程迭代格式：简单迭代收敛。本章目录本章目录总目录总目录3.13.23.33.43.53.63.7第10页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.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页3.2.3 程序实例程序实例 n（1）求解方程组开启VB程序依次输入2，2，1，5，3，7，10，就能够得到方程解。方程解为：本章目录本章目录总目录总目录3.13.23.33.43.53.63.7第12页3.2.3 程序实例程序实例n（2）求解方程组 开启上面VB程序依次输入3，5，1，3，5，2，7，-1，10，1，3，10，9，就能够得到方程解。方程解为：本章目录本章目录总目录总目录3.13.23.33.43.53.63.7第13页3.3 紧凑迭代紧凑迭代本章目录本章目录总目录总目录3.13.23.33.43.53.63.7n3.3.1 紧凑迭代公式紧凑迭代公式n3.3.2 紧凑迭代计算机算法紧凑迭代计算机算法第14页3.3.1 紧凑迭代公式紧凑迭代公式n在简单迭代中，我们用 值代入方程(3-2)中计算出 值，计算公式是：已算出分量直接代入迭代式中，及时使用最新计算出分量值。所以 计算 公式可改为：本章目录本章目录总目录总目录3.13.23.33.43.53.63.7第15页3.3.1 紧凑迭代公式紧凑迭代公式n结构 方程组紧凑迭代格式步骤与简单迭代类似，设 ；n将式(3-1)中每个方程 留在方程左边，其余各项都移到方程右边；方程两边除以 ，得到下面同解方程组：本章目录本章目录总目录总目录3.13.23.33.43.53.63.7第16页3.3.1 紧凑迭代公式紧凑迭代公式n记，对方程组对角线以上取第步迭代数值，对角线以下取第步迭代数值，结构紧凑迭代形式：(3-3)本章目录本章目录总目录总目录3.13.23.33.43.53.63.7第17页3.3.1 紧凑迭代公式紧凑迭代公式 实例实例n例3.2：用紧凑迭代格式解方程组n解：方程迭代格式：取初始值 有 时，时，本章目录本章目录总目录总目录3.13.23.33.43.53.63.7第18页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页3.3.2 紧凑迭代计算机算法紧凑迭代计算机算法 比较二者程序，能够发觉，紧凑迭代格式程序上所作修改：n1、是在进行第一轮计算时，需将变量x1(i)赋值为x0（i），在第一次迭代计算时候认为前后两次计算值相同，经过迭代计算不停修改x1（I）值，这种结构安排能够降低计算机内存。n2、在迭代计算公式中直接用了x1(j)，而不是x0(j)，这么能够确保在同一轮计算中不停用新计算得到值代入到迭代公式中，而确保此项工作有效前提是必须首先作第一项修改工作。本章目录本章目录总目录总目录3.13.23.33.43.53.63.7第20页3.3.2 紧凑迭代计算机算法紧凑迭代计算机算法对于紧凑迭代方法收敛条件有：n1:若方程组系数矩阵为列或行对角优阵时，则迭代收敛。n 2:若方程组系数矩阵为正定阵，则迭代收敛。本章目录本章目录总目录总目录3.13.23.33.43.53.63.7第21页3.3.2 紧凑迭代计算机算法紧凑迭代计算机算法n利用已经有程序，我们进行下面两组方程计算，并和直接迭代法进行比较（精度和初值均相同）:方程组方法迭代次数X1X21直接120.999810.999811紧凑70.999520.999812直接40.2828000.1717002紧凑30.282830.17172本章目录本章目录总目录总目录3.13.23.33.43.53.63.7第22页3.4 松弛迭代松弛迭代本章目录本章目录总目录总目录3.13.23.33.43.53.63.7n3.4.1 松弛迭代公式松弛迭代公式n3.4.2 松弛迭代计算机算法松弛迭代计算机算法n3.4.3 松弛迭代松弛迭代VB程序程序n3.4.4 三种迭代方法混合程序示例三种迭代方法混合程序示例 第23页3.4.1 松弛迭代公式松弛迭代公式(3-5)式(3-5)称为松弛迭代计算格式。本章目录本章目录总目录总目录3.13.23.33.43.53.63.7第24页3.4.1 松弛迭代公式松弛迭代公式 实例实例例3.3 请用松弛迭代法求解下面线性方程组，松弛因子为1.1解：方程迭代格式：取初始值 。本章目录本章目录总目录总目录3.13.23.33.43.53.63.7第25页3.4.1 松弛迭代公式松弛迭代公式 实例实例 k=2，3，4迭代计算请读者仿照前面示例，自己完成，并判断按此迭代格式，方程组收敛趋势。时本章目录本章目录总目录总目录3.13.23.33.43.53.63.7第26页3.4.2 松弛迭代计算机算法松弛迭代计算机算法n该法计算机迭代算法，和紧凑格式基本相同，所不一样是在计算x1(I)时作一修改即可，即只需将紧凑格式中：x1(i)=s+t(i)改为：s=s+t(i)x1(i)=(1-omiga)*x0(i)+omiga*s同时在初始化时增加omiga定义及赋值工作即可。本章目录本章目录总目录总目录3.13.23.33.43.53.63.7第27页3.4.3 松弛迭代松弛迭代VB程序程序VB程序只需按上面所述将紧凑格式程序略作修改即可，不再列出，松弛迭代收敛条件以下：n1、松弛迭代收敛必要条件 02。n2、若A为正定矩阵，则当0p时，,而 ，所以 从而可得：即得到了计算上三角阵U第p行元素。同理，可确定L第p列元素。本章目录本章目录总目录总目录3.13.23.33.43.53.63.7第42页3.6.1 三角分解法计算公式三角分解法计算公式n注意，当rp时，则n从而有 即得到了计算L第p列元素。计算A=LU分解公式为：对p=1,2,3,，n,计算上述这种矩阵ALU分解计算次序也可按下列图所表示一框一框逐步进行。（3-15）本章目录本章目录总目录总目录3.13.23.33.43.53.63.7第43页3.6.1 三角分解法计算公式三角分解法计算公式n公式（3-15）中不含消去法中间结果，是可直接逐框计算，所以称为紧凑格式。n现在把矩阵三角分解方法用来求解方程组AX=t，当系数矩阵A完成了A=LU分解后，这时，方程组AX=t就化为L(UX)=t它等价于求解方程组：本章目录本章目录总目录总目录3.13.23.33.43.53.63.7第44页3.6.1 三角分解法计算公式三角分解法计算公式n方程组求解可分两步完成：第一步：先解下三角方程组LX=tL是单位下三角阵，则有若令则得统一计算公式为（3-16）（3-17）本章目录本章目录总目录总目录3.13.23.33.43.53.63.7第45页3.6.1 三角分解法计算公式三角分解法计算公式n第二步：再解上三角方程组UX=Y从下往上回代，即得递推公式：（3-18）本章目录本章目录总目录总目录3.13.23.33.43.53.63.7第46页3.6.1 三角分解法计算公式三角分解法计算公式n例3.4:用三角分解法求解方程组解：（1）分解 A=LU由公式（3-15）得 即（2）求解LY=t （2）求解UX=Y 得到得到本章目录本章目录总目录总目录3.13.23.33.43.53.63.7第47页3.7 带状方程组三角分解法带状方程组三角分解法本章目录本章目录总目录总目录3.13.23.33.43.53.63.7n3.7.1 基本原理基本原理n3.7.2 等带宽方程组求解等带宽方程组求解n3.7.3 带宽为带宽为1三对角方程组求解三对角方程组求解第48页3.7.1 基本原理基本原理n设 ,对于小于n正整数p和q,当 或 时,则称A是含有上带宽q和下带宽p带状矩阵,以带状矩阵为系数矩阵方程组AX=t,称为带状方程组.尤其,当p=q=s时,称s为A半带宽,2s+1称为A总带宽.本章目录本章目录总目录总目录3.13.23.33.43.53.63.7第49页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页3.7.2 等带宽方程组求解等带宽方程组求解该公式可分为以下几步：n(1)分解：A=LU，对k=1，2，n，计算其中（）n（2）求解下三角方程：LY=t本章目录本章目录总目录总目录3.13.23.33.43.53.63.7第51页3.7.2 等带宽方程组求解等带宽方程组求解n（3）求解上三角方程：UX=Y 本章目录本章目录总目录总目录3.13.23.33.43.53.63.7第52页3.7.3 带宽为带宽为1三对角方程组求解三对角方程组求解n当带宽p=q=1时，该等带宽矩阵称为三对角矩阵n求解这么线性代数方程组AX=t，它系数方阵A是一个阶数较高三对角线方阵。简记为，右端项。现在我们也从矩阵三角分解来讨论三对角线性方程组求解。假定系数矩阵存在下式分解：（3-19）本章目录本章目录总目录总目录3.13.23.33.43.53.63.7第53页3.7.3 带宽为带宽为1三对角方程组求解三对角方程组求解nA是带宽为1三对角阵，所以，也含有特殊形式,均为二对角阵，即 在（3-19）等式右端利用矩阵乘法，然后与左端比较，便可得以下确定 元素 计算公式：（3-20）本章目录本章目录总目录总目录3.13.23.33.43.53.63.7第54页3.7.3 带宽为带宽为1三对角方程组求解三对角方程组求解n三对角线性方程组系数矩阵A有了分解式以后，求解AX=t问题就转化为求解两个特殊三角形方程组：（1）（2）得到其递推计算式为 及（3-22）（3-21）本章目录本章目录总目录总目录3.13.23.33.43.53.63.7第55页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页3.7 3.7 带状方程组三角分解法带状方程组三角分解法 n例3.5:用追赶法求解三对角线性代数方程组解由公式(3.20)得分解式元素为本章目录本章目录总目录总目录3.13.23.33.43.53.63.7第57页3.7 3.7 带状方程组三角分解法带状方程组三角分解法 追过程:赶方程:方程组解为:本章目录本章目录总目录总目录3.13.23.33.43.53.63.7第58页