知道一個多項式在若干點上的值,就得到關於其係數的方程。這些值究竟決定了多少資訊?次數上界是關鍵:若沒有次數上界,一個非零多項式可以在所有選定的點上取值為零,把它加上去並不會改變任何數據。插值構造出唯一的低次代表,並把求值與多項式商環聯繫起來。
由函數值構造多項式
定義 9.1.1
(拉格朗日(Lagrange)基多項式)
設 為一個域, 為 中互不相同的元素(節點)。對每個 ,定義
由於各節點互不相同,每個分母都不為零;又因為 是域,所以分母可逆。在 處每個因子都等於 1,而在任何其他節點 處,有一個分子為零。因此 。
定理 9.1.2
(插值多項式的存在性與唯一性)
設 為域, 互不相同,並設 。則恰有一個次數至多為 的多項式 (包括零多項式)使 對每個 成立,即
證明
(以拉格朗日基證存在性,以因式定理證唯一性)
存在性:此和的次數至多為 ,且因為 ,。唯一性:若 是另一個這樣的多項式,則 在全部 個互不相同的節點上都取值為零。反覆應用因式定理,得 。一個能被該乘積整除的非零多項式,次數至少為 ;然而 的次數至多為 。因此 。這個論證也涵蓋了零多項式,而無需為它指定次數。
證明透視
唯一性論證用到甚麼
不平凡的一步,是由 個各別的根推出單一的整除關係 。寫 。在 處得 ,而 ,所以能推出 ,是因為域沒有零因子;對其餘每個節點重複同一消去,這用到各節點互不相同。然後以次數計算收結:次數為 的多項式的非零倍式,次數不可能低於 。若沒有次數上界,結論只是 ,其中 ,唯一性便不成立。
例題 9.1.3
( 上的插值)
在 上指定 、、。設 、、。首兩個基多項式為
其中在 中 。因此 。直接代入,模 5 得 。第三個基多項式在這個和中不需要,因為它的係數為零。唯一性並不依賴於 ;它由上面的因式定理論證得出。
例題 9.1.4
(常數數據(邊界情況))
取任何至少有三個元素的域 、三個互不相同的節點,以及數據 。定理保證有次數至多為 的多項式,但常數多項式 已有這些值,且次數為 。由唯一性,,因此 。界 只是上界,並非實際次數。
反例模式
插值需要域
斷言:在任何交換環上,於互不相同的節點處插值都是唯一的。在 中取節點 與 ,兩者不同。多項式 非零,次數為 ,但 ,。所以數據 既被 吻合,也被 吻合。證明正好在用到域的地方失效:分母 在 中不可逆,所以 並不存在;而 是零因子關係,透視中的消去步驟無法排除它。
快速檢查
(在 上,求次數至多為 且 、 的多項式。)
使用 。
解答 · 答案
,而第二項的係數為 ,所以在 中 。驗算:,。
快速檢查
(域上一個次數至多為 的多項式在四個互不相同的點取值為零。它是甚麼?)
把根的個數與次數比較。
解答 · 答案
它是零多項式:四個互不相同的根給出次數為 的因式 ,而次數至多為 的非零多項式不可能有這個因式。
所有其他解的形式
命題 9.1.5
(所有的插值多項式)
令 ,並設 為次數至多為 的插值多項式。多項式 對所有 滿足 ,當且僅當
證明
(每個解與 相差 的倍式)
每個多項式 在選定節點上的值都與 相同。反之,若 在這些節點上取相同的值,則每個 都是 的根,所以由同一個因式定理論證得 。
例題 9.1.6
(一個三次的解)
在 上,取第一個例子的數據,,。取 得 。於是模 5 有 、、,所以 雖然是三次,卻與 有相同的值,與命題一致。
用商環的語言來說,求值誘導出一個環同態
其中 中的運算按座標進行。由於 的倍式在每個節點上都取值為零,這個映射是良好定義的。由因式定理論證知它是單射,由插值知它是滿射,因此是同構。特別地,當 時,這個商環有零因子:例如 ,但兩個等價類都不為零。商環不必是域也可以很有用。
有限域與一個必要的區分
在 上,於全部 個域元素處插值,可以把每個函數 表示為唯一一個次數小於 的多項式。但形式多項式 與 是不同的,卻在 上定義同一個函數:對非零的 ,在乘法群中應用拉格朗日(Lagrange)定理得 ,而 。因此,在有限域上取值相等,本身並不等同於形式多項式相等。正是次數上界使代表成為唯一。
常見錯誤
(作為函數相等,不等於作為多項式相等)
在 上,多項式 與 在 處取相同的值(即 ),但在 中 。只有當兩個多項式的次數都低於域的元素個數(這裏即低於 )時,才可由它們在每個域元素處取值相同,推出兩者相等。
快速檢查
( 上次數至多為 的多項式共有多少個?定理如何解釋這個數目?)
先數係數的選法,再數三個節點處的值組。
解答 · 答案
共有 個(三個係數,每個有五種選擇)。在三個固定節點處插值,給出這些多項式與 組值 之間的雙射,兩者的個數相同。