数值积分（基于MATLAB）课件全套 周金明 chapter1 绪论、曲线拟合 -chapter7 特征值与特征向量的计算

在数学发展中，理论和计算是紧密联系的。现代计算机的出现为大规模的数值计算创造了条件，集中而系统的研究适用于计算机的数值方法变得十分迫切和必要。数值计算方法正是在大量的数值计算实践和理论分析工作的基础上发展起来的，它不仅仅是一些数值方法的简单积累，而且揭示了包含在多种多样的数值方法之间的相同的结构和统一的原理。数值算法是进行科学计算必不可缺少的起码常识；更为重要的是通过对它们的讨论，能够使人们掌握设计数值算法的基本方法和一般原理，为在计算机上解决科学计算问题打下基础。因此，计算方法已经成为工科大学生必修课程。为什么要开设这个课呢？认识建立算法和对每个算法进行理论分析是基本任务，主动适应“公式多”的特点；注重各章建立算法的问题的提法，搞清问题的基本提法，逐步深入；理解每个算法建立的数学背景，数学原理和基本线索，对最基本的算法要非常熟悉；认真进行数值计算的训练，学习各章算法完全是为用于实际计算，必须真会算。如何进行学习？科学素质：拓宽对21世纪科学的了解；

加深对数学思想的理解；

培养用数学思考世界的习惯

数学能力：数学知识的运用能力；

对专业中问题建立数学求解方法

与实际计算能力应用问题中数学创

造性能力

计算知识：常用算法的数学理论；

在“误差、存贮、速度”之下的实

际计算方法；

对结果的数值分析方法

数值分析讲述的基本内容如何把数学模型归结为数值问题如何制定快速的算法如何估计一个给定算法的精度分析误差在计算过程中的积累和传播如何构造精度更高的算法如何使算法较少的占用存储量如何分析算法的优缺点本课程的基本要求掌握数值方法的基本原理掌握常用的科学与工程计算的基本方法能用所学方法在计算机上算出正确结果

§1.1数值分析方法的内容§1.2误差§1.2.1误差的来源§1.2.2误差的基本概念§1.2.3有效数字与相对

误差限的关系第一章绪论1.1数值分析方法的内容

数值分析又称计算方法,它是研究各种数学问题的数值解法及其理论的一门学科。数值分析的任务实际问题数学模型数值计算方法程序设计上机计算数值结果

根据数学模型提出求解的数值计算方法直到编出程序上机算出结果，这一过程边是数值分析研究的对象1.对于要解决的问题建立数学模型2.研究用于求解该数学问题近似解的算法和过程3.按照2进行计算，得到计算结果建立数学模型转化为数值公式进行计算数值方法解题的一般过程

数值计算以及计算机模拟（包括当前流行的虚拟现实的方法），已经是在工程技术研究和经济、社会科学中广泛应用的方法，带来巨大的经济效益天气预报与亿次计算机波音777的无纸设计与有限元CT、核磁共振计算流体力学与爆炸工程能源问题与大型计算计算作为工程技术研究方法计算方法课程主要讨论如何构造求数学模型近似解的算法，讨论算法的数学原理、误差和复杂性，配合程序设计进行计算试验并分析试验结果。与纯数学的理论方法不同，用数值计算方法所求出的结果一般不是解的精确值或者准确的解析表达式，而是所求真解的某些近似值或近似曲线。例如方程x2=2sinx，在区间(1,2)内有唯一根,但找不出求根的解析式,只能用数值计算方法求其近似解。有些数学问题虽有理论上的准确的公式解,但不一定实用,例如行列式解法的Cramer法则原则上可用来求解线性方程组,用这种方法解一个n元方程组,要算n+1个阶行列式的值,总共需要n!(n-1)(n+1)次乘法,当n=20时,其乘除法运算次数约需1021次方,即使用每秒千亿次的计算机也得需要上百年,而用高斯（Guass）消去法约需2660次乘除法运算,并且愈大,相差就愈大。可见研究和选择好的算法是非常重要的。

算法(数值算法):是指有步骤地完成解数值问题的过程。数值算法的特点•目的性，条件和结论、输入和输出数据均要有明确的规定与要求。•确定性，精确地给出每一步的操作(不一定都是运算)定义,不容许有歧义。•可执行性，算法中的每个操作都是可执行的•有穷性，在有限步内能够结束解题过程计算机上的算法，按面向求解问题的不同，分为数值算法和非数值算法。1.2误差

早在中学我们就接触过误差的概念，如在做热力学实验中，从温度计上读出的温度是23.4度，就不是一个精确的值，而是含有误差的近似值。事实上，误差在我们的日常生活中无处不在，无处不有。如量体裁衣，量与裁的结果都不是精确无误的，都含有误差。在用数值方法解题过程中可能产生的误差归纳起来有如下几类：1.模型误差2.观测误差3.截断误差4.舍入误差1.2.2误差的来源用数学方法解决一个具体的实际问题，首先要建立数学模型，这就要对实际问题进行抽象、简化，因而数学模型本身总含有误差，这种误差叫做模型误差数学模型是指那些利用数学语言模拟现实而建立起来的有关量的描述数学模型的准确解与实际问题的真解不同实际问题的真解数学模型的真解为减化模型忽略次要因素定理在特定条件下建立与实际条件有别模型误差在数学模型中通常包含各种各样的参变量，如温度、长度、电压等，这些参数往往是通过观测得到的，因此也带来了误差，这种误差叫观测误差数学模型中的参数和原始数据，是由观测和试验得到的由于测量工具的精度、观测方法或客观条件的限制,使数据含有测量误差,这类误差叫做观测误差或数据误差根据实际情况可以得到误差上下界数值方法中需要了解观测误差,以便选择合理的数值方法与之适应观测误差精确公式用近似公式代替时,所产生的误差叫截断误差例如,函数f(x)用泰勒(Taylor)多项式

截断误差（介于0与x之间）近似代替，则数值方法的截断误差是截断误差的大小直接影响计算结果的精度和计算工作量，是数值计算中必须考虑的一类误差在数值计算中只能对有限位字长的数值进行运算需要对参数、中间结果、最终结果作有限位字长的处理工作，这种处理工作称作舍入处理用有限位数字代替精确数，这种误差叫做舍入误差，是数值计算中必须考虑的一类误差舍入误差例如在计算时用3.14159近似代替，产生的误差R=-3.14159=0.0000026…就是舍入误差。上述种种误差都会影响计算结果的准确性，因此需要了解与研究误差，在数值计算中将着重研究截断误差、舍入误差，并对它们的传播与积累作出分析误差的度量

绝对误差和绝对误差限定义1.1

设精确值x的近似值

x*

，称差

e(x*)

=x-x*近似值x*的绝对误差，简称误差。e(x*)又记为e*

当e*>0时，x*称为弱近似值，当e*<0时，x*称为强近似值|e*|越小，x*的精度越高由于精确值一般是未知的,因而e*

不能求出来,但可以根据测量误差或计算情况设法估计出它的取值范围，即误差绝对值的一个上界或称误差限。1.2.2

误差的基本概念定义1.2

设存在一个正数，使则称为近似值的绝对误差限，简称误差限或精度。实际应用中经常使用这个量来衡量误差限,这就是说,如果近似数的误差限为,则表明准确值x必落在

上,常采用下面的写法来表示近似值的精度或准确值x所在的范围。1.2.2误差的基本概念a-εa+εaA例1

设x

=

=3.1415926…

近似值x*

=3.14,它的绝对误差是0.0015926…，有

‌‌

x-x*=0.0015926…

0.002=0.210-2例2又近似值x*

=3.1416，它的绝对误差是

0.0000074…，有

x-x*=0.0000074…

0.000008=0.810-5例3

而近似值x*

=3.1415，它的绝对误差是0.0000926…，有

x-x*=0.0000926…

0.0001=0.110-3可见，绝对误差限

*不是唯一的，但*越小越好1.2.3相对误差和相对误差限只用绝对误差还不能说明数的近似程度,例如甲打字每100个错一个,乙打字每1000个错一个,他们的误差都是错一个,但显然乙要准确些,这就启发我们除了要看绝对误差外,还必须顾及量的本身。定义1.3绝对误差与精确值x的比值

称为相对误差。简记为1.3.2相对误差和相对误差限

相对误差越小,精度就越高,实际计算时,x通常是不知道的,因此可用下列公式计算相对误差定义1.4设存在一个正数，使

则称为近似值的相对误差限。简记为1.3.2相对误差和相对误差限例4.甲打字每100个错一个，乙打字每1000个错一个，求其相对误差解：根椐定义:甲打字时的相对误差

乙打字时的相对误差1.2.3

有效数字定义1.5设x的近似值

其中是0到9之间的任一个数,但n是正整数,m是整数,若

则称为x的具有n位有效数字的近似值，准确到第n位，是的有效数字。

1.2.3有效数字例5.3.142作为π的近似值时有几位有效数字解：3.141592…=0.3141592…×3.142=0.3142×

m=1|π-3.142|=|0.3141592…×-0.3142×

|

＜0.000041×＜0.0005=×

m–n=1–n=-3所以n=4，具有4位有效数字例6.当取3.141作为的近似值时

-3.141=0.3141592…101

-0.3141101

≤0.0000592101

<0.0005=1/210-2

m-n=1-n=-2所以n=3具有3位有效数字推论如果近似数x*误差限是某一位的半个单位,由该位到x*的第一位非零数字一共有n位

x*就有n位有效数字,也就是说准确到该位再如3.1416作为

的近似值时

-3.1416=0.3141592…101-0.31416101

≤0.00000074101

≤0.0000074<0.00005<0.510-4m-n=1-n=-4所以n=5x*=3.1416有5位有效数字关于有效数字说明①用四舍五入取准确值的前n位x*作为近似值,则

x*必有n位有效数字。如3.142作为的近似值有4位有效数字，而3.141为3位有效数字②有效数字相同的两个近似数，绝对误差不一定相同。例如，设x1*=12345,设x2*=12.345,两者均有5位有效数字但绝对误差不一样

x-x1*=x-12345≤0.5=1/2100

x-x2*=x-12.345≤0.0005=1/210-3③把任何数乘以10p(p=0,1,…)不影响有效位数④准确值具有无穷多位有效数字,如三角形面积

S=1/2ah=0.5ah

因为0.5是真值,没有误差

*=0,因此n,准确值具有无穷位有效数字1.2.3有效数字与相对误差定理1.1若近似数x*=0.x1x2…xn10m具有n位有效数字，则其相对误差证:∵x*

=0.x1x2…xn10m

∴

x*

≥x110m-1

又∵x*具有n位有效数字,则x-x*

≤1/210m-n∴

一般应用中可以取

r*=1/2x110-(n-1),n越大,

r*越小,∴有效数字越多，相对误差就越小例7取3.14作为

的四舍五入的近似值时，求其相对误差解：3.14=0.314101x1=3m=1∵四舍五入的近似值,其各位都是有效数字∴n=3

r*=1/2x110-(n-1)=1/2*310-2=17%1.2.3有效数字与相对误差例8已知近似数x*有两位有效数字，试求其相对误差限解：已知n=2代入公式

r*=1/2x110-(n-1)得

r*=1/2x110-1

x*的第一位有效数字x1没有给出，可进行如下讨论：当

x1=1

r*=1/2x110-1=1/2*110-1=5%

x1=9

r*=1/2x110-1=1/2*910-1=0.56%

取x1=1时相对误差为最大，即5%1.2.3有效数字与相对误差1.2.3有效数字与相对误差定理1.2若近似数x*=0.x1x2…xn10m相对误差则该近似数具有n位有效数字

1.2.3有效数字与相对误差证:∵x*=0.x1x2…xn10m

∴

x*≤(x1+1)10m-1由有效数字定义可知,x*具有n位有效数字。证毕例9已知近似数x*的相对误差限为0.3%，问x*有几位有效数字？解：由得ⅰ当x1=1时,310-3=1/410-(n-1)1210-3=10-(n-1)

上式两边取以10为底的对数得

lg22+lg3+(-3)=-n+1∵lg2=0.3010lg3=0.477120.3010+0.4771-4=-n∴n=2.9209ⅱ当x1=9时,310-3=1/2010-(n-1)610-3=10-n上式两边取以10为底的对数得

lg2+lg3+(-3)=-n∴n=2.2219∴x*至少有3位有效数字

例10为使的近似数的相对误差小于0.1%，问查开方表时，要取几位有效数字？解：∵8<<9∴x1=8

∴-(n-1)<lg2+2lg3+(-3)-n<1.2552-4-n<-2.7448

∴n>2.7448取n=3即查平方表时

8.37取三位有效数字

∴

注意:已知有效数字,求相对误差用公式

已知相对误差,求具有几位有效数字公式1.4.1函数运算误差函数运算误差可用泰勒展开式来分析设一元函数f(x)，自变量x的近似值x*，f(x)的近似值f(x*)，其误差限记为

[f(x*)]，对f(x)在近似值x*附近泰勒展开1.4

误差的传播介于x,x*之间其中

*为近似数x*的绝对误差限，设f｀(x*)与f〃(x*)相差不大,可忽略

*的高次项,于是可得出函数运算的误差和相对误差多元函数亦类似，用泰勒展开即可推导出来例11已测得某场地长L的值L*=110m,宽d的值

d*=80m,已知

L-L*≤0.2m,

d-d*≤0.1m求场地面积S=Ld的绝对误差限和相对误差限解：其中

(d*)=0.1m,

(L*)=0.2m绝对误差限

(s*)(800.2+1100.1)m2=27m2相对误差限算术运算误差计算机的数值运算主要是加、减、乘、除四则运算，带有误差的数在多次运算过程中会进行传播。使计算结果产生误差。误差的变化可以用微分简单描述。注意到准确值x与其近似值通常很接近，其差可认为是较小的增量，即可以把差看作微分，由此可得误差的微分近似关系式。即x的微分表示x的绝对误差，的微分表示x的相对误差，利用这两个关系式及微分运算可以得到一系列有关四则运算的误差结果。算术运算误差由d(x±y)=dx±dy可得两数之和(差）的误差等于两数的误差之和（差）；由可得两数之积的相对误差等于两数的相对误差之和；由可得两数商的相对误差可看作是被除数与除数的相对误差之差。例12正方形的边长约为100cm,怎样测量才能使其面积误差不超过1cm2?解：设正方形边长为xcm,测量值为x*cm,面积

y=f(x)=x2由于f

(x)=2x记自变量和函数的绝对误差分别是e*、e(y*),则

e*=x-x*

e(y*)=y-y*

f(x*)(x-x*)=2x*e*=200e*现要求e(y*)200e*<1,于是

e*≤（1/200）cm=0.005cm要使正方形面积误差不超过1cm2，测量边长时绝对误差应不超过0.005cm。减少运算误差原则误差是用来衡量数值方法好与坏的重要标志为此对每一个算法都要进行误差分析(1)两个相近的数相减，会严重损失有效数字例如x=1958.75，y=1958.32都具有五位有效数字，但x-y=0.43只有两位有效数字通常采用的方法是改变计算公式,例如当与很接近时,由于用右端代替左端公式计算,有效数字就不会损失

减少运算误差原则当x很大时可作相应的变换

则用右端来代替左端。

减少运算误差若干原则当x接近0时一般情况，当f(x)≈f(x*)时，可用泰勒展开取右端的有限项近似左端。如果计算公式不能改变，则可采用增加有效位数的方法保证精度

（2）防止大数“吃掉”小数例求二次方程x2-105x+1=0的根解：按二次方程求根公式

x1=(105+(1010-4)1/2)/2x2=(105-(1010-4)1/2)/2在8位浮点数计算得

x1=(105+105)/2=105(正确）,

x2=(105-105)/2=0(错误）产生错误的原因 ①出现大数1010吃掉小数4的情况 ②分子部分出现两个相近数相减而丧失有效数位常称为灾难性的抵消（3）绝对值太小的数不宜做除数当分母为两个相近数相减时,会丧失有效数字这里分子的误差被扩大104倍,再如若将分母变为0.0011,即分母只有0.0001的变化时,计算结果却有了很大变化减少运算误差若干原则例1.8计算 解:分子分母分别计算后相除(取9位小数)

A=0.0005*0.0143*0.0012=0.00000715*0.0012=0.000000009(有舍入)

B=0.0003*0.0125*0.0135=0.00000375*0.0135=0.000000051(有舍入)

D=A/B=0.17647 真值为0.16948148…，所以D只准确到小数后一位减少运算误差若干原则例：计算算法2。分成三组因子。每组只取六位小数计算

a=0.0005/0.0003=1.666667(有舍入)

b=0.0143/0.0125=1.144000c=0.0012/0.0135=0.088889(有舍入)

D=a*b*c=1.666667*1.144000*0.088889=0.169482,准确到小数后5位。bca减少运算误差若干原则（4）简化计算步骤，减少运算次数

x255=xx2x4x8x16x32x64x128原先要做254次乘法现只需14次即可又如计算多项式

p(x)=anxn

an-1xn-1

…

a1x

a0的值若直接计算akxk,再逐项相加，一共要做

n+(n-1)+…+2+1=n(n+1)/2次乘法和n次加法

减少运算误差若干原则如果将前n项提出x，则有p(x)=（anxn-1

an-1xn-2

…

a1）x

a0

=((anxn-2

an-1xn-3

…

a2)x

a1）x

a0

=(…(anx

an-1)x

…

a2)x

a1)x

a0写成递推公式

减少运算误差若干原则于是,这种多项式求值的算法称为秦九韶算法,只做n次乘法和n次加法,程序实现简单

控制递推公式中误差的传播

对于一个数学问题的求解往往有多种数值方法在选择数值方法时，要注意所用的数值方法不应将计算过程中难以避免的误差放大的较快，造成计算结果完全失真。例13计算积分并估计误差解容易得到递推公式

即为则准确的理论递推式实际运算的递推式两式相减有

这就是说,若与的误差为=-,即

，则误差的递推规律为

于是

计算时的误差被扩大了倍,显然算法是数值不稳定的。如果将递推公式

变换一种形式准确的理论递推式实际运算的递推式从而有即于是有则这个算法的误差传递规律为

即每计算一步的误差的绝对值是上一步的十分之一，误差的传播逐步缩小，得到很好的控制，这个算法是数值稳定的本章小结

误差在数值计算中是不可避免的，误差的传播和积累直接影响到计算结果的精度。在研究算法的同时，必须注重误差分析，使建立起来的算法科学有效。按照误差产生的来源可分为模型误差、观测误差，截断误差、和舍入误差等。误差的表示法有绝对误差和相对误差两种。在表示一个近似数时,要用到有效数字的概念,这在数值计算中非常有用,有效数字是由绝对误差决定的通常用函数的泰勒展开对误差进行估计2024/12/23jkhh58第2章II曲线拟合

如果已知函数f(x)在若干点xi(i=1,2,…,n)处的值yi,便可根据插值原理来建立插值多项式作为f(x)的近似。但在科学实验和生产实践中，往往会遇到这样一种情况，即节点上的函数值并不是很精确的，这些函数值是由实验或观测得到的数据，不可避免地带有测量误差，如果要求所得的近似函数曲线精确无误地通过所有的点(xi,yi),就会使曲线保留着一切测试误差。当个别数据的误差较大时,插值效果显然是不理想的。此外,由实验或观测提供的数据个数往往很多,如果用插值法,势必得到次数较高的插值多项式，这样计算起来很烦琐。2024/12/23jkhh59为此,我们希望从给定的数据(xi,yi)出发,构造一个近似函数,不要求函数完全通过所有的数据点，只要求所得的近似曲线能反映数据的基本趋势，如图5-7所示。曲线拟合示意图

换句话说:求一条曲线,使数据点均在离此曲线的上方或下方不远处,所求的曲线称为拟合曲线,它既能反映数据的总体分布,又不至于出现局部较大的波动,更能反映被逼近函数的特性,使求得的逼近函数与已知函数从总体上来说其偏差按某种方法度量达到最小,这就是最小二乘法。2024/12/23jkhh60

2.1最小二乘原理与函数插值问题不同,曲线拟合不要求曲线通过所有已知点,而是要求得到的近似函数能反映数据的基本关系。在某种意义上,曲线拟合更有实用价值。在对给出的实验(或观测)数据作曲线拟合时,怎样才算拟合得最好呢？一般希望各实验(或观测)数据与拟合曲线的偏差的平方和最小,这就是最小二乘原理。两种逼近概念:

插值:在节点处函数值相同.

拟合:在数据点处误差平方和最小2024/12/23jkhh61函数插值是插值函数P(x)与被插函数f(x)在节点处函数值相同,即而曲线拟合函数不要求严格地通过所有数据点,也就是说拟合函数在xi处的偏差(亦称残差）

不都严格地等于零。但是,为了使近似曲线能尽量反映所给数据点的变化趋势,要求按某种度量标准最小。若记向量,即要求向量的某种范数最小,如的1-范数或∞-范数即2024/12/23jkhh62或

最小。为了便于计算、分析与应用，通常要求的2-范数即为最小。这种要求误差（偏差）平方和最小的拟合称为曲线拟合的最小二乘法。2024/12/23jkhh63

（1）直线拟合设已知数据点,分布大致为一条直线。作拟合直线,该直线不是通过所有的数据点,而是使偏差平方和为最小，其中每组数据与拟合曲线的偏差为根据最小二乘原理，应取和使有极小值，故和应满足下列条件：2024/12/23jkhh64即得如下正规方程组

(3.1)例1设有某实验数据如下：12341.361.371.952.2814.09416.84418.47520.963

用最小二乘法求以上数据的拟合函数解:把表中所给数据画在坐标纸上,将会看到数据点的分布可以用一条直线来近似地描述,设所求的

2024/12/23jkhh65拟合直线为记x1=1.36,x2=1.37,x3=1.95x4=2.28,y1=14.094,y2=16.844,y3=18.475,y4=20.963则正规方程组为

其中将以上数据代入上式正规方程组,得解得

即得拟合直线2024/12/23jkhh66（2）多项式拟合有时所给数据点的分布并不一定近似地呈一条直线,这时仍用直线拟合显然是不合适的,可用多项式拟合。对于给定的一组数据寻求次数不超过m(m<<N)的多项式，来拟合所给定的数据，与线性拟合类似，使偏差的平方和为最小2024/12/23jkhh67由于Q可以看作是关于(j=0,1,2,…,m)的多元函数,故上述拟合多项式的构造问题可归结为多元函数的极值问题。令得

即有

2024/12/23jkhh68这是关于系数

的线性方程组，通常称为正规方程组。可以证明，正规方程组有惟一解。

例2设某实验数据如下：123456012345521123用最小二乘法求一个多项式拟合这组数据(3.2)2024/12/23jkhh69解：将已给数据点描在坐标系中，可以看出这些点接近一条抛物线，因此设所求的多项式为

由法方程组（5.2）,经计算得

N=6,其法方程组为

解之得

所求的多项式为

2024/12/23jkhh70（3）可化为线性拟合的非线性拟合有些非线性拟合曲线可以通过适当的变量替换转化为线性曲线，从而用线性拟合进行处理，对于一个实际的曲线拟合问题，一般先按观测值在直角坐标平面上描出散点图，看一看散点的分布同哪类曲线图形接近，然后选用相接近的曲线拟合方程。再通过适当的变量替换转化为线性拟合问题，按线性拟合解出后再还原为原变量所表示的曲线拟合方程。表3-4列举了几类经适当变换后化为线性拟合求解的曲线拟合方程及变换关系

2024/12/23jkhh71曲线拟合方程变换关系变换后线性拟合方程2024/12/23jkhh72几种常见的数据拟合情况。图(a)表示数据接近于直线，故宜采用线性函数拟合；图(b)数据分布接近于抛物线。可采拟合；二次多项式拟合；(a)(b)2024/12/23jkhh73图(c)的数据分布特点是开始曲线上升较快随后逐渐变慢,宜采用双曲线型函数或指数型函数图(d)的数据分布特点是开始曲线下降快,随后逐渐变慢,宜采用或或等数据拟合。(c)(d)2024/12/23jkhh74例3设某实验数据如下:

12345600.511.522.52.01.00.90.60.40.3用最小二乘法求拟合曲线解:将已给数据点描在坐标系中下图所示,可以看出这些点接近指数曲线,因而可取指数函数作为拟合函数.对函数两边取对数得.令得则就得到线性模型2024/12/23jkhh75则正规方程组为

其中

将以上数据代入上式正规方程组，得解得

由得,由得于是得到拟合指数函数为2024/12/23jkhh762.2超定方程组的最小二乘解设线性方程组Ax=b中，,b是m维已知向量，x是n维解向量，当m＞n，即方程组中方程的个数多于未知量的个数时，称此方程组为超定方程组。一般来说，超定方程组无解（此时为矛盾方程组),这时需要寻求方程组的一个“最近似”的解.记,称使,即最小的解为方程组Ax=b的最小二乘解。2024/12/23jkhh77定理6是Ax=b的最小二乘解的充分必要条件为是的解.证明:充分性

若存在n维向量,使任取一n维向量,令,则,且

所以是Ax=b的最小二乘解。

2024/12/23jkhh78必要性:r的第i个分量为,,记由多元函数求极值的必要条件，可得即由线性代数知识知,上式写成矩阵形式为它是关于的线性方程组,也就是我们所说的正规方程组或法方程组。可以证明如果A是列满秩的,则上述方程组存在惟一解2024/12/23jkhh79例4求超定方程组

的最小二乘解,并求误差平方和。解:方程组写成矩阵形式为正规方程组为2024/12/23jkhh80即

解得此时误差平方和为2024/12/23jkhh81我们已经讨论了最小二乘意义下的曲线拟合问题,由于方程比较简单,实际中应用广泛,特别是因为任何连续函数至少在一个较小的邻域内可以用多项式任意逼近,因此用多项式作数据拟合,有它的特殊重要性。从而在许多实际问题中,不论具体函数关系如何,都可用多项式作近似拟合,但用多项式拟合时,当n较大时(n≥7),其法方程的系数矩阵的条件数一般较大,所以往往是病态的,因而给求解工作带来了困难。2024/12/23jkhh82这组基函数就称为点集上的正交函数集。这种情况下法方程组的系数矩阵是对角阵，显然容易求解。近年来,产生一些直接解线性最小二乘问题的新方法，例如正交三角化方法。另外,如果能选取基函数使得时,

在工程技术与科学研究中，常会遇到函数表达式过于复杂而不便于计算，且又需要计算众多点处的函数值；或已知由实验（测量）得到的某一函数y=f(x)在区间[a,b]中互异的n+1个xi(i=0,1,...,n)处的值yi=f(xi)(i=0,1,...,n),需要构造一个简单易算的函数P(x)作为y=f(x)的近似表达式

y=f(x)≈P(x),使得P(xi)=f(xi)=yi(i=0,1,...,n)

这类问题就称为插值问题，P(x)称为插值函数，P(x)一般取最简单又便于计算得函数。第2章I

插值法x0x1x2x3x4xP(x)

f(x)f(x)

y=f(x)≈P(x),使得P(xi)=f(xi)=yi(i=0,1,...,n)其它点P(x)

f(x)=y2.1.1插值问题

设y=f(x)是区间[a,b]

上的一个实函数,xi(i=0,1,...,n)是[a,b]上n+1个互异实数,已知y=f(x)在xi的值

yi=f(xi)(i=0,1,...,n),求一个次数不超过n的多项式Pn(x)使其满足Pn(xi)=yi(i=0,1,...,n)

(5-1)这就是多项式插值问题.2.1引言其中Pn(x)称为f(x)的n次插值多项式,f(x)称为被插函数,xi(i=0,1,...,n)称为插值节点,(xi,yi)(i=0,1,…,n)称为插值点,[a,b]称为插值区间,式(5-1)称为插值条件。

从几何意义来看,上述问题就是要求一条多项式曲线y=Pn(x),使它通过已知的n+1个点(xi,yi)(i=0,1,…,n),并用Pn(x)近似表示f(x).即

P(x)=a0+a1x+a2x2+...+anxn其中ai为实数，就称P(x)为插值多项式，相应的插值法称为多项式插值，若P(x)为分段的多项式，就称为分段插值，若P(x)为三角多项式,就称为三角插值，本章只讨论插值多项式与分段插值。

本章主要研究如何求出插值多项式，分段插值函数，样条插值函数；讨论插值多项式P(x)的存在唯一性、收敛些及误差估计等。定理1

设节点xi(i=0,1,…,n)互异,则满足插值条件

Pn(xi)=yi(i=0,1,...,n)的次数不超过n的多项式存在且唯一.证设所求的插值多项式为Pn(x)=a0+a1x+a2x2+...+anxn(5-2)则由插值条件式Pn(xi)=yi(i=0,1,...,n)可得关于系数a0,a1,…,an的线性代数方程组2.1.2插值多项式的存在性和唯一性此方程组有n+1个方程,n+1个未知数,其系数行列式是范德蒙(Vandermonde)行列式：（5-3）由克莱姆法则知方程组(5-3)的解存在唯一.证毕。

考虑最简单、最基本的插值问题.求n次插值多项式li(x)(i=0,1,…,n),使其满足插值条件2.2.1基函数可知,除xi点外,其余都是li(x)的零点,故可设Lagrange法1736-1813

2.2拉格朗日插值其中A为常数,由li(xi)=1可得称之为拉格朗日基函数,都是n次多项式。

n=1时的一次基函数为:y1O

xy1Ox即已知函数

f(x)在点x0和x1点的函数值

y0=f(x0)，y1=f(x1).求线性函数

L(x)=a0+a1x使满足条件：L(x0)=y0,L(x1)=y1.此为两点线性插值问题或用直线的两点式表示为：插值基函数的特点：

x0x1l010l1011x0x1l0l1记n=2时的二次基函数为:可知其满足2.2.2拉格朗日插值多项式利用拉格朗日基函数li(x),构造次数不超过n的多项式称为拉格朗日插值多项式,再由插值多项式的唯一性,得

特别地,当n=1时又叫线性插值,其几何意义为过两点的直线.当n=2时又叫抛物（线）插值,其几何意义为过三点的抛物线.注意:(1)对于插值节点,只要求它们互异,与大小次序无关;

以xi(i=0,1,…,n)为插值节点,函数f(x)

1作插值多项式,由插值多项式的唯一性即得基函数的一个性质(2)插值基函数li(x)仅由插值节点xi(i=0,1,…,n)确定,

与被插函数f(x)无关;(3)插值基函数li(x)的顺序与插值节点xi(i=0,1,…,n)

的顺序一致.这是因为若取(x)=xk

(k=0,1,…,n),由插值多项式的唯一性有特别当k=0时,就得到所以例1

已知用线性插值(即一次插值多项式)求的近似值。

基函数分别为:解插值多项式为()例2

求过点(-1,-2),(1,0),(3,-6),(4,3)的抛物线插值(即三次插值多项式).解以以为节点的基函数分别为:则拉格朗日的三次插值多项式为

截断误差Rn(x)=f(x)-Ln(x)也称为n次Lagrange插值多项式的余项。以下为拉格朗日余项定理。

定理2

设f(x)在区间[a,b]上存在n+1阶导数,xi∈[a,b](i=0,1,…,n)为n+1个互异节点,则对任何x∈[a,b],有2.2.3插值余项且与x有关)证由插值条件和

n+1(x)

的定义,当x=xk

时,式子显然成立,并且有

n+1(xk)=0(

k=0,1,…,n),这表明x0

,

x1,

…,xn

都是函数

n+1(x)的零点,从而

n+1(x)可表示为其中K(x)是待定函数。

对于任意固定的x

[a,b],x

xk

,构造自变量t的辅助函数

由式

n+1(xk)=0和式Ln(xk)=yk(k=0,1,…,n),以及可知：x0

,

x1,

,xn

和x是

(t)在区间[a,b]上的n+2个互异零点,因此根据罗尔(Rolle)定理,至少存在一点=(x)(a,b),使

即所以

一般来说,外推比内插效果差,在估计误差时下列不等式很有用。的抛物插值多项式,且计算f(3)的近似值并估计误差。例3

设解插值多项式为因为故于是用二次插值计算ln11.25的近似值,并估计误差.例4

给定函数表x10111213lnx2.3025852.3978952.4849072.564949解

取节点x0=10,x1=11,x2=12,作二次插值有ln11.25L2(11.25)在区间[10,12]上lnx的三阶导数的上限M3=0.002,可得误差估计式实际上,ln11.25=2.420368,|R2(11.25)|=0.000058.2.4.1差商及其基本性质定义1

称为f(x)在x0、x1点的一阶差商.一阶差商的差商称为函数f(x)在x0、x1、x2点的二阶差商.英1642-17272.4差商与牛顿插值公式一般地，n-1阶差商的差商

称为f(x)在x0,x1,…,xn点的n阶差商。差商的计算步骤与结果可列成差商表，如下

一般f(xi)称为f(x)在xi点的零阶差商，记作f[xi]。xk函数值一阶差商二阶差商三阶差商...

x0x1

x2

x3...

f(x0)

f(x1)f(x2)f(x3)...

f[x0,x1]

f[x1,x2]

f[x2,x3]

...

f[x0,x1,x2]

f[x1,x2,x3]

...

f[x0,x1,x2,x3]

......表1（差商表）给出节点x0,x1,…,xn和函数值(x0),(x1),…,(xn),可按如下的差商表顺序逐次计算各阶差商值.xiƒ(xi)一阶差商二阶差商三阶差商…n阶差商x0x1x2x3

xnƒ(x0)ƒ(x1)ƒ(x2)ƒ(x3)

ƒ(xn)ƒ[x0,x1]ƒ[x1,x2]ƒ[x2,x3]

ƒ[xn-1,xn]ƒ[x0,x1,x2]ƒ[x1,x2,x3]

ƒ[xn-2,xn-1,xn]ƒ[x0,x1,x2,x3]

ƒ[xn-3,xn-2,x2,x3]………………

ƒ[x0,x1,…,xn]这一性质可以用数学归纳法证明，它表明差商与节点的排列次序无关，即

f[x0,x1,x2,...,xn]=f[x1,x0,x2,...,xn]=…=f[x1,x2,...,xn,

x0

]性质1

差商可以表示为函数值的线性组合，即称之为差商的对称性（也称为对称性质）。性质2

由性质1立刻得到或性质3

n次多项式f(x)的k阶差商,当k

n时是一个n-k次多项式;当k>n时恒等于0.性质4

若f(x)在[a,b]上存在n阶导数,且节点x0,x1,…,xn∈[a,b],则至少存在一点

[a,b]

满足下式例1

f(x)=－6x8+7x5－10,求f[1,2,…,9]及f[1,2,…,10].

解

f(8)(x)=－6·8!,f[1,2,…,9]=-6,

f(9)(x)=0,f[1,2,…,10]=0.2.4.2牛顿插值多项式设x是[a，b]上一点，由一阶差商定义得同理，由二阶差商定义如此继续下去，可得一系列等式得得依次把后式代入前式，最后得其中可见,Nn(x)为次数不超过n的多项式,且易知Rn(xi)=0即Nn(xi)=yi,(i=0,1,…,n)满足插值条件,故其为插值问题的解,Nn(x)称为牛顿插值多项式。

Rn(x)称为牛顿型插值余项。由插值多项式的唯一性知，它与拉格朗日插值多项式是等价的,即Ln(x)

Nn(x)且有如下递推形式和余项公式由此即得性质4。且xkf(xk)一阶差商二阶差商三阶差商四阶差商0.400.550.650.800.900.410750.578150.696750.888111.026521.11601.18601.27571.38410.28000.35880.43360.19700.21370.0344例1已知f(x)=shx的数表,求二次牛顿插值多项式,并由此计算f(0.596)的近似值。解由上表可得过前三点的二次牛顿插值多项式为又可得过前四点的三次牛顿插值多项式故可得N3(x)的截断误差

设函数y=f(x)在等距节点xi=x0+ih(i=0,1,…,n)上的函数值为fi=f(xi)(h为步长)定义2

fi=fi+1-fi

和

fi=fi-fi-1分别称为函数f(x)在点xi处的一阶向前差分和一阶向后差分。

一般地,f(x)在点xi处的m阶向前差分和m阶向后差分分别为

mfi=

m-1fi+1-

m-1fi

和

mfi=

m-1fi-

m-1fi-12.4.3差分与等距节点插值2.4.3.1差分及其性质函数值一阶差分二阶差分三阶差分四阶差分...

f(x0)

f(x1)f(x2)f(x3)f(x4)...

f0

(

f1)

f1

(

f2)

f2

(

f3)

f3

(

f4)...

2f0

(

2f2)

2f1

(

2f3)

2f2

(

2f4)...

3f0

(

3f3)

3f1

(

3f4)...

4f0

(

4f4)......构造差分表容易证明，差分有如下基本性质性质1

各阶差分均可用函数值表示.即且有等式

nfi=

nfi+n.性质3均差与差分的关系式为性质2函数值均可用各阶差分表示.即且有差分与微商的关系式为差分的其它性质参见教材。代入牛顿插值公式,可得称为牛顿向前插值公式，其余项为插值节点为xi=x0+ih(i=0,1,…,n),如果要计算x0附近点x处的函数值f(x),可令x=x0+th

(0

t

n)2.4.3.2等距节点差值公式

类似地,若计算xn附近的函数值f(x),可令x=xn+th(-

n

t

0)

，可得牛顿向后插值公式及其余项例2

设y=f(x)=ex,xi=1,1.5,2,2.5,3,用三次插值多项式求f(1.2)及f(2.8)的近似值.解相应的函数值及差分表如下:xif(xi)一阶差分二阶差分三阶差分四阶差分11.522.532.71828

4.481697.2890612.1824920.08554

1.76341

2.90347

4.793437.90305

1.14396

1.886063.10962

0.74210

1.223560.48146求f(1.2)用牛顿前插公式,且由1.2=1+0.5t,得t=0.4xif(xi)一阶差分二阶差分三阶差分四阶差分11.522.532.71828

4.481697.2890612.1824920.08554

1.76341

2.90347

4.793437.90305

1.14396

1.886063.10962

0.74210

1.223560.48146求f(2.8)用牛顿后插公式,且由2.8=3+0.5t,得t=-0.4xif(xi)一阶差分二阶差分三阶差分四阶差分11.522.532.71828

4.481697.2890612.1824920.08554

1.76341

2.90347

4.793437.90305

1.14396

1.886063.10962

0.74210

1.223560.48146求f(1.8)呢?2.5.1三次埃尔米特插值多项式

设y=f(x)是区间[a,b]上的实函数,x0,x1是[a,b]上相异两点,且x0＜x1,y=f(x)在xi上的函数值和一阶导数值分别为yi=f(xi)(i=0,1)和mi=f

(xi)(i=0,1),求三次多项式H3(x),使其满足：H3(x)称为三次埃尔米特插值多项式。法1822-19012.5埃尔米特(Hermite)插值构造三次埃尔米特插值多项式如下:定理3

满足条件式的三次埃尔米特插值多项式存在且唯一。

条件函数函数值导数值x0x1x0x1

0(x)1000

1(x)0100

0(x)0010

1(x)0001由可将它写成即插值点的Lagrange一次基函数.

可得满足条件的三次埃尔米特插值多项式为定理4

设f(x)在包含x0、x1的区间[a,b]内存在四阶导数，则当x∈[a,b]时有余项设则当x∈(x0,x1)时,余项有如下估计式（误差限）2.5.2误差估计且与x有关)例2

已知f(x)=x1/2及其一阶导数的数据见下表,用埃尔米特插值公式计算1251/2的近似值,并估计其截断误差.x121144f(x)1112f'(x)1/221/24解得由可求得2.6分段低次插值先看下面的例子

对ƒ(x)=(1+25x2)-1,在区间[-1,1]上取等距节点

xi=-1+ih,i=0,1,…,10,h=0.2,作ƒ(x)关于节点

xi(i=0,1,…,10)的10次插值多项式L10(x),

如图所示xyo1-10.511.5y=L10(x)这个现象被称为Runge现象.表明高次插值的不稳定性.实际上,很少采用高于7次的插值多项式.2.6.1分段线性插值求一个分段函数P(x),使其满足:

P(xi)=yi(i=0,1,...,n);

在每个子区间[xi，xi+1]

上是线性函数.称满足上述条件的函数P(x)为分段线性插值函数.分别作线性插值得,在每个子区间[xi，xi+1]已知或由线性插值的误差即得分段线性插值在区间[xi,xi+1]上的余项估计式为因此,在插值区间[a,b]上有余项2.6.2分段抛物线插值(2)在每个子区间[xi-1,xi+1]上，L(x)是次数不超过2的多项式.称满足上述条件的函数L(x)为分段抛物线插值函数.

L(xi)=yi(i=0,1,...,n);对求一个分段函数L(x),使其满足:即将区间[a,b]分为小区间[xi-1,xi+1](i=1,2,…,n)2.6.3分段三次Hermite插值已知求一个分段函数H(x),使其满足:(2)在每个子区间[xi,xi+1]上，H(x)是次数不超过3的多项式.称满足上述条件的函数H(x)为分段三次Hermite插值函数.或[xi，xi+1]上得在每个子区间由分段三次埃尔米特插值在区间[xi,xi+1]上的余项估计式为因此，在插值区间[a,b]上有余项例3

构造函数f(x)=lnx在1≤x≤10上的数表,应如何选取步长h,才能使利用数表进行分段插值时误差不超过0.5×10-4。解欲使即进行分段线性插值时，应取h≤2×10-2，误差不超过0.5×10-4。欲使即进行分段三次埃尔米特插值时,应取误差不超过0.5×10-4。2.7.1问题的提出定义给定区间[a,b]的一个划分a=x0<x1<…<xn=b，yi=f(xi)(i=0,1,…,n),如果函数S(x)满足：

S(xi)=yi(i=0,1,…,n);

在每个小区间[xi,xi+1](i=0,1,...,n-1)上是次数不超过3的多项式;(3)在每个内节点xi(i=1,2,...,n-1)上具有二阶连续导数,

则称S(x)