理学数值分析学习教案

1、会计学1理学理学(lxu)数值分析数值分析第一页，共119页。克莱姆（克莱姆（CramerCramer）法：）法： 一种一种(y zhn)(y zhn)解线性代数方程解线性代数方程组的直接法组的直接法11112211211222221122 nnnnnnnnnnna x a xa xba x a xa xba x a xa xb阶线性方程组： , X ,11Tn nijAXbTA nn , , ) , , )(x(bxbab矩阵表示记为这里第1页/共119页第二页，共119页。 det( )0det() (1,2, )det( )iiAAxinA根据克莱姆(cramer)法则，若方程组系数行列

2、式不为零，即，则该方程组有唯一解。其解为1 (1)!nnnnnn这种方法需要计算行列式并作，而每个阶个 阶次除行列式计算需作法次乘法。3530,2.38 10nn如需次乘法。理论较大时，实上是绝对正确际计算，但不可行。计算量十分惊人!在实际在实际(shj)中如何利用计算机这一强有力工具求解线性方程中如何利用计算机这一强有力工具求解线性方程？第2页/共119页第三页，共119页。3.1 消元法消元法 计算机解线性方程组的一种计算机解线性方程组的一种(y zhn)直接法直接法思路：思路：1 1）先将）先将A A化为上三角化为上三角(snjio)(snjio)阵阵 ( (消消元元) ) 2 2）再回

3、代求解）再回代求解 。 ( (回代回代) )=高斯消元法高斯消元法第3页/共119页第四页，共119页。消元消元记记,)()1()1(nnijaAA )1()1(1)1(.nbbbbStep 1：设设 ，计算因子，计算因子0)1(11 a)., 2(/)1(11)1(11niaamii 将增广矩阵将增广矩阵，得到，得到)1(1)1(1)1(12)1(11.baaan)2(A) 2(b).,2,()1(11)1()2()1(11)1()2(njibmbbamaaiiijiijij 其中其中Step k：设设 ，计算因子，计算因子且计算且计算0)( kkka)., 1(/)()(nkiaamkkk

4、kikik )., 1,()()()1()()()1(nkjibmbbamaakkikkikikkjikkijkij 共进行共进行(jnxng) (jnxng) ？ 步步n 1 )()2(2)1(121)()2(2)2(22)1(1)1(12)1(11.nnnnnnnnbbbxxxaaaaaa第4页/共119页第五页，共119页。回代回代 )()(/nnnnnnabx 0)( nnna 如果如果 ?没有没有(mi yu)唯唯一解一解.) 1., 1()(1)()( niaxabxiiinijjiijiii0)( iiia 如果如果 ?定理定理(dngl) 若若A的所有顺序主子式的所有顺序主子式

5、 均不为均不为0，则高斯消元无需，则高斯消元无需换行即可进行到底换行即可进行到底(do d)，得到唯一解。，得到唯一解。iiiiiaaaaA.)det(1111 事实上，只要事实上，只要 A 非奇异，即非奇异，即 A 1 存在，则可通过逐次存在，则可通过逐次消元及行交换，将方程组化为三角形方程组，求出唯消元及行交换，将方程组化为三角形方程组，求出唯一解。一解。第5页/共119页第六页，共119页。问题(wnt)?第6页/共119页第七页，共119页。例：例：单精度解方程组单精度解方程组 211021219xxxx 精确解为精确解为 和和 .1000.00. 1101191 x8个个.8999.

6、99. 0212 xx8个个用单精度用单精度(8位位)高斯消元法计算高斯消元法计算(j sun)：911212110/ aam999212210101010.0 . 011 ma8个个92121012 mb 9991010011100, 112 xx原因：小主元原因：小主元 导致计导致计算算(j sun)失败。失败。（大数（大数(d sh)吃吃小数）小数）（大数吃小数）（大数吃小数）（结果差异很大（结果差异很大）第7页/共119页第八页，共119页。全主元消去法全主元消去法每一步选绝对值最大的元素为主元素每一步选绝对值最大的元素为主元素，保证，保证 。1| ikmStep k: 选选取取|ma

7、x |0 ;kkijijkinkjnaa If ik k then 交换交换(jiohun)第第 k 行与第行与第 ik 行行; If jk k then 交换交换(jiohun)第第 k 列与第列与第 jk 列列; 消元消元列主元消去法列主元消去法省去换列的步骤省去换列的步骤(bzhu)，每次仅选一列中最大的元。，每次仅选一列中最大的元。0|max|, iknikkiaak 在在第第k kn n行，行，第第k kn n列选列选择择kki ja第8页/共119页第九页，共119页。在第一行在第一行是个小数是个小数(xiosh)，仍是小，仍是小主元主元 导致导致计算失败计算失败例：例： 2111

8、11091,112 xx 110211 11102119 0,112 xx例例： 2111010199 99991010010101注意：这两个方程组注意：这两个方程组在数学上在数学上严格等价严格等价。 取取a21为主元，为主元，避免避免(bmin)大大吃小吃小第9页/共119页第十页，共119页。(GaussLU由由消消元元法法加加上上列列主主元元 或或全全主主元元）法法有有分分解解： 矩阵矩阵(j zhn)(j zhn)三角分解法三角分解法11121n21222n313212(1)nn111 U 1nnn nALULuuuluulllllu L单位单位(dnwi)下三角下三角矩阵矩阵U上三

9、角矩阵上三角矩阵第10页/共119页第十一页，共119页。11121314111213142121222324222344313231323334333441424341424344441000100010001000aaaauuuulaaaauuullaaaauulllaaaau1112131421112112222113232114243111311232223113322333311432243441114112422241134223433341144224433444uuuul ul uul uul uul ul ul ul ul uul ul uul ul ul ul ul ul

10、ul ul ul uu直接直接(zhji)(zhji)计算计算 A A 的的 LU LU 分分解：解：第11页/共119页第十二页，共119页。1212111313111414111i1111 , , ; , i2,nilla ula ula ula u列111111212131314141j1 , , , ; , j1, ,n juuauauauaua行直接直接(zhji)(zhji)比对等式两端矩比对等式两端矩阵元素阵元素2222211223232113242421142j221132323112224242411222i22u2 - , - , - ; - , j2, ,n 2 (-)

11、, (-) ; (-jjilua l uua l uua l uua l ula l uula l uula行列i21222) i3, , n.l uu第12页/共119页第十三页，共119页。i111111 , i2, , j1, ,n , njjiuala uk-1ikk-1kjkmkmimkm 11 jk , 2, 3, , ( )/ ik1, , , n n ikmkkjmjknuallal uuu对计算一般一般(ybn)计算公式：计算公式：第13页/共119页第十四页，共119页。LULU分解系数的计算分解系数的计算(j (j sun)sun)顺序顺序2131413242433331

12、11213222344211323211121314212211121122223243132333441424314111213141442144441000100010001000aaaauuul uuaaauul uullaallluaaaaaaauuuuuluuuulul311232224112422231133223333114322434311141114114422443344441134223433432l ul ul ul ul ul uul ul uul ull ul uul ulll uuuuu按颜色顺序依次计算按颜色顺序依次计算给定矩阵给定矩阵A A，如何计算，如何计算

13、(j sun)(j sun)其对应的其对应的L L矩阵和矩阵和U U矩阵？矩阵？第14页/共119页第十五页，共119页。Matlab的符号计算 思考题：习题(xt)2，写出4阶三对角矩阵的LU分解公式第15页/共119页第十六页，共119页。112221313212(1)1111121n22222nnn111 1 UXnnnnn nnnybybLYbybxyxyYxylllllluuuuuu 利用利用(lyng)LU(lyng)LU分解求解线性方分解求解线性方程组程组Y L b , UXY AXbLbUX即: 思路思路(sl)：第16页/共119页第十七页，共119页。11-11 , 2,

14、3, , (1) Y iiijijjinybyybl求解：1ijii , in 1, , 1 (2) x nnnniijij nyxuyxu xu求解：两步算法两步算法(sun (sun f)f)：第17页/共119页第十八页，共119页。12312314 2521831520 xxx 100123 2100143510024ALU 计解解：用用分分解解算算公公式式得得例：用三角分解例：用三角分解(fnji)(fnji)法求解线性方程法求解线性方程 (14,18,20)(14, 10, 72) ,(14, 10, 72)(1,2,3) .TTTTLyyUxx求解第18页/共119页第十九页，共

15、119页。PALU0321ALULU分解：分解：111203uu212111?aluMatlab中中LU分解函数分解函数(hnsh)“lu()”。 调用方式：调用方式：“L,U,P = lu(A)” 思考：利用思考：利用 MATLAB中的帮助文件中的帮助文件“ help lu” ， 查看查看lu函数的帮助文档，说明函数的帮助文档，说明(shumng)其中其中L, U, P 各是各是 什么矩阵。什么矩阵。 L, U, P, A如何构成等式。如何构成等式。置换矩阵置换矩阵n更一般形式：更一般形式：第19页/共119页第二十页，共119页。由线性代数由线性代数(xin xn di sh)(xin x

16、n di sh)知，对称正定阵的几知，对称正定阵的几个重要性质：个重要性质： A1 亦对称亦对称(duchn)正定正定，且，且 aii 0 A 的顺序的顺序(shnx)主子阵主子阵 Ak 亦对称亦对称正定正定 A 的特征值的特征值 i 0 A 的的全部顺序主子式全部顺序主子式 det ( Ak ) 0 3.2 3.2 Cholesky Cholesky 分解分解（平方根法）（平方根法）： 的分解法的分解法一个矩阵一个矩阵 A = ( aij )n n ，如果，如果 aij = aji称为称为对称阵对称阵。即。即A=AT定义：定义：一个矩阵一个矩阵 A 称为称为正定阵正定阵，如果，如果 对任意非

17、零对任意非零向量向量 都成立。都成立。 0 xAxTx定义：定义：第20页/共119页第二十一页，共119页。u 若若A A为为n n阶满秩方阵，则有阶满秩方阵，则有ATAATA为对称为对称(duchn)(duchn)正定正定矩阵矩阵() ()0TTTx A AxAxAx 又又 ATA ATA为对称为对称(duchn)(duchn)矩阵矩阵0TTx A Ax 由于由于(yuy)A满秩，即方程满秩，即方程 A x = 0 只有只有0解，所以任意非零向量解，所以任意非零向量有：有：根据正定矩阵定义，根据正定矩阵定义，则有则有A AT TA A为对称正定矩阵为对称正定矩阵对称正定矩阵对称正定矩阵Ch

18、oleskyCholesky分解：分解：证明：证明： 第21页/共119页第二十二页，共119页。先将对称先将对称(duchn) (duchn) 正定阵正定阵 A A 做做 LU LU 分解：分解：U =uij=u11uij / uii111u22unn记为记为DU A 对称对称TUL 即即1122()TTALDLDLDL记记 D1/2 =11u22unnuWhy is uii 0?Since det(Ak) 02/1LDL 则则 仍是下三角阵仍是下三角阵TLLA n nLR定理定理 设矩阵设矩阵A对称正定，则存在唯一下三角阵对称正定，则存在唯一下三角阵 ，其，其对角元素为正，使得对角元素为正

19、，使得 ，A的这种分解称为的这种分解称为Cholesky 分解分解。TALL 对于对称正定阵对于对称正定阵 A ，从，从 可知对任意可知对任意k i 有有 。即即 L 的元素不会增大，的元素不会增大，误差可控误差可控，。 ikikiila12iiikal |称为称为(chn wi)Cholesky 分解分解单位单位(dnwi)上三角阵上三角阵第22页/共119页第二十三页，共119页。 LULU分解和分解和CholeskyCholesky矩阵矩阵(j zhn)(j zhn)分解的关系：分解的关系：l已知已知LU分解求分解求cholesky分分解解： 其中其中 D1/2 =11u22unnu2/

20、1LDL L如何计算如何计算D D？U U矩阵的矩阵的对角线元素，或对角线元素，或 的对角线元素平方的对角线元素平方。12LLD1/21/21/2()( )TTTUDLDLDDLl已知已知cholesky分解分解，求求LU分解分解：:TTAAxbA AxA b如如果果秩秩，有有 满则 第23页/共119页第二十四页，共119页。例例对矩阵对矩阵 A = 进行进行Cholesky分解。分解。410141014程序程序A=4,1,0;1,4,1;0,1,4;P=chol(A)P = 2.0000 0.5000 0 0 1.9365 0.5164 0 0 1.9322结果结果是是( )TL第24页/

21、共119页第二十五页，共119页。n 为了研究线性方程组近似为了研究线性方程组近似(jn s)(jn s)解的误差估计和迭代法的收敛性，引进解的误差估计和迭代法的收敛性，引进向量（矩阵）的范数的概念。向量（矩阵）的范数的概念。衡量衡量(hng ling)向向量或矩阵量或矩阵 “大小大小”的概念的概念概念是概念是长度和距离概念长度和距离概念的推广的推广第25页/共119页第二十六页，共119页。 向量向量(xingling)范数（范数（Vector norm）Rn空间的空间的向量范数向量范数 | | 对任意对任意 满足下列条件满足下列条件：nRyx ,00|;0|) 1 ( xxx（正定性（正定

22、性(dng xng)|) 2(xx C 对任意对任意(rny)(齐次性齐次性) |) 3(yxyx （三角不等式三角不等式)常用向量范数常用向量范数：11niixx（ 1 范 数 ）1/ 22212niixx（ 范数或欧氏范数）1/1ppnpipixx（ 范数）m axiixx（范 数 ）n定义：定义：第26页/共119页第二十七页，共119页。000011,0;00niixxxx1xx0 xaaxxx yxy不满足性质不满足性质 2 2aaxx不满足性质不满足性质 1 10 xx0n例：判断例：判断(pndun)下面定义式是否是向量范下面定义式是否是向量范数数（1）（2）第27页/共119页

23、第二十八页，共119页。12xx12xx向量不能比大小向量不能比大小向量通过定义范向量通过定义范数比大小数比大小 最重要的用途最重要的用途(yngt)之一：分析向量收敛性，定义向量之一：分析向量收敛性，定义向量的极限：的极限：向量序列向量序列 于向量于向量 ,是指对每一个是指对每一个 1 i n 都有都有 。)(kx*x*)(limikikxx 可以理解为可以理解为0|*|)( xxk可理解为对任何向可理解为对任何向量量(xingling)范数范数都成立。都成立。定义：定义：第28页/共119页第二十九页，共119页。收敛收敛(shulin)意义意义上的等价，即在不上的等价，即在不同范数下的收

24、敛同范数下的收敛(shulin)性是一致性是一致的的定理定理Rn 上一切范数都等价。上一切范数都等价。1212,0 nststsxxRc cc xxcx：设和是上的任意两种向量范数，则存在常数，使得 向量范数的等价向量范数的等价(dngji)性定理（性定理（79页定理页定理3A.1）：）：利用向量范数的等价性定理，很容易得到下列推论：利用向量范数的等价性定理，很容易得到下列推论：推论：向量序列推论：向量序列(xli)在某范数下收敛，则在任意范数下收敛。在某范数下收敛，则在任意范数下收敛。第29页/共119页第三十页，共119页。 矩阵矩阵(j zhn)(j zhn)范数（范数（Matrix n

25、ormMatrix norm）Rm n空间的空间的矩阵范数矩阵范数 | | 对任意对任意 满足：满足：nmRBA ,00|;0|) 1 ( AAA（正定性（正定性(dng xng)|) 2(AA C 对任意对任意(rny)(齐次性齐次性) |) 3(BABA （三角不等式三角不等式)(4) | AB | | A | | B | （相容相容 ( (当当 m = n 时时)定义：定义：意味多个矩阵（向量）运算意味多个矩阵（向量）运算时，误差是可控的时，误差是可控的第30页/共119页第三十一页，共119页。Frobenius 范数与范数与向量向量(xingling)2范数相容范数相容矩阵矩阵(j

26、zhn) ATA 的最大的最大特征根特征根常用常用(chn yn)矩阵范数：矩阵范数：1. Frobenius 范数范数 ninjijFaA112| 向量向量| |2的直接推广的直接推广 对方阵对方阵 以及以及 有有nnRA nRx 22|xAxAF 2. 算子算子范数范数 由向量范数由向量范数 | |p 导出的关于矩阵导出的关于矩阵 A Rn n 的的 p 范数范数:pxpppxAxxAApx|max|max|10| 则则ppppppxAxABAAB| 常用算子常用算子范数有范数有： njijaAni1|max|1（行和范数行和范数） niijaAnj11|max|1（列和范数列和范数）)(

27、|max2AAAT （谱范数谱范数 ）称为称为算子范数（算子范数（诱导范数）诱导范数）满足相容性满足相容性向量范数向量范数第31页/共119页第三十二页，共119页。我们我们(w men)只关心有相容性的范数，算子范数总是只关心有相容性的范数，算子范数总是相容的。相容的。即使即使(jsh) A中元素全为实数，其特征根和相应特征向量中元素全为实数，其特征根和相应特征向量 仍可能是复数。将上述定义中绝对值换成复数模均成立。仍可能是复数。将上述定义中绝对值换成复数模均成立。否则，必存在某个向量范数否则，必存在某个向量范数| |v 使得使得 对任意对任意A 成立。成立。vvFxxAAx|max|0 注

28、：注：Freebies范数不是范数不是(b shi)算子范数算子范数021|1max1|xnvFivI xInx设设AI（单位阵），（单位阵），其其| |F为：为：| |F不是算不是算子范数子范数第32页/共119页第三十三页，共119页。例：已知矩阵例：已知矩阵(j zhn)A(j zhn)A，求算子，求算子1 1范数和算子范数和算子范范数。数。1max2161236 654 15789 1415 2416 ()16.712497TAAAAA A所以，行和范数为 ，列和范数为和列 和行第33页/共119页第三十四页，共119页。 任意离散有限线性算子任意离散有限线性算子(sun z)可表示为

29、矩阵形式可表示为矩阵形式。可表示为可表示为矩阵形式矩阵形式000000( )( )00.0000aay nax nxya1)1)尺度算尺度算子：子：LTI：线性时不变系统：线性时不变系统(xtng)n为什么叫做为什么叫做“算子范数算子范数”？线性时不变算子线性时不变算子的矩阵表示的矩阵表示第34页/共119页第三十五页，共119页。11000(1)(2)(1)01 .00(2)(3)(2)( )(1)( )00.10.00011(1)( )(1)00001( )0( )xxxxxxy nx nx nx nx nx nx nx n2)2)差分差分(ch (ch fn)fn)算子算子1111(1)

30、10000(1)(1)(2)11.00(2).( )( )11.00.( )11110(1)11111( )( )nniinixxxxxy nx ix ix nx nx i3)3)累加算子累加算子(sun z)(sun z)不考虑边界不考虑边界问题问题第35页/共119页第三十六页，共119页。00000(1)010.00(2)(1)( )(1)01.00.00.00(1)(2)00010( )(1)xxxy nx nx nx nx nx n 4)4)时移算子时移算子(sun z)(sun z)用用D表示表示线性微分方程012012(1)(2)(1)(2)012012(1)(2) ( )(1)

31、(2)( )(1)(2) a x na x na x nb y nb y nb y na Ia Da Dxb Ib Db DyDD可记为：其中，为一阶，二阶时移算子线性时不变算子线性时不变算子(sun z)的矩阵表示的矩阵表示第36页/共119页第三十七页，共119页。0 0010 20 (1)1011121(1)(1) 0(1)1(122222222210222) 2(1) (1)2.( )( ).jjjjNNNNjjjjNNNNNjkiNijjNNjjNNNNNNNNNeeeeeeeey kex ieeee (0)(0)(1)(1) .(1)(2)(1)(1)xyxyx Ny Nx Ny

32、N5)5)傅立叶变换傅立叶变换(binhun)(binhun)线性时变线性时变(sh bin)算子的矩阵表示算子的矩阵表示第37页/共119页第三十八页，共119页。谱半径谱半径 （讨论特征（讨论特征(tzhng)(tzhng)根与根与范数的关系范数的关系 ）矩阵矩阵A的的谱半径谱半径记为记为 (A) = ，其中，其中 i 为为 A 的特征根。的特征根。|max1ini ReIm (A)定义定义(dngy)：特征特征(tzhng)根根中最大的模中最大的模为谱半径为谱半径n矩阵范数的性质矩阵范数的性质第38页/共119页第三十九页，共119页。所以所以(suy)2-范数范数亦称为谱范数。亦称为谱

33、范数。定理定理对任意算子范数对任意算子范数 | | 有有|)(AA 证明证明(zhngmng)：由算子范数的相容性，得到由算子范数的相容性，得到|xAxA 将任意一个特征根将任意一个特征根 所对应的特征向量所对应的特征向量 代入代入u| |AuAuA |uu 定理定理若若A对称矩阵，则有对称矩阵，则有)(|2AA 证明证明(zhngmng)：)()(|2maxmax2AAAAT A对称对称若若 是是 A 的一个特征根，则的一个特征根，则 2 必是必是 A2 的特征根。的特征根。因因 任意性，则有任意性，则有1( )max | |i niAA 若若 （最大特征根），（最大特征根），则则 02 必

34、是必是 A2 的最的最大特征根。大特征根。0( ) |A222max00|()( )AAA计算计算2-范数的范数的一种方法一种方法第39页/共119页第四十页，共119页。后面分析病态后面分析病态(bngti)问题问题时要用时要用非奇异非奇异(qy)阵阵若矩阵若矩阵(j zhn) B 对某个算子范数满足对某个算子范数满足 |B| 1，则必，则必有有定理定理BI 可逆；可逆； |111BBI 证明：证明： 若不然，则若不然，则 有非零解，即存在非零有非零解，即存在非零向量向量 使得使得 0)( xBI0 x00 xxB 1|00 xxB1| B 1()()IIB IB11()()IBB IB11

35、)()( BIBIBI|)(|1|)(|11 BIBBI根据算子范根据算子范数定义数定义：0| max|xBxBx 0|max1|xBxx111|()|(1 |)11 |IBBIBB第40页/共119页第四十一页，共119页。A 4321例例 ，X=-3 5T，分别，分别(fnbi)求求A、X的的“1-范数范数”和和“无穷大范数无穷大范数”613 , 24max1A712 , 34maxA8|5|3|1X5|5|,3max|XMatlab:A=4,-3;2,1X=-3 5norm(A,1), norm(A,inf)norm(X,1), norm(X,inf)第41页/共119页第四十二页，共1

36、19页。3.4 解线性方程组的迭代法解线性方程组的迭代法 迭代法（迭代法（iterative method iterative method ）迭代法是从初始猜测值开始，通过依次逼近迭代法是从初始猜测值开始，通过依次逼近(bjn)获得问题解的获得问题解的方法。方法。(Iterative method: attempts to solve a problem by finding successive approximations to the solution starting from an initial guess；（；（comes from wikipedia） )n应用很广：应用很广

37、：n线性方程组求解、非线性方程求解、非线性方程组求解、特征线性方程组求解、非线性方程求解、非线性方程组求解、特征值求解、最优化方法、分形等，以及数字信号处理中的维纳滤值求解、最优化方法、分形等，以及数字信号处理中的维纳滤波、卡尔曼滤波等等波、卡尔曼滤波等等(dn dn)都要用到迭代法都要用到迭代法n典型方法：典型方法：n数值计算：数值计算：Jacobi法、法、Gauss-Seidel法、法、Newton迭代法、最快迭代法、最快下降法（下降法（Steepest Descent）第42页/共119页第四十三页，共119页。迭代法解一般迭代法解一般(ybn)(非线性非线性)方程方程迭代迭代(di d

38、i)序列的基本公式：序列的基本公式：(1)( )0(),kkxxxa (x)为：任意为：任意n维空间到维空间到n维空间的函数。维空间的函数。 当当 (x)为线性函数时，上式即为线性方程为线性函数时，上式即为线性方程(xin xn fn chn)(组组) 的迭代公式。的迭代公式。如何利用迭代法解方程？如何利用迭代法解方程？迭代法基本原理：迭代法基本原理：如果迭代序列如果迭代序列x（k+1）= (x（k） ) 收敛，收敛，则其极限点则其极限点x*为方程为方程 (x)= x 的解。的解。x*称为函数称为函数 (x)的的不动点（不动点（fixed point）第43页/共119页第四十四页，共119页

39、。迭代函数的构造：对于一般迭代函数的构造：对于一般(ybn)(ybn)的非线性方程的非线性方程f(x)=0f(x)=0例例1 1：用迭代法求解：用迭代法求解(qi ji)(qi ji)方程方程 2 x = 1 2 x = 1构造迭代构造迭代(di di)(di di)函数：函数：11 102112(1 1.5 )312xxxxxxxxx (1)( )1(1)( )2(1)( )3(1)( )4( )11( )(1)/3(1)/3( )2(1 1.5 )2(1 1.5)( )(1 10 )/12(1 10)/12kkkkkkkkxxxxxxxxxxxxxxxx ( )0( )f xf xxx(

40、)0( )a f xa f xxx或或即迭代函数为即迭代函数为 (x)= f(x)+x 或或 (x)= af(x)+x 迭代函数迭代函数:第44页/共119页第四十五页，共119页。迭代函数迭代函数(hnsh)的构造的构造迭代法的步骤迭代法的步骤(bzhu)：1、写出迭代方程、写出迭代方程2、迭代、迭代clear allclose allclcformat long% 迭代迭代(di di)法求解法求解2x=1x0 = 0 % 迭代迭代(di di)初值初值N = 30 % 迭代迭代(di di)次数次数% 方法方法1：f(x) = 1 - xx1(1) = x0;for iii = 2 :

41、N x1(iii) = 1 - x1(iii - 1);endfigure;plot(x1, o-)title(f(x) = 1 - x)第45页/共119页第四十六页，共119页。振荡振荡(zhndng)序列序列收敛收敛(shulin)序列序列发散发散(fsn)序序列列收敛序列收敛序列迭代法的核心问题：迭代法的核心问题：迭代函数收不收敛迭代函数收不收敛收敛速度快不快收敛速度快不快第46页/共119页第四十七页，共119页。 借助于计算机，用迭代法对分形借助于计算机，用迭代法对分形(fn xn)(fn xn)的研究更的研究更加简单化加简单化例例2 2：迭代法用于分形：迭代法用于分形(fn xn

42、)(fractal)(fn xn)(fractal)研究研究 分形分形(fn xn)是一种粗糙的或分裂的几何形状，其每一部分都是是一种粗糙的或分裂的几何形状，其每一部分都是整体的缩小比例的复制（自相似性）整体的缩小比例的复制（自相似性） 分形分形(fn xn)是具有自相似性的几何形状。是具有自相似性的几何形状。分形（分形（FractalFractal）理论，是现代数学的一）理论，是现代数学的一个新分支，但其本质却是一种新的世个新分支，但其本质却是一种新的世界观和方法论。界观和方法论。 A fractal is a rough or fragmented geometric shape that

43、 can be split into parts, each of which is (at least approximately) a reduced-size copy of the whole, a property called self-similarityNOVA纪录片：纪录片： hunting the hidden dimension “寻找隐藏的维度寻找隐藏的维度” 430， 2630 ，3000 分形应用：分形应用： 计算机虚拟现实技术；天线设计；医学；计算机虚拟现实技术；天线设计；医学； 第47页/共119页第四十八页，共119页。分形分形(fn xn) fractal科

44、赫雪花（Koch snowflake）：1、初始(ch sh)为正三角形；2、将每条边等分三段；3、以中段为底向外做等边三角形4、移除被三等分的边的中段。5、如此迭代。第48页/共119页第四十九页，共119页。曼德勃罗集（Mandelbrot）第49页/共119页第五十页，共119页。3.4 思路思路(sl)：将线性方程将线性方程 改写为等价形式改写为等价形式bxA xM xg(1)( ) (k=0,1,2,)kkxM xg(0),nxR从而建立代迭格从而建立代迭格式式)(kx按迭代格式按迭代格式进行迭代，得到向量序列进行迭代，得到向量序列 。当。当k充分大时，以充分大时，以x(k)作为方程

45、组作为方程组 的近似解，这就是求线性方程的近似解，这就是求线性方程组的迭代法。组的迭代法。M称为迭代矩阵。称为迭代矩阵。任取初始向量任取初始向量bxA 优点优点(yudin)：可人为：可人为控制精度特别适合控制精度特别适合于大型稀疏阵列，于大型稀疏阵列，但存在收敛性问题但存在收敛性问题求解求解bxA 第50页/共119页第五十一页，共119页。 如何建立迭代格式？如何建立迭代格式？ 收敛速度？收敛速度？ 向量序列的收敛条件？向量序列的收敛条件？ 误差误差(wch)估估计？计？n研究研究(ynji)内内容：容：第51页/共119页第五十二页，共119页。与直接解法与直接解法(ji f)的比较的比

46、较直接直接(zhji)法法: 经过有限次运算后可求得方程经过有限次运算后可求得方程组精确解的方法组精确解的方法(不计舍入误差不计舍入误差!)第52页/共119页第五十三页，共119页。直接法比较适用于中小型方程组。对高阶方程组直接法比较适用于中小型方程组。对高阶方程组，既使系数矩阵是稀疏的，但在运算中很难保持，既使系数矩阵是稀疏的，但在运算中很难保持(boch)稀疏性，因而有存储量大，程序复杂等不稀疏性，因而有存储量大，程序复杂等不足。足。迭代法则能保持矩阵的稀疏性，具有计算迭代法则能保持矩阵的稀疏性，具有计算(j sun)简单，简单，编制程序容易的优点，并在许多情况下收敛较快。故能有编制程序

47、容易的优点，并在许多情况下收敛较快。故能有效地解一些高阶方程组。效地解一些高阶方程组。第53页/共119页第五十四页，共119页。( )( )( )( )lim-0lim kkknnkkkxRxxxxxxRx设为为数则称敛记为义 中的向量序列，向量，如果 其中向量范，序列收于 ， 定： 收敛收敛(shulin)(shulin)问题问题( )( )( )( )( )( )1( )( )lim-0lim-010-max-0lim0(1,2, , )lim(kkkkkkkkiijjj nkiikkiikxxxxxxinxxxxxxxxiL nxxi 义敛对数则证由由定定， 收 收于于 ，即即 根根据

48、据，必必有有：而而任任意意，有有由由极极限限存存在在准准得得 即即 向向量量范范 的的等等价价 性性：1,2, , )L n第54页/共119页第五十五页，共119页。( )( )( )( )( )12(1)2,(,) ,( ,lim(1,)2, ,knknkkkiikkTTnnRxRxxxxxxx xiLxxxn敛当仅当中中的的向向量量序序列列收收于于中中的的向向量量且且 其其 ： 理理中中 定定 。)()( )( llimi-0mkkkkkkAnAnAAAAAA设为 阶阵为 阶阵为阵数义则称敛阵记为 方 方序序列列，方方，如如果果 其其中中矩矩范范，序序列列收收于于矩矩， 定定： 第55页

49、/共119页第五十六页，共119页。( )( )( )()(1,2lim( ,1, ),()2, , )kijijkkjkkijiAakLAanAAaai jL n设为 阶阵则阵敛阵条为证 均 均方方，矩矩序序列列收收于于矩矩的的充充要要件件 定 定理理 ：明明略略。(1)( )( )(1)( ),limlimkkkkkkkxMxgxxxMxAxxMxgbxg产敛点组则 若 若按按生生的的向向量量序序列列收收于于向向量量有有 即即极极程程限限是是方方 的的解解。定理表明：向量序列和矩阵序列的收敛定理表明：向量序列和矩阵序列的收敛(shulin)可以归结为对应的分量或对应元素序列的收敛可以归结为

50、对应的分量或对应元素序列的收敛(shulin)。第56页/共119页第五十七页，共119页。11112211211222221112,(1,)02,innnnnnnnnniLLLina x a xa xba x a xa xba x a xa xba写为阵则数 系系矩矩若若且且 上上述述可可非非奇奇 改改 异异：第57页/共119页第五十八页，共119页。112213311221123322n112233 nnnnnnnngxb xb xb xgxb xb xb xxb x b xb x-,(, ,1,2, ),(1,2, ).ijiijiiiiiij i jabbgaaL niL ng其其中

51、中第58页/共119页第五十九页，共119页。1213111121232122123100 0nnnnnnnnnnbbbbgbbbbgBgbbbbg记 若 若 (0)(1)10(1)(2)(1)( )( ), (0,1,2 ,) kkkxxxBxgxxxkxBxg选将继续产个满（）（）初初值值向向量量代代入入，代代入入，如如此此，就就生生一一向向量量序序列列足足则方程组可简记则方程组可简记(jin j)为为 xBxg此过程给出的迭代法称为此过程给出的迭代法称为(chn wi)Jacobi迭代法，又称迭代法，又称简单迭代法简单迭代法第59页/共119页第六十页，共119页。12112121221

52、212120110001010 01001nnnnnnnnBbbbbbbbbbbbb 11111121n1121222n221n1n2nn nnII -D Aaaaaaaaaaaaa1 12 111222(,)(, , , )TTDnbnnng ggb aaagbb同样11g=D I DbB-A即：第60页/共119页第六十一页，共119页。1* n0 1 2 g knnJacobigxxxBxxBx（）（ ）（ ），敛，则迭迭代代若若收收 *1*1 () IB xgD AxDAxbb即故如果序列收敛故如果序列收敛, , 则收敛到解则收敛到解. B. B称迭代称迭代(di (di di)di)

53、矩阵矩阵. .第61页/共119页第六十二页，共119页。1231231231027210283542xxxJacobixxxxxx 例 例：用用迭迭代代法法求求解解1(01)(0) 10010100101200.10.21010001 1020.100.2100011150.20.201005 (7.2,8.3,8.4)(0,0,0) ,(7.2,8.3 TTBID AgDxBxgb(1)解：x取取代代入入迭迭代代式式，得得(2)(1)(9)(10.9994,11,8.4)(.9994,9.71,10.70,112.9991.(11,12,13) .)5)2TTTTxBxgxx为精精确确解解

54、第62页/共119页第六十三页，共119页。(0)(0)(0)(0)112(0)(0)(0)11.(),( ,),(,),2.1.3.1,2, ,4.-,55.,1.(-),(1,2, ),3/niiijjiijjijnniiiNxbAabbbn xxxxkiL nx xxkNkk xxna xai 输维数对输则转转败许数则输入入置置 若若出出停停机机；否否精精度度 ，。若若置置；否否，出出最最大大容容迭迭失失信信息息代代次次，停停机机。( )(1,kkMxx变两组单评简单计阵）不不改改的的稀稀疏疏性性，需需工工作作元元，存存价价：公公式式，每每迭迭代代一一次次只只需需算算一一次次矩矩和和向向

55、量量的的乘乘法法，。第63页/共119页第六十四页，共119页。(1)( )( )( )112213311(1)( )( )( )221123322 kkkknnkkkknnJacobigxb xb xb xgxb xb xb x组为(k+1)(k)(k+1)(k)x= Bx+g (k =0,1,2, )，x= Bx+g (k =0,1,2, )，用用方方程程代代公公式式表表示示迭迭：(1)( )( )( )1122,)11( )(1 kkkknnnknnnknJacobixxgxb xb xbx时两计。过个因因此此，在在迭迭代代法法的的算算程程中中需需同同保保留留近近似似解解向向，量量和和第

56、64页/共119页第六十五页，共119页。(1)( )( )( )112213311(1)( )( )223322(1)(1)211(1)112 kkkknnkkknnknkknngxb xb xb xgxb xbbb xxxx(1)(1)2,11 kkn nnnb xbxg 整个计算过程只需用一组（整个计算过程只需用一组（n个）单元存放近似解分量。而且一般个）单元存放近似解分量。而且一般认为新近似解要比老近似解更接近真实解。认为新近似解要比老近似解更接近真实解。 将已计算出的将已计算出的x（k+1）分量替换）分量替换Jacobi 迭代公式迭代公式(gngsh)中中x（k）相应分量，这种方法称

57、为相应分量，这种方法称为Gauss-Seidel迭代。迭代。评价：评价： 与与Jacobi 相比，相比， Gauss-Seidel迭代法只需一组工作单元存迭代法只需一组工作单元存放放(cnfng)近似解。近似解。若把迭代公式若把迭代公式(gngsh)改写为：改写为：第65页/共119页第六十六页，共119页。用矩阵用矩阵(j zhn)表示表示 :(1)( )-1( - )-1,( - )kkI L xUxgI LI L 项为移移可可得得 存存在在，上上式式(1)( )( )( )112213311(1)( )( )22332(12)211(1(1)112 kkkknnkkkknnnnnkkgx

58、b xb xb xgxb xxbbxxxb(1)(1)2,11 kkn nnnb xbxg1212,000U000000nnbbb21120000000 00nnLbbb(1)(1)( ) kkkxLxUxg(1)1( )1()()kkxILUxILg第66页/共119页第六十七页，共119页。12131212323132112111111(1)1( 000000000 , () ()nnnnnnnnkkAaaaaaaLaaUaaaaLD LUD UILD DD LDDLxILUx 阵 来记则 如 如果果用用矩矩表表示示，由由)1()ILg(1)1( )1()()kkxDLUxDLb-1(-

59、)-MD LUGauss Seidel阵为阵式式中中矩矩 迭 迭代代法法的的迭迭代代矩矩。第67页/共119页第六十八页，共119页。Gauss-Seidel迭代法的解迭代法的解123123123(0)1(0)(0)12311(1)(0)21321310272-10283542(0,0,0) ,11 (2)727.2000101011 (2)(7.200083)9.02001010 TxxxGauss Seidelxxxxxxxxxxbxxxbx（ ）（ ）（ ） 例 例：用用迭迭代代法法求求解解解解：仍仍取取代代入入迭迭代代式式，得得(1)(1)123(5)11()7.20009.02004

60、2)11.6440(10.9989,11.9993,12.9996(11,12,13) .)55Txxbxx（继续为如如此此下下去去，精精确确解解(9)(10.9994,11.9994,12.9992)TJacobix迭迭代代法法的的解解：第68页/共119页第六十九页，共119页。比较比较(bjio)：评价：评价： 与与Jacobi 相比，相比， Gauss-Seidel迭代法只需一组工作单元迭代法只需一组工作单元(dnyun)存放近似解。存放近似解。 上例计算结果显示，上例计算结果显示， Gauss-Seidel迭代法比迭代法比Jacobi 迭代效迭代效果好。事实上，果好。事实上， 对有些