多項式の計算法を示す
最小消去多項式を用いた一般固有ベクトル空間の基底計算法 (数式処理とその周辺分野の研究)
... 参考文献 [1] 小原功任，田島慎一 : 最小消去多項式候補を用いた行列の一般固有空間の構造の計算法について， COE Lecture Note 49(2013), Kyushu University, 113-118. [2] 小原功任，田島慎一 : ...
7
代数的Riccati 方程式の定義多項式の計算法について (Computer Algebra : Design of Algorithms, Implementations and Applications)
... $P$ の $(1,1)$ 成分、 $(1,2)$ ...$Q$ の行列のサイズ $n$ に対し、 変数の数が $*^{nn+\lrcorner 1}$ となるため、 比較的小さい $n$ に対しても実用的ではない。 そこで本稿では、 この定義多項式を効率的に計 算する方法について述べる ...
7
異常な多変数多項式の近似 GCD 計算法 (Computer Algebra : Design of Algorithms, Implementations and Applications)
... PRS 法の安定化を考える. 2 では、 1 変数 $PI\mathfrak{i}s$ 法において微小主係数の場合になぜ不安定に なるのか考察し、 安定した算法を提案する。 そして、 QRGCD 法と同等の精度を持つことを示す ...
7
連立多項式の近似根の計算法について (数式処理における理論と応用の研究)
... 多変数多項式の正則点での近似根の計算法 入力 : $x=[x_{1}$ . . . $x_{n}]^{T}$ を変数、 $\alpha$ をパラメータとする多項式 $F=[f1$ . . . $f_{n}]^{T}$ 正則点 $x=\triangle\eta^{()}0=[\eta_{1},0^{\cdot}$ ...
11
多項式のゼロ点の精度と計算方法 (精度保証付き数値計算法とその周辺)
... MS-FORTRAN の複素倍精度計算を用いた。 数値解の精度桁数とそのときの関数値の大きさを図 1 に示す。 $x$ 軸は数値解の位置、 $y$ 軸 は対応する数値解の精度桁数 (菱形印) と数値解を代入したときの 1 ...
4
行列の最小多項式計算について (Computer Algebra : Design of Algorithms, Implementations and Applications)
... 前の節で与えた定理をそのままの形で用いて，最小多項式を求めるアルゴリズムを構成することができ る．しかし，行列のサイズが大きい場合は定理をそのままの形で用いたような計算法では計算量が膨大な ...
8
解析関数の多項式因子を求める方法 (微分方程式の離散化手法と数値計算アルゴリズム)
... $\ldots$ の値を 十分な精度で求める必要がある. 本論文では, 数値積分を単位円周上の等間隔点での関数 値を利用して求めたときに積分誤差がどのような影響を与えるかを考察し, 文献 [4] で示 された方法では数値積分を必ずしも十分な精度で求める必要はないことを示す ...
10
誤差項をもつ実多項式の「近似実根」の計算とその応用 (数式処理における理論と応用の研究)
... Sturm 法を用いて実根の個数を 計算する場合に遭遇しうる微小主項の問題を考察し、 微小主項を除去できるための十分 条件を導いた。 本稿では、 これまでに提案した根の存在領域の計算法の有効性を調べる ...
13
多項式のゼロ点を求める場合の計算量について(数値計算における精度保証付き算法とその計算量に関する研究)
... Newton-Raphson 法について得た結 果の高次収束解法への拡張である。特に彼が考慮しなかった , Newton-Raphson 法が収束 に入る前の状態をも考察の対象としたために, Newton-Raphson 法の収束のプロセスが より明確になったと思われる。 ...
11
NP完全なブール関数に対する多項式時間スライス関数について(計算モデルと計算の複雑さに関する研究)
... TONIAN CIRCUIT, BANDWIDTH などのグラフの性質に関する $\mathrm{N}\mathrm{P}$ 完全関数のスライス関数で、多 項式サイズ回路で計算できるものをいくつか示す。 これらの結果を得るために、 Tur\’an グラフなどの特 ...
7
1変数パタン言語の多項式時間オンライン学習 (アルゴリズムと計算の理論)
... $\mathrm{e}$ -mails:{inago, arim} \copyright i. kyushu-u. $ac.j’p$ 概要: 1 変数パタン言語の族は, 正例から極限において同定可能であることが知られてい る . しかし , この族が多項式時間オンライン学習可能であるかどうかは, 未解決の問題であ る. 本研究では, 1 ...
8
行列多項式$I+A+A^2+\dots+A^{N-1}$の計算における行列乗算回数 (計算理論とアルゴリズムの新潮流)
... $A^{S}$ の新しい計算法を示す．この計算法により， $S$ の値によらず， $A^{S}$ を $G(S, A)$ から一回の行列乗算 で計算することができる．次に，この $A^{S}$ の計算法 を，素因数分解に基づく手法，および混合基数表現 ...
9
正データからのSimple Regular言語の多項式時間帰納推論(アルゴリズムと計算量理論)
... 時間推論可能性が最も基本的でかつ重要な問題として多くの研究がなされてきており, reversible 言 語 [4] や , very regular 言語 [9] などが正データから多項式時間推論可能であることが示されている. 本稿では, simple regular と呼ばれる word 上の決定性オートマトンを導入し , それで受理される ...
8
絡み目のJones多項式の計算 (計算モデルとアルゴリズム)
... Jones 多項式は代表的な絡み目型の不変量のひとつであり , Jones 多項式を求める問題は #P- 完 全であることが知られている ...Jones 多項式を次数の高い項から順に計算するアルゴリ ズムを考察し , これを改良することにより Jones ...
6
質問と正の反例による正則言語の多項式時間学習 (計算機科学の基礎理論 : 21世紀の計算パラダイムを目指して)
... ことを示す。 これは、状態数及び所属性質問では多 項式時間学習不可能であること $[1]_{\text{、}}$ また、状態数及 び等価性質問では多項式時間学習は難しいこと [6] と考えあわせると、教師にとって解決するのに難し い質問ほど学習者にとって有効であることを示して ...
6
多次元補間多項式関数を用いた識別関数の一構成法
... ) の第１項から第 4 項である。これら を合成した関数の合成図は図 8 である。区間 1 から 4 までの補間区間は，図 3 と比較すると， よい近似になっているのが見て取れる。 もし，離散点での値がクラスによって正と負に分かれるのであれば，f ( x ) ＝ 0 を識別関数 とすることができる。ところで， 1 ...
18
多項式剰余公式の計算アルゴリズム (Computer Algebra : Design of Algorithms, Implementations and Applications)
... $\mathrm{E}\mathrm{x}\mathrm{t}_{\mathrm{K}[x]}^{1}(K[x]/\langle f^{\ell}(x)\rangle, K[x])\underline{\simeq}\{[\frac{h(x)}{f^{p}(x)}]\in \mathrm{H}_{[Z]}^{1}(K[x])|h(x)\in K[x]\}$ . ベクトル空間 $K[x]/(f^{\ell}(x)\rangle$ ...
7
行列の最小消去多項式候補を用いた固有ベクトル計算(III) (数式処理とその周辺分野の研究)
... その後，我々は，固有ベクトル算法のさらなる拡張を提案した [5]. それまでに提案した算法は，着目す る固有値の重複度が 1 の場合に限られたが，拡張した算法は，着目する固有値に属する一般固有ベクトル 空間が，固有ベクトル空間に等しいという条件下で，着目する固有値の特性方程式における重複度が 1 よ reaj imaQmath. tsukuba. ac. jp ...
12
Tutte多項式とJones多項式の計算(計算モデルと計算の複雑さに関する研究)
... Tutte 多項式に類似した辺の縮約削除公式が成り立つことが $\mathrm{T}\mathrm{h}\mathrm{i}_{\mathrm{S}}\mathrm{t}\mathrm{l}\mathrm{e}\mathrm{t}\mathrm{h}_{\mathrm{W}\mathrm{a}\mathrm{i}}\mathrm{t}\mathrm{e}[4]$ によって示された ([5, 6] 参照 ) ...
7
行列の最小多項式候補と拡張Horner法を用いた逆行列計算について II (数式処理の新たな発展 : その最新研究と基礎理論の再構成)
... With this result, we propose an algorithm for calculating matrix inverse by evaluating pseudo minimal polynomial via pseudo annihilating polynomial of the matrix using the extended Horne[r] ...
11