リッシュのアルゴリズム

数学におけるリッシュのアルゴリズム（Risch Algorithm、リッシュの算法）とは不定積分を行う（すなわち、ある式の原始関数を求める）アルゴリズムであり、数学者ロバート・H・リッシュに因む。その鍵は不定積分の問題を微分代数の問題へと変換することである。代数学の一分野である微分代数においては、抽象的な微分操作の下での関数の振る舞いが考察される。このことは、不定積分を困難にしている指数関数、対数関数およびべき乗をブラックボックスとして扱う上で都合が良い。

リッシュは1968年にこのアルゴリズムを開発したが、それを決定手順と呼んでいた。このアルゴリズムは与えられた関数がその不定積分を初等関数の範囲に持つかどうかを決定するものだからである。そうして存在するのであれば、それを具体的に与える。

1976年には高速だが一般性の低いリッシュ＝ノーマンのアルゴリズムが開発されている。

概説

リッシュのアルゴリズムが不定積分を実行できる対象は初等関数すなわち、四則演算 (+, −, ×, ÷)、指数関数、そしてこれらの逆関数の組み合わせで得られる関数である。特に指数関数の逆関数として得られる対数関数や、複数回の乗算の逆関数として得られる有理数による冪も初等関数に含まれる。複素数の範囲で考えることで、三角関数も指数関数として扱うことができる。

ピエール＝シモン・ラプラスは、被積分関数が有理関数である場合の不定積分を行うアルゴリズムを得ていた。すなわち有理関数の不定積分は、有理関数と、有理関数の対数関数の有限個の和で書けることを示した。このアルゴリズムは解析学の教科書にもしばしば載っているが、コンピュータ上に実装されたのは1960年代に入ってからである。

ジョゼフ・リウヴィルは、後にリッシュのアルゴリズムによって解決された問題を初めて厳密に定式化した。リウヴィルは解析学の手法により以下の定理を証明した。方程式 g′ = f に初等関数の解 g が存在すれば、n 個（有限個）の定数 α_i と n + 1 個の初等関数 u_i および v が存在し、f を

[math] f = \sum_{i=1}^n \alpha_i \frac{u_i^{\prime}}{u_i} + v^\prime[/math]

の形に書き直せる。そうしてリッシュのアルゴリズムによれば、u_i および v の候補として考慮すべき初等関数の数は有限個となる。

リッシュのアルゴリズムを直感的に理解するために、指数関数および対数関数が微分演算に対しどのように振舞うかを見てみよう。例えば関数 fe^g （ここで f および g は微分可能な関数）について

[math] (f \cdot e^g)' = (f^\prime + f\cdot g^\prime)\cdot e^g [/math]

であるから、不定積分をした結果の式中に e^g が含まれているとすれば、それは被積分関数の中にも含まれていなければならない。 さらに

[math] (f \cdot(\ln g)^n)' = f^\prime (\ln g)^n + n f \frac{g^\prime}{g} (\ln g)^{n-1} [/math]

であるから、不定積分の結果の式に (ln g)ⁿ が含まれているとすれば、被積分関数の中にも (ln g)^m （m は n 以下）が含まれていなければならない。

なおこのアルゴリズムから、ガウス関数 exp(−x²) の原始関数（ガウスの誤差関数 erf の定数倍）は初等関数の範囲では表せないという事実が従う。

実装例

リッシュのアルゴリズムをプログラミング言語によりコンピュータで実行できる形に書き下すことは困難であり、ヒューリスティクスの利用を含めた多数の改変を施す必要がある。実際、2008年5月現在ではこれを完全に実装したソフトウェアは未だ存在しない。ただし、いくつかの計算機代数システムはこれを部分的に実装している。

以下に、（2008年5月現在で）既存のいかなるソフトウェアも不定積分を計算できないような例を示す：

[math]f(x) = \frac{x^2+2x+1+ (3x+1)\sqrt{x+\ln x}}{x\,\sqrt{x+\ln x}(x+\sqrt{x+\ln x})}.[/math]

しかしこの式には短い不定積分が存在する：

[math]F(x) = 2 (\sqrt{x+\ln x} + \ln(x+\sqrt{x+\ln x})) + C.[/math]

なお「リッシュのアルゴリズム」は厳密な意味での「アルゴリズム」ではない。これはリッシュのアルゴリズムの中では（通常の数学の場合と同様に）与えられた数式が零であるかを必ず判定できると仮定しているが，実際には一般の数式に対してはそのような「零判定」処理を行うアルゴリズムは構成できないためである。数式の範囲を通常の「初等関数」（多項式、有理関数、代数関数、三角関数、指数関数、対数関数の組合わせ）に限定しても、数式の零判定（あるいは等式判定）を行えるアルゴリズムは知られていない（これが計算機代数システムが実装においてヒューリスティクスにも依存せざるを得ない理由である）。さらに初等関数に絶対値関数 |x| を追加すると、その範囲の数式の零判定を行うアルゴリズムは存在しないことが既に示されている（これはリッシュのアルゴリズムに限らず、初等関数を含む数式を処理するアルゴリズムの構築全般に関わる根本的な困難である）。

参照: [[リチャードソンの定理]]

参考文献

• R. H. Risch (1969). “The Problem of Integration in Finite Terms”. Transactions of the American Mathematical Society 139: 167–189. doi:10.2307/1995313. http://www.ams.org/journals/tran/1969-139-00/S0002-9947-1969-0237477-8/S0002-9947-1969-0237477-8.pdf. 
• Maxwell Rosenlicht (1972). “Integration in finite terms”. American Mathematical Monthly 79: 963–972. doi:10.2307/2318066. 
• Geddes, Czapor, Labahn (1992). Algorithms for Computer Algebra. Kluwer Academic Publishers. ISBN 0-7923-9259-0. 
• Manuel Bronstein (2005). Symbolic Integration. Springer. ISBN 3-540-21493-3. 
• テンプレート:Cite paper
• リッシュのアルゴリズムに関するMathWorldの項目

• 黒河龍三：「初等函数に関するリウギュの研究」、日本数学物理学会誌 第1巻（1927年）, 頁17–27、頁146–155; 第3巻（1929年）頁8–18, 頁285–296。
• 一松信:「付録A．初等関数に関するLiouvilleの理論」、所収：「初等関数の数値計算」、教育出版（1974年11月20日），頁192–209。
• 佐々木建昭：「初等関数の不定積分」所収：岩波講座情報科学23「数と式と文の処理」，第4章4節（頁120–137）、岩波書店（1981年12月10日）。※ Rischの算法を紹介している。
• 一松信：「リッシュの算法について」所収：一松信「解析学序説 上巻（新版）」補章5節、頁227–230、裳華房、ISBN 978-4-7853-1030-1（1981年12月25日）。※ 概要の記述。

関連項目

• 不定積分#性質
• リウヴィルの定理 (微分代数)
• 記号積分
• Axiom - リッシュのアルゴリズムを部分的に実装している計算機代数システム