리스치 알고리즘

에 대한 일련의 기사의 일부
미적분학.
기본 정리 라이프니즈 적분 규칙 함수의 한계 연속성 평균값 정리 롤의 정리
미분 정의들 파생상품(일반화) 미분 극소수의 함수의. 총계 개념 분화 표기법 제2차 파생상품 암묵적 분화 로그 분화 관련금리 테일러의 정리 규칙 및 ID 합계 제품 체인 힘 지수 라피탈의 법칙 반비례 라이프니즈 장군 파아디 브루노 공식 레이놀즈.
적분 통합 목록 적분 변환 정의들 해독제 적분(불량) 리만 적분 르베그 통합 등고선 통합 역함수의 적분 통합 기준 부품. 디스크 원통 조개 대체(트리거, 위어스트라스, 오일러) 오일러의 공식 부분분수 순서변경 환원공식 통합 기호 아래 차별화 리스치 알고리즘
시리즈 기하학(산술-기하계) 조화 교대로 힘 이항체 테일러 수렴시험 합계한계(기간시험) 비율 뿌리 적분 직접 비교 한계비교 교대계열 코시 응결 디리클레 아벨
벡터 그라데이션 발산 컬 라플라시안 방향파생상품 정체성 정리 그라데이션 그린스 스톡스 발산 일반화 스톡스
다변량 형식주의 매트릭스 텐서 외부 기하학 정의들 부분파생상품 다중 적분 라인 적분 표면 적분 부피 적분 야코비안 헤시안
전문화된 분수 말리아빈 스토카스틱 변형
잡다한 프레살쿨루스 역사 용어집 주제 목록 통합 비 분석
v t

상징적 계산에서, Risch 알고리즘은 해독제를 찾기 위해 일부 컴퓨터 대수 시스템에서 사용되는 무기한 통합의 방법이다. 1968년에 개발한 컴퓨터 대수학 전문가인 미국의 수학자 로버트 헨리 리쉬의 이름을 따서 지은 것이다.

알고리즘은 통합의 문제를 대수학의 문제로 변환한다. 그것은 통합되는 함수의 형태와 합리적인 함수, 급진적 함수, 로그, 지수함수를 통합하는 방법에 기초한다. Risch는 이것이 함수에 비한정적분으로 기본적인 기능이 있는지 여부를 결정하기 위한 방법이고, 만약 있다면, 그 비한정적분을 결정하기 위한 방법이기 때문에 이것을 결정 절차라고 말했다. 그러나 알고리즘이 실제로 주어진 함수의 해독제가 기초함수의 관점에서 표현될 수 있는지 여부를 확인하는 데 항상 성공하는 것은 아니다.^{[example needed]}

Risch 알고리즘의 전체 설명은 100페이지가 넘는다.^[1] Risch-Norman 알고리즘은 1976년에 Arthur Norman에 의해 개발된 더 단순하고 빠르며 덜 강력하다.

설명

Risch 알고리즘은 기본 기능을 통합하는 데 사용된다. 지수, 대수, 급진, 삼각함수, 4개의 산술 연산(+ - × ÷)을 합성하여 얻은 함수들이다. 라플레이스는 이성함수의 무한정 적분은 이성함수이며 이성함수의^{[citation needed]} 로그의 유한한 수배수라는 것을 보여주었기 때문에 이성함수의 경우를 위해 이 문제를 해결했다. 라플레이스에 의해 제안된 알고리즘은 보통 미적분 교과서에 설명되어 있다; 컴퓨터 프로그램으로서, 그것은 1960년대에 마침내 시행되었다.^{[citation needed]}

리우빌은 리슈 알고리즘에 의해 해결되는 문제를 공식화했다. Liouville은 분석적 수단으로 만약 g′ = f 방정식에 기초 솔루션 g가 있다면, f에 의해 생성된 필드에 상수 α와_i 함수 u와_i v가 존재하여 솔루션이 형태라는 것을 증명했다.

${\displaystyle g=v+\sum _{i<n}\reason _{i}\ln(u_{i}})}$

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

Risch 알고리즘에 대한 직감은 분화하에서의 지수함수와 로그함수의 동작에서 비롯된다. f와 g가 서로 다른 함수인 f e 함수에^g 대해 우리는

$\displaystyle \left(f\cdot e^{g}\오른쪽)^{\premy }=\premy }\premy }+f\cdot g^{\premy }\cdot e^{g}\,}$

따라서 e가^g 무기한 통합의 결과인 경우, e는 적분 내부에 있을 것으로 예상해야 한다. 또한, 다음과 같이.

${\displaystyle \f\cdot(\lng)^{n}\오른쪽)^{\prime }=f^{}\prime }\preme }{nf}+{g^{g^{}}}{n-1}{n-1}$

만약 (ln g)ⁿ 통합의 결과라면, 로그의 몇 가지 힘만 예상해야 한다.

문제 예

기본적인 해독제를 찾는 것은 세부적인 것에 매우 민감하다. 예를 들어, 버전 13 이후 울프램 매티매티카에서 볼 수 있듯이 다음과 같은 대수적 함수는 기본적인 반변성을 가지고 있다.^[2][3]

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

즉:

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

그러나 71이라는 상수 용어를 72로 바꾸면, FriCAS가 보여주는 것처럼 기본적인 기능 면에서 해독제를 나타낼 수 없다. 일부 컴퓨터 대수 시스템(버전 13 이전의 mathematica)은 여기에서 Risch 알고리즘의 범위 밖에 있는 비원소 함수(즉 타원형 통합)의 측면에서 해독제를 반환할 수 있다.

다음은 대수적 기능과 초월적 기능을 모두 포함하는 보다 복잡한 예다.^[4]

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

실제로 이 함수의 해독제는 대체${\displaystyle }$u =${\displaystyle x}$ +${\displaystyle \sqrt{}x\sqrt{}}$ + ${\displaystyle \sqrt{\ln x}}$ x ${\$ x$}}}($SymPy는 해결할 수 있는 반면, Risch 알고리즘의 "실행 미완성(일정 잔류물)" 오류로 인해 실패한다.

${\displaystyle F(x)=2\왼쪽({\sqrt {x+\ln x}}}\ln \ln \ln) \left(x+{\sqrt {x+\ln x}\오른쪽)+C+C.}$

실행

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

순수 초월함수(다항식의 뿌리를 포함하지 않는)의 경우는 비교적 쉬우며 대부분의 컴퓨터 대수 체계에서 초기에 구현되었다. 첫 실행은 리쉬의 논문 발표 직후 조엘 모세가 맥시마에서 했다.^[5]

순전히 대수함수의 경우는 제임스 H. 데이븐포트에 의한 감소에서 해결되어 실행되었다.^[6]

일반적인 경우는 마누엘 브론스타인(Manuel Bronstein)에 의해 악시오름의 전구인 스크래치패드에서 해결되어 시행되었으며, 현재는 포크 FriCAS(Fork FriCAS)에서 개발되고 있다.^[7]

결정성

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

이 문제는 다항분할 알고리즘에서도 발생한다는 점에 유의하십시오. 계수가 동일하게 소멸되는지 여부를 정확하게 판단할 수 없는 경우 이 알고리즘은 실패할 것이다.^[8] 사실상 모든 다항식 알고리즘은 포함된 Risch 알고리즘인 다항식 분할 알고리즘을 사용한다. 상수 필드를 계산할 수 있는 경우, 즉, x에 의존하지 않는 요소의 경우 영등가 문제는 디커블할 수 있는 경우, Risch 알고리즘은 완전한 알고리즘이다. 계산 가능한 상수 필드의 예로는 Q와 Q(y), 즉 각각 합리적인 수 계수를 갖는 y의 합리적 수 및 합리적인 함수가 있으며, 여기서 y는 x에 의존하지 않는 불확정이다.

이는 또한 Risch 알고리즘의 많은 부분에도 필요한 가우스 제거 매트릭스 알고리즘(또는 매트릭스의 nullspace를 계산할 수 있는 모든 알고리즘)의 문제이기도 하다. 가우스 제거는 피벗이 동일한 0인지^{[citation needed]} 정확하게 판단할 수 없는 경우 부정확한 결과를 산출한다.

참고 항목

• 상징적 통합
• 리우빌의 정리(차등대수)
• Axiom(컴퓨터 대수 체계)
• 불완전 감마 함수
• 비원소 적분
• 통합 목록

메모들

참조

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

• Bronstein, Manuel (1998). "Symbolic Integration Tutorial" (PDF). {{cite journal}}: Cite 저널은 필요로 한다. journal= (도움말)

• 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. Vol. 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. pp. 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 (2): 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. American Mathematical Society. 139: 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 (3): 605–608. doi:10.1090/S0002-9904-1970-12454-5.

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

외부 링크

• Bhatt, Bhuvanesh. "Risch Algorithm". MathWorld.