Q&A
回答頂きありがとうございます。
apacheでの計算がかなり正確であるようだということが知れ、誤差の原因もなんとなくわかりました。
正規化していないベクトルを知りたかった理由は、ベクトルの成分が０に近かったところ、正規化することで０から離れ、０と１の区別する方法が思いつかなかったからです。ちなみに、固有値が０の固有ベクトルの成分には正規化しなければ０と１しか出てこないはずです。
言葉足らずなところがあり、すみません。
###前提
初めて、質問させていただきますport_sanです。
隣接行列の中に含まれる非連結グラフの行番号を調べるためにjava8でラプラシアンの固有値と固有ベクトルをapache commons mathのバージョン３.６.１を用いて計算したのですが、ラプラシアン行列が
{{1,-1,0,0,0,0,0,0,0}, {-1,3,0,0,-1,0,0,0,-1}, {0,0,0,0,0,0,0,0,0}, {0,0,0,1,0,0,-1,0,0}, {0,-1,0,0,2,-1,0,0,0}, {0,0,0,0,-1,2,-1,0,0}, {0,0,0,-1,0,-1,3,-1,0}, {0,0,0,0,0,0,-1,1,0}, {0,-1,0,0,0,0,0,0,1}}
ラプラシアン行列固有値、ベクトルの検算に使用したサイト(wolfram alpha)
の時、上記のサイトで固有ベクトルの成分が０になるところが私が書いたプログラムではなりませんでした。
###実現したいこと
ラプラシアン行列の固有値が０の時の固有ベクトルの成分が、正規化前が０か１だったのかの判定を行うにはどのようにすればいいでしょうか。
よろしくお願いします。
###該当のソースコード
java
1import org.apache.commons.math3.linear.EigenDecomposition; 2import org.apache.commons.math3.linear.MatrixUtils; 3import org.apache.commons.math3.linear.RealMatrix; 4import org.apache.commons.math3.linear.RealVector; 5 6public class ApacheCommonsMathMartixTest { 7 8 public static void main(String[] args) { 9 test(); 10 } 11 12 public static void test() { 13 double[][] d = {{1,-1,0,0,0,0,0,0,0}, 14 {-1,3,0,0,-1,0,0,0,-1}, 15 {0,0,0,0,0,0,0,0,0}, 16 {0,0,0,1,0,0,-1,0,0}, 17 {0,-1,0,0,2,-1,0,0,0}, 18 {0,0,0,0,-1,2,-1,0,0}, 19 {0,0,0,-1,0,-1,3,-1,0}, 20 {0,0,0,0,0,0,-1,1,0}, 21 {0,-1,0,0,0,0,0,0,1}}; 22 RealMatrix l = MatrixUtils.createRealMatrix(d); 23 EigenDecomposition ed = new EigenDecomposition(l); 24 double eig[] = ed.getRealEigenvalues(); 25 for (int i = 0; i < eig.length; i++) { 26 RealVector rv = ed.getEigenvector(i); 27 System.out.printf("固有値 : %f, 固有ベクトル : %s\n", 28 eig[i] , rv.toString()); 29 } 30 } 31}
##実行結果
固有値 : 4.342923, 固有ベクトル : {0.16065758; -0.5370659325; 0; -0.16065758; 0.3999230778; -0.3999230778; 0.5370659325; -0.16065758; 0.16065758} 固有値 : 4.000000, 固有ベクトル : {-0.2041241452; 0.6123724357; 0; -0.2041241452; -0.2041241452; -0.2041241452; 0.6123724357; -0.2041241452; -0.2041241452} 固有値 : 2.470683, 固有ベクトル : {-0.2051288855; 0.3016796508; 0; 0.2051288855; 0.569941812; -0.569941812; -0.3016796508; 0.2051288855; -0.2051288855} 固有値 : 1.000000, 固有ベクトル : {-0.6194524332; 0; 0; 0.3091611877; -0.0503590556; -0.0503590556; 0; -0.2588021321; 0.6698114888} 固有値 : 1.000000, 固有ベクトル : {0.3717392698; -0; 0; 0.3284343818; -0.5720454059; -0.5720454059; 0; 0.2436110241; 0.2003061361} 固有値 : 1.000000, 固有ベクトル : {0.2478344844; 0; -0; 0.6163469398; 0.0596770677; 0.0596770677; 0; -0.6760240075; -0.3075115521} 固有値 : 0.186393, 固有ベクトル : {0.4267449852; 0.3472024949; 0; -0.4267449852; 0.1234012271; -0.1234012271; -0.3472024949; -0.4267449852; 0.4267449852} 固有値 : 0.000000, 固有ベクトル : {-0.3524973751; -0.3524973751; 0.0772321473; -0.3524973751; -0.3524973751; -0.3524973751; -0.3524973751; -0.3524973751; -0.3524973751} 固有値 : -0.000000, 固有ベクトル : {0.0273056875; 0.0273056875; 0.997013137; 0.0273056875; 0.0273056875; 0.0273056875; 0.0273056875; 0.0273056875; 0.0273056875}
回答2件
0
自己解決
Jacobi法を自分で実装することにしました。
回答下さった方、ありがとうございます。
投稿2016/10/02 11:36
総合スコア12
0
あまり参考にならないかも知れませんが…
固有値を求めるには漸化式を用いた反復計算により有限回で計算を打ち切るしかないというような論文を見かけたので、きっと違いは近似値計算する上で打ち切り誤差とか計算方式の違いによる誤差なんだろうと思いました。その辺りは素人にはわかりませんが「Ax = λx」の解であるということをふまえてapacheと検算サイトを素朴に比較するのはできるかも知れないと思いやってみました。固有値と固有ベクトルについてどのくらい違うのかや、そもそもの方程式に当てはめたとき「Ax - λx = 0」になるかといったことを計算してみると次のようになりました。
[ 1] lambda = 4.342920 : ev = 1.000000, -3.342920, 0.000000, -1.000000, 2.489290, -2.489290, 3.342920, -1.000000, 1.000000 check = -0.000000, -0.000016, 0.000000, 0.000000, 0.000003, -0.000003, 0.000016, 0.000000, -0.000000 lambda = 4.342923 : ev = 0.160658, -0.537066, 0.000000, -0.160658, 0.399923, -0.399923, 0.537066, -0.160658, 0.160658 dot product = 1.000000 check = 0.000000, -0.000000, 0.000000, -0.000000, 0.000000, -0.000000, 0.000000, -0.000000, 0.000000 lambda = 4.342923 : ev = -0.160658, 0.537066, 0.000000, 0.160658, -0.399923, 0.399923, -0.537066, 0.160658, -0.160658 dot product = -1.000000 check = -0.000000, -0.000000, 0.000000, 0.000000, -0.000000, 0.000000, 0.000000, 0.000000, -0.000000 ...途中省略 [ 7] lambda = 0.186393 : ev = 1.000000, 0.813607, 0.000000, -1.000000, 0.289169, -0.289169, -0.813607, -1.000000, 1.000000 check = 0.000000, 0.000001, 0.000000, -0.000000, 0.000001, -0.000001, -0.000001, -0.000000, 0.000000 lambda = 0.186393 : ev = 0.426745, 0.347202, 0.000000, -0.426745, 0.123401, -0.123401, -0.347202, -0.426745, 0.426745 dot product = 1.000000 check = 0.000000, 0.000000, 0.000000, -0.000000, 0.000000, -0.000000, -0.000000, -0.000000, 0.000000 lambda = 0.186393 : ev = 0.426745, 0.347202, 0.000000, -0.426745, 0.123401, -0.123401, -0.347202, -0.426745, 0.426745 dot product = 1.000000 check = 0.000000, -0.000000, 0.000000, -0.000000, 0.000000, -0.000000, 0.000000, -0.000000, 0.000000 [ 8] lambda = 0.000000 : ev = 1.000000, 1.000000, 0.000000, 1.000000, 1.000000, 1.000000, 1.000000, 1.000000, 1.000000 check = 0.000000, 0.000000, 0.000000, 0.000000, 0.000000, 0.000000, 0.000000, 0.000000, 0.000000 lambda = 0.000000 : ev = -0.352497, -0.352497, 0.077232, -0.352497, -0.352497, -0.352497, -0.352497, -0.352497, -0.352497 dot product = -0.997013 check = 0.000000, 0.000000, 0.000000, 0.000000, 0.000000, 0.000000, 0.000000, 0.000000, 0.000000 lambda = 0.000000 : ev = 0.353553, 0.353553, 0.000000, 0.353553, 0.353553, 0.353553, 0.353553, 0.353553, 0.353553 dot product = 1.000000 check = -0.000000, 0.000000, 0.000000, 0.000000, 0.000000, -0.000000, -0.000000, 0.000000, -0.000000 [ 9] lambda = 0.000000 : ev = 0.000000, 0.000000, 1.000000, 0.000000, 0.000000, 0.000000, 0.000000, 0.000000, 0.000000 check = 0.000000, 0.000000, 0.000000, 0.000000, 0.000000, 0.000000, 0.000000, 0.000000, 0.000000 lambda = -0.000000 : ev = 0.027306, 0.027306, 0.997013, 0.027306, 0.027306, 0.027306, 0.027306, 0.027306, 0.027306 dot product = 0.997013 check = 0.000000, 0.000000, 0.000000, 0.000000, 0.000000, 0.000000, 0.000000, 0.000000, 0.000000 lambda = 0.000000 : ev = 0.000000, 0.000000, 1.000000, 0.000000, 0.000000, 0.000000, 0.000000, 0.000000, 0.000000 dot product = 1.000000 check = 0.000000, 0.000000, 0.000000, 0.000000, 0.000000, 0.000000, 0.000000, 0.000000, 0.000000
計算結果は検算サイトを上段にapatchを下段に示しています。checkは「Ax - λx」を計算した結果です。dot productは検算サイトとapatchの結果の固有ベクトルを正規化して内積した結果です。
「Ax - λx」の検算結果はどちらもほぼ0ベクトルに近いですがどちらかといえば検算サイトの方に大きな誤差が見られます。また結果を全部載せられてませんが固有ベクトルの内積の絶対値は最悪で0.91でしたので、2つの解にはそれなりの誤差があるということなのかも知れません。このあたりの素養がないので「Ax - λx」の値がより0に近いapatchの方がよい解じゃないかと思うほどです。
固有値が0のときの固有ベクトルの要素が0になるようにとのことですが、収束を加速するために漸化式を変形するなどのテクニックがあるようなので、そのあたりが原因ではないでしょうか。たまたまなのですが、試しにJacobi法を素朴に実装して解いてみたら固有値が0の3つの項については検算サイトと同一方向の固有ベクトルになりました。apatchのライブラリーリファレンスには実装に用いた論文?の記述がありますので方式の違いについて調べることが可能かと思います。
また固有ベクトルを正規化するかどうかですが、定義だけみると方向が重要で大きさは重要ではないように思えるのですが、もし大きさにも一定の条件を課した固有ベクトルが必要なら方式そのものを限定しなければいけないように思いました。
最後に参考になるかはわかりませんが、素朴なJacobi法を用いたときの固有値が0のときの結果を次に示しておきます。下段がJacobi法です。(P'JP=AのPの初期値は単位行列,許容誤差=1e-8で計算しました)
[ 7] lambda = 0.186393 : ev = 1.000000, 0.813607, 0.000000, -1.000000, 0.289169, -0.289169, -0.813607, -1.000000, 1.000000 lambda = 0.186393 : ev = 0.426745, 0.347202, 0.000000, -0.426745, 0.123401, -0.123401, -0.347202, -0.426745, 0.426745 dot product = 1.000000 check = 0.000000, -0.000000, 0.000000, -0.000000, 0.000000, -0.000000, 0.000000, -0.000000, 0.000000 [ 8] lambda = 0.000000 : ev = 1.000000, 1.000000, 0.000000, 1.000000, 1.000000, 1.000000, 1.000000, 1.000000, 1.000000 lambda = 0.000000 : ev = 0.353553, 0.353553, 0.000000, 0.353553, 0.353553, 0.353553, 0.353553, 0.353553, 0.353553 dot product = 1.000000 check = -0.000000, 0.000000, 0.000000, 0.000000, 0.000000, -0.000000, -0.000000, 0.000000, -0.000000 [ 9] lambda = 0.000000 : ev = 0.000000, 0.000000, 1.000000, 0.000000, 0.000000, 0.000000, 0.000000, 0.000000, 0.000000 lambda = 0.000000 : ev = 0.000000, 0.000000, 1.000000, 0.000000, 0.000000, 0.000000, 0.000000, 0.000000, 0.000000 dot product = 1.000000 check = 0.000000, 0.000000, 0.000000, 0.000000, 0.000000, 0.000000, 0.000000, 0.000000, 0.000000
投稿2016/09/21 09:11
総合スコア18394
あなたの回答
tips
プレビュー
バッドをするには、ログインかつ
こちらの条件を満たす必要があります。