§19-1 量級與成長速度

兩條都趨於無窮的數列，怎麼講清楚誰跑得比較快？只說某條數列趨於零，為什麼幾乎沒有資訊量？而「速度相同」「量級較低」「被支配」這三種說法，彼此是什麼關係？

比較兩條數列的成長速度

兩個人從同一個路口出發散步。第一個人每分鐘固定走 100 公尺，第二個人第 n 分鐘走 n 公尺。前十分鐘明明是第一個人遙遙領先，可是誰都知道後來會被超過，而且會被拉開到看不見。

「後來會被超過」這句話裡有兩件事需要講精確：後來是什麼時候，拉開多少又要怎麼量。第一件事分析裡一向的答案是「不去指定，只問最終」；第二件事的答案是看比值——兩條數列相除，商數列的行為就把兩者的相對大小說完了。

比值趨於 1，兩條數列最終一樣快；比值趨於 0，分子那條最終慢得多；比值只是有界，分子那條至少不會跑贏分母太多。三句話就是本篇要立的三個記號。

這張圖在說本篇要量的是什麼：前幾項誰大誰小完全不算數——藍線一開始在上面，交叉之後就再也追不上。本篇的三個記號都只看商數列 (xₙ/yₙ) 的最終行為，因此對前面任意多項的排序一概免疫。

19.1 DEFINITION

Let X = (xₙ) and Y = (yₙ) be sequences in ℝ with yₙ ≠ 0 for all sufficiently large n ∈ ℕ.
X and Y are equivalent, written X ~ Y, in case lim (xₙ/yₙ) = 1.
X is of lower order of magnitude than Y, written X = o(Y), in case lim (xₙ/yₙ) = 0.
X is dominated by Y, written X = O(Y), in case the sequence (xₙ/yₙ) is bounded.

比值趨於 1 叫等價；比值趨於 0 叫量級較低；比值有界叫被支配。前兩者互斥——比值不可能同時趨於 1 與趨於 0——而它們各自都蘊涵第三者。三個記號量的都是「最終的相對大小」。

正例：X = (1/n) 與 Y = (1/n²)。商數列是 (n)，無界，所以 X 不被 Y 支配；反過來 Y = (1/n²) 對 X 的商是 (1/n) → 0，所以 Y = o(X)。反例：這三個記號不看絕對大小——(1/n) 與 (1000/n) 兩條數列都趨於零，商數列是常數 1/1000，有界卻不趨於 1，於是它們互相支配但不等價。

三件事值得先講明白。第一，記號 X = o(Y) 裡的等號是沿用下來的寫法，不是相等——右邊的 o(Y) 並不指某一條特定的數列，整串符號要當成一個關係來讀。第二，定義只要求 yₙ 對夠大的 n 非零，前面幾項是零沒關係，因為 §15-1 的 15.3 說極限只認尾巴。第三，o 與 O 這兩個記號在後面幾章會反覆出現，值得現在就把它們的差別記牢：o 要求商趨於零，O 只要求商不爆掉。

例 1主導項

多項式的哪一部分決定它最終的大小？

取 xₙ = 2n + 17 與 yₙ = 2n。商是 1 + 17/(2n)，由 §14-4 例 5（1/n → 0）與 15.6 的加法得極限 1。所以 (2n + 17) ~ (2n)：常數項 17 對最終的大小毫無貢獻。
再取 zₙ = n³ − 5n。商 (2n + 17)/(n³ − 5n) 的分子分母同除以 n³，得 (2/n² + 17/n³)/(1 − 5/n²)，分子趨於 0、分母趨於 1，由 15.6(c) 的商得極限 0。所以 (2n + 17) = o(n³ − 5n)。
順帶注意：n = 1 時 zₙ = −4 而 xₙ = 19，n = 2 時 zₙ = −2 而 xₙ = 21——前幾項是 X 大得多。到 n = 4 才反超（44 對 25），而記號完全不管這件事。

把不影響最終比值的部分丟掉，剩下的就是主導項。判斷主導項的機械做法：分子分母同除以最高次的那一項。

例 2問出正確的衰減速率

√(n+1) − √n 趨於零——可是趨得多快？

先把式子有理化。分子分母同乘 √(n+1) + √n：
√(n+1) − √n = 1 / (√(n+1) + √n)。
（這裡的 √n 指平方等於 n 的那個正數，存在性由 §6-4 的 6.8 同一套論證給出，把 2 換成 n 即可。）
再與 1/(2√n) 相除：
(√(n+1) − √n) / (1/(2√n)) = 2√n / (√(n+1) + √n) = 2 / (√(1 + 1/n) + 1)。
令 aₙ = √(1 + 1/n)。則 aₙ ≥ 1 且 aₙ² − 1 = 1/n，於是 0 ≤ aₙ − 1 = (aₙ² − 1)/(aₙ + 1) ≤ 1/(2n)，由 §14-4 的 14.9 得 aₙ → 1。代回去，商趨於 2/2 = 1，所以 (√(n+1) − √n) ~ (1/(2√n))。

只說它趨於零，等於只說了 √(n+1) − √n = o(1)——資訊量幾乎是零，因為所有趨於零的數列都符合。equivalent 給的是速率，o 給的只是「比較慢」。

例 3被支配，卻不等價

O 比另外兩個記號寬鬆在哪裡？

取 xₙ = (−1)ⁿ n² 與 yₙ = n²。商數列是 ((−1)ⁿ)，被 1 界住，所以 ((−1)ⁿ n²) = O(n²)。
可是這條商數列不收斂（§14-2 例 4），所以兩者既不等價，也談不上量級較低。O 只要求有界，不要求極限存在——差別就在這裡。
另一方面 ((−1)ⁿ n²) = o(n³)：商是 ((−1)ⁿ/n)，絕對值被 1/n 壓住，趨於零。量級較低不需要商數列乖巧，只需要它趨於零。

三個記號的分工是：等價與量級較低各自把比值的極限指定成一個值（1 與 0），因此互斥；被支配最寬，只要求比值不爆掉，於是前兩者都落在它裡面。

LEMMA

Let X, Y, Z be sequences in ℝ whose terms are non-zero for all sufficiently large indices.
(a) The relation ~ is reflexive, symmetric and transitive.
(b) Either X ~ Y or X = o(Y) implies X = O(Y).
(c) The relations X = o(Y) and Y = o(X) cannot both hold.

(a) 等價確實是一個等價關係；(b) 前兩個記號都蘊涵第三個；(c) 兩條數列不可能互相比對方慢——「量級較低」這個關係是非對稱的（asymmetric：一個方向成立就排除另一個方向）。注意這比「反對稱」（antisymmetric）強：反對稱只說兩個方向同時成立時兩者必相等，並不禁止兩個方向同時成立。

正例：(n² + 2) ~ (n² − 3) 而 (n² − 3) ~ (n²)，由 (a) 的遞移得 (n² + 2) ~ (n²)——不必再算一次商。反例：(c) 不能加強成「兩者必有其一成立」——取 X = ((−1)ⁿ n²) 與 Y = (n²)，兩個方向的商都是 ((−1)ⁿ) 或它的倒數，都不趨於零，於是兩個 o 關係都不成立。

PROOF

三條都在商數列上算。以下把 X 對 Y 的商數列記為 (xₙ/yₙ)，並且只在下標夠大的範圍內討論——那裡分母都非零，而 15.3 保證只看尾巴不影響任何結論。

Proof. (a) Reflexivity is clear since xₙ/xₙ = 1. If X ~ Y, then lim (xₙ/yₙ) = 1 ≠ 0, so 15.6(c) applies to the reciprocals and gives lim (yₙ/xₙ) = 1; hence Y ~ X. If also Y ~ Z, then xₙ/zₙ = (xₙ/yₙ)(yₙ/zₙ) and 15.6(a) gives lim (xₙ/zₙ) = 1 · 1 = 1.

三條性質各用一次 15.6。對稱性有一個容易漏掉的前提：要談 yₙ/xₙ，得先確定 xₙ 對夠大的 n 非零——這件事由 X ~ Y 本身供給，因為商趨於 1，最終會超過 1/2，於是 xₙ 不可能是零。15.6(c) 的取商要求分母的極限非零，這裡分母的極限是 1，過關。遞移那一步用的是 15.6(a) 的乘積，把兩個商相乘剛好把中間的 yₙ 消掉。

(b) In either case the sequence (xₙ/yₙ) converges, and by 14.6 every convergent sequence is bounded. Hence X = O(Y).

這一步只有一句話：§14-3 的 14.6（收斂必定有界）。X ~ Y 與 X = o(Y) 都在說商數列收斂（只是極限一個是 1、一個是 0），而 O 要的只是有界，比收斂弱。

(c) Suppose both lim (xₙ/yₙ) = 0 and lim (yₙ/xₙ) = 0. For all sufficiently large n the product (xₙ/yₙ)(yₙ/xₙ) equals 1, so the product sequence is eventually constant with limit 1. But 15.6(a) gives the limit of the product as 0 · 0 = 0, and by 14.5 a sequence has at most one limit. Since 1 ≠ 0, the two relations cannot both hold.

這一步的所求：從「互相比對方慢」推出矛盾。把兩個商相乘，得到的數列從某項起恆等於 1，它的極限當然是 1；可是按照 15.6(a)，兩條收斂數列相乘的極限是極限相乘，也就是 0。同一條數列不能有兩個極限（14.5），於是 1 = 0，矛盾。要讓 yₙ/xₙ 寫得出來，得先知道 xₙ 最終非零——這正是敘述裡「各項最終非零」那個前提的用途。

三個記號的相互關係至此釐清：等價是等價關係，前兩者都蘊涵第三者，而量級較低這個關係不可能雙向成立。∎

這張圖在說 (b) 與 (c) 合起來的形狀：兩個小框都被大框裝著，而它們互不相交（比值不可能同時趨於 1 與 0）。要注意小框填不滿大框——例 3 的 ((−1)ⁿ n²) 落在大框內、兩個小框外，因為它的商數列有界卻不收斂。

—— 第一階段到此結束 ——

本篇立了三個量級記號（19.1）：比值趨於 1 是 equivalent、趨於 0 是 o、只要求有界是 O。三個例子分別示範了怎麼找主導項、怎麼問出正確的衰減速率，以及 O 為什麼比另外兩個寬鬆。引理把它們的相互關係收攏成三句話。下一篇 §19-2 換一個題目：數列不收斂時，能不能仍然指定一個合理的值當它的極限。起來動一動再繼續。