1-2 线性方程组求解.ppt

《1-2 线性方程组求解.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、方程组求解高斯消元法及算法实现初等变分原理最速下降法共轭梯度法参考文献[1]李庆扬关治白峰杉,数值计算原理(清华)[2]蔡大用白峰杉,现代科学计算[3]李庆扬等,数值分析[4]NumericalAnalysis(SeventhEdition)数值分析（第七版影印版）[5]DavidKincaid,数值分析(第三版)[6]JohnH.Mathews,数值方法(MATLAB版)线性方程组的矩阵形式a11x1+a12x2+····+a1nxn=b1a21x1+a22x2+····+a2nxn=b2·········································an1x

2、1+an2x2+····+annxn=bnAX=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;增广矩阵计算:[m21m31m41]T=[a21a31a41]T/a11用–m21乘矩阵第一行加

3、到矩阵第二行;用–m31乘矩阵第一行加到矩阵第三行;用–m41乘矩阵第一行加到矩阵第四行;实现第一轮消元计算:[m32m42]T=用–m32乘矩阵第二行加到矩阵第三行;用–m42乘矩阵第二行加到矩阵第四行;实现第二轮消元、第三轮消元·········n阶方程组消元过程乘法次数:(n-1)n+(n-2)(n-1)+…+1×2=(n3-n)/3除法次数:(n-1)+(n-2)+…+1=n(n-1)/2上三角方程组解上三角方程组计算：xn=bn/ann(a11…ann≠0)xk=[bk－(ak,k+1xk+1+…+akn)]/akk(k=n－1,···,1)除法:n次;乘法:n(n-1

4、)/2次,乘、除法运算共n(n+1)/2次,简记为O(n2)n23456高斯6173665106克莱姆851364288525206定义1设Rn是n维向量空间,如果对任意x∈Rn,都有一个实数与之对应,且满足如下三个条件:(1)正定性:

5、

6、x

7、

8、≥0,且

9、

10、x

11、

12、=0<=>x=0;(2)齐次性:λ为任意实数(3)三角不等式:(y∈Rn)则称

13、

14、x

15、

16、为向量x的范数.注:向量范数是向量长度概念的推广.例如是向量x的范数。一、向量的范数例3.范数意义下的单位向量:X=[x1,x2]T11-1-1

17、

18、X

19、

20、2=11-11

21、

22、X

23、

24、1=1-111-1-1

25、

26、X

27、

28、∞=1二、矩阵的范数定义

29、2例5Frobenius范数极小化方法一、与线性方程组等价的变分问题三、共轭梯度法(共轭斜量法)四、预条件共轭梯度法二、最速下降法设x,y∈Rn,记(x,y)=xTy(x,y)=(y,x);(tx,y)=t(x,y);(x+y,z)=(x,z)+(y,z);(x,x)≥0,且(x,x)=0x=0;设A是n阶对称正定阵(Ax,y)=(x,Ay);(Ax，x)≥0,且(Ax,x)=0x=0一、与线性方程组等价的变分问题定理1设A=(aij)n×n为实对称正定矩阵,b,x∈Rn,则x使二次函数取极小值x是线性方程组Ax=b的解。二、最速下降法三、共轭梯度法(CG)(共轭斜量法)四

30、、预条件共轭梯度法(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)