動機
有理逼近是否有用,須把誤差與分母大小一同考慮。連分數反覆取整數部分,再把餘下部分取倒數,構造誤差與分母有很強聯繫的分數。輸入是有理數時,這正是歐幾里得(Euclid)算法;輸入無理數時,算法無限進行,其有限截段則有可證明的收斂與誤差界。
相鄰兩個逼近的行列式是不變量:相應整數向量組成整數格的一組基。把任何競爭分數寫成這組基的整數組合,逼近問題便成為符號問題。我們也會證明一個反向判準:若既約分數的誤差特別小,它必定已出現在漸近分數之中。
本章輸入 是正實數。證明使用精確比較與恆等式,不把有限小數當作有理性或兩個尾項相等的證據。有理數的終止情形與無理數的無限情形會分開處理。
定義
定義 11.1.1
(連分數算法)
設 ,取 ;若 不是整數,令
稱為部分商, 稱為完全商。有 ,而 時 。有限的逐層倒數式 是第 個漸近分數,記為 。
對正有理輸入 ,分子除以分母的整數除法產生下一餘數;取倒數則交換餘數與原分母的角色。正餘數嚴格遞減,故過程終止。除了單項整數展開,最後一個部分商至少為二。反過來,有此末項約定時,逐步取整數部分能恢復所有項,證明標準有限展開唯一。若容許末項一,則 時有另一形式 。
無理輸入不會終止,因為減整數與取倒數保持無理性。定義有限漸近分數時,尚未賦予無限巢狀式意義;它們確實收斂到原輸入,須由下文證明。
定義 11.1.2
(遞推與放大誤差)
取輔助初值
並令 、。零分母初值只用於遞推,不是一個有理逼近。對無理數 記 。候選分數 的放大誤差是 ;當 時,普通絕對誤差是 。
定理
定理 11.1.3
(行列式、尾項與收斂)
遞推確實給出所述有限漸近分數,分母為正,分子分母互質,並滿足
若 無理,則
所以漸近分數交替位於 兩側,收斂到它,並有 。
定理 11.1.4
(最佳放大誤差與 Legendre 判準)
若 無理,整數 滿足 ,則
若既約分數 的 ,且
則 是漸近分數。這是充分判準,並不是說每個漸近分數都滿足這個更強誤差界。
概念視角幾何
最接近一條直線的格點
把每個候選分數 畫成格點 。放大誤差 就是該點到直線 的鉛直距離。因此最佳放大誤差定理是說:在第一座標滿足 的格點中,沒有一點比 在鉛直方向上更接近該直線。符號交替表示相繼的漸近分數點交替落在直線兩側;行列式恆等式則表示相鄰兩點生成面積為一的平行四邊形,其中不含其他格點。
證明思路
遞推與整數可逆矩陣
證明
(矩陣乘積、行列式與精確誤差)
逐步代入巢狀分數,或相乘矩陣 ,得到
由右乘讀出的正是兩個遞推,起始為 。每個因子的行列式是負一,故得到行列式公式。 的公因數必整除此行列式,所以只能是一。分母為正,;當 時,因前一分母為正,故 。
尾項式在 時是 。把尾項換成 ,整理分子分母便由遞推得到下一步。減去 ,再用行列式,便得精確誤差式;分母為正,所以符號交替。
由 ,誤差式內的分母大於 ,得到嚴格界。又因 ,分母無界,誤差趨零,從而證明收斂。單憑分數在兩側交替並不足以推出此結論。初時可能有 ,不妨礙其後嚴格增長。
任何競爭整數對都有整數座標
證明
(漸近分數基中異號的座標)
兩列 、 的行列式為正或負一,故逆矩陣仍為整數矩陣。任何 因而唯一寫成
相應誤差是 ,而兩個 符號相反。
若 ,由 得 ,所需界立即成立。若 ,則 會使 為 的正倍數,違反分母限制。 不可同正,否則 ;亦不可同負,否則 。所以兩者異號,它們與異號的 相乘後反而同號,故
這對所有允許候選都成立,即使候選尚未約分。分母範圍與放大誤差的定義,都是定理不可略去的部分。
小到整數格不能容許的誤差
證明
(小於一的非零整數)
證 Legendre 判準時,選最大的 使 。分母無界且最終嚴格增加,故此 存在,且 。設 ,最佳逼近給出 。
若 ,整數 非零,故 。但
矛盾。因此兩分數相等;既約及正分母使表示也與漸近分數一致。證明的關鍵是非零整數不可能絕對值小於一,並非從小數展開猜出部分商。常數二分之一有明確作用:兩個誤差項都用同一候選誤差估計,所乘分母也不超過候選分母。嚴格界使總和小於一;若只有等號,整數矛盾便消失,所以此證明沒有額外建立邊界情形。
大部分商究竟說明甚麼
完全商嚴格位於整數部分與下一整數之間,把兩界代入精確誤差式,可加強為
這不只給符號,也控制誤差的真實大小。因為 ,下一部分商很大,表示當前漸近分數相對於分母平方特別準確。受惠的是當前分數,不是下一個。例如 的有理展開中, 後面的十六說明 為何接近該有理輸入;但無限無理定理本身仍要求輸入無理。
對無理數還有精確的二分。若首項以後全有 ,,由 得 。上面的下界使每個漸近分數誤差嚴格大於 。不是漸近分數的既約分數,則由 Legendre 判準的逆否命題知誤差至少 ,比 更大。所以每個既約有理數都滿足統一界
反之,部分商若無界,對任何候選正常數 都可選下一部分商大於 。由上誤差界及 ,得到誤差小於 的漸近分數,故不存在這種統一正常數。兩方向合起來證明:部分商有界,恰好等價於存在分母平方型的統一下界。這類無理數稱為難逼近數;名稱指統一常數,並非完全沒有準確逼近。
對 ,已證尾項重複,後續部分商全為二,故 是可行常數。漸近分數仍會隨分母增長而任意接近它;下界本身也隨分母縮小,所以不違反收斂。本章不宣稱這個簡單常數已是最佳值。
證明透視
相鄰漸近分數為何控制所有競爭者
行列式使兩個向量成為整數基,而不只是兩個相近的實數。分母限制迫使競爭者的基底係數異號,於是兩項誤差相加而不能抵消。反向判準再把一個非零整數行列式壓到一以下。逼近估計背後是這些離散限制。
例題
例題 11.1.5
(有理輸入與末項約定)
整數除法給出 、、,所以 ,漸近分數為 。最後的行列式為 。 值相同,但不是標準形式。兩者都是有限式,不需要無限過程的收斂定理。
例題 11.1.6
(平方根二的精確重複尾項)
因為 ,第一完全商的整數部分為二,分數部分是 ,所以同一完全商重現,展開為 。首幾個漸近分數為 ;誤差依定理交替。前四個的精確值 為 ,引出下一章的二次方程。重複由代數恆等式證明,不是從有限小數圖樣推測。
例題 11.1.7
(用範數恆等式辨認漸近分數)
整數九十九與七十滿足 ,所以
它們互質,因公因數的平方須整除一。Legendre 判準證明 是漸近分數;遞推亦確認它接在 之後,因為 、。範數恆等式提供無須浮點近似的精確證書。
反例模式
放大誤差與普通誤差不同
對 ,漸近分數 的下一個是 ,但 的普通誤差比 小;比較等價於 。這不違反最佳放大誤差,因為 ,等價於 。兩個有理界都可把正數平方後驗證。修正方法是保留定理誤差中的分母因子 ,不能悄悄更換所最小化的量。
常見錯誤
常見錯誤
(初值或零餘數都不是漸近分數)
零分母的遞推初值不是漸近分數。有理算法在餘數零時停止,不能再對零取倒數。標準有限展開可有另一個不標準形式;無理輸入則始終不終止。
常見錯誤
(Legendre 界是充分而非必要條件)
最佳逼近定理有明確的分母範圍及誤差種類。Legendre 界是辨認漸近分數的充分條件,不是每個漸近分數都滿足的必要條件。
常見錯誤
(有限個重複的部分商不能證明週期性)
精確的二次尾項恆等式可證重複,有限個係數看似重複則不能證一般週期定理。例如有理數 與 的首五個部分商相同,但它的展開會終止。任何有限長的部分商序列,都為無窮多個輸入所共有。
小結
歐幾里得倒數程序產生的相鄰漸近分數,具有行列式正負一的關係。完全商給出精確帶號誤差並證明收斂;同一行列式提供整數基,證明最佳放大逼近及 Legendre 判準,為二次整數方程建立嚴格工具。
練習
快速檢查
(求 的標準連分數及所有漸近分數。)
對 與 進行歐幾里得算法。
解答 · 答案
除法為 、、、。故展開是 ,遞推給出 。
快速檢查
(證明嚴格位於相鄰漸近分數之間的既約有理數,其分母至少為兩分母之和。)
把 寫成兩個相鄰漸近分數所成整數基的組合。
解答 · 答案
在整數基中寫 。分別與兩鄰向量取行列式,由嚴格介於其間及 得 。兩者為整數,故至少一,於是 。中項分數達到等號;其分子分母互質,因公因數亦須整除相鄰行列式。
快速檢查
(用完全商恆等式證明 ,並求首四個漸近分數。)
把 有理化,並追蹤各完全商。
解答 · 答案
第一尾項為 ,整數部分一;下一個為 ,整數部分二;再下一個回到第一尾項。所以重複項為一、二,漸近分數是 。首兩個分母同為一是遞推允許的,不影響其後增長。
快速檢查
(Legendre 充分判準的逆命題成立嗎?用 的漸近分數 ,精確證明相關誤差比較。)
把正數平方,比較 與 。
解答 · 答案
不成立。上一題證明 是漸近分數,但由 知 ,故 。這個真正的漸近分數不滿足充分界。因此不能因誤差達到或超過該界,就排除一個分數是漸近分數。