把正定六次多项式表为多项式的平方和的一种算法

An Algorithm to Represent a Positive Definite Sixth-Degree Polynomials as the Sum of Squares of Polynomials

摘要: 本文给出了一个把正定的一元六次实系数多项式表示成一些实系数多项式的可行算法。利用这个方法也可证明一个具体的数字系数的一元六次多项式的正定性。

Abstract: This paper presents a feasible algorithm for expressing positive definite sixth-order real coefficient polynomials as the sum of squares of some real coefficient polynomials. This method can also be used to prove that a specific number coefficient polynomial of the sixth degree is positive definite.

如果能把一个实系数多项式 $f\left(x_1,x_2,\cdots ,x_n\right)$ 表示成一些实系数多项式的平方和，那显然 $f\left(x_1,x_2,\cdots ,x_n\right)$ 一定是半正定或正定的多项式。但是反过来如果已知实系数多项式 $f\left(x_1,x_2,\cdots ,x_n\right)$ 是正定的或半正定的，却不一定能将他表示成一些实系数多项式的平方和。一个著名的反例可见 [1]。在什么条件下能将一个正定的或半正定的实系数多项式 $f\left(x_1,x_2,\cdots ,x_n\right)$ 表示成一些实系数多项式的平方和以及如何实现这种表示就是著名的Hilbert第17问题。有关文献可见 [1] [2] [3] [4]。

对 $n=1$，已经知道有一个更强的结果如下：

定理0：一个实系数的一元非负多项式必可表为两个一元实系数多项式的平方和，见 [1] [5] [6]，但是以上定理的证明是存在性的，需要用到方程式的根，因此只能得出近似的表达式。对于一元和多元的非负多项式，也已经有人给出了将其表为多项式平方和的算法和程序，见 [7] [8] [9]，但是一般都比较繁，适用于计算机计算。作者在 [10] 中曾对四次非负多项式给出了一个利用多项式系数的判据，本文则给出了一个把六次正定多项式表为平方和的不依赖于上述文献中算法和程序的独立算法，利用此算法也可证明一个六次多项式的正定性。

定理1 (算法1)：

设 $f\left(x\right)=x^6+a_1{x}^5+a_2{x}^4+a_3{x}^3+a_4{x}^2+a_{5}x+a_6$ 是一个多项式，又设 $\alpha ,\beta$ 是两个有理数

$p=\frac{a_1}{2}$, $q=\frac{a_2-p^2-{\alpha }^2}{2}$, $r=\frac{a_3}{2}-pq-\alpha \beta$, $\gamma =\frac{\frac{a_5}{2}-qr}{\beta }$,

如果 $b_4=a_4-q^2-2pr-{\beta }^2-2\alpha \gamma >0$， $b_6=a_6-r^2-{\gamma }^2>0$，则

$f\left(x\right)={\left(x^3+p{x}^2+qx+r\right)}^2+{\left(\alpha x^2+\beta x+\gamma \right)}^2+b_4{x}^2+b_6$

是有理系数多项式的平方和。

证明：设可把多项式 $f\left(x\right)$ 表示成下面形式的平方和

$f\left(x\right)={\left(x^3+p{x}^2+qx+r\right)}^2+{\left(\alpha x^2+\beta x+\gamma \right)}^2.$

则对照两边的系数可得

$p=\frac{a_1}{2}$ (1)

$p^2+2q+{\alpha }^2=a_2$ (2)

$pq+r+\alpha \beta =\frac{a_3}{2}$ (3)

$q^2+2pr+{\beta }^2+2\alpha \gamma =a_4$ (4)

$qr+\beta \gamma =\frac{a_5}{2}$ (5)

$r^2+{\gamma }^2=a_6$ (6)

设 $\alpha ,\beta$ 是两个有理数，我们用下面的程序逐步算出 $p,q,r,\gamma$，令

$p=\frac{a_1}{2}$ (7)

则从(2)式可以解出q，

$q=\frac{a_2-p^2-{\alpha }^2}{2}$ (8)

再从(3)式可以解出r，

$r=\frac{a_3}{2}-pq-\alpha \beta$ (9)

再从(5)式解出 $\gamma$

$\gamma =\frac{\frac{a_5}{2}-qr}{\beta }$ (10)

这时如果

$b_4=a_4-q^2-2pr-{\beta }^2-2\alpha \gamma >0$ (11)

$b_6=a_6-r^2-{\gamma }^2>0$ (12)

则

$\begin{array}{c}f\left(x\right)=x^6+a_1{x}^5+a_2{x}^4+a_3{x}^3+a_4{x}^2+a_{5}x+a_6\\ =x^6+2p{x}^5+\left(p^2+2q+{\alpha }^2\right)x^4+2\left(pq+r+\alpha \beta \right)x^3\\ +\left(q^2+2pr+{\beta }^2+2\alpha \gamma \right)x^2+2\left(qr+\beta \gamma \right)x+r^2+{\gamma }^2\\ +(a_4-q^2-2pr-{\beta }^2-2\alpha \gamma )x^2+\left(a_6-r^2-{\gamma }^2\right)\\ ={\left(x^3+p{x}^2+qx+r\right)}^2+{\left(\alpha x^2+\beta x+\gamma \right)}^2+b_4{x}^2+b_6\end{array}$

便被表示成了有理系数多项式的平方和。

注1：我们可首先求出 $f\left(x\right)$ 的近似根， $x_1,x_2,x_3,{\bar{x}}_1,{\bar{x}}_2,{\bar{x}}_3$，其中 ${\bar{x}}_1,{\bar{x}}_2,{\bar{x}}_3$ 分别是 $x_1,x_2,x_3$ 的共轭复根，那么

$\begin{array}{c}f\left(x\right)\doteq \left(x^3-\left(x_1+x_2+x_3\right)x^2+\left(x_1{x}_2+x_2{x}_3+x_1{x}_3\right)x+x_1{x}_2{x}_3\right)\\ \left(x^3-\left({\bar{x}}_1+{\bar{x}}_2+{\bar{x}}_3\right)x^2+\left({\bar{x}}_1{\bar{x}}_2+{\bar{x}}_2{\bar{x}}_3+{\bar{x}}_1{\bar{x}}_3\right)x+{\bar{x}}_1{\bar{x}}_2{\bar{x}}_3\right)\\ =[x^3-\mathrm{Re}\left(x_1+x_2+x_3\right)x^2+\mathrm{Re}\left(x_1{x}_2+x_2{x}_3+x_1{x}_3\right)x-\mathrm{Re}\left(x_1{x}_2{x}_3\right)\\ -i\left(\mathrm{Im}\left(x_1+x_2+x_3\right)x^2-\mathrm{Im}\left(x_1{x}_2+x_2{x}_3+x_1{x}_3\right)x+\mathrm{Im}\left(x_1{x}_2{x}_3\right)\right)]\end{array}$

$\begin{array}{l}=[x^3-\mathrm{Re}\left(x_1+x_2+x_3\right)x^2+\mathrm{Re}\left(x_1{x}_2+x_2{x}_3+x_1{x}_3\right)x-\mathrm{Re}\left(x_1{x}_2{x}_3\right)\\ +i\left(\mathrm{Im}\left(x_1+x_2+x_3\right)x^2-\mathrm{Im}\left(x_1{x}_2+x_2{x}_3+x_1{x}_3\right)x+\mathrm{Im}\left(x_1{x}_2{x}_3\right)\right)]\\ ={\left[x^3-\mathrm{Re}\left(x_1+x_2+x_3\right)x^2+\mathrm{Re}\left(x_1{x}_2+x_2{x}_3+x_1{x}_3\right)x-\mathrm{Re}\left(x_1{x}_2{x}_3\right)\right]}^2\\ +{\left[\left(\mathrm{Im}\left(x_1+x_2+x_3\right)x^2-\mathrm{Im}\left(x_1{x}_2+x_2{x}_3+x_1{x}_3\right)x+\mathrm{Im}\left(x_1{x}_2{x}_3\right)\right)\right]}^2\end{array}$

便可把 $f\left(x\right)$ 近似地表示成 ${\left(x^3+p{x}^2+qx+r\right)}^2+{\left(\alpha x^2+\beta x+\gamma \right)}^2$ 的形式，因此我们然后可取 $\mathrm{Im}\left(x_1+x_2+x_3\right)$， $-\mathrm{Im}\left(x_1{x}_2+x_2{x}_3+x_1{x}_3\right)$ 的精确度充分高的有理近似值作为 $\alpha ,\beta$。但有时会可能取的 $\alpha ,\beta$ 近似值精度已经非常高了(例如在例1中，你取到小数点后40位)，条件(11)、(12)仍不能满足，这时就要考虑使用定理2。

注2：本定理的意义在于注1中的平方和表达式是近似的，而利用本定理得出的平方和表达式是精确的，因此是一种理论上可实现的严格证明六次多项式正定性的算法。

例1：考虑多项式

$f\left(x\right)=x^6-2x^5+4x^4-6x^3+6x^2-4x+2={\left(x^3-x^2+x-1\right)}^2+{\left(x^2-x+1\right)}^2$

显然 $f\left(x\right)$ 是正定的。且有

$a_1=-2,a_2=4,a_3=-6,a_4=6,a_5=-4,a_6=2$

取

$\alpha =\text{2}\text{.76404835471887500020216066332}$,

$\beta =-\text{2}\text{.4077057325080608585210484307}$.

那么，可以逐步算出 $p=-1$， $q=-2.319981653612060$， $r=\text{1}\text{.335033414974050}$

$\gamma =-0.455725554366590$

$b_4=0.010000000000012>0$

$b_6=0.009999999999991>0$

因此根据定理1，我们便有

$f\left(x\right)={\left(x^3+p{x}^2+qx+r\right)}^2+{\left(\alpha x^2+\beta x+\gamma \right)}^2+b_4{x}^2+b_6$

由此顺便得出 $f\left(x\right)$ 分解成平方和的方式不是唯一的(这里指本质上不是唯一的，而不是像 ${\left(\sqrt{2}x\right)}^2=x^2+x^2$ 这样平凡的方式。)。

注3：本例中的 $\alpha ,\beta$ 的近似值并不是用注1中的方法得出的，而是根据作者的实验找到的，如果按照注1中的方法，即使把 $\alpha ,\beta$ 的近似值的精度取到小数点后40位，条件(11)、(12)仍不能满足。

在上面的例子中 $\alpha ,\beta$ 的精度都取得相当高，这是因为如果误差 $\alpha ,\beta$ 稍微大一点，就会使条件(11)，(12)无法满足，下面我们给出一个改进的方法，可以允许 $\alpha ,\beta$ 的误差稍微大一点。

定理2 (算法2)：设 $\epsilon >0$ 是一个适当小的正数，对

$f\left(x\right)=x^6+a_1{x}^5+a_2{x}^4+a_3{x}^3+a_4{x}^2+a_{5}x+a_6$

首先考虑多项式

$g\left(x\right)=x^6+a_1{x}^5+\left(a_2-\epsilon \right)x^4+a_3{x}^3+\left(a_4-\epsilon \right)x^2+a_{5}x+a_6-\epsilon$

然后对多项式 $g\left(x\right)$ 应用定理1，算出 $b_4,b_6$，如果

$b_4+\epsilon >0,b_6+\epsilon >0$

则

$f\left(x\right)={\left(x^3+p{x}^2+qx+r\right)}^2+{\left(\alpha x^2+\beta x+\gamma \right)}^2+\epsilon x^4+\left(b_4+\epsilon \right)x^2+b_6+\epsilon$

是一些系数为有理数的多项式的平方和。

证明与定理1类似。

例2：考虑多项式

$f\left(x\right)=x^6-2x^5+4x^4-6x^3+6x^2-4x+2$

取 $\epsilon =0.1$，先考虑多项式

$g\left(x\right)=x^6-2x^5+3.9x^4-6x^3+5.9x^2-4x+1.9$

对它有

$x_1=-0.204208797318388+1.434374365885898i,$

$x_2=0.987381717771217+0.380829640497317i,$

$x_3=0.216827079547169+0.872454488970128i,$

$x_1+x_2+x_3=0.999999999999998+2.687658495353343i,$

$x_1{x}_2+x_2{x}_3+x_1{x}_3=-2.161754093822501+2.415374376021576i,$

$x_1{x}_2{x}_3=-1.329947367350680-0.362270617186915i$

因此我们可取

$p=-1$, $\alpha =2.6877$, $\beta =-2.4154$

然后逐步算出

$q=\frac{a_2-p^2-{\alpha }^2}{2}=-2.161865645000000$

$r=\frac{a_3}{2}-pq-\alpha \beta =1.330004935000000$

$\gamma =\frac{\frac{a_5}{2}-qr}{\beta }=-0.362379720401158$

$b_4=a_4-q^2-2pr-{\beta }^2-2\alpha \gamma =0.0001255920131197907>0$

$b_6=a_6-r^2-{\gamma }^2=-0.000\text{232188882375528}0$

$b_6+\epsilon =0.099767811117624>0$

因此根据定理2就有

$f\left(x\right)={\left(x^3+p{x}^2+qx+r\right)}^2+{\left(\alpha x^2+\beta x+\gamma \right)}^2+\epsilon x^4+\left(b_4+\epsilon \right)x^2+b_6+\epsilon$

是有理系数多项式的平方和。

在这个例子中，对 $\alpha ,\beta$ 的精度要求只需要四位小数(从第五位小数四舍五入得出)。

注4：本文的方法不适用于系数中含有参数的多项式，也不适用于可以取到0值的非负多项式。本文作者在 [11] 中研究了一个这类多项式，给出了它的非负条件

$\begin{array}{c}g\left(z\right)=z^6+\left(3\mu +1\right)z^5+\left(3{\mu }^2+4\mu +1\right)z^4+\left({\mu }^3+5{\mu }^2+3\mu +1\right)z^{3}3\\ +\left(2{\mu }^3+3{\mu }^2+3\mu +1\right)z^2+\left({\mu }^3+2{\mu }^2+2\mu +1\right)z+{\mu }^2+\mu +1\end{array}$

其中 $\mu \ge 0$。

作者得出了下面的公式

$g\left(z\right)={\left(z^3+\frac{3\mu +1}{2}{z}^2+\left(2\mu +3-\frac{1}{2}\lambda \right)z+\frac{\mu +5}{2}-\frac{1}{2}\lambda \right)}^2+\frac{\text{1}}{\text{4}}\lambda {\left(z+1\right)}^2{\left(z+\mu \right)}^2$

其中

$\lambda =7+2\mu -{\mu }^2$

因此当 $0\le \mu \le 1+\sqrt{8}$ 时 $g\left(z\right)$ 是非负的，其当且仅当 $\mu =1+\sqrt{8}$ 时， $g\left(z\right)$ 有三个不同的二重根。