項順序

出典: フリー百科事典『ウィキペディア（Wikipedia）』

項順序（こうじゅんじょ、term order）とは、単項式に対し定義され、多変数の多項式環全体で通用する全順序の総称である。単項式順序（たんこうしきじゅんじょ、monomial order）ともいう。

体上の一変数多項式におけるユークリッドの互除法や、多変数の連立線形方程式系にけるガウスの消去法は、多項式の割算のアルゴリズムであり、環論の言葉で言えば、多項式環のイデアルに対し、そのイデアルを生成する既約多項式の組を探し出す手続きを示している。

このような割算のアルゴリズムを拡張し、割算アルゴリズムを定式化するために項順序を導入することは有用である。また、このような多項式の割算アルゴリズムを含むアルゴリズムにブッフバーガーアルゴリズムがあり、多項式環のイデアルの基底としてグレブナー基底とよばれる素性の良いものが取れることが知られている。

[編集] 定義

体 K 上の n 変数多項式環 R = K[x₁, ..., x_n] を考える. R の係数 1 の単項式 を項（こう、term）と呼ぶ。項全体からなる集合

$T = \{ x_1^{i_1} x_2^{i_2}\cdots x_n^{i_n} \mid (i_1,i_2,\ldots,i_n) \in \mathbb{N}^n \}$

（ただし、N には 0 を含む）における順序 ≤ が次の条件をみたすとき項順序であるという；

≤ は全順序である。
1 ≤ t if t ∈ T。
t₁ ≤ t₂ ⇒ st₁ ≤ st₂ if t₁, t₂, s ∈ T。

記述の簡素化のために、項 $x_1^{i_1} x_2^{i_2}\cdots x_n^{i_n}$ を多重指数（たじゅうしすう、multi-index） α = (i₁, ..., i_n) を用いて x^α などとあらわすことがある。このとき、α を x の指数ベクトル（または単に指数）と呼ぶ。指数ベクトルの全体 E = Nⁿ は α ↔ x^α により T と一対一に対応するから、項順序は次のようにも定義できる。

指数ベクトルの集合 E における順序 ≤ が定まっていて

≤ は E の全順序である。
(0, 0, ..., 0) ≤ α if α ≤ E。
α ≤ β ⇒ α + γ ≤ β + γ if α, β, γ ∈ E。

が満たされるとき、≤ は E の項順序であるという。

[編集] 先頭項

R に項順序 ≤ を一つ決めておく。多項式 f ∈ R が

f = c₁t₁ + c₂t₂ + … + c_kt_k (t₁ > t₂ > … > t_k)

と表されているとき、

t₁ を f の先頭項（せんとうこう、leading term）と呼び、LT_≤(f) などであらわす。
c₁ を f の先頭係数（せんとうけいすう、leading coefficient）と呼び、LC_≤(f) などであらわす。
c₁t₁ を f の先頭単項式（せんとうたんこうしき、leading monominal）と呼び、LM_≤(f) などであらわす。

leading の代わりに、initial とか head をつかって、head term などのようにも呼ぶ。入れている項順序が明らかなときは ≤ を省略して単に LT(f) などのように書く。

[編集] 項順序の例

[編集] 辞書式順序

E における順序 ≤_lex を

(i₁, ..., i_n) <_lex (j₁, ..., j_n)

⇔ ある k (1 ≤ k ≤ n) が存在して i₁ = j₁, i₂ = j₂, ..., i_k-1 = j_k-1 かつ i_k < j_k

により定義すると ≤_lex は項順序になる。これを E における辞書式順序（じしょしきじゅんじょ）という。lex は lexicographic order から。

辞書式順序は消去法の一般化に向いている。（らしい）

[編集] 全次数辞書式順序

E における順序 ≤_glex を

(i₁, ..., i_n) <_glex (j₁, ..., j_n)

⇔ i₁ + i₂ + …+ i_n < j₁ + j₂ + …+ j_n

または

i₁ + i₂ + …+ i_n = j₁ + j₂ + …+ j_n かつ

ある k (1 ≤ k ≤ n) が存在して i₁ = j₁, i₂ = j₂, ..., i_k-1 = j_k-1 かつ i_k < j_k

により定義すると ≤_glex は項順序になる。これを E における全次数辞書式順序（ぜんじすうじしょしきじゅんじょ）という。glex は　graded lexicographic order から。

[編集] 全次数逆辞書式順序

E における順序 ≤_drl を

(i₁, ..., i_n) <_drl (j₁, ..., j_n)

⇔ i₁ + i₂ + …+ i_n < j₁ + j₂ + …+ j_n

または

i₁ + i₂ + …+ i_n = j₁ + j₂ + …+ j_n かつ

ある k (1 ≤ k ≤ n) が存在して i_n = j_n, i_n-1 = j_n-1, ..., i_k+1 = j_k+1 かつ i_k > j_k

により定義すると ≤_drl は項順序になる。これを E における全次数逆辞書式順序（ぜんじすうぎゃくじしょしきじゅんじょ）という。drl は total degree revers lexicographic order から。

全次数逆辞書式順序は高速なグレブナー基底計算に向いている（らしい）。

[編集] 関連項目

行列順序 (matrix order)

この項目「項順序」は、自然科学に関連した書きかけの項目です。加筆・訂正などをして下さる協力者を求めています。

"http://ja.wikipedia.org../../../%E9%A0%85/%E9%A0%86/%E5%BA%8F/%E9%A0%85%E9%A0%86%E5%BA%8F.html" より作成

カテゴリ: 自然科学関連のスタブ項目 | 順序構造

See also ebooksgratis.com: no banners, no cookies, totally FREE.

項順序