ファデーエフ・ルヴェリエアルゴリズム

ユルバン・ル・ヴェリエ(1811–1877)海王星
の発見者。

数学（線型代数）において、ファデーエフ・ルヴェリエ法は、正方行列Aの特性多項式の係数を計算する 再帰的手法であり、ドミトリー・コンスタンティノヴィチ・ファデーエフとウルバン・ルヴェリエにちなんで名付けられました。この多項式を計算すると、Aの固有値がその根として得られます。行列A自体の行列多項式であるため、ケーリー・ハミルトン定理により消えます。特性多項式を行列式の定義から直接計算することは、新しい記号量を導入する点で計算上面倒です。対照的に、ファデーエフ・ルヴェリエ法は行列の係数を直接処理します。 ${\displaystyle p_{A}(\lambda )=\det(\lambda I_{n}-A)}$ ${\displaystyle \lambda }$ ${\displaystyle A}$

このアルゴリズムは、異なる形で何度も独立して再発見されてきました。1840年にUrbain Le Verrierによって初めて発表され、その後P. Horst、Jean-Marie Souriauによって再開発され、現在の形ではFaddeevとSominsky、そしてJ.S. Frameらによって提唱されました。^{[1] [2] [3] [4] [5]}（歴史的な点については、Householderを参照。^[6]ニュートン多項式を迂回する簡潔な証明法は、Houによって導入された。^[7]ここでの提示の大部分は、Gantmacherの88ページに準拠している。 ^[8]）

アルゴリズム

目的は、 n × n行列Aの特性多項式の係数c _kを計算することである。

${\displaystyle p_{A}(\lambda )\equiv \det(\lambda I_{n}-A)=\sum _{k=0}^{n}c_{k}\lambda ^{k}~,}$

ここで、明らかに、c _n = 1（特性多項式は単項多項式）であり、c ₀ = (−1) ⁿ det Aです。

係数c _{n − iは}、補助行列列を用いて iに関する帰納法によって決定される。

${\displaystyle {\begin{aligned}M_{0}&\equiv 0&c_{n}&=1\qquad &(k=0)\\M_{k}&\equiv AM_{k-1}+c_{n-k+1}I\qquad \qquad &c_{n-k}&=-{\frac {1}{k}}\mathrm {tr} (AM_{k})\qquad &k=1,\ldots ,n~.\end{aligned}}}$

したがって、

${\displaystyle M_{1}=I~,\quad c_{n-1}=-\mathrm {tr} A=-c_{n}\mathrm {tr} A;}$

${\displaystyle M_{2}=A-I\mathrm {tr} A,\quad c_{n-2}=-{\frac {1}{2}}{\Bigl (}\mathrm {tr} A^{2}-(\mathrm {tr} A)^{2}{\Bigr )}=-{\frac {1}{2}}(c_{n}\mathrm {tr} A^{2}+c_{n-1}\mathrm {tr} A);}$

${\displaystyle M_{3}=A^{2}-A\mathrm {tr} A-{\frac {1}{2}}{\Bigl (}\mathrm {tr} A^{2}-(\mathrm {tr} A)^{2}{\Bigr )}I,}$

${\displaystyle c_{n-3}=-{\tfrac {1}{6}}{\Bigl (}(\operatorname {tr} A)^{3}-3\operatorname {tr} (A^{2})(\operatorname {tr} A)+2\operatorname {tr} (A^{3}){\Bigr )}=-{\frac {1}{3}}(c_{n}\mathrm {tr} A^{3}+c_{n-1}\mathrm {tr} A^{2}+c_{n-2}\mathrm {tr} A);}$

等、^{[9] [10]}   …

${\displaystyle M_{m}=\sum _{k=1}^{m}c_{n-m+k}A^{k-1}~,}$

${\displaystyle c_{n-m}=-{\frac {1}{m}}(c_{n}\mathrm {tr} A^{m}+c_{n-1}\mathrm {tr} A^{m-1}+...+c_{n-m+1}\mathrm {tr} A)=-{\frac {1}{m}}\sum _{k=1}^{m}c_{n-m+k}\mathrm {tr} A^{k}~;...}$

A ⁻¹ = − M _n /c ₀ = (−1) ^{n −1} M _n /detを観察すると、 A はλで再帰を終了します。これはAの逆行列または行列式を求めるために使用できます。

導出

証明は、補助行列である随伴行列B _k ≡ M _n−kのモードに依存します。この行列は次のように定義されます

${\displaystyle (\lambda I-A)B=I~p_{A}(\lambda )}$

そしてそれは溶解度に比例する

${\displaystyle B=(\lambda I-A)^{-1}I~p_{A}(\lambda )~.}$

これは明らかにλのn−1次行列多項式である。したがって、

${\displaystyle B\equiv \sum _{k=0}^{n-1}\lambda ^{k}~B_{k}=\sum _{k=0}^{n}\lambda ^{k}~M_{n-k},}$

ここで無害なM ₀ ≡0を定義することができる。

上記の従属項の定義式に明示的な多項式を挿入すると、

${\displaystyle \sum _{k=0}^{n}\lambda ^{k+1}M_{n-k}-\lambda ^{k}(AM_{n-k}+c_{k}I)=0~.}$

さて、最高次では、最初の項はM ₀ =0によって消えます。一方、最低次（ λが一定、上記の随伴項の定義式より）では、

${\displaystyle M_{n}A=B_{0}A=c_{0}~,}$

最初の項のダミーインデックスをシフトすると、

${\displaystyle \sum _{k=1}^{n}\lambda ^{k}{\Big (}M_{1+n-k}-AM_{n-k}+c_{k}I{\Big )}=0~,}$

これにより再帰が決定される

${\displaystyle \therefore \qquad M_{m}=AM_{m-1}+c_{n-m+1}I~,}$

m =1,..., nの場合。指数の昇順はλのべき乗の降順に相当するが、多項式の係数cはMとAに関してまだ決定されていないことに注意する。

これは次の補助方程式（Hou, 1998）を通して最も簡単に達成できる。

${\displaystyle \lambda {\frac {\partial p_{A}(\lambda )}{\partial \lambda }}-np=\operatorname {tr} AB~.}$

これはヤコビの公式による Bの定義式の単なる痕跡である 。

${\displaystyle {\frac {\partial p_{A}(\lambda )}{\partial \lambda }}=p_{A}(\lambda )\sum _{m=0}^{\infty }\lambda ^{-(m+1)}\operatorname {tr} A^{m}=p_{A}(\lambda )~\operatorname {tr} {\frac {I}{\lambda I-A}}\equiv \operatorname {tr} B~.}$

この補助方程式に多項式モード形式を挿入すると、

${\displaystyle \sum _{k=1}^{n}\lambda ^{k}{\Big (}kc_{k}-nc_{k}-\operatorname {tr} AM_{n-k}{\Big )}=0~,}$

そう

${\displaystyle \sum _{m=1}^{n-1}\lambda ^{n-m}{\Big (}mc_{n-m}+\operatorname {tr} AM_{m}{\Big )}=0~,}$

そして最後に

${\displaystyle \therefore \qquad c_{n-m}=-{\frac {1}{m}}\operatorname {tr} AM_{m}~.}$

これで、 λの降順で展開される前のセクションの再帰が完了します

さらに、アルゴリズムでは、より直接的に、

${\displaystyle M_{m}=AM_{m-1}-{\frac {1}{m-1}}(\operatorname {tr} AM_{m-1})I~,}$

そして、ケーリー・ハミルトン定理に従って、

${\displaystyle \operatorname {adj} (A)=(-1)^{n-1}M_{n}=(-1)^{n-1}(A^{n-1}+c_{n-1}A^{n-2}+...+c_{2}A+c_{1}I)=(-1)^{n-1}\sum _{k=1}^{n}c_{k}A^{k-1}~.}$

最終的な解は、より簡便には完全指数ベル多項式で次のよう に表現されるかもしれない。

${\displaystyle c_{n-k}={\frac {(-1)^{n-k}}{k!}}{\mathcal {B}}_{k}{\Bigl (}\operatorname {tr} A,-1!~\operatorname {tr} A^{2},2!~\operatorname {tr} A^{3},\ldots ,(-1)^{k-1}(k-1)!~\operatorname {tr} A^{k}{\Bigr )}.}$

例

${\displaystyle {\displaystyle A=\left[{\begin{array}{rrr}3&1&5\\3&3&1\\4&6&4\end{array}}\right]}}$

${\displaystyle {\displaystyle {\begin{aligned}M_{0}&=\left[{\begin{array}{rrr}0&0&0\\0&0&0\\0&0&0\end{array}}\right]\quad &&&c_{3}&&&&&=&1\\M_{\mathbf {\color {blue}1} }&=\left[{\begin{array}{rrr}1&0&0\\0&1&0\\0&0&1\end{array}}\right]&A~M_{1}&=\left[{\begin{array}{rrr}\mathbf {\color {red}3} &1&5\\3&\mathbf {\color {red}3} &1\\4&6&\mathbf {\color {red}4} \end{array}}\right]&c_{2}&&&=-{\frac {1}{\mathbf {\color {blue}1} }}\mathbf {\color {red}10} &&=&-10\\M_{\mathbf {\color {blue}2} }&=\left[{\begin{array}{rrr}-7&1&5\\3&-7&1\\4&6&-6\end{array}}\right]\qquad &A~M_{2}&=\left[{\begin{array}{rrr}\mathbf {\color {red}2} &26&-14\\-8&\mathbf {\color {red}-12} &12\\6&-14&\mathbf {\color {red}2} \end{array}}\right]\qquad &c_{1}&&&=-{\frac {1}{\mathbf {\color {blue}2} }}\mathbf {\color {red}(-8)} &&=&4\\M_{\mathbf {\color {blue}3} }&=\left[{\begin{array}{rrr}6&26&-14\\-8&-8&12\\6&-14&6\end{array}}\right]\qquad &A~M_{3}&=\left[{\begin{array}{rrr}\mathbf {\color {red}40} &0&0\\0&\mathbf {\color {red}40} &0\\0&0&\mathbf {\color {red}40} \end{array}}\right]\qquad &c_{0}&&&=-{\frac {1}{\mathbf {\color {blue}3} }}\mathbf {\color {red}120} &&=&-40\end{aligned}}}}$

さらに 、上記の計算を裏付ける ${\displaystyle {\displaystyle M_{4}=A~M_{3}+c_{0}~I=0}}$

行列Aの特性多項式は、 Aの行列式は、トレースは10=− c ₂であり、Aの逆行列は、 ${\displaystyle {\displaystyle p_{A}(\lambda )=\lambda ^{3}-10\lambda ^{2}+4\lambda -40}}$ ${\displaystyle {\displaystyle \det(A)=(-1)^{3}c_{0}=40}}$

${\displaystyle {\displaystyle A^{-1}=-{\frac {1}{c_{0}}}~M_{3}={\frac {1}{40}}\left[{\begin{array}{rrr}6&26&-14\\-8&-8&12\\6&-14&6\end{array}}\right]=\left[{\begin{array}{rrr}0{.}15&0{.}65&-0{.}35\\-0{.}20&-0{.}20&0{.}30\\0{.}15&-0{.}35&0{.}15\end{array}}\right]}}$ 。

同等だが異なる表現

上記のヤコビの公式のm × m行列解のコンパクトな行列式は、係数cを決定することもできる。^{[11] [12]}

${\displaystyle c_{n-m}={\frac {(-1)^{m}}{m!}}{\begin{vmatrix}\operatorname {tr} A&m-1&0&\cdots &0\\\operatorname {tr} A^{2}&\operatorname {tr} A&m-2&\cdots &0\\\vdots &\vdots &&&\vdots \\\operatorname {tr} A^{m-1}&\operatorname {tr} A^{m-2}&\cdots &\cdots &1\\\operatorname {tr} A^{m}&\operatorname {tr} A^{m-1}&\cdots &\cdots &\operatorname {tr} A\end{vmatrix}}~.}$

参照

• 特性多項式
• ホーナー法
• フレドホルム行列式

参考文献

1. ウルバン・ル・ヴェリエ：軌道要素の二次的変化について、J. de Math. (1) 5 , 230 (1840)、オンライン
2. ポール・ホルスト「特性方程式の係数を決定する方法」Ann. Math. Stat. 6 83-84 (1935), doi :10.1214/aoms/1177732612
3. Jean-Marie Souriau、 Une methode pour la decomposition spectrale et l'inversion des matrices、 Comptes Rend。 227、1010-1011 (1948)。
4. DK Faddeev, IS Sominsky, Sbornik zadatch po vyshej algebra (Problems in high algebra Archived 2016-03-09 at the Wayback Machine , Mir publishers, 1972), Moscow-Leningrad (1949). Problem 979 .
5. JSフレーム：逆行列を求めるための簡単な再帰式（要約） Bull . Am. Math. Soc. 55 1045（1949）、doi：10.1090/S0002-9904-1949-09310-2
6. ハウスホルダー、アルストンS. (2006).数値解析における行列理論. ドーバー数学書籍. ISBN  0486449726。
7. Hou, SH (1998). 「教室ノート：レヴァリエ-ファデーエフ特性多項式アルゴリズムの簡単な証明」SIAMレビュー 40(3) 706-709, doi :10.1137/S003614459732076X
8. Gantmacher, FR (1960). 『行列の理論』 ニューヨーク: Chelsea Publishing. ISBN 0-8218-1376-5。
9. ザデー、ロトフィ・A.、デソア、チャールズ・A. (1963, 2008). 線形システム理論：状態空間アプローチ(マクグローヒル社; ドーバー土木機械工学社) ISBN 9780486466637、303～305ページ
10. Abdeljaoued, Jounaidi and Lombardi, Henri (2004). Méthodes matricielles - Introduction à la complexité algébrique , (Mathématiques et Applications, 42) Springer, ISBN 3540202471。
11. ブラウン、ローウェル S. (1994).『場の量子論』、ケンブリッジ大学出版局. ISBN 978-0-521-46946-3、54ページ。また、Curtright, TL、Fairlie, DB、Alshal, H. (2012)「A Galileon Primer」arXiv:1212.6972、第3節も参照
12. Reed, M.; Simon, B. (1978). Methods of Modern Mathematical Physics . Vol. 4 Analysis of Operators. USA: ACADEMIC PRESS, INC. pp.  323– 333, 340, 343. ISBN 0-12-585004-2。

Barbaresco F. (2019) Souriau 指数写像アルゴリズムによる行列リー群の機械学習。Nielsen F.、Barbaresco F. (編) Geometric Sc​​ience of Information。GSI 2019. Lecture Notes in Computer Science、vol 11712。Springer、Cham。https://doi.org/10.1007/978-3-030-26980-7_10