※ [本文轉錄自 Keelungman 信箱]
作者: [email protected] ("[email protected]")
標題: 關於李天岩(二)
時間: Mon Oct 18 05:03:07 2004
作者: DarthRaider (...........) 看板: BBMak
標題: 關於李天岩(二)
時間: Sun Oct 17 00:40:11 2004
（三）現代同倫算法
學過代數拓樸或非線性泛函分析的人都知道有名的布勞爾不動點定理：n 維閉球 Dｎ到此
自身的光滑映射 g：Dｎ → Dｎ 必有不動點。此定理的一個漂亮證明是用反證法。若 g
無不動點，則對閉球 Dｎ上任一點 x，令 f(x) 為由 g(x) 到 x 的線段延長到與球面之
交點。易知當 x 在球面上時，f(x) = x。這樣我們得到一個由閉球到其邊界 Sｎ 上且在
Sｎ 上為恆同映射的光滑映射。而拓樸學告訴我們，這是不可能的。
1973年，當李天岩在旁聽美國馬里蘭大學數學系凱洛格教授的研究生課程“非線性方程組
數值解”時聽到布勞爾不動點定理的屬於美國拓樸學家赫希 (Morris W. Hirsh) 的發表
於1963年的如上證明時，一個奇妙的想法在他腦海中湧現：既然在赫希的證明中若假設 g
無不動點時，則對如上定義的 f ，f ({y}) 這條光滑曲線無處可跑，則 f ({y}) 必然
跑到 g 的不動點集合中去。更精確地說，若令 F 為光滑映射 g : D ----> D 的所有不
動點組成的非空集合，則利用如上反證法的思想，我們可定義n 維流形 D \ F 到 n - 1
維球面 S 中的一個光滑映射 f : D \ F -----> S 。由微分拓樸的沙德 (A. Sard) 定理
可知，對幾乎所有的球面上的點 y ， y 是 f 的正則值，因而 y 在 f 下的逆象 f ({y}
) 為起始於 y 的一維流形，即一條光滑曲線。這條曲線的另一端不能再回到球面上，也
不能在 D \ F 中停止，故必定趨向於 g 的不動點集。如果能數值逼近這條曲線，就能計
算出 g 的一個不動點。在凱洛格和約克兩位教授的鼓勵下，李天岩開始了這一卓越思想
的數值實現。
在接下來的三個月時間內，他幾乎每天都與學校計算中心那台只能卡片輸入的電腦打交道
，但總是無功而返，電腦吐出的厚厚一迭紙預示著程序的失敗。但李天岩契而不舍，堅持
不懈地修改程序。改錯、輸入、再改錯、再輸入，從一個實際計算的門外漢逐步登堂入室
。直到有一天，他驚喜地發現電腦僅僅輸出一張打印紙，上面正是成功計算出的布勞爾不
動點！他成功了！一個全新的布勞爾不動點算法誕生了。這同時也給出了現代同倫算法的
肇始。
古典的同倫算法早在上世紀五十年代就有研究，尤其是前蘇聯數學家戴維登科 (D. Davi-
denko) 引入相應的常微分方程初始值問題來數值求解同倫方程。如果我們要計算一個非
線性映射 f : Rn → Rn 的零點，我們可將一個零點 x０ 已知的平凡映射 f０：Rn →
Rn（譬如說 f (x) = x - x ) 與 f 同倫，即定義同倫映射 H(x, t) = (1 - t) f (x)
+ t f(x)，其中參數 0 < t < 1。傳統的同倫算法的思想是假設 H 的零點集 H (0) 可表
示成曲線 (x(t), t) R x [0, 1]， 0 < t < 1，此曲線連接 x０ 與 f 的一個零點 x 。
若對恆等式 H(x(t), t) ≡ 0 求關於 t 的導數，我們就得到可以數值求解的戴維登科常
微分方程初值問題：x' (t) = - H (x, t) H (x, t), x(0) = x 。由 t = 0 起數值積分
到 t = 1 時，就可得到 f 的一個零點 x。然而，這一方法的致命弱點在於，在一般情況
下同倫曲線不一定總能定義 x 為 t 的單值函數。凱洛格－李－約克同倫方法的革命性思
想是：只要能保證 0 是映射 H(x, t) 的正則值，則由於沙德定理及隱函數定理，光滑同
倫曲線必定存在。坐標變量 x 與參變量 t 應具有同等的地位，它們均可視為曲線長度 s
的函數。這樣，無論曲線關於ｔ是否“轉彎”，運用“預測－校正”(predictor -
corrector)的數值手段，我們均能追蹤此同倫曲線而得到解。這是現代理論數學，尤其是
微分拓樸，在計算數學領域中的重要應用。
有趣的是，凱洛格－李－約克關於布勞爾不動點的計算，並非是歷史上的首次嘗試。盡管
他們當時不知道，早在1967年，美國耶魯大學 (Yale University) 經濟學教授斯卡夫
(H. Scarf) 在研究數量經濟學時將求解一個經濟模型的均衡點問題歸結為求解定義在 n
維標準單純形上的一個連續映射 f 的不動點問題。根據布勞爾不動點定理，這樣的不動
點存在。斯卡夫採用了所謂的單純三角剖分方法，運用組合數學中的斯泊訥 (E. Sperner)
引理，跟隨一條折線來近似 f 的不動點，從而設計了一種單純剖分不動點算法。在七十
年代，此算法被推廣成求解非線性方程組的單純不動點算法，成了熱極一時的研究領域。
1974年，當在美國克萊姆森大學 (Clemson University) 舉行的第一屆國際不動點算法大
會組委會獲悉凱洛格-李-約克的新方法時，立即提供了兩張飛機票讓他們赴會報告這一激
動人心的結果。正如斯卡夫在其會議論文集《不動點算法及其應用》序文中所述：“對
我們眾多與會者而言，克萊姆森會議之令人驚奇之處在於凱洛格 - 李 - 約克關於計算連
續映射不動點的文章。他們提出了第一個基於微分拓樸思想 --- 而不是我們習以為常的
組合技巧 --- 的計算方法”。雖然單純不動點算法的研究目前已趨沉寂，以凱洛格 - 李
- 約克方法為初始點的現代同倫延拓法研究依然方興未艾，在不同的領域生根發芽。如
今，李天岩與凱洛格 和約克一道是目前世界上被公認為非線性問題同倫法數值計算的創
始人，並且對此重要的領域作出了巨大的貢獻。
（四）多項式系統數值解
自七十年代提出計算布勞爾不動點的同倫方法後至今，李天岩一直在求解多項式系統同倫
算法這一領域辛勤地開拓著。解多項式方程組的根是相當有趣而且經常出現在應用科學上
的問題。譬如說電路分配問題，機械手問題等等。同時這種問題也出現在混沌理論的研究
中，如洛倫茨研究的具有混沌現象的四維常微分方程組的定常狀態事實上是其右端多項式
方程組的解。
對具有 n 個變數的 n 個多項式方程組，設其第 i 個多項式的階為d , 則代數幾何中古
典的比左(Bezout)定理給出此方程組所有孤立解總數的一個上界d d ... d , 稱之為對應
於該方程組的比左數。 但在絕大多數情況下， 此上界遠大於實際孤立解的個數。 其典
型例子為代數特徵值問題。 對應於 n x n 矩陣 A 的特徵值問題的二次多項式系統之比
左數為 2 ， 但 A 最多僅有 n 個特徵值。
最近這些年來，用同倫算法來解多項式方程組“所有”孤立解的研究引起了很大的注意。
1979年，迦協-贊格維爾(C. B. Garcia -- W. I. Zangwill) 對解 n 元 n 個多項式方程
組P(x) = (p (x), p (x), ..., p (x)) = 0 首先建立同倫 H : C x [0, 1] ----> C ，
H(x, t) = (1 - t) Q(x) + t P(x)。 這裡 Q = (q , q , ..., q )的分量 q : C --->
C 是 q (x , x , ..., x ) = x - 1, 其中 d 是 p 的階數。他們證明了: 若 H 是正
則的， 則 P(x) = 0 的每一個孤立解都是同倫方程 H(x, t) = 0 的一個相應的解曲線
x(t) 當t = 1時的終點。重要的是，曲線 x(t) 絕不轉彎回頭。這樣求解常微分方程初始
問題 x'(t) = - H (x(t), t) H (x(t), t), x(o) = x ，其中 x 是 Q(x) = 0 的解，我
們就可以在數值上逼近 x(t), 因此可找出 P(x) = 0 的所有孤立解的逼近值。由比左定
理知，P(x) = 0 最多有 d = d d ... d 個孤立解，而 Q(x) = 0 卻有 d' = (d +1)
(d + 1) ... (d + 1) 個解。因此，為了保證找到P(x) = 0 的所有孤立解，我們必須去
逼近d' 條曲線x(t)。這樣在 t ----> 1 時，許多曲線都跑到無窮遠去了。跟隨這些曲線
是個很大的浪費。
同倫算法計算多項式方程組所有孤立解的一大優點是它可並行化，因可在並行機器上同時
求解對應於不同初始條件的同一常微分方程。為了克服上述 迦協 - 贊格維爾同倫法的缺
陷，周修義(S. N. Chow)、莫萊特-派瑞特(J. Mallet-Paret) 以及約克介紹了一個同倫
H(x, t) = (1 - t) Q(x) + t P(x) + t (1 - t) R(x), 其中 q = x - b 及 r = a x ,
j = 1,..., n。他們證明，除了測度為零的集合外，對幾乎所有的 (a, b) C x C , 追
隨同倫方程 H(x, t) = 0 的所有 d 條解曲線，就可將 P(x) = 0 的所有孤立解找出來。
八十年代初，李天岩大大改進了同倫映射的構造。他證明，對於初始多項式方程組 q (x)
= a x - b = 0, j = 1, 2, ... , n, 對幾乎所有的 (a，b) C x C , 追隨同倫映射
H( x, t ) = (1 - t) Q(x) + t P(x) = 0 的 d 條解曲線一樣可以找到 P(x) = 0 的
所有孤立解。
從八十年代開始，李天岩繼續探索求解孤立解總數大大小於其比左數的多項式方程組。
這樣的方程組被稱之為虧損 (Deficient) 方程組。若用同倫法求解這種多項式方程組，
從 t = 0 開始我們必須追隨 d 條曲線，在 t ---> 1 時，大多數的曲線都跑到無窮遠去
了，只能少數的曲線收斂，因此造成極大的浪費。
對於數值代數中最重要也是最常見的虧損多項式系統------ 矩陣特徵值問題，李天岩與
他的合作者們及學生們提出了用同倫思想求解大型 矩陣所有特徵值：將一個特徵值為已
知或易於求得的同階矩陣 D 與所求矩陣 A 同倫，即定義同倫 H(t) = (1 - t) D + t A
，然後從 t = 0 出發數值追隨 H(t) 的特徵值和特徵向量曲線，而當 t =1 時得到A 的
特徵值與特徵向量。他和其韓國博士生李弘九 (Noah Rhee) 第一個將這一思想在電腦上
實現。此後他指導他的中國學生張紅、李奎元、曾鐘鋼、黃良椒、叢欒、金鳴等進一步完
善這一算法思想與數值實現。他們成功地發展了用於實對稱矩陣、一般實矩陣、以及大型
稀疏矩陣特徵值計算的同倫算法。即使未考慮其可並行化的優勢，僅用單個處理器，對許
多大規模代數特徵值問題，同倫算法優於基於 QR 分解的標準程序。
對於一般的虧損多項式方程組，構造一個好的同倫算法依賴於初始多項式系統的有效選取
。這是因為不光多項式方程組 P(x) = 0 的每一個孤立解均來自於初始多項式方程組
Q(x) = 0 的某個解出發的同倫曲線，更重要的是我們希望盡可能少的同倫曲線當 t --->
1 時趨於無窮。最理想的構造是 Q(x) 與 P(x) 有同樣數目的在無窮遠處的零點。近二十
年來，李天岩與索耶爾 (T. Sauer)、約克以及他的學生王筱沈、李星、高堂安等人運用
代數幾何的理論和方法，先後發明出選取 Q(x) 的一些行之有效的方法，如隨機乘積同倫
法和 Cheater 同倫法。近十年來，由於伯恩希坦 (D. N. Bernshtein) 定理的應用，基
於解個數組合計數的多面體同倫法倍受青睞。在其中，所謂的“混合體積”(mixed volume
) 之計算至關重要。李天岩與他過去及現在的學生們已取得一系列令人矚目的新成果，其
詳情可見他近期應邀所撰寫的長篇綜述性論文 [ ]。 在多項式方程組數值解領域，李天
岩無愧於其領軍人之一之稱號。
--
※ 發信站: 批踢踢兔(ptt2.cc)
◆ From: 218.167.228.139
--
愛因斯坦的廣義相對論 不過是另一個精緻的手編藤籃罷了.
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 140.112.102.37