リッシュのアルゴリズム

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

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

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

概説

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

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

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

f=\sum _{i=1}^{n}\alpha _{i}{\frac {u_{i}^{\prime }}{u_{i}}}+v^{\prime }

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

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

(f\cdot e^{g})'=(f^{\prime }+f\cdot g^{\prime })\cdot e^{g}

なので、 e^g が不定積分の結果に含まれていたならば、原始関数の中にも含まれていなければならない。さらに

(f\cdot \ln ^{n}g)'=f^{\prime }\ln ^{n}{g}+nf{\frac {g^{\prime }}{g}}\ln ^{n-1}{g}

なので、 lnⁿg が不定積分の結果に含まれていたならば、原始関数の中にも ln^mg （m は n 以下）が含まれていなければならない。

なおこのアルゴリズムから、ガウス関数の原始関数（ガウスの誤差関数 erf の定数倍）は初等関数では書けないという事実が従う。

実装例

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

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

f(x)={\frac {x^{2}+2x+1+(3x+1){\sqrt {x+\ln x}}}{x\,{\sqrt {x+\ln x}}(x+{\sqrt {x+\ln x}})}}

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

F(x)=2({\sqrt {x+\ln x}}+\ln(x+{\sqrt {x+\ln x}}))+C

なお「リッシュのアルゴリズム」は厳密な意味では「アルゴリズム」ではない。これはリッシュのアルゴリズムが利用する下請けアルゴリズムに、「ある式が零に等しいかどうかを調べるアルゴリズム」が含まれるせいである。「初等関数」の範囲として常識的なものを採る限り、そのような下請けアルゴリズムが存在するかどうかは知られていない（これが既存の計算機代数システムがヒューリスティクスに依存せざるを得ない理由である）。さらに絶対値関数 abs(x) を初等関数として含めることにすると、そのような下請けアルゴリズムは存在しないことが知られている。

「en:Richardson's theorem」を参照

参考文献

^ 杉浦光夫『解析入門』 I、東京大学出版会〈基礎数学〉、1980年。ISBN 978-4130620055。

R. H. Risch (1969). “The Problem of Integration in Finite Terms”. Transactions of the American Mathematical Society 139: 167–189. doi:10.2307/1995313. [1]
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. I. Springer. ISBN 3-540-21493-3
Manuel Bronstein (1998). Symbolic Integration Tutorial.
リッシュのアルゴリズムに関するMathWorldの項目

概説

実装例

参考文献

関連項目