廣義鞍點問題的結構化預處理方法

《廣義鞍點問題的結構化預處理方法》是依託上海交通大學，由王增琦擔任項目負責人的青年科學基金項目。

基本介紹

• 中文名：廣義鞍點問題的結構化預處理方法
• 項目類別：青年科學基金項目
• 項目負責人：王增琦
• 依託單位：上海交通大學

項目摘要

大規模廣義鞍點線性方程組的求解問題來源於科學與工程計算的很多領域。例如：流體力學中Stokes方程，Navier-Stokes方程，電磁場力學中Maxwell方程和非線性最佳化問題等等，經離散逼近後都轉化為該類問題的求解。由於廣義鞍點矩陣通常是壞條件的，且缺乏對稱正定性、對角占優性等特點，使得傳統的疊代算法的數值效果並不理想，預處理技術成為了算法成敗的關鍵。針對來源於上述幾個領域的廣義鞍點問題，本課題將結合Krylov子空間方法探索結構化的預處理技術。包括約束預處理技術及相應的約束預處理共軛梯度方法；乘積型能量預處理技術及相應的預處理極小殘量法；分裂型預處理技術及相應的預處理廣義極小殘量法等。另外，我們在設計這些結構化預處理方法時，將充分結合多重格線、Chebyshev加速技巧以及非精確求解技巧，旨在得到可行、高效的數值算法的同時，通過嚴密的理論分析，保證算法的穩定性和收斂性。

結題摘要

本項目依計畫完成以下工作:設計了約束型預處理子及約束預處理Chebyshev方法。約束預處理方法通過約束分解和線性變換，將原來對稱不定的問題轉化為對稱正定的問題，進而採用具有短遞推格式的疊代方法求解。理論分析表明，精確求解意義下的約束預處理Chebyshev格式是無條件收斂的。收斂速度僅依賴於預處理Schur補的條件數。在此基礎上，研究了更加實用的不精確約束預處理Chebyshev格式，Chebyshev外疊代框架對於完成不精確求解的內疊代沒有任何限制,只通過控制預處理步驟的殘量來控制收斂，操作簡單，降低了計算複雜度，節約了計算時間。我們對求解鞍點和廣義鞍點問題的不精確約束預處理Chebyshev方法的誤差界給出了清晰的描述。它的上界依賴於預處理Schur補矩陣的條件數，約束矩陣的條件數和不精確求解的殘量範數界。不精確約束預處理Chebyshev 方法彌補了不精確約束預處理共軛梯度方法收斂性無法保證的不足；針對帶偏微分方程約束的最佳化控制問題，構造了改進對稱/反對稱分裂預處理子和加性塊對角預處理子。針對該問題非對角塊矩陣的規模與對角塊矩陣的規模相同的特殊結構，該乘積型預處理子避免了求解和近似Schu補矩陣，突破了數值方法求解鞍點問題的瓶頸。這是求解該問題的其他算法所不具備的特點，也是設計求解鞍點問題的高效數值算法的困難所在。經改進對稱/反對稱預處理後矩陣的特徵值全部集中在以1為圓心，譜半徑小於1的圓盤內。預處理係數矩陣的特徵向量均為正交向量，在特徵向量意義下，條件數為1。這些結論為預處理的高效性提供了理論保證。在此基礎上，研究了具有對稱塊對角結構的預處理子。該預處理子適合於具有短遞推格式的疊代算法，節省了存儲空間和計算時間。