リッシュアルゴリズム

記号計算において、リッシュアルゴリズムは不定積分の手法の一つであり、一部のコンピュータ代数システムで不定積分を求めるために用いられます。このアルゴリズムは、1968年にこのアルゴリズムを開発したコンピュータ代数の専門家 であるアメリカの数学者ロバート・ヘンリー・リッシュにちなんで名付けられました。

このアルゴリズムは、積分の問題を代数の問題に変換する。これは、積分対象となる関数の形と、有理関数、根号、対数、指数関数の積分法に基づいている。リッシュはこれを「決定手続き」と呼んだ。これは、関数が不定積分として初等関数を持つかどうかを判定し、持つ場合はその不定積分を決定する方法だからである。しかし、このアルゴリズムは、与えられた関数の原始関数が実際に初等関数で表現できるかどうかを常に判定できるわけではない。^{[例が必要]}

リッシュアルゴリズムの完全な説明には100ページ以上かかります。^[1]リッシュ-ノーマンアルゴリズムは、1976年にアーサー・ノーマンによって開発された、より単純で高速ですが、それほど強力ではない変種です。

ブライアン・L・ミラーによる混合超越代数積分の対数部分の計算において、大きな進歩がありました。^[2]

説明

リッシュのアルゴリズムは、基本関数の積分に用いられます。基本関数とは、指数関数、対数関数、根号関数、三角関数、四則演算（+ − × ÷）を合成して得られる関数です。ラプラスは、有理関数の不定積分が有理関数であり、かつ有理関数の対数の定数倍が有限個存在することを示して、この問題を有理関数の場合に解決しました^{（[要出典]）}。ラプラスが提案したアルゴリズムは、通常、微積分の教科書に記載されていますが、コンピュータプログラムとして実装されたのは1960年代になってからでした（ ^{[要出典]） 。}

リウヴィルは、リッシュのアルゴリズムによって解かれる問題を定式化した。リウヴィルは解析的な手法を用いて、方程式g ′ = fの基本解gが存在する場合、定数α _iと関数u _iおよびv がfによって生成される体上に存在し、その解が以下の形になることを証明した。

${\displaystyle g=v+\sum _{i<n}\alpha _{i}\ln(u_{i})}$

リッシュは、リウヴィル形式の関数の有限集合のみを考慮できる手法を開発しました。

リッシュアルゴリズムの直感は、指数関数と対数関数の微分下での挙動から得られる 。関数f e ^g （ fとgは微分可能関数）に対して、

${\displaystyle \left(f\cdot e^{g}\right)^{\prime }=\left(f^{\prime }+f\cdot g^{\prime }\right)\cdot e^{g},\,}$

したがって、e ^{g が}不定積分の結果に含まれる場合、積分の内部にあると予想される。また、

${\displaystyle \left(f\cdot (\ln g)^{n}\right)^{\prime }=f^{\prime }\left(\ln g\right)^{n}+nf{\frac {g^{\prime }}{g}}\left(\ln g\right)^{n-1}}$

積分の結果に (ln g ) ⁿが含まれる場合、対数のべき乗はわずかしか期待できないはずです。

問題の例

基本的な原始積分を求めることは、細部に非常に敏感です。例えば、次の代数関数（1993年にHenri Cohenによってsci.math.symbolicに投稿^[3]）は、Wolfram Mathematicaバージョン13以降で基本的な原始積分を持つことがわかります（ただし、Mathematicaはこの積分の計算にRischアルゴリズムを使用していません）。^{[4] [5]}

${\displaystyle f(x)={\frac {x}{\sqrt {x^{4}+10x^{2}-96x-71}}},}$

すなわち：

${\displaystyle {\begin{aligned}F(x)=-{\frac {1}{8}}\ln &\,{\Big (}(x^{6}+15x^{4}-80x^{3}+27x^{2}-528x+781){\sqrt {x^{4}+10x^{2}-96x-71}}{\Big .}\\&{}-{\Big .}(x^{8}+20x^{6}-128x^{5}+54x^{4}-1408x^{3}+3124x^{2}+10001){\Big )}+C.\end{aligned}}}$

しかし、定数項71を72に変更すると、FriCASでも示されているように、原始関数を用いて原始積分を表すことができなくなる^[6]。一部のコンピュータ代数システムは、ここで原始関数以外の関数（すなわち楕円積分）を用いて原始積分を返すことがあるが、これはRischアルゴリズムの範囲外である。例えば、Mathematicaは関数EllipticPiとEllipticFを用いて結果を返す。この形式の積分はチェビシェフによって解かれており（そしてどのような場合に原始積分となるのか）^{[7] 、その厳密な証明は最終的に}ゾロタレフによってなされた^[6]。${\displaystyle \int {\frac {x+A}{\sqrt {x^{4}+ax^{3}+bx^{2}+cx+d}}}\,dx}$

以下は代数関数と超越関数の両方を含むより複雑な例である: ^[8]

${\displaystyle f(x)={\frac {x^{2}+2x+1+(3x+1){\sqrt {x+\ln x}}}{x\,{\sqrt {x+\ln x}}\left(x+{\sqrt {x+\ln x}}\right)}}.}$

実際、この関数の原始関数は、置換を使って見つけられるかなり短い形式を持っています （SymPyでは解けますが、FriCASではRischアルゴリズムで「実装が不完全（定数留数）」エラーが発生して失敗します）。 ${\displaystyle u=x+{\sqrt {x+\ln x}}}$

${\displaystyle F(x)=2\left({\sqrt {x+\ln x}}+\ln \left(x+{\sqrt {x+\ln x}}\right)\right)+C.}$

ダベンポートの「定理」^{[定義が必要]}の中には、いまだ解明されていないものもある。例えば2020年には、そのような「定理」に対する反例が発見され、結局は初等的な原始積分が存在することが判明した。^[9]

実装

リッシュの理論的なアルゴリズムを、コンピューターが効果的に実行できるアルゴリズムに変換するのは、長い時間を要した複雑な作業でした。

純粋超越関数（多項式の根を含まない関数）の場合は比較的容易であり、ほとんどのコンピュータ代数システムに早期に実装されていました。最初の実装は、Rischの論文発表直後にJoel MosesによってMacsymaで行われました。 ^[10]

純粋代数関数の場合は、ジェームズ・H・ダベンポートによってReduceで部分的に解決され実装されました。単純化のため、平方根と繰り返し平方根のみを扱うことができ、一般的な根号や変数間のその他の非二次代数関係は扱うことができませんでした。^[11]

一般的なケースは、Axiomの前身であるScratchpadでManuel Bronsteinによって解決され、ほぼ完全に実装されました。AxiomのフォークであるFriCASがあり、githubでRischやその他のアルゴリズムの開発が活発に行われています。^{[12] [13]}しかし、実装では特殊なケースのブランチの一部が完全には含まれていませんでした。^{[14] [15]} 2025年現在、Rischアルゴリズムの完全な実装は知られていません。^[16]

決定可能性

一般的な初等関数に適用されるRischアルゴリズムは、アルゴリズムではなく半アルゴリズムです。なぜなら、演算の一部として、特定の式がゼロと等しいかどうか（定数問題）を、特に定数体において確認する必要があるからです。一般的に初等関数とみなされる関数のみを含む式については、そのような確認を行うアルゴリズムが存在するかどうかは不明です（現在のコンピュータ代数システムはヒューリスティックスを用いています）。さらに、初等関数のリストに絶対値関数を追加すると、そのようなアルゴリズムは存在しないことがわかります。リチャードソンの定理を参照してください。^{[説明が必要]}

この問題は多項式除算アルゴリズムでも発生する。このアルゴリズムは、係数が同一にゼロになるかどうかを正しく判断できない場合は失敗する。^[17]多項式に関するほぼすべての非自明なアルゴリズムは、Risch アルゴリズムを含め、多項式除算アルゴリズムを使用する。定数体が計算可能、すなわちxに依存しない要素の場合、ゼロ同値の問題は決定可能であるため、Risch アルゴリズムは完全なアルゴリズムである。計算可能な定数体の例としては、ℚとℚ( y ) 、つまりそれぞれ有理数係数を持つyの有理数と有理関数があり、yはxに依存しない不定数である。

これはガウス消去法行列アルゴリズム（あるいは行列の零空間を計算できるあらゆるアルゴリズム）においても問題となる。このアルゴリズムは、Rischアルゴリズムの多くの部分でも必要となる。ガウス消去法は、ピボットが同一にゼロであるかどうかを正しく判断できない場合、誤った結果を生成する^[要出典]。

参照

• コンピュータプログラミングポータル
• 数学ポータル

• Axiom（コンピュータ代数システム）
• 閉じた形式の表現
• 不完全ガンマ関数
• 積分のリスト
• リウヴィルの定理（微分代数）
• 非初等積分
• 記号積分

注記

1. ゲデス、チャポル、ラバーン 1992.
2. ミラー、ブライアン・L. (2012年5月). 「初等関数の積分について：対数部分の計算」 . 2023年12月10日閲覧。
3. コーエン、アンリ（1993年12月21日）「お気に入りのCASへのクリスマスプレゼント」
4. “Wolfram Cloud”. Wolfram Cloud . 2021年12月11日閲覧。
5. この例は、2000年11月24日にManuel BronsteinによってUsenetフォーラムcomp.soft-sys.math.mapleに投稿されました。[1]
6. Zolotareff、G. (1872 年 12 月 1 日)。「M.チェビシェフの統合方法」。Mathematische Annalen (フランス語)。5 (4): 560–580。土井:10.1007/BF01442910。ISSN  1432-1807。S2CID  123629827。
7. チェビシェフ, PL (1899–1907). Oeuvres de PL Tchebyshev (フランス語). University of California Berkeley. San. Petersbourg, Commissionaires de l'Academie imperiale des sciences. pp.  171– 200.
8. ブロンスタイン 1998.
9. Masser, David; Zannier, Umberto (2020年12月). 「Torsion points, Pell's equation, and integration in elementary terms」. Acta Mathematica . 225 (2): 227– 312. doi : 10.4310/ACTA.2020.v225.n2.a2 . hdl : 11384/110046 . ISSN  1871-2509. S2CID  221405883.
10. モーゼス 2012.
11. ダベンポート 1981年。
12. fricas/fricas、fricas、2025 年 2 月 5 日、 2025 年2 月 6 日に取得
13. ブロンスタイン 1990.
14. “MathAction RischImplementationStatus”. 2023年9月30日. 2024年12月23日閲覧。
15. Bronstein, Manuel (2003年9月5日). 「Manuel BronsteinによるAxiomの統合機能について」. groups.google.com . 2023年2月10日閲覧。
16. 「積分 - Rischアルゴリズムの完全な実装は存在するのか？」MathOverflow . 2020年10月15日. 2023年2月10日閲覧。
17. 「Mathematica 7 ドキュメント: PolynomialQuotient」.セクション: 起こりうる問題. 2010年7月17日閲覧。

参考文献

• ブロンスタイン、マヌエル (1990). 「初等関数の積分」.シンボリック計算ジャーナル. 9 (2): 117– 173. doi :10.1016/s0747-7171(08)80027-2.

• ブロンスタイン、マヌエル (1998). 「記号積分チュートリアル」(PDF) . ISSAC'98、ロストック (1998年8月) および微分代数ワークショップ、ラトガース大学.

• ブロンスタイン、マヌエル（2005年）『記号積分I』シュプリンガー、ISBN 3-540-21493-3。

• ダベンポート、ジェームズ・H. (1981).代数関数の積分について.コンピュータサイエンス講義ノート. 第102巻. シュプリンガー. ISBN 978-3-540-10290-8。

• Geddes, Keith O. ; Czapor, Stephen R. ; Labahn, George (1992). コンピュータ代数アルゴリズム. ボストン, MA: Kluwer Academic Publishers. pp. xxii+585. Bibcode :1992afca.book.....G. doi :10.1007/b102438. ISBN 0-7923-9259-0。

• モーゼス、ジョエル (2012). 「Macsyma：個人的な歴史」. Journal of Symbolic Computation . 47 (2): 123– 130. doi :10.1016/j.jsc.2010.08.018.

• リッシュ, RH (1969). 「有限項における積分の問題」.アメリカ数学会誌. 139.アメリカ数学会誌: 167–189 . doi : 10.2307/1995313 . JSTOR  1995313.

• リッシュ, RH (1970). 「有限項における積分問題の解」アメリカ数学会報. 76 (3): 605– 608. doi : 10.1090/S0002-9904-1970-12454-5 .

• ローゼンリヒト, マクスウェル (1972). 「有限項における積分」.アメリカ数学月刊. 79 (9). アメリカ数学会誌: 963–972 . doi :10.2307/2318066. JSTOR  2318066.

外部リンク

• バット、ブバネシュ。 「高度なアルゴリズム」。マスワールド。