数值计算课件-PPT.ppt

《数值计算课件-PPT.ppt》由会员分享，可在线阅读，更多相关《数值计算课件-PPT.ppt（576页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、机械工业出版社机械工业出版社第第1 1章章 数值计算引论第第2 2章章 非线性方程的数值解法非线性方程的数值解法第第3 3章章 线性代数方程组的数值解法线性代数方程组的数值解法第第4 4章章 插值法插值法第第5 5章章 曲线拟合的最小二乘法曲线拟合的最小二乘法第第6 6章章 数值积分和数值微分数值积分和数值微分第第7 7章章 常微分方程初值问题的数值解法常微分方程初值问题的数值解法数值计算方法数值计算方法 第第1 1章章数值计算引论1.1 数值计算方法 1.2 误差的来源1.3 近似数的误差表示法1.4 数值运算误差分析1.5 数值稳定性和减小运算误差 第第1 1章章 数值计算引论 数值计算方

2、法与误差分析数值计算方法与误差分析 理工科大学本科生理工科大学本科生 科学研究。科学研究。现代科学研究的三大手段现代科学研究的三大手段 理论分析、科学实验、科学计算。理论分析、科学实验、科学计算。1.11.1数值计算方法数值计算方法1.1.1 1.1.1 数值计算方法及其主要内容数值计算方法及其主要内容 1.1.课程名称：科学与工程数值计算方法课程名称：科学与工程数值计算方法 简称：科学计算、科学与工程计算、数值分析、简称：科学计算、科学与工程计算、数值分析、计算方法、数值计算方法。计算方法、数值计算方法。科学与工程：从实用的角度，将科学研究与工科学与工程：从实用的角度，将科学研究与工程技术上

3、遇到的实际问题用数学模型来描述，以程技术上遇到的实际问题用数学模型来描述，以便进行定量的分析、研究。便进行定量的分析、研究。数值：数、数字，由数值：数、数字，由0-90-9十个数字、小数点和十个数字、小数点和正负号等组成的数。正负号等组成的数。计算方法：解题的方法。可以用自然语言、数计算方法：解题的方法。可以用自然语言、数学语言或约定的符号语言来描述。学语言或约定的符号语言来描述。计算：只能包括计算机能够直接处理的运算计算：只能包括计算机能够直接处理的运算,即加减乘除等基本运算。即加减乘除等基本运算。数值计算：相对于非数值计算，如查表、排序数值计算：相对于非数值计算，如查表、排序等。用（等。用

4、（0-90-9十个数字、小数点、正负号等组成的）十个数字、小数点、正负号等组成的）数，通过计算机进行加减乘除等基本运算。数，通过计算机进行加减乘除等基本运算。2 2。数值算法：对科学研究与工程技术上遇到的。数值算法：对科学研究与工程技术上遇到的实际数学问题的解法归结为用数值进行加减乘除等实际数学问题的解法归结为用数值进行加减乘除等基本运算，并有确定运算顺序，完整而准确的描述基本运算，并有确定运算顺序，完整而准确的描述称为数值算法。称为数值算法。数值计算方法是研究用数字计算机解决数学问数值计算方法是研究用数字计算机解决数学问题的数值算法及其理论的一门课程。题的数值算法及其理论的一门课程。3.3.

5、主要内容：工程上遇到的数学问题主要内容：工程上遇到的数学问题 数值计算的误差分析数值计算的误差分析 非线性方程非线性方程 线性方程组线性方程组 插值法插值法 最小二乘法最小二乘法 数值积分和数值微分数值积分和数值微分 常微分方程常微分方程1.1.2 1.1.2 用计算机解题的步骤用计算机解题的步骤 当给定一个科学研究与工程技术上遇到的实当给定一个科学研究与工程技术上遇到的实际问题时，首先根据专业知识建立实际问题的数际问题时，首先根据专业知识建立实际问题的数学模型，即模型化（学模型，即模型化（modeling)或建模。然后对数或建模。然后对数学模型进行求解。学模型进行求解。数学模型（包括公式、表

6、格、图形等）求解有数学模型（包括公式、表格、图形等）求解有两条途径：求解析解和数值解。两条途径：求解析解和数值解。求解析解，解以表达式表示，这是准确解。求解析解，解以表达式表示，这是准确解。求数值解，解是以一些离散点上取值的形式表示，求数值解，解是以一些离散点上取值的形式表示，多数情况下，数值解是近似的，求数值解要用计算机。多数情况下，数值解是近似的，求数值解要用计算机。求数学模型数值解的方法称为数值计算方法。求数学模型数值解的方法称为数值计算方法。选择计算方法以后进行程序设计，即用程序语言选择计算方法以后进行程序设计，即用程序语言把算法编成程序，然后上机得出数值解。把算法编成程序，然后上机得

7、出数值解。实际问题实际问题-数学问题数学问题(建模建模)-)-构造数值计算方法构造数值计算方法-程序设计程序设计-上机计算上机计算-数值解数值解-结果分析结果分析1.1.3 1.1.3 数值计算的特点：对算法的要求。数值计算的特点：对算法的要求。1.1.只能包括计算机能够直接处理的运算只能包括计算机能够直接处理的运算,即加减乘即加减乘除等基本运算。除等基本运算。2.2.能任意逼近并达到精度要求，对近似算法要保能任意逼近并达到精度要求，对近似算法要保证收敛性和稳定性。证收敛性和稳定性。3.3.计算时间少，存储空间小。计算时间少，存储空间小。4.4.数值试验证明算法有效。数值试验证明算法有效。误差

8、的来源即产生误差的原因。主要有四种：误差的来源即产生误差的原因。主要有四种：1.1.模模型型误误差差-建建立立的的数数学学模模型型和和实实际际的的距距离离，客客观观量量的的准准确确值值与数学模型的准确解的差。与数学模型的准确解的差。例如自由落体运动方程例如自由落体运动方程1-2 1-2 1-2 1-2 误差的来源误差的来源2.2.观观测测误误差差：数数学学模模型型当当中中的的参参数数或或常常数数常常常常是是是是观观测测或或实实验验来来的的，这这样样必必然然有有误误差差，称称为为观观测测误误差差或或测测量量误误差差，由由观观测测数数据而产生的误差。据而产生的误差。例如自由落体运动方程例如自由落体

9、运动方程3.3.截截断断误误差差(方方法法误误差差)-)-数数学学模模型型的的准准确确解解与与利利用用数数值值计计算算方方法得到的准确解之差。法得到的准确解之差。无穷过程用有穷项代替无穷过程用有穷项代替例如例如:无穷级数无穷级数取前取前n n项代替项代替截断误差截断误差用有限的过程代替无限的过程，和用简单的计算问题代替复杂的计算问题所产生 的误差。4.4.舍入误差舍入误差 ：计算工具字长是有限位，在计算时只能对有限：计算工具字长是有限位，在计算时只能对有限位数字进行运算，超过这个位数时，要舍入，于是产生舍入位数字进行运算，超过这个位数时，要舍入，于是产生舍入误差。原始数据、中间步骤和最终结果都

10、可能产生舍入误差。误差。原始数据、中间步骤和最终结果都可能产生舍入误差。如圆周率如圆周率3.141592653.14159265 一般实数不能精确存储，例如：在一般实数不能精确存储，例如：在1010位十进制数限制下：位十进制数限制下：1-3 近似数的误差表示1.3.2 1.3.2 相对误差相对误差1.3.3有效数字：由绝对误差决定。有效数字：由绝对误差决定。若近似值若近似值x*的绝对误差的绝对误差(限限)是某位的半个是某位的半个单位，则说单位，则说 x*精确到该位，若从该位到精确到该位，若从该位到 x*的的左面第一位非零数字一共有左面第一位非零数字一共有n n位，则称近似值位，则称近似值x*有

11、有n位有效数字。位有效数字。1.1.用四舍五入得到的近似数的误差限是用四舍五入得到的近似数的误差限是末位的半个单位。近似数的误差限是末位末位的半个单位。近似数的误差限是末位的半个单位，则有的半个单位，则有n n位有效数字。因此用位有效数字。因此用四舍五入得到的近似数是有效数字。四舍五入得到的近似数是有效数字。2.2.在公式运算中，要先区分准确量和近在公式运算中，要先区分准确量和近似数。准确数有无穷多位有效数字似数。准确数有无穷多位有效数字.3.3.有效数字位与小数点后有多少位数无有效数字位与小数点后有多少位数无直接关系。直接关系。1.3.4 1.3.4 有效数字与相对误差有效数字与相对误差 1

12、.1.定理给出的是一个充分条件，而不是必要条件。定理定理给出的是一个充分条件，而不是必要条件。定理的逆命题不成立。的逆命题不成立。2.2.在实际应用时，为了要使所取近似数的相对误差满足一在实际应用时，为了要使所取近似数的相对误差满足一定要求，可以用定理，确定所取近似数应具有有效数字的位定要求，可以用定理，确定所取近似数应具有有效数字的位数。数。1.1.定理给出的是一个充分条件，而不是必要条件。定理的定理给出的是一个充分条件，而不是必要条件。定理的逆命题不成立。即若近似数有逆命题不成立。即若近似数有n n位有效数字，相对误差不一定满位有效数字，相对误差不一定满足定理。足定理。2.2.在实际应用时

13、，为了要使所取近似数具有在实际应用时，为了要使所取近似数具有n n位有效数字，位有效数字，要要求所取近似数的相对误差满足定理的要求。求所取近似数的相对误差满足定理的要求。1.4 1.4 数值运算误差分析数值运算误差分析 函数运算误差函数运算误差 算术运算误差算术运算误差1.5 1.5 数值稳定性和减小运算误差数值稳定性和减小运算误差 在计算过程中误差不会扩大或对计算结果的精度要求影在计算过程中误差不会扩大或对计算结果的精度要求影响不大。响不大。减小运算误差减小运算误差:1 1 要避免两相近数相减。要避免两相近数相减。2 2 要防止大数吃掉小数要防止大数吃掉小数 。3 3 要避免除数绝对值远小于

14、被除数绝对值要避免除数绝对值远小于被除数绝对值 。4 4 注意简化计算步骤，减少运算次数注意简化计算步骤，减少运算次数 。例：计算积分例：计算积分写成递推公式写成递推公式 误差传递规律误差传递规律公式改为公式改为 则误差按规律则误差按规律 逐渐缩小逐渐缩小 1.5.1 1.5.1 数值稳定性数值稳定性:一个算法，如果计算结果受误差的影响一个算法，如果计算结果受误差的影响小，就称这个算法具有较好的数值稳定性。否则，就称数值小，就称这个算法具有较好的数值稳定性。否则，就称数值稳定性不好。因此要设法控制误差的传播稳定性不好。因此要设法控制误差的传播 。1.5.2 1.5.2 减小运算误差减小运算误差

15、1.1.要避免相近两数相减要避免相近两数相减 13.5846-13.5839=0.000713.5846-13.5839=0.00076 6位有效数字变成了位有效数字变成了1 1位有效数字。损失了有效数字的位数。位有效数字。损失了有效数字的位数。当当x x接近于接近于0 0时，应时，应例例解一元二次方程解一元二次方程ax2+bx+c=0，其中其中-b,c2 2 要防止大数要防止大数“吃掉吃掉”小数，注意保护重要物理参数。小数，注意保护重要物理参数。在在8位十进制计算机上计算。要规格化和对阶。位十进制计算机上计算。要规格化和对阶。结果，结果，大数大数“吃掉吃掉”小数。小数。类似地类似地改变计算方

16、法改变计算方法例例在在5位十进制计算机上计算位十进制计算机上计算在在5位十进制计算机上计算。要规格化和对阶。位十进制计算机上计算。要规格化和对阶。结果，结果，大数大数“吃掉吃掉”小数。小数。改变计算方法，按绝对值由小到大相加。改变计算方法，按绝对值由小到大相加。3 3 注意简化计算步骤，减少运算次数，避免误差积累注意简化计算步骤，减少运算次数，避免误差积累 例：计算例：计算的值。的值。又如又如只需只需14次乘法。次乘法。采用采用“秦九韶算法秦九韶算法”例：计算多项式例：计算多项式只需只需n次乘法和次乘法和n次加法。次加法。第第2 2 章章 非线性方程的数值解法非线性方程的数值解法 2.1 2.

17、1 初始近似值的搜索初始近似值的搜索 2.2 2.2 迭代法迭代法 2.3 2.3 牛顿迭代法（切线法）牛顿迭代法（切线法）2.4 2.4 弦截法（割线法）弦截法（割线法）2.1 2.1 初始近似值的搜索初始近似值的搜索2.1.12.1.1方程的根单根和重根有根区间 假设假设f(x)f(x)在区间在区间 a,ba,b 内有一个内有一个实根实根x*,若若 b b a a较小，则可在较小，则可在(a,b)(a,b)上任取一点上任取一点x0 0作为作为初始近似根。初始近似根。一般情形，可用逐步搜索法。一般情形，可用逐步搜索法。2.1.2 逐步搜索法逐步搜索法例 对方程 搜索有根区间。解解由于由于f(

18、x)是连续函数，是连续函数，f(0)=-10，故方程，故方程至少有一正实根。设从至少有一正实根。设从x=0出发，取出发，取h=0.5为步长，逐步为步长，逐步右跨搜索，得右跨搜索，得x00.51.01.5f(x)+所以所以f(x)在区间（在区间（1,1.5）上单调连续，因而在）上单调连续，因而在(1,1.5)内内有且仅有一个实根，故可取有且仅有一个实根，故可取1,1.5上任一点做初始近上任一点做初始近似根。似根。可见在（可见在（1，1.5）内有根。又）内有根。又2.1.3 2.1.3 区间二分法区间二分法 定理定理 函数函数f(x)在在 a,ba,b 上单调连续，且上单调连续，且f(a)f(b)

19、f(a)f(b)00，则方程，则方程f(x)=0在区间在区间 a,ba,b 上有且上有且仅有一个实根仅有一个实根x*。二分法的基本思想二分法的基本思想 将有根的区间二分为两个小区间，然后判将有根的区间二分为两个小区间，然后判断根在那个小区间，舍去无根的小区间，而把断根在那个小区间，舍去无根的小区间，而把有根的小区间再一分为二，再判断根属于哪个有根的小区间再一分为二，再判断根属于哪个更小的区间，如此反复更小的区间，如此反复 ，直到求出满足精度，直到求出满足精度要求的近似根。要求的近似根。令令近似根近似根xk的误差估计的误差估计中点中点这时有三种情况：这时有三种情况：f(x0)=0,x0为所求的根

20、为所求的根.f(x0)和和a0同号，取同号，取x0=a1f(x0)和和b0同号，取同号，取x0=b1x*x*新的有根区间为新的有根区间为(a1,b1)，长度是原来的一半。，长度是原来的一半。如此反复，有如此反复，有(ak,bk),k=0,1,2,.近似根近似根xk的误差估计的误差估计第第2次二分，取中点次二分，取中点若若f(a1)f(x1)0，则，则x*(a1,x1)，令令a2=a1,b2=x1；否则否则令令a2=x1,b2=b1。新的有根区间为新的有根区间为(a2,b2)。由此得二分过程结束的原则：由此得二分过程结束的原则：先给定精度要求先给定精度要求(绝对误差限绝对误差限)，（2）当当|b

21、k+1ak+1|时结束二分计算，取时结束二分计算，取x*xk；（1）事先由）事先由估计出二分的最小次数估计出二分的最小次数k，取取x*xk2.2 2.2 迭代法迭代法2.2.1 2.2.1 迭代原理迭代原理2.2.2 2.2.2 迭代的收敛性迭代的收敛性2.2.3 2.2.3 迭代的收敛速度迭代的收敛速度2.2.4 2.2.4 迭代的加速迭代的加速预备定理2.2.1迭代原理迭代原理计算结果见下表计算结果见下表方程方程f(x)=0化为等价形式的方程化为等价形式的方程x=(x)，构造迭代公式构造迭代公式xk+1=(xk),k=0,1,2,取初始近似根取初始近似根x0,进行迭代计算进行迭代计算x1=

22、(x0),x2=(x1),.则有则有x1,x2,.,xk,.,得到迭代序列得到迭代序列xk.如果这个序列有极限，则迭代公式是如果这个序列有极限，则迭代公式是收敛的。这时收敛的。这时则则，x*为不动点，等价地有为不动点，等价地有f(x*)=0,x*即为方程的根。连续函数即为方程的根。连续函数(x)称称为迭代函数。为迭代函数。实实际际计计算算到到|xkxk-1|（是是预预定定的的精精度），取度），取x*xk。迭代公式收敛指迭代序列迭代公式收敛指迭代序列xk收敛，迭代收敛，迭代公式发散指迭代序列公式发散指迭代序列xk不收敛，即发散。不收敛，即发散。迭代公式不一定总是收敛。迭代公式不一定总是收敛。例如

23、求方程例如求方程f(x)=x3-x-1=0的一个根的一个根。对应的迭代公式为对应的迭代公式为取初值取初值迭代序列迭代序列xk发发散散.x1=(x0)x2=(x1)迭代法收敛与发散的图示迭代法收敛与发散的图示迭代法的收敛与发散 收敛的情形 发散的情形2.2.2迭代的收敛性迭代的收敛性迭代法的收敛条件及误差估计式迭代法的收敛条件及误差估计式定理（充分性条件）定理（充分性条件）设函数设函数(x)在在a,b上连续，且上连续，且(1)对对xa,b,有有(x)a,b(2)存在存在0L1，使对任意，使对任意xa,b有有|(x)|L1则方程则方程x=(x)在在a,b上的根上的根x*存在且唯一；存在且唯一；对初

24、值对初值x0a,b,迭代过程迭代过程xk+1=(xk)均收敛于方程均收敛于方程的根的根x*。定理中的定理中的(1)对对xa,b,有有(x)a,b，称，称为适定性（映内性）。为适定性（映内性）。证明证明先证根的存在性。先证根的存在性。作连续函数作连续函数(x)=x-(x),由条件（由条件（1）xa,b,(x)a,b，即，即a(x)、xb,于是于是(a)=a-(a)0(b)=b-(b)0由于由于(x)是连续函数，故必存在是连续函数，故必存在x*a,b使使(x*)=0.即即(x*)=x*-(x*)=0.于是于是x*=(x*)即即x*为方程为方程x=(x)的根。的根。其次，证根的唯一性其次，证根的唯一

25、性。设设y*也是方程的根，则也是方程的根，则x*=(x*),y*=(y*),x*-y*=(x*)(y*)=()(x*-y*)x*-y*()(x*-y*)=0，（x*-y*）1-()=0由条件（由条件（2）|(x)|L1，故有故有x*-y*=0，即即x*=y*所以方程在所以方程在a,b的根唯一的根唯一。再证迭代的收再证迭代的收敛性敛性。由由xk=(xk-1),x*=(x*),有有|xk-x*|=|()(xk-1-x*)|L|xk-1-x*|L2|xk-2-x*|L3|xk-3-x*|Lk|x0-x*|0（k）所以，对所以，对a,b上任取的上任取的x0,迭代公式迭代公式xk+1=(xk)都收敛于都

26、收敛于x*。L越小收敛得越快。越小收敛得越快。定理是充分性条定理是充分性条件件xk-x*=(xk-1)(x*)=()(xk-1-x*)推论：在定理的条件下，有误差估计式推论：在定理的条件下，有误差估计式验后验后误差估计式误差估计式验前验前误差估计式误差估计式证明：证明：|xk-x*|L|xk-1-x*|=L|xk-1-xk+xk-x*|L（|xk-x*|+|xk-1-xk|）（1-L)|xk-x*|L|xk-1-xk|迭代法的终点判断：只要相邻两次迭代法的终点判断：只要相邻两次迭代值的偏差充分小，就能保证迭迭代值的偏差充分小，就能保证迭代值足够准确，因而用代值足够准确，因而用|xk-xk-1|

27、控制迭代过程的结束。控制迭代过程的结束。定理定理设在区间设在区间a,b上方程上方程x=(x)有根有根x*,且对一切且对一切xa,b都有都有|(x)|1，则对于该区间上任意，则对于该区间上任意x0(x*),迭代公式迭代公式xk+1=(xk)一定发散。一定发散。证明证明不可能收敛于不可能收敛于0。计算结果见下表计算结果见下表取方程的根取方程的根2.0946。由于 ，故取 迭代法的局部收敛性迭代法的局部收敛性由于在实际应用中根由于在实际应用中根x*事先不知道，故条事先不知道，故条件件|(x*)|1无法验证。但已知根的初值无法验证。但已知根的初值x0在根在根x*邻域，邻域，又根据又根据(x)的连续性，

28、则可采用的连续性，则可采用|(x0)|1来代替来代替|(x*)|1，判断迭代的收敛性。，判断迭代的收敛性。例例 求方程求方程x=ex在在x=0.5附近的一个根，附近的一个根，按按5位小数计算，结果的精度要求位小数计算，结果的精度要求为为=103.解解迭代公式迭代公式xk+1=exk，取取(x)=ex,迭代公式迭代公式xk+1=exk收敛。收敛。迭代结果迭代结果:0123450.50.606530.545240.579700.560070.571170.106530.061290.034460.019630.011106789100.564860.568440.566410.567560.566

29、910.006310.003580.002030.001150.00065kxkxkxk-1xkxk-1kxk|x10-x9|=0.000650)解的正实根。因为 f(x)=2x，由牛顿迭代公式得当a=115时，取初值 x0=10，迭代4次可得10，10.7500，10.723837，10.723805，10.72380510.723805是否还能用牛顿法计算一个正数的立方根？,则x3-3=0,求等价于求方程 令例 用牛顿迭代法求解的正实根。由牛顿迭代公式得当a=4111.7910时，取初值 x0=8，迭代4次可得7.48，7.439977,7.439760,7.439760,令例 用牛顿迭代

30、法造倒数表，计算解3、牛顿迭代法的计算步骤(1)给出x0,，N(2)计算(3)若则转(4)；否则，转(2);(4)输出x1,结束。牛顿迭代法局部收敛:2.4.2 牛顿迭代法的收敛情况1.局部收敛性结论：f(x)=0的单根x*附近存在着连续的二阶导数，当初值在单根x*附近时，牛顿法具有平方收敛速度。证 牛顿法迭代函数当 f(x*)=0，而 f(x*)0，则x*是f(x)=0的单根,单根x*附近存在着连续的二阶导数，有 牛顿法至少具有平方收敛速度。2.3.3 牛顿迭代法的修正1.简化牛顿法(平行弦法)2.牛顿下山法 在牛顿法基础上，构造既有较高的收敛速度，又不 需要求导数的迭代公式。1公式的推导

31、用差商 则得两个弦截迭代公式 2.5 弦截法（割线法）单点弦法 双点弦法 例用单点弦截迭代法求方程 x3-0.2x-1.2=0 在x=1.5附近的根。解弦截迭代公式据题意，取x0=1.5,f(x0)=1.425,代入单点弦迭代法所以有k1234567xk11.1501.1901.1931.1981.1991.200例用双点弦截迭代法求方程 xex-1=0 在x=0.5附近的根。解弦截迭代公式方程化为 x-e x=0,令 ，代入双点弦迭代法 kxk 0 1 2 30.50.60.567 540.567 15第第3 3章章 线性代数方程组的数值解法线性代数方程组的数值解法3.1 3.1 高斯消去法

32、高斯消去法3.2 3.2 矩阵三角分解法矩阵三角分解法3.3 3.3 平方根法平方根法3.4 3.4 向量和矩阵的范数向量和矩阵的范数3.5 3.5 方程组的形态和误差分析方程组的形态和误差分析3.6 3.6 迭代法迭代法3.7 3.7 迭代法的收敛性迭代法的收敛性矩阵形式矩阵形式Ax=b,其中其中n n个未知量个未知量n n个方程的线性代数方程组个方程的线性代数方程组或写成或写成两类数值解法：两类数值解法：直接解法直接解法:假定计算过程没有舍入误差的情况下，假定计算过程没有舍入误差的情况下，经过有限步算术运算后能求得线性方程组精确解的方经过有限步算术运算后能求得线性方程组精确解的方法。法。经

33、过有限步运算就能求得精确解的方法，但实际经过有限步运算就能求得精确解的方法，但实际计算中由于舍入误差的影响，这类方法也只能求得近计算中由于舍入误差的影响，这类方法也只能求得近似解；似解；例如：高斯消去法、三角分解法等。例如：高斯消去法、三角分解法等。迭代解法迭代解法:构造适当的向量序列，用某种极限过构造适当的向量序列，用某种极限过程去逐步逼近精确解。程去逐步逼近精确解。例如：雅可比迭代法、高斯例如：雅可比迭代法、高斯-赛德尔迭代法等。赛德尔迭代法等。上三上三角形方程角形方程组组回代求解，得回代求解，得下三角形方程组下三角形方程组 顺代可求得顺代可求得 上二对角方程组上二对角方程组 回代求解，回

34、代求解，得得 下二对角方程组下二对角方程组 顺代可求得顺代可求得 3.1 高斯消去法高斯消去法3.1.1顺序顺序高斯消去法高斯消去法 (按方程和未知量的自然顺序进行按方程和未知量的自然顺序进行)基本思想：用逐次消去未知数的方法把原方程组化为上三角形方程组进行求解。求解 分成两步：1.消元过程：用初等行变换将原方程组的系数矩阵化为上三角形矩阵（简称上三角阵）。2.回代过程：对上三角形方程组的最后一个方程求解，将求得的解逐步往上一个方程代入求解。顺序高斯消去法消元过程顺序高斯消去法消元过程:依依从从左左到到右右、自自上上而而下下的的次次序序将将主主对对角角元元下下方方的的元素化为零。元素化为零。1

35、不作行交换。不作行交换。2用不等于零的数乘某行，加至另一行。用不等于零的数乘某行，加至另一行。系数行列式的计算：系数行列式的计算：例例 消元过程消元过程 主元为主元为2，2.5，0.6detA=22.50.6=3消元过程消元过程回代过程顺序高斯消去法的使用条件顺序高斯消去法的使用条件使用条件之一使用条件之一定理定理线性方程组系数矩阵线性方程组系数矩阵A的顺序主子的顺序主子矩阵矩阵Ak(k=1,2,n)非奇异非奇异，则顺序高斯消去，则顺序高斯消去法能实现方程组的求解。法能实现方程组的求解。即方程组能用顺序高斯消去法求解的充即方程组能用顺序高斯消去法求解的充要条件是系数行列式的顺序主子式非零。要条

36、件是系数行列式的顺序主子式非零。高高斯斯消消去去法法能能按按顺顺序序进进行行到到底底的的充充要要条条件件是是在原方程组的系数矩阵中如何反映出这个条件在原方程组的系数矩阵中如何反映出这个条件呢呢?A的的k阶顺序主子矩阵阶顺序主子矩阵Ak的行列式的行列式使用条件之二使用条件之二n阶矩阵阶矩阵A为严格对角占优矩阵是指其每个主对为严格对角占优矩阵是指其每个主对角元的绝对值大于同一行其他元素绝对值之和，即角元的绝对值大于同一行其他元素绝对值之和，即 一阶严格对角占优矩阵指一个非零数。定理定理方程组系数矩阵方程组系数矩阵A为严格对角占优矩为严格对角占优矩阵则可实现阵则可实现用顺序高斯消去法求解。用顺序高斯

37、消去法求解。3.1.2列主元高斯消去法列主元高斯消去法为什么列选主：数值不稳定为什么列选主：数值不稳定 当当高高斯斯消消去去法法的的主主元元时时,尽尽管管“当当 A A 非非奇奇异异时时，det det A0A0，方方程程组组有有唯唯一一解解”，也不能实现，也不能实现高斯消去法求解。高斯消去法求解。例例，A A 非非奇奇异异，det det A0A0，方程组有，方程组有唯唯一一解解，但但 ，不不能能实实现现高高斯斯消消去去法法求解。求解。高斯消去法的主元 ，但绝对值很小时，用绝对值小的数做除数，会导致其它元素数量级的严重增长和舍入误差的扩大。列列选选主主高高斯斯消消去去法法：避避免免用用绝绝对

38、对值值小小的的元元素素，作作除除数数。每每次次消消元元前前选选取取一一列列中中绝绝对对值值最最大大的的元元素素作作为为主主元元素素。用用这这个个主主元元素素作除数，这样便可以减少舍入误差。作除数，这样便可以减少舍入误差。列列选选主主高高斯斯消消去去法法的的优优越越性性，不不增增加加求求解过程的运算量，而大大减小误差。解过程的运算量，而大大减小误差。例例用列主元高斯消去法求解方程组用列主元高斯消去法求解方程组(用三位用三位有效数字计算有效数字计算)解解选主元选主元选主元选主元消元过程完成，得到上三角形消元过程完成，得到上三角形方程组方程组 再作回代可再作回代可求得求得 行列式的计算：行列式的计算

39、：列主元法的消元列主元法的消元过程过程 计算过程有计算过程有2次行交换，故次行交换，故m=2，主元为，主元为5，-1.6，2detA=(-1)25(-1.6)2=16m为消元过程中交换行的次为消元过程中交换行的次数。数。列列主主元元高高斯斯消消去去法法(简简称称列列主主元元消消去去法法)的的计计算算框框图图d:绝对值最大的主元素的存储单元。绝对值最大的主元素的存储单元。l:绝对值最大的主元素所在的行的存储单元。绝对值最大的主元素所在的行的存储单元。定理定理系数矩阵为对称严格对角占优，则全是主元。系数矩阵为对称严格对角占优，则全是主元。3.1.3高斯高斯-约当约当(Jordan)消去法消去法1。

40、方法的描述。方法的描述消元时将主元上方元素也消为消元时将主元上方元素也消为0，最后系数矩阵化为对角矩阵。这种算最后系数矩阵化为对角矩阵。这种算法只有消元，没有回代，这种方法称法只有消元，没有回代，这种方法称做高斯做高斯-约当约当(Jordan)消去法。消去法。2。归一方法。归一方法消元时将主元上方也消为消元时将主元上方也消为0，并将，并将第第k行除以行除以akk(k=1,2,n)，使主元位，使主元位置化为置化为1，最后系数矩阵化为，最后系数矩阵化为单位矩单位矩阵。这种方法无须回代，称做归一的阵。这种方法无须回代，称做归一的高斯高斯-约当约当(Jordan)消去法。消去法。归一方法的例子归一方法

41、的例子3。列选主高斯。列选主高斯-约当约当(Jordan)消去法。消去法。4。高斯。高斯-约当约当(Jordan)消去法的计算量消去法的计算量5。高斯。高斯-约当约当(Jordan)消去法求逆矩阵消去法求逆矩阵 当当detA0时，时，A存在逆矩阵，设存在逆矩阵，设s=1,2,n求求A-1就相当于求解就相当于求解n个线性方程组个线性方程组高斯高斯-约当约当(Jordan)消去法求逆。消去法求逆。3.2矩阵矩阵三角分解法三角分解法。定定义义 将将矩矩阵阵A A分分解解成成一一个个下下三三角角阵阵L L和和一一个个上上三三角阵角阵U U的乘积，即的乘积，即 A=LUA=LU称为称为A A的三角分解或

42、的三角分解或LULU分解。分解。例如例如A=A=这里有这里有A A的两种不同的三角分解，类似可举出的两种不同的三角分解，类似可举出很多，一般，若很多，一般，若A=LUA=LU是一个三角分解，任取是一个三角分解，任取与与A A同阶的非奇异对角矩阵同阶的非奇异对角矩阵D D，则，则 A A=(=(LDLD)()(D D-1-1U U)=)=L L1 1U U1 1也是也是A A的三角分解。的三角分解。杜利特尔杜利特尔分解分解(Doolittle)常用的两种三角分解常用的两种三角分解克洛特分克洛特分解解(Crout)定理定理 n n阶矩阵阶矩阵A A存在唯一的杜利特尔分解或克劳特存在唯一的杜利特尔分

43、解或克劳特分解的充要条件是分解的充要条件是A A的顺序主子矩阵的顺序主子矩阵A Ak k (k k=1,2,=1,2,n n-1)1)非奇异。非奇异。例例设设讨论讨论a取何值时，取何值时，矩阵矩阵A可作可作LU分解。分解。解解 当当A的的顺序主子式不为零，顺序主子式不为零，矩阵矩阵A有有LU分解。分解。所以，有所以，有非奇异矩阵不一定存在非奇异矩阵不一定存在LU分解。例分解。例 解解 A是是非奇异矩阵，假设有非奇异矩阵，假设有LU分解（分解（杜利特杜利特尔分解）尔分解）比较等式两端第比较等式两端第1列，可得列，可得 上二式不能同时成立，即非奇异矩阵上二式不能同时成立，即非奇异矩阵A不存在不存在

44、LU分解。分解。复习：矩阵乘法复习：矩阵乘法 A=BC3.2.2Doolittle3.2.2Doolittle分解步骤分解步骤 A=LU 令令i=r,r+1,n，(即即i大于等于大于等于r)例例紧凑格式紧凑格式3.2.3用三角分解求解线性方程组用三角分解求解线性方程组设设A非奇异，并有三角分解非奇异，并有三角分解A=LU，则方程组，则方程组Ax=b就化为就化为LUx=b只须求解两个简单的三角形方程组：只须求解两个简单的三角形方程组：（1）解）解Ly=b顺代求出顺代求出y（2）解）解Ux=y，回代求出，回代求出x.求得求得L、U后再求解方程组后再求解方程组Ly=b,Ux=y例例用杜利特尔分解法求

45、解方程组用杜利特尔分解法求解方程组解解先对系数矩阵进行杜利特尔分解先对系数矩阵进行杜利特尔分解A=LU求解两个三角形方程组，求解两个三角形方程组，得得方程组方程组Ax=b化为化为Ux=y时，时，A通过通过LU分解得到分解得到U，b通过通过LU分解得到分解得到y，则，则Ax=b化化为为Ux=y时，将时，将b增广到增广到A进行进行LU分解得到分解得到y。例例用杜利特尔分解法求解方程组用杜利特尔分解法求解方程组解解先求增广系数矩阵的杜利特尔分解，即先求增广系数矩阵的杜利特尔分解，即例例用杜利特尔分解法求解方程组系用杜利特尔分解法求解方程组系解解先求增广矩阵的杜利特尔分解，即先求增广矩阵的杜利特尔分解

46、，即3.2.4追赶法追赶法(托马斯法）：解三对角线性方程组托马斯法）：解三对角线性方程组系数矩阵为三对角矩阵，非零元素分布在主对角线系数矩阵为三对角矩阵，非零元素分布在主对角线及其相邻两条次对角线上。及其相邻两条次对角线上。三对角线性方程组三对角线性方程组Ax=f对系数矩阵对系数矩阵A进行克劳特分解进行克劳特分解A=LUL下二对角矩阵，下二对角矩阵，U单位上二对角矩阵。单位上二对角矩阵。定理定理当三对角矩阵满足条件当三对角矩阵满足条件时，其所有顺序主子矩阵均非奇异。时，其所有顺序主子矩阵均非奇异。解下三角形方程组解下三角形方程组解下三角形方程组解下三角形方程组对称正定矩阵 对称正定矩阵 对称正

47、定矩阵 对称正定矩阵 3.3.2对称正定矩阵的乔累斯基分解对称正定矩阵的乔累斯基分解3.3.3改进平方根法改进平方根法3.4 向量和矩阵的范数3.4.1 向量范数4收敛性收敛性342 矩阵范数矩阵范数的性质 常用的矩阵范数有行（无穷）范数和列常用的矩阵范数有行（无穷）范数和列（一）范数。（一）范数。例例如如 4常用的矩阵范数常用的矩阵范数设设4常用的矩阵范数常用的矩阵范数矩阵的收敛矩阵的收敛 谱半径谱半径的性质3.6 线性代数方程组的迭代法 3.6.1 迭代原理 3.6.2 雅可比迭代 3.6.3 高斯-赛德尔迭代 3.6.4 松弛法 3.6.5 迭代公式的矩阵表示 写成矩阵形式 Ax=b其中

48、3.6.1 迭代原理 设线性代数方程组例 用雅可比迭代法求解方程组 解 从3个方程分离出构造雅可比迭代公式 3.6.2 雅可比迭代迭代计算k012345x1(k)00.30.800.91800.97160.9894x2(k)01.51.761.92601.97001.9897x3(k)02.02.662.86402.95402.9823设线性方程组 其中系数矩阵非奇异，且主对角元aii0，(i=1,2,n)，由第i 个方程解出xi，有建立迭代格式写成取初值 ，进行迭代。这种方法称为雅可比迭代法。雅可比迭代公式即i=1,2,n雅可比迭代的算法框图3.6.3 高斯-赛德尔(Gauss-Seidel

49、)迭代 迭代收敛时，新值xi(k+1)比老值xi(k)更准确，在雅可比迭代中，算出新值xi(k+1)后，用新值xi(k+1)代替用于后面计算的老值xi(k)，期望这样会收敛得更快些。例 用高斯-赛德尔迭代法求解方程组解 方程组化为等价的方程组 构造高斯-赛德尔迭代公式 迭代计算：1.562.6842.953870.88041.94448高斯-赛德尔迭代公式 0.3计算结果:k0123x1(k)00.30.88040.98428x2(k)01.561.944481.99224x3(k)02.6842.953872.99375高斯-赛德尔(Seidel)迭代公式 3.6.4 松弛法 矩阵形式 Ax

50、=b其中3.6.5 迭代公式的矩阵表示n个未知量n个方程的线性代数方程组令其中 D为对角阵，L,U为严格下三角阵，严格上三角阵。L+U=D-A雅可比迭代公式分量形式矩阵形式雅可比迭代的矩阵形式雅可比迭代矩阵 将L+U=D-A代入写成雅可比迭代的矩阵形式为J为雅可比迭代矩阵。三种迭代格式总结3.7 迭代法的收敛性 3.7.1 收敛的基本定理 迭代法收敛的充分必要条件 定理 迭代法 收敛的充分必要条件是迭代矩阵B的谱半径(B)1。.例题 试判断迭代公式是否收敛。解 迭代矩阵,故迭代发散。迭代法收敛的充分条件3.7.2迭代矩阵法例题 试判断以下迭代公式是否收敛：解(1)迭代矩阵，故迭代公式收敛。(2