2022年2022年解线性方程组的基本思想 .pdf

《2022年2022年解线性方程组的基本思想 .pdf》由会员分享，可在线阅读，更多相关《2022年2022年解线性方程组的基本思想 .pdf（17页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、四：基本方法基本思路将在解题的过程中得到体现。1（求线性方程组的唯一解或特解），这类问题的求法分为两类：一类主要用于解低阶稠密矩阵直接法；一类是解大型稀疏矩阵迭代法。1.1 利用矩阵除法求线性方程组的特解（或一个解）方程：AX=b，解法：X=Ab，(注意此处 不是/)例 1-1 求方程组的解。解:A=;=；b=(1,0,0,0,1)由于 rank(A)=5,rank()=5%求秩，此为R（A）=R（）=n 的情形，有唯一解。X=Ab%求解X=(2.2662,-1.7218,1.0571,-0.5940,0.3188)或用函数rref 求解，sv=rref(A:b);所得 sv 的最后一列即为所

2、要求的解。12 利用矩阵的LU、QR 和 cholesky 分解求方程组的解这三种分解，在求解大型方程组时很有用。其优点是运算速度快、可以节省磁盘空间、节省内存。I)LU 分解又称Gauss消去分解，可把任意方阵分解为下三角矩阵的基本变换形式（行交换）和上三角矩阵的乘积。即A=LU，L 为下三角阵，U 为上三角阵。则：A*X=b 变成 L*U*X=b 所以 X=U(Lb)这样可以大大提高运算速度。命令L，U=lu(A)在 matlab 中可以编如下通用m 文件：在 Matlab 中建立 M 文件如下%exp1.m A;b;L，U=lu(A);X=U(Lb)II）Cholesky 分解若 A 为

3、对称正定矩阵，则 Cholesky 分解可将矩阵A 分解成上三角矩阵和其转置的乘积，即：其中 R 为上三角阵。方程A*X=b 变成所以在 Matlab 中建立 M 文件如下%exp2.m A;b;R ，R=chol(A);(R b)III）QR 分解对于任何长方矩阵A，都可以进行QR 分解，其中 Q 为正交矩阵，R 为上三角矩阵的初等变换形式，即：A=QR 方程A*X=b 变形成QRX=b 所以X=R(Qb)名师资料总结-精品资料欢迎下载-名师精心整理-第 1 页，共 17 页 -上例中Q,R=qr(A)X=R(QB)在 Matlab 中建立 M 文件如下%exp3.m A;b;Q，R=qr(

4、A);X=R(Qb)2求线性齐次方程组的通解(A*X=0)在 Matlab 中，函数 null 用来求解零空间，即满足 A•X=0的解空间，实际上是求出解空间的一组基（基础解系）。在 Matlab 中建立 M 文件如下%exp4.m format rat%指定有理式格式输出A;b=0;r=rank(A);bs=null(A，r );%一组基含(n-r)个列向量%k,k,k%X=k*bs(:,1)+k*bs(:,2)+k*bs(:,n-r)方程组的通解pretty(X)%让通解表达式更加精美3 求非齐次线性方程组的通解（A*X=b）非齐次线性方程组需要先判断方程组是否有解，若有解，再

5、去求通解。因此，步骤为：第一步：判断AX=b 是否有解，(利用基本思路的第一条)若有解则进行第二步第二步：求AX=b 的一个特解第三步：求AX=0 的通解第四步：AX=b 的通解为：AX=0 的通解加上AX=b 的一个特解。在 Matlab 中建立 M 文件如下%exp4.m clear all A;b;%输入矩阵A,b m,n=size(A);R=rank(A);B=A b;Rr=rank(B);format rat if R=Rr&R=n%n 为未知数的个数，判断是否有唯一解x=Ab;elseif R=Rr&R|aij|i=1,2,n,j=1,ji 则称方阵 A 是严格(行)对角占优的.7

6、.收敛定理对任意初始向量x(0)及任意右端向量g，由迭代 x(k+1)=B x(k)+g 产生的迭代向量序列x(k)收敛的充要条件是谱半径（B）1 8.收敛判别条件判别条件 1：若|B|1,则迭代 x(k+1)=B x(k)+g 对任何初始向量x(0)都收敛.判别条件 2：如果 A 为严格对角占优阵，则其Jacobi迭代和 Seidel 迭代对任何初始向量x(0)都收敛。判别条件 3：如果 A 为对称正定阵，则其Seidel 迭代对任何初始向量x(0)都收敛。9.迭代法的误差估计若|B|1，则对迭代格式x(k+1)=B x(k)+g 有3.3 程序中 Mathematica 语句解释a*mat

7、rix 数 a 与矩阵 matrix 相乘matrix1+matrix2 矩阵 matrix1 和矩阵 matrix2 相加（注意矩阵的大小相同）matrix1.matrix2 矩阵 matrix1 和矩阵 matrix2 相乘(注意矩阵乘法的规则)Transposematrix 求矩阵 matrix 转置Inversematrix 求矩阵(方阵)matrix 的逆)()1(*)()1()(*)(1.21.1okkkkkxxBBxxxxBBxx名师资料总结-精品资料欢迎下载-名师精心整理-第 5 页，共 17 页 -DiagonalMatrixlist使用列表 list 中的元素生成一个对角矩

8、阵.IdentityMatrixn 生成 n 阶单位矩阵Maxx求向量 x 中元素的最大值3.4 方法、程序、实验解线性方程组的迭代法是将线性方程组Ax=b 化为等价线性方程组x=Bx+f 再由矩阵迭代格式x(k+1)=Bx(k)+f 构造向量序列 x(k)来求线性方程组解的。如果得出的向量序列x(k)收敛至某个向量x*，则可得该向量x*就是所求方程组Ax=b 的准确解.线性方程组的迭代法主要有Jocobi 迭代法、Seidel 迭代法和超松弛(Sor)迭代法。1.Jocobi 迭代法1)Jocobi迭代法的构造过程假设 aii0，依次在第i 个方程解出x i,i=1,2,n 并令cij=-a

9、ij/aii(i j)，gi=bi/aii 就得到如下 Jocobi 迭代格式：x1(k+1)=c12x2(k)+c13x3(k)+c1nxn(k)+g1x2(k+1)=c21x1(k)+c23x3(k)+c2nxn(k)+g2。xn(k+1)=cn1x1(k)+cn2x2(k)+cn(n-1)xn-1(k)+gn若令nnnnnnJggggxxxxccccccB212121221112000名师资料总结-精品资料欢迎下载-名师精心整理-第 6 页，共 17 页 -则有 Jocobi 迭代的矩阵格式：x(k+1)=BJx(k)+gJ BJ称为 Jocobi 迭代矩阵。Jocobi 迭代可以写成如

10、下紧凑格式：在给定初始迭代向量x(0)后就可以进行Jocobi 迭代求解了。2)Jacobi 迭代算法1.输入变量个数n、初值向量x（0）、迭代精度eps、系数矩阵A、常数项 b 和迭代最大次数nmax 2 For i=1,2,n 2.1 如果|aii|eps1,则输出“迭代失败”提示并终止3.Bj E-D-1A 4.gj D-1b 5.For k=1,2,nmax 5.1 x Bj.x0+gj5.2 如果|x-x0|eps,输出迭代失败，终止。3)Jacobi 迭代法程序Cleara,b,x;nmax=500;n=Input“线性方程组阶数n=”;a=Input 系数矩阵 A=；b=Inpu

11、t 常数项 b=；x0=Input 输入迭代初值向量x0；eps1=0.000001;eps=Input 输入精度控制eps=；ninijjiiikjiiijkiabxaax,2,11)()1(名师资料总结-精品资料欢迎下载-名师精心整理-第 7 页，共 17 页 -DoIfAbsai,ieps1,t1=1;Return,t1=0,i,1,n;Ift1=1,PrintJacobi 迭代法失效,d=DiagonalMatrixTableai,i,i,1,n;d1=Inversed;bj=IdentityMatrixn-d1.a;gj=d1.b;Do x=bj.x0+gj;err=MaxAbsx-

12、x0;Printx=,x/N,i=,i,err=,err/N;IfNerr=eps,Print 迭代失败 说明本程序用于求线性方程组Ax=b 的解。程序执行后，先通过键盘输入线性方程组阶数n、系数矩阵 A、常数项 b、迭代初值向量x0 和输入精度控制eps，程序即可给出每次迭代的次数和对应的迭代向量序列x(k),其中最后输出的结果即为所求的根。如果迭代超出500 次还没有求出满足精度的根则输出迭代失败提示，如果出现主对角线元素aii=0 给出 Jacobi迭代法失效提示。程序中变量说明x0：存放初始向量和迭代过程中的向量x（k）x:存放迭代过程中的向量x（k+1）nmax:存放迭代允许的最大次

13、数err:存放误差|x-x0|t1:临时变量注：迭代最大次数可以修改为其他数字。4)例题与实验例 1.用 Jacobi 迭代法解如下线性方程组5x1+2x2+x3=-12-x1+4x2+2x3=20 名师资料总结-精品资料欢迎下载-名师精心整理-第 8 页，共 17 页 -2x1-3x2+10 x3=3 要求误差|x(k+1)-x(k)|10-4，并用取不同初值的方法实验观察迭代收敛的情况。解：执行 Jacobi 迭代法程序后在输入的四个窗口中按提示分别输入:3、5,2,1,-1,4,2,2,-3,10、-12,20,3、0,0,0、0.0001 每次输入后用鼠标点击窗口的“OK”按扭，得如下

14、输出结果：x=-2.4,5.,0.3 i=1 err=5.x=-4.46,4.25,2.28 i=2 err=2.06 x=-4.556,2.745,2.467 i=3 err=1.505 x=-3.9914,2.6275,2.0347 i=4 err=0.5646 x=-3.85794,2.9848,1.88653 i=5 err=0.3573 x=-3.97123,3.09225,1.96703 i=6 err=0.113286 x=-4.03031,3.02368,2.02192 i=7 err=0.0685705 x=-4.01386,2.98146,2.01316 i=8 err=0

15、.042216 x=-3.99522,2.98995,1.99721 i=9 err=0.0186374 x=-3.99542,3.00259,1.99603 i=10 err=0.0126367 x=-4.00024,3.00313,1.99986 i=11 err=0.0048186 x=-4.00122,3.00001,2.00099 i=12 err=0.00312067 x=-4.0002,2.9992,2.00025 i=13 err=0.00102319 x=-3.99973,2.99983,1.9998 i=14 err=0.000625697 x=-3.99989,3.000

16、17,1.99989 i=15 err=0.00034136 x=-4.00005,3.00008,2.00003 i=16 err=0.000155236 x=-4.00004,2.99997,2.00003 i=17 err=0.000106099 x=-4.,2.99997,2.i=18 err=0.0000414468 此结果说明迭代18 次，求得误差为err=0.0000414468 的近似解，最后显示的近似解向量为x=-4.,2.99997,2.，它表示所求解为x1=-4，x2=2.99997，x3=2。本题的准确解为x1=-4，x2=3，x3=2。名师资料总结-精品资料欢迎下载-

17、名师精心整理-第 9 页，共 17 页 -如果将如上输入的初值改为21,-18,30，执行 Jacobi 迭代法程序后得如下输出结果：x=-1.2,-4.75,-9.3 i=1 err=39.3 x=1.36,9.35,-0.885 i=2 err=14.1 x=-5.963,5.7825,2.833 i=3 err=7.323 x=-5.2796,2.09275,3.22735 i=4 err=3.68975 x=-3.88257,2.06642,1.98375 i=5 err=1.39703 x=-3.62332,3.03749,1.69644 i=6 err=0.97106 x=-3.9

18、5428,3.24595,1.93591 i=7 err=0.330963 x=-4.08556,3.04347,2.06464 i=8 err=0.202475 x=-4.03032,2.94629,2.03015 i=9 err=0.0971858 x=-3.98455,2.97734,1.98995 i=10 err=0.0457716 x=-3.98893,3.00889,1.99011 i=11 err=0.0315451 x=-4.00158,3.00771,2.00045 i=12 err=0.0126504 x=-4.00318,2.99938,2.00263 i=13 err

19、=0.00833246 x=-4.00028,2.99789,2.00045 i=14 err=0.00289753 x=-3.99925,2.99971,1.99942 i=15 err=0.0018145 x=-3.99977,3.00048,1.99976 i=16 err=0.000770763 x=-4.00014,3.00018,2.0001 i=17 err=0.000375926 x=-4.00009,2.99992,2.00008 i=18 err=0.000261658 x=-3.99998,2.99994,1.99999 i=19 err=0.000107579 x=-3

20、.99997,3.00001,1.99998 i=20 err=0.0000714045 从计算结果可以看到虽然所取的初值不同，但迭代总是收敛相同的结果。考察本题系数矩阵可以发现它是严格对角占优矩阵，由收敛判别法，Jacobi 迭代对任意初值都是收敛的，我们通过实际计算验证了这个结果。例 2.通过 Jacobi 迭代序列观察用Jacobi 迭代法解如下线性方程组x1+2x2+2x3=-12-x1+4x2+x3=20 2x1-3x2+x3=3 的收敛性。解：执行 Jacobi 迭代法程序后在输入的四个窗口中按提示分别输入:名师资料总结-精品资料欢迎下载-名师精心整理-第 10 页，共 17 页

21、-3、1,2,2,-1,4,1,2,-3,1、-12,20,3、0,0,0、0.0001 每次输入后用鼠标点击窗口的“OK”按扭，得如下输出结果：x=-12.,5.,3.i=1 err=12.x=-28.,1.25,42.i=2 err=39.x=-98.5,-12.5,62.75 i=3 err=70.5 x=-112.5,-35.3125,162.5 i=4 err=99.75,.246.719,-120.176,696.719 i=8 err=763.5 x=-1165.09,-107.5,-850.965 i=9 err=1547.68 x=1904.93,-73.5303,2010.

22、67 i=10 err=3070.02 x=-3886.28,-21.4355,-4027.45 i=11 err=6038.12 x=8085.77,40.2917,7711.26 i=12 err=11972.1 x=-15515.1,98.6279,-16047.7 i=13 err=23758.9 x=31886.1,138.141,31329.1 i=14 err=47401.2 x=-62946.5,144.247,-63354.7 i=15 err=94832.5 x=126409.,107.068,126329.i=16 err=189683.x=-252883.,25.077

23、5,-252494.i=17 err=379292.x=504925.,-92.4305,505845.i=18 err=758339.,.通过观察迭代过程中的误差是不断变大的特点可以知道本题的Jacobi 迭代序列是不收敛的，因此，本题线性方程组不能用Jacobi 迭代法求解。这个实验说明并不是每个线性方程组都能用Jacobi 迭代法求解。2.Seidel迭代1)Seidel 迭代的构造过程为了加快收敛速度，同时节省计算机的内存，对 Jocobi 迭代作如下的改进：每算出一个分量的近似值，立即用到下一个分量的计算中去，即用迭代格式：x1(k+1)=c12x2(k)+c13x3(k)+c1nx

24、n(k)+g1x2(k+1)=c21x1(k+1)+c23x3(k)+c2nxn(k)+g2。名师资料总结-精品资料欢迎下载-名师精心整理-第 11 页，共 17 页 -xn(k+1)=cn1x1(k+1)+cn2x2(k+1)+cn(n-1)xn-1(k+1)+gn如上迭代可以写成如下紧凑格式：这样所得的迭代法就称为Seidel 迭代法。利用 Ax=b 及 A=L+D+U,其中 D 为对角矩阵,L,U 分别为严格下，上三角矩阵则有Seidel 迭代法的矩阵形式为x(k+1)=Bs x(k)+gs其中：Bs=-(L+D)-1U，g s=D-1b Seidel 迭代矩阵为Bs=-(L+D)-1U

25、。在给定初始迭代向量x(0)后就可以进行Seidel 迭代求解了。Jacobi 迭代和 Seidel 迭代格式可表述为统一形式:2)Seidel迭代算法1.输入变量个数n、初值向量x（0）、迭代精度eps、系数矩阵A、常数项 b 和迭代最大次数nmax 2.For i=1,2,n 2.1 如果|aii|eps1,则输出“迭代失败”提示并终止3.For i=1,2,nmax 3.1 For i=1,2,n 3.2 如果|x(k+1)-x(k)|eps,输出解向量x，终止；否则x（k）x(k+1)4.如果|x-x0|eps,输出迭代失败，终止。iinijkjijijkjijikiaxaxabx1)

26、(11)1()1(gBxxkk)()1(iinijkjijijkjijikiaxaxabx1)(11)1()1(名师资料总结-精品资料欢迎下载-名师精心整理-第 12 页，共 17 页 -3)Seidel 迭代法程序Cleara,b,x;nmax=500;n=Input“线性方程组阶数n=”;a=Input 系数矩阵 A=；b=Input 常数项 b=；x0=Input 输入迭代初值向量x0；eps1=0.000001;eps=Input 输入精度控制eps=；x=x0;DoIfAbsai,ieps1,t1=1;Return,t1=0,i,1,n;Ift1=1,PrintSeidel 迭代法失

27、效,Do Dou1=Sumai,j*xj,j,1,i-1;u2=Sumai,j*x0j,j,i+1,n;xi=(bi-u1-u2)/ai,i,i,1,n;err=MaxAbsx-x0;Printx=,x/N,k=,k,err=,err/N;IfNerr=eps,Print 迭代失败 说明本程序用于求线性方程组Ax=b 的解。程序执行后，先通过键盘输入线性方程组阶数n、系数矩阵 A、常数项 b、迭代初值向量x0 和输入精度控制eps，程序即可给出每次迭代的次数和对应的迭代向量序列x(K),其中最后输出的结果即为所求的根。如果迭代超出500 次还没有求出满足精度的根则输出迭代失败提示，如果出现主对

28、角线元素aii=0 给出 Jacobi迭代法失效提示。程序中变量说明x0：存放初始向量和迭代过程中的向量x（k）名师资料总结-精品资料欢迎下载-名师精心整理-第 13 页，共 17 页 -x:存放迭代过程中的向量x（k+1）nmax:存放迭代允许的最大次数err:存放误差|x-x0|t1,u1,u2:临时变量注：迭代最大次数可以修改为其他数字4)例题与实验例 3.用 Seidel 迭代法解如下线性方程组5x1+2x2+x3=-12-x1+4x2+2x3=20 2x1-3x2+10 x3=3 要求误差|x(k+1)-x(k)|10-4。解：执行 Seidel 迭代法程序后在输入的四个窗口中按提示

29、分别输入:3、5,2,1,-1,4,2,2,-3,10、-12,20,3、0,0,0、0.0001 每次输入后用鼠标点击窗口的“OK”按扭，得如下输出结果：x=-2.4,4.4,2.1 k=1 err=4.4 x=-4.58,2.805,2.0575 k=2 err=2.18 x=-3.9335,2.98787,1.98306 k=3 err=0.6465 x=-3.99176,3.01053,2.00151 k=4 err=0.0582625 x=-4.00451,2.99812,2.00034 k=5 err=0.0127509 x=-3.99931,3.,1.99986 k=6 err=

30、0.00519946 x=-3.99997,3.00007,2.00002 k=7 err=0.000659841 x=-4.00003,2.99998,2.k=8 err=0.0000916628 此结果说明迭代8 次，求得误差为err=0.0000916628 的近似解，最后显示的近似解向量为x=-4.00003,2.99998,2.，与本题的准确解为x1=-4.，x2=3.，x3=2.误差很小。注意到本题在同样迭代误差和初值前提下，用 Jacobi 迭代需要18 次迭代才获得具有同样精度的解，这说明，在都收敛的前提下，Seidel 迭代比Jacobi 迭代收敛快。例 4.设线性方程组为x

31、1+2x2-2x3=1 x1+x2+x3=1 名师资料总结-精品资料欢迎下载-名师精心整理-第 14 页，共 17 页 -2x1+2x2+x3=1 考 察 用 Jacobi 迭代法和Seidel 迭代法求解该线性方程组的收敛情况。如果收敛，给出误差满足|x(k+1)-x(k)|10-4的解。解：执行 Seidel 迭代法程序后在输入的四个窗口中按提示分别输入:3、1,2,-2,1,1,1,2,2,1、1,1,1、0,0,0、0.0001 每次输入后用鼠标点击窗口的“OK”按扭，得如下输出部分结果：,.x=-5123.,5379.,-511.k=9 err=3072.x=-11779.,1229

32、1.,-1023.k=10 err=6912.x=-26627.,27651.,-2047.k=11 err=15360.x=-59395.,61443.,-4095.k=12 err=33792.x=-131075.,135171.,-8191.k=13 err=73728.x=-286723.,294915.,-16383.k=14 err=159744.x=-622595.,638979.,-32767.k=15 err=344064.,.x=-8.050181016,8.10648 1015,-1.1259 1015 k=50 err=4.13768 1016通过观察迭代过程中的误差是

33、不断变大的特点可以知道本题的Seidel 迭代序列是不收敛的，因此，本题线性方程组不能用Seidel 迭代法求解。执行 Jacobi 迭代法程序后在输入的四个窗口中按提示分别输入:3、1,2,-2,1,1,1,2,2,1、1,1,1、0,0,0、0.0001 每次输入后用鼠标点击窗口的“OK”按扭，得如下输出结果：x=1.,1.,1.i=1 err=1.x=1.,-1.,-3.i=2 err=4.x=-3.,3.,1.i=3 err=4.x=-3.,3.,1.i=4 err=0 此结果说明迭代4 次，求得误差为err=0 的近似解，最后显示的近似解向量为x=-3.,3.,1.，与本题的准确解为

34、x1=-3.，x2=3.，x3=1.相同。本次实验说明Seidel 迭代与 Jacobi 迭代不是包含与被包含关系，Seidel 迭代不能取代Jacobi 迭代。2.5 思考与提高名师资料总结-精品资料欢迎下载-名师精心整理-第 15 页，共 17 页 -1.在例题中如果选用|x(k+1)-x(k)|1eps来控制迭代终止会出现什么情况？2.设 y(k+1)是利用 Seidel 迭代法由 x(k)算出的下一个向量，人们又构造出如下称为超松弛迭代格式（Sor 迭代格式）：x(k+1)=x(k)+x=x(k)+(y(k+1)x(k)=(1-)x(k)-y(k+1)其中称为松弛因子。研究由此编制程序

35、进行求解一个线性方程组的迭代计算情况，运算中要选用不同的松弛因子进行尝试。3在解线性方程组时，是否Seidel 迭代法总比Jacobi 迭代法收敛的快？4.分析 Jacobi 迭代法程序的编程优缺点，你能给出哪些改进？5.分析 Seidel 迭代法程序的编程优缺点，你能给出哪些改进？2.6 练习1 用 Seidel 迭代法求如下线性方程组的解要求误差|x(k+1)-x(k)|10-8。2 用 Jacobi 迭代法法解线性方程组3.用=1.25 和 0.5 的超松弛方法解线性方程组3322224343238243214225432154321543215422153321xxxxxxxxxxxxxxxxxxxxxxxxx1102151012402170183131204321xxxx02020202125454343232121xxxxxxxxxxxxx名师资料总结-精品资料欢迎下载-名师精心整理-第 16 页，共 17 页 -要求误差|x(k+1)-x(k)|10-8名师资料总结-精品资料欢迎下载-名师精心整理-第 17 页，共 17 页 -