补充学习材料.pdf

GAMES102 学习材料 (1) 1 函数插值 在许多实际问题中，某个函数 f (x) 往往很复杂、没有解析表达或者未知。我们往往只能通过某些手段 观测到反映该函数的一些采样数据。我们希望通过这些观测的采样数据来估计该函数的信息，并预测函数 在其他观测点的值。这时，我们从观测数据来求得一个函数 ϕ(x) 来近似 f (x)。 定义：f (x) 为定义在区间 [a, b] 上的函数，x0 , x1 , · · · , xn 为区间上 n + 1 个互不相同的点，Φ 为给定 的某一函数类。求 Φ 上的函数 ϕ(x)，满足： ϕ(xi ) = f (xi ), i = 0, 1, · · · , n 则称 ϕ(x) 为 f (x) 关于节点 x0 , x1 , · · · , xn 在 Φ 上的插值函数。称 x0 , x1 , · · · , xn 为插值节点，称 (xi , f (xi )) 为插值点。 1.1 多项式插值定理 定理：若 xi 两两不同，则对任意给定的 yi ，存在唯一的次数至多是 n 次的多项式 pn ，使得 pn (xi ) = yi �i = 0, · · · , n。 证明：在幂基 {1, x, · · · , xn } 下待定多项式 p 的形式为： p(x) = a0 + a1 x + a2 x2 + · · · + an xn 由插值条件 p(xi ) = yi , i = 0, · · · , n，得到如下方程组：      1 x0 x20 . . . xno a y    0  0 1 x x2 . . . xn   a   y  1   1 1 1   1       1 x2 x22 . . . xn2   a2  =  y2        .. ..   ..   ..  . . . . . . . .  .   .  . . .      1 xn x2n ... xnn an yn 系数矩阵为 Vandermonde 矩阵，其行列式非零，因此方程组有唯一解。 1.2 不同形式的插值多项式 对于给定问题，插值多项式存在唯一。但是可以用不同的方法给出插值多项式的不同表示形式。 1 1.2.1 Lagrange 插值 Lagrange 基函数：由多项式插值定理存在函数 li (x) 满足 li (xj ) = σij ： Y li (x) = j=0,j̸=i Lagrange 插值多项式： Ln (x) = n X x − xj xi − xj yk lk (x) k=0 1.2.2 Newton 插值 定义： 一阶差商： f [x0 , x1 ] = f (x1 ) − f (x0 ) x1 − x0 k 阶差商： 设 {x0 , x1 , · · · , xk } 互不相同，f (x) 关于 {x0 , x1 , · · · , xk } 的 k 阶差商为： f [x0 , x1 , · · · , xk ] = f [x1 , · · · , xk ] − f [x0 , x1 , · · · , xk−1 ] xk − x0 所以 Newton 插值多项式表示为： Nn (x) = f (x0 ) + f [x0 , x1 ](x − x0 ) + · · · + f [x0 , x1 , · · · , xn ](x − x0 ) · · · (x − xn−1 ) 2 2 函数拟合 函数拟合是指：给出一组离散的点，需要确定一个函数来逼近原函数。由于离散数据通常是由观察或 测试得到的，所以不可避免的会有误差。我们需要的逼近原函数的手段要满足如下两个条件： 1. 不要求过所有的点（可以消除误差影响） 2. 尽可能表现数据的趋势，靠近这些点 用数学的语言来说即是，需要在给定的函数空间 Φ 上找到函数 ϕ，使得 ϕ 到原函数 f 的距离最小。这 里的距离指的是某种度量，不同的度量对应着不同的拟合方法。则函数 ϕ(x) 称为 f (x) 在空间 Φ 上的拟合 曲线。 2.1 函数拟合的最小二乘法问题 定义：f (x) 为定义在去区间 [a, b] 上的函数，{xi }m i=0 为区间上 m + 1 个互不相同的点，Φ 为给定的某 一函数类。求 Φ 上的函数 ϕ(x) 满足 f (x) 和 ϕ(x) 在给定的 m + 1 个点上的距离最小，如果这种距离取为 2-范数的话，则称为最小二乘问题。即：求 ϕ(x) ∈ Φ，使得： v um uX R2 = t (ϕ(xi ) − f (xi ))2 i=0 最小。 2.1.1 最小二乘问题的求解 首先给出如下离散内积与离散范数的定义： 定义：函数 f, g 的关于离散点列 {xi }m i=0 的离散内积为： (f, g)h = n X f (xi )g(xi ) i=0 定义: 函数 f 的离散范数为： ||f ||h = p (f, f )h 该种内积下，范数的定义与向量的 2 范数一致。 注：上述定义中的下标 h 表示对离散内积与离散范数的指代，类似 1-范数的定义 ||x||1 = 无其他特殊含义。 设 Φ = span{ϕ0 , ϕ1 , · · · , ϕn } ϕ(x) = a0 ϕ0 (x) + a1 ϕ1 (x) + · · · + an ϕn (x) 3 Pn i=1 |xi |， 则最小二乘问题为： ||f (x) − (a0 ϕ0 (x) + a1 ϕ1 (x) + · · · + an ϕn (x))||h 关于系数 {a0 , a1 , · · · , an } 最小。 ||f (x) − (a0 ϕ0 (x) + a1 ϕ1 (x) + · · · + an ϕn (x))||2h =||f ||2h − 2(f, a0 ϕ0 (x) + a1 ϕ1 (x) + · · · + an ϕn (x))h + ||a0 ϕ0 (x) + a1 ϕ1 (x) + · · · + an ϕn (x)||2h =||f ||2h − 2 n X ak (f, ϕk )h + k=0 n X ai ak (ϕi , ϕk )h i,k=0 =Q(a0 , a1 , · · · , an ) 由于它关于系数 a0 , a1 , · · · , an 最小，因此有 ∂Q = 0, i = 0, 1, · · · , n ∂ai n X i.e. ak (ϕi , ϕk )h = (f, ϕi )h , i = 0, 1, · · · , n k=0 写成矩阵形式有：  (ϕ0 , ϕ0 )h  ..  .      (ϕ0 , ϕn )h a0 (f, ϕ0 )h  .    .. ..   ..  =   . .     (ϕn , ϕn )h an (f, ϕn )h ... .. . (ϕn , ϕ0 )h . . . 2.1.2 线性拟合 例 1：取 Φ 为线性多项式空间，函数空间的基为 {1, x}, 拟合曲线为 y = a + bx，则法方程为： (1, 1)h (1�x)h ! (x, 1)h (x, x)h ! a b = (f, 1)h ! (f, 2)h 2.1.3 二次拟合 例 2：取 Φ 为线性多项式空间，函数空间的基为 {1, x, x2 }, 拟合曲线为 y = a0 + a1 x + a2 x2 ，则法方 程为：  (1, 1)h (1�x)h   (x, 1)h (x, x)h  (x2 , 1)h (x2 , x)h     a0 (f, 1)h h     2     (x, x )h  a1  =  (f, x)h   2 2 2 (x , x )h a2 (f, x )h (1, x2 ) 4 Weierstrass 第一逼近定理 3 定理：设 f (x) 是闭区间 [a, b] 上的连续函数，则存在多项式序列 Pn (x) 在 [a, b] 上一致收敛于 f (x)。 也就是对任意给定的 ϵ > 0，存在多项式 P (x)，使得： |P (x) − f (x)| < ϵ 对一切 x ∈ [a, b] 成立。 证：不失一般性，设 [a, b] 为 [0, 1]，使用构造性的证明。 设 X 是 [0, 1] 上连续函数 f (t) 的全体构成的集合，Y 是多项式全体构成的集合，定义映射： Bn : X → Y f (t) 7→ Bn (f, x) = n X k=0 k f ( )Cnk xk (1 − x)n−k n 得到 Bn (f, x)，Bn (f, x) 表示 f ∈ X 在映射 Bn 作用下的像，它是以 x 为变量的 n 次多项式，称为 f 的 n 此 Bernstein 多项式。 关于映射 Bn , 有下述基本性质与基本关系式： 1. 线性性: 对于任意 f, g ∈ X 及 α, β ∈ R，成立 Bn (αf + βg, x) = αBn (f, x) + βBn (g, x) 2. 单调性: 若 f (t) ≥ g(t)(t ∈ [a, b]), 则 Bn (f, x) ≥ Bn (g, x) x ∈ [a, b] 3. Bn (1, x) = n X Cnk xk (1 − x)n−k = 1 k=0 Bn (t, x) = 2 n X k n k=0 n X Bn (t , x) = k=0 Cnk xk (1 − x)n−k = x x − x2 k2 k k n−k 2 C x (1 − x) =x + n2 n n 函数 (t − s)2 在 Bn 映射下的像 (视 s 为常数): Bn ((t − s)2 , x) = Bn (t2 , x) − 2sBn (t, x) + s2 Bn (1, x) = x2 + x − x2 x − x2 − 2sx + s2 = (x − s)2 + n n 5 由于 f 在 [0, 1] 上连续，所以有界，即存在 M > 0，对于一切 t ∈ [0, 1]，成立： |f (t)| ≤ M 根据 Cantor 定理，f 在 [0, 1] 上一致连续，于是对于任意给定的 ϵ > 0，存在 δ > 0，对一切 t, s ∈ [0, 1]: 当 |t − s| < δ 时，成立： |f (t) − f (s)| < 当 |t − s| ≥ δ 时，成立： |f (t) − f (s)| ≤ 2M ≤ ϵ 2 2M (t − s)2 δ2 于是对一切 t, s ∈ [0, 1], 成立： |f (t) − f (s)| ≤ ϵ 2M + 2 (t − s)2 2 δ 即： ϵ 2M ϵ 2M − − 2 (t − s)2 ≤ f (t) − f (s) ≤ + 2 (t − s)2 2 δ 2 δ 对上式左端，中间，右端三式（视 t 为变量，s 为常数）考虑在映射 Bn 作用下的像，得到对一切 x, s ∈ [0, 1]，成立： x − x2 ϵ 2M x − x2 ϵ 2M ] ≤ Bn (f, x) − f (s) ≤ + 2 [(x − s)2 + ] − − 2 [(x − s)2 + 2 δ n 2 δ n 令 s = x，注意到 x(1 − x) ≤ 41 ，即得到对一切 x ∈ [0, 1]，成立： | n X k=0 k ϵ M f ( )Cnk xk (1 − x)n−k − f (x)| ≤ + n 2 2nδ 2 取 N = d δM2 ϵ e，当 n > N 时： | n X k=0 k f ( )Cnk xk (1 − x)n−k − f (x)| < ϵ n 对一切 x ∈ [0, 1] 成立。 ■ 6 4 Weierstrass 第二逼近定理 定理：设 f (x) 是以 2π 为周期的连续函数，则存在三角多项式序列一致收敛于 f (x)。也就是对于任意 给定的 ϵ > 0，存在三角多项式 T (x)，使得: |T (x) − f (x)| < ϵ 对一切 x ∈ (−∞, +∞) 成立。 先证明一个引理： 引理：设 g(x) 在 [0, π] 上连续，则对于任意 ϵ > 0，存在余弦三角多项式 T (x)，使得： |T (x) − g(x)| < ϵ 对一切 x ∈ [0, π] 成立。 证：由 g(arccos y) 在 [−1, 1] 上连续，由 Weierstrass 第一逼近定理，对任意 ϵ > 0，存在多项式 P (y)， 使得： |P (y) − g(arccos y)| < ϵ 对一切 y ∈ [−1, 1] 成立，即： |P (cos x) − g(x)| < ϵ 对一切 x ∈ [0, π] 成立。由三角恒等式 1 cos2 x = (1 + cos 2x), 2 1 cos3 x = (3 + cos 3x), 4 ··· , 2n cos x= 1 22n−1 n−1 X ( k=1 1 n k C2n cos 2(n − k)x + C2n ), 2 n 1 X k 2n+1 cos x = 2n C2n+1 cos (2n − 2k + 1)x 2 k=0 可知 P (cos x) = T (x) 是余弦三角多项式。 推论：设 g(x) 是以 2π 为周期的连续偶函数，则 Weierstrass 第二逼近定理成立，且三角多项式是余 弦三角多项式。 Weierstrass 第二逼近定理的证明： 设 f (x) 是以 2π 为周期的连续函数，令： ϕ(x) = f (x) + f (−x), ψ(x) = [f (x) − f (−x)] sin x 7 则 ϕ(x) 和 ψ(x) 都是以 2π 为周期的连续偶函数，由上面推论，可知对任意给定的 ϵ > 0，存在余弦三角多 项式 T1 (x) 与 T2 (x)，使得： ϵ ϵ |ϕ(x) − T1 (x)| < , |ψ(x) − T2 (x)| < 2 2 对一切 x ∈ (−∞, +∞) 成立。 记 T3 (x) = T1 (x) sin2 x + T2 (x) sin x，于是由： ϵ ϵ |ϕ(x) sin2 x − T1 (x) sin2 x| < , |ψ(x) sin x − T2 (x) sin x| < 2 2 得到： |2f (x) sin2 x − T3 (x)| < ϵ (1) 对一切 x ∈ (−∞, +∞) 成立。由于上式对 f (t − π2 ) 也成立，于是也有： |2f (t − π ) sin2 t − T4 (t)| < ϵ 2 令 x = t − π2 ，得到： |2f (x) cos2 x − T4 (x + π )| < ϵ 2 (2) 对一切 x ∈ (−∞, +∞) 成立。 记 T5 (x) = 12 [T3 (x) + T4 (x + π2 )]，结合(1)和(2)，得到： |f (x) − T5 (x)| < ϵ 对一切 x ∈ (−∞, +∞) 成立。 ■ 8 5 距离空间的完备性 定义：设 X 是距离空间，{xn } ⊂ X。{xn } 是 X 中的基本列，是指对任意 ϵ > 0，存在 N = N (ϵ)， 当 m, n > N 时，有 ρ(xm , xn ) < ϵ。 定义：称 X 是完备距离空间，是指 X 中的任何基本列都收敛于 X 中的点。 例：C[a, b] 按距离 ρ(x, y) = max |x(t) − y(t)| 是完备距离空间。 9 Fourier 级数 6 首先，周期函数是客观世界中周期运动的数学表述，如物体挂在弹簧上作简谐振动、单摆振动、无线 电电子振荡器的电子振荡等，大多可以表述为： f (t) = A sin(ωt + ψ) 这里 t 表示时间，A 表示振幅，ω 为角频率，ψ 为初相（与考察时设置原点位置有关，可以理解为一个常 量）。 然而，世界上许多周期信号并非正弦函数那么简单，如方波、三角波等。于是傅里叶在其著作《热的 解析理论》中，推导出用一系列的三角函数 An sin(nωt + ψn ) 之和来表示那个较复杂的周期函数 f (x)，即： ∞ X f (t) = A0 + An sin(nωt + ψn ) (3) n=1 由 ψn 为常数，An 也是常数，则对上式进行变形： An sin(nωt + ψn ) = An sin ψn cos(nωt) + An cos ψn sin(nωt) 记 an = An · sin ψn , bn = An cos ψn ，则(3)可写为如下形式： f (t) = A0 + ∞ X [an cos(nωt) + bn sin(nωt)] (4) n=1 即是常见的 Fourier 级数形式。 系数求解 6.1 对(4)式从 [−π, π] 积分，得： Z π Z π f (t)dt = −π −π Z π = −π A0 dt + Z π X ∞ [an cos(nωt) + bn sin(nωt)]dt −π n=1 A0 dt + 0 = 2πA0 1 解得：A0 = 2π Rπ −π f (t)。 这样就求得了第一个系数 A0 的表达式，接下来求 an 和 bn 的表达式。用 cos(kωt) 乘(4)式两边得： f (t) · cos(kωt) = A0 cos(kωt) + ∞ X [an cos(nωt) cos(kωt) + bn sin(nωt) cos(kωt)] n=1 对上式从 [−π, π] 积分，得： Z π −π f (t) · cos(kωt)dt = A0 Z π cos(kωt)dt + −π ∞ X Z π Z π [an n=1 −π 10 cos(nωt) cos(kωt)dt + bn sin(nωt) cos(kωt)dt] −π 由三角函数系的正交性，A0 和 bn 后积分均为 0，an 后积分当且仅当 k = n 时不为 0，所以： Z π f (t) · cos(nωt)dt = an intπ−π cos2 (nωt)dt −π Z an π = (1 + cos 2nωt)dt 2 −π Z π Z π an = ( 1dt + cos 2nωtdt) 2 −π −π an = 2̇π = an π 2 解得： 1 an = π 同理用 sin(kωt) 乘(4)式两边得： 1 bn = π 令 a0 = 2A0 则有： Z π −π Z π −π f (t) · cos(nωt)dt f (t) · sin(nωt)dt ∞ a0 X f (t) = + [an cos(nωt) + bn sin(nωt)] 2 n=1 11