《解多項式方程組的同倫分治法》是依託大連理工大學,由張金濤擔任醒目負責人的青年科學基金項目。
基本介紹
- 中文名：解多項式方程組的同倫分治法
- 依託單位：大連理工大學
- 項目類別：青年科學基金項目
- 項目負責人：張金濤
項目摘要,結題摘要,
項目摘要
多項式方程組是科學和工程中常見的數學模型，其理論和解法是代數幾何和計算數學中的重要而困難的課題。同倫方法是解多項式方程組的主要數值方法。理論上可以用同倫方法求任何多項式方程組的全部孤立解，但由於問題的固有複雜性，很多實際問題無法在容許時間內用現有的同倫方法解決。本項目將在前期工作基礎上，研究解多項式方程組的同倫分治法。該方法並不像已有的同倫方法那樣，將目標多項式組同倫形變為直接可解的初始多項式組，而是儘可能多地保持問題的稀疏和對稱結構，而初始多項式組可以分解為若干個子方程組，它們或者能通過消元來化簡為低維、具有低Bezout數或BKK界的問題，或者具有相同的單項式結構，因而可以用較小的代價求解。我們將研究適合一般問題的同倫分治法和針對重要套用問題的特殊同倫分治法的構造、理論分析和程式實現。
結題摘要
科學和工程中經常需要解多項式方程組，它可能直接來自於工程問題（如聲吶信號處理）或是某些模型轉化而來（如某些微分方程離散化）。解多項式方程組的理論和快速算法具有十分重要的意義。一、對於一般的虧欠多項式方程組，我們提出同倫分治法，該方法並不像已有的同倫方法那樣，將目標多項式組同倫形變為直接可解的初始多項式組，而是儘可能多地保持原問題的稀疏和對稱結構，其可以分解為若干個子方程組，它們或能通過消元來化簡為低維、具有低Bezout數或BKK界的問題，或具有相同的單項式結構，從而可以用較小的代價求解。二、在正電子湮滅壽命譜分析、放射性探測以及解常係數齊次微分或差分方程等問題中有重要套用的稀疏插值問題。我們對等距情形下的稀疏插值問題，通過變元替換轉化為解多項式方程組問題，並利用其對稱結構給出一個高效的同倫，其在置換意義下只需要跟蹤一條解路徑即可得到全部孤立解。對於非等距情形，採樣點由於觀測設備的不精確可能會出現部分採樣點失效或者缺失的情況，這樣就會出現跳點的情況。此時，經典的Prony方法無法使用，而我們將其轉化為多項式方程組求解依然有效且仍然保持置換意義下對稱性。但是對孤立解的個數上界的估計比較困難。我們給出了一種估計，只給出了部分證明。假定孤立解上界估計正確，多項式方程組的解就可以分為多個等價類，每個等價類求一個代表解即可，將大大節省了計算量。我們證明了解路徑的可達性和光滑性。三、對於多項式非線性橢圓方程和橢圓方程組多解問題，我們提出一種特徵函式展開法，將原微分方程問題轉化為解多項式方程組問題。該多項式方程組具有一種特殊的D4對稱結構，構造保持該特殊結構的同倫，節省了大量的計算量。從多項式非線性橢圓方程多解問題擴展到多項式非線性橢圓方程組多解問題，我們將此類問題，先在較粗糙狀態下，利用特徵函式展開將其離散為多項式組，保持其特有對稱性構造同倫並求解這個多項式系統，去除偽解，逐步加細並反覆使用上述過程。
