Overview

多项式

  • 一些有趣的尝试

多项式和函数近似

  • Bézier curve
  • 连续的函数近似

多项式的运算

  • 快速傅里叶变换

本次课用到的代码 (Jupyter)

多项式

多项式：一种非常基础的数学对象

最基础的数学对象

多项式是连接它们的 “第一个纽带”

  • 所以和 $$ax^2 + bx + c$$ 有关的习题，从初中开始就做到吐了……

格局打开

把视角 “放大”

  • 一个多项式里可以包含很多信息！
    • 32-bit (float), 1,000 项：4 KB
    • (所以高考不会考)
  • 但我们真正感兴趣的问题：能用多项式放什么信息？


(以上图片均为 4 KB; jpeg v.s. webp)

一次有趣的尝试

$f(x) = ax^3 + bx^2 + cx + d$

  • 同时穿过 $(2, 1), (3, 7), (5, -2), (6, 1)$？
    • 这几个点是随便选的
    • $f(2) = 8a + 4b + 2c + d = 1$
    • $f(3) = 27a + 9b + 3c + d = 7$
    • $f(5) = 125a + 25b + 5c + d = -2$
    • $f(6) = 216a + 36b + 6c + d = 1$
    • Life is short (You need Python)

任给 $n$ 个 $x$ 坐标不同的点，恰好可以用唯一的 $n-1$ 次多项式穿过

  • Vandermonde 行列式——数学对象之间广泛的 “关联”

多项式的应用: 近似 “任何” 函数

平面上 “画出” 的任何线段都可以近似！

Bézier curve

  • ($0 \le t \le 1$)
  • $B(t) = P_0 + (P_1 - P_0) t$
  • $B(t) = (1 - t)^2 P_0 + 2t (1-t)P_1 + t^2 P_2$
    • TrueType Font
  • $B(t) = (1-t)^3 P_0 + 3t(1-t)^2 P_1 + 3t^2(1-t) P_2 + t^3 P_3$
    • SVG, PostScript, ... (可视化)
    • 一组 “四个点 (三次函数)” = “肉眼辨识” 极限
  • 多项式可能比我们想象的强大

(几乎) 任何函数都可以近似！

Weierstrass Approximation Theorem

  • “一切实连续函数在任意 $[a,b]$ 上皆可多项式逼近”

没啥不能近似的

  • $f(x) = \sin(x)$, $f(x) = e^x$, $f(x) = \frac{x^2 \log x}{x + 1}$
    • 注意这是一个非常强大的工具
    • 把 “难处理” 的函数变成了一个 $\sum{a_k x^k}$

但也总近似不好

  • 计算近似的 “尾巴” 就打开了 “高等数学” 世界的大门
  • Runge's Phenomenon

多项式的运算

我们能对多项式做什么？

$$\textrm{加减} \qquad f(x) \pm g(x)$$

$$\textrm{乘} \qquad f(x) \cdot g(x)$$

$$\textrm{除} \qquad \frac{f(x)}{g(x)}$$

除法很特殊

  • 结果不是再多项式
  • (模运算意义下就不一样了)
    • $a / b = a \cdot b^{-1}$
    • 然后各种妖魔鬼怪的题就来了…… (oiwiki)

多项式的表示方法

回顾：$n$ 个点可以确定一个 $n-1$ 次多项式

  • 平面三点确定二次函数
    • $f(x)$ 穿过 $(x_1, y_1), (x_2,y_2), (x_3,y_3)$
    • $f(x) = ax^2 + bx + c$
      • 这种题真的在中学做腻了……

试试能不能做点别的？

  • 能求 $f(x)$ 吗？
  • 能求 $f(x) + g(x)$ 吗？
  • 能求 $f(x) \cdot g(x)$ 吗？
    • 诶，变简单了！

Lagrangian Interpolation

给定 $x$ 不重合的 $(x_i, y_i)$ ($0 \le i \le n$)，多项式 $$ f(x) = \sum_{i=0}^{n} y_i p_i(x) $$ 满足 $f(x_i) = y_i$，其中 $$ p_i(x) = \prod_{0 \le j \le n,j\ne i} \frac{x-x_j}{x_i-x_j} $$

  • 背了公式？善用互联网：搜索 “Lagrangian interpolation intuition”
    • $p_0(x)$ 在 $x = x_0$ 时为 $1$，在其他 $x_i$ 时为 $0$
    • $p_1(x)$ 在 $x = x_1$ 时为 $1$，在其他 $x_i$ 时为 $0$
    • 然后带权加起来 $y_0 p_0(x) + y_1 p_1(x) + \ldots + y_n p_n(x)$

下一个问题

取任何 $n$ 个点都能表示一个多项式

  • 那取哪 $n$ 个点最好呢？
    • $1, 2, \ldots, n$
    • $\frac{1}{n}, \frac{2}{n}, \ldots, \frac{n-1}{n}$
      • 这个似乎好一些
      • 但还不够好
  • 能使得插值的计算能最快？
    • 如何不出现巨大的复杂分数？
    • 如果 $1 + 1 = 0$ 能 “回到原点” 就好了
      • 使用复数 - FFT (Fast Fourier Transformation)
      • 取模 - NTT (Number Theoretic Transformation)

Fast Fourier Transformation

两个重要的方向

  • $f(x) = A + Bx + Cx^2 + \ldots \Rightarrow f(1), f(\omega), f(\omega^2), \ldots$
    • 求值
    • 一个非常巧妙的分治法
  • $f(\omega), f(\omega^2), \ldots \Rightarrow A, B, C, \ldots$
    • 插值

多项式乘法的应用

用来表示数字

$f(x) = a x^3 + b x^2 + c x + d$

  • 代入 $x = 10$, $f(x)$ 可以表示一个四位数
  • 代入 $x = 100$, $f(x)$ 可以表示一个八位数
    • $a = 98$, $b = 76$, $c = 54$, $d = 32$

所以如果能求 $f(x) \cdot g(x)$，不就能求整数的乘法了吗？

  • 回顾多项式的能力：把 “整体” 化成 “简单局部” 的和

用来表示数字：太大材小用了

多项式可以连乘

  • $(1 + x + x^2 + \ldots)(1 + x + x^2 + \ldots) \ldots$
  • $x^k$ 的系数
    • 满足 $a + b + c + \ldots = k$ 的所有对应系数乘积的和
      • $a$ 是第一个多项式的 $x^a$
      • $b$ 是第二个多项式的 $x^b$
      • ……
    • 一大堆生成函数
      • 对于 $P(x)^k$ 还可以快速幂

用来表示生成函数：太大材小用了

The JPEG Standard (ISO/ISEC 10918-1)

  • “锯齿” 和 “色块” 不是偶然的！
  • 把 $8\times8$ 的小块用 64 个 “色块” 的线性组合表示 (sum of product)

总结

多项式

一个非常有趣的基础数学对象

  • $ax^2 + bx + c$
    • “Sum of product”
    • 求和使我们能分开/并行求解
    • $x^k$ 作为基础的数学对象更容易处理