计算方法课件第三章

1

第3章函数逼近与快速傅里叶变换§3.1函数逼近的基本概念§3.2正交多项式§3.3最佳平方逼近§3.4曲线拟合的最小二乘法§3.5有理逼近§3.6三角逼近与快速傅里叶变换2§3.1函数逼近的基本概念问题的提出在数值计算中经常要计算函数值，如计算机中计算基本初等函数及其它特殊函数；当函数只在有限点集上给定函数值，要在包含该点集的区间上用公式给出函数的简单表达式，这些都涉及在区间[a,b]上用简单函数逼近已知复杂函数的问题，这就是函数逼近问题.第二章讨论的插值法就是函数逼近的一种.3本章讨论的函数逼近，是指“对函数类A中给定的函数f(x)，记作f(x)∈A，要求在另一类简单的便于计算的函数类B中求函数p(x)∈B，使p(x)与f(x)的误差在某种度量意义下最小”.函数类A通常是区间[a,b]上的连续函数，记作C[a,b]，称为函数逼近空间；而函数B通常为n次多项式,有理函数或分段低次多项式等.为了在数学上描述更精确，先要介绍代数和分析中一些基本概念及预备知识。问题的提出4空间定义

数学上常把在各种集合中引入某一些不同的确定关系称为赋予集合以某种空间结构，并将这样的集合称为空间。5空间举例例3

所有定义在[a,b]集合上的连续函数全体，按函数的加法和数乘构成数域R上的连续函数线性空间–

C[a,b],称为连续函数空间.类似地记Cp[a,b]为具有p阶连续导数的函数空间.例1

所有实n维向量集合，按向量的加法和数乘构成实数域R上的线性空间---Rn,称为n维向量空间.例2

对次数不超过n的（n为正整数）实系数多项式全体，按多项式加法和数乘构成数域R上的多项式线性空间--Hn,称为多项式空间.6线性无关

定义1

设集合S是数域P上的线性空间，元素x1,x2,…,xn∈S，如果存在不全为零的数a1,a2,…,an∈P，使得则称x1,x2,…,xn

线性相关，否则称x1,x2,…,xn

线性无关，即只有当a1=a2=…=an=0时等式(3.1)才成立.

(3.1)7线性空间

若线性空间S是由n个线性无关元素x1,…,xn生成的，即对任意x∈S，都有则x1,…,xn称为空间S的一组基,记为S=span{x1,…,xn},并称空间S为n维空间，系数a1,…,an为x在基x1,…,xn下的坐标，记作(a1,…,an)，如果S中有无限多个线性无关元素x1,…,xn,…，则称S为无限维线性空间.

8多项式空间

下面考虑次数不超过n实系数多项式集合Hn，其元素p(x)∈Hn表示为它由n+1个系数(a0,a1,…,an)唯一确定.1,x,…,xn

线性无关，它是Hn的一组基，故集合

Hn=span{1,

x,…,xn}，且(a0,a1,…,an)是p(x)的坐标向量，Hn是n+1维的.9连续函数逼近

对连续函数f(x)∈C[a,b]，它不能用有限个线性无关的函数表示，故C[a,b]是无限维的，但它的任一元素f(x)∈C[a,b]均可用有限维的p(x)∈Hn逼近，使误差其中ε为任意给的小正数，即精度要求.这就是下面著名的魏尔斯特拉斯（Weierstrass）定理.10魏尔斯特拉斯定理

定理1

设f(x)∈C[a,b]，则对任何ε>0，总存在一个代数多项式p(x)

，使在[a,b]上一致成立.（证明略，见书p52有说明.）11伯恩斯坦多项式

由(3.3)式给出的Bn(f,x)也是f(x)在[0,1]上的一个逼近多项式，但它收敛太慢，实际中很少使用.12一般提法

更一般地，可用一组在C[a,b]上线性无关的函数集合

来逼近f(x)∈C[a,b]，元素表示为

函数逼近问题就是对任何f(x)∈C[a,b]，在子空间中找一个元素*(x)∈，使f(x)-*(x)在某种意义下最小.13范数与赋范线性空间

为了对线性空间中元素大小进行衡量，需要引进范数定义，它是Rn空间中向量长度概念的直接推广.

定义2

设S为线性空间，xS，若存在唯一实数·，满足条件：

(1)

x0;当且仅当x＝0时,x=0;(正定性) (2)x=||x,R;(齐次性) (3)x+yx+y,x,yS.(三角不等式)

则称·为线性空间S上的范数，S与·一起称为赋范线性空间，记为X.14向量的常用范数对Rn上的向量

x＝(x1,x2,…,xn)T,

三种常用范数为：15函数的常用范数

类似的对连续函数空间C[a,b],若f∈C[a,b]可定义以下三种常用函数的范数16矩阵的常用范数max11=å=££¥aAnjijni)=aAnij（()0)(max=-=AAEfAAAATTTmax111=å=££aAniijnjlll)(max2=AAATl即的最大特征值表示其中称为A的行范数对n阶方阵称为A的列范数称为A的2-范数17例题例4

计算向量x的范数，其中解

18例题例5

计算函数x2关于C[0,1]的范数.解

19例题例6

计算矩阵A的范数，其中解

20向量内积

在线性代数中，Rn上的两个向量

x＝(x1,x2,…,xn)T与y＝(y1,y2,…,yn)T的内积定义为

(x,y)=x1y1+x2y2+…+xnyn.

若将它推广到一般的线性空间X，则有下面的定义.21内积与内积空间

定义3

设X是数域K(R或C)上的线性空间，对任意u,v∈X，有K中一个数与之对应，记为(u,v)，它满足以下条件：则称(u,v)

为X上u与v的内积，对应了内积的线性空间称为内积空间.定义中(1)当K为实数域R时为

(u,v)＝(v,u).22向量垂直

如果(u,v)=0，则称u与v正交(记为u⊥v)，这是向量相互垂直概念的推广.23加权内积若给定实数wi>0(i=1,…,n)，{wi}称为权函数，则在Rn上可定义加权内积为

在C[a,b]上也可以类似定义带权内积，为此先给出权函数定义.24权函数

定义4

设[a,b]是有限或无限区间，在[a,b]上的非负函数w(x)满足条件：则称w(x)为[a,b]上的一个权函数.它的物理意义可以解释为密度函数..0)(0)()(],[)2(º=òxgdxxxgbaba则，如果上的非负连续函数g(x)对w25例题

例7

C[a,b]上的内积，设f(x),g(x)∈C[a,b]，w(x)是上给定的权函数，则可内积定义为容易验证它满足内积定义的4条，由此内积导出的范数为带权w(x)的范数.26最佳逼近则称P*(x)是f(x)在[a,b]上的最佳逼近多项式.如果P(x)∈=span{0,1,…,n}，则称相应的P*(x)为最佳逼近函数.函数逼近主要讨论给定f(x)∈C[a,b]，求它的最佳逼近多项式.若P*(x)∈Hn=span{1,x,…,xn}，使误差27最佳一致逼近若范数·取为·∞,即则称P*(x)是f(x)在[a,b]上的最佳一致逼近多项式.这时求P*(x)就是求[a,b]上使得最大误差最小的多项式.

28最佳平方逼近如果范数·取为·2，即则称P*(x)为f(x)在[a,b]上的最佳平方逼近多项式.

29最小二乘拟合若f(x)是[a,b]上的一个列表函数，在区间节点a≤x0<

x1<…<xm≤b上给出(xi)(i=0,1,…,m)，要求P*(x)∈使本章将着重讨论实际应用多便于计算的最佳平方逼近与最小二乘拟合.则称P*(x)为f(x)在[a,b]上的最小二乘拟合.

30§3.2正交多项式略31§3.3最佳平方逼近略32§3.4曲线拟合的最小二乘法问题的提出某种合成纤维的强度与其拉伸倍数有直接关系，下表是实际测定的24个纤维样品的强度与相应拉伸倍数的记录。提示：将拉伸倍数作为x,强度作为y,在座标纸上标出各点，可以发现什么?33数据表格34数据图35曲线拟合

已知的离散数据yi=f(xi)(i=0,1,2,…,n)往往是通过观测而得到的，经常带有观测误差。

曲线拟合：希望找到—条曲线，它既能反映结定数据的总体分布形式，又不致于出现局部较大的波动。这种逼近方式．只要所构造的逼近函数(x)与被逼近函数f(x)在区间[a,b]上的偏差满足其种要求即可。36偏差

设给定数据点(xi,yi),(i=0,1,2,…,n),记并称ei为偏差。37最小二乘法曲线拟合的最小二乘法：以使得偏差的平方和最小为标难38线性最小二乘拟合假设所给的数据点(xi，yi),(i=0,1,2,…,n)的分布大致呈直线，故可选择线性函数作拟合曲线。【问题1】对于给定的数据点(xi，yi),(i=0,1,2,…,n)，求作一次式y＝a+bx，使总误差为最小。39线性最小二乘拟合（续）【解】由微积分的知识可知，这一问题的求解，可归结为求二元函数E(a,b)的极值，即40线性最小二乘拟合（续）这是关于a,b的线性方程组，称为法方程。4041多项式最小二乘拟合有时所给数据点的分布并不一定近似地呈一条直线，这时若仍用直线似合显然是不合适的。对于这种情况，可以考虑用多项式拟合。【问题2】对于给定的数据点(xi，yi),(i=0,1,2,…,n)，求作多项式，使总误差为最小。42多项式最小二乘拟合（续）【解】由微积分的知识可知，这一问题的求解，可归结为求二元函数E(a0,a1,…,am)的极值，即43多项式最小二乘拟合（续）这是关于a0,a1,…,am的线性力程组，称为法方程。44例题例8

某合金成分x与膨胀系数y之间的关系有如下实验数据，求膨胀系数y与成分x的拟合曲线y=P(x)。i0123456x37383940414243y3.403.002.101.531.801.902.9045例题解将数据标在坐标纸上，由散点图可以推断他们大致分布在一条抛物线上。为此取46例题法方程47例题代入数据后得解得于是所求拟合曲线为48其他函数曲线拟合最小二乘法并不只限于多项式，也可以用任何具体给出的函数形式。即可取【问题3】对于给定的数据点(xi，yi),(i=0,1,2,…,n)，求作曲线，使总误差为最小。49其他函数曲线拟合（续）【解】由微积分的知识可知，这一问题的求解，可归结为求二元函数E(a0,a1,…,am)的极值，即50其他函数曲线拟合（续）引进内积记号51其他函数曲线拟合（续）这是关于a0,a1,…,am的线性方程组，称为法方程。52例题例9

对例8中的数据，试求形如的拟合函数。解取拟合函数系53例题53得法方程解出因此所求的拟合函数为54正交多项式最小二乘拟合

普通多项式作最小二乘拟合时，其法方程是病态的。为了避免解病态方程组，通常用正交多项式作最小二乘拟合。

55正交多项式

正交多项式：对给定点集

及权函数如果函数系满足则称函数系带权函数关于点集正交。56法方程56代替现在以，并利用的正交性，则法方程（3.4）成为对角型方程组（3.5）57广义多项式其解为于是所求的拟合函数（称为广义多项式）为误差为58正交多项式递推公式推导

设式（3.7）中的正交函数系系数为1的正交多项式系。正交多项式的一个基本性质是能够通过递推关系逐个生成。事实上，任何一个k次多项式能表示成正交多项式的线性组合，于是成立，其中是特定参数。以为最高次项对式（3.9）两边作内积59正交多项式递推公式推导（续）即由于次数小于k，可写成代入上式，并利用正交性，得60正交多项式递推公式推导（续）以对式（3.9）两边内积即可写成代入上式，并利用正交性，得61正交多项式递推公式推导（续）以对式（3.9）两边作内积，得将的表达式，代入式（3.9），得62正交多项式递推公式推导（续）若记63正交多项式递推公式则得递推公式64误差递推关系另外，误差的递推关系也不难得到。由式（3.8）可得由式（3.7）和（3.8）可得65例题例10

利用正交多项式对例8中的数据作二次拟合。解按递推公式（3.10）计算权函数为1的正交多项式按公式（3.6）计算广义多项式系数66例题代入式（3.7）中，得到所求的二次函数67非线性最小二乘拟合两边取对数，得则得令两边取自然对数，得令则得（1）（2）68非线性最小二乘拟合（续）（3）两边取对数，得则得令令则得（4）69非线性最小二乘拟合（续）令则得（6）令则得（5）70例题例11

给定实验数据x1.001.251.501.752.00y5.105.796.537.458.46试求形如的拟合函数。解对拟合函数的两边取自然对数，即令则上式成为关于A，b的线性函数71例题根据数据(x,y)算出对应的(z,w),得下表z1.001.251.501.752.00w1.62921.75611.87642.00822.1353建立法方程解得因此，所求的拟合函数为72线性矛盾方程组方程个数大于未知量个数的方程组称为矛盾方程组，一般形式为即73线性矛盾方程组（续）

Ax＝