モーメント問題の解法の数値計算量の削減
11SE225 坂元 悠介
指導教員：杉浦洋

1

はじめに

ak = ak −これより m = U −1 b が計算でき，計算量はき網法を提案した．上岡 [1] はそれを解析関数 f (x) の零点問題に拡張した．巻き網法では零点はモーメント方程式式に変換して Aberth 法で解いた．一方、変換に伴う誤差

aj

j=k+1

村井 [2] は多項式 f (x) の領域内の零点を全て求める巻の解として得られる．村井と上岡はそれを 1 変数代数方程n∑n(n+1)
で22ある．よって高速解法の計算量は O(n ) である．

4

数値実験を避けるために, 山田 [3] はそれを直接多次元 Newton 法

計算途中で発生する丸め誤差が計算過程で拡大伝播せで解いた. しかし，計算量の増大が問題であった．本研究ず，精度のよい計算結果を得る計算法を数値的に安定とでは, モーメント問題の高速解法を考える。高速解法の精いう．拡大伝播して計算結果を破壊する計算法を数値的に度を保障するためにシミュレーションを行う.

不安定という．高速解法は数学的には正しい解を与えるの2で，問題となるのは，数値的安定性である．

モーメント問題

今回の高速解法の数値的安定性を調べるため，数値実験を行った．

改めて，問題を定義する．点 z0 , z1 , . . . , zn ∈ C の質量＜条件数の理論＞

を w0 , w1 , . . . , wn ∈ C とするとき，その i(0 ≤ i ≤ n′ ) 次精度の目安を得るために，V T の条件数 cond（V T ）をモーメントは計算する．ノルムは全て 2-ノルムである．入力誤差をµi =n∑

wj zji (0 ≤ i ≤ n′ )j=0である．逆に，与えられたモーメント µi (0 ≤ i ≤ n′ ) から点の位置や質量を求める問題をモーメント問題という．
モーメント問題は，• 質量問題（質量のみ未知、線形問題 n′ = n）
• 位置問題（位置のみ未知、非線形問題 n′ = n）
• 位置質量問題（両方未知、非線形問題 n′ = 2n + 1）の 3 つに分かれる．今回は，質量問題の解法シミュレーションについて述べる

3．

質量問題のＬＵ分解法と高速解法
LU 分解法と高速解法を説明する。

||∆µ|| = ||µ0 − µ||，出力誤差を ||∆m|| = ||m − m0 || とすると，入出力の相対誤差について||∆µ||||∆m||≤ cond(V T )||µ||||m||が成立する．最悪の場合には等号が成立する．入力相対誤差は，丸め誤差単位 u = 2−53 ∼= 10−16 により||∆m|| ∼=u||m||なので，出力相対誤差は||∆m|| ∼= u cond(V T )||m||と推定される．すなわち，• LU 分 解 法：与 え ら れ た 点 z = z0 , z1 , · · · , zn の||∆m||log10 ()∼=0Vandelmonde 行 列 を V，モ ー メ ン ト ベ ク ト ル を||m||cond(V T )uµ = (µ0 , µ1 , · · · , µn )T とし，質量ベクトルを w =である．この左辺を安定性の指標とする．左辺 ≤ 0 なら(w0 , w1 , · · · , wn )T と す る と ，モ ー メ ン ト 方 程 式 は安定，そうでないなら不安定である．
V T w = µ とベクトル表記される．通常，この方程＜実験方法＞
式は LU 分解法で解かれる．計算量は O(n3 ) である。
＜実験１＞領域 {−r ≤ Re ≤ r} ∩ {−r ≤ Im ≤ r}
• 高速解法：bii = ai (0 ≤ i ≤ n) を初期値として， に配置した z を求める．Vandelmonde 行列の大きさを(i = 1, 2, …, n)(k = n, n − 1, …, i) で，
n = 10, 15, 20, 25, 30 の 5 パターン．r = 1, 10, 100 の 3 パ
ターン．計 15 パターンで計測する．
bk,k−i = bk,k−i+1 − zi−1 bk−1,k−i＜実験 2 ＞ θ を [0, 2π] の一様乱数で定め，領域 {−r ≤n(n+1)
として b = M a が計算でき，計算量はでRe(z) − cos θ ≤ r} ∩ {−r ≤ Im(z) − sin θ ≤ r} に配置2ある．ai = ci (0 ≤ i ≤ n) と初期化して，k = された z を求める．Vandelmonde 行列の大きさを n =(n − 1, n − 2, · · · , 0) で10, 15, 20 の 3 パターン．r = 1, 0.5, 0.25 の 3 パターン．
計 9 パターンで計測する．
aj
aj =(j = k + 1, k + 2, · · · , n)
それぞれ回数 1000 回ループさせ，ランダムシードを 10 に
zj − zk固定して行う．以下の項目で LU 分解法と高速解法を比較

表 4 n = 10, r = 1 のときする．

• 問題の条件数 (最大・最小・平均)5

条件数の常用対数• LU 分解法と高速解法の相対誤差 (最大・最小・平均・分散)

相対誤差

高速解法の常用対数

LU 分解法• 相対誤差/条件数を調べ，精度保障 (最大・最小・平均)

安定性指標高速解法の常用対数

LU 分解法

高速解法の安定性実験の結果を評価し，高速解法が安定であることを述

条件数の常用対数

表 1 n = 10, r = 1 のとき

条件数の常用対数
相対誤差

高速解法の常用対数

LU 分解法

安定性指標

高速解法の常用対数

LU 分解法

最小平均

7.08-9.77
-9.92
0.81
0.01

1.71
-15.0
-14.8
-2.16-2.02

3.56
-13.2
-13.1
-0.84
-0.74

分散0.610.68

相対誤差

高速解法の常用対数

LU 分解法

安定性指標

高速解法の常用対数

LU 分解法条件数の常用対数

相対誤差

高速解法の常用対数

LU 分解法

安定性指標

高速解法の常用対数

LU 分解法

24.3-9.92
-9.70
-15.7
-15.4

19.4
-14.9
-15.1
-20.1
-20.2

21.2-13.2-13.1-18.4-18.3

7.44-10.3-10.1-1.80-1.61

0.71
0.71

最大最小平均15.0-2.58-1.85-0.32-0.15

10.0-7.35-7.71-2.45-2.63

11.7-5.38-5.22-1.15-0.99

分散0.620.61

表 6 n = 20, r = 1 のとき

表 2 n = 10, r = 100 のとき

条件数の常用対数

5.17-12.8-12.6-3.33-3.49められる．

果と比較する．

平均

12.0-6.63
-6.24
-0.55
-0.46

分散同等の精度を得た．条件数が小さければよい精度の解を求分解法と同等の精度を得た．この結果を基準として他の結最小平均n = 10, r = 0.25 では，安定性は保障され，LU 分解とn = 10，r = 1 での高速解法の安定性は保障され，LU

最大最小表 5 n = 10, r = 0.25 のときべる．

最大最大分散0.590.69

相対誤差

高速解法の常用対数

LU 分解法

安定性指標

高速解法の常用対数

LU 分解法

最大最小平均

19.9
0.62
-0.06
-1.71
-1.60

12.0
-6.70
-6.74
-4.89
-4.71

15.3
-3.77
-3.57
-3.19
-2.99

分散

1.34
1.32

n = 20, r = 0.25 では，LU 分解法は安定性が保障され，我々の高速解法は安全性が保障されなかった．相対誤差も

n = 10，r = 100 では，安定性は保障され，LU 分解法

LU 分解法より明らかに悪い結果を得た．

おわりにと同等の精度は得た．よって一様乱数を変化させても精度6を保障できる．

本研究では，発見した高速解法と LU 分解法を比較し，LU 分解法とほぼ同等の精度の結果を得ることができた．

表 3 n = 30, r = 1 のとき

条件数の常用対数
相対誤差

高速解法の常用対数

LU 分解法

安定性指標

高速解法の常用対数

LU 分解法

今後の課題として一様乱数で生成された問題以外でも精度

最大

最小

平均

15.2
-2.59-1.79
-0.16
-0.20

6.27-10.8-10.5-3.77-3.68

10.2-7.22-7.08-1.45-1.32

分散

参考文献
2.14
2.23

n = 30, r = 1 では，安定性は保障され，LU 分解法と同等の精度を得た．よって行列の大きさを変化させても精度が保障できる．

n = 10, r = 1 では，安定性は保障され，LU 分解法と同等の精度を得た．この結果を基準として，他の結果と比較する．

が保障できるのかを実験し，確認する．

[1] 上岡航平：複素周回積分による解析関数の因数分解，南山大学数理情報システム数理学科 2012 年度卒業論文(2013)．
[2] 村井智：複素関数による多項式の因数分解，南山大学
数理情報システム数理学科 2011 年度卒業論文 (2011)．
[3] 山田ひかる：複素周回積分による非線形方程式の解法，
南山大学数理情報システム数理学科 2012 年度卒業論
文 (2013)．