リッシュアルゴリズム

数式処理において、リッシュアルゴリズムは、一部の数式処理システムで原始関数を求めるために用いられる不定積分法である。このアルゴリズムは、1968年に開発した数式処理の専門家であるアメリカの数学者ロバート・ヘンリー・リッシュにちなんで名付けられた。

このアルゴリズムは、積分問題を代数の問題に変換する。これは、積分される関数の形式と、有理関数、根号、対数、指数関数の積分法に基づいている。リッシュはこれを決定手順と呼んだ。なぜなら、これは関数が不定積分として基本関数を持つかどうかを判定し、持つ場合はその不定積分を決定する方法だからである。しかし、このアルゴリズムは、与えられた関数の原始関数が実際に基本関数で表現できるかどうかを常に特定できるとは限らない。具体的には、任意の複素数式がゼロに等しいかどうかを判定する必要がある場合、このアルゴリズムは定数問題を解決できない。

Rischアルゴリズムの完全な説明は100ページ以上に及ぶ。^{[ 1 ]} Risch –Normanアルゴリズムは、より単純で高速だが、性能は劣るバリアントで、1976年にArthur Normanによって開発された。

Brian L. Miller により、混合超越代数積分の対数部分の計算において、いくつかの重要な進歩が達成された。^{[ 2 ]}

リッシュアルゴリズムは、初等関数の積分に用いられます。初等関数とは、指数関数、対数関数、根号関数、三角関数、および四則演算（+ − × ÷）を組み合わせた関数です。ラプラスは、有理関数の不定積分が、有理関数と有理関数の対数の定数倍の有限個の和であることを示し、この問題を有理関数の場合について解決しました。ラプラスが提案したアルゴリズムは、通常、微積分学の教科書に記載されています。コンピュータプログラムとしては、1960年代にようやく実装されました。

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

${\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},\,}$

したがって、例えばが^不定積分の結果に含まれる場合、それは積分の中にあると予想される。また、

${\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 関数で結果を返します。積分は次の形式で表されます。${\displaystyle \int {\frac {x+A}{\sqrt {x^{4}+ax^{3}+bx^{2}+cx+d}}}\,dx}$チェビシェフによって解決された（そしてどのような場合かは初歩的である）^{[ 7 ]}が、その厳密な証明は最終的にゾロタレフによって行われた。^{[ 6 ]}

以下は、代数関数と超越関数の両方を含む、より複雑な例です。^{[ 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)}}.}$

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

${\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 ]}

純粋に代数的な関数のケースは部分的に解決され、James H. DavenportによってReduceに実装されました。簡略化のため、平方根と重平方根のみを扱うことができ、一般的な根号や変数間のその他の非二次代数関係を扱うことはできませんでした。^{[ 11 ]}

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

一般的な初等関数に適用されるリッシュアルゴリズムは、アルゴリズムではなく半アルゴリズムです。なぜなら、その操作の一部として、特定の式がゼロと等価であるかどうか（定数問題）、特に定数体においてチェックする必要があるからです。一般的に初等関数とみなされる関数のみを含む式については、そのようなチェックを実行するアルゴリズムが存在するかどうかは不明です（現在の数式処理システムはヒューリスティックを使用しています）。さらに、絶対値関数を初等関数のリストに追加すると、そのようなアルゴリズムは存在しないことがわかっています。リチャードソンの定理を参照してください。

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

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

• Axiom（数式処理システム）
• 閉じた形式の式
• 不完全なガンマ関数
• 積分の一覧
• リウヴィルの定理（微分代数学）
• 非初等積分
• 記号統合

• ブロンスタイン、マヌエル( 1990)。「基本関数の積分」。Journal of Symbolic Computation。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。

• ゲデス、キース・O.、チャポル、スティーブン・R.、ラバーン、ジョージ（1992）。コンピュータ代数のためのアルゴリズム。ボストン、マサチューセッツ州：クルーワー・アカデミック・パブリッシャーズ。pp.  xxii+585。Bibcode ：1992afca.book .....G。doi：10.1007 / b102438。ISBN 0-7923-9259-0。

• Moses, Joel (2012). "Macsyma: 個人的な歴史". Journal of Symbolic Computation . 47 (2): 123–130 . doi : 10.1016/j.jsc.2010.08.018 .

• Risch, RH (1969). 「有限項の積分問題」 .アメリカ数学会紀要. 139.アメリカ数学会: 167–189 . doi : 10.2307/1995313 . JSTOR 1995313 . 

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

• Rosenlicht, Maxwell (1972). "有限項による積分". American Mathematical Monthly . 79 (9). Mathematical Association of America: 963–972 . doi : 10.2307/2318066 . JSTOR 2318066 . 

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