空間駆動P-線形再帰式構成アルゴリズム
あいさつ
んちゃろりん🎵
今回は主(やなさん)がベクトル空間からP-線形再帰式を構成する方法を思いついたらしいのでそれについて書いていきますのだ。
やなさんより
割り込み失礼。正直言いますけど人間の手で本記事の計算をするのはかなり難しいですが、計算さえできれば何処なる非自明なP-線形再帰式も構成できる様になるはずです。僕はこの方法を空間駆動P-線形再帰式構成アルゴリズムと呼ぶ事にしました。
興味を持ってくれると嬉しいぞ☆
あーごめん。ずんだもん続けてなー。
空間駆動P-線形再帰式構成
ベクトル空間$W$とその部分ベクトル空間$V_{k}=span\{\vb*{v_{0}}^{(k)},\vb*{v_{1}}^{(k)},...,\vb*{v}_{N}^{(k)}\}\subset W\quad(k\in\{0,1,...,D\})$について以下の条件が成り立つ十分条件は何だろうか？
\begin{equation}
\exists \tilde{D}\in\mathbb{N}_{0}\ s.t.\ \forall \tilde{d}\in \{0,1,2,...,D+\tilde{D}\}\ s.t.\ (a_{n}^{(\tilde{d})})_{0\leq \tilde{d}\leq\tilde{D},0\leq n\leq N}\in\mathbb{C}\ s.t.\ \sum_{d=\min\{0,\tilde{d}-D\}}^{\min\{\tilde{d},\tilde{D}\}}\sum_{n=0}^{N}a_{n}^{(d)}\vb*{v}_{n}^{(\tilde{d}-d)}=0
\end{equation}
[1]$\tilde{d}=0$の場合は$\sum_{n=0}^{N}a_{n}^{(0)}\vb*{v}_{n}^{(0)}=0$なので$\vb*{v}_{0}^{(0)},\vb*{v}_{1}^{(0)},...,\vb*{v}_{N}^{(0)}$は一次従属。
[2]次に、$\tilde{d}\leq \tilde{D}$の場合、線形写像$R^{(k)}_{n}:V_{k}\rightarrow V_{k},S^{(k)}:W\rightarrow W$が存在して$\vb*{v}_{n}^{(k)}=(R_{n}^{(k)}+S^{(k)}|_{V_{0}})\vb*{v}_{n}^{(0)}-\frac{1}{a_{n}^{(0)}}\sum_{d=1}^{k-1}a_{n}^{(d)}\vb*{v}_{n}^{(k-d)}$が成り立つとすると
\begin{eqnarray}
\sum_{d=0}^{\tilde{d}}\sum_{n=0}^{N}a_{n}^{(d)}\vb*{v}_{n}^{(\tilde{d}-d)}&=&\sum_{n=0}^{N}a_{n}^{(0)}\vb*{v}_{n}^{(\tilde{d})}+\sum_{d=1}^{\tilde{d}}\sum_{n=0}^{N}a_{n}^{(d)}\vb*{v}_{n}^{(\tilde{d}-d)}\\
&=&\sum_{n=0}^{N}a_{n}^{(0)}\{(R_{n}^{(k)}+S^{(\tilde{d})}|_{V_{0}})\vb*{v}_{0}^{(0)}-\frac{1}{a_{n}^{(0)}}\sum_{d=1}^{\tilde{d}-1}a_{n}^{(d)}\vb*{v}_{n}^{(\tilde{d}-d)}\}+\sum_{d=1}^{\tilde{d}}\sum_{n=0}^{N}a_{n}^{(d)}\vb*{v}_{n}^{(\tilde{d}-d)}\\
&=&\sum_{n=0}^{N}a_{n}^{(0)}R_{n}^{(\tilde{d})}\vb*{v}_{0}^{(0)}-\sum_{n=0}^{N}\sum_{d=1}^{\tilde{d}-1}a_{n}^{(d)}\vb*{v}_{n}^{(\tilde{d}-d)}+\sum_{d=1}^{\tilde{d}}\sum_{n=0}^{N}a_{n}^{(d)}\vb*{v}_{n}^{(\tilde{d}-d)}\\
&=&\sum_{n=0}^{N}a_{n}^{(0)}R_{n}^{(\tilde{d})}\vb*{v}_{0}^{(0)}+\sum_{n=0}^{N}a_{n}^{(\tilde{d})}\vb*{v}_{n}^{(0)}
\end{eqnarray}
ゆえに、$\sum_{n=0}^{N}a_{n}^{(0)}R_{n}^{(\tilde{d})}\vb*{v}_{0}^{(0)}+\sum_{n=0}^{N}a_{n}^{(\tilde{d})}\vb*{v}_{n}^{(0)}=0$が成り立つ事が分かる。
[3]また以下の式が成り立つ。
\begin{eqnarray}
\forall\tilde{d}\in\mathbb{N}(\tilde{D}\lt\tilde{d}\leq D+\tilde{D}):\sum_{d=\tilde{d}-D}^{\tilde{d}}\sum_{n=0}^{N}a_{n}^{(d)}\vb*{v}_{n}^{(\tilde{d}-d)}=0
\end{eqnarray}
[4]故に十分条件は次の様に書ける。
\begin{eqnarray}
\left\{
\begin{array}{l}
0)\vb*{v}_{0}^{(0)},\vb*{v}_{1}^{(0)},...,\vb*{v}_{N}^{(0)}は一次従属\\
1)\forall d\in\{0,1,2,...,\tilde{D}\}: \sum_{n=0}^{N}a_{n}^{(d)}\vb*{v}_{n}^{(0)}=0\\
2)\forall n\in\{1,2,...,N\}:\forall k\in\{1,2,...,\tilde{D}\}に対して線形写像R_{n}^{(k)}:V_{k}\rightarrow V_{k},S^{(k)}:W\rightarrow Wが存在して\vb*{v}_{n}^{(k)}=(R_{n}^{(k)}+S^{(k)}|_{V_{0}})\vb*{v}_{n}^{(0)}-\frac{1}{a_{n}^{(0)}}\sum_{d=1}^{k-1}a_{n}^{(d)}\vb*{v}_{n}^{(k-d)}\\
3)\forall n\in\{0,1,2,...,N\}:\forall \tilde{d}\in\{1,2,....,\tilde{D}\}:a_{n}^{(\tilde{d})}は次の式を満たす。\sum_{n=0}^{N}a_{n}^{(0)}R_{n}^{(\tilde{d})}\vb*{v}_{0}^{(0)}+\sum_{n=0}^{N}a_{n}^{(\tilde{d})}\vb*{v}_{n}^{(0)}=0\\
4)\forall\tilde{d}\in\mathbb{N}(\tilde{D}\lt\tilde{d}\leq D+\tilde{D}):\sum_{d=\tilde{d}-D}^{\tilde{D}}\sum_{n=0}^{N}a_{n}^{(d)}\vb*{v}_{n}^{(\tilde{d}-d)}=0
\end{array}
\right.
\end{eqnarray}
ベクトル空間$W$とその部分ベクトル空間$V_{k}=span\{\vb*{v_{0}}^{(k)},\vb*{v_{1}}^{(k)},...,\vb*{v}_{N}^{(k)}\}\subset W\quad(k\in\{0,1,...,D\})$について以下の式:
\begin{equation}
\exists \tilde{D}\in\mathbb{N}_{0}\ s.t.\ \forall \tilde{d}\in \{0,1,2,...,D+\tilde{D}\}\ s.t.\ (a_{n}^{(\tilde{d})})_{0\leq \tilde{d}\leq\tilde{D},0\leq n\leq N}\in\mathbb{C}\ s.t.\ \sum_{d=\min\{0,\tilde{d}-D\}}^{\tilde{d}}\sum_{n=0}^{N}a_{n}^{(d)}\vb*{v}_{n}^{(\tilde{d}-d)}=0
\end{equation}
が成り立つ為の十分条件は次の様に書ける。
\begin{eqnarray}
\left\{
\begin{array}{l}
0)\vb*{v}_{0}^{(0)},\vb*{v}_{1}^{(0)},...,\vb*{v}_{N}^{(0)}は一次従属\\
1)\forall d\in\{0,1,2,...,\tilde{D}\}: \sum_{n=0}^{N}a_{n}^{(d)}\vb*{v}_{n}^{(0)}=0\\
2)\forall n\in\{1,2,...,N\}:\forall k\in\{1,2,...,\tilde{D}\}に対して線形写像R_{n}^{(k)}:V_{k}\rightarrow V_{k},S^{(k)}:W\rightarrow Wが存在して\vb*{v}_{n}^{(k)}=(R_{n}^{(k)}+S^{(k)}|_{V_{0}})\vb*{v}_{n}^{(0)}-\frac{1}{a_{n}^{(0)}}\sum_{d=1}^{k-1}a_{n}^{(d)}\vb*{v}_{n}^{(k-d)}\\
3)\forall n\in\{0,1,2,...,N\}:\forall \tilde{d}\in\{1,2,....,\tilde{D}\}:a_{n}^{(\tilde{d})}は次の式を満たす。\sum_{n=0}^{N}a_{n}^{(0)}R_{n}^{(\tilde{d})}\vb*{v}_{0}^{(0)}+\sum_{n=0}^{N}a_{n}^{(\tilde{d})}\vb*{v}_{n}^{(0)}=0\\
4)\forall\tilde{d}\in\mathbb{N}(\tilde{D}\lt\tilde{d}\leq D+\tilde{D}):\sum_{d=\tilde{d}-D}^{\tilde{D}}\sum_{n=0}^{N}a_{n}^{(d)}\vb*{v}_{n}^{(\tilde{d}-d)}=0
\end{array}
\right.
\end{eqnarray}
上記の事を応用すると次の様な事ができる。
1. まずベクトル空間$W$とベクトル空間$V_{0}\coloneqq span\{\vb*{v}_{0}^{(0)},\vb*{v}_{1}^{(0)},...,\vb*{v}_{N}^{(0)}\}\subset W$を与える。ただし、$\vb*{v}_{0},\vb*{v}_{1},...,\vb*{v}_{N}$は一次従属。
2. 次に$D,\tilde{D}\in\mathbb{N}$を与える。
3. $k=1,2,...,\tilde{D}$に対して任意の線形写像$R_{n}^{(k)}:V_{k}\rightarrow V_{k},S^{(k)}:W\rightarrow W$を与え$\vb*{v}_{n}^{(k)}=(R_{n}^{(k)}+S^{(k)}|_{V_{0}})\vb*{v}_{n}^{(0)}-\frac{1}{a_{n}^{(0)}}\sum_{d=1}^{k-1}a_{n}^{(d)}\vb*{v}_{n}^{(k-d)}$を作り$a_{0}^{(\tilde{d})},a_{1}^{(\tilde{d})},...,a_{N}^{(\tilde{d})},V_{k}\coloneqq span\{\vb*{v}_{0}^{(k)},\vb*{v}_{1}^{(k)},...,\vb*{v}_{N}^{(k)}\}$を構成する。
4. $\forall\tilde{d}\in\mathbb{N}(\tilde{D}\lt\tilde{d}\leq D+\tilde{D}):\sum_{d=\tilde{d}-D}^{\tilde{D}}\sum_{n=0}^{N}a_{n}^{(d)}\vb*{v}_{n}^{(\tilde{d}-d)}=0$を満たす様に$\{a_{n}^{(d)}\}_{0\leq n\leq N,0\leq d\leq \tilde{D}}\subset\mathbb{C},\vb*{v}_{n}^{(k)}(k=\tilde{D}+1,...,D)$を構成する。
5. $\vb*{v}_{m}^{(0)}\coloneqq\begin{pmatrix}v_{m0}^{(0)}\\v_{m1}^{(0)}\\\vdots\\v_{mE}^{(0)}\end{pmatrix},\vb*{v}_{m}^{(1)}\coloneqq\begin{pmatrix}v_{m0}^{(1)}\\v_{m1}^{(1)}\\\vdots\\v_{mE}^{(1)}\end{pmatrix},...,\vb*{v}_{m}^{(D)}\coloneqq\begin{pmatrix}v_{m0}^{(D)}\\v_{m1}^{(D)}\\\vdots\\v_{mE}^{(D)}\end{pmatrix}$を並べる。そして、それぞれの第$i$成分を$\mathbb{C}$上一次独立な多項式$f_{i}^{(m)}(n_{1},n_{2},...,n_{M})$を対応づける。そして以下の式を構成する。
\begin{equation} \vb*{v}_{m}\mapsto Q_{m}(n_{1},n_{2},...,n_{M})=\sum_{d=0}^{D}n^{d}\sum_{k=0}^{E}v_{mk}^{(d)}f_{k}^{(d)}(n_{1},n_{2},...,n_{M}) \end{equation}
6. $(a_{m}^{(0)},a_{m}^{(1)},...,a_{m}^{(\tilde{D})})\mapsto p_{k}(n)\coloneqq\sum_{d=0}^{\tilde{D}}n^{d}a_{m}^{(d)}$を構成。
7. するとP-線形再帰式を得る事ができる。
\begin{equation} \sum_{m=0}^{N}p_{m}(n)Q_{m}(n_{1},n_{2},...,n_{M})=0 \end{equation}
8. 特に$\tilde{D}\rightarrow\infty$とした場合は、任意の$k\in\mathbb{N}$任意の線形写像$R_{n}^{(k)}:V_{0}\rightarrow V_{0},S^{(k)}:W\rightarrow W$を与え$\vb*{v}_{n}^{(k)}=(R_{n}^{(k)}+S^{(k)}|_{V_{0}})\vb*{v}_{n}^{(0)}-\frac{1}{a_{n}^{(0)}}\sum_{d=1}^{k-1}a_{n}^{(d)}\vb*{v}_{n}^{(k-d)}$を作り$V_{k}\coloneqq span\{\vb*{v}_{0}^{(k)},\vb*{v}_{1}^{(k)},...,\vb*{v}_{N}^{(k)}\}$を構成すればよい。
実は無限の方が楽!!!!!!!!|!!!!!!!|!!!
展覧会
ベクトル空間$V_{0}\coloneqq span\{\vb*{v}_{0}^{(0)}\coloneqq\begin{pmatrix}1\\0\end{pmatrix},\vb*{v}_{1}^{(0)}\coloneqq\begin{pmatrix}0\\1\end{pmatrix},\vb*{v}_{2}^{(0)}\coloneqq\begin{pmatrix}1\\1\end{pmatrix}\}$としたとき$D=2,\tilde{D}\rightarrow\infty$として非自明な三項間線形漸化式を構成せよ。
[1]$\vb*{v}_{0}^{(0)}+\vb*{v}_{1}^{(0)}-\vb*{v}_{2}^{(0)}=0$なので$a_{0}^{(0)}=a_{1}^{(0)}=-a_{2}^{(0)}=1$
[2]線型写像$R_{n}^{(d)}:V_{0}\rightarrow V_{0}$を次の性質が成り立つ様に定める。
\begin{eqnarray}
\left\{
\begin{array}{l}
0=R_{n}^{(d)}\vb*{v}_{n}^{(0)}-\frac{1}{a_{n}^{(0)}}(a_{n}^{(d-1)}\vb*{v}_{n}^{(1)}+a_{n}^{(d-2)}\vb*{v}_{n}^{(2)})\quad(d=3,4,5,...)\\
R_{n}^{(d)}\vb*{v}_{n}^{(0)}=\sum_{m=0}^{N}\vb*{v}_{m}r_{mn,n}^{(d)}\\
a_{n}^{(d)}=\lambda^{(d)}a_{n}^{(0)}-\sum_{m=0}^{N}r_{nm,n}^{(d)}a_{m}^{(0)}
\end{array}
\right.
\end{eqnarray}
[3]
\begin{eqnarray}
R_{n}^{(d)}\vb*{v}_{n}^{(0)}-\frac{1}{a_{n}^{(0)}}(a_{n}^{(d-1)}\vb*{v}_{n}^{(1)}+a_{n}^{(d-2)}\vb*{v}_{n}^{(2)})&=&R_{n}^{(d)}\vb*{v}_{n}^{(0)}-\frac{1}{a_{n}^{(0)}}(a_{n}^{(d-1)}R_{n}^{(1)}\vb*{v}_{n}^{(0)}+a_{n}^{(d-2)}R_{n}^{(2)}\vb*{v}_{n}^{(0)}-\frac{a_{n}^{(1)}}{a_{n}^{(0)}}R_{n}^{(1)}\vb*{v}_{n}^{(0)})\\
&=&\{R_{n}^{(d)}-\frac{a_{n}^{(0)}a_{n}^{(d-1)}-a_{n}^{(1)}}{(a_{n}^{(0)})^{2}}R_{n}^{(1)}-\frac{a_{n}^{(d-2)}}{a_{n}^{(0)}}R_{n}^{(2)}\}\vb*{v}_{n}^{(0)}\\
&=&0
\end{eqnarray}
ゆえに以下の様に定めれば良い。
\begin{equation}
R_{n}^{(d)}\coloneqq\frac{a_{n}^{(0)}a_{n}^{(d-1)}-a_{n}^{(1)}}{(a_{n}^{(0)})^{2}}R_{n}^{(1)}+\frac{a_{n}^{(d-2)}}{a_{n}^{(0)}}R_{n}^{(2)}
\end{equation}
[4]
\begin{eqnarray}
a_{n}^{(d)}&=&\lambda^{(d)}a_{n}^{(0)}-\sum_{m=0}^{N}r_{nm,n}^{(d)}a_{m}^{(0)}\\
&=&\lambda^{(d)}a_{n}^{(0)}-\sum_{m=0}^{N}\{\frac{a_{n}^{(0)}a_{n}^{(d-1)}-a_{n}^{(1)}}{(a_{n}^{(0)})^{2}}r_{nm,n}^{(1)}+\frac{a_{n}^{(d-2)}}{a_{n}^{(0)}}r_{n,m,n}^{(2)}\}a_{m}^{(0)}\quad(n=0,1,2)
\end{eqnarray}
[5]
\begin{eqnarray}
\left\{
\begin{array}{l}
p_{k}(n)=1+\sum_{d=1}^{\infty}a_{k}^{(d)}n^{d}\quad(k=0,1,2)\\
Q_{k}(x,y)=1+\sum_{d=1}^{2}(v_{k,0}^{(d)}+v_{k,1}^{(d)}x)n^{d}\quad(k=0,1,2)
\end{array}
\right.
\end{eqnarray}
とすれば以下の式が成り立つ。
\begin{equation}
\sum_{k=0}^{2}p_{k}(n)Q_{k}(x,n)\equiv0
\end{equation}
[6]
\begin{eqnarray}
\left\{
\begin{array}{l}
a_{0}^{(0)}=a_{1}^{(0)}=-a_{2}^{(0)}=1\\
\forall r_{00,n}^{(d)},r_{01,n}^{(d)},r_{10,n}^{(d)},r_{11,n}^{(d)}\in\mathbb{C}:R_{n}^{(d)}\coloneqq\begin{pmatrix}r_{00,n}^{(d)}&r_{01,n}^{(d)}\\r_{10,n}^{(d)}&r_{11,n}^{(d)}\end{pmatrix}\quad(d=1,2;n=0,1,2)\\
R_{n}^{(d)}\coloneqq\frac{a_{n}^{(0)}a_{n}^{(d-1)}-a_{n}^{(1)}}{(a_{n}^{(0)})^{2}}R_{n}^{(1)}+\frac{a_{n}^{(d-2)}}{a_{n}^{(0)}}R_{n}^{(2)}\quad(d\geq3;n=0,1,2)\\
\forall \lambda^{(d)}\in\mathbb{C}:a_{n}^{(d)}\coloneqq\lambda^{(d)}a_{n}^{(0)}-\sum_{m=0}^{N}\{\frac{a_{n}^{(0)}a_{n}^{(d-1)}-a_{n}^{(1)}}{(a_{n}^{(0)})^{2}}r_{nm,n}^{(1)}+\frac{a_{n}^{(d-2)}}{a_{n}^{(0)}}r_{n,m,n}^{(2)}\}a_{m}^{(0)}\quad(d\geq3;n=0,1,2)
\end{array}
\right.
\end{eqnarray}
この記事を高評価した人
この記事に送られたバッジ
投稿者
