リッシュのアルゴリズムのソースを表示

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

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

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

== 概説 ==

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

[[ピエール＝シモン・ラプラス]]は、被積分関数が[[有理関数]]である場合の不定積分を行うアルゴリズムを得ていた。すなわち有理関数の不定積分は、有理関数と、有理関数の対数関数の有限個の和で書けることを示した。このアルゴリズムは解析学の教科書にもしばしば載っているが<ref>{{cite book | 和書 | author=杉浦光夫 | title=解析入門 | year=1980 | publisher=東京大学出版会 | series=基礎数学 | volume=I | id=ISBN 978-4130620055 }}</ref>、[[コンピュータ]]上に実装されたのは[[1960年代]]に入ってからである。

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

:<math> f = \sum_{i=1}^n \alpha_i \frac{u_i^{\prime}}{u_i} + v^\prime</math>

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

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

: <math> (f \cdot e^g)' = (f^\prime + f\cdot g^\prime)\cdot e^g </math>

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

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

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

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

== 実装例 ==

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

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

: <math>f(x) = \frac{(x+1)^2+ (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''| を追加すると、その範囲の数式の零判定を行うアルゴリズムは存在しないことが既に示されている（これはリッシュのアルゴリズムに限らず、初等関数を含む数式を処理するアルゴリズムの構築全般に関わる根本的な困難である）。{{see|{{ill2|リチャードソンの定理|en|Richardson's theorem}}}}

== 脚注 ==
{{reflist}}

== 参考文献 ==
* {{cite journal | author=R. H. Risch | title= The Problem of Integration in Finite Terms | journal= Transactions of the American Mathematical Society | year= 1969 | volume=139 | pages= 167–189 | doi=10.2307/1995313 | url=http://www.ams.org/journals/tran/1969-139-00/S0002-9947-1969-0237477-8/S0002-9947-1969-0237477-8.pdf}}
* {{cite journal | author=Maxwell Rosenlicht | title=Integration in finite terms | journal=American Mathematical Monthly | year= 1972 | volume=79 | pages=963–972 | doi=10.2307/2318066}}
* {{cite book | author=Geddes, Czapor, Labahn| title=Algorithms for Computer Algebra | publisher=Kluwer Academic Publishers | year=1992 | id=ISBN 0-7923-9259-0}}
* {{cite book | author=Manuel Bronstein | title=Symbolic Integration | volume=I | publisher=Springer | year=2005 | id=ISBN 3-540-21493-3}}
* {{cite paper | author=Manuel Bronstein | title=Symbolic Integration Tutorial | date=1998 | url=http://www-sop.inria.fr/cafe/Manuel.Bronstein/publications/issac98.pdf }}
*[http://mathworld.wolfram.com/RischAlgorithm.html リッシュのアルゴリズムに関する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 (数式処理システム)|Axiom]] - リッシュのアルゴリズムを部分的に実装している[[計算機代数]]システム

{{DEFAULTSORT:りつしゆのあるこりすむ}}
[[Category:数学に関する記事]]
[[Category:解析学]]
[[Category:代数学]]
[[Category:数式処理システム]]