早稲田大学大学院基幹理工学研究科

九州大学学術情報リポジトリ

Kyushu University Institutional Repository

解の複雑度による4近傍max方程式およびセルオート マトンのクラス判定

小俣, 亮

早稲田大学大学院基幹理工学研究科

高橋, 大輔

早稲田大学大学院基幹理工学研究科

https://doi.org/10.15017/1957517

出版情報：応用力学研究所研究集会報告. 29AO-S7 (1), pp.107-112, 2018-03. 九州大学応用力学研究所 バージョン：

権利関係：

応用力学研究所研究集会報告 No.29AO-S7

「非線形波動研究の新潮流―理論とその応用―」

Reports of RIAM Symposium No.29AO-S7

New trends in nonlinear waves - theory and applications -

Proceedings of a symposium held at Chikushi Campus, Kyushu University, Kasuga, Fukuoka, Japan, November 9 - November 11, 2017

Research Institute for Applied Mechanics Article No. 16 (pp. 107 - 112)

解の複雑度による 4 ^近傍 max ^方程式 およびセルオートマトンのクラス判定

小俣 亮（ OMATA Ryo ），高橋 大輔（ TAKAHASHI daisuke ）

（ Received 9 January 2018; Accepted 8 March 2018 ）

解の複雑度による 4 近傍 max 方程式およびセルオートマトンのクラス判定

早稲田大学大学院基幹理工学研究科 小俣 亮(OMATA Ryo)

早稲田大学大学院基幹理工学研究科 高橋 大輔(TAKAHASHI Daisuke)

概要

時間1階空間4近傍のmax方程式およびそれに付随するCAの初期値問題を考え，解の複雑度と いう視点から方程式の分類を行う[1]．本研究では時間発展則がある単純な形式に従う4近傍の方 程式に対してこの解析を試みた．

1 準備

本節ではmax方程式において用いられる演算に関する公式，解析の対象とする4近傍の方程式 の形式，方程式をクラス分けするための解の複雑度について説明する．

1.1 min, max 演算の公式

本研究で扱うmax方程式は実変数に対するmax, min演算と∗の演算で構成されるものとし，記 号を簡略化するためx=−xと表す．これら演算から得られる基本公式は以下のものがある．

• min(x, y) = min(y, x), max(x, y) = max(y, x)

• min(x,min(y, z)) = min(min(x, y), z) = min(x, y, z), max(x,max(y, z)) = max(max(x, y), z) = max(x, y, z)

• min(x, y) +z= min(x+z, y+z), max(x, y) +z= max(x+z, y+z)

• min(x, x) =x, max(x, x) =x

• min(x,max(x, y)) =x, max(x,min(x, y)) =x

• min(x,max(y, z)) = max(min(x, y),min(x, z)), max(x,min(y, z)) = min(max(x, y),max(x, z))

• min(x, y) = max(x, y), max(x, y) = min(x, y)

• x=x

なお演算xについては，実数の大小の順序を逆にする他の操作に置き換えても同じ公式が成立す る．x= 1−xとし，x,y,z∈ {0,1}と変数の値域を仮定すると，

x= NOTx, min(x, y) =xANDy, max(x, y) =xORy

と2進演算に置き換えても差し支えない．このときmax方程式を2進のブール演算で構成するこ とも可能である．

1

1.2 本研究で対象とする 4 近傍 max 方程式の形式

今回は4近傍のmax方程式の中で，以下のような形式に従う方程式のみを対象にする．

uⁿ⁺¹_j =f(uⁿ_j−2, uⁿ_j−1, uⁿ_j+1) (j：位置,n：時刻, u：状態) (1) 標準の4近傍方程式はuⁿ⁺¹_j =f(uⁿ_j−2, uⁿ_j−1, uⁿ_j, uⁿ_j+1)の形をとるが，上式はuⁿ⁺¹_j の値がuⁿ_j に依 存しない．また(1)の右辺の関数f(uⁿ_j−2, uⁿ_j−1, uⁿ_j+1)にはさらに制限を設け，

uⁿ_j−2かuⁿ_j−2, uⁿ_j−1かuⁿ_j−1,uⁿ_j+1かuⁿ_j+1がいずれも一度まで登場し，それらをmin, max演算で結びつけた形

に限定する．たとえば次式はこの制限に従うmax方程式である．

uⁿ⁺¹_j = min(uⁿ_j−2, uⁿ_j−1, uⁿ_j+1) (2) ブール束の場合は表1の2進表で時間発展を定義できる．図1に(2)の時間発展を示す．

uⁿ_j−2uⁿ_j−1∗uⁿ_j+1 11∗1 11∗0 10∗1 10∗0 01∗1 01∗0 00∗1 00∗0

uⁿ⁺¹_j 0 0 0 0 0 1 0 0

表1：ブール束での(2)の時間発展則

図1: (2)の時間発展：左がR，右がブール束

1.3 解の複雑度を表すクラス P

時刻nに対して，初期値で表した一般解に含まれる初期値の項数や演算数をO(n^k)まで減らす ことができるような方程式のクラスをPkと定義する．Pkは解ひいては方程式の複雑度の反映で あり，これによって方程式を分類する．例として以下に2つの方程式を挙げる．

（例1）uⁿ⁺¹_j = min(uⁿ_j−2, uⁿ_j−1, uⁿ_j+1)の解はuⁿ_j = min(u⁰_j−n−1, u⁰_j−n, u⁰_j−n+2) (n≥1)である．

よってクラスP0である．

（例2）uⁿ⁺¹_j = min(uⁿ_j−2, uⁿ_j−1, uⁿ_j+1)の解はuⁿ_j = min(u⁰_j−2n, . . . , u⁰_j−n, u⁰_j−2n+3, . . . , u⁰_j−n+2)であ る．よってクラスP1である．

なお，一般解に含まれる初期値の項数や演算数を最小オーダーまで減らしたときにクラスを定義す べきであるが，最小オーダーであることの証明が必要となる．たとえば例2の解はさらにP0まで

2 ^{クラス分け}

2.1 クラス判定

本節では記号を簡略化するため,uⁿ_j−2=a,uⁿ_j−1=b,uⁿ_j+1=dとおき, (1)の右辺をf(a, b, d)と 表すことにする. (1)の形式のうち，クラスを（暫定的に）定めることのできた方程式の右辺の関 数f(a, b, d)を以下に列挙する．

クラスP0

min(a, b, d), min(a, b, d), min(a, b, d),

min(max(a, b), d), min(a,max(b, d)), min(max(a, d), b) クラスP₁

min(a, b, d), min(a, b, d), min(a, b, d), min(a, b, d) クラスP2

min(max(a, b), d), max(min(a, b), d), min(a,max(b, d))

なお，変換により等価になる方程式の組については，そのうちのひとつのみを取り上げている．た とえば

z= min(max(a, b), d)

という関係を考え，すべての変数をz=z^′, a=a^′, b=b^′,d=d^′と変換する．すると

z^′= min(max(a^′, b^′), d^′) となるが，両辺にxを作用すると

z^′= max(min(a^′, b^′), d^′)

となり，元の関係式のminとmaxをそれぞれmax, minに置き換えたものとなる．この例のよう にminとmaxの演算を交換することで等価な方程式が得られる．なお，座標の左右反転の変換に ついては，今回対象とする方程式がj−2,j−1,j+ 1に依存する形式を考えているため，等価な 方程式は一般には対象外の形式になる．

2.2 数学的帰納法によるクラスの証明例

以下の2つの式について，具体的に解の証明を行う．

【例1】

方程式: uⁿ⁺¹_j = min(uⁿ_j−2, uⁿ_j−1, uⁿ_j+1)

解: uⁿ_j = min(u_j−2n, u_j−2n+1, . . . , u_j−n, u_j−2n+3, u_j−2n+4, . . . , u_j−n+2)

3

上の解の表現では初期値u⁰_jの上付き添え字0を省略している．解よりクラスP1であることがわ かる．この解が確かに解であることの証明は以下の通り．

uⁿ⁺¹_j = min(uⁿ_j−2, uⁿ_j−1, uⁿ_j+1)

= min( min(uj−2n−2, . . . , uj−n−2, uj−2n+1, . . . , uj−n), min(uj−2n−1, . . . , uj−n−1, uj−2n+2, . . . , uj−n+1), max(uj−2n+1, . . . , uj−n+2, uj−2n+4, . . . , uj−n+3))

= min(uj−2n−2, . . . , uj−n−1, uj−2n+1, . . . , uj−n+1, max(uj−2n+1, . . . , uj−n+2, uj−2n+4, . . . , uj−n+3))

= min(uj−2n−2, . . . , uj−n−1, uj−2n+1, . . . , uj−n+1)

= min(uj−2(n+1), . . . , uj−(n+1), uj−2(n+1)+3, . . . , uj−(n+1)+2)

【例2】

方程式: uⁿ⁺¹_j = min(uⁿ_j−2,max(uⁿ_j−1, uⁿ_j+1))

解: uⁿ_j = min( max(u_j−n+2, u_j−n+1, . . . , u_j−2n+4, u_j−2n+3, u_j−n), max(u_j−n+1, u_j−n, . . . , u_j−2n+4, u_j−2n+3, u_j−n−1), . . . ,

max(u_j−2n+5, u_j−2n+4, u_j−2n+3, u_j−2n+3), max(uj−2n+4, uj−2n+3, uj−2n+2),

max(uj−2n+3, uj−2n+1), uj−2n)

解よりクラスP2であることがわかる．この解が確かに解であることの証明は以下の通り．

uⁿ⁺¹_j = min(uⁿ_j−2,max(uⁿ_j−1, uⁿ_j+1))

= min(max(uj−n, . . . , uj−2n+1, uj−n−2), . . . ,max(uj−2n+2, uj−2n+1, uj−2n), max(uj−2n+1, uj−2n−1), uj−2n−2,

max(min(max(uj−n+1, . . . , uj−2n+2, uj−n−1), . . . ,max(uj−2n+3, uj−2n+2, uj−2n+1), max(uj−2n+2, uj−2n), uj−2n−1),

min(uj−n+3, . . . , uj−2n+4, uj−n+1), . . . ,min(uj−2n+5, uj−2n+4, uj−2n+3), min(uj−2n+4, uj−2n+2), uj−2n+1))

= min(max(uj−n, . . . , uj−2n+1, uj−n−2), . . . ,max(uj−2n+2, uj−2n+1, uj−2n), max(uj−2n+1, uj−2n−1), uj−2n−2,

max(max(u_j−n+1, . . . , u_j−2n+2, u_j−n−1), u_j−2n+1,

min(u_j−n+3, . . . , u_j−2n+4, u_j−n+1), . . . ,min(u_j−2n+5, u_j−2n+4, u_j−2n+3), min(u_j−2n+4, u_j−2n+2)))

= min(max(u_j−n+1, . . . , u_j−2n+2, u_j−2n+1, u_j−n−1),

max(u_j−n, . . . , u_j−2n+1, u_j−n−2), . . . ,max(u_j−2n+2, u_j−2n+1, u_j−2n)

この証明は複雑であり詳細は省略するが，上式の等式の前後で同じ色の下線が付いている部分は同 じであり，最終的に赤と青の下線部のみ残る．

ブール束ではその2値性により，1.1節の公式に加えてmax(a, a) = 1, min(a, a) = 0という公式 もさらに用いることが可能で，解は次式に簡約化され,クラスP₀相当の複雑度になる．

uⁿ_j = min(max(uj−2n+4, uj−2n+3, uj−2n+2),max(uj−2n+3, uj−2n+1), uj−2n)

3 2 種の波動が混在する方程式

(1)の形式に従う4近傍max方程式の中で，それに付随するブール束のCAが3近傍では見ら れない時間発展をするものがある．そのような例として次式が挙げられる．

uⁿ⁺¹_j = min(uⁿ_j−2,max(uⁿ_j−1, uⁿ_j+1)) (3) この式に付随するCAの時間発展を図2に示す．

図2: ブール束での(3)の時間発展

このmax方程式には図3のような速さ1の波と図4のような速さ1/2の波が安定に存在する．図2 ではこの2種類の波が混在する結果が見られ，3近傍では見られない解が存在する．

図3: 速さ1の波 図4: 速さ1/2の波

5

4 ^{今後の課題}

今後の課題としては，以下のようなものが挙げられる．

• (3)のような3近傍では見られない解を持つ方程式についてクラスを定めたい．

• より広い範囲の4近傍方程式についてクラス分けを行いたい．

• 任意の方程式について厳密なクラスの同定を行いたい．すなわち解の複雑度がO(n^k)である とき，kよりも小さい値を取り得ないことを証明したい．

• ソリトン解のプリュッカー関係式のような汎用の公式を利用する解の証明を行いたい．

• max方程式と解はR上の束に関する演算で構成されているが，この結果はより一般の束に ついても適用できる[2]．これら知見の応用を行いたい．

参考文献

[1] T.Ikegami, D.Takahashi, J.Matsukidaira, “On solutions to evolution equations defined by lattice operators”, Japan J. Indust. Appl. Math.31(2014) 211-230.

[2] 安藤卓哉，高橋大輔, “束方程式の解の挙動について”,日本応用数理学会2016年度年会