《线性方程组求解.ppt》由会员分享，可在线阅读，更多相关《线性方程组求解.ppt（30页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、1方程组求解高斯消元法及算法实现高斯消元法及算法实现初等变分原理初等变分原理最速下降法最速下降法共轭梯度法共轭梯度法2参考文献参考文献1李庆扬李庆扬 关治关治 白峰杉白峰杉,数值计算原理数值计算原理(清华清华)2蔡大用蔡大用 白峰杉白峰杉,现代科学计算现代科学计算3 李庆扬李庆扬 等等,数值分析数值分析4Numerical Analysis (Seventh Edition)数值分析数值分析 （第七版（第七版 影印版）影印版）5David Kincaid,数值分析数值分析(第三版第三版)6 John H.Mathews,数值方法数值方法(MATLAB版版)3线性方程组的矩阵形式线性方程组的矩阵
2、形式a11x1+a12x2+a1nxn=b1a21x1+a22x2+a2nxn=b2an1x1+an2x2+annxn=bnA X=b(i=1,2,n)线性方程组求解线性方程组求解:1.直接方法直接方法;2.基本迭代法基本迭代法;3.子空间方法子空间方法X?b4解线性方程组的克莱姆方法解线性方程组的克莱姆方法1.输入矩阵输入矩阵 A 和右端向量和右端向量 b;高斯消元法高斯消元法第一步第一步:将方程组化简为三角形方程组将方程组化简为三角形方程组;第二步第二步:解三角形方程组解三角形方程组,获方程组的解。获方程组的解。4.计算并输出计算并输出 x1=D1/D,xn=Dn/D,结束结束。3.对对
3、k=1,2,n 用用 b 替换替换 A 的第的第 k 列数据列数据,并计算并计算替换后矩阵的行列式值替换后矩阵的行列式值 Dk;2.计算计算 A 的行列式的行列式 D,如果如果 D=0,则输出错信息结束则输出错信息结束,否则进行否则进行 3;5增广矩阵增广矩阵 计算计算:m21 m31 m41T=a21 a31 a41T/a11 用用m21乘矩阵第一行加到矩阵第二行乘矩阵第一行加到矩阵第二行;用用m31乘矩阵第一行加到矩阵第三行乘矩阵第一行加到矩阵第三行;用用m41乘矩阵第一行加到矩阵第四行乘矩阵第一行加到矩阵第四行;6实现第一轮消元实现第一轮消元计算计算:m32 m42T=用用m32乘矩阵第
4、二行加到矩阵第三行乘矩阵第二行加到矩阵第三行;用用m42乘矩阵第二行加到矩阵第四行乘矩阵第二行加到矩阵第四行;实现第二轮消元、第三轮消元实现第二轮消元、第三轮消元7n阶方程组消元过程乘法次数阶方程组消元过程乘法次数:(n-1)n+(n-2)(n-1)+12=(n3-n)/3除法次数除法次数:(n-1)+(n-2)+1=n(n-1)/2上三角方程组上三角方程组8解上三角方程组解上三角方程组计算计算：xn=bn/ann(a11ann0)xk=bk(ak,k+1xk+1+ak n)/ak k (k=n1,1)除法除法:n次次;乘法乘法:n(n-1)/2次次,乘、除法运算共乘、除法运算共 n(n+1)
5、/2 次次,简记为简记为 O(n2)9定义定义1 设设 Rn是是n维向量空间维向量空间,如果对任意如果对任意xRn,都有都有一个实数与之对应一个实数与之对应,且满足如下三个条件且满足如下三个条件:(1)正定性正定性:|x|0,且且|x|=0 x=0;(2)齐次性齐次性:为任意实数为任意实数(3)三角不等式三角不等式:(y Rn)则称则称|x|为向量为向量x的范数的范数.注注:向量范数是向量长度概念的推广向量范数是向量长度概念的推广.例如例如是向量是向量 x 的范数的范数。一、向量一、向量的的范数范数1011例例3.范数意义下的单位向量范数意义下的单位向量:X=x1,x2T11-1-1|X|2=
6、11-11|X|1=1-111-1-1|X|=112二、二、矩阵的范数矩阵的范数定义定义 2 2 13例例 5Frobenius范数范数14极小化方法极小化方法一、与线性方程组等价的变分问题一、与线性方程组等价的变分问题三、共轭梯度法三、共轭梯度法(共轭斜量法共轭斜量法)四、预条件共轭梯度法四、预条件共轭梯度法二、最速下降法二、最速下降法15设设x,yR n,记记 (x,y)=xT y(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
7、,且且(Ax,x)=0 x=0 一、与线性方程组等价的变分问题一、与线性方程组等价的变分问题1617定理定理1 1 设设A=(aij)nn为实为实对称正定矩阵对称正定矩阵,b,xR n,则则 x使二次使二次函数函数 取极小值取极小值 x 是线性方程组是线性方程组Ax=b 的解。的解。181920二、最速下降法二、最速下降法21222324三、共轭梯度法三、共轭梯度法三、共轭梯度法三、共轭梯度法(CG)(CG)(共轭共轭共轭共轭斜量斜量斜量斜量法法法法)25262728四、预条件共轭梯度法四、预条件共轭梯度法四、预条件共轭梯度法四、预条件共轭梯度法(PCG)(PCG)29预条件共轭梯度法预条件共轭梯度法 实际计算，可通过变实际计算，可通过变换，转化成用原方程组换，转化成用原方程组的量来计算。的量来计算。30预条件共轭梯度法预条件共轭梯度法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)