第3章 函数逼近与快速傅里叶变换 3.1 函数逼近的基本概念 3.2 正交多项式 3.3 最佳平方逼近 3.4 曲线拟合的最小二乘法

Presentation on theme: "第3章 函数逼近与快速傅里叶变换 3.1 函数逼近的基本概念 3.2 正交多项式 3.3 最佳平方逼近 3.4 曲线拟合的最小二乘法"— Presentation transcript:

1 第3章 函数逼近与快速傅里叶变换 3.1 函数逼近的基本概念 3.2 正交多项式 3.3 最佳平方逼近 3.4 曲线拟合的最小二乘法
第3章 函数逼近与快速傅里叶变换 3.1 函数逼近的基本概念 3.2 正交多项式 3.3 最佳平方逼近 3.4 曲线拟合的最小二乘法 3.5 有理逼近 3.6 三角多项式与快速傅里叶变换

2 3.1 函数逼近的基本概念 3.1.1 函数逼近与函数空间 1、数值计算中经常要计算函数值，如计算机中计算 问题
函数逼近的基本概念 函数逼近与函数空间 1、数值计算中经常要计算函数值，如计算机中计算 基本初等函数及其他特殊函数； 问题 2、当函数只在有限点集上给定函数值，要在包含该 点集的区间上用公式给出函数的简单表达式. 这些都涉及到在区间 上用简单函数逼近已知复杂 函数的问题， 这就是函数逼近问题.

3 插值法就是函数逼近问题的一种. 本章讨论的函数逼近，是指“对函数类 中给定的函数 记作 ， 要在另一类简单的便于计算的函数类 中求函数 ， 使 与 的误差在某种度量 意义下最小”. 函数类 通常是区间 上的连续函数，记作 ， 称为连续函数空间.

4 赋予集合以某种空间结构，并将这样的集合称为空间.
函数类 通常为 次多项式，有理函数或分段低次多项 式等. 数学上常把在各种集合中引入某些不同的确定关系称为 赋予集合以某种空间结构，并将这样的集合称为空间. 与数的乘法构成实数域上的线性空间， 例如将所有实 维向量组成的集合，按向量加法及向量 称为 维 记作 ， 向量空间.

5 按通常多项式与多项式加法及数与多项式乘法也构成数域
对次数不超过 ( 为正整数)的实系数多项式全体， 按通常多项式与多项式加法及数与多项式乘法也构成数域 称为多项式空间. 用 表示， 上一个线性空间， 所有定义在 上的连续函数集合，按函数加法和 数与函数乘法构成数域 上的线性空间， 记作 类似地, 记 为具有 阶连续导数的函数空间.

6 定义1 设集合 是数域 上的线性空间，元素 如果存在不全为零的数 ， 使得 （1.1） 则称 线性相关. 否则，若等式(1.1)只对 成立， 则称 线性无关.

7 若线性空间 是由 个线性无关元素 生成的， 即对 都有 则 称为空间 的一组基， 记为 并称空间 为 维空间， 系数 称为 在基 下的坐标， 记作 如果 中有无限个线性无关元素 则称 为无限维线性空间.

8 考察次数不超过 次的多项式集合 ， 其元素 表示为 （1.2） 它由 个系数 唯一确定. 是线性无关的， 它是 的一组基， 故 且 是 的坐标向量， 是 维的.

9 对连续函数 ，它不能用有限个线性无关的 函数表示，故 是无限维的，但它的任一元素 均可用有限维的 逼近， 使误差 ( 为任给的小正数)， 这就是著名的魏尔斯特拉斯定理.

10 定理1 总存在一 设 ， 则对任何 ， 个代数多项式 ， 使 在 上一致成立. 伯恩斯坦1912年给出的证明是一种构造性证明. 他根据函数整体逼近的特性构造出伯恩斯坦多项式 （1.3）

11 其中 为二项式展开系数，并证明了 在 上一致成立； 若 在 上 阶导数连续，则 这个结果不但证明了定理1，而且由(1.3)给出了 的一个逼近多项式，但它收敛太慢，实际中很少使用.

12 更一般地，可用一组在 上线性无关的函数集合
来逼近 ， 此时元素 可表示为 （1.4） 函数逼近问题就是对任何 ， 找一个元素 ， 使 在某种意义下最小. 在子空间Φ中

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

14 定义2 设 为线性空间， ，若存在唯一实数‖·‖，
满足条件： （1）  当且仅当 时， （正定性） （2） (齐次性) （3） (三角不等式) 则称‖·‖为线性空间 上的范数， 与‖·‖一起称为赋范 线性空间，记为

15 例如，在 上的向量 三种常 用范数为 称为 范数或最大范数， 称为 1-范数， 称为 2-范数.

16 实际上任何向量的实值函数，只要满足上述三个条件，
就可以定义成一种向量范数. 在 中，满足‖·‖2 =1 ，即 的向量 为单位圆， 满足‖·‖∞ =1 ，即 的向量为单位正 方形， 而满足‖·‖1 =1 的向量 则为对角线长 度为1的菱形.

17 所以说，范数是对向量长度的度量，度量方式不同，
结果也不一样，但不同范数之间是存在等价关系的.

18 类似地，对连续函数空间 ，若 , 可定义三种常用范数如下： 称为 范数， 称为 1-范数， 称为 2-范数. 可以验证这样定义的范数均满足定义2中的三个条件.

19 内积与内积空间 在线性代数中， 中两个向量 及 的内积定义为 （1.5） 若将它推广到一般的线性空间 ，则有下面的定义.

20 定义3 X 是数域K(R或C)上的线性空间，对 有K中一个数与之对应，记为 ，它满足 以下条件： 则称 为X上 与 的内积.

21 定义了内积的线性空间称为内积空间. 定义中（1）的右端 称为 的共轭， 当K为实数域R时  如果 ，则称 与 正交，这是向量相互垂 直概念的推广.

22 定理2 设X为一个内积空间， 对 有 （1.6） 称为柯西-施瓦茨(Cauchy-Schwarz)不等式. 证明 当 时（1.6）式显然成立. 现设 ， 则 ， 且对任何数 有 取 ， 代入上式右端，得

23 即得 时

24 定理3 设X为一个内积空间， 矩阵 （1.7） 称为格拉姆(Gram)矩阵， 则 非奇异的充分必要条件是 线性无关.

25 G非奇异等价于 ，其充要条件是齐次 方程组 证明 （1.8） 只有零解； 而 （1.9）

26 从以上等价关系知， 等价于从（1.8）推出 （1.8） 而后者等价于从（1.9）推出 即 线性无关. 在内积空间X上，可以由内积导出一种范数，即对于 记 （1.10）

27 利用 两端开方即得三角不等式 （1.11）

28 例1 与 的内积. 设 （1.12） 向量2-范数为

29 若给定实数 称 为权系数， 上的加权内积为 （1.13） 相应的范数为 当 时， （1.13）就是前面定义的内积.

30 如果 ， 带权内积定义为 （1.14） 这里 仍为正实数序列， 为 的共轭. 在 上也可以类似定义带权内积.

31 设 是有限或无限区间，在 上的非负 函数 满足条件： 定义4 （1）  存在且为有限值 （2） 对 上的非负连续函数 ，如果 则 则称 为 上的一个权函数.

32 例2 上的内积. 设 是 上给定的权函数, 则可定义内积 （1.15） 由此内积导出的范数为 （1.16） 称（1.15）和（1.16）为带权 的内积和范数.

33 常用的是 的情形，即

34 若 是 中的线性无关函数族， 记 它的格拉姆矩阵为 （1.17） 根据定理3可知 线性无关的充要条件是

35 3.1.4 最佳逼近 函数逼近主要讨论给定 ，求它的最佳逼近多项式的问题. 若 使误差 则称 是 在 上的最佳逼近多项式. 若 则称相应的
最佳逼近 函数逼近主要讨论给定 ，求它的最佳逼近多项式的问题. 若 使误差 则称 是 在 上的最佳逼近多项式. 若 则称相应的 为最佳逼近函数. 通常将范数 取为 或

36 若取 ，即 （1.18） 则称 是 在 上的最优一致逼近多项式. 求 就是求 上使最大误差 最小的多项式.

37 若取 ，即 （1.19） 则称 是 在 上的最佳平方逼近多项式. 若 是 上的一个列表函数，在 上给出 ，要求 使 （1.20） 则称 为 的最小二乘拟合.

38 正交多项式 正交函数族与正交多项式 定义5 若 上的权函数且满足 为 （2.1） 则称 与 在 上带权 正交.

39 若函数族 满足关系 （2.2） 则称 是 上带权 的正交函数族. 若 ，则称之为标准正交函数族.

40 三角函数族  就是在区间 上的正交函数族. 定义6 设 是 上首项系数 的 次多 项式， 为 上权函数， 满足关系式(2.2)， 则称多项式序列 为在 上 带权 正交，称 为 上带权 的 次正交多项式. 如果多项式序列

41 只要给定区间 及权函数 ，均可由一族线性 无关的幂函数 利用逐个正交化手续构造 出正交多项式序列 ： （2.3）

42 正交多项式 的最高次项系数为1. 而若 是正交多项式，则 在 上是 线性无关的. 事实上，若 用 乘上式并积分得

43 利用正交性有 由于 ，故 即 线性无关. 关于正交多项式，有  （1） 任何 均可表示为 的线性组合. 即

44 （2） 与任一次数小于 的多项式 正交. 即 除此之外，还有

45 定理4 设 是 上带权 的正交多项式，对 成立关系 （2.4） 其中 这里

46 定理5 设 是 上带权 的正交多项式，则 在区间 内有 个不同的零点.
证明 假定 在 内的零点都是偶数重的，则 在 符号保持不变，这与 矛盾.故 在 内的零点不可能全是偶数重的，现设 为 在 内的奇数重零点，不妨设 则 在 处变号.

47 令 于是 在 上不变号，则得 若 ，由 的正交性可知 这与 矛盾，故 .而 只有 个零点，故 ，即 个零点都是单重的.

48 3.2.2 勒让德多项式 当区间为 ，权函数 时， 由 正交化得到的多项式就称为勒让德(Legendre)多项式， 并用 表示.
勒让德多项式 当区间为 ，权函数 时， 并用 表示. 正交化得到的多项式就称为勒让德(Legendre)多项式， 由 罗德利克(Rodrigul）给出了简单的表达式 （2.5）

49 由于 是 次多项式， 所以对其求 阶导数后得 于是得首项 的系数 最高项系数为1的勒让德多项式为 （2.6）

50 勒让德多项式重要性质： 性质1 正交性 （2.7） 证明 令 ，则 设 是在区间 上 阶连续可微的函数，由分部 积分知

51 下面分两种情况讨论: （1） 若 是次数小于 的多项式， 则 故得

52 （2） 若 则 于是 由于 故

53 性质2 奇偶性 （2.8） 由于 是偶次多项式，经过偶次求导仍为 偶次多项式，经过奇次求导则为奇次多项式，故 为偶数时 为偶函数， 为奇数时 为奇函数，于是（2.8）成 立.

54 性质3 递推关系 考虑 次多项式 它可表示为 两边乘 并从-1到1积分， 得 当 时， 次数小于等于 ， 为0， 上式左端积分 故得

55 当 时， 左端积分仍为0， 为奇函数， 故 于是 其中

56 从而得到以下的递推公式 （2.9） 由 利用上述递推公式就可推出

57 图3-1给出了 的图形. 图3-1

58  在区间 内有 个不同的实零点. 性质4

59 3.2.3 切比雪夫多项式 当权函数 ，区间为 时，由序 列 正交化得到的正交多项式就是切比雪夫 (Chebyshev)多项式. 它可表示为
切比雪夫多项式 当权函数 ，区间为 时，由序 列 正交化得到的正交多项式就是切比雪夫 (Chebyshev)多项式. 它可表示为 （2.10） 若令 ， 则

60 切比雪夫多项式有很多重要性质： 性质1 递推关系 （2.11） 这只要在三角恒等式 中， 令 即得.

61 由（2.11）可推出 的函数图形见图3-2.

62 图3-2 由递推关系（2.11）还可得到 的最高次项系数是

63 性质2 切比雪夫多项式 在区间 上带权 正交，且 （2.12） 令 ， 则 ， 于是

64 性质3 只含 的偶次幂， 只含 的奇次幂. 这个性质由递推关系直接得到. 性质4 在区间 上有 个零点 性质 的首项 的系数为 若令 ，则 是首项系数为1的切比雪夫多项式.

65 若记 为所有次数小于等于 的首项系数为1的多项
式集合，对 有以下性质： 定理6 设 是首项系数为1的切比雪夫多项式，则 且

66 定理6表明在所有首项系数为1的 次多项式集合 中，
所以 是 中最大值最小的多项式，即 （2.13） 利用这一结论，可求 在 中的最佳（一致）逼近多项式.

67 求 在 上的最佳2次逼 近多项式. 例3 解 由题意，所求最佳逼近多项式 应满足 由定理6可知， 当 时， 多项式 与零偏差最小， 故

68 就是 在 上的最佳2次逼近多项式. 由于切比雪夫多项式是在区间 上定义的，对于 一般区间 ，要通过变量替换变换到 ，可令 （2.14） 则可将 变换到

69 3.2.4 切比雪夫多项式零点插值 切比雪夫多项式 在区间 上有 个零点 和 个极值点（包括端点）
切比雪夫多项式零点插值 切比雪夫多项式 在区间 上有 个零点 和 个极值点（包括端点） 这两组点称为切比雪夫点，它们在插值中有重要作用.

70 从图3-3可以看到切比雪夫点恰好是单位圆周上等距分
布点的横坐标，这些点的横坐标在接近区间 的端点 处是密集的. 利用切比雪夫点做插值，可使插值区间最大误差最小化. 设插值点 为相应的 次拉格朗日插值多项式，则余项 图3-3

71 于是 其中 是由被插函数决定的. 如果插值节点为 的零点

72 则由（2.13）可得 由此可导出插值误差最小化的理论. 定理7 设插值节点 为切比雪夫多项式 的零点，被插函数 为相应的插值多项式，则 （2.15）

73 对于一般区间 上的插值只要利用变换（2.14）则 可得到相应结果，此时插值节点为

74 例4 求 在 上的四次拉格朗日插值多项式 ，插值节点用 的零点并估计误差 解 利用 的零点和区间变换可知节点 即 对应的拉格朗日插值多项式为

75 利用（2.15）可得误差估计 而 于是有

76 在第2章中曾经指出，高次插值会出现龙格现象，一般
不收敛于 ，因此并不适用. 但若用切比雪夫多项 式零点插值却可避免龙格现象，可保证整个区间上收敛.

77 例5 设 ，在 上利用 的零点 作插值点，构造10次拉格朗日插值多项式 与第2章 得到的等距节点造出的 近似 作比较. 解 在 上的10次切比雪夫多项式 的零点为 作变换 它们是 内的插值点， 由此得到 在 上的拉格朗日插值多项式

78 的图形见图3-4，从图上可见 没有出现龙格现象. 图3-4

79 3.2.5 其他常用的正交多项式 区间 及权函数 不同，则得到的正交多项式也 不同. 除上述两种最重要的正交多项式外，下面是三种较常
区间 及权函数 不同，则得到的正交多项式也 不同. 除上述两种最重要的正交多项式外，下面是三种较常 用的正交多项式. 1. 第二类切比雪夫多项式 在区间 上带权 的正交多项式 称为第二类切比雪夫多项式.

80 表达式为 （2.16） 令 ， 可得 即 是 上带权 的正交多项式族.

81 递推关系

82 2. 拉盖尔多项式 在区间 上带权 的正交多项式称为拉 盖尔(Laguerre)多项式. 其表达式为 （2.17） 正交性质

83 递推关系

84 3. 埃尔米特多项式 在区间 上带权 的正交多项式称 为埃尔米特多项式. 表达式 （2.18） 正交关系

85 递推关系

86 最佳平方逼近

87 最佳平方逼近及其计算 对 及 中的一个子集 若存在 ，使 （3.1） 则称 是 在子集 中的最佳平方逼近 函数.

88 由（3.1）可知该问题等价于求多元函数 （3.2） 的最小值. 是关于 的二次函数， 利用多元函数求极值的必要条件 即

89 于是有 （3.3） 这个关于 的线性方程组，称为法方程. 由于 线性无关，故 于是方程组（4.3）有唯一解 从而得到

90 下面证明 满足（3.1）， 即对任何 有 （3.4） （3.1） 为此只要考虑

91 由于 的系数 是方程（3.3）的解， 故 （3.3） 从而上式第二个积分为0， 于是 故（3.4）成立. 这就证明了 是 在 中的最佳平方逼近函数. （3.4）

92 若令 则平方误差为 （3.5） 若取 中求 次最佳平方逼近多项式 则要在

93 此时 若用 表示 对应的矩阵， 即 （3.6） 称为希尔伯特(Hilbert)矩阵.

94 记 则 （3.7） 的解 即为所求.

95 例6 设 求 上的一次最佳平方 逼近多项式. 解 利用（3.7），得 得方程组

96 解之 故 平方误差 最大误差

97 3.3.2 用正交函数族作最佳平方逼近 设 若 是满足条件(2.2)的正交函数族， 则 （3.3） 而 故法方程（3.3）的系数矩阵
用正交函数族作最佳平方逼近 设 若 是满足条件(2.2)的正交函数族， 则 （3.3） （2.2） 而 故法方程（3.3）的系数矩阵

98 为非奇异对角阵， 且方程（3.3）的解为 （3.8） （3.3） 于是 在 中的最佳平方逼近函数为 （3.9）

99 由（3.5）可得均方误差为 （3.10） （3.5） 由此可得贝塞尔(Bessel)不等式 （3.11）

100 若 ， 按正交函数族 展开， 系数 按（3.8）计算， 得级数 （3.12） （3.8） 称这个级数为 的广义傅里叶(Foureir)级数， 系数 称为广义傅里叶系数. 它是傅里叶级数的直接推广. 讨论特殊情况，设 是正交多 项式， 可由 正交化得到，则有下面的收敛定理.

101 定理8 设 的最佳平方逼近多项式， 是由（3.9）给出的 其中 是正交多项式族， 则有 （3.9） 考虑函数 按勒让德多项式 展开， 由(3.8)，(3.9)可得 （3.13）

102 （3.10） 其中 （3.14） 根据均方误差公式(3.10)，平方误差为 （3.15） 由定理8可得

103 （3.13） 如果 满足光滑性条件,还有 一致收敛于 的结论. 定理9 设 由(3.13)给出， 则对任意 和 当 充分大时有 公式(2.6)给出了首项系数为1的勒让德多项式 ， 它具有以下性质. （2.6）

104 定理10 在所有最高次项系数为1的 次多项式中， 勒让德多项式 在 上与零的平方误差最小. 证明 设 是任意一个最高次项系数为1的 次 多项式， 它可表示为

105 于是 当且仅当 时等号才成立， 即当 时平方误差最小.

106 例7 求 在 上的三次最佳平方逼近多项式. 解 先计算

107 由(3.14) 得 （3.14） 代入(3.13) 得三次最佳平方逼近多项式 （3.13）

108 均方误差 最大误差 如果 求 上的最佳平方逼近多项式， 做变换

109 于是 在 上可用勒让德多项式做最佳平方逼近多项式 从而得到区间 上的最佳平方逼近多项式

110 由于勒让德多项式 是在区间 上由 正交化得到的，因此利用函数的勒让德展 开部分和得到最佳平方逼近多项式与由 直接通过解法方程得到 中的最佳平方逼近多项式是一致 的. 只是当 较大时法方程出现病态，计算误差较大，不能 使用，而用勒让德展开不用解线性方程组，不存在病态问题， 因此通常都用这种方法求最佳平方逼近多项式.

111 3.3.3 切比雪夫级数 如果 ，按 展成广义傅里叶级数， 由（3.12）可得级数 （3.16）
切比雪夫级数 如果 ，按 展成广义傅里叶级数， 由（3.12）可得级数 （3.16） 其中系数根据（3.8）式，由（2.12）得到 （3.17） 这里 级数（3.16）称为 在 上的切比雪夫级数.

112 若令 ，则（3.16）就是 的傅里 叶级数，其中 （3.18） 根据傅里叶级数理论，只要 在 上分段连续，则 在 上的切比雪夫级数（3.16）一致收敛于 从而 （3.19）

113 取部分和 （3.20） 其误差为 在 上 是均匀分布的，它的最大值 最小，因此 可作为 在 上的近似最佳一致 逼近多项式.

114 例8 求 在 上的切比雪夫部分和 解 由（3.18）得 利用第4章的数值积分法得 由（3.20）及 的表达式有 及

115 3.4 曲线拟合的最小二乘法 3.4.1 最小二乘法及其计算 在函数的最佳平方逼近中 如果 只在一组离散点集 上给定，这就是科
3.4 曲线拟合的最小二乘法 最小二乘法及其计算 在函数的最佳平方逼近中 如果 只在一组离散点集 上给定，这就是科 学实验中经常见到的实验数据 的 曲线拟合.

116 问题为利用 求出一个函数 与所给数据 拟合. 记误差

117 设 是 上线性无关函数族， 在 中找一函数 ， 使误差平方和 （4.1） 这里 （4.2）

118 这个问题称为最小二乘逼近，几何上称为曲线拟合的
最小二乘法. 用最小二乘求拟合曲线时,首先要确定 的形式. 确定 的形式问题不仅是数学问题, 还与问题的 实际背景有关. 通常要用问题的运动规律及给定的数据进行数据描图, 确定 的形式, 然后通过实际计算选出较好的结果.

119 的一般表达式为（4.2）表示的线性形式. 若 是 次多项式， 就是 次多项式. （4.2） 为了使问题的提法更有一般性，通常在最小二乘法中 考虑加权平方和 （4.3） 这里 是 上的权函数，它表示不同点 处的数据比重不同.

120 用最小二乘法求拟合曲线的问题，就是在形如(4.2)的
中求一函数 ， 使（4.3）取得最小. 这样，最小二乘问题就转化为求多元函数 （4.2） （4.4） （4.3） 的极小点 问题. 由求多元函数极值的必要条件，有

121 若记 （4.5） 上式可改写为 （4.6） 这方程称为法方程， 可写成矩阵形式

122 其中 （4.7） 要使法方程(4.6)有唯一解，就要求矩阵 非奇异， 而 在 上线性无关不能推出 矩阵 非奇异，必须加上另外的条件. （4.6）

123 设 的任意线 性组合在点集 上至多只有 个 不同的零点， 定义7 则称 在点集 上满足哈尔(Haar)条件. 显然 在任意 个点上满足哈尔条件. 哈尔条件，则法方程(4.6) 的系数矩阵(4.7) 非奇异， 如果 在 上满足 于是 方程(5.6)存在唯一的解 从而得到 （4.6） 函数 的最小二乘解为

124 这样得到的 ， 对任何形如(4.2)的 ， 都有 故 确是所求最小二乘解. （4.2）

125 给定 的离散数据 ， 一般可取 ，但这样做当 时， 求解法方程（4.6）将出现系数矩阵 为病态的问题， 通常对 的简单情形都可通过求法方程（4.6）得到 有时根据给定数据图形，其拟合函数 表面上 不是（4.2）的形式，但通过变换仍可化为线性模型. 例如， ， （4.2） 若两边取对数得

126 此时，若令 则 这样就变成了形如（4.2）的线性模型 .

127 例9 已知一组实验数据如下，求它的拟合曲线. 解 将所给数据在坐标纸上标出，见图3-5. 图3-5

128 从图中看到各点在一条直线附近，故可选择线性函数作拟合曲线，
令 这里 故

129 由（4.6）得方程组 （4.6） 解得 于是所求拟合曲线为

130 关于多项式拟合，Matlab中有现成的程序
其中输入参数 为要拟合的数据， 为拟合多项式的次数， 输出参数 为拟合多项式的系数. 利用下面的程序，可在Matlab中完成上例的多项式拟合.

131 x=[ ]; f=[ ]; aa=polyfit(x,f,1); y=polyval(aa,x); plot(x,f,’r+’,x,y,’k’) xlabel(‘x’); ylabel(‘y’); gtext(‘y=s1(x)’）

132 结果如下：

133 例10 设数据 由表3-2给出， 表中第4行为 通过描点可以看出数学模型为 用最小二乘法确定 及 .

134 解 用给定数据描图可确定拟合曲线方程为 它不是线性形式. 两边取对数得 若令 则得 为确定 ， 先将 转化为 数据表见表3-2. 根据最小二乘法，取 得

135 故有法方程 解得 于是得最小二乘拟合曲线为

136 gtext(‘y=a*exp(bx))’;
利用下面的程序，可在Matlab中完成曲线拟合. x=[ ]; y=[ ]; y1=log(y); aa=polyfit(x,y1,1); a=aa(1); b=exp(aa(2)); y2=b*exp(a*x); plot(x,y,’r+’,x,y2,’k’) xlabel(‘x’); ylabel(‘y’); gtext(‘y=a*exp(bx))’;

137 结果如下：

138 3.4.2 用正交多项式做最小二乘拟合 用最小二乘法得到的法方程组（4.6），其系数矩阵 是病态的. 如果 是关于点集 （4.6）
用正交多项式做最小二乘拟合 用最小二乘法得到的法方程组（4.6），其系数矩阵 是病态的. 如果 是关于点集 （4.6） 带权 正交的 函数族，即 （4.8）

139 则方程（4.6）的解为 （4.6） （4.9） 且平方误差为

140 接下来根据给定节点 及权函数 构造带权 正交的多项式 注意 ，用递推公式表示 ，即 （4.10） 这里 是首项系数为1的 次多项式， 根据 的 正交性，得

141 （4.11） 下面用归纳法证明这样给出的 是正交的.

142 由（4.10）第二式及（4.11）中 的表达式，有 （4.10） 假定 对 及 均成立， 要证 对 均成立. 由（4.10）有 （4.10） （4.12）

143 由归纳法假定， 当 时 另外， 是首项系数为1的 次多项式，它可由 的线性组合表示. 而 ， 由归纳法假定又有 于是由（4.12），当 时， （4.12）

144 再考虑 （4.13） 由假定有 利用（4.11）中 表达式及以上结果，得

145 最后，由 和 的表达式（4.11）有 至此已证明了由（4.10）及（4.11）确定的多项式  组成一个关于点集 的正交系. 用正交多项式 的线性组合作最小二乘曲线拟合， 只要根据公式（4.10）及（4.11）逐步求 的同时， 相应计算出系数

146 并逐步把 累加到 中去，最后就可得到所求的 拟合曲线 这里 可事先给定或在计算过程中根据误差确定. 用这种方法编程序不用解方程组，只用递推公式，并 且当逼近次数增加一次时，只要把程序中循环数加1，其余 不用改变.

147 2017/3/20 147

148 2017/3/20 148

149 2017/3/20 149

150

151

152 3.5 有 理 逼 近 3.5.1 有理逼近与连分式 有理函数逼近是指用形如 （5.1） 的函数逼近 与前面讨论一样，如果 最小就可得到
有 理 逼 近 有理逼近与连分式 有理函数逼近是指用形如 （5.1） 的函数逼近 与前面讨论一样，如果 最小就可得到 最佳有理一致逼近.

153 如果 最小则可得到最佳有理平方逼近 函数. 本节主要讨论利用函数的泰勒展开获得有理逼近函数 的方法. 对函数 用泰勒展开得 （5.2） 取部分和

154 另一方面若对（5.2）式用辗转相除可得到 的 一种连分式展开 （5.2） （5.3）

155 （5.3）右端为 的无穷连分式的前5项，最后式子 是它的紧凑形式. 若取（5.3）的前2，4，6，8项，则可分别得到 的以下有理逼近 （5.4）

156 若用同样多项的泰勒展开部分和 逼近 并计算 处的值 及 ，计算结果见表3-3. 的准确值为 从表3-1可以看出，

157 由此看出 的精度比 高出近10万倍， 但它们的计算量是相当的，这说明用有理逼近比多项式逼近好得多.

158 例11 给出有理函数 用辗转相除法将它化为连分式并写成紧凑形式. 解 用辗转相除可逐步得到

159 本例中用连分式计算 的值只需3次除法，1次乘 法和7次加法.

160 若直接用多项式计算的秦九韶算法则需6次乘法和1次
除法及7次加法. 可见将 化成连分式可节省计算乘除法次数. 对一般的有理函数,（5.1）可转化为一个连分式 它的乘除法运算只需 次. 而直接用有理函数（5.1）计算乘除法次数为 次.

161 帕德逼近  利用函数 的泰勒展开可以得到它的有理逼近. 设 在 的泰勒展开为 （5.5） 它的部分和记作 （5.6）

162 定义8 设 如果有理函数 （5.7） 其中 无公因式，且满足条件 （5.8） 则称 为函数 在 处的 阶帕德逼近， 记作 ,简称 的帕德逼近.

163 根据定义，若令 则满足条件（5.8）等价于 即 （5.8） 由于 应用莱布尼兹求导公式得

164 这里 是由（5.6）得到的， 上式两端除 ， 并由 可得 （5.9） （5.6） 及 （5.10） 注意当 时 故（5.10）可写成

165 （5.11） 其中 时 ， 若记 （5.12）

166 则方程组（5.11）的矩阵形式为 定理11 （5.7）的有理函数 是 的 阶帕德逼近的 充分必要条件是多项式 的系数 及 满足方程组（5.9）及（5.11）. 设 则形如

167 根据定理11, 求 的帕德逼近时， 首先要由（5.11）解出 的系数 ， （5.11） 再由（5.9）直接算出 的系数 的各阶帕德逼近可列成一张表，称为帕德表（见表3-4）. （5.9）

168 例12 求 的帕德逼近 及 解 由 的泰勒展开 得 当 时，由（5.11）得 求得 再由（5.9）得

169 于是得 当 时，由（5.11）得

170 解得 代入（5.9）得 于是得

171 可以看到这里得到的 及 与 的前面 连分式展开得到的有理逼近（5.4）结果一样. 为了求帕德逼近 的误差估计，由(5.9)及(5.11) 求得的 系数 及 ，直 接代入则得 将 除上式两端，即得

172 （5.13） 其中 当 时可得误差近似表达式

173 3.6 三角多项式逼近与快速傅里叶变换 当模型数据具有周期性时，用三角函数特别是正弦和余
3.6 三角多项式逼近与快速傅里叶变换 当模型数据具有周期性时，用三角函数特别是正弦和余 弦函数作为基函数是合适的，这时前面讨论的用多项式、分 段多项式或有理函数作基函数都是不适合的. 用正弦函数和余弦函数级数表示函数称为傅里叶变换 （简称傅氏变换）.

174 3.6.1 最佳平方三角逼近与三角插值 设 是以 为周期的平方可积函数，用三角多 项式 （6.1） 做最佳平方逼近函数.
最佳平方三角逼近与三角插值 设 是以 为周期的平方可积函数，用三角多 项式 （6.1） 做最佳平方逼近函数. 由于三角函数族 在 上是正交函数族，于是 在 上的最小 平方三角逼近多项式 的系数是

175 （6.2） 称为傅里叶系数. 函数 按傅里叶系数展开得到的级数 （6.3） 就称为傅里叶级数.

176 只要 在 上分段连续，则级数（6.3）一致 收敛到 . 对于最佳平方逼近多项式（6.1）有 （6.3） （6.1） 由此可以得到相应于（3.11）的贝塞尔不等式 （3.11） 因为右边不依赖于 ，左边单调有界，所以级数

177 收敛，并有 当 只在给定的离散点集 上已知时，则可类似得到离散点集正交性与相应的离散傅 里叶系数. 下面只给出奇数个点的情形.

178 令 可以证明对任何 成立

179 这表明函数族 在点集 上正交. 若令 则 的最小二 乘三角逼近为 其中

180 （6.4） 当 时 于是 就是三角插值多项式，系数仍由（6.4）表示.

181 一般情形，假定 是以 为周期的复函数，给定 在 个等分点 上的值 由于 所以函数族 在区间 上是正交的. 函数 在等距点集 上的值 组成的向量记作

182 当 时， 个复向量 具有 如下正交性： （6.5）

183 事实上，令 若 则有 于是 即 若 则 从而

184 于是 若 则 于是 这就证明了（6.5）成立. 即 是正交的. 因此， 在 个点 上的 最小二乘傅里叶逼近为 （6.5）

185 （6.6） 其中 （6.7） 在（6.6）中， 若 ， 则 为 在点 上的插值函数， 即 于是由（6.6）得 （6.8）

186 （6.7）是由 求 的过程， 称为 的离散 傅里叶变换. 简称DFT， 而（6.8）是由 求 的过程，称为反变换. （6.7） （6.8）

187 3.6.2 点DFT与FFT算法 不论是按（6.7）式由 求 ， 或是按（6.8） 由 求 ， 还是由（6.4）计算傅里叶逼近系数
不论是按（6.7）式由 求 ， 或是按（6.8） 由 求 ， 还是由（6.4）计算傅里叶逼近系数 都可归结为计算 （6.4） （6.9） 其中 为已知的输入数据， 为输出数据，而

188 （6.9）式称为 点DFT，表面上看计算 需要 次复
数乘法和 次复数加法，称为 个操作，计算全部 共要 个操作. （6.9） 当 较大且处理数据很多时，就是用高速的电子计算 机，很多实际问题仍然无法计算， 直到20世纪60年代中期产生了FFT算法，大大提高了 运算速度，才使DFT得到更广泛的应用. FFT是快速算法的一个典范，其基本思想就是尽量减 少乘法次数.

189 对于任意正整数 ，成立 由周期性可知所有 中，做多有 个不 同的值 特别地，有 当 时， 只有 个不同的值. 利用这些性质可将（6.9）式对半折成两个和式，再将 对应项相加，有

190 依下标奇、偶分别考察，则 若令 则可将 点DFT归结为两个 点的DFT： 如此反复施行二分手续即可得到FFT算法.

191 以 为例说明FFT的计算方法，此时 在（6.9）中将 记为 ，于是（6.9）式的和为 （6.10） 将 用二进制表示为 其中 只能取0或1. 例如 根据 表示法，有

192 公式（6.10）可表示为 （6.10） （6.11） 若引入记号 （6.12）

193 则（6.11）变成 若注意 公式（6.12）还可进一步 简化为

194 将这表达式中二进制表示还原为十进制表示：
即 得 （6.13） 同样（6.12）中的 也可简化为 即

195 把二进制表示还原为十进制表示，得 （6.14） 同理（6.12）中 可简化为 即

196 表示为十进制，有 （6.15） 根据公式(6.13)，(6.14)，(6.15)，由 逐次计算到 见表3-5(略）. 从表3-5中看到计算全部8个 只用8次乘法运算和24次 加法运算.

197 上面推导的 的计算公式可类似地推广到 的情形. 根据公式(6.13)，(6.14)，(6.15)，一般情况的FFT 计算公式如下： （6.16） 其中 括号内的数代表它的位置，在计算机中代表存放数的地址.

198 一组 占用 个复数单元，计算时需给出两组单元，
从 出发， 由 到 算到 即为所求. 计算过程中只要按地址号存放 则最后得到的 就是所求离散频谱的次序. 这个计算公式除了具有不倒地址的优点外，计算只有两 重循环. 外循环 由 计算到 ，内循环 由 计算到 由 计算到 更重要的是整个计算过程省计算量.

199 由公式看到算一个 共做 次复数乘法， 而最后一步计算 时，由于 （注意 时 故 ），因此，总共要算 次复数乘法，它比直接用（6.9）需 次乘法 快得多，计算量比值是 当 时比值是 它比一般FFT的 计算量（ 次乘法）也快一倍. 我们称（6.16）的计算公式为改进的FFT算法 .

200 例13 设 给定 数据 确定三角插值多项式. 解 先将 变换为 ，可令 ， 故输入数据为 给定8个点可确定8个参数的4次三角插值多项式 （6.17） 这里 （6.18）

201 与（6.10）式比较可先计算 这里 代替（6.10）式的 ， 对每个 有

202 所以 即 显然 ，用FFT算法求出 ，也就 得到（6.18）式的系数，从而得到（6.17）式的4次三角 插值多项式

203 将 代入 可以得到 上的三角多项式 图3-6给出了 及 的图形. 表3-6给出了在点 处 与 的值. 图3-6

204 随机数据点上的二元拟合

205

206

207

208

209

210

211

212

213