리슈 알고리즘

기호 계산에서 리슈 알고리즘(Risch algorithm)은 일부 컴퓨터 대수학 시스템에서 부정적분을 찾는 데 사용되는 부정 적분 방법이다. 이 알고리즘은 1968년에 이 알고리즘을 개발한 컴퓨터 대수학 전문가인 미국의 수학자 로버트 헨리 리슈의 이름을 따서 명명되었다.

이 알고리즘은 적분 문제를 대수학 문제로 변환한다. 이 알고리즘은 적분되는 함수의 형태와 유리 함수, 거듭제곱근, 로그 (수학), 지수 함수를 적분하는 방법에 기반을 둔다. 리슈는 이 알고리즘을 판정 절차라고 불렀는데, 그 이유는 함수가 초등함수를 부정적분으로 갖는지 여부를 결정하고, 갖는다면 그 부정적분을 결정하는 방법이기 때문이다. 그러나 이 알고리즘이 주어진 함수의 원시 함수가 실제로 초등함수로 표현될 수 있는지 여부를 식별하는 데 항상 성공하는 것은 아니다.

리슈 알고리즘의 완전한 설명은 100페이지가 넘는다. 리슈-노먼 알고리즘은 1976년 아서 노먼이 개발한 더 간단하고 빠르지만 덜 강력한 변형이다.

브라이언 L. 밀러는 혼합된 초월-대수 적분의 로그 부분을 계산하는 데 상당한 진전을 이루었다.

설명

리슈 알고리즘은 초등함수를 적분하는 데 사용된다. 초등함수는 지수 함수, 로그 함수, 거듭제곱근, 삼각 함수 및 4가지 산술 연산(+ − × ÷)을 합성하여 얻는 함수이다. 라플라스는 유리 함수의 경우에 이 문제를 해결했으며, 유리 함수의 부정적분은 유리 함수와 유리 함수의 로그에 상수를 곱한 유한 개의 항들의 합으로 이루어진다는 것을 보였다. 라플라스가 제안한 이 알고리즘은 일반적으로 미적분학 교과서에 기술되어 있으며, 컴퓨터 프로그램으로서는 1960년대에 최종적으로 구현되었다.

리우빌은 리슈 알고리즘으로 해결되는 문제를 정식화했다. 리우빌은 해석적 방법을 통해 방정식 g′ = f에 대한 초등적 해 g가 존재한다면, f에 의해 생성된 필드에 상수 α_i와 함수 u_i 및 v가 존재하여 해가 다음과 같은 형태를 갖는다는 것을 증명했다.

$g=v+\sum _{i<n}{\alpha }_i\ln (u_i)$

리슈는 리우빌 형태의 유한한 함수 집합만을 고려할 수 있는 방법을 개발했다.

리슈 알고리즘에 대한 직관은 미분 하에서의 지수 함수와 로그 함수의 동작에서 비롯된다. 미분 가능 함수인 f와 g에 대해 함수 f e^g의 경우 다음이 성립한다.

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

따라서 e^g가 부정적분의 결과에 있다면 적분 내부에 있을 것으로 예상된다. 또한 다음과 같이

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

적분 결과에 (ln g)ⁿ이 있다면 로그의 몇 가지 거듭제곱만 예상해야 한다.

문제 예시

초등 원시 함수를 찾는 것은 세부 사항에 매우 민감하다. 예를 들어, 다음 대수 함수(1993년 앙리 코앙이 sci.math.symbolic에 게시한)는 버전 13 이후의 매스매티카가 보여주듯이 초등 원시 함수를 갖는다(그러나 매스매티카는 이 적분을 계산하기 위해 리슈 알고리즘을 사용하지는 않는다):

$f(x)=\frac{x}{\sqrt{x^4+10x^2-96x-71}},$

즉:

$\begin{array}{cc}F(x)=-\frac{1}{8}\ln & ((x^6+15x^4-80x^3+27x^2-528x+781)\sqrt{x^4+10x^2-96x-71}\\ & -(x^8+20x^6-128x^5+54x^4-1408x^3+3124x^2+10001))+C.\end{array}$

그러나 상수항 71이 72로 변경되면 원시 함수를 초등 함수로 표현할 수 없으며, FriCAS도 마찬가지다. 일부 컴퓨터 대수학 시스템은 여기서 비초등 함수(예: 타원 적분)로 표현되는 원시 함수를 반환할 수 있는데, 이는 리슈 알고리즘의 범위를 벗어난다. 예를 들어, 매스매티카는 EllipticPi 및 EllipticF 함수를 포함하는 결과를 반환한다. $\int \frac{x+A}{\sqrt{x^4+a{x}^3+b{x}^2+cx+d}}dx$ 형태의 적분은 체비쇼프에 의해 해결되었으나 (그리고 어떤 경우에 초등적인지), 이에 대한 엄밀한 증명은 최종적으로 졸로타레프에 의해 이루어졌다.

다음은 대수 함수와 초월함수를 모두 포함하는 더 복잡한 예시이다.

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

사실 이 함수의 원시 함수는 치환 $u=x+\sqrt{x+\ln x}$를 사용하여 찾을 수 있는 비교적 짧은 형태를 갖는다(SymPy는 이를 풀 수 있지만 FriCAS는 리슈 알고리즘에서 "구현 불완전(상수 잔차)" 오류와 함께 실패한다):

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

일부 데이븐포트 "정리"는 여전히 명확하게 밝혀지고 있다. 예를 들어 2020년에 그러한 "정리"에 대한 반례가 발견되었으며, 결국 초등 원시 함수가 존재하는 것으로 밝혀졌다.

구현

리슈의 이론적 알고리즘을 컴퓨터로 효과적으로 실행할 수 있는 알고리즘으로 변환하는 것은 복잡한 작업이었고 오랜 시간이 걸렸다.

순수 초월 함수(다항식의 근을 포함하지 않는)의 경우는 비교적 쉽고 대부분의 컴퓨터 대수학 시스템에 일찍 구현되었다. 첫 번째 구현은 리슈의 논문이 발표된 직후 조엘 모제스에 의해 Macsyma에서 이루어졌다.

순수 대수 함수의 경우는 제임스 H. 데이븐포트에 의해 Reduce에서 부분적으로 해결되고 구현되었다. 단순화를 위해 이 구현은 제곱근과 반복 제곱근만 처리할 수 있었고 일반적인 거듭제곱근이나 변수 간의 다른 비-이차 대수적 관계는 처리할 수 없었다.

일반적인 경우는 Manuel Bronstein에 의해 Axiom의 전신인 Scratchpad에서 해결되고 거의 완전히 구현되었으며, 현재 github에서 활발한 리슈 및 기타 알고리즘 개발이 진행 중인 Axiom의 포크인 FriCAS가 있다. 그러나 이 구현에는 특수 사례에 대한 일부 분기가 완전히 포함되지 않았다. 2025년 현재, 리슈 알고리즘의 완전한 구현은 알려져 있지 않다.

판정 가능성

일반적인 초등 함수에 적용되는 리슈 알고리즘은 알고리즘이 아니라 준알고리즘이다. 이는 특정 표현식이 0과 동등한지(상수 문제)를 확인해야 하기 때문이며, 특히 상수 필드에서 그렇다. 일반적으로 초등함수로 간주되는 함수만 포함하는 표현식의 경우, 그러한 검사를 수행하는 알고리즘이 존재하는지는 알려져 있지 않다(현재 컴퓨터 대수학 시스템은 휴리스틱을 사용한다). 더욱이, 초등 함수의 목록에 절댓값 함수를 추가하면 그러한 알고리즘이 존재하지 않는다는 것이 알려져 있다. 리처드슨 정리를 참조하라.

이 문제는 다항식 나눗셈 알고리즘에서도 발생한다. 이 알고리즘은 계수가 항등적으로 소멸하는지 정확히 판단할 수 없으면 실패한다. 거의 모든 비자명한 다항식 관련 알고리즘은 다항식 나눗셈 알고리즘을 사용하며, 리슈 알고리즘도 마찬가지이다. 상수 필드가 계산 가능, 즉 x에 의존하지 않는 요소에 대해 영-동등성 문제가 판정 가능하면 리슈 알고리즘은 완전한 알고리즘이다. 계산 가능한 상수 필드의 예로는 ℚ 및 ℚ(y)가 있으며, 각각 유리수와 유리수 계수를 갖는 y의 유리 함수이며, 여기서 y는 x에 의존하지 않는 미지수이다.

이것은 가우스 소거법 행렬 알고리즘(또는 행렬의 영공간을 계산할 수 있는 모든 알고리즘)에서도 문제인데, 이 역시 리슈 알고리즘의 많은 부분에 필요하다. 가우스 소거법은 피벗이 항등적으로 0인지 정확히 판단할 수 없으면 잘못된 결과를 산출한다.

같이 보기

• 닫힌 형식
• 불완전 감마 함수
• 적분표
• 리우빌의 정리 (미분 대수)
• 초등적이지 않은 원시함수
• 기호 적분

참고 자료

• Bronstein, Manuel (1990). 《Integration of elementary functions》. 《Journal of Symbolic Computation》 9. 117–173쪽. doi:10.1016/s0747-7171(08)80027-2. 

• Bronstein, Manuel (1998). 《Symbolic Integration Tutorial》 (PDF). 《ISSAC'98, Rostock (August 1998) and Differential Algebra Workshop, Rutgers》. 

• Bronstein, Manuel (2005). 《Symbolic Integration I》. Springer. ISBN 3-540-21493-3. 

• Davenport, James H. (1981). 《On the integration of algebraic functions》. Lecture Notes in Computer Science 102. Springer. ISBN 978-3-540-10290-8. 

• Geddes, Keith O.; Czapor, Stephen R.; Labahn, George (1992). 《Algorithms for computer algebra》. Boston, MA: Kluwer Academic Publishers. xxii+585쪽. Bibcode:1992afca.book.....G. doi:10.1007/b102438. ISBN 0-7923-9259-0. 

• Moses, Joel (2012). 《Macsyma: A personal history》. 《Journal of Symbolic Computation》 47. 123–130쪽. doi:10.1016/j.jsc.2010.08.018. 

• Risch, R. H. (1969). 《The problem of integration in finite terms》. 《Transactions of the American Mathematical Society》 139 (American Mathematical Society). 167–189쪽. doi:10.2307/1995313. JSTOR 1995313. 

• Risch, R. H. (1970). 《The solution of the problem of integration in finite terms》. 《Bulletin of the American Mathematical Society》 76. 605–608쪽. doi:10.1090/S0002-9904-1970-12454-5. 

• Rosenlicht, Maxwell (1972). 《Integration in finite terms》. 《American Mathematical Monthly》 79 (Mathematical Association of America). 963–972쪽. doi:10.2307/2318066. JSTOR 2318066. 

외부 링크

• Bhatt, Bhuvanesh. “리슈 알고리즘” (영어). 《Wolfram MathWorld》. Wolfram Research.