다항식의 체계

다항 방정식의 시스템(때로는 단순히 다항식 시스템)은 f₁ = 0, ..., f = 0의 동시 방정식 집합이며, 여기서_h f는_i 일부 필드 k에 대한₁ x, ..., x와_n 같은 여러 변수의 다항식이다.

다항식 시스템의 해법은 일부 대수적으로 닫힌 k의 필드 확장자 K에 속하는 xs에_i 대한 값 집합이며, 모든 방정식을 참으로 만든다. k가 합리적인 수의 분야일 때, K는 일반적으로 복합수의 분야로 가정되는데, 각 용액은 복합수의 하위 분야인 k의 분야 확장에 속하기 때문이다.

이 글은 해결 방법, 즉 모든 해결책을 찾거나 설명하는 방법에 관한 것이다. 이러한 방법들은 컴퓨터에 구현하기 위해 고안된 것이므로, 계산(평등 시험 포함)이 쉽고 효율적인 분야인 합리적 숫자와 유한한 분야를 강조한다.

특정 세트에 속하는 해결책을 찾는 것은 일반적으로 훨씬 더 어려운 문제로서 주어진 한정된 분야에서 해결책의 경우를 제외하고는 이 글의 범위 밖에 있다. 모든 성분이 정수 또는 합리적인 숫자인 용액의 경우 Diopantine 방정식을 참조하십시오.

정의

다항식 방정식의 매우 간단한 예는 다음과 같다.

${\displaystyle {\displaysty}x^{2}-1&=0\\y^{2}-4&=0.\end{정렬}}}$

그것의 해결책은 네 쌍(x,y) = (1, 2), (-1, 2), (1, -2)이다.^[1]

이 글의 주제는 이 예에 대한 일반화 연구와 해결책 계산에 사용되는 방법에 대한 설명이다.

다항식 또는 다항식의 시스템은 방정식의 집합이다.

${\displaystyle {\datastyled}f_{1}\좌측(x_{1},\ldots,x_{m}\우측)&=0\\\\&\\;\vdots \\\f_{n}\n}좌측(x_{1}, }우측)&#0,\end{liged}}}}}}}}$

여기서 각 f는_h 정수 계수가 있는 x₁, ..., x의_m 다항식 또는 일부 고정된 필드(흔히 합리적 수 또는 유한 필드)의 계수다.^[1] 실제 숫자와 같은 다른 계수의 분야는 그 요소들이 컴퓨터로 표현될 수 없기 때문에 덜 자주 사용된다(실수의 근사치만 계산에 사용할 수 있으며, 이러한 근사치는 항상 합리적인 숫자다).

다항식 시스템의 해법은 다항식의 모든 방정식을_m 만족시키는 (x₁, ..., x)의 값의 튜플이다. 해결책은 복잡한 수에서 찾거나 계수를 포함하는 대수적으로 닫힌 분야에서 더 일반적으로 찾는다. 특히 특징 0에서는 모든 복잡한 해결책을 모색한다. 현실적이거나 합리적인 해결책을 찾는 것은 이 글에서 고려되지 않은 훨씬 더 어려운 문제들이다.

예를 들어, 시스템의 해결책들이 항상 유한하지는 않다.

${\displaystyle {\displaysty}x(x-1)&=0\x(y-1)&=0\end{aigned}}}$

점(x,y) = (1,1)이고 선 x = 0이다.^[2] 용액 집합이 유한한 경우에도 일반적으로 용액의 폐쇄형 표현은 없다(단일 방정식의 경우 이것이 아벨-루피니 정리).

그림에서 볼 수 있는 바스 표면은 3개 변수에서 도 6의 단일 방정식으로 축소된 다항식 용액의 기하학적 표현이다. 그것의 수많은 단수점들 중 일부는 이미지에서 보인다. 그것들은 3개의 변수에서 4개의 도 5 방정식의 시스템 해법이다. 그러한 지나치게 결정된 시스템은 일반적으로 (계수가 특정되지 않은 경우) 해법이 없다. 만약 한정된 수의 해답을 가지고 있다면, 이 숫자는 베주트의 정리로는 최대³ 5 = 125이다. 단, 6도 표면의 단수점의 경우, 최대 용액의 수는 65이며, 바스 표면으로 도달하는 것으로 나타났다.

기본 속성 및 정의

방정식 개수가 변수 개수보다 많으면 시스템이 초과 결정된다. 복잡한 용액이 없는 시스템(또는 계수가 복잡한 숫자가 아닌 경우 계수를 포함하는 대수적으로 닫힌 필드에 용액이 없는 경우)은 일관성이 없다. 힐베르트의 Nullstellensatz에 의해 이것은 1이 방정식의 첫 번째 구성원의 선형 결합(다항식을 계수로 함)임을 의미한다. 무작위 계수로 구성되었을 때, 모든 과결정된 시스템은 일관성이 없다. 예를 들어, 시스템³ x – 1 = 0, x² – 1 = 0은 초과 결정되지만(두 개의 방정식을 가지고 있지만 한 개의 방정식만 알 수 없음) x = 1 용액이 있으므로 일관성이 없다.

방정식의 수가 변수의 수보다 적을 경우 시스템이 충분히 결정되지 않는다. 결정되지 않은 시스템은 일관성이 없거나 한없이 많은 복잡한 해법(또는 방정식의 계수를 포함하는 대수적으로 폐쇄된 분야의 해법)을 가지고 있다. 이것은 특히 힐베르트의 Nullstellensatz와 Krull의 주된 이상적 정리를 수반하는 역학대수의 비견적 결과물이다.

시스템은 한정된 수의 복잡한 해법(또는 대수적으로 닫힌 분야의 해법)을 가지고 있다면 0차원이다. 이 용어는 해답의 대수적 다양성이 차원 0을 가지고 있다는 사실에서 유래한다. 해결책이 무한히 많은 시스템은 양차원이라고 한다.

변수만큼 방정식이 많은 0차원 체계는 때로는 품행이 단정하다고 한다.^[3] 베주트의 정리는 방정식이₁ d, ..., d를_n 갖는 얌전한 체계는 기껏해야₁ d⋅⋅⋅d_n 해답이 있다고 주장한다. 이 바운드는 날카롭다. 모든도가 d와 같으면 이 바운드는 d가ⁿ 되고 변수의 수가 기하급수적으로 된다. (대수의 기본 정리는 특수한 경우 n = 1.)

이러한 지수적 행동은 다항식 시스템의 해결을 어렵게 하며, 예를 들어 25(도 3의 방정식이나 도 2의 5 방정식은 이 경계를 벗어난다)^{[citation needed]}보다 베주트의 한계치가 높은 시스템을 자동으로 해결할 수 있는 해결사가 거의 없는 이유를 설명한다.

해결이란 무엇인가?

다항식 시스템을 풀기 위해 가장 먼저 해야 할 일은 그것이 일관성이 없는 것인지, 0차원인지, 양차원인지를 결정하는 것이다. 이것은 방정식의 왼쪽 측면에 대한 그뢰브너 기초의 계산에 의해 수행될 수 있다. 이 그뢰브너 기준을 1로 줄이면 시스템은 일관성이 없다. 모든 변수에 대해 이 변수의 순수한 힘인 그뢰브너 기초의 일부 요소의 선행 단원이 있는 경우 시스템은 0차원이다. 이 테스트의 경우 최상의 단일 순서(일반적으로 가장 빠른 연산으로 이어지는 순서)는 대개 등급이 매겨진 역 사전 편찬 순서(grevlex)이다.

시스템이 양차원이라면 무한히 많은 해결책을 가지고 있다. 그러므로 그것들을 열거하는 것은 불가능하다. 따라서 이 경우 해결이란 "해결책의 관련 특성을 추출하기 쉬운 해결책의 설명을 찾는 것"만을 의미할 수 있다. 일반적으로 받아들여지는 그런 묘사는 없다. 사실, 대수 기하학의 거의 모든 하위 분야를 포함하는 많은 다른 "관련 특성"이 있다.

양차원 시스템에 관한 그러한 질문의 자연스러운 예는 다음과 같다: 합리적인 숫자에 걸친 다항식 시스템이 한정된 수의 실제 해결책을 가지고 있는지 판단하고 그것들을 계산한다. 이 문제의 일반화는 다항식 시스템의 실제 솔루션 집합의 각 연결된 구성 요소에서 적어도 하나의 해결책을 찾는 것이다. 이러한 문제를 푸는 고전적인 알고리즘은 원통형 대수분해로서, 두 배로 지수적인 계산 복잡성을 가지고 있기 때문에 매우 작은 예를 제외하고는 실제로 사용할 수 없다.

0차원 시스템의 경우, 해결은 모든 해결책을 계산하는 것으로 구성된다. 해결책을 산출하는 데는 두 가지 다른 방법이 있다. 가장 일반적인 방법은 실제 또는 복잡한 솔루션에 대해서만 가능하며, 솔루션의 숫자 근사치를 출력하는 것으로 구성된다. 그런 해답을 숫자라고 한다. 솔루션은 근사치의 오차에 대한 바운드가 제공되고, 이 바운드가 다른 솔루션을 분리하는 경우에 인증된다.

해답을 표현하는 다른 방법은 대수학이라고 한다. 0차원 시스템의 경우 해법이 시스템 계수의 필드 k의 대수적 폐쇄에 속한다는 사실을 이용한다. 대수학적 폐쇄에서 해결책을 나타내는 몇 가지 방법이 있는데, 아래에서 이에 대해 논의한다. 이들 모두 하나 또는 여러 개의 일변량 방정식을 풀어서 해답의 수치 근사치를 계산할 수 있게 한다. 이 계산의 경우 근사치 계수를 갖는 다항식의 뿌리를 계산하는 것은 매우 불안정한 문제이기 때문에, 용액당 하나의 일변량 다항식만 푸는 것을 포함하는 표현을 사용하는 것이 바람직하다.

확장

삼각 방정식

삼각 방정식은 등식 g = 0이고, g는 삼각 다항식이다. 그러한 방정식은 그 안에 있는 사인 및 코사인(합과 차이 공식 사용)을 확장하고, sin(x)과 cos(x)를 두 개의 새로운 변수 s와 c로 대체하고, 새로운 방정식 s² + c² – 1 = 0을 추가함으로써 다항식 시스템으로 변환될 수 있다.

예를 들어, 정체성 때문에

${\displaystyle \cos(3x)=4\cos ^{3}(x)-3\cos(x),}$

방정식의 해결

${\displaystyle \sin ^{3}(x)+\cos(3x)=0}$

다항식 시스템 해결과 같다.

${\displaystyle {\displaysty}s^{3}+4c^{3}-3c&=0\\s^{2}+c^{2}-1&=0.\end{case}}}$

이 시스템의 각 용액(c₀₀, s)에는 0 ≤ x < 2 π과 같은 방정식의 고유한 용액 x가 있다.

이 간단한 예시의 경우, 시스템이 방정식보다 풀기 쉬운지, 그렇지 않은지는 불분명할 수 있다. 좀 더 복잡한 예에서는 방정식을 직접 푸는 체계적인 방법이 부족한 반면, 소프트웨어는 자동으로 해당 시스템을 풀 수 있는 것이 특징이다.

유한 분야의 솔루션

q요소로 유한한 필드 k에 걸쳐 시스템을 풀 때, 주로 k의 해법에 관심이 있다. k의 원소는 정확히^q x – x = 0 등식의 해법이기 때문에 k로 용액을 제한하기 위해서는_i 각 변수 x에_i^q 대해_i x – x = 0 등식을 추가하면 된다.

수치 필드 또는 소수점 순서가 아닌 유한한 필드의 계수

대수적 숫자 필드의 원소는 대개 단변 다항식을 만족하는 필드의 생성기에서 다항식으로 표현된다. 계수가 숫자 필드에 속하는 다항식 시스템으로 작업하려면 이 생성기를 새 변수로 간주하고 생성기의 방정식을 시스템의 방정식에 추가하면 충분하다. 따라서 숫자 필드에 대한 다항식 시스템의 해결은 합리적인 숫자에 대한 또 다른 시스템의 해결로 축소된다.

예를 들어 시스템에 $2{\displaystyle \sqrt{\mathrm{}}}$ ${\$2}이$($가) 포함되어 있는 경우, r₂² – 2 = 0을 추가하고 다른 방정식에서 $2{\displaystyle \sqrt{\mathrm{}}}${\$displaystyle${\$sqrt{2}}}$을₂ r로$$ 대체하여 합리적인 숫자 이상의 시스템을 얻는다.

유한 장의 경우, 동일한 변환을 통해 항상 필드 k가 원시 질서를 갖는다고 가정할 수 있다.

해답의 대수적 표현

일반 체인

해결책을 나타내는 일반적인 방법은 0차원 일반 사슬을 통해서입니다. 그러한 체인은 1 i i ≤ n의 모든 i에 대해 f₁(x₁), f₂(x₁, x₂), ..., f_n(x₁, ..., x_n)의 순서로 구성된다.

• f는_i x₁, ..., x에만_i 있는 다항식이며, x에_i 도_i d > 0을 가지고 있다.
• f에서_i x의_i^d_i 계수는 x₁, ..., x의_{i −1} 다항식이며 f₁, ..., f와_{i − 1} 0의 공통점을 가지고 있지 않다.

그러한 정규 체인에 삼각형 계통의 방정식을 연결한다.

${\displaystyle {\case}f_{1}(x_{1})=0\\\f_{2}(x_{1},x_{2})=0\\\ndots \\\f_{n}(x_{1},x_{2},\ldots,x_{n}=0.\end{case}}}$

이 시스템의 해법은 제1차 일변량 방정식을 풀고, 다른 방정식의 해법들을 대체한 다음, 현재 일변량인 제2차 방정식을 푸는 등의 방법으로 얻어진다. 일반 사슬의 정의는_i f로부터 얻은 일변량 방정식이 d를_i 가지므로, 이 분해능 과정(대수의 근본적 정리)에 복수 루트가 없다면, 시스템에는 d₁ ... d 솔루션이_n 있다는 것을 암시한다.

모든 다항식 방정식의 0차원 시스템은 한정된 수의 정규 체인과 동등하다(즉, 같은 해법이 있다). 세 가지 해결책이 있는 다음 시스템에 해당하기 때문에 여러 개의 일반 체인이 필요할 수 있다.

${\displaystyle {\case}x^{2}-1=0\(x-1)=0\\\y^{2}-1=0.\end{case}}}$

임의의 다항식 시스템(필수적으로 0차원인 것은 아님)^[4]을 일반 체인(또는 일반 반알제브라틱 시스템)으로 삼각 분해하는 계산 알고리즘은 여러 가지가 있다.

0차원 사례에 특유하고 이 경우 직접 알고리즘과 경쟁하는 알고리즘도 있다. 등급 역독성 순서(grevlex)에 대한 그뢰브너 기반(Gröbner)을 먼저 계산한 다음, FGLM 알고리즘에^[5] 의한 사전적 그뢰브너 기반을 추론하고 마지막으로 렉스트리사각형 알고리즘을 적용하는 것으로 구성된다.^[6]

이러한 용액의 표현은 유한한 분야의 계수에 매우 편리하다. 그러나 합리적인 계수의 경우 다음 두 가지 측면을 고려해야 한다.

• 산출물은 계산과 결과의 사용을 문제화할 수 있는 거대한 정수를 포함할 수 있다.
• 산출물에서 해답의 숫자값을 추론하려면 근사치수를 갖는 일변량 다항식을 풀어야 하는데, 이는 매우 불안정한 문제다.

첫 번째 문제는 다한과 쇼스트에 의해 해결되었다.^[7][8] 주어진 솔루션 세트를 나타내는 일반 체인 세트 중에는 계수가 입력 시스템의 크기 측면에서 명시적으로 경계되고 거의 최적의 경계로 되어 있는 세트가 있다. 등주체 분해라고 불리는 이 집합은 좌표의 선택에만 의존한다. 이를 통해 효율적인 등가 분해 계산을 위해 모듈식 방법을 사용할 수 있다.^[9]

두 번째 문제는 일반적으로 형태 보조정리라고 불리는 특별한 형태의 정기적인 체인을 출력함으로써 해결되는데, 이 체인은 첫 번째 것을 제외한 모든 것이_i 1과 같다. 이러한 일반 체인을 얻기 위해서는 지수 0이 주어지는 분리 변수라는 변수를 더 추가해야 할 수도 있다. 아래에 설명된 합리적인 일변량 표현은 일반 체인 또는 그뢰브너 기반에서 시작하여 다한-쇼스트 바인딩을 만족시키는 그러한 특별한 정규 체인을 계산할 수 있다.

합리적 일변량 표현

합리적인 일변량 표현 또는 RUR는 F에 의해 도입된 합리적 숫자에 대한 0차원 다항식 시스템의 해법들을 나타낸 것이다. 더 거칠다.^[10]

0차원 시스템의 RUR는 분리 변수라고 불리는 변수의 선형 조합 x와₀ 방정식의^[11] 시스템으로 구성된다.

${\displaystyle {\case}h(x_{0})=0\\x_{1}=g_{1}/g_{0}(x_{0})/g_{n}=g_{n}(x_{0}),\case{0}}}}}\case {case}}}}$

여기서 h는 도 D x의₀ 단변₀ 다항식이고, g는 D보다_n 도 x의₀ 단변 다항식이다.

합리적인 숫자에 대해 0차원 다항식 시스템을 부여하면, RUR에는 다음과 같은 특성이 있다.

• 변수의 유한한 수 선형 조합을 제외한 모든 조합은 변수를 분리하고 있다.
• 분리 변수를 선택하면 RUR가 존재하며 고유하다. 특히 h와 g는_i 이를 계산하기 위한 알고리즘과는 독립적으로 정의된다.
• 시스템의 솔루션은 h의 뿌리와 일대일 대응이며 h의 각 뿌리의 다중성은 해당 솔루션의 다중성과 동일하다.
• 시스템의 해법은 다른 방정식에서 h의 뿌리를 대체함으로써 얻어진다.
• h가 다중 루트를 가지고 있지 않다면 g는₀ h의 파생물이다.

예를 들어, 이전 절의 시스템의 경우 x, y, x + y의 배수를 제외한 변수의 모든 선형 조합은 분리 변수다. 만약 하나를 선택하지=.mw-parser-output .sfrac{white-space:nowrap}.mw-parser-output.sfrac.tion,.mw-parser-output.sfrac .tion{디스플레이:inline-block, vertical-align:-0.5em, font-size:85%;text-align:센터}.mw-parser-output.sfrac.num,.mw-parser-output.sfrac .den{디스플레이:블록, line-height:1em, 마진:00.1em}.mw-parser-output.sfrac .den{border-top:1px sOlid}는 이는 변수로, 다음 RUR은 .sr-only{국경:0;클립:rect(0,0,0,0), 높이:1px, 마진:-1px, 오버 플로: 숨어 있었다. 패딩:0;위치:절대, 너비:1px}x – y/2 .mw-parser-output.

${\displaystyle {\case}t^{3}-t=0\x={\frac {t^{2}+2t-1}{3t^{2}}-1}\y={\frac {t^{2}-2t-1}{3t^{2}-1}-1}.\\end{case}}$

RUR는 알고리즘과 독립적으로 주어진 분리 변수에 대해 고유하게 정의되며 루트의 승수를 보존한다. 이것은 삼각분해(등주형 분해까지)와의 현저한 차이인데, 일반적으로는 승수를 보존하지 않는다. RUR는 비교적 작은 크기의 계수로 출력을 생성하는 속성을 등가대상 분해와 공유한다.

0차원 시스템의 경우, RUR는 단변 다항식 하나를 해결하여 합리적인 함수로 대체함으로써 해결책의 숫자 값을 검색할 수 있다. 이를 통해 주어진 정밀도에 대한 인증된 솔루션 근사치를 생산할 수 있다.

또한, RUR의 일변량 다항식 h(x₀)는 인수될 수 있으며, 이는 모든 수정 불가능한 인자에 대해 RUR를 제공한다. 이것은 주어진 이상(이상적인 급진적인 것의 일차적인 분해)의 원시적인 분해를 제공한다. 실제로 이것은 특히 높은 승수를 가진 시스템의 경우 훨씬 더 작은 계수를 가진 출력을 제공한다.

반대로 삼각 분해와 등가 대상 분해에 대해 RUR는 양의 차원으로 정의되지 않는다.

숫자로 푸는 중

일반해결 알고리즘

비선형 방정식의 모든 시스템을 위해 설계된 일반적인 수치 알고리즘은 다항식 시스템에도 적용된다. 그러나 일반적인 방법으로는 일반적으로 모든 해결책을 찾을 수 없기 때문에 구체적인 방법이 일반적으로 선호될 것이다. 특히 일반적인 방법이 아무런 해결책도 찾지 못하는 경우 이는 대개 해결책이 없다는 것을 나타내는 것이 아니다.

그럼에도 불구하고 여기서 두 가지 방법이 언급될 만하다.

• 방정식의 수가 변수의 수와 같을 경우 뉴턴의 방법을 사용할 수 있다. 그것은 모든 해결책을 찾도록 허락하지도 않고, 해결책이 없다는 것을 증명하지도 않는다. 그러나 해답에 가까운 지점에서 시작할 때는 매우 빠르다. 따라서 아래에 기술된 호모토피 연속법의 기본 툴이다.
• 최적화는 다항식 시스템 해결에 거의 사용되지 않지만, 56개의 변수에 81개의 2차 방정식을 갖는 시스템이 일관성이 없다는 것을 보여주는 데 1970년 경에 성공했다.^[12] 다른 알려진 방법들과 함께 이것은 현대 기술의 가능성을 넘어선 채로 남아있다. 이 방법은 단순히 방정식의 제곱합을 최소화하는 데 있다. 0이 국소 최소값으로 발견되면 용액에서 얻는다. 이 방법은 초과 결정된 시스템에 대해 작동하지만, 발견된 모든 로컬 최소값이 양수일 경우 빈 정보를 출력한다.

호모토피 연속법

이것은 방정식의 개수가 변수의 개수와 같다고 가정하는 반수법이다. 이 방법은 비교적 오래되었지만 지난 수십 년 동안 극적으로 개선되었다.^[13]

이 방법은 세 단계로 나뉜다. 첫째로 해결책 수에 대한 상한을 계산한다. 이 바운드는 가능한 한 날카로워야 한다. 따라서 최소 네 가지 방법으로 계산되며 최상의 값인 $N{\displaystyle }$ ${\displaystyle$ N$}$이$($가) 유지된다.

두 번째 단계에서는${\displaystyle {}_{}{계산}_{}}$하기 ${\displaystyle \mathrm{쉬운}}$ $N{\displaystyle }$ ${\displaystyle g_$${1}=0,\,\dots,\,g_$${$n$$}=$0}$의 다항 방정식이$$ ${\displaystyle {생성}_{}}$된다. 이 새로운 시스템은 변수의 수$$ $n{\displaystyle }${\$displaystyle n}$과 방정식의$$ $수{\displaystyle }$ n ${\displaystyle n}$을(를) 가지고 있으며,${\displaystyle 풀{}_{}}$ 시스템과 동일한 일반 구조인 ${\displaystyle {f\mathrm{}}_{}}$ $1{\displaystyle {}_{}}$=$,$ f = ${\displaystyle 0}$,\,\,\$dots ,\,f_{n}=0}$을(를) 가지고 있다$.$

그런 다음 두 시스템 사이의 호모토피가 고려된다. 예를 들어, 두 시스템 사이의 직선으로 구성되지만, 특히 시스템에서 일부 특이점을 방지하기 위해 다른 경로를 고려할 수 있다.

${\displaystyle (1}$- ${\displaystyle t}$) ${\displaystyle {g\mathrm{}}_{}}$ 1${\displaystyle {}_{}}$+ t ${\displaystyle {f\mathrm{}}_{}}$ ${\displaystyle 1{}_{}}$= 0${\displaystyle }$,${\displaystyle }$…${\displaystyle }$,${\displaystyle }$( ${\displaystyle 1}$- ${\displaystyle \mathrm{t}}$) ${\displaystyle g_{}}$ + ${\displaystyle n_{}}$= ${\displaystyle 0}$ + t = 0 ${\displaystyle (1-t)g_{1}+tf_{1}=0,\,\,\,(1-t)g_{n}+tf_{n}=0$

호모토피 연속성은 파라미터 $t{\displaystyle }$ ${\displaystyle t}$을 0에서$$ 1로 변형하고 이 변형 중에 $N{\displaystyle }$ ${\displaystyle N}$ 용액을 따르는$$ 것으로 구성된다. $이것$은 t${\displaystyle }$= ${\displaystyle 1}$ ${\displaystyle t=1}$에 대해 원하는 솔루션을 제공한다$.$ 따라서 t < 2 ${\$t${\displaystyle }$= ${\displaystyle {}_{}}$ $2{\displaystyle }$ ${\$}}:$t{\displaystyle }$ = t${\$의 솔루션에서 뉴턴의$$ 방법으로 추론한다$$. 여기서의 어려움은 t ${\displaystyle {2\mathrm{}}_{}}$- ${\displaystyle {}_{}}$ ${\displaystyle {1\mathrm{}}_{}}$: ${\displaystyle t_{2}-t_{1}:}}}$너무$$ 크면 뉴턴의 수렴 속도가 느려 솔루션 경로에서 다른 경로로 뛰어오를 수도 있다. 너무 작아서, 스텝 수가 방법을 늦춘다.

합리적인 일변량 표현을 통한 수치적 해결

RUR에서 해결책의 숫자 값을 추론하는 것은 쉬워 보인다: 일변량 다항식의 뿌리를 계산하고 다른 방정식에서 그것들을 대체하는 것으로 충분하다. 이것은 다른 다항식의 뿌리에서 다항식의 평가가 매우 불안정하기 때문에 그렇게 쉽지는 않다.

따라서 일변량 다항식의 뿌리는 모두 한 번 정의되지 않을 수 있는 높은 정밀도로 계산되어야 한다. 이 요건을 충족하는 알고리즘은 두 가지가 있다.

• MPSolve에서 구현된 Averth 방법은 모든 복잡한 뿌리를 어떤 정밀도로 계산한다.
• 우스펜스키의 콜린스와 아크리타스의 알고리즘은 루우엘리에와 짐머만이 개선했으며 데카르트의 기호 지배에 기초했다.^[14] 이 알고리즘은 임의의 작은 폭의 간격으로 격리된 실제 뿌리를 계산한다. 메이플(fsolve and RootFinding[Isolate])에서 시행된다.

소프트웨어 패키지

0차원 시스템을 자동으로 해결할 수 있는 소프트웨어 패키지는 최소 4개(자동으로 입력과 출력 사이에 사람의 개입이 필요 없어 사용자가 방법을 알 필요가 없다는 의미)가 있다. 0차원 시스템을 해결하는 데 유용할 수 있는 몇 가지 다른 소프트웨어 패키지도 있다. 그 중 일부는 자동 해결기의 뒤에 나열되어 있다.

Maple 함수의 RootFinding[Isolate]은 합리적인 숫자에 대해 모든 다항식 시스템을 입력(일부 계수가 부동 소수인 경우, 그것들은 합리적인 숫자로 변환됨)하고, 합리적인 숫자의 간격 또는 임의의 정밀도의 부동 소수 근사치로 표현되는 실제 솔루션을 출력한다. 시스템이 0차원이 아닌 경우 오류로 표시된다.

내부적으로는 F가 설계한 이 해결사. Rouillier는 먼저 Gröbner 기준을 계산한 다음, 용액의 필요한 근사치를 추론하는 Rational Univariate Presentation을 계산한다. 그것은 최대 수백 개의 복잡한 해결책을 가진 시스템에서 일상적으로 작동한다.

합리적인 일변량 표현은 Maple 함수 Groebner[RationalUnivariateRepresation]로 계산할 수 있다.

합리적인 일변량 표현에서 모든 복잡한 해결책을 추출하기 위해, 사람들은 일변량 다항식의 복잡한 뿌리를 어떤 정밀도로 계산하는 MPSolve를 사용할 수 있다. MPSolve는 입력 변수의 방정식에 있는 뿌리의 치환이 매우 불안정할 수 있으므로 솔루션이 안정적으로 유지될 때까지 매번 정밀도를 두 배로 증가시키는 것이 좋다.

두 번째 해결사는 PHCpack으로,^[13][16] J. Verschelde의 지시로 작성되었다. PHCpack은 호모토피 연속법을 구현한다. 이 해결사는 변수만큼 많은 방정식을 갖는 다항식 시스템의 격리된 복잡한 해결책을 계산한다.

세 번째 해결사는 베르티니(Bertini)로,^[17][18] D.J.Bates(D. J. Bates)가 썼다. Hauenstein, A. J. Sommese, C. W. Wampler. 베르티니는 적응 정밀도와 함께 수치적 호모토피 연속성을 사용한다. 0차원 솔루션 세트를 계산하는 것 외에도 PHCpack과 Bertini 모두 양차원 솔루션 세트와 작업할 수 있다.

네 번째 해결사는 Mark Moreno-Maza와 협력자들이 쓴 Maple LibraryChains이다. 일반 체인을 이용해 다항식 시스템을 푸는 다양한 기능을 담고 있다.

참고 항목

• 다항식 불평등의 체계
• 삼각분해
• 우의 특성 집합법

참조