實(shí)代數(shù)曲線的孤立零點(diǎn)

徐 嘉

(西南民族大學(xué)數(shù)學(xué)學(xué)院，四川 成都 610041)

實(shí)系數(shù)多項(xiàng)式f(x，y)∈R[x，y]的實(shí)零點(diǎn)是指集合VR(f)

VR(f)傳統(tǒng)上稱為實(shí)代數(shù)曲線.雖然VR(f)可能是空集(例如而不是真正的曲線(一維幾何對(duì)象).f(x，y)的實(shí)零點(diǎn)又分為兩類，奇異點(diǎn)和非奇異點(diǎn).如果點(diǎn)P∈R2滿足

則稱為奇異的，否則稱為非奇異的(或正則的).而奇異點(diǎn)中有一類點(diǎn)具有特殊的重要性，那就是孤立零點(diǎn).一個(gè)點(diǎn)P∈R2被稱為代數(shù)曲線VR(f)的孤立零點(diǎn)如果它滿足以下兩個(gè)條件:

1)f(P)=0

2)存在充分小的正數(shù)ε使得

條件2直觀的說(shuō)法是:在一個(gè)中心為P半徑充分小的圓內(nèi)，除了點(diǎn)P以外f(x，y)沒(méi)有其它的實(shí)零點(diǎn).等價(jià)地說(shuō)，f(x，y)在P的附近有恒定的符號(hào).因此孤立零點(diǎn)又可分為兩種類型，極小型和極大型，分別對(duì)應(yīng)著條件在P的附近f(X)＞0和f(X)＜0.容易看出P是曲線VR(f)的極小型孤立零點(diǎn)?P是曲線VR(-f)的極大型孤立零點(diǎn).

因此，我們研究極小型孤立零點(diǎn)就足夠了.

通過(guò)坐標(biāo)的平移，我們總可以假定P是原點(diǎn)(0，0)，而不會(huì)改變問(wèn)題的實(shí)質(zhì).當(dāng)然，一般情況下點(diǎn)P的坐標(biāo)可能是較為復(fù)雜的實(shí)代數(shù)數(shù)，對(duì)于代數(shù)數(shù)的處理已經(jīng)有較為成熟的方法可參考文獻(xiàn)[1-2].我們將集中精力討論原點(diǎn)的孤立性.本文中研究的主要問(wèn)題是:

給定多項(xiàng)式f∈R[x，y]，判斷原點(diǎn)是否代數(shù)曲線VR(f)的孤立零點(diǎn)?

實(shí)代數(shù)曲線的孤立零點(diǎn)有基本的重要性，它涉及許多其它的數(shù)學(xué)問(wèn)題.如曲線在奇異點(diǎn)附近的拓?fù)浣Y(jié)構(gòu)問(wèn)題，例如代數(shù)曲線VR(f)，f=(x-y)20+x40-x10y20+x28在原點(diǎn)附近是否有實(shí)分枝?這類問(wèn)題在計(jì)算機(jī)輔助幾何設(shè)計(jì)中常常會(huì)遇到.另一類問(wèn)題是函數(shù)的極值點(diǎn)問(wèn)題.例如對(duì)多項(xiàng)式函數(shù)

問(wèn):原點(diǎn)是否f的極值點(diǎn)?如果是，是極大值點(diǎn)，還是極小值點(diǎn)?否則，是鞍點(diǎn)嗎?判斷極大極小點(diǎn)問(wèn)題是最優(yōu)化理論中的基本問(wèn)題，常常使用熟知的海賽(Hessen)矩陣方法[3].但是當(dāng)海賽矩陣是奇異矩陣時(shí)該方法失效.

人們對(duì)實(shí)代數(shù)曲線的研究已經(jīng)有相當(dāng)長(zhǎng)的歷史.對(duì)于孤立零點(diǎn)的研究也積累了大量的資料和方法.首先，一種較為平凡的方法是實(shí)量詞消去方法.也就是將問(wèn)題歸結(jié)為如下的量詞消去問(wèn)題，給定實(shí)量詞公式

求等價(jià)的無(wú)量詞公式.標(biāo)準(zhǔn)的量詞消去工具，如塔斯基方法(Tarski)[4]，著名的柱形代數(shù)分解方法(CAD)[5-6]，都可以被使用來(lái)解決孤立零點(diǎn)的問(wèn)題.2019年文獻(xiàn)[7]新近建立的一種方法是將問(wèn)題歸結(jié)為一個(gè)最優(yōu)化問(wèn)題，然后使用數(shù)學(xué)規(guī)劃的策略解決問(wèn)題.這幾種類型方法的復(fù)雜性對(duì)多項(xiàng)式的次數(shù)有較大的依賴性.在針對(duì)下面這類多項(xiàng)式時(shí)，有明顯的不足.考慮多項(xiàng)式

容易發(fā)現(xiàn)原點(diǎn)(0，0)是這個(gè)多項(xiàng)式的孤立零點(diǎn)，它與具體的多項(xiàng)式g(x，y)無(wú)關(guān)，僅僅只需要g(x，y)的次數(shù)大于4就足夠了，也就是說(shuō)它可以是100 000次，然而并不影響原點(diǎn)的孤立性.在本文中我們將要建立一個(gè)方法，它充分利用了上面觀察到的特點(diǎn).

本文以下部分的內(nèi)容被安排為三節(jié)，第二節(jié)是預(yù)備知識(shí)，主要復(fù)習(xí)關(guān)于牛頓(I.Newton)多邊形和牛頓變換以及單變量多項(xiàng)的實(shí)根隔離等基本內(nèi)容，它們是證明主要結(jié)果和建立算法的工具.第三節(jié)是主要結(jié)果及其證明.最后一節(jié)是算法的描述以及運(yùn)算實(shí)例.

1 預(yù)備知識(shí)

首先，我們需要復(fù)習(xí)一些關(guān)于代數(shù)曲線的基本知識(shí)，可參考文獻(xiàn)[8-9].

1.1 牛頓折線.

令

在實(shí)平面R2上描出滿足ai，j≠0的點(diǎn)(i，j).我們獲得集合

Δ(f)稱為f的牛頓圖(Newton diagram).牛頓圖Δ(f)的凸包是一個(gè)凸多邊形，它的下邊界被稱為牛頓折線，記為N(f).牛頓折線另一個(gè)嚴(yán)格的定義為:凸集的緊面.其中Conv(S)表示集合的凸包，R+是非負(fù)實(shí)數(shù)集合.

多項(xiàng)式

的牛頓圖和牛頓折線見圖1.牛頓折線N(f)的一條邊T對(duì)應(yīng)了多項(xiàng)式f的一個(gè)子多項(xiàng)式，我們記為fT

對(duì)本文中，主要被使用的是N(f)最陡的那條邊.

注意到有一些平凡的情況會(huì)出現(xiàn).如果N(f)僅僅是一個(gè)點(diǎn)時(shí)，則必有x|f或y|f，也就是有f(0，y)=0或f(x，0)=0，都表明(0，0)不是曲線VR(f)的孤立零點(diǎn).

圖1 多項(xiàng)式的牛頓圖與牛頓折線Fig.1 Newtondiagram and Newton polyline of a polynomial

1.2 擬齊次多項(xiàng)式

多項(xiàng)式g∈R[x，y]被稱為擬齊次的，如果存在正整數(shù)w1，w2，μ滿足

w1，w2稱為權(quán).

容易驗(yàn)證任意多項(xiàng)式的牛頓折線的一條邊T對(duì)應(yīng)的子多項(xiàng)式fT都是擬齊次的.為了讓?duì)瘫M可能的小，我們假設(shè)w1，w2是互素的，并稱這時(shí)的μ為g的擬次數(shù).

1.3 牛頓變換

實(shí)系數(shù)多項(xiàng)式f∈R[x，y]滿足f無(wú)平方因子，f(0，0)=0，且x f，y f.于是f(0，y)≠0，設(shè)d是f(0，y)的最低次數(shù)，也記為tdeg(f，y)，則(0，d)是N(f)的一個(gè)頂點(diǎn).我們假定T是牛頓折線N(f)包含(0，d)的那條邊.令z是fT(1，y)或fT(-1，y)的一個(gè)根，再設(shè)

其中w1，w2是fT的權(quán)，μ為fT的擬次數(shù).

引理1是多項(xiàng)式.

證明：與通常關(guān)于Newton-Puiseux算法中的證明是一樣的.可參考文獻(xiàn)[8-9].

我們把

稱為牛頓變換.

討論:在經(jīng)典的文獻(xiàn)(如[8-9])中的牛頓變換，只考慮fT(1，y)=0的復(fù)根，這對(duì)討論復(fù)代數(shù)曲線是足夠的.但是如果要討論實(shí)代數(shù)曲線在實(shí)空間的情況，則fT(1，y)的信息是不夠的，還需要考慮fT(-1，y)=0的實(shí)根.一個(gè)簡(jiǎn)單的例子如下

其牛頓折線N(f)只有一條邊，它就是連接(3，0)和(0，2)的線段，fT=x3+y2.此時(shí)fT(1，y)=1+y2無(wú)實(shí)根，這樣就得不到關(guān)于f在原點(diǎn)附近實(shí)分枝的信息.事實(shí)上f在原點(diǎn)附近有一個(gè)實(shí)分枝，對(duì)應(yīng)的Newton-Puiseux展開為

為了得到實(shí)代數(shù)曲線實(shí)分枝的信息，解決問(wèn)題的思路有兩個(gè)，一是考慮所謂Rational Puiseux展開[10]，另一個(gè)就是同時(shí)考慮fT(1，y)和fT(-1，y)的實(shí)根.本文的方法屬于后者.

1.4 單變量多項(xiàng)式的實(shí)根隔離算法

實(shí)系數(shù)多項(xiàng)式的實(shí)根隔離就是求一列互不相交的區(qū)間，使其包含該多項(xiàng)式的所有實(shí)根，而且其中的每一個(gè)區(qū)間恰含有一個(gè)根.從某種意義上，完成實(shí)根隔離就代表求出了多項(xiàng)式的所有實(shí)根，我們可以用某個(gè)區(qū)間來(lái)指代那個(gè)區(qū)間上的代數(shù)數(shù)并進(jìn)行各種運(yùn)算.

實(shí)根隔離算法是實(shí)代數(shù)的基本算法之一.有大量的參考文獻(xiàn)[11-13]和基于不同原理的算法.本文中，我們僅僅指出實(shí)根隔離算法的基本應(yīng)用，就是計(jì)算給定多項(xiàng)式相異實(shí)根的個(gè)數(shù)，以及判斷一個(gè)實(shí)根是奇數(shù)重根還是偶數(shù)重根.一個(gè)實(shí)例如下

例1.考慮多項(xiàng)式

使用實(shí)根隔離算法，例如運(yùn)行數(shù)學(xué)軟件Maple中的命令realroot，我們能夠獲得三個(gè)區(qū)間

也就是說(shuō)h(x)有三個(gè)不同的實(shí)根.計(jì)算區(qū)間端點(diǎn)的符號(hào)可知，位于區(qū)間中的實(shí)根是偶數(shù)重根，因?yàn)閰^(qū)間端點(diǎn)的符號(hào)相同.而位于區(qū)中的根是奇數(shù)重根，因?yàn)閰^(qū)間端點(diǎn)的符號(hào)不同.從下面的分解式可以驗(yàn)證這些斷言都是正確的

一般情況也是如此.在下文算法IsolatedZero中需要使用實(shí)根隔離算法.

2 主要結(jié)果

在敘述我們的主要結(jié)果之前先證明幾個(gè)引理.

引理2：設(shè)f∈R[x，y]是非常數(shù)的擬齊次多項(xiàng)式.則下面三個(gè)條件是等價(jià)的.

1)(0，0)是曲線VR(f)的極小型孤立零點(diǎn)；

2)?y∈Rf(±1，y)＞0；

3)多項(xiàng)式f(±1，y)無(wú)實(shí)根且f(1，0)＞0.

證明：2與3的等價(jià)性是明顯的.下面主要證明1與2之間的等價(jià)性.f是擬齊次的，記它的權(quán)為w1，w2，擬次數(shù)為μ.則f(xw1，yw2)，

是次數(shù)為μ的齊次多項(xiàng)式.于是有恒等式

1?2.如果(0，0)是曲線VR(f)的孤立零點(diǎn)，則由定義不妨設(shè)正數(shù)ε滿足

對(duì)任意給定的點(diǎn)(a，b)∈R2/{(0，0)}，考慮曲線又

所以當(dāng)t充分小時(shí)，于是得到:存在正數(shù)t使

從(1)立刻得到f(a，b)＞0.由于(a，b)是任意的，取(a，b)=(±1，y)，即得

2?1.反過(guò)來(lái)，如果

由于f(±1，y)是只含有y的多項(xiàng)式，所以最大次數(shù)是偶數(shù)，系數(shù)是正數(shù).于是可以推出

假設(shè)a≠0，利用等式(1)，有

其中±1由a的符號(hào)確定，保持一致.于是我們證明了，對(duì)任意(a，b)≠(0，0)，都有

由定義，(0，0)是曲線VR(f)的極小型孤立零點(diǎn).

引理3：實(shí)系數(shù)多項(xiàng)式f∈R[x，y]滿足f(0，0)=0.如果存在牛頓折線的一條邊T使得?(x，y)∈R2/{(0，0)}fT(x，y)＞0(或＜0)，則f的牛頓折線只含有一條邊T.

證明：注意到如果?(x，y)∈R2/{(0，0)}fT(x，y)＞0，則fT(x，y)不能被x或y整除.也就是fT(x，y)必須同時(shí)滿足fT(0，y)，fT(x，0)都不恒為0，記它們的最低次數(shù)分別為s，t(s≥1，t≥1).因?yàn)閒T是擬齊次的，它的所有的單項(xiàng)xi yj對(duì)應(yīng)的點(diǎn)(i，j)都滿足線性關(guān)系

點(diǎn)(s，0)和(0，t)也在這條線上，所以線段T滿足

可見T是凸包的一維緊面.所以f的牛頓折線只含有一條邊，就是T.

引理4：(廣義平均值不等式)[14]x，y是正實(shí)數(shù)，a，b，c，d是實(shí)數(shù).存在常數(shù)λ，0≤λ≤1，使得

則有如下不等式成立

引理5：實(shí)系數(shù)多項(xiàng)式f∈R[x，y]滿足f(0，0)=0.如果存在牛頓折線的一條邊T使得多項(xiàng)式fT(±1，y)無(wú)實(shí)根且fT(1，0)＞0，則(0，0)是VR(f)的極小型孤立零點(diǎn).

證明：因?yàn)閒T是擬齊次的，從引理2的證明，容易看出

由引理3可知f的牛頓折線只含有一條邊T.可以將多項(xiàng)式f表示為w1，w2是fT的權(quán)，μ是擬次數(shù).因?yàn)楣?2)，可知兩個(gè)單項(xiàng)

注意到對(duì)任意單項(xiàng)式xi yj，iw1+j w2＞μ，存在正實(shí)數(shù)使得是根據(jù)引理4，知存在正常數(shù)對(duì)任意正實(shí)數(shù)x，y，滿足不等式

其中N是求和號(hào)中單項(xiàng)式的個(gè)數(shù).

于是有

sign(ai，j)是符號(hào)函數(shù)，即

由不等式(3)有

當(dāng)x，y都充分小時(shí)，有

所以當(dāng)x，y都是正數(shù)且時(shí)

完全類似，我們能夠證明，當(dāng)x，y都是正數(shù)且時(shí)

也就是證明了(0，0)是f的極小型孤立零點(diǎn).

定理1：實(shí)系數(shù)多項(xiàng)式f∈R[x，y]滿足f無(wú)平方因子，f(0，0)=0，且x f，y f.T是N(f)中最陡的那條邊.(0，0)是曲線VR(f)的極小型孤立零點(diǎn)當(dāng)且僅當(dāng)下面兩個(gè)條件之一成立

1)fT(±1，y)沒(méi)有實(shí)根且fT(1，0)＞0；

2)fT(±1，y)僅有偶數(shù)重實(shí)根且fT(1，0)＞0，且對(duì)fT(±1，y)=0的任意實(shí)根γ，(0，0)是曲線的極小型孤立零點(diǎn)，其中由第二節(jié)的(*)式定義.

證明：必要性.假設(shè)(0，0)是曲線VR(f)的極小型孤立零點(diǎn)，如果fT(±1，y)沒(méi)有實(shí)根且fT(1，y)＞0，則結(jié)果顯然.如果fT(±1，y)有實(shí)根，先來(lái)證明fT(±1，y)不能有奇數(shù)重實(shí)根.反證法，假設(shè)fT(±1，y)有奇數(shù)重實(shí)根，不失一般性，設(shè)y0是fT( 1，y0)=0的奇數(shù)重實(shí)根(y0是fT(-1，y0)=0的奇數(shù)重實(shí)根的情況完全類似討論)，則存在一個(gè)小區(qū)間[a，b]，滿足y0∈[a，b]，且fT(1，a)fT(1，b)＜0.令x=tw1，y=tw2根據(jù)表達(dá)式

有

其中g(shù)(t)是一個(gè)多項(xiàng)式.當(dāng)t＞0并趨于0時(shí)，的符號(hào)與tμfT(1，a)的符號(hào)相同.同理，當(dāng)t＞0并趨于0時(shí)的符號(hào)與tμfT(1，b)的符號(hào)相同，但是fT(1，a)fT(1，b)＜0，也就是說(shuō)f在原點(diǎn)附近任意小的鄰域都可取到正值和負(fù)值，所以(0，0)不是曲線VR(f)的孤立零點(diǎn).矛盾.

于是當(dāng)x=0時(shí)

當(dāng)x≠0時(shí)，但

于是對(duì)一個(gè)給定的正數(shù)ε存在正數(shù)ε2，使得當(dāng)時(shí)

也就是說(shuō)當(dāng)(x，y)充分接近原點(diǎn)時(shí)，也充分接近原點(diǎn).根據(jù)孤立零點(diǎn)的定義，對(duì)充分小的ε3我們有

所以

取δ=min{ε1，ε3}，獲得

充分性.

如果fT(±1，y)沒(méi)有實(shí)根且fT(1，0)＞0，由引理5，(0，0)是VR(f)的極小型孤立零點(diǎn).如果fT(±1，y)每一個(gè)實(shí)根都是偶數(shù)重根，由fT(1，0)＞0則有fT(±1，y)≥0.

記

于是Br被分解到了三個(gè)部分

條件fT(1，0)＞0推知fT(±1，y)的最低次數(shù)d＞0，于是點(diǎn)(0，d)∈T.單項(xiàng)a0，d yd的系數(shù)a0，d＞0.因此，V+(f)≠φ.假設(shè)(0，0)不是VR(f)的極小型孤立零點(diǎn)，也就是說(shuō)，存在正數(shù)ε當(dāng)r＜ε時(shí)，VR(f)∩Br≠φ.根據(jù)曲線挑選引理[15]，我們能夠找到實(shí)解析函數(shù)φ(t)滿足φ(0)=0，f(t，φ(t))≡0(t∈(0，ε)).

另一方面，根據(jù)代數(shù)曲線的基本理論[8-9]，每一個(gè)實(shí)解析函數(shù)φ(t)都可以通過(guò)Newton-Puiseux展開來(lái)得到，因此φ(t)可以寫為的高階項(xiàng)

其中γ是fT(±1，y)=0的實(shí)根.于是

定理1顯示了一個(gè)迭代的過(guò)程去決定(0，0)是否f的極小型孤立零點(diǎn).詳細(xì)內(nèi)容將在下一節(jié)給出.

3 算法

根據(jù)主要定理，我們能夠建立判定孤立零點(diǎn)的如下算法

算法IsolatedZero

輸入:f∈R[x，y]，滿足f無(wú)平方因子，f(0，0)=0.

輸出:

①如果x|f或y|f或次數(shù)d=tdeg(f(0，y)，y)是奇數(shù)則輸出false

②T←牛頓多邊形N(f)的包含點(diǎn)(0，d)的那條邊

③R1←fT(1，y)的實(shí)根集合 ＃利用實(shí)根隔算法獲得實(shí)根的不可約多項(xiàng)式區(qū)間表示

④R-1←fT(-1，y)的實(shí)根集合

⑤如果f(1，y)或f(-1，y)之一有單重實(shí)根，則輸出false

⑥如果R1∪R-1=?則輸出true

⑦w1，w2←fT的權(quán)

⑧μ←fT的擬次數(shù)

⑩?γ∈R1∪R-1IsolatedZero

算法的正確性由定理1保證，而算法的終止性則依賴于引理1.

上述算法中第3，4步中的實(shí)根可表示為不可約多項(xiàng)式和一個(gè)區(qū)間，區(qū)間由第二部分的4小節(jié)中實(shí)根隔算法來(lái)得到.算法的第5步，判斷實(shí)根的奇偶重?cái)?shù)也由實(shí)根隔離算法來(lái)實(shí)現(xiàn).最后，以引言中的例子來(lái)看看算法的運(yùn)行過(guò)程.

1)牛頓折線N(f)只有一條邊T，對(duì)應(yīng)的子多項(xiàng)式fT=(x-y)20.于是

2)R1={1}，R-1={-1}，并且1和-1都是偶重根.fT的權(quán)是w1=1，w2=1，擬次數(shù)μ=20.

4)f的牛頓折線也只有一條邊T，對(duì)應(yīng)的子多項(xiàng)式是fT=x8+y20.這時(shí)

fT(±1，y)無(wú)實(shí)根，因此輸出true.

獲得(0，0)是f的極小型孤立零點(diǎn).