高效率更新非線性偏微分方程導出之線性系統序列的預處理器

Effective Preconditioner Updates for Sequences of Linear Systems Derived from Nonlinear Partial Differential Equations

郭彥祥(Yen-Hsiang Kuo)

指導教授 ： 王藹農

國立臺灣大學/理學院/數學研究所/碩士(2015年)

https://doi.org/10.6342/NTU.2015.00698

摘要

隨著科技的進步，人們在許多領域（如物理學、地震學、氣體動力學、化學等）上處理著更精密且精確的問題，因此科學計算應該被高度重視。在科學計算中，有率效地解決一連串大型且稀疏的線性系統扮演了極為重要的角色。

在早期，人們使用直接法或迭代法單獨地解決一連串線性系統中的每一個問題，當線性系統的維度很大時，直接法將會非常悲慘。如果我們使用迭代法，強大的預處理器對於解決線性系統非常有幫助，但是要找尋或建造出全能的預處理器是非常困難且耗時的任務。現今，我們應用先前線性系統的資訊到目前線性系統或是其餘的線性系統達到節省時間的功效。

在文章中我們將會以一個二維度非線性對流-擴散模型問題來當作我們的例子。我們會簡單的介紹有限差分方法,牛頓-拉弗森方法和線搜索法，而且透過以上的這些概念，我們將會創造出一連串的線性系統。

之後，我們會討論三種有趣的逼近更新分解預處理器的方法，數值結果告訴我們這三種方法是有幫助的，也就是在使用預處理器的迭代法時，相較於固定一連串線性系統中的第一個預處理器，這三種方法會得到比較少的迭代次數。因為這三種有趣的更新預處理器的方法基本上來說是很省時的、容易實行的，所以他們可以取代很耗時的重新計算預處理器。

最後，為了完成我們的工作，我們主要的參考文獻為 Jurjen Duintjer Tebbens和Miroslav Tuma 共同研究的[7]與[8]，基本知識的準備我們參考 John E Dennis Jr和 Robert B Schnabel 的[1]、Hans Petter Langtangen 的[2]、Randall J LeVeque的[3]和Stephen J Wright與Jorge Nocedal合力完成的[10]等著作。我們重新設計與安排[7]，盡可能讓讀者容易了解[7]的內容與想法。

關鍵字

一連串線性系統 ； 預處理迭代法 ； 不完全分解 ； 分解更新 ； 高斯喬丹轉換 ； 謝爾曼·莫里森公式

並列摘要

With the advance of science and technology, people deal with problems more precisely and accurately in many fields like Physics, Seismology, Aerodynamics, Chemistry and so on and so forth. Therefore scientific computing should be highly concerned. Effective solving sequence of linear systems with large and sparse matrices plays a very important role in scientific computing.

With the advance of science and technology, people deal with problems more precisely and accurately in many fields like Physics, Seismology, Aerodynamics, Chemistry and so on and so forth. Therefore scientific computing should be highly concerned. Effective solving sequence of linear systems with large and sparse matrices plays a very important role in scientific computing.

In our article, we will take a two-dimensional nonlinear convection-diffusion model problem to be our example. We present a brief introduction of finite difference method, Newton-Raphson method and line search method. After applying these ideas, we will have a sequence of linear systems needed to be solve.

And then, we will discuss three interesting methods for approximate updates of factorized preconditioners for solving sequences of linear systems. Numerical experiments show that these three method are profitable, that is, they have fewer number of iterations of preconditioned iterative methods for solving sequent systems of a sequence than freezing the preconditioner from the first system of the sequence. Since the interesting updates mainly cost less and straightforward, they may substitute for recomputing preconditioners which may take lots of time.

To complete our work, we mainly consult [1], [2], [3], [7], [8] and [10]. And we also redesign and rearrange [7] in order to introduce everything as explicit as we can.

並列關鍵字

Sequence of linear systems ； Preconditioned Iterative method ； Incomplete factorizations ； Factorization updates ； Gauss-Jordan transformations ； Sherman–Morrison formula

參考文獻

[1] John E Dennis Jr and Robert B Schnabel. Numerical methods for unconstrained optimization and nonlinear equations, volume 16. Siam, 1996.

[2] Hans Petter Langtangen. Computational partial differential equations: numerical methods and diffpack programming. Springer Berlin, 1999.

[3] Randall J LeVeque. Finite difference methods for differential equations. Draft version for use in AMath, 585(6), 1998.

[4] Angelo Lucia. An explicit quasi-newton update for sparse optimization calculations. MATHEMATICS of computation, 40(161):317–322, 1983.

[5] LK Schubert. Modification of a quasi-newton method for nonlinear equations with a sparse jacobian. Mathematics of Computation, 24(109):27–30, 1970.