若干多項式系統(tǒng)計算問題的符號數值混合算法研究.pdf

1、科學計算中的諸多問題都可以轉化為多項式系統(tǒng)求解問題。符號計算和數值計算是兩種不同的計算方法。與傳統(tǒng)的數值方法相比,利用符號方法得到的解是完備精確解,不存在計算誤差等問題。但符號方法由于中間系數膨脹的原因導致了存儲空間的增加,降低了計算的速度,因而不能滿足實際應用的需求。數值方法采用插值、擬合、迭代法等求解問題的數值近似解,計算效率較高,被廣泛應用于解決工程實際問題。但受病態(tài)問題與近似計算的約束,數值方法存在迭代不收斂等問題。同時,計算結

2、果需要進行可信性與正確性驗證。本文針對上述問題,采用符號數值混合計算方法進行深入研究,討論了若干機器證明和科學計算中的典型問題,設計和實現(xiàn)了一些解決這些問題的高效的、可信的算法,并進一步探討了它們在一些工程問題中的應用。
　　主要工作包括以下幾個方面:
　　1.針對一類代數系統(tǒng)重零點的計算問題,提出了一個顯式表示對偶空間元素的公式。在此基礎上,利用對偶空間對原代數系統(tǒng)做微分運算構造新系統(tǒng),得到一個在初始點雅克比矩陣滿秩的代數

3、系統(tǒng),從而恢復了牛頓迭代算法的二階收斂性。同時,得到了重零點的重數。最后應用此算法解決了電力系統(tǒng)潮流計算的病態(tài)問題。
　　2.半代數系統(tǒng)實根隔離方面,提出了基于連續(xù)同倫算法和區(qū)間牛頓算法的高效、可信的方法。該方法首先通過連續(xù)同倫算法和區(qū)間牛頓算法得到代數系統(tǒng)的實根區(qū)間。然后利用區(qū)間擴展對半代數系統(tǒng)中的限制條件進行驗證。該方法克服了符號算法只能解決中小規(guī)模以及有理系統(tǒng)的缺點。此外,該算法具有明顯的可并行性。
　　3.研究了一個

4、含超越函數的半代數系統(tǒng)的實根計算問題。首先,通過超越函數在區(qū)間上的泰勒展開,將此系統(tǒng)轉化為多項式系統(tǒng)。然后采用連續(xù)同倫方法和區(qū)間算法得到此多項式系統(tǒng)在區(qū)間上的近似實數解。最后,將此實數解視為原系統(tǒng)的近似零點,利用牛頓迭代算法,得到系統(tǒng)的實數解。實驗結果表明,該方法的效率比二分法的效率更高。
　　4.針對具有不同維數的不可約分支的正維數系統(tǒng)的實根計算問題。利用隨機行滿秩矩陣構造新系統(tǒng),使得原系統(tǒng)中維數不等于變量個數與方程個數之差的不

5、可約分支滿足新系統(tǒng),且維數等于新系統(tǒng)的變量個數與方程個數之差。以此為基礎,構造特殊的同倫方程以保證在此不可約分支上找到至少一個實數解。該方法克服了已有方法不能得到所有不可約分支上實數點的問題,且算法可以并行計算所有不同維數的分支。同時,基于李雅普諾夫函數的性質,通過增加變量,將微分系統(tǒng)李雅普諾夫函數的計算問題轉化為正維數系統(tǒng)的實根計算問題。實驗結果表明,該方法效率更高。
　　5.基于三種經典結式矩陣之間的轉換關系,通過構造中間矩陣