2007/04/21

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。

Labels:

<< 回到主頁