憑一篇博士論文留名數學史 | 紀念楊大衞百年誕辰_風聞
返朴-返朴官方账号-关注返朴(ID:fanpu2019),阅读更多!3小时前
今年是美國計算數學家David M. Young Jr.(楊大衞)誕辰一百週年。他在博士學位論文中提出的“逐次超鬆弛迭代法”,在計算機求解大型線性方程組方面發揮着重要作用,成為留名數學史的傑出工作。
撰文 | 丁玖(美國南密西西比大學數學系教授)
光看標題,讀者可能以為楊大衞是一位華人學者。其實他是純粹的美國人,全名為David M. Young Jr. (1923年10月20日-2008年12月21日)。他不像德國“大衞”——David Hilbert (1862-1943) 那樣蜚聲國際數學界,我甚至查不到他全名的標準中文翻譯;再加上他的姓在西方人中罕見地只有一個元音,我就順勢給他起了個響亮的中文名字:“楊大衞”。
楊大衞生前在計算數學界是個響噹噹的人物。他畢生致力於求解線性方程組的迭代法,最偉大的成就是發明了SOR方法,即逐次超鬆弛迭代法(successive over-relaxation method)。更了不起的是,這項與時俱進的發明脱胎於他在1950年完成的博士論文。按照抽象代數名家和教學名師丁石孫 (1927-2019) 校長所言,數學博士論文“有百分之九十大幾的比例對所在學科沒有影響”。但是,楊大衞的博士論文影響了整個線性迭代法。1984年,我在南京大學讀到了丁校長的採訪記錄,感受到他希望研究生們多讀書以拓寬知識面,而不囿於一篇學位論文的苦心。
楊大衞於1944年在紐約州的韋伯海軍建築學院獲得學士學位,為海軍工作到二戰結束,其後進入哈佛大學數學系讀研究生,分別於1947年和1950年獲得碩士和博士學位。他的博士論文導師是加勒特·伯克霍夫 (Garrett Birkhoff,1911-1996)。加勒特和父親喬治 (George David Birkhoff,1884-1944) 是少見的數學家父子,而且都是哈佛教授,父親在動力系統和遍歷理論領域有開創性貢獻,兒子的成就主要集中在格論 (lattice theory)。
格論是抽象代數的一個分支,起始於布爾代數,研究的對象是有序集,小伯克霍夫在老伯克霍夫任教的哈佛大學數學系本科畢業後,去了劍橋大學,先學數學物理,後轉向抽象代數。在遊學歐洲的那年,他從幾大數學名家那裏獲益良多。1933年後,他一直待在哈佛。期間發表的一系列論文,構成了他1940年出版的經典著作《格論》,其第三版至今還在印刷。二戰中,他的興趣轉向應用數學,尤其是流體力學,研究成果包含在他於1950年出版的專著《流體動力學》中。由於和馮·諾伊曼是好朋友,他在三十五歲後對計算的愛好與日俱增。
這就是1948年楊大衞投入伯克霍夫教授門下攻讀博士時的背景。導師給了弟子一個題目:研究數值求解泊松偏微分方程。正是對這一博士學位論題的研究推動了SOR方法的問世。之後若干年,在楊大衞研究工作的基礎上,伯克霍夫與1950年進入哈佛數學系讀研究生的瓦爾加 (Richard Steven Varga,1928-2022) 合作,研究了用於微分方程和正算子的迭代法。瓦爾加於1962年出版的《流體動力學》成了這一領域的經典著作。
楊大衞在他1990年撰寫的綜述性文章《迭代方法的歷史回顧》( A historical review of iterative methods)中回憶,當他找伯克霍夫教授選博士論文題目時,心中的頭選是純數學領域的李代數,但是教授建議他做計算數學的“鬆弛方法”,並遞給他幾篇文獻,其中包括論文《拉普拉斯和泊松方程的數值解》( Numerical solution of Laplace’s and Poisson’s equations)和英國數學家索斯韋爾爵士 (Sir Richard V. Southwell,1888-1970) 的著作《理論物理中的鬆弛方法》( Relaxation Methods in Theoretical Physics)。
所謂“鬆弛方法”,從廣義上講是指獲得偏微分方程近似數值解的過程,但從狹義上講,它僅指用於求解線性代數方程組Ax = b的迭代過程。在此過程中,“鬆弛”技術與方程組的殘量r = b - Ax密切相關,目的是加快收斂。
伯克霍夫對楊大衞的博士論文研究幫助很大,他不僅提供了指導和鼓勵、給出建議的參考文獻,還仔細閲讀了論文草稿。據楊大衞回憶, “逐次超鬆弛方法”的英文全稱就是伯克霍夫建議的——“我相信這是一個很好的選擇”。這樣的導師堪稱良師益友。
楊大衞的博士論文研究開局並不順利,甚至來訪的索斯韋爾爵士也留下一句令人沮喪的評述“任何機械化鬆弛方法的嘗試都是浪費時間( Any attempt to mechanize relaxation methods would be a waste of time)。”但他毫不氣餒,繼續工作。不久他有了一個好發現:對某些線性方程組,高斯-賽德爾迭代矩陣的特徵值是雅可比迭代矩陣特徵值的平方。得益於從閲讀相關文章獲得的靈感,楊大衞有了突破性的進展:對於他通過引進超鬆弛因子ω而設計出的SOR方法,如果方程組係數矩陣A一致有序 (consistently ordered),則其迭代矩陣的特徵值與雅可比方法迭代矩陣的特徵值有個關鍵性的關係。他所數值求解的橢圓型偏微分方程在區域網格按從左到右和向上的自然順序編號,使用標準五點差分格式,會產生一致有序的矩陣。
我在之前一篇《返樸》文章《簡單實用!3個德國人創造的線性迭代法,超越了一個時代》中介紹了雅可比迭代法和高斯-賽德爾迭代法,在此基礎上,可以進一步瞭解楊大衞的SOR方法。設Ax = b為待解的線性方程組,其中n階係數矩陣A為非奇異的,b為給定的n維列向量,x為n維未知列向量。將A寫成其嚴格下三角部分L、對角線部分D和嚴格上三角部分之和:A = L + D + U,則原方程可寫為Lx = b – (D + U)x。
令ω為一個小於2的正數,稱為鬆弛因子。上述方程等價於ωLx = ω[b – (D + U)x],兩邊加上Dx,得(D + ωL)x = Dx + ω[b – (D + U)x]。化簡右端,便有
(D + ωL)x = ωb – [ωU +(ω - 1)D]x, (1)
這就是SOR方法的方程組形式。如果讓ω = 1,(1)就變成(D + L)x = b – Ux,即高斯-賽德爾方程組。
為何在經典高斯-賽德爾方法的矩陣形式中塞進可調參數ω?這是為了改善收斂速率。SOR方法的迭代格式如下:
上世紀四十年代末,楊大衞研究迭代方法伊始,對於在新生的電子計算機上使用迭代法求解大型問題的想法,有人表示懷疑。但自從他開創性的博士論文問世後,迭代法已被廣泛應用於科學和工程中,並衍生出許多新的變種。
在科學計算的廣闊領域,楊大衞的功績永遠不會被人遺忘,今年12月21日是他十五週年忌辰,謹以此短文感謝他,並簡單介紹他留名數學史的博士論文成果——SOR方法。
寫於2023年11月23日星期四,感恩節
美國哈蒂斯堡夏日山莊
本文受科普中國·星空計劃項目扶持
出品:中國科協科普部
監製:中國科學技術出版社有限公司、北京中科星河文化傳媒有限公司
特 別 提 示
1. 進入『返樸』微信公眾號底部菜單“精品專欄“,可查閲不同主題系列科普文章。
2. 『返樸』提供按月檢索文章功能。關注公眾號,回覆四位數組成的年份+月份,如“1903”,可獲取2019年3月的文章索引,以此類推。
版權説明:歡迎個人轉發,任何形式的媒體或機構未經授權,不得轉載和摘編。轉載授權請在「返樸」微信公眾號內聯繫後台。