JA4-2-线性方程组迭代

4 2 线性方程组的迭代解 2 1 Jacobi 迭代法 3 1 1 1 2 1 1 1 9 4 2 1 0 0 1 11 33 22 11 1 2 11 2 323 121222 1 2 1 11 1 313 212111 1 1 11 332211 211 3231212222 111 3132121111 2211 2222121 11212111 k nnn k n k n k nnnn k n k nn k nn kkk k nn k nn kkk nnnnnnnnnn nnnnn nnnnn ii nnnnnn nnn nn xaxaxaxabax xaxaxaxabax xaxaxaxabax xaxaxaxabax xaxaxaxabax xaxaxaxabax nia xf bxaxaxa bxaxaxa bxaxaxa 建立迭代格式 可以改写为时当 式的求根方法建立迭代格可仿照 对线性方程组 Jacobi Jacobi 5 2 1 4 2 1 3 0000 000 00 0 0 000 0000 00000 diag diag 2 1 0 4 9 1 11 1 1 1 1 223 11312 1 321 3231 21 11 22 1 11 1 2211 迭代矩阵称为迭代的矩阵形式称为 则迭代格式为进一令 可以写为则迭代格式为对角阵为严格上三角阵为严格下三角阵上面 记设改用矩阵形式表示为将 M kgMxx bDgFEDM kbDxFEDx DFE a aa aaa F aaaa aa a E aaaDaaaD niabAx kk kk nn n n nnnnn nnnn ii 算法 3 exceeded iterations ofnumber Maximun 5 step 0 1 4 step 3 step 0 1 2 step 4 2 step 1 1 step 0 10 1 1 0 范数最常用的是任何一种简便的范数所用的向量范数可以是 可用中的迭代终目准则在 停机输出 对 停机则输出若 对 做对 的信息或迭代次数超过近似解输出 最大迭代次数误差容限初始向量中的方程组输入 l TOL x xx step xx ni xxTOLxx axabx ni mk mx mTOLxbAbAx ii n ii n j j jijii 2 2 迭代的收敛条件 6 9 7 1 2 4 6P99 8 4 2 5 3 260 32 9 10 13 20 3 5 85 2 6 1 2 4 5P99 8 4 2 5 3 260 32 7 4 2 5 3 260 32 6 6 45 2 26203 Ex 2 1 1 1 2 2 1 1 12 21 2 1 1 1 2 2 1 1 12 21 21 21 列收敛于解满足什么条件时迭代序论不同造成的因此需要讨 显然这是由于迭代矩阵但迭代结果却不相同等价都与与虽然方程组由此可见 收敛于精确解知迭代序列表由 迭代格式为则 重新改写为的两个方程后若交换 收敛于精确解知不能确定迭代序列表由 迭代格式为则 改写为若将解 的解 用迭代法求方程组 M M xx xx xx Jacobi xx xx ii xx xx xx Jacobi xx xx i xx xx TTkk kk kk TTkk kk kk 1 向量的范数 不等式再根据条满足向量范数定义前两容易验证 中引进函数在 的赋范线性空间是赋以范数并说的一种范数为则称 三角不等式 及齐次性 非负性 它满足记作的一个实值函数中定义了向量若在定义 Minkowskixf pxxf R xRxx Ryxyxyx RRxxx xRxx xxxxxR p p n i p ip n n n n n T n n 2 1 3 2 0 0 1 1 1 21 max 1 lim 2 1 1 2 1 0 max max lim EuclidEuclid 2 1 2 1 3 2 1 1 1 1 1 1 1 1 1 1 1 1 2 2 1 1 2 2 1 1 1 1 1 1 1 1 1 1 i ni j p n i p j i p n i p j i p n i p j i j p n i p ip i ni j i ni p p n i i n i i n i i p n i p ip p pp n pp p n i p i p n i p i p n i p ii xxx x x pn x x p x x xxx xxx xxx xxx xx p pxx x lxxfRxfxf pxxyx 有则对令事实上现证明上面这条 长度范数或 我们有显然的情形特别有用的是对于数值方法来说 即记作范数 的为向量我们称中的一种范数是因此条满足定义中的第立即推得 AA TT TTT A n TTTTTT A T TT A T A n T A n yxyLxL yLxLyxLyx Ryx xLxLxLxLLxx LLALA xAxxxAxx xAxxxA R Axxx RxnA 3 0 0 2 0 0 1 Ex 22 22 2 2 1 2 1 2 1 2 1 2 1 2 1 恒有对任意的从而 于是使得角阵因此总存在非奇异下三正定因 对任意的实数 因此正定因 满足范数定义中的三条验证如上定义的实函数证 中的一种向量范数是 则阶实对称正定矩阵是给定的设 n 1 2 1 0 0 have we 3 2 0 1 量范数是相容的则说上述矩阵范数和向成立 恒有不等式中任何一个向量和的任何一个矩阵 中若对中规定了一种向量范数在中规定了一种矩阵范数假定在 的赋范线性空间是赋以范数并说的一种范数为矩阵则称 及 它满足 记作若在其上定义了实函数实矩阵构成的线性空间表示全体设定义 xAAx xRA RRR ARAA RBABAAB RBABABA RRAAA OARAA xnnR n nnnnn nn nn nn nn nn nn 00 00 00 00 00 4 3 1 00 00 00 2 1 21 22221 11211 1 1 2 1 xAAx x x x aaa aaa aaa xa xa aA x x x x x Rx RR nnnnn n n n j jnj n j jij nnij n n nnn 便有的定义据据此 有条再由矩阵范数第设的条件 满足向量范数定义中易知件据矩阵范数应满足的条事实上就是一种这种的范数 取设证 是相容的和 使得数中至少存在一种向量范则在中的任意一种矩阵范数是设定理 1 0 0 1 0 000 0 00 0 Ix xIIxx xIII xA xA xAAx ARx RAxA n nn 得由 使得必存在一个向量对于单位矩阵这是因为为单位矩阵其中且相容 与向量范数的必要条件是矩阵范数从属于向量范数矩阵范数 的矩阵范数是从属于向量范数则说 使得有关它与 都存在一个非零向量且对每一个相容与向量范数假定矩阵范数 max max max 3 3 max max 2 2 0 max 0 0 1 0 0 1 4 1 1 max 2 1 1 1 1 1 1 00 00 1 BABxAxxBABA AAxAxA AR AxA AxAxx yyxyAyyRyOA A xAAAx xRx xAxRA AxA RxR xxx xx x n n nn x nnn 有据向量范数条件 有的定义及向量范数条件据对 因此从而并且仍然有 则即令规格化我们可以将使得则必存在设 个条件以及相容性条件满足矩阵范数的所定义的其次验证 使得一定存在一个非零向量这就是说因此必达到它的最大值 习题上连续在有界闭集由于对于任意一个矩阵首先证 数就是这样的一种矩阵范 定义它的矩阵范数中至少存在一种从属于中的每一向量范数对定理 1 max max max max 5 1 1 1 1 4 1 1 1 1 xA AxxBxA BABxABxABxAAB RBA xAAxx x Axx x AxAx x x Rx x xxx nn n 从属于向量范数故矩阵范数 无关与上来求的在是关于上式中 对 因此由于非零对 93 max max 2 1 2 1 2 1 2 1 1 2 1 1 1 P AA ax AAA aA aAplp AplA n j ij ni T n i ij nj nnijp pp 上科学出版社林成森继续参阅数值计算方法证明略 的谱范数又称为矩阵 的最大特征值是 则 设式它们有比较明显的表达范数这三种范数分别从属于 记作得到具体的矩阵范数范数分别取向量的的定义式中在 Frobenius Schur Frobenius 22 2 2 2 111 22 111 22 11 2 2 2 11 2 2 1 1 2 矩阵的情形矩阵范数还可以推广到以上介绍的 即 事实上范数是相容的范数与 范数又称为范数数是还有一种常用的矩阵范 nmnn xAAx xAxaxaxaAx l aaA F F n i n j n j jij n i n j n j jij n i n j jij n i n j ij n ji ijF 0 0 max 2 1 lim 0 lim lim 0 lim 1 AA A xx xAAxxxAxx xAA A Ani AAAA AAxxxxxx i ni i k k k k k k k kk k 的关系式由此我们得到一个重要 从而有得由特征向量 有的特征向量的任一个对应于由于的谱半径为矩阵 称的全部特征值为设 记为收敛于则称矩阵序列 若记为收敛于则称向量序列若 P102 1 1 5 4 4 0 1 0 1 书证 且有误差估计式收敛迭代序列和初始向量 则对任意的某一种范数若即对于迭代格式定理 xx M M xx xgx MMgMxx k k k kk 1 5 5 4 1 书上没证略证 收敛的充要条件是即迭代格式定理 M gMxx kk 本段一开始的例题法1中出现的M不满足定理4 5 而法2中出现的M满足定理条件 J Ex 1 0在程序中 及初始解向量迭代法解方程组用xbAbAxacobi restart with linalg Warning the protected names norm and trace have been redefined and unprotected Jacobi proc A b x0 m local n x X0 a1 a2 k i j n vectdim col A 1 X0 x0 x vector 0 0 0 0 for k from 1 to m do for i from 1 to n do a1 0 a2 0 for j by 1 from 1 to i 1 do a1 a1 A i j X0 j end do for j by 1 from i 1 to n do a2 a2 A i j X0 j end do x i b i a1 a2 A i i end do X0 x print map evalf x end do end A matrix 4 4 5 1 1 1 1 10 1 1 1 1 5 1 1 1 1 10 b vector 4 12 8 34 x0 vector 0 0 0 0 Jacobi A b x0 6 8000000000 1 200000000 1 600000000 3 400000000 4400000000 1 744000000 2 716800000 3 890080000 8701760000 1 947705600 2 941592320 3 975947392 9730490624 1 989058877 2 987611066 3 994971901 9943283689 1 997691134 2 997398281 3 998941778 9988062385 1 999514630 2 999452529 3 999777340 精确结果为 1 2 3 4 2 3 Gauss Seidel 迭代法 在Jacobi迭代法中 有一个明显的特点 就是每次迭代右端的变量的值全部用前一次迭 代值来代换 所以Jacobi迭代 又称为同步迭代法 可以设想 如果迭代序列收敛 则将迭代格式 3 中第一个方程计算出来的 Seidel Gauss 3 Jacobi 1 3 1 12 1 1 1 1 迭代格式如下迭代法称为按这样建立的迭代方程 算出来马上代入到第三个方程的把前两个方程计算出来代入到第二个方程使用 马上的中第一个方程计算出来将其迭代格式迭代法中迭代序列收敛如果 k kk k x xx x 6 SeidelGuass 7 7 6 6 6 4 6 1 1 1 1 1 1 1 1 1 1 1 1 1 11 1 1 1 1 1 1 11 1 33 1 22 1 11 11 1 3 33 3 11 3 1 232 1 131 11 1 3 2 22 2 11 2 323 1 121 22 1 2 1 11 1 11 1 313 212 11 1 1 存在而 迭代的矩阵形式为称则其中 改写为进一下可将 可以写成矩阵形式式式由 EDbFxxEDbDgbFxExDx bEDgFEDM gxMx gFxDExDx b a xaxaxaxa a x b a xaxaxaxa a x b a xaxaxaxa a x b a xaxaxaxa a x kkkkk kk kkk n nn k nnn k n k n k n k n k nn k nn kkk k nn k nn kkk k nn k nn kkk 关于Gauss Seidel迭代法的收敛结论 除了用定理4 4与4 5外 还可由方程组 的系数矩阵的某些特征来判断迭代是不收敛 bAx 1 若A为严格对角占优矩阵 各行非对角元绝对值之和小于对角元绝对值的矩阵 则 且Jacobi迭代法与Gauss Seidel迭代法都收敛 0 A 2 对A为对称正定阵 则且Gauss Seidel迭代法收敛 Jacobi 0 A 需进一步说明 某些方程对于Jacobi迭代收敛 而对Gauss Seidel迭代不收敛 而某些对 于Gauss Seidel收敛 但用Jacobi迭代却不收敛 但 对待实际问题可用上述两个结论加以判 断 或交换方程的次序使迭代法收敛 Seidel Gauss Ex 1 Ex 2 0在程序中 及初始解向量迭代法解方程组用对xbAbAx restart with linalg GaussSeidel proc A b x0 m local n x X0 a1 a2 k i j n vectdim col A 1 X0 x0 x vector 0 0 0 0 for k from 1 to m do for i from 1 to n do a1 0 a2 0 for j by 1 from 1 to i 1 do a1 a1 A i j x j end do for j by 1 from i 1 to n do a2 a2 A i j X0 j end do x i b i a1 a2 A i i end do X0 x print k print map evalf x end do end A matrix 4 4 5 1 1 1 1 10 1 1 1 1 5 1 1 1 1 10 b vector 4 12 8 34 x0 vector 0 0 0 0 GaussSeidel A b x0 6 8000000000 1 120000000 1 664000000 3 598400000 4764800000 1 773888000 2 769753600 3 902012160 8891307520 1 956089651 2 949446513 3 979466692 9770005711 1 990591378 2 989411728 3 995700368 9951406946 1 998025279 2 997773268 3 999093924 9989784943 1 999584569 2 999531397 3 999809446 精确结果为 1 2 3 4 2 4 逐次超超松弛迭代法 逐次超松驰迭代法是Gauss Seidel迭代法的一种加速方法 是解大型稀疏矩阵方程组的有 效方法之一 它具有计算公式简单 程序设计容易 占用计算机内存比较少之优点 但需要 选择好的加速因子 即最佳松弛因子 现将迭代法 5 改写成 则上式写成矩阵形式为 式写成等价形式现将 迭代法为时 当称为松驰因子驰迭代法这咱方法称为逐步超松可使迭代收敛速度加快值适当选取 为即个参数 在修正量前乘以一为获得更快的收敛效果加一个修正量的基础上每一个分量增 步步是相当于在第迭代法的第因此则当迭代收敛时 若记 1 2 1 9 9 1 9 1 2 8 1 1 0 1 2 8 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 3 2 1 121222 2 1 2 2 1111 1 1 1 nixaxab a xx SeidelGauss nixaxab a xx r a kkSeidelGausskr nixaxabr xaxabaxx xaxabaxx xaxabaxx xabaxx n ij k jij i j k jiji ii k i k i n ij k jij i j k jiji ii k i k i k i ii k i n ij k jij i j k jiji k i k nnn n j k jnjnnn k n k n n ij k jij i j k jijiii k i k i n j k jj kkk n j k jj kk 11 2 2 0 10 1 6 4 1 1 1 10 1 0 0 2 0 1 1 1 11 1 1 1 1 的近似值 确定出大都由经验通过计算来在实际计算时的理论结果目前尚无确定正定对称矩阵 即使是对于一般矩阵弛因子为某些特殊矩阵的最优松可以证明 件是 收敛的必要条进一步地有的充要条件是逐次超松驰迭代法收敛定理 我们有下面的结论关于逐步超松驰迭代法 其中 或 M M bxFDxED FxExbDxDx bEDgFDEDM gxMx F