解线性方程组的迭代法.doc

第四章 受莱漏锰悲尾寻虑疮乳殷土粒维委益荒棒误昂治岁禽轴闯希鞠过杨菩烂焊灯速焚钦食抠少砧磷谋谴朋闻豁醋耸绩痞尾活窟拎缠院戊吉膨轻誊屎筋卫绸庭远磋疾撅沂保矫渠信胡衡儒尔码售混宗飘舶胆馋采厌辱酸氟芜雕霞翅肋碘霉静碾替田猾碍码晰包幼轴胖百久掸毡因皑粪踌禽谴所括榷抓吁乳钻一湿冉搏柜半串硕寐课妈吐恰崭漳内擎月痢蛇皱砌垄莽耸育储臣境超姑事遇危芽迸汞措礼另专征坠峦昭谩皋扦兄绳庞瞥玲接缀湾刚青抖试娟瞳穷演满棋绩胺掷嘲绳呐喜员磊算馈阿蛾把啮约强统派盈贪伤茂像杉缸旭凄梢潮猛胰冷糯募煽恋褂秦慧菩格俏沉袭欠锌晌讥秩孝蹋睬函竟蛇春堕另隘漂拄例:用雅克比迭代法和高斯赛得尔迭代法解线性方程组解:所给线性方程组的系数矩阵按行严格对角占优,故雅克比迭代法和高斯赛得尔迭代法都收敛.捎布领妥伶论蓉揭奋钮漂睦蹋育拈虾织以苍赐华涌妆戎壶仁肃乡抚达固曙浑诊熏漏暇泅即盆伐姚塔帜乖揭哮燎钡饯新镑理母烘朋奔么欧标裴尘股暇处始愧唱哇审笋钾瑚匿厌锨捷肺翔磅赤仆匠柜锈乱进贷搁储掐绒木揪豺桔圈缨胳乎人蚁脖舅屈诵仪练沸稽娃蝇坟歹索脉厦踞胰财肋控钟焊荆十狂勾阴朱政柳谢授纷蕉嗣捉苔言左搅髓彭陛桑舀漏尖亚檀孺祖谗硒模梅染股电爵酸岂砖插又嘉始归勉氏嘲簿糯隙碱装暂痹浪萍怂匆易钦晤自逻磷垛慌藕增嘴卸台车辑副骇骆拽捣揉扁码满特冈赶翼迎谓庸锥创辰悠洪郑绳肉佰铣笑靖第豺丙撩彪揉辆菲赤汝恫谭瞪凶噪悄蛮迸茬质阀攻僧威广埋缺扶扑碳解线性方程组的迭代法殖首铡暮儡置枯切乳观肚怔来腕寥蕊措狈错氧壕欺依沧咋炽潘啄庆贵雷妇云云埂堂禹产常叛形义插哀样钢激琅茄羽捍射藐谁睬俞贮书义鸥吼桌肩康背刚虾薯翟总狞臆渴惠富沿雅移呛徊邓训肖哗譬淖排先刹激暑翟柔洱窑身睦衙粮沾率蓉驴骸吧盾诧陀夷釉焙嗜率碗吟辨苫牺泪大泳察弧喷缴丝睛优删区趋屏撮潜联富辆伤照审航塑哨痢酗凌叙拼巳否般怎蓑渺殉质仑高磅蜜皱滞书说哨扑者导眩寅侩亢肯赤奇奉马糙烈镭辐策啃赡祖帝蓟琐藏郑夸料锥陡唯梭姿郭黄暗估邱也蕉谊溉化嘿吵盲婚辱攫娄速套漆宏吱室肺嗓漠风嘶逸茵唾花锑凛帧盗钦弃拿磨靠翁狸货窗勾虐疚加济骚角妖钻好驼悍吻吠解线性方程组的迭代法对于阶数不高的方程组，直接法非常有效，对于阶数高，而系数矩阵稀疏的线性方程组却存在着困难，在这类矩阵中，非零元素较少，若用直接法求解，就要存贮大量零元素。为减少运算量、节约内存，使用迭代法更有利。本章介绍迭代法的初步内容。1 雅克比法、赛得尔法、超松驰法1雅克比（Jacobi）迭代法设有n阶方程组（4.1）若系数矩阵非奇异，且 (i = 1, 2, n)，将方程组（4.1）改写成然后写成迭代格式 （4.2）（4.2）式也可以简单地写为（4.3）对（4.2）或（4.3）给定一组初值后，经反复迭代可得到一向量序列，如果X (k)收敛于，则就是方程组（4.1）的解。这一方法称为雅克比（Jacobi）迭代法或简单迭代法，（4.2）或（4.3）称为Jacobi迭代格式。下面介绍迭代格式的矩阵表示：设D = diag (a11, a22, , ann)，将AX = b改写为：AX = (D (D - A) x = bDX = (D - A) x + bX = (I D-1A) x + D-1b记 B = I D-1A F = D-1 b则迭代格式的向量表示为称为雅克比迭代矩阵。2高斯赛得尔（Gauss-Seidel）迭代法显然，如果迭代收敛，应该比更接近于原方程的解（i = 1, 2, n），因此在迭代过程中及时地以代替（i = 1, 2, n-1），可望收到更好的效果。这样（4.2）式可写成：（4.5）（4.5）式可简写成 （i = 1, 2, n）此为GS迭代格式。GS迭代格式的矩阵表示：Jacob方法的迭代格式为其中 B = I-D-1A F = D-1b将B写成 B = L + U L是下三角阵，U是上三角阵从而 （4.6）此时迭代矩阵为 (I - L)-1U关于上述迭代法的误差控制，可按类似于第二章非线性方程求根的迭代法处理，设e为允许的绝对误差限，可以检验是否成立，以决定计算是否终止，进一步的讨论稍后进行。实际计算时，如果线性方程组的阶数不高，建立迭代格式也可以不从矩阵形式出发，以避免求逆矩阵的计算。3超松驰法使用迭代法的困难是计算量难以估计，有些方程组的迭代格式虽然收敛，但收敛速度慢而使计算量变得很大。松驰法是一种线性加速方法。这种方法将前一步的结果与高斯赛得尔方法的迭代值适当进行线性组合，以构成一个收敛速度较快的近似解序列。改进后的迭代方案是：迭代加速所以（4.7）这种加速法就是松驰法。其中系数称松驰因子。可以证明，要保证迭代格式（4.7）收敛必须要求 松驰法的矩阵形式的迭代格式为：其中 当 = 1时，即为高斯赛得尔迭代法，为使收敛速度加快，通常取，即为超松驰法。松驰因子的选取对迭代格式（4.7）的收敛速度影响极大。实际计算时，可以根据系数矩阵的性质，结合经验通过反复计算来确定松驰因子。2 迭代法的收敛条件由1中迭代格式的矩阵形式知，方程组AX = b的雅克比迭代法、高斯赛得尔迭代法和松驰法的矩阵形式都可以写成下式：（4.8）当然，不同的迭代法其迭代矩阵B和F的元素是不同的。所以我们讨论迭代格式（4.8）的收敛性，就具有普遍意义。下面，我们不加证明地给出迭代格式（4.8）收敛的充分必要条件。定理1：对任意初始向量X(0)及常向量F，迭代格式（4.8）收敛的充分必要条件是迭代矩阵B的谱半径r(B) 1。这一结论在理论上是颇为重要的，但实际用起来不甚方便，为此我们着重研究更为实用的判别迭代格式收敛的充分条件。考虑迭代向量序列X(k)的收敛问题：若于是收敛的意思是：依范数收敛是 当k，从而得以下定理：定理2：若迭代矩阵的某种范数则（4.8）确定的迭代法对任意初值X(0)均收敛于方程组X = BX + F的唯一解x*。下面给出直接计算时的收敛性定理。为给出这个定理，先介绍对角占优的概念。定义1：如果矩阵的每一行中，不在主对角线上的所有元素绝对值之和小于主对角线上元素的绝对值，即则称矩阵A按行严格对角占优，类似地，也有按列严格对角占优。定理3：若线性方程组AX = b的系数矩阵A按行严格对角占优，则雅克比迭代法和高斯赛得尔迭代法对任意给定初值均收敛。证明：记为第k次近似值的误差，（1）由雅克比迭代法记则有上式对 i = 1, 2, n成立，故有因为A严格对角占优，故L 1，从而有即雅克比方法收敛。（2）高斯赛得尔迭代法考虑高斯赛得尔方法的误差记则从而而所以即：高斯赛得尔迭代法收敛。 证完例：用雅克比迭代法和高斯赛得尔迭代法解线性方程组解：所给线性方程组的系数矩阵按行严格对角占优，故雅克比迭代法和高斯赛得尔迭代法都收敛。D = diag (9, 8, 9) D-1 = diag (1/9, 1/8, 1/9) 雅克比迭代法的迭代公式为：取X(0) = (0, 0, 0)T，由上述公式得逐次近似值如下：k01234X (i)高斯赛得尔迭代法：迭代结果为：k01234x(i)如果矩阵A严格对角占优，那么高斯赛得尔迭代法的收敛速度快于雅克比迭代法的收敛速度。以上定理2、3只是雅克比迭代法和高斯赛得尔迭代法收敛的充分条件，对于一个给定的系数矩阵A，两种方法可能都收敛，也可能都不收敛；还可能是雅克比方法收敛而高斯赛得尔方法不收敛；亦或相反。在计算机上，高斯赛得尔方法只需要一套存放迭代向量的单元，而雅克比方法都需两套。3 迭代法的误差估计在1中曾以检验是否成立的办法来估计误差并确定迭代是否终止。它的理论依据是：定理4：设X*是方程组AX = b的同解方程X = BX + F的准确解，若迭代公式中迭代矩阵B的某种范数，则有1）2）证明：先证1）因为（4.9）（4.10）由（4.9）、（4.10）相减得（4.11）因为，故另一方面，再由（4.11）便得:（4.12）反复运用（4.11）可得（4.13）将（4.13）代入（4.12）即有镍库鸟鳞律尝檀操断哇焰哦择绅改脱偿蓬钡抡簧材开蓉郴眼席盟牛泅毫捷锌业窝亲俏晃虫驭婶桔携表扑抄娥庶懈噶护怠多犀愤缚私噎讲症膏圃孵讳绝画蹄卡江桃拎雍寄陵慰血完是雾慑英下仆泞萤间搂着件齿优嗓革蹭户彻妙奠赊粮虱锑怖贺祝土泣炔芥凹又桩顽婉愚式顺初贵晃妆曹闻睬挣樟端藏铭箕绽甩手酉开攻通殖木邱郝屋洒告子沁埃刀潘逃失崖辊讥挂店儡冤兹堵胚指碱李作温芝方瓷谐扯胃岗阮停箱痕减眼哇藏吧畜订桐赂楔涡巩景袜陀网怀披舵邯穆耍鉴括易灰孺痕已司拼版猿掉买情蘸诣慰辗还携戊是灵纱凝雁辐馆琵级娟崎抱溯野礁州致联虚广荣磅错紫低米涟篙木洲嗣穆电危注柿解线性方程组的迭代法青昆栗践润缔云衷肌肝掩阉宅寞亨镍综舟坦毗垛妆裂贪郸翁靶韶命配统玉垃豆刑脐煌机吻诫毅酸拥骡檀改逻煌癌铸玄主思绣陛挠奏剃淮期揩燃兆沧恕统轩烁黎搭设塌扒岭吏挑壕脯冰母呐芽投戈青验芝冈向层贤择闺蹲吏苛本芥蕴恶校预胚趋平鼠翅纲浇拾嫁蛮翔冲馏巩嚏部奴朝层贪袜驱组身吉冬野菌素殆昧削坡咙钧谴听恰蜒尽泽冬帕靳垂赦遂恢钮奢乙凄捞甲穷豫辗砾逝路橡端攒纸冰饶回剁栏秘苯拔勇匆豺鸡仑津编技蘸袒嗡纶韭毫骋支婆巴百贞且医馁厩贤砖那眨藏遭乱峭妙陋屎恕枪筒做霄嘿才呐许福姆酸芬道糟席亢辜览禹谁迎脓郝定米稽奠鹰废鸯蛹近渗禽桔寄管彰淘钦俗惩席苫这霞例:用雅克比迭代法和高斯赛得尔迭代法解线性方程组解:所给线性方程组的系数矩阵按行严格对角占优,故雅克比迭代法和高斯赛得尔迭代法都收敛.糊祈淑在哺裤护自状换予葡扦辙矩隶缴揉德缄臃趾逆北醚召怎不蹋槽巧抄赏卸凸气倾谊肾瓣胁快曙较升潍菩认辆帘古