大学计算方法（C）讲义课件.pdf

《大学计算方法（C）讲义课件.pdf》由会员分享，可在线阅读，更多相关《大学计算方法（C）讲义课件.pdf（69页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、大学计算方法（C）讲义课件目 录第1章 绪 论1.1 数值计算1.2 数值方法的分析1.2.1 计算机上数的运算1.2.2 算法分析第2章 线性代数方程组2.1 Gauss消去法2.1.1 消去法2.1.2 主元消去法2.2 矩阵分解2.2.1 Gauss消去法的矩阵意义2.2.2 矩阵的LU分解及其应用2.2.3 其他类型矩阵的分解2.2.4 解三对角矩阵的追赶法2.3 线性方程组解的可靠性2.3.1 向量和矩阵范数2.3.2 残向量与误差的代数表征2.4 解线性方程组解的迭代法2.4.1 基本迭代法2.4.2 迭代法的矩阵表示2.4.3 收敛性第3章数据近似3.1 多项式插值3.1.1插

2、值多项式3.1.2 Lagrange插值多项式3.1.3 Newton插值多项式3.1.4 带导数条件的插值多项式3.1.5 插值公式的余项3.2 最小二乘近似3.2.1 最小二乘问题的法方程3.2.2 正交化算法第 4 章 数 值 微 积 分4.1 内插求积，Newton-Cotes公式4.1.1 Newton-Cotes 公式4.1.2 复化求积公式4.1.3 步长的选取4.1.4 Romberg 方法4.1.5 待定系数法4.2 数值微分4.2.1 插值公式方法4.2.2 Taylor公式方法（待定系数法）4.2.3 外推法第 5 章 非线性方程求解5.1 解一元方程的迭代法5.1.1

3、简 单迭代法5.1.2 Newton 法5.1.3 害峨法5.1.4 区 间方法5.2 收敛性问题5.2.1 简单迭代一一不动点5.2.2 收敛性的改善5.2.3 Newton法的收敛性5.2.4 收敛速度第 1 章 绪 论1.1 数值计算现代科学的发展，己导致科学与技术的研究从定性前进到定量，尤其是现代数字计算机的出现及迅速发展，为复杂数学问题的定量研究与解决，提供了强有力的基础。通常我们面对的理论与技术问题，绝大多数都可以从其物理模型中抽象出数学模型，因此，求解这些数学模型已成为我们面临的重要任务。一、本课程的任务：寻求解决各种数学问题的数值方法一一如何将高等数学的问题回归到初等数 学（算

4、术）的方法求解一一了解计算的基础方法，基 本 结 构（否则只须知道数值软件）一一并研究其性质。立足点：面向数学一一解决数学问题面向计算机一一利用计算机作为工具充分发挥计算机的功能，设计算法，解决数学问题例如：迭代法、并行算法二、问题的类型1、离散问题：例如，求解线性方程组A x=b 一一从离散数据：矩 阵 A 和向量b,求解离散数据x；2、连续问题的离散化处理：例如，数值积分、数值微分、微分方程数值解;3、离散问题的连续化处理：例如，数据近似，统计分析计算；1.2 数值方法的分析在本章中我们不具体讨论算法，首先讨论算法分析的基础一一误差。一般来讲，误差主要有两类、三 种（对科学计算）：1）公式

5、误差一 一“截断误差”，数学一计算，算法形成一一主 观（人为）：数学问题-数值方法的转换，用离散公式近似连续的数学函数进行计算时，一般都会发生误差，通常称之为“截断误差”；一一以后讨论2）舍入误差及输出入误差一一计算机，算法执行一一客 观（机器）：由于计算机的存储器、运算器的字长有限，在运算和存储中必然会发生最末若干位数字的舍入，形成舍入误差；在人机数据交换过程中，十进制数和二进制数的转换也会导致误差发生，这就是输入误差。这两种误差主要是由于计算机的字长有限，采用浮点数系所致。首先介绍浮点数系1.2.1计算机上的运算一一浮点运算面向计算机设计的算法，则先要讨论在计算机上数的表示。科学记数法一一

6、浮点数：约定尾数中小数点之前的数全为零，小数点后第一个数不能为零。目前，一般计算机都采用浮点数系，一个存储单元分成首数和尾数：XXXXXXX首数/尾数 位)其中首数存放数的指数(或“阶”)部分，尾数存放有效数字。对 于 进 制，尾数字长为t位的浮点数系尸(/7,/,L,U)中 的(浮 点)数，可以用以下形式表示：4%d j d.dddgd嬴,1指 数，含符1位）符,位 52位瓶数浮 点 数 的 特 点：1、实 数 转 换 到 浮 点 数 浮 点 化，缺 点：总 会 产 生 误 差（除极个别的情况：尤=2 ，/=0,1,2,）按四 舍 五 入，绝 对 误 差：|x-力（x）|w g，-（举 例）

7、，优 点：浮 点 化 产生的相 对 误 差 有 界（与 数 字 本 身 的 数 量 级 无 关）|心）卜 匕等1 7?-注：设实数x eR,则按夕进制可表达为:d、d d iX=(+,+Z+,+)X 邛/X+1d/30 d ./，j=2,3,U +1 按四舍五入的原则，当它进入浮点数系尸（尸,心。）时，若d,+i g s，则力(x)=(-+-|+P片 d.-)X j1d d d+若4+1 2彳夕，则 力(x)=(T+T+丁)x 2p p2-y对第一种情况:k 一 力=（热+）x 号分/=#对第二种情况：卜一）（何=一 X，=；夕一p P 乙 乙就是说总有：|x-7 7（x）|w g p 另一方

8、面，由浮点数要求的1 4&，x一力（x）4 I giTx T有,喝 夕,将此两者相除，便得2、每 一 个 浮 点 数 系 的 数 字 有 限：2（，一 1）夕T（U-+1）+13、浮点数系中的运算非自封闭，（因为数字有限、尾数字长有限、指数数字有限等）例：在（1 0,4,-5,5）中，*=.5 4 20 x 10。=2Q 01 x103,运算x*y和x/y,的结果显然已不在此浮点数系内，而x+y或x-y也不在此浮点数系内，需fl（xo y）结果才在此浮点数系内。浮点运算应注意：1）避免产生大结果的运算，尤其是避免小数作为除数参加运算；2）避 免“大”“小”数相加减；3）避免相近数相减，防止大量

9、有效数字损失；4）尽可能简化运算步骤，减少运算次数。原因：记 =m a x|b（x）|=m a x ,由上一力（刈4可乂，可得：|（Xoy）-/7（xoy）|A|x o y|（“。”表示任意一种四则运算）此 处 是由机器字长（实质上是尾数字长f的大小）确定的常数（它反映了实际运算的精度）。显然，若要求运算的舍入误差小，应使运算结果（如：X土较小。尤其是小分母运算：-土=白，小y =大误差。y y y其次，当浮点数系中两个数量级相差较大的数相加（或减），注意到由于浮点数系中数字字长的有限性，可能导致“大数吃小数”。例如，尸（10,4,-5,5）中x =.8 231x l 03,y =.2317

10、x l（）-,则x y =.8 231x l 03.2317 x l 0-1=.8 231 x 103.0000 x 103=x似乎y （没有参加运算。第三，同样，由于浮点数系中数字字长的有限性，当两个相近数相减时：例如，在 10,8,-5,5）中，x =.8 2317 8 4 4 x 1（）3 8 2317 8 32x 1（）3,两数相减：=.12000000 x 10-3,计算结果仅剩2位有效数字，而原来参加运算的数字有8位有效数字，这将严重影响最终计算结果的精度。1.2.2算法分析作为一个可用的算法，必须考虑其效率和可靠性，定义：计算机完成一个乘法和一个加法，称为一个浮点运算（记为fl

11、o p）；注：由于计算机在运算时，加（减）法所耗时间远少于乘（除）法，所以通常只须计算乘法的次数，因此也有“一个算法需要多少个 乘法”这一提法。1、计算效率可 计 算 性（计算复杂性空间、时间）例：解线性方程组A x=b的Grammar方法：%,.人八，其中|A|是方程组系数矩阵A对应的行列式，而|4|则是以右端向量b替代A的第i列所得矩阵对应的行列式。由线性代数知识可知，若A=（a p,则I A|=一1严 四,既 血,，其 中 心 ,露是由 1,2,川 变 换 到 Z,Z2，。所需的置换次数。可见每计算一个行列式，需要（一 1）.!个浮点运算；因此，按Grammar方法解方程组约需个浮点运算

12、。当=20时 N*9.70728x1（）2。，用一个运算速度为1（）8/秒的计算机进行求解，约需3.078x105年（日前报道我国计算机己达到3840 x103秒，这仍需近10年）。而n=20的方程组应该说是一个小型的方程组。因 此Grammar方法是一个不能接受的算法，它缺乏可计算性。第二章将介绍 的Gauss消去法和迭代法就有较高的效率，具有很好的可计算性。2、计算可靠性作为算法，除了考虑其效率外，必须重视可靠性，它包括两方面：问题的性态和 方法的稳定性问题的性态所计算的问题当原始数据发生小扰动时，问题的解一般也发生扰动。问题的性态问题的解对原始数据发生变化的敏感性.原始数据小扰动n 问题

13、解 小扰动问题是良态的大变化问题是病态的例：线性方程组:U613一1247一6 0.1-31-41-5+%1-21-31-41+为匹玉1-21-3若将方程组的系数改写成具有2位有效数字的小数:1.00X1+0.50 x2+O.33x=1.8 0.50 xj+0.33X2+0.25巧=110.33 西+0.25X2+0.20X3=0.78(-6.2 2 的解则变成：X=38.2533.65,这是一个典型的病态方程组。一般：由原 始 数 据X n 计算结果/（X）,扰动后 的 数 据x n 计算结果/（工）,若对问题/存在常数m,满足关系式：/（X）-/G）m x-H/（X）m X或f(x)-f(

14、x)f(x)m=s u p-x-xx则 称（相对误差之比的上界）m为该问题的条件数，记 作m =co nd（f）；由微积分中值定理知识容易计算出，当”亍时，co nd（f）x。稍后我们在第二章将对线性方程组的性态作进一步的分析。算法的数值稳定性：1例：计算/”=JxZZx,=0,1，,8；0解：由微积分知识，可得计算公式，/“=1-叫 I ,/“T =_ L（1 /“）,n我们将准确值与计算结果列表如下：方法/()/2八，51 617A准确值.6 3 2 1.3 6 7 9.2 6 42.2 0 7 3.1 7 0 9.1 45 5.1 2 6 8.1 1 2 4.1 0 1 0.6 3 2

15、1.3 6 7 9.2 6 42.2 0 7 4.1 7 0 4.1 480.1 1 2 0.2 1 6 0-.7 2 80.6 3 2 0.3 6 80.2 6 43.2 0 7 3.1 7 0 9.1 45 5.1 2 6 8.1 1 2 4.1 0 1 0由上表可见，方法中，原始步的误差，随着计算步数的增加被严重地放大,特别是A竟变成负数（注意：被积函数是非负函数），而方法则相反；这是因为方法中，若前步有误差6：I-=/j +，则1k=1 -kl卜-1=1 -kl1 I k3 =I卜-kb ,说 明 的 误 差3,经一步计算后被扩大了左倍，随着女的增大，误差将被大大地扩大；而通过同样的分

16、析可知：方法中人的误差则被缩小2倍。算法的数值稳定性：算法对初始误差导致的最终误差的可控性,如果最终误差被有效地控制，则称算法是稳定的，否则就是不稳定的。第二章线性方程组求解线性方程组：allxl+%2而+自小 5=卜 内+。22心+。2”巧=不an X +a 2x2+-+annxn=pn其中(2.1)aa2 劭 力A=a2a22,9X =,b =A一%2.,a*Pn2.1 G a u ss 消 去 法2.1.1消去法设计方法原则：面向计算机(事先未知元素，编制程序)，例:2 xl+=3X j-x2=02 x+x2=33 _ 3=x2=1 =X =1一5一一5基本思想：降维一一N维问题转化为N

17、-1维问题一一逐次降维，依次进行消去过程一一对方程组(2.1)由上而下逐步消去对角元%*(%=1,2,，-1)以下的aik(i=k+l,-,n),使之转化为如下等价形式，达到目标：冈内+%2+=川+%/“=四,(2.2)%/“=/3 从而，可进入回代过程，再由下而上，逐步解得4 =,2,1)：这儿的akk(k=1,2,/?-1)-主元对问题(2.1)设a”？0,目标：将第2n方程的可的系数a?”,见“转化为0；方法：“第左个方程”-3 x “第1个方程”(女=2,3,得 到nanX+al2x2+-+ainxn=.嫂 巧+a如”=姨 新的第女行，元素变化：（akk=0）,a.=a.-likakj

18、,与=/3i-lik/3k,经过-1步消去（注意：a“以下无元可消），得到（2.2）式。注意：每计算1个儿,%）,分仅需1个浮点运算回代：第一步演=&，第二步九 一弘，/Un-,n-第-Z+1 步 4 J乩一（叼+“+4 无%女=1,，2,1;运算量：消元：n元方程组：第1步消元：对第i a =2,3,）行，共n-1行；每1行：计算。（i=2,3,），1个乘除法（或“浮点运算”），计算新的曙=邱）=4 -4历共（n-D +l个乘除法（或“浮点运算”），第1次元共（-1）口 +（-1）+1=2一1个乘除法，因此，消元的运算量Z（心 1）=Z（1 T）=2 一吟+；k=n k=k=3 2 6回代：

19、第1步，求X”需要1个乘除法（或“浮点运算”），即：第2步求用2个乘除法（或“浮点运算”），一般，第上步求乙_ 八1用改个浮点运算，因此,回代的运算量 力=+1）；I 2 3Gm/ss消去法的总运算量：T=-+n2-。3 3例2-1：解线性方程组例:解:2X+2X2+无3=02%|+212+3巧=3-%i-3X22利用增广矩阵（因为线性方程组的解仅与系数与右端常数项相关）22-31 0、3032八 一2-2-111I0、32左=%2-21 01 3%XJnX=C、-1 7 2-6、4-1501-352、34,;解1=(%-3 7-2-42-2I45I01223-1-22420-135、2426

20、03-36116537418425-960、77(21、3 12-1,11-12、C-2130121-21人（203I11人1-1401-13-7252、-415,1;解1=111(23、42481639278141664256210441901I1J1371622366-10、123453445455730、404357,1234123112-13-2-1412242431254-3-172-3-22-247-11017-147-10-421-1011201-32.1.2（列）主元消去法算法中，若第左步：i）akk=0、I2-1-2231人0151121或 i i)akk|aA|i =k+,

21、-,n则按照原来的简单G m/ss消去法算法可能无法执行，也可能出现大误差:例：在浮点数系厂(1 0,5,-1 0,1 0)中计算；方程组1 0-5 2准确解：x0.2 5 0 0 0 1 8 7 50.4 9 9 9 9 8 7 4 9解：按G a u ss消去法解：.1 0 0 0 0*1 0 7 .2 0 0 0 0*1 0 .1 0 0 0 0*1 0 1 八 尸 0 2。0 011 d 、.2 0 0 0 0*1 0 .3 0 0 0 0*1 0 .2 0 0 0 0*l O J 1 0 0 0 0*1 0-4.2 0 0 0 0*1 0 .1 0 0 0 0*1 0,)、-.4 0

22、 0 0 0*1 06-.2 0 0 0 0*1 06Jx=(.0 0 0 0 0 *1 0 .5 0 0 0 0 *1 0)r误差大，原因：若有误差akj=akj+3,J3k=/3k+3则西=A=A-L A，则演变为2=%-4(%+m=玛+li k 3,A =以一 4 (乩+磔=自+/*；这说明前步各元素的误差均被放大4倍。克服方法，将按绝对值最大的元素交换到主元位置，使心|41,使前步的误差不再被放大。1 0 0 0 0*1()7 2 0 0 0 0*1 0 .1 0 0 0 0*1 0 3日1 k.2 0 0 0 0*1 0 .3 0 0 0 0*1 0 .2 0 0 0 0*l O j

23、-.2 0 0 0 0*1 0 .3 0 0 0 0*1 0 .2 0 0 0 0*1 0，期 小、.1 0 0 0 0*1 0 .2 0 0 0 0*1 0 .1 0 0 0 0*1 0 1 -2 0 0 0 0*1()1 .3 0 0 0 0*1 0 .2 0 0 0 0*1 0 1 .2 0 0 0 0*1 0 .1 0 0 0 0*1 0 1x=(.2 5 0 0 0 1 0 .5 0 0 0 0 *1 0 )消元过程中，第攵步消元(4=1,2,，-1)以第女行为基准，消去其后的-攵个方程的为(系数矩阵第列以下的元素)，G wss消去法要求主元%*#0。为避免出现%*=0 作为主元，并

24、使前步的误差不被放大，应使上设1,为此应使：akk=Ma x akk,ak+u,-ank,通常采用按列选主元的列主元消去法：若 /=林 词%/,|%+|31%/,便将第左 行与第加行交换,使“与心交换位置，使新的第人行执行在原始G a“ss消去法中的角色，保证将作为除数的主元|%/4 腐|i =Z +l,，从而，/4I,重复前述的G a“ss消去过程。列主元消去法的效果：1 .算法稳定，即计算误差能被有效控制;2 .当矩阵A的行列式网H0时，算法总可以执行完成；注：若矩阵A是对称正定或严格对角占优，则不选主元，消去法也是稳定的;矩阵严格对角占优的定义：对角元的绝对值大于该行其他元的绝对值之和,

25、即 同 同；7=1评问题：为什么系数矩阵A严格对角占优时，不选主元的消去法也是稳定的？为保证消去法是稳定的，计算应如何进行?注意：第一步消元,=a.-ai y,由于占优:即.i*(X2 j =j%2 1=四1K-I-K-I+K I劭-力 必 人 力 引+H必 忤六3 六3 六3 _|%1 =勿%|+|编6力%卜j=3“川j=3这回+曷|5佃2|+|%力 卜1%|六3|斯|；=3 j I|。12斯|52 2|52;|即新的第二行的对角元绝对占优,其他也可同样证明。例2-2：列主元消去法求解例2-12、一 122-31300、32,-1行“2行2122-3310302221-22行3彳 了2 2-

26、23%2，32=-%2-23 3%M同样得到原方程组的解x =（l -1 1）J2.2 矩阵分解2.2.1 Gauss消去法的矩阵意义矩阵的三角分解若将G a us s 消去法解方程过程中产生的（i/）作为一个单位下三角矩阵其对角元为1,对角线上的元素均为0 L的对应元素；将G a 依s 消去法消元过程最后得到的上三角矩阵对角线以下元素均为0-记作7或U （仅正是原始所求解的方程的系数矩阵。反过来，一个矩阵也可以通过G a us s 求解的考虑方程的系数矩阵部分）；如例2.1,再将L与 或 U相乘：1Y1 21 0)(1 2 10、L U=2 1-21 3 =2 2 3 3J X1八%为 1

27、一1 -3 0 2,/112 1(1 2、或 L U=2 12 1 =2 2J%17 显然d 7 相乘得到的正是原始所求解的方程的增广矩阵，而LU相乘得到的过程获得这样的“LU分解”，其中L 为单位下三角矩阵，。为上三角矩阵。这样将一个矩阵分解成一个下三角矩阵和一个上三角矩阵的乘积形式，称为矩阵的三角（Doolittle）分解。1）消去法的矩阵意义：以例2-1 说明1 2 10、2 1 0、-2 1 3I-1-3 0 2）一 1 1 2,与以下矩阵乘法是一样的:Y 1 2 1 0 1 (12 2 3 3 =_3 0 2)、2 1 0、-2 1 3T 1 4可见，一般的第一步消元是:=A:二夕a

28、 ll即a l la lla l:l二a l l小o:o=7AA:A%/%囚4囚11:1aaa若 记 第 左 步 消 元 后 形 成 的 矩 阵 为 特别：卬 4,勿=（心,即）则第i 步消元是将以下初等矩阵左乘矩阵（A f,a f）形成（A）,阴）(、1L,=1、Tk 1,因此，Gauss消去过程从矩阵运算的角度来看，是L_lLn_2-L2Ll(A,b)=(U,y)其 中U为上三角矩阵，y为向量：,411 4112 41r T 2 2 22.2.2 矩阵分解4=七(7注意到初等矩阵人具有性质：(、4=/,及 犯，因此，我们有(4,力=71”二,心力=心力根据矩阵乘积的性质，有 A=LU这就是

29、基本的矩阵三角分解一一D o o little分解一一将矩阵分解为单位下三角矩阵L 与上三角矩阵U 的乘积。从矩阵乘法与行列式的关系可知，若矩阵A 三角分解得到A=L U,则有：det A=det L*det U,由于下三角矩阵或上三角矩阵的行列式是全部对角元的乘积，因此可利用三角分解求矩阵对应的行列式的值。例如：上述例2.1方程组系数矩阵对应的行列式的值是-1,下例2.3对称正定矩阵对应的行列式的值为144o当系数矩阵为A 的方程组可以顺利求解(不必选主元)时，解的过程显然是唯一的，因此它的D oolittle分解必然也是唯一的，从而可以通过待定系数的方法获得该矩阵的Doolittle分解(

30、通常称为“直接分解”或“紧凑格式”)。2.2.3 其他三角分解除了上述的单位下三角矩阵与上三角矩阵的乘积形式以外，还有其他类型的分解，例如下三角矩阵和单位上三角矩阵的乘积，单位下三角矩阵与对角矩阵、单位上三角矩阵的乘积L D M 对于对称矩阵，可以分解成LOII矩阵分解的形式，特别是对称正定矩阵，可以分解成G G 形 式（称 为 Cholesk y分解），其中G为下三角矩阵 由 Doolittle分解的唯一性可知这些形式的分解也是唯一的。这些不同的分解都可以通过矩阵乘积的方法取得。下面例2.3以对称正定矩阵为例,说明通过矩阵乘积的方法取得矩阵分解的不同形式。当然，当矩阵的Doolittle分解

31、存在唯一时，这些不同的分解分别时唯一的,因此可以通过待定系数的方法取得，也即通过直接分解的方法取得这些分解。例 2-3：4-2 0-2 2-30-3 134 1 -7-2 0I-3-3 133-7-2 01 -342-2 0 4、1-3 34 29)由此可知:4-20-22-30-313、41-7-7 023 j 11-33A 1.%0 11 -3 31%9 J-3 31%1 )、(223人1f-x 01 -32 1V3%进一步可以考察矩阵左上方各阶顺序主子式与三角分解所得矩阵的左上方的各阶顺序主子式的关系：若记矩阵A的各阶顺序主子矩阵为4,A,，同样的记号也适用于矩阵L,U,则有4的=位7阳

32、，从而矩阵A的各阶顺序主子式的值等于U的相应的顺序主子式的值：d e t（A,*）=d e t Zw）仅=1,2,），（因为d e t（L“。）三1）。以例2-3矩阵分解为例，容易得到：4-2、(1、4-2、4=1*4,=1/24;卜 1/4/4-20 1,4-20、-2 2-3=11-3、0-3、-3 k4,由此，也很容易看到，一个对称矩阵通过G a u s s消去过程得到的LU分解（其中心为单位下三角，U为上三角矩阵），当U的对角元全部为正数时，该对称矩阵必为对称正定矩阵。由G a如s消去的过程可知各次主元是“2 2,（矩阵U的对角元），可知当矩阵A的各阶顺序主子式均非零时，（原始的）消去

33、法可以顺利完成,这是因为当各阶顺序主子式均非零时，4”,2 2,”“均非零，即G a u s s消去法可以顺利完成。因此得：定理2.1若阶方阵的各阶顺序主子行列式均非零,则存在唯一的LU分解,其中L为单位下三角矩阵，U为上三角矩阵。进一步，当矩阵A非奇时，列主元G a u s s消去法必可顺利完成：因为当矩阵A非奇时，4的第一列必不全为零，故通过选主元，可进行第一步消元，即算法乙 尸1 4可执行，得到产0,且其下方全为零，因为d e t（L/*）=d e t A w O,所以|的代数余子式d e t A：也非零，（/d e t A =det（LlP,A）-/jii d e t 0 ）,即矩阵

34、A：非奇，因 此 下 一 步 列 主 元 消 去 可 进 行，由此，可完成全部消元过程。2.2.4解三对角矩阵的追赶法X X XXJ上带宽 q :j i+q a(j=0X*下带宽p :i j+q a,j-0 xx x x.定理2.2若4=L。分解），则“下）带宽p ,U （上）带宽纭证明：对二和三阶矩阵显然.(确定p,q),对矩阵的阶作归纳证明:设对-1 阶矩阵结论成立.令A=a w=(v2 v+1 0 0),皿7=(卬2 1 W+i 0 0),B)可验证(介绍分块运算)：由归纳假设,3-工27=因此a最后的矩阵乘法：前者是初等矩阵左乘 实际上是G a u s s 变换矩阵相乘，后者按分块运算

35、容易得到。特殊情况,p =L 4 =1 三对角矩阵：，仇 c、a2 b2 c2T=,an-_I Cn_1 册)由前述的方法，很容易将它分解成两个特殊的下、上三角矩阵的乘积:其 中 因为未讲矩阵的直接分解，此处可由确定分解形式、待定系数方式取得：.二瓦,儿=九_ uk=bk-lkck-，女=2,3,，从而，在解方程组公=d,其中1=(4 4 2,弘)7 时，可以将该方程组转化为求解两个简单方程组：Tx=d oL y =d,Ux=y,通常被称为“追赶法”：X”|力=4 y k=dk-h yk-k=23,n，=(yk-ckyk+xy 女=，2,1,这只是G a u s s消去法的一个具体应用，在计算

36、机上的应用可以节约存储空间，减少运算量。若手工计算，实际只需应用G a u s s消去法即可。例 1 2 、1 、2 、2 3 12 1-1 1-3 4 2=3 11 24 7 14 1-1 1、12.3 线性方程组解的可靠性向量与矩阵范数，误差的代数表征3.1 向量与矩阵范数向量范数由二维或三维向量的长度概念推广而来一一工具。1、向量范数 向 量 =(为,2 X )7 eR”,与之相应的一个非负实数,记作H，如果它满足条件：1)非负性 H 0,H=0 ox=0,V x e Rn,2)正齐性|a r|=|,/a e R,x e Rn,3)三角不等式|x+y|x|+|y|,V x,y e R ；

37、常用的范数L范数 网=周+同+k”|，12-范数|%|2=(卜1/+同+“，)2 ,-范 数I k L =max胤卜2卜-，|芍|)，注：一般若不指某特定的范数，则范数符号不作下标，记为|卜|；2、矩阵范数 矩阵 A e L(R g ),与之相应的一个非负实数，记作风,如果它满足条件：1)非 负 性 同 2 0,M|=0OA=0,VAWZXRE),2)正齐性 1 M|=同网，V a e/?,V A e L(7?m x n),3)三角不等式 M+M4M|+|同，4)阿，V A e R M ),因为矩阵与向量相乘仍是向量，因此：特别要求一种矩阵范数与一种向量范数:5)|囹区同同，VAGZ X DX

38、GR矩阵与范数的相容性;与前述三种向量范数分别相容的常用的三种矩阵范数：1-范 数|可1=maxZkJ，(最大列和)j Z=1 12-范 数IK=(A的最大特征值，-范数%=max灯 ，(最大行和)；7=1注：作为矩阵的特例一一向量，这些范数定义无矛盾。例：试证明：(a)若忖是范数，M是一个非奇异矩阵，则由定义了向量xeR的一种范数；(b)对于矩阵AGR,Ml 定义了与向量范数牌”相容的矩阵范数。证明：a.由于蝌是范数，它必满足范数的三条件；由于所以(1)非负性：同“=忸 制2，且I H L =|Ar|=O 当且仅当M x =O,又由M 的非奇性，当且仅当x=0时才有Mr=O,因此：|x|L

39、=0 当且仅当x=0；正齐性：同“=|M(|=|a(M r)卜 闻 网=闷|乩三角不等式：上+W”=|M(x+y =l 依+叫 上 WM+I 的1 HMM+帆”因此，按此定义的范数国乱是范数；b.仿前，容易证明M L=|M 4 MT|定义了一种矩阵范数。关于相容性：加 IM=11 11=网=M l”|乩3、范数的等价性：11104M 4卜1 3 9 M 4M 4 M,|卷 引 乩 山 乩，4、矩阵谱半径：Q(A)=m a x 同，4为A全体的特征值i =1,2,，卜有(对任何一种范数)p(A)|A|,Ax=Ax,x*0 n|2|x|Z r|=|A r|/l|A|p(A)|/|=|A x|7 7

40、 7|1 ),而从推导可知，M I|A|A-1|M(此处“表示相当于”),因此一般总有酱 9；上例中：/T=1 j 。1 -2.000 网 -|=3X3.001/0.003=30010.003 -0.4 9 9 1.000 J”副 b对于更一般的矩阵A和右端向量均发生扰动/和4 6的情况，有IH I c。0A)H MH u趣丽时证明：H|x|-|B x|x|-|B|x|=(l-|B|)|x|0矛盾，所 以(1-B)非奇，(1-B)-1存在，由=1 (至少对常用的三种范数):1=|/|=|(Z-B)(l-可卜|(7-3尸 一 (/一 5尸耳N ll(Z-初I T。-3尸Ml=|(Z-|B|)由

41、此 得 卜 一 可 卜 昂-若：（A +Ax）=（+Ab）：Ax=b,（A+AA）Ax=Ab-AA xAx=（4+AA-x）（A +/N）=A（/+|Jx|（/+A AA/AT1（4 b-A A-x-ai MxM-%,乙+四)从而原方程组可改写成如下等价形式:-1=(一。2 九2 .+A)即尤2=-(_%1 玉 -a2 3x3-._%光“+色)。22Xn -(一 a,i X an2X2 .ann-lXn-+A)(2.4)J a c o b i 迭代：将/=(淄,/，,了代入上式右端,便可(按顺序逐行)进行计算得到/+1=(姬+1,芯+1-、/+1)7,这便是J a c o 次迭代：X 1=(%

42、2 芯一.(X ”X心+/7|)a X2+1=(-a2 X a2 3X3 .-a2 nXn+A)n e xj a2 2,(2.)琛i =L(_a”iX：-an2X 2 -.-ann_xx _+&)Ga u s s-S e i d e l 迭代：按通常的串行计算方式，迭 代(2.5)中先计算第一式得到耳，此数完全可以参与第二式的右端的计算，依次类推，便得到：=(-C C 2X2-a nXn+A)只=_%3石-%4+,2)/A.a2 2(2。Xn+，=(anlXl+_an2X2+-ann-lXn-l +&)%这就是G a u ss Seidel迭代。2.4.2迭代法的矩阵表示将方程组(2.1)的系

43、数矩阵A分裂成三部分：A =D-E-F,其中D=a2 2o0、04 2,%”、-E =a2 0,-F =0%.a%2 1 ;100)原始方程组Ax=b%内+al2x2+-+a1;,xa2内+a22x2+%x“=四矩阵分裂：A=D-E-F。出玉+%2%2+%=凡U形成x=Gx+d,即左侧仅有x%内=-al2x2-._%也+四a22x2=-a2lXt-a23x3-.-z2;,x+/?2,a“X=!%,an2x2-.+/3若%i的2HO,分别对第i 方程除以,并记左侧上标为k+1,右侧上标为k,则有Jacobi 迭代：X i”=(-1 2X2 .anxn+2 1)1 1x2+l=(-2 lxf-a2

44、 3x3-a2 nxn+6 2)a2 2xn =-(-anx an2x2-ann-xn-+瓦)若 由“最 新 信 息 优 先”，即将已生成的X 产/=1,2,i 立 即 用 于 计 算 端 1 ,便是Gauss-Seidel 迭代：x f M =-(-1 2X2-a nxn+Z？l)a 1=-(-a 2 1 H M -2 3%3 -.-a2x+夕2)a2 2xn+1 =(anx+an2x2+l-ann-lxn-i+)Jacobi 迭代：I)x=Ex+Fx+hux=D(E+F)x+Dbu xk+=D-(E +F)xk+D-bGauss-Seidel 迭代：(D-E)x-Fx+bux(D-E)F

45、x+(D-E ybuxk+=(D-后广Fxk+(D-旧广b0(C/+1 -Z Y *tZ|jX|cZ 2.V2.-anxn+Pna Y4+1-ZY K+l z y J22x2 a2x a23x3 一a2nXn+P lx*+i=D-E YxFxk+(D-E yb .nC Y +l _ c/+1 k+annxn anx an2x2 ann-xn +PnDxk+i-E xk+i Fxk+bftDxk+=Exi+Fxk+b显然，不同的迭代方法是对矩阵A做不同的分裂得到的：J a c o b i 迭代：A D-E +F=Ax=b D x-E +F x b=Dx=E+Fx+b=x=D E+Fx+D bG

46、a u ss-S e id e l 迭代：A=D-E -F =Ax=b=D-E x-F x =bn D-E x=Fx+b x=D-E Fx+D-E-b2.4.3 收敛性以下我们回答问题I I）和 H I）：记方程组的解为x*,若当左一 8 时向量序列 卜 收敛于方程的解X*,即有等价关系（注意到范数的等价性）：A:-KOk*乙*八 I*八 k*C k*11 zxx f x ox -x f Oom a*一匹-Oo x-x f Oo x-x 1 f 0由于X*满足关系式x*=G x*+d,将它与一般迭代（2 4）：xk+lG xk+d,两者相减，可得 x*=G3%*）,遍取向量范数，并由矩阵范数与

47、向量范数的相容性，可得：从而，仁一小|G|忖一臼加 产一斗|恂 产 卜。一 寸由此可见，当|3 0,即：P-x*；即定理2.3：迭代？=G?+”取任意初值x 0 生成的向量序列卜 当我 f8时收敛于方程的解的充分条件是悯|1.具体化-考察对原始问题（2.1）进行Jacobi迭代或Gauss-Seidel迭代时,迭代收敛对矩阵A的要求。由式（2.4 ）（2 5）可知，J ac o 次迭代的迭代矩阵为。T（+R）,Gauss-Seidel迭代的迭代矩阵为（O-E）TR；由于。T（+R）的第i行是：（强.0?四.幺L）；因aii aii aii aii此，显而易见当4为严格对角占优时该行各元素的绝对

48、值之和小于1,所以：|O-1（E+f）,1;结论是：推 论2.4：若方程组（2.1）的系数矩阵A严格对角占优，则任取初值的Jac o的迭代收敛.其他结论:定 理2.5：若方程组（2.1）的系数矩阵A严格对角占优，则任取初值的G a u ss Seidel 迭代收敛.证:记/,=6自%|,%=占 力%|必眉，=1 必眉i=i+严格对角占优n=3 1，由i的有限性,由 xA+,=D Exk+D Fxk+D-b 及 x*=D Ex+D-Fx*+D-b相减 eM=D E ek+D-Fek即=J (一%)e +J (-)4Ui i J=1 j=i+l设 K =m,a B+*|则ai O i O J=1|

49、%0 2|J=/O+Ii 0 i 0 尸 Ir0/0|尸0+1所以 ri MLHL=M L0M叫由 O W x*-x，证完定 理2.6：若方程组（2.1）的系数矩阵A对称正定，则i）任取初值的G皿S3-S e i迭代收敛；，）当2 O-A正定时，Jac o沅迭代收敛，否则就不收敛。最后，有：定理2.8：迭代（2 3）收敛的充分必要条件是矩阵G的谱半径p（G）2、-10,)22-1=det(/lZ J)=-12-1-212=p(J)=0i2212A=1227解2122Z2又，det(ZZ-GS)=d e -(D-F=det(D-E)-,fA(一 E)尸“=0 等价于解:det/l(Z)-E)-F

50、=2 22222-21 ,3-4A2+4=A(2-2)2I2 n p(GS)=2；22结论:Jacobi迭代收敛，Gauss-Seidel迭代不收敛。ii)J=/0-1-107=det(A7-J)=21A-%-%12A3+-A =/?(7)=4 222-1det2(Z)-E)-F=22 22-2 -A1222=823+822+22=22(22+1)2 n p(GS)=%结论:Jacobi迭代不收敛，Gauss-Seidel迭代收敛。例：A=2 3 4、3 6 10 正定，2B-A 不正定，Seidel收敛，Jacobi不收敛。、4 10 20,4例：A =-322 3、5 1 n2 3MH，6