多項式の係数と根のべき乗和との関係【ニュートンの恒等式】のPythonプログラム

多項式の係数と根のべき乗和との関係【ニュートンの恒等式】のPythonプログラム

ニュートンの恒等式(Newton’s identities)はべき乗和と基本対称式に関する恒等式です。

その関係式を用いることで、根のべき乗和から多項式の係数を求めることができ、さらにそれを解くことで多項式の根が得られます。

今回は、ニュートンの恒等式を用いて根のべき乗和から多項式の係数とその根を求めるPythonプログラムを紹介します。

ニュートンの恒等式とは?

\(n\)次多項式の場合

\(n\)次の多項式\(f(x)\)を考えます。

$$ f(x) = x^n + a_1 x^{n-1} + a_2 x^{n-2} +\cdots + a_{n-1}x + a_n $$

この多項式の根を\(x_1,x_2,\cdots,x_n\)とします。すると、『解と係数の関係』より多項式の係数\(a_1, a_2, \cdots, a_n\)は\(k\)次の基本対称式\( \ e_k(x_1,x_2,\cdots,x_n) \ (k=0,1,2,\cdots,n) \ \)を用いて表現でき、以下のように表せます。

$$ f(x) = x^n – e_1 x^{n-1} + e_2 x^{n-2} + \cdots + (-1)^{n-1}e_{n-1}x + (-1)^n e_n $$

基本対称式\( \ e_k(x_1,x_2,\cdots,x_n) \ (k=0,1,2,\cdots,n) \ \)は多項式の根を\(x_1,x_2,\cdots,x_n\)を用いて、次のような式となります。

$$ \begin{eqnarray}
e_0(x_1,x_2,\cdots,x_n) &=& 1 \\
e_1(x_1,x_2,\cdots,x_n) &=& x_1 + x_2 + \cdots + x_n \\
e_2(x_1,x_2,\cdots,x_n) &=& \sum_{1 \leq i < j \leq n}x_i x_j \\
\cdots \\
e_n(x_1,x_2,\cdots,x_n) &=& x_1 x_2 \cdots x_n \\
\end{eqnarray} $$

ここで、\( k \geq 1\)として根の\(k\)次のべき乗和\( \ p_k(x_1,x_2,\cdots,x_n) \ \)を考えます。

$$ \begin{eqnarray}
p_k(x_1,x_2,\cdots,x_n) &=& \sum_{i=1}^n x_i^k \\
&=& x_1^k + x_2^k + \cdots + x_n^k
\end{eqnarray} $$

ニュートンの恒等式は根のべき乗和\( \ p_k(x_1,x_2,\cdots,x_n) \ \)と基本対称式\( \ e_k(x_1,x_2,\cdots,x_n) \ (k=0,1,2,\cdots,n) \ \)について次のような等式が成立するというものです。

$$ ke_k(x_1,x_2,\cdots,x_n) = \sum_{i=1}^k (-1)^{i-1} e_{k-i}(x_1,x_2,\cdots,x_n) p_i(x_1,x_2,\cdots,x_n)$$

具体例(3次多項式の場合)

具体的に、3次多項式の場合におけるニュートン恒等式の導出を以下で行います。

$$ f(x) = x^3 +a_1 x^2 + a_2 x + a_3 $$

この多項式の根を\( x_1, x_2, x_3\)とすると、3次多項式の解と係数の関係より、基本対称式と係数の間に次式が成り立ちます。

$$ \begin{eqnarray}
e_1 &=& x_1 + x_2 + x_3 = -a_1 \\
e_2 &=& x_1 x_2 + x_2 x_3 + x_3 x_1= a_2 \\
e_3 &=& x_1 x_2 x_3 = -a_3
\end{eqnarray} $$

まず、1次のべき乗和と基本対称式はそのまま、

$$ p_1 = x_1 + x_2 + x_3 = e_1 = -a_1 \tag{1}$$

となります。

続いて2次のべき乗和と基本対称式を求めるには、「2次多項式のべき乗和と基本対称式の関係」を使って、以下のように導出します。

$$ \begin{eqnarray}
x_1^2 + x_2^2 &=& (x_1+x_2)^2 – 2x_1 x_2 \\
x_2^2 + x_3^2 &=& (x_2+x_3)^2 – 2x_2 x_3 \\
x_3^2 + x_1^2 &=& (x_3+x_1)^2 – 2x_3 x_1 \\
\end{eqnarray} $$

上式の右辺、左辺どうしを足し合わせて少し計算すると次のようになります。

$$ x_1^2+ x_2^2 + x_3^2 = ( x_1 + x_2 + x_3)^2 -2 (x_1x_2+x_2x_3+x_3x_1) $$

よって、

$$ \begin{eqnarray}
p_2 &=& p_1^2 -2 e_2 \\
&=& e_1^2-2e_2 \tag{2} \\
&=& a_1^2 – 2a_2
\end{eqnarray} $$

最後に、3次のべき乗和と基本対称式は次のように求めます。

多項式\(f(x)\)の根が\(x_1,x_2,x_3\)なので、それらを代入すると0となるので、

$$ \begin{eqnarray}
f(x_1) &=& x_1^3 +a_1 x_1^2 + a_2 x_1 + a_3 =0 \\
f(x_2) &=& x_2^3 +a_1 x_2^2 + a_2 x_2 + a_3 =0 \\
f(x_3) &=& x_3^3 +a_1 x_3^2 + a_2 x_3 + a_3 =0 \\
\end{eqnarray} $$

という式が成り立ちます。これらの辺々を足し合わせると

$$(x_1^3+x_2^3+x_3^3)+a_1(x_1^2+x_2^2+x_3^2)+a_2(x_1+x_2+x_3) +3a_3 = 0 $$

$$p_3+a_1p_2+a_2p_1+3a_3 = 0 $$

となるので、

$$ \begin{eqnarray}
p_3 &=& e_1^3 -3e_1 e_2 + 3e_3 \tag{3} \\
&=& -a_1^3 + 3a_1 a_2 -3 a_3
\end{eqnarray} $$

式(1),(2),(3)を整理すれば、

$$ \begin{eqnarray}
e_1 &=& p_1 \\
2e_2 &=& e_1p_1-p_2 = p_1^2 – p_2 \\
3e_3 &=& e_2p_1 -e_1p_2+p_3 = \tfrac{1}{2}p_1^3 -\tfrac{3}{2}p_1p_2+p_3
\end{eqnarray} $$

となり、3次多項式の場合のニュートンの恒等式を導くことができました。

Pythonコード

以下のPythonプログラムでは、最初に多項式の根を与えてそのべき乗和を計算し、ニュートンの恒等式を適用して多項式の係数を求め、その方程式の解を求めています。

上手く動いてくれれば、最初に入力した根と方程式を解いて得られた根が一致するはずです。

根として\([1,-1,0,2] \)を入力しています。

import numpy as np

# 根
roots = [1,-1,0,2]  # 解を入力
n = len(roots)  # 多項式の次数

# べき乗和(ニュートン多項式) [0乗和、1乗和、2乗和・・・]
p = [n]
for i in range(1,n+1):  # 1 ~ n
    p.append(sum([rt**i for rt in roots]))


# 対称式のリスト
e = [0]*(n+1)
e[0] = 1  # e0 = 1

# 多項式の係数のリスト
poly = [1]  # 最高次の係数は1 

# ニュートンの恒等式を適用する
for k in range(1,n+1):
    for i in range(1,k+1):
        e[k] += (-1)**(i-1) * e[k-i] * p[i]
    e[k] /= k
    poly.append((-1)**k * e[k])  # 解と係数の関係を利用して、対称式 -> 係数に変換

f = np.poly1d(poly)  # ニュートンの恒等式から求めた係数を持つ多項式を作る
print(f.r)  # 根を得る

出力結果は次のようになります。

[-1.  2.  1.  0.]

ちゃんと入力した根と同じ結果が得られました。

関連記事
ガウス求積で数値積分を行う-Pythonプログラム
ニュートン法で関数のすべての複素根を求める-Pythonプログラム