多項(xiàng)式零點(diǎn)的并行圓盤迭代法研究

努爾麥麥江·阿布都吾甫

(喀什大學(xué) 數(shù)學(xué)與統(tǒng)計(jì)學(xué)院，新疆 喀什 844000)

求解多項(xiàng)式零點(diǎn)問題是解決很多實(shí)際問題的過程中經(jīng)常要遇到的數(shù)學(xué)問題之一，也引起了眾多人的廣泛關(guān)注[1]。多項(xiàng)式方程到了5次及其以上就沒有公式解，因而對(duì)于多項(xiàng)式方程的求解，一般只能用迭代法得到近似解，研究其迭代法尤為必要。章迪平等人通過構(gòu)建4階并行迭代方法，實(shí)現(xiàn)了多項(xiàng)式重零點(diǎn)的求解，并通過收斂性定理的證明解釋了多階方程快速計(jì)算思路[2]。安靜等人建立Jacobi多項(xiàng)式及其任意階導(dǎo)數(shù)零點(diǎn)求解方法，通過數(shù)值實(shí)例證明該方法的實(shí)效性[3]。目前多項(xiàng)式方程的迭代法有很多，由于一般的迭代法，在得到近似值時(shí)，誤差需另外估計(jì)。但區(qū)間和圓盤算法在得到近似值的同時(shí)還給出了誤差估計(jì)。王秋華等人利用圓盤算法構(gòu)建多項(xiàng)式并行Halley算法，收斂速度能夠達(dá)到10階，極大的拓寬了算法的應(yīng)用范圍[4]。因而本文主要集中討論區(qū)間和圓盤算法，但是其算法對(duì)于多項(xiàng)式方程有重根的情形可能失效[5]。本文將在異步并行圓盤迭代法的基礎(chǔ)上，對(duì)其進(jìn)行了改進(jìn)，使它既保留了原算法的優(yōu)點(diǎn)，而且還是適用于有重根的多項(xiàng)式方程，使之在實(shí)際應(yīng)用中更具有實(shí)效性。

1 并行算法基本概念及其分類

1.1 并行算法基本概念

并行算法是使用多個(gè)并行處理器實(shí)現(xiàn)大數(shù)據(jù)多次重復(fù)計(jì)算的手段，并且要求計(jì)算必須在一定的時(shí)間內(nèi)同時(shí)完成。其相關(guān)的性能定義主要包括：

定義1 一個(gè)算法的并行度是算法中能用一個(gè)運(yùn)算步并行完成的運(yùn)算個(gè)數(shù)。假設(shè)算法運(yùn)算個(gè)數(shù)為r，利用s個(gè)運(yùn)算步完成，則r/s稱為平均并行度。

圖1 并行計(jì)算模型

如圖1所示，并行計(jì)算有別于串行算法，將并行算法的設(shè)計(jì)與計(jì)算模型映射到并行機(jī)上進(jìn)行運(yùn)算，大大提高了運(yùn)算的速度與運(yùn)算之間的并行度。此外，加速比與效率是對(duì)并行算法設(shè)計(jì)以及并行計(jì)算模型構(gòu)建能效的重要影響因素，通過提升并行算法的加速比使其無限接近SP=P，即并行效率EP=1，從而提升并行機(jī)的運(yùn)算速度。然而，由于并行度、系統(tǒng)負(fù)荷、同步時(shí)間延長(zhǎng)遲等原因，往往無法實(shí)現(xiàn)理想狀態(tài)(加速比SP=P)。因此，需要通過調(diào)整并行運(yùn)算的計(jì)算模型結(jié)構(gòu)與算法設(shè)計(jì)過程，最大限度的降低各種影響因素的負(fù)效應(yīng)，例如異步算法的改進(jìn)就是提升運(yùn)算加速比的最直接有效的方法。

1.2 并行算法分類

并行算法的分類比較廣泛，通用的分類是根據(jù)運(yùn)算進(jìn)程是否同步可以分為同步并行算法與異步并行算法[7]。其中，同步并行算法是指存在k個(gè)進(jìn)程的算法同時(shí)進(jìn)行，但是執(zhí)行過程是按照一個(gè)一個(gè)進(jìn)程有序的進(jìn)行。因此會(huì)出現(xiàn)某些進(jìn)程待機(jī)或者計(jì)算冗余的情況，而且只能在擁有k臺(tái)并行機(jī)的SIMD系統(tǒng)或MIMD系統(tǒng)中進(jìn)行運(yùn)算。而異步并行算法則是需要擁有k臺(tái)并行機(jī)的MIMD系統(tǒng)中進(jìn)行運(yùn)算，k個(gè)進(jìn)程執(zhí)行過程不需要同步，因此在算法上不存在重復(fù)運(yùn)行的情況發(fā)生，大大提升了運(yùn)算的加速比，但是卻需要比較復(fù)雜的控制指令。此外，異步并行算法在執(zhí)行k個(gè)進(jìn)程過程中存在轉(zhuǎn)折區(qū)間，即當(dāng)通信變量信息出現(xiàn)問題或者存在沖突的時(shí)候可以選擇終止或者暫停，實(shí)現(xiàn)執(zhí)行過程的轉(zhuǎn)變以達(dá)到后驗(yàn)先趨的運(yùn)算關(guān)系。所以，本文選擇靈活性更強(qiáng)的異步并行算法作為研究對(duì)象，以滿足多項(xiàng)式方程重根求解的需要。

2 多項(xiàng)式方程求根算法的改進(jìn)

2.1 異步并行圓盤算法

多項(xiàng)式方程求根的算法有很多，包括Laguerre方法，圓盤Schroeder方法，Halley法等。這些算法不僅具有收斂速度快，還具有同時(shí)求解零點(diǎn)的特點(diǎn)。下面Halley異步并行算法作簡(jiǎn)單介紹。

記f(x)=(x-ξi)g(x)，其中f(x)和g(x)均為包含ξi的某個(gè)區(qū)域上的解析函數(shù)，且g(ξi)≠0，記

設(shè)f(x)是以ξ1,ξ2,…,ξn為全部零點(diǎn)的n次多項(xiàng)式，則

在具體計(jì)算時(shí)，用

來計(jì)算Wk+1可能更方便。由圓盤的四則運(yùn)算的包含單調(diào)性可知，在ξj∈Uk條件下，有ξi∈Wk+1。對(duì)于算法(5)，有如下收斂定理。

2.2 改進(jìn)的圓盤迭代法

通過前文介紹了異步并行圓盤迭代法，它雖然既保持了Halley圓盤迭代法的優(yōu)點(diǎn)，同時(shí)又是異步并行算法，但它并不適用于有重根的情形。因此，后續(xù)將對(duì)異步并行圓盤迭代法進(jìn)行改進(jìn)，在保留該法的原有優(yōu)點(diǎn)前提下，而且適用于單根或重根的情形。

(6)

(7)

(8)

設(shè)f(x)是最高次項(xiàng)系數(shù)為1，且以ξm1,ξm2,…,ξml(ln)為全部零點(diǎn)的n次多項(xiàng)式，其中ξi≠ξj(i≠j)，ξi重?cái)?shù)為mi(i=1,2,…,l)為正整數(shù)，則

(9)

Step1Wk=[xk;rk]；

Step2 若f(xk)=0，則轉(zhuǎn)入Step5；

Step4 若rk+1>ε，則k=k+1，轉(zhuǎn)入Step2，否則轉(zhuǎn)入Step5；

Step5 結(jié)束。

在具體計(jì)算時(shí)，用

來計(jì)算Wk+1可能更方便。由圓盤的四則運(yùn)算的包含單調(diào)性可知，在ξj∈Uk條件下，有ξi∈Wk+1。對(duì)于算法(10)，有如下收斂定理。

(11)

rk+1

(12)

證明：利用式(7)和式(10)得

(13)

下面分情況證明：

(1)當(dāng)f(x0)=0時(shí)，取x0=x1，r1=0；

(2)當(dāng)f(x0)≠0時(shí)，根據(jù)圓盤運(yùn)算的定義，由x0?U0得

a0=0

(14)

(15)

則由式(6)，(9)，(14)，(15)得

R0

(16)

(17)

(18)

(19)

故有r1即無論f(x)=0還是f(x)≠0，都有

r1

成立。

由式(11)，(19)得

r1

(20)

如能證明ξj∈U1，α1成立，則式(12)對(duì)所有的k成立，下面分情況證明它。

(1)當(dāng)f(x0)=0時(shí)，取x0=x1，r1=0，則有

1)由于|ξj-x1|=|ξj-x0|-|x0-x1|≥ρ0-|x0-x1|=ρ1，所以ξj∈U1；

(2)當(dāng)f(x0)≠0時(shí)，證明如下：

由于|ξj-x1|≥|ξj-x0|-|x0-x1|≥ρ0-|x0-x1|=ρ1，所以ξj∈U1。

由式(11)，(13)，(17)得：

(21)

由式(20)，(21)得：

故無論f(x)=0還是f(x)≠0，都有ξj∈U1，α1成立。同時(shí)式(12)結(jié)果對(duì)任意k都成立，且rk+1當(dāng)k→時(shí)，rk→0，而ξi∈Wk，所以定理證明完畢。綜上所述，當(dāng)W0中f(x)有且只有零點(diǎn)ξi，同時(shí)f(x)其余零點(diǎn)均在中，W0的半徑滿足(11)式，則由式(10)產(chǎn)生的圓盤序列至少以3階的收斂速度收斂于ξi。

3 結(jié)論

本文主要針對(duì)多項(xiàng)式方程求根時(shí)有重根問題進(jìn)行展開討論，在現(xiàn)有的異步并行圓盤迭代法基礎(chǔ)上，進(jìn)行改進(jìn)，構(gòu)造一種新的圓盤迭代法，使得其算法不僅保持了原算法的優(yōu)點(diǎn)，而且適用于多項(xiàng)式有重零點(diǎn)的情形，使之在實(shí)際應(yīng)用中更具有實(shí)效性。最后討論了它的收斂性，得出該算法的收斂定理。此外，改進(jìn)后的迭代法能夠適用于存在重根的多項(xiàng)式方程，對(duì)于零點(diǎn)的計(jì)算具有十分重要的應(yīng)用意義。