数值分析第五版章PPT课件

1、2022-2-3第1章 数值分析与科学计算引论1第1章 数值分析与科学计算引论数值分析与科学计算引论数值分析研究对象、作用与特点数值计算的误差误差定性分析与避免误差危害数值计算中算法设计的技术数学软件第1页/共90页2022-2-3第1章 数值分析与科学计算引论2研究对象作用特点数值计算误数值计算误差差误差分析避误差分析避免危害免危害数值计算算数值计算算法设计法设计数学软件数学软件1 1 研究对象 用计算机求解数学问题的数值计算方法、理论及软件实现 实际问题 数学模型 数值计算方法 程序设计（数学软件） 上机计算求出结果应用数学计算数学即数值分析数值分析（计算方法）的研究对象(理论与计算结合)

2、插值与函数逼近（2、3）数值微分与数值积分（4）非线性方程数值解（7）数值线性代数（5、6、8）常微与偏微分方程的数值解（9）等1.1 1.1 数值分析的对象、作用与特点数值分析的对象、作用与特点第2页/共90页2022-2-3第1章 数值分析与科学计算引论3研究对象作用特点数值计算误数值计算误差差误差分析避误差分析避免危害免危害数值计算算数值计算算法设计法设计数学软件数学软件例 考虑线性方程组数值解问题相关理论与精确解法根据方程的特点研究算法及相关理论纯数学计算数学Axb3 数值分析特点 面向计算机提供有效算法； TSP问题 可靠的理论分析（精度、收敛、稳定）; 好的计算复杂性（时、空）;阿

3、基米德、刘徽、祖冲之 数值实验 B.C. 3 A.D.3 A.D.52 数值分析作用 科学研究的手段：科学理论、科学实验与科学计算Axb第3页/共90页2022-2-3第1章 数值分析与科学计算引论4研究对象作用特点数值计算误差误差分析避误差分析避免危害免危害数值计算算数值计算算法设计法设计数学软件数学软件1.2 1.2 数值计算的误差数值计算的误差1 误差分类模型误差: 数学模型 实际问题观测误差: 由观测产生截断误差/方法误差: 近似解 精确解舍入误差:计算机字长的限制(不讨论)2 误差与有效数字记x为准确值，x* 为 x的一个近似值 定义1 称 为近似值 的绝对误差，简称误差。xxe *

4、x强近似值: 当弱近似值: 当00* ee第4页/共90页2022-2-3第1章 数值分析与科学计算引论5研究对象作用特点数值计算误差误差分析避误差分析避免危害免危害数值计算算数值计算算法设计法设计数学软件数学软件误差限: 误差绝对值的上界(不能完全反映近似值的好坏)* xx相对误差:)(*实际中取值或xxxxeexxxxer相对误差限: (可反映出近似程度的好坏)*xr 定义2 有效数字 若近似值 的误差限是某一位的半个单位，该位到 的 第一位非零数 字共有n位，就说 有n位有效数字。*x*x*x*1(1)121*110(1010),011023.143.1413.mnlm nxaaaaxn

5、xx 设若 有位 有效数字，则例：和作为 的近似值都是 位有效数字003. 1,00314. 110001003. 0,00314. 01000*yyxx第5页/共90页2022-2-3第1章 数值分析与科学计算引论6注: 有效位数与小数点后有多少位无关； m相同情况下，有效位数越多，误差限越小； 相对误差及相对误差限是无量纲的，绝对误差及误差限是有量纲的。研究对象作用特点数值计算误数值计算误差差误差分析避误差分析避免危害免危害数值计算算数值计算算法设计法设计数学软件数学软件*1(1)121*(1)1*(1)1*110(1010)(1,2, )090.,:11021102(1).mllinrn

6、rxxaaaa ilamxnaxaxn 定理 ：设近似数 表示为其中是 到 中的一个数字， 为整数若 具有 位有效数字 则其相对误差限为反之，若 的相对误差限则 至少具有 位有效数字第6页/共90页2022-2-3第1章 数值分析与科学计算引论7研究对象作用特点数值计算误数值计算误差差误差分析避误差分析避免危害免危害数值计算算数值计算算法设计法设计数学软件数学软件3 数值运算的误差估计*1212*1212*122112*2112*122*21.,(), (),:()()();()()();()()(/)xxxxxxxxx xxxxxxxxxxxx与为两近似数 误差限为则)()()(:)(2)(

7、)()()()()Taylor(.2*2*xxfxfxfxxfxfxf 忽略高阶项展开利用一元函数误差限nkkkrnkkknAxxfAxxfAxxfATaylor1*1*1)()()(, )()()(),()(. 3展式多元函数多元函数误差限第7页/共90页2022-2-3第1章 数值分析与科学计算引论8研究对象作用特点数值计算误数值计算误差差误差分析避误差分析避免危害免危害数值计算算数值计算算法设计法设计数学软件数学软件1.3 1.3 误差定性分析及避免误差危害误差定性分析及避免误差危害概率分析法 向后误差分析法 区间分析法1. 病态问题与条件数病态问题输入(微小的扰动) 输出(相对误差很大

8、)条件数pC)()()()()()()()()()(*xfxf xxxxfxfxfCxfxfxfxfexxexxxxxfprr有微小的扰动，对于即认为是病态即认为是病态10 pC( )nf xx第8页/共90页2022-2-3第1章 数值分析与科学计算引论9研究对象作用特点数值计算误数值计算误差差误差分析避误差分析避免危害免危害数值计算算数值计算算法设计法设计数学软件数学软件2. 算法的数值稳定性定义3 一个算法如果输入数据有误差，而在计算过程中舍入误差不增长，则称此算法是数值稳定的，否则称此算法为不稳定 的。例1.1：P.110nxnIex e dx, 2 , 1 , 0n)1 (10684

9、. 0)(0684. 0)10110(21,10110,111552. 7,7280. 016321. 03679. 01)(1,1*1*9*9199119810110nnnnnnnInIIBIeIIenIneIIInIIAnIIeI第9页/共90页2022-2-3第1章 数值分析与科学计算引论106321. 0,3679. 0,2643. 0,2073. 0,1708. 0,1455. 0,1268. 0,1121. 0,1035. 0,0684. 0)1 (10684. 0)(0684. 0)10110(21,10110,111552. 7,7280. 0,2160. 0,1120. 0,

10、1480. 0,1704. 0,2074. 0,2642. 0,3679. 0,6321. 016321. 03679. 01)(1,1*0*1*2*3*4*5*6*7*8*9*1*9*919911987654321010110IIIIIIIIIIInIIBIeIIenIneIIIIIIIIIIInIIAnIIeInnnnnnn研究对象作用特点数值计算误数值计算误差差误差分析避误差分析避免危害免危害数值计算算数值计算算法设计法设计数学软件数学软件000025. 0 3679. 0Rerror truncation! 7) 1(! 2) 1() 1(1!177210eenxennx第10页/共9

11、0页2022-2-3第1章 数值分析与科学计算引论11研究对象作用特点数值计算误数值计算误差差误差分析避误差分析避免危害免危害数值计算算数值计算算法设计法设计数学软件数学软件3. 误差危害的避免（1）避免除数的绝对值远远小于被除数绝对值的除法；）避免除数的绝对值远远小于被除数绝对值的除法；（2）避免两相近数相减，引起有效数字严重损失；）避免两相近数相减，引起有效数字严重损失；（3） 防止大数吃小数；防止大数吃小数；（4） 简化计算简化计算 步骤，减少运算次数；步骤，减少运算次数；秦九韶、秦九韶、Horner（5） 数值稳定性。数值稳定性。)(xPn01101111000001)()() 1(1

12、00000axaxaxaaxaxaxaxPnnnnnnniiixxxx1111sin22cos110000000032. 0123456789020）（）秦九韶方法（1837-17861268-1208methodsHorner第11页/共90页2022-2-3第1章 数值分析与科学计算引论12研究对象作用特点数值计算误数值计算误差差误差分析避误差分析避免危害免危害数值计算算法设计数学软件数学软件算法设计的三种基本技术（1）化大为小的缩减技术）化大为小的缩减技术 Zeno悖论悖论 古希腊哲学家古希腊哲学家 结绳记数（结绳记数（13）10=（1101）2（2）化难为易的校正技术）化难为易的校正技

13、术 用四则运算计算开方用四则运算计算开方（3）化粗为精的松弛技术）化粗为精的松弛技术a1.1. 数值计算中算法设计的技术数值计算中算法设计的技术19219296307236()3.1416105SSSSSxxxxaxxa0102, 0,也永远追不上乌龟。一个人不管跑得多快，VUiSV1iSU周易.系辞下说：“上古结绳而治，后世圣人（伏羲）易之以书契“。第12页/共90页2022-2-3第1章 数值分析与科学计算引论13谢谢谢谢!第一章习题第一章习题1, 5,12,1第13页/共90页2022-2-3第2章 插值法14第2章 插值法插值法引言拉格朗日（Lagrange）插值均差与牛顿（Newto

14、n）插值埃尔米特（Hermite）插值分段低次插值三次样条插值第14页/共90页2022-2-3第2章 插值法15引言拉格朗日拉格朗日插值插值牛顿插值牛顿插值埃尔米特埃尔米特插值插值分段低次分段低次插值插值三次样条插三次样条插值值2.1 2.1 引言引言 在科学计算中经常要用较简单的函数来逼近较复杂的函数。按函数逼近问题提法的不同，通常有插值、函数逼近及曲线拟合等三种问题。)(xfy bxxxan10nyyy,10)(xp（1）插值 设函数在点上的函数值分别为，求一简单函数 ，使 （2.1）), 1 , 0()(niyxpii 0 0y( )yf x( )yp xnyy0 xnxx0 第15页

15、/共90页2022-2-3第2章 插值法16nxxx,10,ba)(xf)(xp)(xf)(xp称点为插值节点，区间为插值区间，为被插值函数，为的插值函数。引言拉格朗日拉格朗日插值插值牛顿插值牛顿插值埃尔米特埃尔米特插值插值分段低次分段低次插值插值三次样条插三次样条插值值 由于多项式具有结构简单，数值计算和理论分析都很方便的优点，因此通常取 为多项式。相应的插值法称为多项式插值。 nnxaxaxaaxp2210)(第16页/共90页2022-2-3第2章 插值法17引言拉格朗日拉格朗日插值插值牛顿插值牛顿插值埃尔米特埃尔米特插值插值分段低次分段低次插值插值三次样条插三次样条插值值A,baBAA

16、xf)(Bxp)()(xp)(xf（2）函数逼近 设 为定义在区间 上的某类函数构成的线性空间， 为 的子集，对于 ，求 ，使 与 的差在某种度量意义下最小，这就是函数逼近问题。AB 通常取为连续函数空间，而 通常是多项式、有理函数或三角多项式函数等。)()(xpxf2)()(xpxf另一种是2-范数对应的函数逼近分别称为最佳一致逼近和最佳平方逼近。常用的度量标准有两种：一种是-范数第17页/共90页2022-2-3第2章 插值法18引言拉格朗日拉格朗日插值插值牛顿插值牛顿插值埃尔米特埃尔米特插值插值分段低次分段低次插值插值三次样条插三次样条插值值)(xfy ), 1 , 0(),(miyxi

17、i)(),;(10mnaaaxgyn), 1 , 0(nkakix), 2 , 1 , 0(),;(10miyaaaxginiimii02（3）曲线拟合 设已知函数 的数据点为，在某一函数类中求函数其中为待定系数，使在节点 处的误差的平方和最小。第18页/共90页2022-2-3第2章 插值法19引言拉格朗日插值牛顿插值牛顿插值埃尔米特埃尔米特插值插值分段低次分段低次插值插值三次样条插三次样条插值值2.2 2.2 拉格朗日插值n次插值多顶式：nnxaxaaxP 10)(1 线性插值（一次）线性插值（一次）11111111)()()()(),(,1kkkkkkkkkkyxLyxLxLxfyxfy

18、xxn，满足：要求线性插值多项式已知，区间， y O x xk xk+1 yk yk+1)()(1xfxL对称式点斜式1111111)()(kkkkkkkkkkkkkkyxxxxyxxxxxxxxyyyxL第19页/共90页2022-2-3第2章 插值法20引言拉格朗日插值牛顿插值牛顿插值埃尔米特埃尔米特插值插值分段低次分段低次插值插值三次样条插三次样条插值值1)(, 0)(, 0)(, 1)()()(01)(1)(, 0)(, 0)(, 1)()(,)(1111111111111111kkkkkkkkkkkkijjikkkkkkkkkkkkkkkkxlxlxlxlyxLyxLjijixlxl

19、xlxlxlxxxxxlxxxxxl与，比较条件，或，满足其中插值基函数对称式点斜式111111111)()()()(kkkkkkkkkkkkkkkkkkyxlyxlyxxxxyxxxxxxxxyyyxL x y O xk xk+1 1)()(1xlxlkk111)()(kkkkkxxxxxxcxl 利用函数的零点及一次多项式性质，由待定系数法可求得第20页/共90页2022-2-3第2章 插值法21引言拉格朗日拉格朗日插值插值牛顿插值牛顿插值埃尔米特埃尔米特插值插值分段低次分段低次插值插值三次样条插三次样条插值值2 抛物插值（二次）抛物插值（二次）), 1(0)(, 1)() 1, 1(,

20、0)(, 1)() 1,(, 0)(, 1)()()()()()(),(),(, 2111111111122112211111,1kkjxlxlkkjxlxlkkjxlxlxlxlxlyxLyxLyxLxLxfyxfyxfyxxxnjkkkjkkkjkkkkkkkkkkkkkkkkkkkkk）分别满足：）及），转化为求，满足：要求二次插值多项式，已知节点)()()(,)()()(,)()()(11111111111111kkkkkkkkkkkkkkkkkkkkkxxxxxxxxxlxxxxxxxxxlxxxxxxxxxl 由待定系数法可求得：)()()(11xlxlxlkkk 1 y O x1

21、1kkkxxx第21页/共90页2022-2-3第2章 插值法22引言拉格朗日拉格朗日插值插值牛顿插值牛顿插值埃尔米特埃尔米特插值插值分段低次分段低次插值插值三次样条插三次样条插值值1111111111111111112)()()()()()()()()()(kkkkkkkkkkkkkkkkkkkkkkkkkkkyxxxxxxxxyxxxxxxxxyxxxxxxxxyxlyxlyxlxL22200( )( )(0,1,2)ijijjijijjL xlx yyyi第22页/共90页2022-2-3第2章 插值法233 拉格朗日插值多项式将线性与抛物型插值推广到一般的情形), 2, 1 , 0()

22、()()()()()( )()()()( )()()(), 0,()(0)(1)(), 0()()(), 2, 1 , 0()()(,1)(000n1k1-k0n1k1-k01010njyyyxlxLLagrangeyxlxLxxxxxxxxxxxxxxxxxlnkjkjkjxlnkxlnnjyxLxLnyyyxxxnxfjnkkjkknkjkjnknkknkkkkkjkjkkjjnnnn插值多项式从而则满足：次多项式令插值基函数满足：次插值多项式求，上的函数值为，个互异节点在已知引言拉格朗日拉格朗日插值插值牛顿插值牛顿插值埃尔米特埃尔米特插值插值分段低次分段低次插值插值三次样条插三次样条插值

23、值第23页/共90页2022-2-3第2章 插值法24引言拉格朗日拉格朗日插值插值牛顿插值牛顿插值埃尔米特埃尔米特插值插值分段低次分段低次插值插值三次样条插三次样条插值值knknkjjjkjknkknknknkknnkkkkkkknnnyxxxxyxxxxyxlxLxxxxxxxxxxxxxxxx)()()()()()()()()()()()()()(0001101101101 从而则记。的插值多项式存在唯一中，满足条件的多项式集合在次数不超过定理), 1 , 0()(:1njyxLHnjjnn第24页/共90页2022-2-3第2章 插值法25引言拉格朗日拉格朗日插值插值牛顿插值牛顿插值埃尔

24、米特埃尔米特插值插值分段低次分段低次插值插值三次样条插三次样条插值值nnnxaxaxaaxL2210)(01,na aa1n行列式的互异，所以其系数构成因为eVandermond,n1022n101121211000202010 xxxyxaxaxaayxaxaxaayxaxaxaannnnnnnnn0)(1110212110200nijjinnnnnnxxxxxxxxxxxV)(xLn证明 设所求的插值多项式为 则由插值条件得关于 的线性方程组从而线性方程组有唯一解。这就证明了 的存在唯一性。的插值多项式存在唯一中，满足条件在定理), 1 , 0()(:1njyxLHjjnn第25页/共90

25、页2022-2-3第2章 插值法26引言拉格朗日拉格朗日插值插值牛顿插值牛顿插值埃尔米特埃尔米特插值插值分段低次分段低次插值插值三次样条插三次样条插值值4 插值余项与误差估计)()()()()(,xLxfxRxfxLbannn。称为插值多项式的余项，一般存在截断误差或近似上以在),()()!1()()()()(:,)()(),()(,)(:21)1(10)1()(baxnfxLxfxRbaxyxLxLbxxxabaxfbaxfnnnnjjnnnnn，插值余项何的插值多项式，则对任是满足条件，内存在，节点在上连续，在设定理)()!1()(, )(max0!1)()()(), 1 , 0(0)()

26、(),()()()()()()()(), 1 , 0(0)(11)1(1)1()1(11xnMxRxfMnxKfnkxxtxKtLtftxxKxRnkxRnnnnbxannnknnnnkn则记）（构造证明：第26页/共90页2022-2-3第2章 插值法27,12144,11121,10100115例2.1 已知 （1）用线性插值及抛物插值计算 的近似值；（2）并问它们各有几位有效数字；（3）求抛物插值的误差。115,11,10,121,1001010 xyyxx1110012110010121100121)(101001011xxyxxxxyxxxxxL71429.1011100121100

27、11510121100121115)(1151151xxL72380.10115 115解 先用线性插值计算，取 ，由线性插值公式得 所以而因此用线性插值所得 的近似值具有3位有效数字。引言拉格朗日拉格朗日插值插值牛顿插值牛顿插值埃尔米特埃尔米特插值插值分段低次分段低次插值插值三次样条插三次样条插值值第27页/共90页2022-2-3第2章 插值法28引言拉格朗日拉格朗日插值插值牛顿插值牛顿插值埃尔米特埃尔米特插值插值分段低次分段低次插值插值三次样条插三次样条插值值115,12,11,10,144,121,100210210 xyyyxxx12)121144)(100144()121)(100

28、(11)144121)(100121()144)(100(10)144100)(121100()144)(121()()()()()()()(2120210121012002010212xxxxxxyxxxxxxxxyxxxxxxxxyxxxxxxxxxL72276.10)(1151152xxL115再用抛物插值计算，取由抛物插值公式得：所以因此用抛物插值所得 的近似值具有4位有效数字。 线性插值仅用两个节点上的信息，精度自然较低，而抛物插值用了三个节点上的信息，精度通常会有所提高。72380.10115 第28页/共90页2022-2-3第2章 插值法29引言拉格朗日拉格朗日插值插值牛顿插值

29、牛顿插值埃尔米特埃尔米特插值插值分段低次分段低次插值插值三次样条插三次样条插值值25232183)( 41)( 21)( )(xxfxxfxxfxxf，则设2201202( )( )( )( )()()()(,)3!fR xf xL xxxxxxxx x52225213(115)(115)(115)(115 100)(115 121)(115 144)3! 81310015 6 290.0016368RfL 这又一次说明了用抛物插值所得的近似值具有4位有效数字。第29页/共90页2022-2-3第2章 插值法30引言拉格朗日拉格朗日插值插值牛顿插值牛顿插值埃尔米特埃尔米特插值插值分段低次分段低

30、次插值插值三次样条插三次样条插值值2.3 2.3 均差与牛顿插值均差与牛顿插值一阶均差:二阶均差:K阶均差:11102010110010000,)()(, kkkkkkkkkkkkxxxxxfxxxfxxxfxxxxfxxfxxxfxxxfxfxxf,!)(,. 3,. 2)()()()(,. 1:)(00101001100banfxxfxxxxfxxfxxfxxxxxxxxxfxxfnnkkkkkjkjjjjjjjk 性质性质承袭性承袭性1 均差及其性质第30页/共90页2022-2-3第2章 插值法31引言拉格朗日拉格朗日插值插值牛顿插值牛顿插值埃尔米特埃尔米特插值插值分段低次分段低次插值

31、插值三次样条插三次样条插值值2 牛顿插值公式)(,)(,)(,)()(:,01010110100000nnnnxxxxxfxxxfxxxfxxxxxfxxfxxfxxxxfxfxfbax可得由均差定义上一点为)()!1()()(,)()()()()(,)(,)(,)()()()()(1)1(10100102100100 xnfxxxxfxNxfxRxxxxxxfxxxxxxxfxxxxfxfxNxRxNxfnnnnnnnnnnn从而nkxxfaxxxxaxxxxaxxaaxPxNkknnnn, 1 , 0,)()()()()(:)(010102010 形如形如可克服Lagrange插值法无承袭

32、性的缺点。第31页/共90页2022-2-3第2章 插值法32引言拉格朗日拉格朗日插值插值牛顿插值牛顿插值埃尔米特埃尔米特插值插值分段低次分段低次插值插值三次样条插三次样条插值值jx)(jxf3210 xxxx)()()()(3210 xfxfxfxf,302010 xxfxxfxxf,310210 xxxfxxxf,3210 xxxxf差商表一阶差商二阶差商三阶差商第32页/共90页2022-2-3第2章 插值法33引言拉格朗日拉格朗日插值插值牛顿插值牛顿插值埃尔米特埃尔米特插值插值分段低次分段低次插值插值三次样条插三次样条插值值的近似值。插值求用二次，设115Newton,14412110

33、0)(210 xxxxxfjx1441211001211102212112322211一阶差商二阶差商)121)(100(2322211)100(21110)(,)(,)()(1021001002xxxxxxxxxxfxxxxfxfxN72276.10)121115)(100115(2322211)100115(21110)115(1152 N)(2xN例2.2解 的表达式中前两项为线性插值，加上第三项后为二次插值，与前例比较结果是相同的。)(jxf第33页/共90页2022-2-3第2章 插值法34引言拉格朗日拉格朗日插值插值牛顿插值牛顿插值埃尔米特埃尔米特插值插值分段低次分段低次插值插值三

34、次样条插三次样条插值值 前面讨论插值问题只提函数值条件，没有导数条件。有些实际问题不但要求插值函数与被插值函数在节点上函数值相同，即“过点”，而且要求导数值也相同，即“相切”，有时甚至要求高阶导数也相同。满足这种既要求函数值相同也要求导数值相同的插值多项式称为Hermite插值多项式。函数值的个数与导数值的个数可以不等也可以相等，下面分别用基于承袭性方法及基函数方法来讨论。2.4 2.4 埃尔米特插值埃尔米特插值第34页/共90页2022-2-3第2章 插值法35引言拉格朗日拉格朗日插值插值牛顿插值牛顿插值埃尔米特埃尔米特插值插值分段低次分段低次插值插值三次样条插三次样条插值值)() 1 ,

35、0()(,0010 xfyixfyxxii，)(2xH0022)() 1 , 0()(yxHiyxHii，)(1xL 先考虑函数值的个数与导数值的个数不等的情形，以一个具体问题为例进行讨论。 问题的提法为已知 ，求二次函数 ，使 这里给出了三个条件，可唯一地确定一个次数不超过二次的多项式。由于前两个条件可确定一个一次函数，正是Lagrange插值函数 ，因此可令)()()()()(100010101012xxxxcxxxxyyyxxxxcxLxH10010101()yycyxxxx10102000011010101( )()()()()yyyyHxyxxyxxxxxxxxxx从而 由第三个条件

36、得第35页/共90页2022-2-3第2章 插值法36引言拉格朗日拉格朗日插值插值牛顿插值牛顿插值埃尔米特埃尔米特插值插值分段低次分段低次插值插值三次样条插三次样条插值值1n 再考虑函数值的个数与导数值的个数相等且具有 个节点的一般情形。0)()(2)()(1)()(),()()(), 1 , 0,()(, 0)(0)()(:), 1 , 0()(),(12)()()(), 1 , 0()()()(12), 1 , 0()()(2201212121210jjjjjjjjjjjjjjjjjkkjkjkjjkkjjjnjjjjjnjjnjjnnjjjjnxlxldcxxclxxldcxxxldcx

37、xnkjxxxxnjxxnmxyxxHnjmxHyxHxHnnjxfmxfybxxxa）（）（则令，满足次插值基函数其中令，使的插值多项式求次数不超过，上，已知在节点第36页/共90页2022-2-3第2章 插值法37引言拉格朗日拉格朗日插值插值牛顿插值牛顿插值埃尔米特埃尔米特插值插值分段低次分段低次插值插值三次样条插三次样条插值值)()()()(1)(21 )(1)()()()()()()()()(21)(22200110110 xlxxxxlxxxxxxxxlxxxxxxxxxxxxxxxxxlxlxdxlcjjjjnjiiijjjnjiiijjjnjjjjjjnjjjjjjjj同理从而得

38、上式两端取对数再求导由于，解得第37页/共90页2022-2-3第2章 插值法38引言拉格朗日拉格朗日插值插值牛顿插值牛顿插值埃尔米特埃尔米特插值插值分段低次分段低次插值插值三次样条插三次样条插值值)(1n2xH)(xp。故，个零点，除非的多项式，最多存在为次数不超过个零点。但至少存在的二重根，即为则节点)()(0)(1212)(22)(0)(), 1 , 0()()()(121n2xHxqxqnnxqnxqxqnixxpxHxqni定理 满足插值条件 的多项式 是存在唯一的。证明 存在性的证明已由前面的构造而得，下面证明唯一性。 设 也是满足插值条件且次数不超过2n1的多项式，令), 1 ,

39、 0()()(1212njmxHyxHjjnjjn。第38页/共90页2022-2-3第2章 插值法39引言拉格朗日拉格朗日插值插值牛顿插值牛顿插值埃尔米特埃尔米特插值插值分段低次分段低次插值插值三次样条插三次样条插值值）（，有插值多项式，则次的为阶导数，有直到上的区间个互异节点在含有设baxnfxHxfxRbaxnxfxHnbaxxxnxfnnnnn,)()!22()()()()(,Hermite12)()(22,1)(21)22(121210 与Lagrange插值余项定理类似地有下列Hermite插值余项定理，其证明方法也相似。定理第39页/共90页2022-2-3第2章 插值法40引言

40、拉格朗日拉格朗日插值插值牛顿插值牛顿插值埃尔米特埃尔米特插值插值分段低次分段低次插值插值三次样条插三次样条插值值),()()(! 4)()()()()()()()()(21 ()()(21 ()()()(),(),()()()()()()(,)(,)(,)(110212043320101121010020101011210101001010110011003113003113003xxxxxxfxHxfxRxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxyxyxyxyxxHyxHyxHyxHyxHn，为插值基函数及其中时，特别）（ 第40页/共90页2022-2-3第2

41、章 插值法41引言拉格朗日拉格朗日插值插值牛顿插值牛顿插值埃尔米特埃尔米特插值插值分段低次分段低次插值插值三次样条插三次样条插值值3333(1)2,(2)3,(1)1,(2)1HHHH 3( )Hx从而，则令1, 1, 3, 22, 1101010yyyyxx323( )2895Hxxxx 例2.3 求满足条件 且次数不超过三的Hermite插值多项式解)()(! 4)()()()()(Hermite)()( ),()(),()(),()(),(,)(2)4(3333333bxcxaxfxHxfxRxHcfcHcfcHbfbHafaHbacbaxf的余项为插值多项式且次数不超过三次的，证明满足

42、条件上有直到四阶导数，在设例2.40)(! 4)()()()()()()()()()()()()()()()4()4(23233xKftbtctatxKtHtftbxcxaxxKxHxfxR有五个零点，从而则作设证：第41页/共90页2022-2-3第2章 插值法42引言拉格朗日拉格朗日插值插值牛顿插值牛顿插值埃尔米特埃尔米特插值插值分段低次分段低次插值插值三次样条插三次样条插值值2.5 2.5 分段低次插值分段低次插值 插值多项式的次数是随着插值节点的增加而升高的，那么插值多项式的次数越高是否意味着逼近效果越好呢？到被插值函数。，则称插值多项式收敛若)()(limxfxPnn发散。，)( ,

43、63. 3|);()(lim,63. 3|)()()(11)(), 1 , 0( ,105,5 , 511)(:11022xLxxfxLxxxxxxxLnjnjxxxfRungennnjnjnnjjnj)(10 xL211x 第42页/共90页2022-2-3第2章 插值法43引言拉格朗日拉格朗日插值插值牛顿插值牛顿插值埃尔米特埃尔米特插值插值分段低次分段低次插值插值三次样条插三次样条插值值1 分段线性插值分段线性插值 用折线来逼近曲线。用折线来逼近曲线。上是线性函数在每个小区间）,)(3), , 1 , 0()(2,)(11iihiihhxxxIniyxIbaCxI)()(11111iiii

44、iiiiiihxxxyxxxxyxxxxxI，满足：求一折线函数线性插值问题的提法为。分段，步长上的函数值分别为在设已知)(max) 1, 1 , 0(,)(11010 xIhhnixxhyyybxxxaxfyhiiiiinn第43页/共90页2022-2-3第2章 插值法44引言拉格朗日拉格朗日插值插值牛顿插值牛顿插值埃尔米特埃尔米特插值插值分段低次分段低次插值插值三次样条插三次样条插值值jnjjhjjjjjjjjjjjjjjyxlxIbaxxxbaxnjxxxxxxxjxxxxxxxxlxl011111111)()(:,0)()0()(: )(上则在整个区间略去略去引入基函数第44页/共9

45、0页2022-2-3第2章 插值法45引言拉格朗日拉格朗日插值插值牛顿插值牛顿插值埃尔米特埃尔米特插值插值分段低次分段低次插值插值三次样条插三次样条插值值。其中有线性插值函数，则为其分段，设已知| )(|max8| )()(|,)(), 1 , 0()(,)(22xfMMhxIxfbaxxInixfybaCxfbxahhii 定理。一致收敛到，即)()()()(lim8| )(|max8)(max| )( |2)(max| )()(|) 1, 1 , 0(),()(2)()()(02,211111xfxIxfxIMhxfxxxxxxfxIxfnixxxxxxfxIxfhhhxxxiiiiiii

46、hiiiiiihii 证明第45页/共90页2022-2-3第2章 插值法46引言拉格朗日拉格朗日插值插值牛顿插值牛顿插值埃尔米特埃尔米特插值插值分段低次分段低次插值插值三次样条插三次样条插值值上是三次多项式。在每个小区间）；，）；）,)(3), , 1 , 0()()(2,)(111iihiihiihhxxxIniyxIyxIbaCxI，满足：分段函数导数连续的插值问题的提法为求一。分段三次，步长为导数值上的函数值为在设已知)(Hermitemax) 1, 1 , 0(,)(1101010 xIhhnixxhyyyyyybxxxaxfyhiiiiinnn2 分段三次分段三次Hermite插值

47、插值,)()()()()(2)()(2)(1)(111221112213iiiiiiiiiiiiiiiiiiihxxxyxxxxhyxxxxhyxxhxxyxxhxxhxI第46页/共90页2022-2-3第2章 插值法47引言拉格朗日拉格朗日插值插值牛顿插值牛顿插值埃尔米特埃尔米特插值插值分段低次分段低次插值插值三次样条插三次样条插值值。一致收敛到，即)()()()(lim0 xfxIxfxIhhh, 0 )(,)(2)()0(,)(2)()(111321131121jjjjjjjjjjjjjjjxxxnjxxxhxxhxxjxxxhxxhxxx略去略去基函数21121211211() ()

48、,(0)() ()( ),()0,jjjjjjjjjjjjjxxxxxxxjhxxxxxxxxjnhxxx略去略去njjjjjhyxyxxI0)()()(则第47页/共90页2022-2-3第2章 插值法48引言拉格朗日拉格朗日插值插值牛顿插值牛顿插值埃尔米特埃尔米特插值插值分段低次分段低次插值插值三次样条插三次样条插值值2.6 2.6 三次样条插值插值三次样条插值插值为三次样条插值函数。则称）上还满足插值条件：若在节点上的三次样条函数。是节点则称上是三次多项式在每个小区间）；）满足条件：若函数，上的函数值为在设定义)()2 , 1 , 0()(3,)(,)2 , 1 , 0(,)(2,)(1

49、)()()(:101210 xSnjyxSxxxxxSnjxxxSbaCxSxSxfybxxxaxfyjjjnjjjjn第48页/共90页2022-2-3第2章 插值法49引言拉格朗日拉格朗日插值插值牛顿插值牛顿插值埃尔米特埃尔米特插值插值分段低次分段低次插值插值三次样条插三次样条插值值 由定义知在每个小区间上为次数不超过三次的多项式，有4个待定系数，共有n个小区间，故共有4n个待定系数。个条件，还要两个条件个插值条件，共再加上，个连续条件：处满足，则在节点由2-n41n)0()0()0()0()0()0(3-n3), 2 , 1(,)(2 iiiiiiixSxSxSxSxSxSnixbaCx

50、SnnnnyxSyxSyxSyxS )()()()(0000，)0()0()0()0()()(000 nnnxSxSxSxSxSxS，1）已知两端点的一阶导数值，即2）已知两端点的二阶导数值，即3）S(x)为周期的周期函数时 求S(x)的方法有多种，现以S(x)的二阶导数表达S(x)为例。第49页/共90页2022-2-3第2章 插值法50引言拉格朗日拉格朗日插值插值牛顿插值牛顿插值埃尔米特埃尔米特插值插值分段低次分段低次插值插值三次样条插三次样条插值值), 1 , 0()(niMxSii 设11( )iiiiiixxxxSxMMhhiiixxh1332211111()()( )()()666

51、6iiiiiiiiiiiiiiiixxxxxxh Mxxh MS xMMyyhhhh221111()()( )()226iiiiiiiiiiiixxxxyyhS xMMMMhhh 11(0)36iiiiiiiihhyyS xMMh 1111136)0(iiiiiiiihyyMhMhxS,1iixxx) 1-,2 , 1(2)0()0(11niMMMxSxSiiiiiiii，得由)(61111111iiiiiiiiiiiiiiiiihyyhyyhhhhhhhh，其中 第50页/共90页2022-2-3第2章 插值法51引言拉格朗日拉格朗日插值插值牛顿插值牛顿插值埃尔米特埃尔米特插值插值分段低次分

52、段低次插值插值三次样条插三次样条插值值对第一、第二种边界条件可得方程组nnnnnnnMMMM110110111102222对第三种边界条件可得方程组nnnnnnnnMMMM1211211122112222第51页/共90页2022-2-3第2章 插值法52引言拉格朗日拉格朗日插值插值牛顿插值牛顿插值埃尔米特埃尔米特插值插值分段低次分段低次插值插值三次样条插三次样条插值值iixiy0)3(, 1)0( SS)(xS例2.4 给定数据表如下：012301230000求满足边界条件 的三次样条插值函数改、并给出余项表达式、习题：-20181685424948.P第52页/共90页2022-2-3第3

53、章 函数逼近与曲线拟合53第3章 函数逼近与曲线拟合函数逼近与曲线拟合函数逼近基本概念正交多项式最佳一致逼近最佳平方逼近曲线拟合的最小二乘法第53页/共90页2022-2-3第3章 函数逼近与曲线拟合54基本概念正交正交多项式多项式最佳最佳一致逼近一致逼近最佳最佳平方逼近平方逼近曲线拟合最曲线拟合最小二乘小二乘3.1 3.1 函数逼近基本概念函数逼近基本概念1 函数逼近与函数空间 函数逼近: 对函数类A中给定的函数f(x)A, 要求在另一类简单的便于计算的函数类B中求函数p(x) B, 使p(x)与f(x)的误差在某种度量意义下最小。 一般A Ca,b ,B通常为多项式、有理函数和分段低次多项

54、式。基本概念: 线性相关、 线性无关、 基、坐标、n维空间、无限维空间。.,)()(),(, 0,)(:上一致成立在使总存在一个代数多项式则对任何设定理baxpxfxpbaCxfsWeierstras)()()(max,)(, 0,)(的多项式集合的多项式集合为次数不超过为次数不超过使误差使误差逼近逼近均可用有限维的均可用有限维的及及nHxpxfHxpbaCxfnbxan 第54页/共90页2022-2-3第3章 函数逼近与曲线拟合55基本概念正交正交多项式多项式最佳最佳一致逼近一致逼近最佳最佳平方逼近平方逼近曲线拟合最曲线拟合最小二乘小二乘。其中来逼近用更一般的敛慢。优点：稳定；缺点：收，其

55、中伯恩斯坦多项式,)(),(),()(:)()()()()(:),()1 ()(, )()(),(1011000baCxxxspanxxfxaxaxaxxfBxxCxPxPnkfxfBnnnnknkknknkkn。在某种意义度量下最小使找一个对目的)()(,)(,:*xxfxbaCf第55页/共90页2022-2-3第3章 函数逼近与曲线拟合56基本概念正交正交多项式多项式最佳最佳一致逼近一致逼近最佳最佳平方逼近平方逼近曲线拟合最曲线拟合最小二乘小二乘2 范数与赋范空间 。为称为赋范线性空间，记与。）三角不等式，）齐次性时，当且仅当）正定性上的范数，若它满足称为线性空间XSSyxyxyxRxx

56、xxxS,:3;:2; 000:1:2112211121)(:2:1max:),( niiniiininTnxxxxxxRxxxx范数范数范数范数范数范数对于对于21221)(:2)(:1)(max:,dxxffdxxffxffbaCfbababxa 范数范数范数范数范数范数对于对于第56页/共90页2022-2-3第3章 函数逼近与曲线拟合57基本概念正交正交多项式多项式最佳最佳一致逼近一致逼近最佳最佳平方逼近平方逼近曲线拟合最曲线拟合最小二乘小二乘3 内积与内积空间nnTnTnnyxyxyxyyyyxxxxR112121),(:),(,),(的内积定义为中的内积，与上为称时当且仅当），），

57、），），满足记为中的一个数与之对应，有，上的线性空间，是数域设中在一般线性空间vuXvuuuuuuXwvuwvwuwvuXvuKvuvuXvuuvvuvuKXvuKXX),(0),( ;0, 0),(4),(),(),(3),(),(2),(),(1:),(:正交。称时时vuvuuvvuRK,0),();,(),( ,),)(,(),(,)(:22vvuuvuXvuXSchwarzCauchy 有有对对为一个内积空间为一个内积空间设设不等式不等式定理定理第57页/共90页2022-2-3第3章 函数逼近与曲线拟合58基本概念正交正交多项式多项式最佳最佳一致逼近一致逼近最佳最佳平方逼近平方逼近曲

58、线拟合最曲线拟合最小二乘小二乘.,),(),(),(),(),(),(),(),(),()(,:32121222211121121线性无关线性无关非奇异非奇异矩阵矩阵矩阵矩阵为一个内积空间为一个内积空间设设定理定理nnnnnnnnuuuuuuuuuuuuuuuuuuuuuGGramXuuuX 内积空间X上可引入范数 满足范数的三 条性质Xuuuu ),(0)(, 0)()(),(,. 2), 1 , 0()(. 1:,)(,: xgdxxxgxgbakdxxxbaxbababak则则如果如果上的非负连续函数上的非负连续函数对对存在且为有限值存在且为有限值若若上的一个权函数上的一个权函数为为上的

59、非负函数上的非负函数称有限或无限区间称有限或无限区间定义定义 第58页/共90页2022-2-3第3章 函数逼近与曲线拟合59基本概念正交正交多项式多项式最佳最佳一致逼近一致逼近最佳最佳平方逼近平方逼近曲线拟合最曲线拟合最小二乘小二乘3.2 3.2 正交多项式正交多项式1 正交函数族与正交多项式;)(,)(, 0, 0)()()(),(:),(,),(),(0)()()()(),(:.,)()(,)(,)(),(:10的正交函数族上带权是则称满足关系若函数族若带权正交上在与称上的权函数为定义xbaxkjAkjdxxxxxxxdxxgxfxxgxfbaxgxfbaxbaCxgxfkkbakjkj

60、nba上是正交函数族。在区间三角函数族如族。则称之为标准正交函数若,2sin,2cos,sin,cos, 1:, 1xxxxAk第59页/共90页2022-2-3第3章 函数逼近与曲线拟合60基本概念正交正交多项式多项式最佳最佳一致逼近一致逼近最佳最佳平方逼近平方逼近曲线拟合最曲线拟合最小二乘小二乘.)(,)(;)(,)(, 0, 0)()()(),(:)(,)(,0,)(:00次正交多项式的权上带为称正交上带权为在则称多项式序列满足关系式如果多项式序列上权函数为次多项式的上首项系数是设定义nxbaxxbaxkjAkjdxxxxxbaxnabaxnnkbakjkjnnn), 2, 1()()(