リッシュのアルゴリズム

ウィキペディア

リッシュのアルゴリズム

出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2024/09/01 15:52 UTC 版)

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

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

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

概説

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

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