《关于解大型稀疏线性代数方程组一种算法的误差分析》由会员分享，可在线阅读，更多相关《关于解大型稀疏线性代数方程组一种算法的误差分析（4页珍藏版）》请在金锄头文库上搜索。
1、? ?年?月高等学 校计算数 学 学报创刊号关于解大型稀疏线性代数方程组一种算法的误差分析黄开斌?南京 师 范 学院? ? !? ? ? ? ? !? ? ? ? ? ? !?“? ?一? ? ? ? ?本文利用?主? ?“向后 分析”误差理 论证 明了?中算法念?的 稳定性,并给 出近似解残 量的 估计式。?算法给定线性 代数方程组?二?,?其 中?是大型稀疏 对称正定矩阵。为了有效 地求解 它,所用算法必须是稳 定的,? 且?在计算过程中要求充分利用和保持?的稀疏性,以节省存储量,并使计算时间短,解 的精度高。本文讨论的算法具有上述 特点。经南京一 些单位近几 年的实践,都反映该算法的 计
2、算效果较好。为此本文对它进行误差 分 析,并给 出近似解残量的估计式。对?做 对称三 角分解? ? ?,其 中?是下三角阵,?,是?的 转置矩 阵,?是对角阵?邝,?,?八二二?。于是解?变成 解?和? ?犷、 二?。分解和向前、向后回代的计 算公式分别为忍? ?乙,?。?向艺砷? 了?或 ?,?,?,?。一灯,? ? 龟、了、?、一一声一?山扒“?一习忍?。?“,? ?,?,?,?,?心刀 二“?一?习不。二?不“,?,?,?。?裕?了?,? 分别表示?中第行和第 ? 行 第一个非零 元 的列号。鉴于矩 阵?和矩阵?每行 第一个非零元列号相同,且 位于各行第一个非零元之左的所有零元索可以不
3、参加 计算,故这部分数量极大的“零”不必 存入 机器,经程序处理,相应运算也予避 免。程序 中实现算式? ? ?时,先固定 行号?。 ,继 之?。,算出的艺。 。?乙?。?。按 列号?的次序 分配去做相 应乘法,这样 使分解过程 中除法次数减 少可?日年?月?日收到。高等学校计算数学学报?右 ?年万 艺?一? ?,比通常 除法 次数 的数量 级约降低一 阶。本算法 乘除法总次数 不 超过 祖? ? ?二,?一诊?。“?十? ?,其中。? ?一? ?。若 按? ? ?“对稀 疏矩 阵的描述, ?一一 ”?一”丁?“?“曰一一“一一”一一“, ?川?盯?丁”?川一当。? ?时,本 算法乘除法总次数
4、的数量级 至多为?。当?相 当大仅用内存无 法解?时,可以利用磁盘 对本算 法采用分 块 技 术 解?,从 而方程 组? ?的阶数 实际不 受限制。?误差 分析由于舍入误差 的影 响,方程 组? ?由实际计算所 得的解?乙?并不精确地 满足? ?。“向后 分析”的观 点是将无 ?各?看成 为?的某一扰动问题的精确 解,即?乙? ?从?二?乙?。众所周知,若?一各?,则该方程组?有 解,巨对具性?。此即扰动乙?,乙合?口一?一丈?一?土一 ? ?划一爪一州卜比质? ? 卜?的范数,还有?各? ?乙 ? ? ? 月?气?气少叹“不一丁丽? 一?八? ? 咬爷?一?,?对? ?解的影响 的灵敏程度依
5、赖于矩阵?关于所用范数的条件数? ?。给定方程 组? ? ?及其近似解万、正容 限矩阵?和正容限向量?,是否存在一个邻 近方程 组 ? ?义 ?,?乙?以万为其精 确解? ? ?和? ?对此作了讨 论弓、”,并建 立了万的残量之大小与存在以了为精确 解的邻近方程 组? ?一? ?间的关系。为讨论本文算法的稳定性,首先 给出下列定 义定义?设用 某种算法解方程组? ? ?所得的解丫精确 地满足某一个“邻 近的”方 程组?占? ?至?乙?,其 中? ?,? ?的元素按绝对倪而言都比较小,则 称所用算法是稳定的。定义?当方程 组? ? ?的条件不太 坏 时,用稳定的算法所 得的解被称为是可以接受 的
6、。我们先分别 对 算法的 分解和向前、向后回代 过程进行误差分 析。设参与运算的数都是二进制 浮点 规格 化数,其尾 数 有?位,全过程采用单精度计算并假 定机器 对浮点 算木 运算能 正确地给出具 有规格 化尾数 的舍入结果。关于 分解 过程,有定理?设?是?阶 稀疏 对称正定矩 阵,?二?,是?的对 应于算式? ? ?的浮点计算 实 际分解 式,则误差矩 阵?是对称的,其 元素价,满足?,?,叹sa(j一八)2一, jlj或jNO,2一亡, j= l,(。+2)IR“,2一, j=+1,(留+i一j+4)R, 2一, j二艺+2, N, N, R,是矩 阵万亡望中的元素, NO机n(i+。
7、,N)。(2. 7) g其中艺二1,推论.令R=。a xR, !,则 ,夕 G! 1。告R二(。+7)2一公, (2. 8)定理2.3表明,向前、!句后回代的计算过程是稳定的。综合上述三个定理的结果,得知木文算法是稳定的。最后估计近似解残量b一 A王的界。定 理 4.设呀是用对应于(1.2 )一 (1.4 )的浮点计算所得的(1.1 ) 的近似解,则万是邻近方程组(A十d A)x二b的精确解,其中占 A二E十 LG+F万毛,十F G。并一且 b一 AX满 足 lb一 A 无 。(、+i)2巨 RZ(。+6)+l oa2一 又 !.。 (2.9)至此看出,用本文算法解(1.1 )时舍入误差 的影
8、响等价于一开始 对系数 矩阵A有扰动SA所引起 的误差。估计式 ( 2,9 )中2一,的系数的数 量级比通 常的小。当 ( 1.1 )条件不 太坏时,用该算法所 得的解是可以接受 的。何 旭初先生对本文提 出了许 多宝贵 意见,特此致谢。高等学校计算数学学报1盯9年参考文献1J.H. Wilkin son:Rou ndingErro rinA lgebraiePro eesses,Prentiee-五a11, Ne wJersey,1963.比长野纵:大 型 矩 阵的一种解法,日本钢 构造协会第五回大会研究集会,卜夕,夕,构 造解析 法研 究发表论文 集,pp.1 0一1 7,1971.3R.
9、P.Tewa rson:Spa rseMatriees,Aeademie,Press, New.Yorkand工ondon, PP. 1一2,1973.4W.Oettlia ndW.P户age r:Compatib ilityofApproximateSolutionofLin ea rEgu atio n swithGivenErro rBo u刀dsfo rCon ef fieie ntsandRi gl it一Ha nd5i de s. Nume ris eheMathemat ikBand6, (5),1964.【5J.sto er:Einful iru ng ind ieNumeriseheMathematik.1.Springer一Ver lag刀o rlinZweiteAnflage19 76.
