线性代数方程组的数值解法ne.ppt
《线性代数方程组的数值解法ne.ppt》由会员分享,可在线阅读,更多相关《线性代数方程组的数值解法ne.ppt(162页珍藏版)》请在淘文阁 - 分享文档赚钱的网站上搜索。
1、上页上页下页下页第第3章章 线性方程组的数值解法线性方程组的数值解法3.1 引言与预备知识引言与预备知识3.2 高斯消去法高斯消去法3.3矩阵三角分解法矩阵三角分解法3.4向量和矩阵的范数误差分析向量和矩阵的范数误差分析3.5迭代方法迭代方法上页上页下页下页 这一章讨论线性方程组这一章讨论线性方程组3.1 引言与预备知识引言与预备知识的数值解法的数值解法.上页上页下页下页 在自然科学和工程技术中在自然科学和工程技术中,很多问题归结为很多问题归结为解解线性方程组线性方程组.例如电学中的网络问题,船体数学放例如电学中的网络问题,船体数学放样中建立三次样条函数问题,用最小二乘法求实验样中建立三次样条
2、函数问题,用最小二乘法求实验数据的曲线拟合问题,解非线性方程组问题,用差数据的曲线拟合问题,解非线性方程组问题,用差分法或者有限元方法解常微分方程、偏微分方程边分法或者有限元方法解常微分方程、偏微分方程边值问题等都导致求解线性方程组,而这些值问题等都导致求解线性方程组,而这些方程组的方程组的系数矩阵大致分为两种系数矩阵大致分为两种,一种是低阶稠密矩阵一种是低阶稠密矩阵(例例如,阶数不超过如,阶数不超过150).150).另另一种是大型稀疏矩阵一种是大型稀疏矩阵(即即矩阵阶数高且零元素较多矩阵阶数高且零元素较多).).3.1.1 引言引言上页上页下页下页 有有的的问问题题的的数数学学模模型型中中
3、虽虽不不直直接接表表现现为为含含线线性性方方程程组组,但但它它的的数数值值解解法法中中将将问问题题“离离散散化化”或或“线线性性化化”为为线线性性方方程程组组.因因此此线线性性方方程程组组的的求求解解是是数值分析课程中最基本的内容之一数值分析课程中最基本的内容之一.关于线性方程组的解法一般有两大类:关于线性方程组的解法一般有两大类:上页上页下页下页 但但实实际际计计算算中中由由于于舍舍入入误误差差的的存存在在和和影影响响,这这种种方方法法也也只只能能求求得得线线性性方方程程组组的的近近似似解解.本本章章将将阐阐述述这这类类算算法法中中最最基基本本的的和和具具有有代代表表性性的的算算法法就就是是
4、高高斯斯消消元元法法,以以及及它它的的某某些些变变形形和和应应用用.这这类类方方法法是是解解低低阶阶稠稠密密矩矩阵阵方方程程组组及及某某些些大大型型稀稀疏疏矩矩阵阵方方程程组组(例例如,大型带状方程组如,大型带状方程组)的有效方法的有效方法.1.直接法直接法 经经过过有有限限次次的的算算术术运运算算,可可以以求求得得方方程程组组的的精精确确解解(假假定定计计算算过过程程没没有有舍舍入入误误差差).).如如线线性性代代数数课课程程中中提提到到的的克克莱莱姆姆算算法法就就是是一一种种直直接接法法.但但该该法法对对高高阶阶方方程组计算量太大程组计算量太大,不是一种实用的算法不是一种实用的算法.上页上
5、页下页下页 就就是是用用某某种种极极限限过过程程去去逐逐步步逼逼近近方方程程组组精精确确解解的的方方法法.迭迭代代法法具具有有计计算算机机的的存存储储单单元元较较少少、程程序序设设计计简简单单、原原始始系系数数矩矩阵阵在在计计算算过过程程中中始始终终不不变变等等优优点点,但但存存在在收收敛敛条条件件和和收收敛敛速速度度问问题题.迭迭代代法法是是解解大大型型稀稀疏疏矩矩阵阵方方程程组组(尤尤其其是是由由微微分分方方程程离离散散后后得得到到的的大大型型方程组方程组)的重要方法的重要方法.为为了了讨讨论论线线性性方方程程组组数数值值解解法法,需需复复习习一一些些基基本本的矩阵代数知识的矩阵代数知识.
6、2.迭代法迭代法上页上页下页下页3.1.2 向量和矩阵向量和矩阵 基本概念基本概念:用用Rmn表示全部表示全部mn实矩阵的向量空间;实矩阵的向量空间;用用Cmn表示全部表示全部mn复矩阵的向量空间复矩阵的向量空间.(由数排成的矩阵表,称为由数排成的矩阵表,称为m行行n列矩阵列矩阵).上页上页下页下页其中其中aj为为A的第的第j列的列的m维列向量维列向量.同理同理(m维列向量维列向量).其中其中biT为为A的第的第i行的行的n维行向量维行向量.上页上页下页下页 矩阵的基本运算矩阵的基本运算:(1)矩阵加法矩阵加法 (2)矩阵与标量的乘法矩阵与标量的乘法 (3)矩阵与矩阵的乘法矩阵与矩阵的乘法 (
7、4)转置矩阵转置矩阵上页上页下页下页 (5)单位矩阵单位矩阵其中其中 (6)非奇异矩阵非奇异矩阵则称则称B是是A的逆矩阵,记为的逆矩阵,记为A-1,且,且(A-1)T=(AT)-1.如如果果A-1存在,则存在,则A称为非奇异矩阵称为非奇异矩阵.如果如果A、B均为非均为非奇异矩阵,则有奇异矩阵,则有(AB)-1=B-1A-1.上页上页下页下页 (7)矩阵的行列式矩阵的行列式 设设ARnn,则,则A的行列式可按任一行的行列式可按任一行(列列)展开展开,其中其中Aij为为aij的代数余子式,的代数余子式,Aij=(-1)i+jMij,Mij为元素为元素aij的余子式的余子式.行列式性质行列式性质:上
8、页上页下页下页 定理定理1 设设ARnn,则下述命题等价:,则下述命题等价:(1)对任何对任何bRn,方程组,方程组Ax=b有唯一解有唯一解.(2)齐次方程组齐次方程组Ax=0只有唯一解零解只有唯一解零解x=0.(3)det(A)0.(4)A-1存在存在.上页上页下页下页3.2 高斯消去法高斯消去法 本本节节介介绍绍高高斯斯消消去去法法(逐逐次次消消去去法法)及及消消去去法法和和矩矩阵阵三三角角分分解解之之间间的的关关系系.虽虽然然高高斯斯消消去去法法是是一一种种古古老老的的求求解解线线性性方方程程组组的的方方法法(早早在在公公元元前前250250年年我我国国就就掌掌握握了了解解方方程程组组的
9、的消消去去法法),但但由由它它改改进进、变变形形得得到到的的选选主主元元素素消消去去法法、三三角角分分解解法法仍仍然然是是目目前前计计算算机机上上常常用用的的有有效效方方法法.我我们们在在中中学学学学过过消消去去法法,高高斯斯消消去去法法就就是是它它的的标标准准化化的的、适适合合在在计计算算机机上上自自动计算的一种方法动计算的一种方法.上页上页下页下页3.2.1 高斯消去法高斯消去法 设有线性方程组设有线性方程组或写成矩阵形式或写成矩阵形式简记为简记为Ax=b.上页上页下页下页如如:上三角矩上三角矩阵阵所对应所对应的线性方的线性方程组程组解为解为 当当m=n时,对时,对三角形方程组三角形方程组
10、的解非常容易,如的解非常容易,如上页上页下页下页例如例如:上页上页下页下页下三角矩阵下三角矩阵所对所对应的线性方程组应的线性方程组计算量(乘除法的主要部分)都为计算量(乘除法的主要部分)都为 n2/2.解为解为 因此,我们将一般的线性方程组化成等价的三因此,我们将一般的线性方程组化成等价的三角形方程组来求解角形方程组来求解.上页上页下页下页 首先举一个简单的例子来说明消去法的基本思想首先举一个简单的例子来说明消去法的基本思想.例例1 用消去法解方程组用消去法解方程组 解解 第第1步,将方程步,将方程(2.2)乘上乘上-2加到方程加到方程(2.4)上上去,消去去,消去(2.4)中的未知数中的未知
11、数x1,得到,得到 第第2步,将方程步,将方程(2.3)加到方程加到方程(2.5)上去,消去上去,消去(2.5)中的未知数中的未知数x2,得到与原方程组等价的三角形方,得到与原方程组等价的三角形方程组程组上页上页下页下页显然,方程组是显然,方程组是(2.6)是容易求解的,解为是容易求解的,解为 上述过程相当于对方程的上述过程相当于对方程的增广阵做初等行变换增广阵做初等行变换其中其中ri用表示矩阵的第用表示矩阵的第i行行.上页上页下页下页 由此看出,用消去法解方程组的由此看出,用消去法解方程组的基本思想基本思想是用是用逐次消去未知数的方法把原方程组逐次消去未知数的方法把原方程组Ax=b化为与其等
12、化为与其等价的三角形方程组,而求解三角形方程组可用回代价的三角形方程组,而求解三角形方程组可用回代的方法求解的方法求解.换句话说,上述过程就是用初等行变换换句话说,上述过程就是用初等行变换将原方程组系数矩阵化为简单形式将原方程组系数矩阵化为简单形式(上三角矩阵上三角矩阵),从,从而求解原方程组而求解原方程组(2.1)的问题转化为求解简单方程组的问题转化为求解简单方程组的问题的问题.或者说,对系数矩阵或者说,对系数矩阵A施行一些行变换施行一些行变换(用一用一些简单矩阵左乘些简单矩阵左乘A)将其约化为上三角矩阵将其约化为上三角矩阵.这就是这就是高高斯消去法斯消去法.上页上页下页下页 下面讨论求解一
13、般线性方程组的高斯消去法下面讨论求解一般线性方程组的高斯消去法.由由上页上页下页下页 将将(2.1)记为记为A(1)x=b(1),其中,其中上页上页下页下页 (1)第第1步步(k=1).设设a11(1)0,首先计算,首先计算乘数乘数 mi1=ai1(1)/a11(1)(i=2,3,m).用用-mi1乘乘(2.1)的第一个方程,加到第的第一个方程,加到第i个个(i=2,3,m)方程上,消去方程上,消去(2.1)的从第二个方程到第的从第二个方程到第m个方程中的个方程中的未知数未知数x1,得到与,得到与(2.1)等价的方程组等价的方程组(2.7)上页上页下页下页简记为简记为 A(2)x=b(2),其
14、中其中A(2),b(2)的元素计算公式为的元素计算公式为 (2)第第k次消元次消元(k=1,2,s,s=min(m-1,n).设上述第设上述第1步,步,第,第k-1步消元过程计算已经完步消元过程计算已经完成,即已计算好与成,即已计算好与(2.1)等价的方程组,简记为等价的方程组,简记为A(k)x=b(k),其中,其中上页上页下页下页 设设akk(k)0,计算,计算乘数乘数 mik=aik(k)/akk(k)(i=k+1,m).用用-mik乘乘(2.8)的第的第k个方程加到第个方程加到第 i个个(i=k+1,m)方方程上,消去从第程上,消去从第k+1个方程到第个方程到第m个方程中的未知数个方程中
15、的未知数xk,得到与,得到与(2.1)等价的方程组等价的方程组A(k+1)x=b(k+1),上页上页下页下页其中其中A(k+1),b(k+1)的元素计算公式为,的元素计算公式为,显然显然A(k+1)中从第中从第1行到第行到第k行与行与A(k)相同相同.(3)继续上述过程,且设继续上述过程,且设aii(i)0(i=1,2,s),直到,直到完成第完成第s步消元计算步消元计算.最后得到与原方程组等价的简最后得到与原方程组等价的简单方程组单方程组A(s+1)x=b(s+1),其中,其中A(s+1)为上阶梯为上阶梯.上页上页下页下页 特别当特别当m=n时,时,与原方程组等价的简单方程组为与原方程组等价的
16、简单方程组为A(n)x=b(n),即,即由由(2.1)约化为约化为(2.10)的过程称为的过程称为消元过程消元过程.如果如果A是非奇异矩阵,且是非奇异矩阵,且akk(k)0(k=1,2,n-1),求解三角形方程组求解三角形方程组(2.10),得到求解公式,得到求解公式(2.10)的求解过程的求解过程(2.11)称为称为回代过程回代过程.上页上页下页下页 注意:设注意:设Ax=b,其中,其中ARnn为非奇异矩阵,如为非奇异矩阵,如果果a11(1)=0,由于,由于A为非奇异矩阵,所以为非奇异矩阵,所以A的第的第1列一定列一定有元素不等于零,例如有元素不等于零,例如al1 0,于是可交换两行元素,于
17、是可交换两行元素(即即r1rl),将,将al1 调到调到(1,1)位置,然后进行消元计算,位置,然后进行消元计算,这时这时A(2)右下角矩阵为右下角矩阵为n-1阶非奇异矩阵,继续这过程,阶非奇异矩阵,继续这过程,高斯消去法照样可进行计算高斯消去法照样可进行计算.总结上述讨论即有总结上述讨论即有上页上页下页下页 定理定理5 设设Ax=b,其中,其中ARnn.(1)如果如果akk(k)0(k=1,2,n),则可通过高斯消去,则可通过高斯消去法将法将Ax=b约化为等价的三角形方程组约化为等价的三角形方程组(2.10),且计算,且计算公式为公式为 (a)消元计算消元计算(k=1,2,n-1)上页上页下
18、页下页 (b)回代计算回代计算 (2)如果如果A为非奇异矩阵,则可通过高斯消去法为非奇异矩阵,则可通过高斯消去法(及交换两行的初等变换及交换两行的初等变换)将方程组将方程组Ax=b约化为等价的约化为等价的三角形方程组三角形方程组(2.10).上页上页下页下页例例2 2 解方程组解方程组解解:消元:消元回代得回代得上页上页下页下页习题:求解下列方程组,(1)(2)上页上页下页下页3.2.2 高斯主元素消元法高斯主元素消元法 由高斯消去法知道由高斯消去法知道,在消元过程中可能有在消元过程中可能有akk(k)0的情况,这时消去法将无法进行;即使主元素的情况,这时消去法将无法进行;即使主元素akk(k
19、)0但很小时,用其作除数,会导致其它元素数量级的严但很小时,用其作除数,会导致其它元素数量级的严重增长和舍入误差的扩散,最后也使得计算解不可靠重增长和舍入误差的扩散,最后也使得计算解不可靠.先看一个例子先看一个例子 高斯消去法也称高斯消去法也称主元素消去法主元素消去法(条件条件det A 0)即即当当akk(k)=0 时,高斯消元法时,高斯消元法无法进行无法进行;或;或|akk(k)|0(i=1,2,n).由矩阵乘法及由矩阵乘法及ljk=0(当当j1时时,aij=0,且且满足如下的对角占优条件满足如下的对角占优条件满足如下的对角占优条件满足如下的对角占优条件:(a)|b1|c1|0;(b)|b
20、i|ai|+|ci|,ai,ci0,(i=2,3,n-1).(c)|bn|an|0.我们利用矩阵的直接三角分解法来推导解三对我们利用矩阵的直接三角分解法来推导解三对角线方程组角线方程组(4.12)的计算公式的计算公式.由系数阵由系数阵A的特点,的特点,可以将可以将A分解为两个三角矩阵的乘积,即分解为两个三角矩阵的乘积,即A=LU,其中取其中取L下三角阵下三角阵,取取U为单位上三角阵为单位上三角阵,这样求解这样求解方程组方程组Ax=f的方法称为的方法称为追赶法追赶法.设设上页上页下页下页其中其中 为待定系数,比较为待定系数,比较(4.13)两边即得两边即得 上页上页下页下页 求解求解Ax=f等价
21、于求解两个三角形方程组等价于求解两个三角形方程组.(1)Ly=f,求求y;(2)Ux=y,求求x.从而得到解三对角线方程组的追赶法从而得到解三对角线方程组的追赶法.上页上页下页下页 我们将计算系数我们将计算系数 及及 的过程称为的过程称为追的过程追的过程,将计算方程组的解将计算方程组的解 的过程称为的过程称为赶的过程赶的过程.合起来就是合起来就是追赶法追赶法.追赶法公式实际上就是把高斯消去法用到求解追赶法公式实际上就是把高斯消去法用到求解三对角线方程组上去的结果三对角线方程组上去的结果.这时由于这时由于A特别简单特别简单,因此使得求解的计算公式非常简单因此使得求解的计算公式非常简单,追赶法的计
22、算量追赶法的计算量比较小的比较小的.上页上页下页下页3.4方程组的性态、条件数方程组的性态、条件数 在在分分析析方方程程组组的的解解的的误误差差及及下下章章中中迭迭代代法法的的收收敛敛性性时时,常常产产生生一一个个问问题题,即即如如何何判判断断向向量量 x 的的“大大小小”,对对矩矩阵阵也也有有类类似似的的问问题题.本本节节介介绍绍n维维向向量量范范数数和和nn矩矩阵阵的的范范数数.向向量量范范数数是是三三维维欧欧氏氏空空间间中中向量长度概念的推广,在数值分析中起着重要作用向量长度概念的推广,在数值分析中起着重要作用.3.4.1 向量与矩阵的范数向量与矩阵的范数上页上页下页下页 首先将向量长度
23、概念推广到首先将向量长度概念推广到Rn(或或Cn)中中.称为向量称为向量x,y的的数量积数量积(内积内积).将非负实数将非负实数称为向量称为向量x的的欧氏范数欧氏范数.定义定义1 设设x=(x1,x2,xn)T,y=(y1,y2,yn)T Rn,将将实数实数上页上页下页下页 下面定理可在线性代数书中找到下面定理可在线性代数书中找到.定理定理13 设设x,y Rn(或或Cn),则则 1.(x,x)=0,当且仅当当且仅当x=0时成立时成立;上页上页下页下页 我我们们还还可可以以用用其其他他办办法法来来度度量量Rn中中向向量量的的“大大小小”.例例如如,对对于于x=(x1,x2)T Rn,可可以以用
24、用一一个个x的的函函数数N(x)=max|xi|来来度度量量 x 的的“大大小小”,而而且且这这种种度度量量 x 的的“大大小小”的的方方法法计计算算起起来来比比欧欧氏氏范范数数方方便便.在在许许多多应应用用中中,对对度度量量x的的“大大小小”的的函函数数N(x)都都要要求求是是正正定定的的、齐齐次次的的且且满满足足三三角角不不等等式式.下下面面我我们们给出向量范数的一般定义给出向量范数的一般定义.上页上页下页下页 (1)|x|0(|x|=0当且仅当当且仅当x=0)(正定性正定性),(2)|x|=|x|,对任何对任何 R(或或 C)(齐次性齐次性),(3)|x+y|x|+|y|(三角不等式三角
25、不等式).则称则称N(x)=|x|是是Rn(或或Cn)上的一个上的一个向量范数向量范数(或或模模).定义定义2(向量的范数向量的范数)如果向量如果向量x Rn(或或Cn)的某个的某个实值函数实值函数N(x)=|x|,满足条件,满足条件:由由(3)可推出不等式可推出不等式.(4)|x|-|y|x-y|.上页上页下页下页 下面给出几种下面给出几种常用的向量范数常用的向量范数,设设x=(x1,x2,xn)T.容易证明前三种范数是的容易证明前三种范数是的p-范数范数特殊情况特殊情况,其中其中向量的向量的-范数范数(最大范数最大范数)向量的向量的1-范数范数向量的向量的p-范数范数(0p+)向量的向量的
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 线性代数 方程组 数值 解法 ne
限制150内