数值分析教案省公共课一等奖全国赛课获奖课件.pptx

第第1页页绪论绪论 第一章插值法第一章插值法第二章数值积分和数值微分第二章数值积分和数值微分第三章曲线拟合最小二程法第三章曲线拟合最小二程法第四章第四章 求非线性方程根近似方法求非线性方程根近似方法第五章第五章 线性代方程组直接法线性代方程组直接法第六章第六章 解线性方程组迭代法第七章矩阵特征值和特征向量计算第七章矩阵特征值和特征向量计算第八章常微分方程数值解法第八章常微分方程数值解法计算方法计算方法第第2页页参考书1.数值分析，翟瑞彩，天津大学出版社；2.计算方法，中山大学与武汉大学编写 3.数值计算计算原理，李庆杨，关治，白峰彬，清华大学出版社4.计算方法引论，徐萃薇，科学出版社第第3页页1.1.计算方法任务与特点计算方法任务与特点绪论绪论实际问题数学问题提供计算方法实际问题数学问题提供计算方法程序设计上机计算结果分析程序设计上机计算结果分析计算方法计算方法第第4页页2.2.基本数学问题基本数学问题:1.大型线性代数方程组大型线性代数方程组Ax=b求解求解;2.矩阵矩阵A特征值和特征向量计算特征值和特征向量计算;3.非线性方程非线性方程求解求解(求根求根);4.积分积分计算计算;5.常微分方程初值问题求解常微分方程初值问题求解;6.其它。其它。第第5页页求准确解求准确解(值值)普通非常困难。比如：普通非常困难。比如：1.1.方程组阶数方程组阶数n n很大，比如很大，比如n=20,n=20,计算机运算速度计算机运算速度 1 1亿次亿次/秒秒,用不好方法用不好方法,大约需算大约需算3030多万年多万年;好方法不到一分钟。另外，有计算结果可靠性好方法不到一分钟。另外，有计算结果可靠性 问题。问题。2.2.特征值定义特征值定义 第第6页页3.3.形式复杂时求根和求积分很困难。形式复杂时求根和求积分很困难。4.4.线性微分方程易解，线性微分方程易解，如如 非线性方程难解，如非线性方程难解，如 希希望：望：求近似解，但方法简单可行，行之有效求近似解，但方法简单可行，行之有效（计算量小，误差小等）。以计算机为工（计算量小，误差小等）。以计算机为工具，易在计算机上实现。具，易在计算机上实现。计算机运算计算机运算:只能进行加，减，乘，除等算术运只能进行加，减，乘，除等算术运算和一些逻辑运算。算和一些逻辑运算。计算方法：计算方法：把求解数学问题转化为按一定次序只把求解数学问题转化为按一定次序只进行加，减，乘，除等基本运算进行加，减，乘，除等基本运算数值方法。数值方法。第第7页页3.3.数值分析研究对象与特点数值分析研究对象与特点第第8页页先看两个例子。先看两个例子。例例1 1 求方程求方程 x x2 2=2sinx=2sinx，在区间，在区间(1,2)(1,2)内根。内根。理论上可知显然找不出根解析式，即无法求出准理论上可知显然找不出根解析式，即无法求出准确解。确解。例例2 2 用用CramerCramer法则求解法则求解n n元线性方程组。元线性方程组。显然理论上可行，且有准确表示式。实际计算时显然理论上可行，且有准确表示式。实际计算时会出现什么问题呢？会出现什么问题呢？第第9页页实际问题实际问题数学模型数学模型上机计算求出结果上机计算求出结果数值计算方法数值计算方法看用数学和计算机处理实际问题过程：看用数学和计算机处理实际问题过程：应用数学研究任务应用数学研究任务 数值分析研究对象数值分析研究对象最终提供是针对各类数学问题数值算法（即最终提供是针对各类数学问题数值算法（即计算公式、计算方案、计算过程）计算公式、计算方案、计算过程）第第10页页 3 3、含有好计算复杂性、含有好计算复杂性 4.4.数值分析提供算法含有下面四个特点：数值分析提供算法含有下面四个特点：1 1、面向计算机、面向计算机 2 2、有可靠理论分析、有可靠理论分析4 4、经过数值试验验证有效性、经过数值试验验证有效性第第11页页 3 3、化整为零、化整为零 5.5.数值分析共同思想和方法：数值分析共同思想和方法：1 1、迭代法、迭代法 2 2、以直代曲、以直代曲4 4、外推法、外推法第第12页页1.1.认识建立算法和对每个算法进行理论分析是基本认识建立算法和对每个算法进行理论分析是基本 任务，主动适应任务，主动适应“公式多公式多”特点；特点；2.2.重视各章建立算法问题提法，搞清问题基重视各章建立算法问题提法，搞清问题基 本提法，逐步深入；本提法，逐步深入；3.3.了解每个算法建立数学背景，数学原理和基本了解每个算法建立数学背景，数学原理和基本 线索，对最基本算法要非常熟悉；线索，对最基本算法要非常熟悉；4.4.认真进行数值计算训练，学习各章算法完全是认真进行数值计算训练，学习各章算法完全是 为用于实际计算，必须真会算。为用于实际计算，必须真会算。第第13页页n本课程基本要求本课程基本要求掌握数值方法基本原理掌握数值方法基本原理掌握惯用科学与工程计算基本方法掌握惯用科学与工程计算基本方法能用所学方法在计算机上算出正确结果能用所学方法在计算机上算出正确结果第第14页页课程学习结束后你具备能力1.对详细数值计算问题，你会选择适当算法，并经过计算机计算出正确结果；2.对给定算法会从理论上分析其优劣性；3.会依据原理结构处理较简单数值计算问题算法。第第15页页1.2 1.2 误差基础知识误差基础知识一一.误差起源（分类）误差起源（分类）1.模型误差。模型误差。2.观察误差。观察误差。3.截断误差，如截断误差，如右端是截断误差。右端是截断误差。第第16页页4.4.舍入误差。计算机字长有限，普通实数不能准确舍入误差。计算机字长有限，普通实数不能准确存放，于是产生舍入误差。比如：在存放，于是产生舍入误差。比如：在1010位十进位十进制数限制下：制数限制下：舍入误差很小，本课程将研究它在运算过程中舍入误差很小，本课程将研究它在运算过程中 是否能有效控制。是否能有效控制。第第17页页实际问题实际问题确定数确定数值解法值解法上机求解上机求解用计算机处理实际问题普通过程用计算机处理实际问题普通过程建立数建立数学模型学模型模型误差、观察误差模型误差、观察误差截断误差截断误差舍入误差舍入误差应用数学处理问题应用数学处理问题数值分析处理问题数值分析处理问题在此主要研究这两种误差在此主要研究这两种误差第第18页页二误差基本概念二误差基本概念1 1绝对误差。设绝对误差。设 准确值，准确值，近似值。近似值。称称 为为 绝对误差。绝对误差。为为 绝对误差限。绝对误差限。2 2相对误差。称相对误差。称 为为 相对误差。相对误差。实用中，惯用实用中，惯用 表示表示 相对误差。相对误差。称称 为为 相对误差限。相对误差限。第第19页页3 3有效数字有效数字设设 若若 (1.1)(1.1)则说则说 含有含有n n位有效数字，分别是位有效数字，分别是 若若 ，则称，则称 为有效数。为有效数。第第20页页例例1.11.1 设设 =0.0270=0.0270是是某某数数 经经“四四舍舍五五入入”所所得得，则则 误差误差 不超出不超出 末位半个单位，即：末位半个单位，即：又又 ,故该不等式又可写为故该不等式又可写为 由有效数字定义可知由有效数字定义可知,有有3 3位有效数字，分别位有效数字，分别 是是2,72,7，0 0。第第21页页例例1.2 1.2 =32.93,=32.89,=32.93,=32.89,故故 有有3 3位有效数字，分别是位有效数字，分别是3,23,2，8 8。因因为为 中中数数字字9 9不不是是有有效效数数字字，故故 不不是是有有效效数。数。第第22页页三、有效数位与误差关系三、有效数位与误差关系1.1.有效数位有效数位n n越多，则绝对误差越多，则绝对误差 越小越小 (由定义由定义1.1)1.1)2.2.定理定理1.1 1.1 若近似数若近似数 含有含有n n位有效数字，则位有效数字，则 (1.2)(1.2)反之，反之，若若 则则 最少有最少有n n位有效数字。位有效数字。第第23页页 两边除以两边除以 得得 (1.3)(1.3)和（和（1.41.4）给出了由自变量误差引发函）给出了由自变量误差引发函 数值误差近似式（误差传输）。数值误差近似式（误差传输）。四、数值运算误差预计四、数值运算误差预计(误差传输误差传输)1.1.一元函数情形一元函数情形 设设 则则 ，由，由TaylorTaylor展开公式展开公式 (1.4)(1.4)（1.3）第第24页页2.2.多元函数情形多元函数情形 设设 ，则，则，由多元函数由多元函数TaylorTaylor展开公式类似可得展开公式类似可得 （1.51.5）（1.61.6）在（在（1.61.6）式中，分别取）式中，分别取,可得可得同号)（1.71.7）（1.81.8）（1.91.9）(,第第25页页例例1.31.3：测得某桌面长测得某桌面长a a近似值近似值a*=120cm,a*=120cm,宽宽b b 近似值近似值b*=60cmb*=60cm。若已知。若已知|e(a*)|0.2cm,|e(a*)|0.2cm,|e(b*)|0.1cm|e(b*)|0.1cm。试求近似面积试求近似面积s*=a*b*s*=a*b*绝对误差限与相对误差限。绝对误差限与相对误差限。解解:面积面积s=ab,s=ab,在公式（在公式（1.51.5）中）中,将将 换为换为 s=ab,s=ab,则则相对误差限为相对误差限为第第26页页 1.3 1.3 选取算法应遵照标准选取算法应遵照标准1.1.尽可能简化计算步骤，降低乘除运算次数尽可能简化计算步骤，降低乘除运算次数.比如，计算多项式比如，计算多项式 通常运算乘法次数为通常运算乘法次数为 若采取递推算法若采取递推算法,则乘法次数仅为则乘法次数仅为n.n.又如又如 第第27页页2.2.预防大数预防大数“吃掉吃掉”小数小数 当当|a|b|a|b|时，尽可能防止时，尽可能防止a+b a+b。比如，假设计算。比如，假设计算机机 只能存放只能存放1010位尾数十进制数，则位尾数十进制数，则3.3.尽可能防止相近数相减尽可能防止相近数相减 比如，当比如，当x x很大时，应很大时，应 ，当当x x靠近于靠近于0 0时，应时，应第第28页页 4.4.防止绝对值很小数做分母防止绝对值很小数做分母 当当|b|a|b|a|时，应尽可能防止时，应尽可能防止 。5.5.选取数值稳定性好算法，以控制舍入误差高速选取数值稳定性好算法，以控制舍入误差高速 增加增加 比如比如 若若 （误差（误差 ）则计算）则计算 时误差扩大了时误差扩大了 倍倍,而而 （n=1,2,n=1,2,）是稳定。是稳定。第第29页页范数n范数是长度概念推广范数是长度概念推广,是一个度量定义是一个度量定义,是测量两个函数是测量两个函数,向量向量,矩阵等之间矩阵等之间距离一个非负实数距离一个非负实数.范数定义形式各种多样范数定义形式各种多样,采取同范数定义采取同范数定义,可得不一样可得不一样范数范数,但都满足以下三个条件但都满足以下三个条件(公理化定义公理化定义):1.(非负性非负性)2.(齐次性齐次性)3.(三角不等式三角不等式)称实数称实数|X|为向量为向量X范数范数.#不一样范数间关系不一样范数间关系:等价等价.第第30页页基本要求：基本要求：1.1.熟悉计算方法在处理实际问题中所处地位，熟悉熟悉计算方法在处理实际问题中所处地位，熟悉计算方法是以计算机为工具求近似解数值方法；计算方法是以计算机为工具求近似解数值方法；2.2.熟悉绝对误差（限），相对误差（限）及有效数熟悉绝对误差（限），相对误差（限）及有效数字概念；字概念；3.3.熟悉公式（熟悉公式（1.21.2）-（1.91.9）；）；4.4.熟悉选取算法应遵照标准；熟悉选取算法应遵照标准；第第31页页 计算方法计算方法 f(x)=0 f(x)=0根或根或f(x)f(x)零点，当零点，当f(x)f(x)复杂时，极难求复杂时，极难求 （找近似有效简单方法）。（找近似有效简单方法）。第二章第二章 求方程根近似方法求方程根近似方法 2.1 2.1 区间二分法区间二分法理理 论论 :f(x)Ca,b,:f(x)Ca,b,单调，单调，f(a)f(b)0 f(a)f(b)0 f(x)=0 f(x)=0在在(a,b)(a,b)有惟一根。有惟一根。根分离：画草图，试算根分离：画草图，试算.多项式方程根模多项式方程根模 上下界。上下界。第第32页页例例2.1 2.1 用二分法求用二分法求 在在(1,2)(1,2)内根，要求绝对误差不超出内根，要求绝对误差不超出 解解：f(1)=-50-(1,2)+f(1.25)0(1.25,1.375)f(1.313)0(1.313,1.375)f(1.344)0(1.344,1.375)f(1.360)0(1.360,1.368)f(1.5)0(1,1.5)第第33页页 优点：条件简单优点：条件简单.缺点：收敛慢缺点：收敛慢.不易求偶数重根不易求偶数重根.如图如图，则则 （事后预计事后预计）xy第第34页页 2.2 2.2 迭代法迭代法一一.迭代法建立与收敛性迭代法建立与收敛性第第35页页第第36页页2.2.收敛定理（定理收敛定理（定理2.22.2）第第37页页第第38页页(2)(2)，故收敛。，故收敛。()1第第39页页(3)(3)注：注：L L越小，收敛越快。越小，收敛越快。第第40页页3 3编程停机判断编程停机判断（取定初值（取定初值）计算，当）计算，当时，由（）时，由（）3 3 式知式知 比较小，此时停机，比较小，此时停机，二、迭代加速公式（略）二、迭代加速公式（略）由由第第41页页 2.3 2.3Newton Newton 迭代法迭代法一一 Newton Newton 迭代法迭代法 1.1.迭代公式建立迭代公式建立 在在 点点TaylorTaylor展开展开 TaylorTaylor展开线性化（主要思想）展开线性化（主要思想）近似于近似于解出解出 记为记为，则，则 将将第第42页页2.Newton2.Newton迭代法几何意义迭代法几何意义 过过 切线切线 与与 求交点，解出求交点，解出 ,则则第第43页页3.Newton3.Newton迭代法收敛定理（定理迭代法收敛定理（定理 2.6 2.6）在在有根有根，且，且在在（1 1）连续，且分别不变号；连续，且分别不变号；,使使则则 Newton Newton 迭代法（迭代法（2.12.1）产生数列）产生数列收敛到根收敛到根。为例证实（其它情况类似）为例证实（其它情况类似）（2 2）取初值取初值设设 证：证：以以第第44页页将将 处处TaylorTaylor展开展开 说明数列说明数列 有下界有下界 又又 故故单调递减。单调递减。收敛。设收敛。设则由（则由（2.12.1），），第第45页页例例2.22.2 解：设解：设取取，则由（，则由（2.12.1）用用 Newton Newton 迭代法求迭代法求第第46页页基本要求基本要求1.1.熟悉区间分法；熟悉区间分法；2.2.熟悉迭代法建立，会使用收敛定理；熟悉迭代法建立，会使用收敛定理；3.3.熟悉熟悉NewtonNewton迭代法及其几何意义和收敛条件。迭代法及其几何意义和收敛条件。作业：作业：习题习题4 4：1 1、2 2、3 3、4 4、6 6第第47页页 计算方法计算方法二二.迭代法收敛阶迭代法收敛阶(收敛速度收敛速度)1.1.定义定义:设设 若有实数若有实数p0,p0,使使 则称则称 p p阶收敛阶收敛,对应迭代法称为对应迭代法称为p p阶方法阶方法.尤其尤其,p=1p=1时叫线性收敛时叫线性收敛,p=2p=2时叫平方收敛时叫平方收敛.p p越大越好越大越好(why?)(why?)第第48页页2.2.定理定理2.72.7 第第49页页 所以，此时所以，此时NewtonNewton法最少二阶收敛法最少二阶收敛.(2)(2)由由2.62.6证实有：证实有：第第50页页3.Newton3.Newton法改进：法改进：2.4 2.4 弦截法弦截法(略略)第第51页页第三章第三章 线性代数方程组解法线性代数方程组解法解线性方程组解线性方程组 第第52页页一、一、GaussGauss消去法消去法设设 有有线性代数：方法不好时工作量非常大，线性代数：方法不好时工作量非常大，工作量小方法是工作量小方法是 Gauss Gauss 消去法。消去法。消消 元：元：3.1 3.1直接法直接法第第53页页二二 列主元素消去法列主元素消去法-计算结果可靠计算结果可靠第第54页页到此原方程组化为到此原方程组化为 第第55页页 到此原方程组化为到此原方程组化为第第56页页（3.3)3.3)是回代过程。是回代过程。(上三角方程组上三角方程组)（3.2)3.2)(n)(n)回代求解公式回代求解公式 (n-1)(n-1)原方程组化为原方程组化为以上为消元过程。以上为消元过程。（3.3)3.3)第第57页页三、三、Gauss Gauss 全主元消去法：全主元消去法：优点优点-计算结果更可靠；计算结果更可靠；缺点缺点-挑主元花机时更多，挑主元花机时更多，次序有变动，程序复杂。次序有变动，程序复杂。说明：说明：(1)(1)也可采取无回代列主元消去法也可采取无回代列主元消去法(叫叫Gauss-Gauss-Jordan -Jordan消去法消去法)，但比有回代列主元消，但比有回代列主元消 去法乘除运算次数多。去法乘除运算次数多。(2)(2)有回代列主元消去法所进行乘除运算有回代列主元消去法所进行乘除运算 次数为次数为 ，量很小。，量很小。第第58页页 四、应用四、应用 （1）求行列式）求行列式 （2）求逆矩阵）求逆矩阵 (以上过程都应选主元以上过程都应选主元)第第59页页 记记，则，则 （三角因子分解）（三角因子分解）Gauss Gauss消元，初等行变换，化原方程组为上三角型。消元，初等行变换，化原方程组为上三角型。五矩阵三角分解法五矩阵三角分解法第第60页页定义定义3.13.1 叫叫三角（因子）分解，其中三角（因子）分解，其中 是是是上三角。是上三角。下三角下三角,为单位下三角阵（对角元全为为单位下三角阵（对角元全为1 1），），为上三角阵，则称为上三角阵，则称 为为DoolittleDoolittle分解分解;若若 是下三角，是下三角，是单位上三角，则称是单位上三角，则称定理定理3.1 n3.1 n阶阵阶阵 有唯一有唯一DoolittleDoolittle分解分解(Crout(Crout）前前n-1n-1个次序主子式不为个次序主子式不为0.0.（证略）（证略）三角分解不唯一三角分解不唯一,为此引入为此引入定义定义3.2 3.2 若若 为为CroutCrout分解。分解。第第61页页 为何要讨论三角分解？若在消元法进行前能实为何要讨论三角分解？若在消元法进行前能实 现三角分解现三角分解 ，则则 轻易回代求解轻易回代求解第第62页页回代求解很轻易，如回代求解很轻易，如 第第63页页基本要求：基本要求：1.1.熟悉收敛阶定义；熟悉收敛阶定义；2.2.熟悉熟悉NewtonNewton法及改进方法收敛阶；法及改进方法收敛阶；3.3.熟悉列主元消去法解线性方程组计算熟悉列主元消去法解线性方程组计算 过程；过程；4.4.熟悉矩阵三角分解中熟悉矩阵三角分解中DoolittleDoolittle分解和分解和 Crout Crout分解定义；分解定义；5.5.熟悉利用三角分解来求解线性方程组熟悉利用三角分解来求解线性方程组 思绪；思绪；作业：作业：作业集（作业集（A A）第三章第三章 1 1，2 2 第第64页页计算方法计算方法1 1直接三角分解法（以直接三角分解法（以DoolittleDoolittle分解为例）设分解为例）设 第第65页页由矩阵乘法由矩阵乘法第第66页页(k)第第67页页第第68页页第第69页页例例3 31 1选主元三角分解法（略）选主元三角分解法（略）第第70页页2 2平方根法平方根法定理定理3.23.2 设设A A对称正定，则有非奇异下三角阵对称正定，则有非奇异下三角阵L L，使，使 -理论基础理论基础 (证略）证略）分解方法：设分解方法：设(choleskey(choleskey分解分解)第第71页页第第72页页第第73页页六、解三对角方程组六、解三对角方程组追赶法追赶法(Crout分解分解)第第74页页第第75页页 ,故有故有 (3.1)第第76页页解解解解 (3.1)(3.1)(3.3)(3.3)叫追赶法，工作量小，非常有效。叫追赶法，工作量小，非常有效。(3.2)(3.2)（3.33.3）第第77页页基本要求基本要求1.1.会矩阵直接三角分解法过程（不记公式）；会矩阵直接三角分解法过程（不记公式）；2.2.熟悉平方根法计算过程（不记公式）及其优缺熟悉平方根法计算过程（不记公式）及其优缺 点。点。作业：作业：作业集（作业集（A A）第三章第三章 3.3.第第78页页一一.简单迭代法简单迭代法 1.1.迭代法建立迭代法建立.考虑考虑 (矩阵矩阵B B不唯一不唯一)对应写出对应写出 3.2 3.2 解线性方程组迭代法解线性方程组迭代法 计算方法计算方法产生向量序列产生向量序列若收敛若收敛,记记第第79页页则于则于(3.4)(3.4)两端取极限有：两端取极限有：上式说明：上式说明：是解向量是解向量,从而当从而当k k充分大时充分大时注意注意:迭代阵迭代阵B B不唯一不唯一,影响收敛性。影响收敛性。解向量解向量(1)(1)叫简单迭代法叫简单迭代法,B,B叫迭代矩阵。叫迭代矩阵。2.2.收敛性收敛性.定义定义3.3 3.3 称称 为矩阵为矩阵B B谱半径。谱半径。定理定理3.3 3.3 简单迭代法简单迭代法 第第80页页 定理定理3.43.4 第第81页页 收敛列解收敛列解 (i=1,2,(i=1,2,n),n)即即=0,=0,例例3.2 3.2 设有方程组设有方程组(其中其中 )Ax=b,)Ax=b,即即 (3.5)(3.5)作等价变形作等价变形(3.6)(3.6)第第82页页-Jacobi-Jacobi迭代法迭代法于是有迭代公式于是有迭代公式(k=0,1,2,(k=0,1,2,)(3.7)(3.7)第第83页页矩阵形式为：矩阵形式为：第第84页页(3)(3)设方程组（设方程组（3.53.5）系数矩阵）系数矩阵A A按行严格对角占优即：按行严格对角占优即：或按列严格对角占优，即或按列严格对角占优，即二、二、迭代法迭代法 设有简单迭代法设有简单迭代法 即即(3.8)(3.8)第第85页页 称以下迭代法称以下迭代法(3.9)(3.9)为与为与(3.8)(3.8)对应对应 迭代法，其迭代矩阵迭代法，其迭代矩阵 可用可用 “代入法代入法”求得。求得。第第86页页 （1 1）迭代法迭代法(3.9)(3.9)对任意对任意 收敛收敛（2 2）若）若 则则 迭代法迭代法(3.9)(3.9)对对 任意任意 收敛；收敛；（3 3）若简单迭代法）若简单迭代法(3.8)(3.8)迭代矩阵迭代矩阵 满满 足足 或或 ，则对应，则对应SeidelSeidel迭代法迭代法 (3.9)(3.9)对任意对任意 收敛（证略）收敛（证略）迭代法迭代法(3.9)(3.9)收敛性收敛性第第87页页 例例3.3 3.3 迭代方法迭代方法 （3.103.10）称为与称为与JacobiJacobi迭代法（迭代法（3.73.7）对应）对应SeidelSeidel方法方法,其收敛情况以下：其收敛情况以下：(1)(1)使用普通使用普通SeidelSeidel方法（方法（3.93.9）收敛性判别法）收敛性判别法(2)(2)若系数矩阵若系数矩阵A A对称正定，则求解方程组（对称正定，则求解方程组（3.53.5）与与JacobiJacobi迭代法对应迭代法对应SeidelSeidel方法（方法（3.103.10）对任意）对任意 收敛。收敛。（证略）（证略）第第88页页 松弛因子松弛因子,=1,=1 即即SeidelSeidel方法方法(3.10)(3.10)(3)(3)若系数矩阵若系数矩阵A A按行（或按列）严格对角占优，则按行（或按列）严格对角占优，则 求解（求解（3.53.5）与）与JacobiJacobi方法对应方法对应ScidelScidel方法方法 （3.103.10）对任意）对任意 收敛收敛.（练习）（练习）(3.11)(3.11)是一个加权平均。是一个加权平均。三三.逐次超松弛迭代法逐次超松弛迭代法(SOR(SOR法法)第第89页页SORSOR方法收敛性以下（不加证实）：方法收敛性以下（不加证实）：(1)SOR(1)SOR方法对任意方法对任意 都收敛必要条件是：都收敛必要条件是：(2)(2)若系数矩阵若系数矩阵A A对称正定，则对称正定，则 时时SORSOR方法方法 求解求解 对任意对任意 收敛；收敛；(3)(3)若系数矩阵若系数矩阵A A按行（或按列）严格对角占优，按行（或按列）严格对角占优，则则 时时SORSOR方法对任意方法对任意 收敛。收敛。最正确松弛因子最正确松弛因子 选取问题。选取问题。第第90页页 例例3.4 3.4 用用SeidelSeidel迭代法求解方程组迭代法求解方程组解解：因为系数矩阵严格对角占优，故因为系数矩阵严格对角占优，故SeidelSeidel方方 法对任意法对任意 收敛。收敛。取初始向量取初始向量,要求要求 时迭代终止。时迭代终止。Seidel Seidel迭代格式为迭代格式为第第91页页计算结果可列表以下计算结果可列表以下 注意：未必注意：未必SeidelSeidel方法一定比方法一定比JacobiJacobi方法好。方法好。第第92页页1 1 熟悉简单迭代法及其收敛条件使用；熟悉简单迭代法及其收敛条件使用；2 2 熟悉熟悉JacobiJacobi迭代法及其对应迭代法及其对应SeidelSeidel迭代法迭代法 计算公式以及它们收敛条件；计算公式以及它们收敛条件；3 3 熟悉熟悉SORSOR方法计算公式及其收敛条件；方法计算公式及其收敛条件；作业：作业：作业集作业集(A)(A)第三章第三章 4 4，5 5，6 6，7 7基本要求：基本要求：第第93页页 复习：复习：线代：线代：1.1.定义：若定义：若 则则 叫叫A A特征特征 值，值，叫其对应特征向量。叫其对应特征向量。说明说明 还是特征向量。还是特征向量。2.2.求法求法 十分困难十分困难;应寻求近似解法应寻求近似解法,且简单、且简单、可行、有效。可行、有效。计算方法计算方法 第四章第四章 矩阵特征值和特征向量计算矩阵特征值和特征向量计算第第94页页设设A A特征值特征值 特征向量特征向量4.14.1乘幂法与反幂法乘幂法与反幂法一乘幂法一乘幂法求求A A主特征值（按模最大者）及主特征值（按模最大者）及 其对应特征向量其对应特征向量 （假定（假定线形无关线形无关）第第95页页第第96页页第第97页页说明说明:有算法：有算法：第第98页页第第99页页第第100页页第第101页页6.6.几何解释几何解释第第102页页解：解：第第103页页 二反幂法二反幂法求求A A按摸最小特征值按摸最小特征值。设设A可逆，由可逆，由第第104页页对实对称矩阵对实对称矩阵A A全部特征值及特征向量全部特征值及特征向量 JacobiJacobi旋转法旋转法基本思想：基本思想：求普通矩阵全部特征值和特征向量求普通矩阵全部特征值和特征向量QRQR方法方法 参考书。参考书。4.2Jacobi旋转法旋转法第第105页页1.熟悉特征值和特征向量定义；熟悉特征值和特征向量定义；2.熟悉乘幂法求主特征值计算过程；熟悉乘幂法求主特征值计算过程；3.了解反幂法思绪；了解反幂法思绪；基本要求基本要求：作业：作业：作业集（作业集（A）第四章）第四章1.第第106页页 第二章第二章插值法插值法第第107页页第第108页页注注:不用待定系数法不用待定系数法-(1)-(1)计算量大计算量大;(2);(2)不易讨论误不易讨论误 差差;二次多项式插值二次多项式插值-过两点直线过两点直线;三次多项式插值三次多项式插值-过三点抛物线过三点抛物线;3.几何意义几何意义第第109页页插值满足条件插值满足条件:找一个多项式找一个多项式满足满足:1.2.p(x)是一个次数不超出是一个次数不超出n多项式多项式第第110页页一一.插值基函数插值基函数.2.1Lagrange插值公式插值公式第第111页页二二.Lagrange.Lagrange插值多项式插值多项式第第112页页三三截断误差：截断误差：第第113页页一差商一差商2.2 Newton2.2 Newton插值公式插值公式1.定义定义第第114页页3.3.造差商表造差商表(实用实用)第第115页页二二NewtonNewton插值公式插值公式第第116页页第第117页页第第118页页第第119页页解：先造差商表解：先造差商表第第120页页由由Newton公式得四次插值多项式为：公式得四次插值多项式为：第第121页页1.熟悉插值法含义及其几何意义；熟悉插值法含义及其几何意义；2.熟悉熟悉Lagrange插值公式及其余项使用；插值公式及其余项使用；3.会造差表，并熟悉会造差表，并熟悉Newton插值公式使用；插值公式使用；4.熟悉差商与导数关系式。熟悉差商与导数关系式。基本要求：基本要求：作业：作业：P40-41:2，3,4,5,6,8,13,14第第122页页 牛顿基本插值公式对结点是否等矩没有牛顿基本插值公式对结点是否等矩没有限制限制.不过当结点等距时前述牛顿插值公式可不过当结点等距时前述牛顿插值公式可进行简化进行简化.为此先介绍差分概念为此先介绍差分概念.2.3等矩结点插值公式等矩结点插值公式第第123页页1.1.定义定义 设设 为为 在在以以h h为为步长一阶向前差分步长一阶向前差分 m m阶阶一一.差分差分叫步长叫步长称称普通普通:一阶一阶二阶二阶第第124页页(1)(1)差分可表为函数值线性组合差分可表为函数值线性组合 (证略证略)(2)(3)2.性质性质:(2)(证实用归纳法证实用归纳法,略略)3.差分表差分表(实用实用)第第125页页二二 等矩结点插值公式等矩结点插值公式:将将NewtonNewton插值公式插值公式 中差商用性质中差商用性质(2)(2)换为差分换为差分,可整理为以下可整理为以下NewtonNewton向前插值公式向前插值公式设设（5.65.6）第第126页页截断误差可表示为截断误差可表示为 (5.7)(5.7)NewtonNewton向后插值公式及向后插值公式及BesselBessel插值公式插值公式 参考文件参考文件第第127页页5.4 Hermite5.4 Hermite插值介绍插值介绍前述插值问题前述插值问题:要求被插函数与插值多项式在结点取要求被插函数与插值多项式在结点取 相同值相同值,Lagrange Lagrange型插值条件型插值条件 然而然而,实际许多问题还经常要求两曲线深入有共同切线实际许多问题还经常要求两曲线深入有共同切线:插值插值条件为条件为:求一次数求一次数多项式多项式,使之满足给定使之满足给定HermiteHermite型插值条件型插值条件 (5.8)(5.8)第第128页页求求不用待定系数法不用待定系数法.可设可设 其中其中，且，且插值基函数表示法插值基函数表示法（5.9）（5.10）（5.11）第第129页页满足条件（满足条件（5.105.10）和（）和（5.115.11）多项式（）多项式（5.95.9）一一定满足（定满足（5.85.8），故即为所求），故即为所求所以主要是求插值基函数所以主要是求插值基函数可借用可借用LagrangeLagrange插值基函数插值基函数得公式得公式 （5.375.37）有规律有规律余项余项易验证：易验证：第第130页页例例5.3 5.3 给定函数值表以下给定函数值表以下:第第131页页第第132页页第第133页页问题：结点增多，多项式次数增高，迫近精度越问题：结点增多，多项式次数增高，迫近精度越 好？未必！多结点高次插值往往在局部误好？未必！多结点高次插值往往在局部误 差更大差更大RungeRunge现象。现象。实用：采取分段低次插值实用：采取分段低次插值 有分段线形，分段二次插值等，几何上有分段线形，分段二次插值等，几何上5.5三次样条插值介绍三次样条插值介绍1.分段插值法：分段插值法：缺点：分段插值函数只能确保连续性，缺点：分段插值函数只能确保连续性，不能确保光滑性。不能确保光滑性。折线代替曲线第第134页页 分段插值能够得到整体连续函数，但在连分段插值能够得到整体连续函数，但在连 接点处普通不光滑，而接点处普通不光滑，而HermiteHermite插值即使插值即使 在连节点处一阶光滑，但整体插值因为结在连节点处一阶光滑，但整体插值因为结 点多，次数高而有可能发生点多，次数高而有可能发生RungeRunge现象。现象。2.2.三次样条插值三次样条插值既想分段插值，又想在结点处保持光滑，既想分段插值，又想在结点处保持光滑，甚至二阶光滑甚至二阶光滑三次样条。三次样条。希望：希望：样条起源：样条起源：第第135页页1.1.定义：在定义：在a,ba,b上取上取n+1n+1个点个点 若函数若函数S(x)S(x)满足：满足：此时此时S(x)S(x)叫插值函数；叫插值函数；(3)在内结点或在整个区间上具二阶连续导数。在内结点或在整个区间上具二阶连续导数。则称则称S S(x)为为y=f(y=f(x)三次样条插值函数。三次样条插值函数。(2)在每个小区间在每个小区间上是三次多项式；上是三次多项式；2.结构：有两种方法，导出三对角方程组，用追结构：有两种方法，导出三对角方程组，用追赶法。赶法。(1)第第136页页三次样条插值三次样条插值n分段线性插值优点分段线性插值优点：计算简单、稳定性好、收敛性有确保且易在计算机上实现n 缺点缺点：它只能确保各小段曲线在连接点连续性，却无法确保整条曲线光滑性，这就不能满足一些工程技术要求。n三次三次Hermit插值优点插值优点：有很好光滑性，缺点缺点：要求节点一阶导数已知。n从世纪年代开始，首先因为航空、造船等工程设计需要而发展起来所谓样条(Spline)插值方法，既保留了分段既保留了分段低次插值多项式各种优点，又提升了插值函数光滑性。低次插值多项式各种优点，又提升了插值函数光滑性。今天，样条插值方法已成为数值迫近一个极其主要分支，在许多领域里得到越来越多广泛应用。n 我们介绍应用最广具二阶连续导数三次样条插值函数。第第137页页一、三次样条插值函数定义：一、三次样条插值函数定义：n给定区间 上个节点 和这些点上函数值 n若 满足：n（1）；n（2）在每个小区间 上至多是一个三次多项式；n（3）在 上连续。n则 称为函数 关于节点 三次样三次样条插值函数。条插值函数。第第138页页二、边界问题提出与类型二、边界问题提出与类型n单靠一个函数表是不能完全结构出一个三三次样条插值函数。次样条插值函数。我们分析一下其条件个数，条件（2）三次样条插值函数 是一个分段三次多项式，若用 表示它在第 i个子区间 上表示式，则 形如:第第139页页n其中有四个待定系数 ，子区间共有 n个，所以共有共有4n个待定系数。个待定系数。n由条件（由条件（3）在在上连续，上连续，即它们在各个子区间上连接点即它们在各个子区间上连接点上连续即可，共有上连续即可，共有4n-2个条件，即个条件，即第第140页页n 共有3(n-1)+(n+1)=4n-2个条件，未知量个数是 n个。这么需要加这么需要加2个条件个条件。n这两个条件通常在插值区间边界点a,b处给出，称为边界条件。边界条件类型很多，常见有：n(1)给定一阶导数值给定一阶导数值n(2)给定一阶导数值n（尤其地 时称为自然边界条件，满足自然边界条件次样条插值函数称为自然样条次样条插值函数称为自然样条插值函数）插值函数）n（3)当 是周期为b-a函数时，要求 及其导数都是以b-a为周期函数，对应边界条件为：第第141页页见word 文档第第142页页熟悉差分定义，会造差分表；熟悉差分定义，会造差分表