Bernstein Polynomial

雖然 Bernstein polynomial 看起來已經是很真實、「可以摸到」的函數了,但是用數學家的方式看 Bernstein polynomial 還是有點飄渺 XD。給一個閉區間上的連續函數和誤差 epsilon,若要造出一個每一點誤差都小於 epsilon 的 Bernstein polynomial,首先要確定 n 的值,而 n 的值取決於 uniform continuous 的 delta 值(among other values),這個 delta 值是用「[a, b] 為 compact」造出 finite subcovering 得到,而促成「[a, b] 為 compact」的 Heine-Borel 定理完全是存在式的定理。這個狀況和 Knuth 在〈Computer Science and its Relation to Mathematics〉(《Selected Papers on Computer Science》,p.8)描述的真實故事如出一轍:

The following true story is perhaps the best way to explain the distinction I have in mind. Some years ago I had just learned a mathematical theorem from which it followed that any two n \times n matrices A and B of integers have a "greatest common right divisor" D. This means that D is a right divisor of A and of B, i.e., A = A' D and B = B' D for some integer matrices A' and B', and that every common right divisor of A and B is a right divisor of D. So I wondered how to calculate the greatest common right divisor of two given matrices. A few days later I happened to be attending a conference where I met the mathematician H. B. Mann, and I felt that he would know how to solve this problem. I asked him and he did indeed know the correct answer; but it was a mathematician's answer, not a computer scientist's answer! He said, "Let R be the ring of of n \times n integer matrices; in this ring, the sum of two principal left ideals is principal, so let D be such that

  RA + RB = RD.

Then D is the greatest common right divisor of A and B." This formula is certainly the simplest possible one; we need only eight symbols to write it down. And it relies on rigorously-proved theorems of mathematical algebra. But from the standpoint of a computer scientist, it is worthless, since it involves constructing the infinite sets RA and RB, taking their sum, then searrching through infinitely many matrices D until finding one for which this sum matches the infinite set RD.

Knuth 後來倒有找到解決這個問題的 "computer scientist's answer"。Bernstein polynomial 在圖學的 Bézier curve 上好像也有一些應用,according to Wikipedia。(然後才突然想到,Bernstein polynomial 的形式的確和 Bézier curve 有點像,都有二項式的痕跡 XD。)

其實我之前很多關於 CS 的想法都可以在 Knuth 這本書裡看到類似敘述 XD。


<< 回到主頁