努爾麥麥江·阿布都吾甫
(喀什大學(xué) 數(shù)學(xué)與統(tǒng)計(jì)學(xué)院,新疆 喀什 844000)
求解多項(xiàng)式零點(diǎn)問題是解決很多實(shí)際問題的過程中經(jīng)常要遇到的數(shù)學(xué)問題之一,也引起了眾多人的廣泛關(guān)注[1]。多項(xiàng)式方程到了5次及其以上就沒有公式解,因而對于多項(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ū)間和圓盤算法,但是其算法對于多項(xiàng)式方程有重根的情形可能失效[5]。本文將在異步并行圓盤迭代法的基礎(chǔ)上,對其進(jìn)行了改進(jìn),使它既保留了原算法的優(yōu)點(diǎn),而且還是適用于有重根的多項(xiàng)式方程,使之在實(shí)際應(yīng)用中更具有實(shí)效性。
并行算法是使用多個(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)算之間的并行度。此外,加速比與效率是對并行算法設(shè)計(jì)以及并行計(jì)算模型構(gòu)建能效的重要影響因素,通過提升并行算法的加速比使其無限接近SP=P,即并行效率EP=1,從而提升并行機(jī)的運(yùn)算速度。然而,由于并行度、系統(tǒng)負(fù)荷、同步時(shí)間延長遲等原因,往往無法實(shí)現(xiàn)理想狀態(tài)(加速比SP=P)。因此,需要通過調(diào)整并行運(yùn)算的計(jì)算模型結(jié)構(gòu)與算法設(shè)計(jì)過程,最大限度的降低各種影響因素的負(fù)效應(yīng),例如異步算法的改進(jìn)就是提升運(yùn)算加速比的最直接有效的方法。
并行算法的分類比較廣泛,通用的分類是根據(jù)運(yùn)算進(jìn)程是否同步可以分為同步并行算法與異步并行算法[7]。其中,同步并行算法是指存在k個(gè)進(jìn)程的算法同時(shí)進(jìn)行,但是執(zhí)行過程是按照一個(gè)一個(gè)進(jìn)程有序的進(jìn)行。因此會出現(xiàn)某些進(jìn)程待機(jī)或者計(jì)算冗余的情況,而且只能在擁有k臺并行機(jī)的SIMD系統(tǒng)或MIMD系統(tǒng)中進(jìn)行運(yùn)算。而異步并行算法則是需要擁有k臺并行機(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)的異步并行算法作為研究對象,以滿足多項(xiàng)式方程重根求解的需要。
多項(xiàng)式方程求根的算法有很多,包括Laguerre方法,圓盤Schroeder方法,Halley法等。這些算法不僅具有收斂速度快,還具有同時(shí)求解零點(diǎn)的特點(diǎn)。下面Halley異步并行算法作簡單介紹。
記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。對于算法(5),有如下收斂定理。
通過前文介紹了異步并行圓盤迭代法,它雖然既保持了Halley圓盤迭代法的優(yōu)點(diǎn),同時(shí)又是異步并行算法,但它并不適用于有重根的情形。因此,后續(xù)將對異步并行圓盤迭代法進(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。對于算法(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)對所有的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é)果對任意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。
本文主要針對多項(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)式方程,對于零點(diǎn)的計(jì)算具有十分重要的應(yīng)用意義。