04 · 多項式：係數序列與 Sturm 序列

多項式：係數序列與 Sturm 序列¶

從有限係數序列建構多項式，再以精確有理數運算研究區間內的實根數。

閱讀本章前

你已能把有理數運算追溯到整數與自然數的定義。

完成本章後，你可以

數學定義

多項式由 `(a₀,a₁,…)` 表示，其中 `aᵢ` 是 `xⁱ` 的係數。Sturm 定理以符號變化數之差給出區間內相異實根的數目。

資料表示

`Polynomial` 保存從常數項開始的係數 tuple，並移除尾端的零；零多項式因此有唯一表示。

Python 實作

`(a₀,a₁,…)` → `Polynomial`; `#roots` → `sturm_sequence`

與本章一起閱讀的實作與測試

peano/polynomial.py · tests/test_polynomial.py

數學定義

數學定義¶

多項式由 (a₀,a₁,…) 表示，其中 aᵢ 是 xⁱ 的係數。Sturm 定理以符號變化數之差給出區間內相異實根的數目。

資料表示

Polynomial 保存從常數項開始的係數 tuple，並移除尾端的零；零多項式因此有唯一表示。

Python 實作

evaluate 依係數求值；sturm_sequence 反覆取得帶負號的餘式；count_real_roots 比較區間端點的符號變化。

本課程使用的精確對應關係:

`(a₀,a₁,…)` → `Polynomial`; `#roots` → `sturm_sequence`

執行過程

對 x²-2 在 1 與 2 求值，會得到一負一正，為下一章的隔離區間提供依據。

執行前預測

執行前判斷兩端點的符號，並說明這是否足以證明區間內恰有一根。

⌘ / Ctrl + Enter

輸出

請先寫下預測，再執行。

用測試核對

測試檢查係數規範化、求值、除法及已知多項式的根數。恰有一根要由 Sturm 計數確認，而非只看符號。

適用範圍

這裡只處理有理係數的一元多項式；重根與端點根需要實作中的明確約定。