《线性方程组求解》PPT课件.ppt

方程组求解,高斯消元法及算法实现初等变分原理最速下降法共轭梯度法,参考文献,1李庆扬关治白峰杉,数值计算原理(清华)2蔡大用白峰杉,现代科学计算3李庆扬等,数值分析4NumericalAnalysis(SeventhEdition)数值分析（第七版影印版）5DavidKincaid,数值分析(第三版)6JohnH.Mathews,数值方法(MATLAB版),线性方程组的矩阵形式,a11x1+a12x2+a1nxn=b1a21x1+a22x2+a2nxn=b2an1x1+an2x2+annxn=bn,AX=b,(i=1,2,n),线性方程组求解:1.直接方法;2.基本迭代法;3.子空间方法,X?b,解线性方程组的克莱姆方法1.输入矩阵A和右端向量b;,高斯消元法第一步:将方程组化简为三角形方程组;第二步:解三角形方程组,获方程组的解。,4.计算并输出x1=D1/D,xn=Dn/D,结束。,3.对k=1,2,n用b替换A的第k列数据,并计算替换后矩阵的行列式值Dk;,2.计算A的行列式D,如果D=0,则输出错信息结束,否则进行3;,增广矩阵,计算:m21m31m41T=a21a31a41T/a11,用m21乘矩阵第一行加到矩阵第二行;用m31乘矩阵第一行加到矩阵第三行;用m41乘矩阵第一行加到矩阵第四行;,实现第一轮消元,计算:m32m42T=,用m32乘矩阵第二行加到矩阵第三行;用m42乘矩阵第二行加到矩阵第四行;实现第二轮消元、第三轮消元,n阶方程组消元过程乘法次数:(n-1)n+(n-2)(n-1)+12=(n3-n)/3,除法次数:(n-1)+(n-2)+1=n(n-1)/2,上三角方程组,解上三角方程组,计算：xn=bn/ann,(a11ann0),xk=bk(ak,k+1xk+1+akn)/akk(k=n1,1),除法:n次;乘法:n(n-1)/2次,乘、除法运算共n(n+1)/2次,简记为O(n2),定义1设Rn是n维向量空间,如果对任意xRn,都有一个实数与之对应,且满足如下三个条件:,(1)正定性:|x|0,且|x|=0 x=0;,(2)齐次性:为任意实数,(3)三角不等式:(yRn),则称|x|为向量x的范数.,一、向量的范数,例3.范数意义下的单位向量:X=x1,x2T,二、矩阵的范数,定义2,例5,Frobenius范数,极小化方法,一、与线性方程组等价的变分问题,三、共轭梯度法(共轭斜量法),四、预条件共轭梯度法,二、最速下降法,设x,yRn,记(x,y)=xTy,(x,y)=(y,x);(tx,y)=t(x,y);(x+y,z)=(x,z)+(y,z);(x,x)0,且(x,x)=0x=0;,设A是n阶对称正定阵,(Ax,y)=(x,Ay);(Ax，x)0,且(Ax,x)=0x=0,一、与线性方程组等价的变分问题,定理1设A=(aij)nn为实对称正定矩阵,b,xRn,则x使二次函数,取极小值x是线性方程组Ax=b的解。,二、最速下降法,三、共轭梯度法(CG)(共轭斜量法),四、预条件共轭梯度法(PCG),预条件共轭梯度法,实际计算，可通过变换，转化成用原方程组的量来计算。,预条件共轭梯度法MATLAB的三种调用格式:1.不用预优矩阵的共轭梯度法x=pcg(a,b,tol,kmax)2.用预优矩阵的共轭梯度法(1)x=pcg(a,b,tol,kmax,m)(2)r=chol(m)x=pcg(a,b,tol,kmax,r,r,x0)3.未给定预优矩阵的共轭梯度法r=cholinc(sa,0)x=pcg(a,b,tol,kmax,r,r,x0),