24 第九章函数逼近 L(e)的递推计算公式： Lk+1(x)=(2k+1-x)Lk(x)-k2Lk-1(x),k=1,2,·,n, (9.21) L0(x)=1,L1(x)=1-x. 5)埃尔米特(Hermite)多项式 设p(x)=e-2,区间(-o,+o∞)上Pn(e)的正交基{Hk(e)}R=o,称H(z)为埃 尔米特多项式.埃尔米特多项式的解析表达式 =-rege=01…n (9.22) Lk(x)的递推计算公式： Hk+1(x)=2xHk(x)-2kH-1(x),k=1,2,·,n, (9.23) Lo(x)=1,L1(x)=2x. 关于正交多项式及其应用的更多内容，可参阅文献[⑧： 例9.10设f(x)=si(πx),利用正交多项式理论，求f(x)在区间0,1上的二次 最佳平方逼近多项式。 解令t=2x-1,则t∈【-1,1，函数f可写成关于t的函数，即 f)=sim「化+m 2 根据勒让德多项式的定义，有 B0=1,n(0=t,20=3-l 2 容易算得 (P,P)=2,(B,B)=2/3,(P,PB)=2/5 -1 GA)-m4]女-a =厂”]业= 2 3
24 第九章 函数逼近 Lk(x) 的递推计算公式: Lk+1(x) = (2k + 1 − x)Lk(x) − k 2Lk−1(x), k = 1, 2, · · · , n, L0(x) = 1, L1(x) = 1 − x. (9.21) 5) 埃尔米特 (Hermite) 多项式 设 ρ(x) = e −x 2 , 区间 (−∞, +∞) 上 Pn(x) 的正交基 {Hk(x)} n k=0, 称 Hk(x) 为埃 尔米特多项式. 埃尔米特多项式的解析表达式 Hk(x) = (−1)n e x 2 d k dx k (e −x 2 ), k = 0, 1, · · · , n. (9.22) Lk(x) 的递推计算公式: Hk+1(x) = 2xHk(x) − 2kHk−1(x), k = 1, 2, · · · , n, L0(x) = 1, L1(x) = 2x. (9.23) 关于正交多项式及其应用的更多内容, 可参阅文献 [8]. 例 9.10 设 f(x) = sin(πx), 利用正交多项式理论, 求 f(x) 在区间 [0, 1] 上的二次 最佳平方逼近多项式. 解 令 t = 2x − 1, 则 t ∈ [−1, 1], 函数 f 可写成关于 t 的函数, 即 f(t) = sin [ (t + 1)π 2 ] . 根据勒让德多项式的定义, 有 P0(t) = 1, P1(t) = t, P2(t) = 3t 2 − 1 2 . 容易算得 (P0, P0) = 2, (P1, P1) = 2/3, (P2, P2) = 2/5, (f, P0) = ∫ 1 −1 sin [ (t + 1)π 2 ] dx = 4 π , (f, P1) = ∫ 1 −1 tsin [ (t + 1)π 2 ] dx = 0, (f, P2) = ∫ 1 −1 3t 2 − 1 2 sin [ (t + 1)π 2 ] dx = 4(π 2 − 12) π 3
9.5周期函数的最佳平方逼近与快速傅立叶变换 25 按式(9.5)有 0=×2x0+0xgxB0+2x号xB0 分3 -2+-163e- 将t=2x-1代入上式并化简得 i=122-120_60m2-720+60m2-7202 T3 元3 与例9.9的结果一致. ◇ 通过对比，容易看出利用正交多项式理论可以避免求解法方程组，从而适用于法方 程组的系数是病态的情形 9.5周期函数的最佳平方逼近与快速傅立叶变换 在科学与工程领域，傅立叶分析作为最基本的数学工具，被广泛应用于信号的时频 域分析、谱分析、微分方程求解等.法国数学家傅立叶(Fourier)出生于l768年，他具 有代表性的一项工作是研究热的传播和扩散现象.在此过程中，他发现在表示一个物 体的温度分布时，三角函数级数非常有用.不仅如此，他大胆断言：“任何”周期函数都 可以表示为三角函数级数的形式，即傅立叶级数.对于非周期信号，傅立叶指出可用三 角函数的加权积分来表示，即傅立叶变换.傅立叶变换与傅立叶级数有一个共同的重 要性质，即可以通过反变换恢复原来的表示 首先，我们讨论连续情形的傅立叶级数.考虑区间O,T)上的平方可积函数空间 L2[0,T),使用式(9.2)定义的内积及其诱导的范数.若规定f(x)=f(x-T),x∈R,则 可将L2[0,T)中的任一函数延拓为实数域R上周期为T的函数.在此意义下，2[0，T) 称为周期为T的平方可积函数空间. 若取[0，T)上的逼近函数空间M=span{po,p1,·,P2n,其中 cos,Pa=sin kur,.. 容易验证三角多项式函数系{}o构成M的一组正交基.利用定理9.8和9.9知，对于 任意的函数f(x)∈L2[0,T),存在唯一的最佳平方逼近元fn(x)∈M,且有 人创=空+2a:o+nk. k=1
9.5 周期函数的最佳平方逼近与快速傅立叶变换 25 按式 (9.5) 有 p ∗ 2 (t) = 4 π × 1 2 × P0(t) + 0 × 3 2 × P1(t) + 4(π 2 − 12) π 3 × 5 2 × P2(t) = 2 π + 5(π 2 − 12)(3t 2 − 1) π 3 . 将 t = 2x − 1 代入上式并化简得 p ∗ 2 (x) = 12π 2 − 120 π 3 − 60π 2 − 720 π 3 x + 60π 2 − 720 π 3 x 2 , 与例9.9的结果一致. 通过对比, 容易看出利用正交多项式理论可以避免求解法方程组, 从而适用于法方 程组的系数是病态的情形. 9.5 周期函数的最佳平方逼近与快速傅立叶变换 在科学与工程领域, 傅立叶分析作为最基本的数学工具, 被广泛应用于信号的时频 域分析、谱分析、微分方程求解等. 法国数学家傅立叶 (Fourier) 出生于 1768 年, 他具 有代表性的一项工作是研究热的传播和扩散现象. 在此过程中, 他发现在表示一个物 体的温度分布时, 三角函数级数非常有用. 不仅如此, 他大胆断言: “任何” 周期函数都 可以表示为三角函数级数的形式, 即傅立叶级数. 对于非周期信号, 傅立叶指出可用三 角函数的加权积分来表示, 即傅立叶变换. 傅立叶变换与傅立叶级数有一个共同的重 要性质, 即可以通过反变换恢复原来的表示. 首先, 我们讨论连续情形的傅立叶级数. 考虑区间 [0, T) 上的平方可积函数空间 L 2 [0, T), 使用式 (9.2) 定义的内积及其诱导的范数. 若规定 f(x) = f(x−T), ∀x ∈ R, 则 可将 L 2 [0, T) 中的任一函数延拓为实数域 R 上周期为 T 的函数. 在此意义下, L 2 [0, T) 称为周期为 T 的平方可积函数空间. 若取 [0, T) 上的逼近函数空间 M = span{φ0, φ1, · · · , φ2n}, 其中 φ0 = 1 2 , φ2k = cos kωx, φ2k−1 = sin kωx, k = 1, 2, · · · , n, ω = 2π T . 容易验证三角多项式函数系 {φi} 2n i=0 构成 M 的一组正交基. 利用定理9.8和9.9知, 对于 任意的函数 f(x) ∈ L 2 [0, T), 存在唯一的最佳平方逼近元 fn(x) ∈ M, 且有 fn(x) = a0 2 + ∑n k=1 ( ak cos kωx + bk sin kωx) ,
26 第九章函数逼近 其中 Ok= (P2k) 2 ()c,k=0,1…,n 2,p2=70 (9.24) （,P2k-1）2 由数学分析中的Fourier级数理论知，最佳平方逼近三角多项式fn(x)恰好是f(z) 的Fourier级数的部分和，而a,bk为Fourier系数.此外，利用Fourier级数的收敛性定 理可得：limf-fnl=0,即fn(e)平方收敛到f(x) 利用Euler公式e"=cos0+isin,Fourier级数可以写成复数形式 f)=∑ k=- 其中 o4=T人(e)ed血 例9.I1设f(x)=z,求f(x)在区间【-π，上的n次最佳平方逼近三角多项 式 解设∫(x)在区间【-π，]上的n次最佳平方逼近三角多项式为 ia()=罗+∑a匙cosk+smka).u===l 按式(9.24)，展开系数 w=d=人xd= 2 f f()cos kr dar =2 sr立=是-- f()sin kr dr=2 Jo (x-x)sinkx dx =0. 其中k=1,2,…,n.因此有 回=+2-1-cws 2 当n=0,1,3时，函数图像如图9.3所示
26 第九章 函数逼近 其中 ak = (f, φ2k) (φ2k, φ2k) = 2 T ∫ T 0 f(x) cos kωx dx, k = 0, 1, · · · , n, bk = (f, φ2k−1) (φ2k−1, φ2k−1) = 2 T ∫ T 0 f(x)sin kωx dx, k = 0, 1, · · · , n. (9.24) 由数学分析中的 Fourier 级数理论知, 最佳平方逼近三角多项式 fn(x) 恰好是 f(x) 的 Fourier 级数的部分和, 而 ak, bk 为 Fourier 系数. 此外, 利用 Fourier 级数的收敛性定 理可得: lim n→∞ ∥f − fn∥ = 0, 即 fn(x) 平方收敛到 f(x). 利用 Euler 公式 e iθ = cos θ + i sin θ, Fourier 级数可以写成复数形式 f(x) = ∑ +∞ k=−∞ cke ikωx , 其中 ck = 1 T ∫ T 0 f(x)e −ikωx dx. 例 9.11 设 f(x) = |x|, 求 f(x) 在区间 [−π, π] 上的 n 次最佳平方逼近三角多项 式. 解 设 f(x) 在区间 [−π, π] 上的 n 次最佳平方逼近三角多项式为 fn(x) = a0 2 + ∑n k=1 ( ak cos kωx + bk sin kωx) , ω = 2π T = 1. 按式 (9.24), 展开系数 a0 = 1 π ∫ π −π f(x) dx = 2 π ∫ π 0 x dx = π, ak = 1 π ∫ π −π f(x) cos kx dx = 2 π ∫ π 0 x cos kx dx = 2 πk2 [(−1)k − 1], bk = 1 π ∫ π −π f(x)sin kx dx = 2 π ∫ π 0 (x − x)sin kx dx = 0, 其中 k = 1, 2, · · · , n. 因此, 有 fn(x) = π 2 + 2 π ∑n k=1 [(−1)k − 1] k 2 cos kx. 当 n = 0, 1, 3 时, 函数图像如图9.3所示.
9.5周期函数的最佳平方逼近与快速傅立叶变换 27 f(r) Ps(z) Pi() po(r) -3 -2 -1 图9.3：函数f(x)=z在区间【-元，元上的最佳平方逼近三角多项式 下面我们讨论离散情形的傅立叶级数.在许多实际问题中，譬如信号处理，函 数∫(x)是未知的，但是∫(x)在某些时刻的值可以通过测量的方式获得.数学上，设 f(x)∈L20,T),己知f(x)在一系列等距离散点上的值，即 h=f(rk).t=kT k=0,1,2,…,n-1 明显地，(o,1,·,∫n-1)T∈C.若在L20,T)上定义离散的内积和诱导的拟范数 (J.g)->f9 Vf.geL20.T). k=0 IfI=V,f,f∈20，T), 利用公式(9.5)及{1，ewr,e2wx,…,em-1)wr}的正交性，即 (er,e）=e6-w= 0,j≠1 k=司 n,j=l, 则fe)的离散数据{ek,)}在空间M=span{1,e,e2,…,e(m-1r}的最 佳平方逼近元为 sn回=e,=c-e 0 n n k=0 特别地，当m=n时，插值条件sn(xk)=f(z),k=0,1,·,n-1成立，称sn(z)为 f(x)的一1次插值三角多项式.利用插值三角多项式的系数与样本值之间的关系，来 定义离散傅立叶变换及其逆变换
9.5 周期函数的最佳平方逼近与快速傅立叶变换 27 f(x) p3(x) p1(x) p0(x) −3 −2 −1 0 1 2 3 x 1 2 3 y 图 9.3: 函数 f(x) = |x| 在区间 [−π, π] 上的最佳平方逼近三角多项式 下面, 我们讨论离散情形的傅立叶级数. 在许多实际问题中, 譬如信号处理, 函 数 f(x) 是未知的, 但是 f(x) 在某些时刻的值可以通过测量的方式获得. 数学上, 设 f(x) ∈ L 2 [0, T), 已知 f(x) 在一系列等距离散点上的值, 即 fk = f(xk), xk = k T n , k = 0, 1, 2, · · · , n − 1. 明显地, (f0, f1, · · · , fn−1) T ∈ C n . 若在 L 2 [0, T) 上定义离散的内积和诱导的拟范数 (f, g) = ∑n−1 k=0 fk · gk , ∀f, g ∈ L 2 [0, T), ∥f∥ = √ (f, f), ∀f ∈ L 2 [0, T), 利用公式 (9.5) 及 {1, eiωx, ei2ωx , · · · , ei(m−1)ωx} 的正交性, 即 (e ijx, eilx) = ∑n−1 k=0 e i(j−l)ωxk = 0, j ̸= l, n, j = l, 则 f(x) 的离散数据 {(xk, fk)} n−1 k=0 在空间 M = span{1, eiωx, ei2ωx , · · · , ei(m−1)ωx} 的最 佳平方逼近元为 sm(x) = m∑−1 l=0 gle ilωx, gl = (f, eilωx) n = 1 n ∑n−1 k=0 fke −ilωxk . 特别地, 当 m = n 时, 插值条件 sn(xk) = f(xk), k = 0, 1, · · · , n − 1 成立, 称 sn(x) 为 f(x) 的n − 1 次插值三角多项式. 利用插值三角多项式的系数与样本值之间的关系, 来 定义离散傅立叶变换及其逆变换
8 第九章函数逼近 定义9.10设有向量f=(fo,1,…,n-)T∈C”,称向量 g=(90,91,…,gn-1)T∈Cn 为向量f的离散傅立叶变换(Discrete Fourier Transform,DFT),其中 =2he-wn1=l…n-1 n K=0 反之，称向量「为向量g的离散傅立叶逆变换，即 j方=∑9e2m,j=0,1…,n-1. =0 利用线性代数的语言，离散傅立叶变换可写成 0 00 fo 00 p 03 n-I 92 03 0 2m-1 f2 >g=Fnf(9.25) (oo pn-1 p2n-1) pn-1)2 其中p=e-2mn,称Fn为傅立叶变换矩阵.容易看出，Fn是对称矩阵，且除了第一行 (列)外，矩阵的每一行（列）元素之和为零.此外，Fn满足Fn可=I/m,即Fn/元是酉 阵.因此，傅立叶变换矩阵Fn的逆为 p -(n-1】 Fn=nFn -2(n-1) p-a-1p-2n-1) p-a-1) 即离散傅立叶逆变换的矩阵表示。 在许多工程领域，利用计算机进行Fourier分析的主要方法是离散傅立叶变换.从 式(925)不难看出，计算离散傅立叶变换需要n2次乘法，n(n-1)次加法及n次除法， 故时间复杂度为O(2).类似地，离散傅立叶逆变换的时间复杂度亦为O(n).然而，当 N很大时，运算量会变得相当大，即使用高速计算机，也需要花费大量的时间.正因为
28 第九章 函数逼近 定义 9.10 设有向量 f = (f0, f1, · · · , fn−1) T ∈ C n , 称向量 g = (g0, g1, · · · , gn−1) T ∈ C n 为向量 f 的离散傅立叶变换 (Discrete Fourier Transform, DFT), 其中 gl = 1 n ∑n−1 k=0 fke −i2πlk/n , l = 0, 1, · · · , n − 1. 反之, 称向量 f 为向量 g 的离散傅立叶逆变换, 即 fj = ∑n−1 k=0 gle i2πjk/n , j = 0, 1, · · · , n − 1. 利用线性代数的语言, 离散傅立叶变换可写成 g0 g1 g2 . . . gn−1 = 1 n ρ 0 ρ 0 ρ 0 · · · ρ 0 ρ 0 ρ 1 ρ 2 · · · ρ n−1 ρ 0 ρ 2 ρ 4 · · · ρ 2(n−1) . . . . . . . . . . . . . . . ρ 0 ρ n−1 ρ 2(n−1) · · · ρ (n−1)2 f0 f1 f2 . . . fn−1 ⇐⇒ g = Fnf, (9.25) 其中 ρ = e −i2π/n , 称 Fn 为傅立叶变换矩阵. 容易看出, Fn 是对称矩阵, 且除了第一行 (列) 外, 矩阵的每一行 (列) 元素之和为零. 此外, Fn 满足 FnFT n = I/n, 即 Fn/ √ n 是酉 阵. 因此, 傅立叶变换矩阵 Fn 的逆为 F −1 n = nFn = ρ 0 ρ 0 ρ 0 · · · ρ 0 ρ 0 ρ −1 ρ −2 · · · ρ −(n−1) ρ 0 ρ −2 ρ −4 · · · ρ −2(n−1) . . . . . . . . . . . . . . . ρ 0 ρ −(n−1) ρ −2(n−1) · · · ρ −(n−1)2 , 即离散傅立叶逆变换的矩阵表示. 在许多工程领域, 利用计算机进行 Fourier 分析的主要方法是离散傅立叶变换. 从 式 (9.25) 不难看出, 计算离散傅立叶变换需要 n 2 次乘法, n(n − 1) 次加法及 n 次除法, 故时间复杂度为 O(n 2 ). 类似地, 离散傅立叶逆变换的时间复杂度亦为 O(n 2 ). 然而, 当 N 很大时, 运算量会变得相当大, 即使用高速计算机, 也需要花费大量的时间. 正因为