毕业答辩-关于方程Ax + d = λx的求解.ppt

浙江大学毕业论文,关于方程Ax+d=x的求解,答辩人：导师：专业：数学系信息与计算科学,论文框架,第1章绪论第2章相关理论基础第3章根据A矩阵的情况对问题的讨论第4章复杂度分析和数值例子第5章总结参考文献附录,第1章绪论,本文主要研究方程Ax+d=x的解，其中A是一个给定的n阶矩阵，且情况未知，d是一个给定的非零向量，所需要求解的未知量为向量x与一个数值，且向量x中满足x(n-1)=x(n)。如果把这个向量方程看做一个方程组并且把的x(n-1)=x(n)也看做一个方程的话，这个方程组一共有n+1个方程，n+1个未知量，但由于的存在，它并不是一个通常的线性方程。通过对给定但是不确定具体形式的A矩阵进行讨论，根据A矩阵的性质来解原方程。由于原方程的形式非常接近线性方程组，如果先确定或者固定了的值，那么，来解这个方程剩余的x的值就很方便了。为了体现在方程中的意义，我将原方程变形为(*)(-A)x=d这个形式很容易让我们想到最后的解x与的值，是否会与A矩阵的特征值和特征向量有关联。,第2章相关理论基础,线性方程相关理论线性方程组的解法（直接法、迭代法）特征值和特征向量相关理论矩阵的相似与相似对角化矩阵特征值的计算方法牛顿法等数值算法,第3章根据A矩阵的情况对问题的讨论,当A矩阵是对角阵的情况,若A矩阵是一个对角阵，那么我们不妨设对角线上的元素为a1,a2an-1,an。那么(*)就可以转化为n个非常简单的方程：(ak)xk=dk,k=1,2,n-1,n。然后利用x(n-1)=x(n)这个条件，我们先分析(an-1)xn-1=dn-1和(an)xn=dn这最后的两个式子，不妨令x=xn-1=xn，那么这两个方程可以重写作：(an-1)x=dn-1(-an)x=dn这是个二元方程组，而这个方程里面和x的解的情况（是否有解，有解的话是唯一解还是无穷多解）和系数an-1,an,dn-1,dn有相当大的关系。我们只要分情况讨论就可以了。分类情况步骤：（1）dn-10，dn0。如果dn-1和dn不相等，那么=(an-1*dn-an*dn-1)/(dn-dn-1)。如果dn-1和dn相等，那就看一下an-1和an的情况：如果an-1和an不相等，那么就一定无解了；如果an-1和an相等，那么就相当于这两个方程其实是一个方程，我们只要找出和前n-1个ak不相等的即可。,第3章根据A矩阵的情况对问题的讨论,当A矩阵是对角阵的情况,（2）dn-1=0，dn0。由于dn0，所以x一定不能等于0，而dn-1=0，则只能让取an-1的值了。（3）dn-10，dn=0。类似于（2）的情况只能取=an。（4）dn-1=0，dn=0。那么就找出和前n-2个ak不相等的即可。这样，只要求出了的值（或者已经判断无解），那么求x的值就非常方便了，只需要把求出的值分别代入方程(ak)xk=dk，就可以解出xk,k=1,.,n了。而且由于是利用x(n-1)=x(n)的性质求出来的，所以这也就保证了解出来的xk,k=1,.,n里面一定是满足x(n-1)=x(n)的。这样，对于A矩阵是对角阵的情况我们就完美解决了。,第3章根据A矩阵的情况对问题的讨论,当A矩阵是上三角矩阵的情况,我们假定A=ai,ji,j=1,n，且当ij时，ai,j=0。让我们写出方程组的一般表达形式为：xiai,jxj=di,i=1,n。然后我们看当i=n-1和i=n时的两项，分别为：xn-1an-1,n-1xn-1an-1,nxn=dn-1xnan,nxn=dn令xn-1=xn=x，并且重新整理上述两项可以得到：(an-1,n-1an-1,n)x=dn-1(an,n)x=dn那么，我们很容易的得到了和我们在讨论A矩阵是对角阵的时候产生的非常相似的两个方程，那么类似的，我们利用相同的分类讨论方法就可以求出或者判断方程是否是无解的了，这里就不重复叙述了。,第3章根据A矩阵的情况对问题的讨论,当A矩阵是实对称矩阵的情况,当A是实对称矩阵的时候，我们再去写出具体方程组然后考察性质似乎遇到了一点麻烦。那么我们可以利用A可以相似对角化成一个实对角阵的性质来帮助我们解决问题。即，对于实对称矩阵A，一定可以找到一个酉矩阵P，以及一个实对角阵，满足A=PPT。那么利用这个有利条件，我们可以把方程(*)改写为(*)(PPT)x=d=P(-)PTx=d对于这个形式，我们再细分两种情况：(1)取的对角线上的元素即k。对于这种情况，相当只要我们把A的所有特征值取出来，然后一一带入判断k是否是我们需要的就可以了。由于=k，所以(-A)矩阵一定是奇异矩阵，那么(*)的解要么是无解，要么就是无穷多解。如果是无穷多解的话，我们就只要在无穷多解的形式中要求x(n-1)=x(n)就可以了。对于这种情况，我们先判断rank(-A)是否和rank(A,d)相等，如果不相等，那么就是无解；如果相等，那么一定有无穷多解。然后设无穷多解中的自由变量为ti，自由变量的个数r等于nrank(-A)0。那么不妨令x(n-1)=,第3章根据A矩阵的情况对问题的讨论,当A矩阵是实对称矩阵的情况,p0+(pi*ti),x(n)=q0+(qi*ti)。x(n-1)x(n)=(p0q0)+(pi-qi)*ti。对于这个式子，我们可以得知，如果p0q0=0，那么令所有的ti都等于0即可；如果p0q00，那么，如果至少存在一组piqi0，那么我们可以控制那个ti的值使得最后总的x(n-1)x(n)=0，反之，如果所有的piqi都为0，那么就无解了。当然，还有一种思路就是把x(n-1)=x(n)当作一个方程添加到方程组里面，那么可以得到一个新的n+1行n列的矩阵U，和一个新的n+1维列向量D，通过判断rank(U)和rank(U,D)是否相等来判断方程是否存在我们需要的解，如果存在，那么就一定是满足x(n-1)=x(n)的。(2)不取的对角线上的元素即k。这就保证了(-)矩阵一定是可逆的，显然其逆矩阵上也是一个对角阵。那么P(-)PTx=d可以变形为(*)x=P(-)-1PTd由于P和是可求的，那么我们不妨令P=pi.ji,j=1,n和()-1对角线上,第3章根据A矩阵的情况对问题的讨论,当A矩阵是实对称矩阵的情况,的值为(k)-1,k=1,n。那么我们甚至可以直接把x(i)的具体表达式写出来：x(i)=(pi,k*pj,k/(-k)*dj然后利用x(n-1)=x(n)这个条件，可以得到：(pn,k*pj,k/(-k)*dj=(pn-1,k*pj,k/(-k)*dj然后对上式进行整理：(pn,kpn-1,k)*pj,k/(-k)*dj=0在对进行整理就可以得到一个关于的方程：f()=(k/(k)=0,k=(pn,kpn-1,k)(pj,k*dj)这个方程的的值，我们可以利用一些数值方法，例如牛顿法来求，只需要给出一个0k的初值就可以了。那么，我们就把的值给确定下来了。需要提出的是，如果直接对f()=0作牛顿迭代的话，是会有很大的麻烦的。因为由于不能取k值，那么就相当于在x方向上给挖了最多有n个坑，或者说是由这n,第3章根据A矩阵的情况对问题的讨论,当A矩阵是实对称矩阵的情况,个坑把f()的零点隔开了（当然不一定保证两个相邻的k之间有零点）。而我们知道，牛顿迭代法对初值是有一定的依赖性的，所以，初值0被夹在某两个k之间，而这两个k之间如果没有零点的话，那么这个迭代法就不会收敛了！所以我们要将f()做稍微的变化。最显而易见的方法就是给f()乘上一个多项式，例如可以令g()=f()*()，其中()=(k)。由于不能取k，那么就保证了()是非零的。同时，g()的导数也非常容易求。那么，我们就可以比较放心的取0的初值了。以上两种情况的关键都是在于对于实对称的矩阵A，首先要求出A的特征值，并且对于第二种情况，我们还要求出对应的酉矩阵P。对于实对称矩阵求特征值和特征向量的方法，我们已经在上文中提及了。所以，我们只需要在这些方法中选取我们所需要的方法（比如可以使用Jacobi迭代法来求出特征值和特征向量）就可以了。那么，对于A矩阵是实对称的情况，我们也就解决了。,第3章根据A矩阵的情况对问题的讨论,当A矩阵是实矩阵的情况,当A矩阵是实矩阵的时候，一个简单的想法也是对方程进行相似对角化，不过是在复数域上的相似对角化，即A=PQ，其中P,QCnn，PQ=I。那么(*)可以整理为：(*)P(-)Qx=d同对(*)的处理办法，我们依然分两种情况讨论，即：(1)取的对角线上的元素即k。这种情况和A是实对称矩阵的时候几乎是完全相同的，只是解方程的时候是在复数域上。(2)不取的对角线上的元素即k。对于这种情况，我们要重新更新x(i)的表达式，即写出x=P(-)-1Qd中x的具体形式。这里，不妨令P=pi.ji,j=1,n；Q=qi.ji,j=1,n和()-1对角线上的值为(-k)-1,k=1,n。类似于实对,第3章根据A矩阵的情况对问题的讨论,当A矩阵是实矩阵的情况,称的(2)情况，可以得到：x(i)=(pi,k*qk,j/(-k)*dj然后同理，利用x(n-1)=x(n)这个条件，并整理可以得到只关于的方程：f()=(k/(-k)=0,k=(pn,kpn-1,k)(qk,j*dj)那么，同理，我们类似的对f()构造出g()=f()*()，然后再在复数域上利用牛顿法就可以求出的值了，当然，最后求出的也有可能是实数值的。A矩阵是实矩阵的情况和A矩阵是实对称的时候我们处理办法似乎是非常相同的，不过最大的区别就是在于A矩阵是实对称的时候，我们需要的是一个酉矩阵P，而A是一般的实矩阵的时候我们需要A矩阵在复数域上的用来作相似对角化矩阵的矩阵P和Q，并满足PQ=I。而要求出P以及它的逆矩阵Q的代价似乎会比较大一些。,第4章复杂度分析和数值例子,对于A矩阵是对角阵的算法的复杂度分析显然，由于A矩阵是对角阵，那么我们在上文中提及的算法在时间和空间复杂度上都是O(n)的。对于A矩阵是上三角矩阵的算法的复杂度分析由于A矩阵是上三角矩阵采用的算法和A矩阵是对角阵时基本相同，那么此时的时间和空间复杂度都是O(n2)即读入数据的复杂度。,第4章复杂度分析和数值例子,对于A矩阵是实对称矩阵的算法的复杂度分析对于A矩阵是实对称矩阵的情况。我采用的算法是先对A矩阵用Jacobi方法计算出A矩阵的特征值和特征向量组成的酉矩阵，时间复杂度单次处理是O(n)，对于非对角元要消一次0，所以相当于要做O(n2)次，那么总体复杂度是O(n3)。对于取A特征值的情况就直接带入(*)式中判断并求解x的值，单个特征值的复杂度为O(n3)，所以对于最多n个特征值，时间复杂度会达到O(n4)；对于不取A特征值的情况，利用推导出的g()函数使用牛顿迭代法求出一个零点,牛顿迭代法迭代一次需要计算g()相关的函数，其时间复杂度为O(n),然后迭代次数为k（k的大小和精度相关），所以总体时间复杂度是O(n*k)。然后再将求出的回代到(*)式中来计算出x的值，因为这样做的复杂度仅仅是O(n2)的。所以总体的时间复杂度是O(n4+n*k)，而空间复杂依然是O(n2)。,第4章复杂度分析和数值例子,对于A矩阵是实矩阵的算法的复杂度分析A矩阵是实矩阵的算法和A矩阵是实对称时的算法类似，不同点在于前期求A矩阵的特征值、特征向量组成的矩阵P和P矩阵的逆的效率和A矩阵是实对称时是不同的。我使用了QR方法来求特征值和特征向量（也可以用matlab的eig函数代替）。而求P矩阵的逆也没有非常好的办法，只能使用比较暴力的解方程的办法（对P做LU分解，然后求Pqk=ek的qk向量，其中ek为只在k位置是1其他位置都是0的列向量），时间复杂度为O(n3)（也可以用matlab的inv函数代替）。后面部分依然是分为取A矩阵的特征值和不取特征值两种情况，那么总体的时间爱你复杂度依然是O(n4+n*k)，空间复杂度也是O(n2)。,第4章复杂度分析和数值例子,对于A矩阵是对角阵时的数值例子例如令n=10运行DataMaker(Diag,input.txt,n);生成数据运行MainFunc(input.txt);生成结果,第4章复杂度分析和数值例子,对于A矩阵是上三角矩阵时的数值例子例如令n=10运行DataMaker(UTM,input.txt,n);生成数据运行MainFunc(input.txt);生成结果,第4章复杂度分析和数值例子,对于A矩阵是实对称矩阵时的数值例子例如令n=10运行DataMaker(RSM,input.txt,n);生成数据运行MainFunc(input.txt);生成结果,第4章复杂度分析和数值例子,对于A矩阵是实矩阵时的数值例子例如令n=10运行DataMaker(Normal,input.txt,n);生成数据运行MainFunc(input.txt);生成结果,第5章总结,先说一下总体的认识，通过对Ax+d=x这个方程的研究，我对线性方程、矩阵的特征值、特征向量以及一些数值线性代数的算法有了更进一步的认识和了解。对于解决一个一般性的问题也有了系统的认识。同时，在研究问题的过程中，对于查阅文献，使用matlab等都变得比较熟练了。再说一下关于研究的问题。这个方程从外观上来看就是一个非常简洁的方程，虽然不是简单的线性方程，但是与线性方程的形式非常类似。在研究这个问题的过程中，我主要把握住了两点：1、抓住主要变量，控制次要变量。由于方程中同时存在一维变量和向量变量x，我通过对方程的观察，发现是主要变量，只要能够找出合适的，那么x是很容易就能求解的。反之，如果我先去搜寻x，再去确定的话，势必就比较困难了；2、对于未知的矩阵A进行分类递进式的研究。方程中是一个数，x和d都是n维向量，而唯有A是一个矩阵，而且是一个并不清楚类型的矩阵。那么，一下子就让我思考任意的矩阵A这个问题就变得似乎无从下手。所以，我就考虑先将A的形式简单化，从而简单化整个问题来思考，然后递进式的逐渐加强A的形式，从而解决整个问题。事实上，这个问题也确实随着我将A从对角阵、上三角矩阵一直到实对称矩阵、实矩阵一步一步，一个类型一个类型的解决掉了。,附：代码清单,DataMaker.m：用来生成实验用的数据，根据输入的矩阵类型（对角、上三角、实对称、实矩阵）以及一个矩阵阶数n来生成随机矩阵A、随机的值和x值，并且保证x(n-1)=x(n)，然后利用这些数据生成向量d。当然，由于方程可能有多个解，通过此程序生成的值和x值不一定是原方程的唯一解。DoubleStepQR.m：双重歩位移QR迭代法。eig2.m：计算22矩阵的特征值。FindAllEIGs.m：找出Hessenberg矩阵的所有特征值。HessenbergResolve.m：对实矩阵做Hessenberg分解。house.m：Householder变换。JacobiMethod.m：求实对称矩阵特征值和特征向量的Jacobi方法。MainFunc.m：主程序。NewtonMethod.m：求解方程ak/(-bk)=0(k=1,.,n)的牛顿法，返回一个值。SolveDiagType.m：解A矩阵是对角阵的原方程的算法。SolveDiagTypeSpl.m：找一个非k的实值的方法。SolveNormal.m：求解A矩阵是一般实矩阵的原方程的算法。SolveRSM.m：求解A矩阵是实对称矩阵的原方程的算法。SolveSingularType.m：求解奇异矩阵的线性方程的解。SolveUTM.m：求解A矩阵是上三角矩阵的原方程的算法。,感谢各位老师的指导！,n=10A=0.8147240.0000000.0000000.0000000.0000000.0000000.0000000.0000000.0000000.0000000.0000000.9705930.0000000.0000000.0000000.0000000.0000000.0000000.0000000.0000000.0000000.0000000.8491290.0000000.0000000.0000000.0000000.0000000.0000000.0000000.0000000.0000000.0000000.0461710.0000000.0000000.0000000.0000000.0000000.0000000.0000000.0000000.0000000.0000000.1868730.0000000.0000000.0000000.0000000.0000000.0000000.0000000.0000000.0000000.0000000.4983640.0000000.0000000.0000000.0000000.0000000.0000000.0000000.0000000.0000000.0000000.5472160.0000000.0000000.0000000.0000000.0000000.0000000.0000000.0000000.0000000.0000000.2510840.0000000.0000000.0000000.0000000.0000000.0000000.0000000.0000000.0000000.0000000.3804460.0000000.0000000.0000000.0000000.0000000.0000000.0000000.0000000.0000000.0000000.337123d=-0.518304-0.251589-0.3630740.019217-0.014863-0.088406-0.251842-0.061272-0.163294-0.130882,返回,A矩阵形如对角阵有解limda=0.1622x=0.79430.31120.52850.16560.60200.26300.65410.68920.74810.7481,返回,n=10A=0.0838210.9618980.9106480.6220550.0496540.3897390.3531590.2963210.7757130.3786090.0000000.0046340.1818470.3509520.9027160.2416910.8211940.7446930.4867920.8115800.0000000.0000000.2638030.5132500.9447870.4039120.0154030.1889550.4358590.5328260.0000000.0000000.0000000.4018080.4908640.0964550.0430240.6867750.4467840.3507270.0000000.0000000.0000000.0000000.4892530.1319730.1689900.1835110.3063490.9390020.0000000.0000000.0000000.0000000.0000000.9420510.6491150.3684850.5085090.8759430.0000000.0000000.0000000.0000000.0000000.0000000.7317220.6256190.5107720.5501560.0000000.0000000.0000000.0000000.0000000.0000000.0000000.7802270.8176280.6224750.0000000.0000000.0000000.0000000.0000000.0000000.0000000.0000000.7948310.5870450.0000000.0000000.0000000.0000000.0000000.0000000.0000000.0000000.0000000.207742d=-1.655708-1.314069-0.737942-0.704078-0.570864-0.848425-0.700642-0.656711-0.3361860.029089,返回,A矩阵形如上三角矩阵有解limda=0.3012x=0.46920.23030.84410.19470.22590.17070.22770.43570.31110.3111,返回,n=10A=0.4302070.6028430.8010150.5211360.9132870.4941740.5000220.8865120.0424310.9729750.6028430.7112160.0292200.2315940.7961840.7790520.4799220.0286740.0714450.6489910.8010150.0292200.9288540.4888980.0987120.7150370.9047220.4899010.5216500.8003310.5211360.2315940.4888980.6240600.2618710.9037210.6098670.1679270.0967300.4537980.9132870.7961840.0987120.2618710.3353570.8909230.6176660.9786810.8181490.4323920.4941740.7790520.7150370.9037210.8909230.3341630.8594420.7126940.8175470.8253140.5000220.4799220.9047220.6098670.6176660.8594420.8054890.5004720.7224400.0834700.8865120.0286740.4899010.1679270.9786810.7126940.5004720.4710880.1498650.1331710.0424310.0714450.5216500.0967300.8181490.8175470.7224400.1498650.6596050.1733890.9729750.6489910.8003310.4537980.4323920.8253140.0834700.1331710.1733890.390938d=-2.024962-2.075029-2.734421-1.891045-2.551137-2.707424-2.412982-2.205310-1.673791-2.077894,返回,A矩阵形如实对称矩阵JacobiMethodRunTimes=23奇异情况，取为A矩阵的特征值：=-1.205402无解=5.537017无解=1.093153无解=0.142588无解=-1.086903无解=-0.456063无解=-0.745843无解=0.785018无解=1.220649无解=0.406762无解,非奇异情况，取不为A矩阵的特征值：NewtonMethodRunTimes=22有解limda=0.8314x=0.80340.06050.39930.52690.41680.65690.62800.29200.43170.4317,返回,n=10A=0.9840640.7378580.5391260.6691750.4282530.2652810.2607280.4709240.8199810.266471