三角分解解线性方程组的公式.ppt

《三角分解解线性方程组的公式.ppt》由会员分享，可在线阅读，更多相关《三角分解解线性方程组的公式.ppt（46页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。

1、的求解过程为:可推导求解单位下三角形方程组 的递归公式为:求解上三角形方程组 的递归公式为:三角分解解线性方程组的公式三角分解解线性方程组的公式12/26/直接三角分解法 发现计算 的规律与计算 的规律相同,因此计算 的求方程组的过程可用三角分解的紧凑格式取代。事实上，这只要把 做为A的第n1列进行直接三角分解即可。Reamrk：上述直接三角分解法所对应的是Gauss顺序消去法，二者的乘除运算次数是相当的。实际中对阶数较高的线性方程组，应采用选主元的三角分解法求解，以保证计算结果的可靠性。续续12/26/设对 的分解已完成k-1步，即L 的前k-1列,U之的前k-1行已求出：第k步计算：先选主

2、元，再计算列，最后计算行3.3 列主元直接三角分解法列主元直接三角分解法12/26/参选主元量若 ,则需将第k行与第ik行完全交换，这样满足前面情形，按第一种情形实施计算。12/26/1.正定矩阵的正定矩阵的Cholesky分解分解定义定义：设A为n阶 对称正定矩阵，L是非奇异下三角矩阵，称 为矩阵A的CholeskyCholesky分解。分解。定理定理:n阶 对称正定矩阵A一定存在分解:其中L为单位下三角阵，D是对角元全为正的对角阵且这种分解式唯一;其中L为下三角阵，当限定L的对角元为正时的分解式唯一（Cholesky分解分解）.3.4 平方根法（平方根法（Cholesky分解）分解）12/

3、26/证明：因为因为 A对称正定，故其顺序主式 ，有唯一的DoolittleDoolittle分解从而A 平方根法（Cholesky分解）定理证明定理证明12/26/（D可逆）平方根法（Cholesky分解）即 ,由DoolittleDoolittle分解分解的唯一性，及 的分解过程可知该分解式的唯一性。续续1由DoolittleDoolittle分解的唯一性有12/26/改写则 这时 为一般的下三角矩阵，故 ，若 的对角元全为正时，由DoolittleDoolittle分解的唯一性及上述分解的推理过程，可以得到CholeskyCholesky分解的唯一性。平方根法（Cholesky分解）续续

4、212/26/第一步：平方根法（Cholesky分解）：分解公式分解公式设L前k-1列元素已求出，则第k步12/26/平方根法（Cholesky分解）12/26/ 在分解过程中有n次开方运算，故Cholesky分解法分解法也称为平方根法平方根法。用Gauss顺序消去法求解对称正定的方程组Axb，由用平方根法解对称正定的方程组时，不必考虑选主元的问题，算法本身数值稳定。这表明用Gauss顺序消去法求解对称正定方程组也不用选主元。几点说明几点说明12/26/从运算量的角度看，平方根法是有利的，用平方根法解Axb所需乘除法的运算次数为：令有n次开方运算。n次开方运算一般使用迭代法，所需乘除法的运算次

5、数大约为n的常数倍。故平方根法总的乘除法运算次数大约为为避免开方运算，也可对A做 分解。续续12/26/ 矩阵对角占优的概念矩阵对角占优的概念 类似地，也可定义按列对角占优和按列严格对角类似地，也可定义按列对角占优和按列严格对角占优的概念。通常的对角占优是指按行或者按列。占优的概念。通常的对角占优是指按行或者按列。则称矩阵则称矩阵A按行严格按行严格对角对角占优。占优。则称矩阵则称矩阵A按行对角占优按行对角占优。3.5 三对角线性方程组求解三对角线性方程组求解12/26/满足严格对角占优条件 严格对角占优的矩阵行列式不等于零，故该系数矩阵的各级顺序主子式不等于零。追赶法解三对角方程组追赶法解三对

6、角方程组12/26/ 若A为上述三对角阵时，则A有三角分解：追赶法解三对角方程组分解公式12/26/追赶法解三对角方程组由 得 由 得 方程求解公式12/26/追赶法解三对角方程组Remark：只要三对角矩阵按行严格对角占优，则追只要三对角矩阵按行严格对角占优，则追赶法定能进行下去，且计算过程是稳定的（不必选赶法定能进行下去，且计算过程是稳定的（不必选主元素），其乘除法运算次数为主元素），其乘除法运算次数为5 5n4 4。上述方法上述方法称称为解三为解三对角方程组的对角方程组的追赶法追赶法，又称为，又称为Thomas方法。方法。说明12/26/其中Ai，Bi，Ci均为q阶矩阵，是q维向量。对于

7、这种方程组，可以类似地建立追赶法。追赶法解块状三对角方程组12/26/追赶法解块状三对角方程组其中I为q阶单位矩阵，Li和Ui是q阶矩阵。根据矩阵的分块运算，容易求得块三对角方程组的追赶法如下：续12/26/追赶法解块状三对角方程组续212/26/4.1 4.1 向量范数向量范数1.定义：设 的某个实值函数 满足(3).（三角不等式）(2).（齐次性）c为任意实数(1).（非负性)当且仅当 时有 0则称 是 上的一个向量范数。4 矩阵的条件数和方程组的性态12/26/证明：故必有命题1 向量范数具有性质：4.1 向量范数连续性定理连续性定理：设 为 上的某种范数，则 为分量的连续函数.证明：1

8、2/26/对任意给定正数 向量范数范数连续性证明12/26/等价性定理：设 是 上的两种向量范数，则存在与 无关的常数 ，使得 证明：当 时上式显然成立。故假设首先证明存在常数由连续性定理结论成立。等价性定理12/26/向量范数的性质联合即得 即 ，其中 使同理 有续12/26/1定义：如果矩阵A 的实值函数 ，满足：（1）正定性：（当且仅当A=0）（2）齐次性：c为实数（3）三角不等式 其中A,B（4）则称 是 上的一个矩阵范数。特别地，若还具备特性（5）(为 的某种向量范数)则方阵范数特别叫做与向量范数 相容的方阵范数。4.2 矩阵范数12/26/ 称为A的行范数；称为A的列范数；称为A的

9、2一范数，其中 表示 的按模最大的特征值。称为A的F一范数。常用的矩阵范数12/26/ 设 ,A ,给出一种向量范数 (p=1，2或 等)定义矩阵的非负函数 是 上矩阵的一种范数,称为A的算子范数，也称从属范数。Remark：向量范数 所导出的矩阵范数 与该向量范数是相容的。矩阵的算子范数12/26/定理：设 则证明：（1）设 。不妨设A 。(A=0时显然二者一致)常用向量范数与矩阵范数间的关系12/26/即对任何非零向量 有 （a）下面来说明有一向量 使 设 在第 行达到，即算子范数（续）证明12/26/且A 的第 个分量为即有 （b）结合（a），（b）得 取向量 其中 （j=1，2，n）（

10、2）证明与（1）类似。算子范数（续）这说明证明12/26/（3）因A为实矩阵，故 为实对称的，并且还是非负定的。设 为任一非零向量，则有故 的特征值排列为其中 为标准正交的特征向量，为组合系数。设算子范数（续）证明12/26/即从而得到 取 ,则算子范数（续）证明12/26/背景：实际求解方程组Axb时，A和b都可能有微小变化，如计算机计算时产生的舍入误差，采集数据误差等，此时方程组的解会如何变化？例：求解方程组该方程组的精确解是x1=x2=1。考虑系数矩阵及右端项有微小扰动的方程组：该方程组的精确解是x1=-2，x2=8.5。扰动方程组解的误差界12/26/从上例可看出，虽系数矩阵和右端向量

11、变化很小，但解的误差却很大。这说明该方程组的解对系数矩阵和右端项的扰动很敏感。事实上，该方程组的系数矩阵行列式仅为-0.002，方程组的解为两条接近平行的直线的交点，因而当其中一条直线稍微变化时，新交点与原来的交点相偏离很远。方程组的这种扰动性质是由其系数矩阵的固有性质所确定的。举例分析12/26/定理：设有方程组Ax=b，其中A非奇异。设A和b有微小扰动A和b，扰动后的方程组为这里用到向量范数和矩阵范数相容。则当 时，有误差估计 扰动方程组解的误差界证明：将扰动方程组与原方程组相减，得12/26/扰动方程组解的误差界（续）因Axb，故上式为：故证明12/26/扰动方程组解的误差界Remark

12、：若方程组仅有右端扰动b，即A0时,解的误差界为：若方程组仅有系数矩阵扰动A，即b0时，解的误差界为：结论：解的相对误差是在扰动相对误差 和 的基础上通过量 所刻划的，其大小反映了解的相对误差的大小。分析12/26/定义：设A是n阶非奇异矩阵，称 为矩阵A的条件数。由此可见，当Cond(A)较大时，A和b的小扰动可能引起解的较大误差，故条件数Cond(A)刻划了方程组Axb的性态。条件数12/26/例：n阶Hilbert矩阵nCond2(A)nCond2(A)35.2410274.75 10841.55 10481.53 101054.77 10594.93 101161.50 107101.

13、601013例12/26/Remark：对于给定的Axb，计算 涉及到矩阵求逆。按照定义，若Axb的解x和有小扰动的方程组 的解 误差很大，则原方程组是病态的。但这并不是一个实用的判断方法。一种可能的情况是，若 接近于零或者说A的行向量组（或列向量组）近似线性无关，则有可能方程组Axb病态。至于 是否接近于零，可在列主元消去法的进行过程中观察是否某个主元 绝对值很小而进行判断。说明12/26/矩阵的条件数和方程组的性态另外一种情况是，当A的元素数量级差别很大并且无一定规则时，方程组Axb可能病态。如：相应的方程组Axb是病态的。但对于相应的方程组Axb是良态的。续12/26/一般病态方程组的求

14、解是比较困难的。方程组给定，其系数矩阵的条件数就随之确定，所以方程组的性态是方程组的固有性质，与求解方法无关。一般来说，在计算机上求解的方程组都是所给方程组的扰动方程，这是因为计算机存储数据的舍入误差所致。对于良态方程组，只要求解方法稳定，即可得到比较满意的计算结果。但对于病态方程组，即使用稳定性很好的算法求解也未必得到理想的结果。对于病态方程组Axb的求解，可在计算实践中考虑下述方法的使用：关于病态方程组的求解12/26/关于病态方程组的求解1.采用高精度的算术运算采用高精度的算术运算，如采用双精度运算，使，如采用双精度运算，使由于舍入误差的放大损失若干有效位数之后，还能由于舍入误差的放大损

15、失若干有效位数之后，还能保留一些有效位数，从而改善和减轻保留一些有效位数，从而改善和减轻“病态病态”的影的影响响。2.对对原方程组作一些预处理原方程组作一些预处理，如进行，如进行矩阵平衡矩阵平衡，以，以降低矩阵的条件数。矩阵平衡就是给降低矩阵的条件数。矩阵平衡就是给A的每一行的每一行（或每一列）分别乘以适当的常数，即找可逆的对（或每一列）分别乘以适当的常数，即找可逆的对角阵角阵D1和和D2，使方程组使方程组Axb转化为：转化为：D1AD2y=D1b,D2y=x理论上应选择D1和D2，使Cond(D1AD2)min，但实际上这很难实现，一般矩阵的平衡只是针对具体问题进行具体的处理。续12/26/关于病态方程组的求解一种简单的处理办法是令D2I，这称为行平衡。D1的选择可使 每一行的范数大体相当，以避免消元过程中“大数吃掉小数”。具体的处理方法如下：设有n阶方程组Ax=b，A=(aij)nn非奇异，计算则得到与Ax=b等价的方程组DAx=Db，其系数矩阵DA的条件数有可能大大低于A的条件数。续212/26/关于病态方程组的求解例：对方程组系数矩阵的条件数 故此方程组病态的。采用行平衡，取D=diag(10,10-10)，则得到同解方程组此时系数矩阵的条件数 续312/26/