Ruffini's rule

수학에서, 루피니의 규칙(Ruffini's rule)은 x − r 형식의 이항식(binomial)에 의해 다항식을 나누기 위한 효율적인 기법입니다. 그것은 1804년에 파올로 루피니(Paolo Ruffini)에 의해 묘사되었습니다.^[1] 루피니의 규칙은, 나누는 식이 선형 인수일 때, 조립 제법(synthetic division)의 특별한 경우입니다.

Algorithm

규칙은 다항식

P(x)=a_{n}x^{n}+a_{n-1}x^{n-1}+\cdots +a_{1}x+a_{0}

을 이항식

Q(x)=x-r

으로 나눔으로써, 몫 다항식

R(x)=b_{n-1}x^{n-1}+b_{n-2}x^{n-2}+\cdots +b_{1}x+b_{0}

을 얻기 위해 방법을 수립하는 것입니다.

알고리듬은 사실 Q(x)에 의한 P(x)의 긴 나눗셈(long division)입니다.

P(x)를 Q(x)로 나누기 위해:

오직 P(x)의 계수를 가져와서 차수가 높은 것에서 낮은 것으로 쓰십시오 (이때, 모든 차수를 다 기록해야 하는데, 계수가 0인 것도 반드시 포함해야 합니다). 그런 다음 바로 줄 위의, 아래 왼쪽 가장자리에 r을 쓰십시오:
${\begin{array}{c|c c c c|c}&a_{n}&a_{n-1}&\dots &a_{1}&a_{0}\\r&&&&&\\\hline &&&&&\\\end{array}}$
가장 왼쪽의 계수 (a_n)은, 그냥 줄 아래에 내려서 쓰십시오:
${\begin{array}{c|c c c c|c}&a_{n}&a_{n-1}&\dots &a_{1}&a_{0}\\r&&&&&\\\hline &a_{n}&&&&\\&=b_{n-1}&&&&\end{array}}$
줄 아래의 가장 오른쪽 숫자에 r을 곱하고 그것을 한 칸 오른쪽의 줄 위에 쓰십시오:
${\begin{array}{c|c c c c|c}&a_{n}&a_{n-1}&\dots &a_{1}&a_{0}\\r&&b_{n-1}\cdot r&&&\\\hline &a_{n}&&&&\\&=b_{n-1}&&&&\end{array}}$
같은 열에 위치한 두 값을 더하십시오.
${\begin{array}{c|c c c c|c}&a_{n}&a_{n-1}&\dots &a_{1}&a_{0}\\r&&b_{n-1}\cdot r&&&\\\hline &a_{n}&b_{n-1}\cdot r+a_{n-1}&&&\\&=b_{n-1}&=b_{n-2}&&&\end{array}}$
단계 3과 4를 남겨진 숫자가 없을 때까지 반복하십시오:
${\begin{array}{c|c c c c|c}&a_{n}&a_{n-1}&\dots &a_{1}&a_{0}\\r&&b_{n-1}\cdot r&\dots &b_{1}\cdot r&b_{0}\cdot r\\\hline &a_{n}&b_{n-1}\cdot r+a_{n-1}&\dots &b_{1}\cdot r+a_{1}&a_{0}+b_{0}\cdot r\\&=b_{n-1}&=b_{n-2}&\dots &=b_{0}&=R\\\end{array}}$

b 값들은 결과 (R(x)) 다항식의 계수이고, 그것의 차수는 P(x)의 차수보다 하나 작습니다. 얻어진 마지막 값, R은 나머지입니다. 다항식 나머지 정리(polynomial remainder theorem)는, 이 나머지가, r에서 다항식의 값, P(r)와 같음을 주장합니다.

Example of use

위에서 설명한, 다항식 나눗셈의 예제입니다.

다음과 같이 놓습니다:

P(x)=2x^{3}+3x^{2}-4\,\!

Q(x)=x+1.\,\!

우리는 루피니의 규칙을 사용하여 P(x)를 Q(x)로 나누기를 원합니다. 한가지 문제는 Q(x)가 형태 x − r의 이항식이 아니라, x + r의 이항식이라는 것입니다. 반드시 아래와 같이 Q(x)를 다시 써야 합니다:

Q(x)=x+1=x-(-1).\,\!

이제 알고리듬을 적용합니다:

1. 계수와 r을 다음과 같이 씁니다. P(x)가 x에 대해 계수를 포함하고 있지 않음을 주목하시고, 그것에 대해 0을 쓰야 합니다:

    |     2     3     0     -4
    |                                    
 -1 |                                    
----|----------------------------
    |                                    
    |

2. 첫 번째 계수는 그냥 아래로 내려서 쓰십시오:

    |     2     3     0     -4
    |                                    
 -1 |                                    
----|----------------------------
    |     2                              
    |

3. 마지막 획득된 값에 r을 곱하십시오:

    |     2     3     0     -4
    |                                    
 -1 |          -2                         
----|----------------------------
    |     2                              
    |

4. 값을 더하십시오:

    |     2     3     0     -4
    |
 -1 |          -2
----|----------------------------
    |     2     1
    |

5. 단계 3과 4를 마지막 숫자까지 반복하십시오:

    |     2     3     0     -4
    |
 -1 |          -2    -1      1
----|----------------------------
    |     2     1    -1     -3
    |{result coefficients}{remainder}

그래서, 만약 원래 다항식 = 나누는 식 × 몫 + 나머지이면,

P(x)=Q(x)R(x)+s\,\!

, 여기서

R(x)=2x^{2}+x-1\,\!

및

s=-3;\quad \Rightarrow 2x^{3}+3x^{2}-4=(2x^{2}+x-1)(x+1)-3\!

Uses of the rule

루피니의 규칙은 많은 실제 응용을 가집니다; 그들 중 대부분은 (아래에서 보여주는 것처럼) 단순 나눗셈 또는 아래에 같이 추가로 제공되는 공통 확장에 의존합니다.

Polynomial root-finding

유리 근 정리(rational root theorem)는 다항식 $f (x) = a n x n + a n -1 x n -1 + ... + a 1 x + a 0$ 에 대해, (a_n에서 a₀까지) 그의 계수가 모두 정수(integer)이면, 실수 유리(rational) 근은 항상 p/q의 형태임을 말하는데, 여기서 p는 a₀의 정수 약수이고 q는 a_n의 정수 약수입니다. 따라서 만약 다항식이 다음과 같으면,

P(x)=x^{3}+2x^{2}-x-2=0\,\!,

가능한 유리 근은 a₀ (−2)의 모든 정수 약수입니다:

{\text{Possible roots:}}\left\{+1,-1,+2,-2\right\}.

(이 예제는 다항식이 일계수(monic) (즉, a_n = 1)이기 때문에 간단합니다; 비-일계수 다항식의 가능한 근의 집합은 일부 분수를 포함할 것이지만, 그것들은 오직 유한한 숫자인데 왜냐하면 a_n와 a₀는 각각 오직 유한 개의 정수 약수를 가지기 때문입니다.) 임의의 경우에서, 일계수 다항식에 대해, 모든 각 유리 근은 정수이고, 그래서 모든 각 정수 근은 바로 상수 항(constant term) (즉, a₀)의 약수 중 하나입니다. 이것은 비-일계수 다항식에 대해 여전히 참인 것을 보일 수 있습니다. 즉, 정수 계수를 가진 임의의 다항식의 정수 근을 찾기 위해, 상수 항의 약수를 확인하는 것으로 충분합니다.

그래서, r을 차례로 이들 가능한 각 근과 같다고 놓으면, 다항식은 ( $x - r$ )로 나누어질 것입니다. 만약 결과 몫이 나머지를 가지지 않으면, 근이 발견된 것입니다.

다음 세 가지 방법 중 하나를 선택할 수 있습니다: 그들은 모두 같은 결과를 산출하는데, (인수분해를 구하기 위해 루피니의 규칙을 적용할 때) 두 번째 방법과 세 번째 방법은 주어진 근이 반복됨을 발견할 수 있다는 예외 사항이 있습니다. (방법은 모두 무리 근 또는 복소수 근을 발견하지 못합니다.)

Method 1

이항식 (x − 각각의 가능한 근)에 의한 P(x)를 나누십시오. 만약 나머지가 0이면, 선택된 숫자는 근입니다 (그 반대도 마찬가지입니다):

    |    +1    +2    -1     -2                      |    +1    +2    -1    -2
    |                                               |
 +1 |          +1    +3     +2                   -1 |          -1    -1    +2
----|----------------------------               ----|---------------------------
    |    +1    +3    +2      0                      |    +1    +1    -2     0

    |    +1    +2    -1     -2                      |    +1    +2    -1    -2
    |                                               |
 +2 |          +2    +8    +14                   -2 |          -2     0    +2
----|----------------------------               ----|---------------------------
    |    +1    +4    +7    +12                      |    +1     0    -1     0

{\begin{cases}x_{1}=+1\\x_{2}=-1\\x_{3}=-2\end{cases}}

예제에서, P(x)는 삼차 다항식입니다. 대수학의 기본 정리(fundamental theorem of algebra)에 의해, 그것은 세 복소수 해보다 많은 해를 가질 수 없습니다. 그러므로, 다항식은 다음으로 인수회됩니다:

P(x)=(x-x_{1})(x-x_{2})(x-x_{3})=(x-1)(x+1)(x+2)=x^{3}+2x^{2}-x-2.

Method 2

유효한 근을 찾을 때까지 방법 1에서와 같이 시작하십시오. 그런 다음, 가능한 다른 근을 갖는 프로세스를 다시 시작하는 대신, 현재 발견된 유효한 근에서 루피니의 결과에 대해 가능한 근을 계속 테스트하십시오, 이것을 오직 하나의 계수가 남을 때까지 계속하십시오 (근이 반복(중복)될 수 있음을 기억하십시오: 만약 테스트가 막히면, (앞에서 구한) 유효한 각 근을 다시 시도하십시오):

    |    +1    +2    -1    -2                      |    +1    +2    -1    -2
    |                                              |
 -1 |          -1    -1    +2                   -1 |          -1    -1    +2
----|---------------------------               ----|---------------------------
    |    +1    +1    -2   | 0                      |    +1    +1    -2   | 0
    |                                              |
 +2 |          +2    +6                         +1 |          +1    +2
-------------------------                      -------------------------
    |    +1    +3   |+4                            |    +1    +2   | 0
                                                   |
                                                -2 |          -2
                                               -------------------
                                                   |    +1   | 0

{\begin{cases}x_{1}=-1\\x_{2}=+1\\x_{3}=-2\end{cases}}

Method 3

유리 근 정리(rational root theorem)에 따라 다항식의 가능한 정수 또는 유리 근의 집합을 구하십시오.
각 가능한 근 r에 대해, 나눗셈 P(x)/(x–r)을 수행하는 것 대신에, 다항식 나머지 정리(polynomial remainder theorem)를 적용하십시오, 그것은 이 나눗셈의 나머지가 P(r)인 것, 즉, x = r에 대해 다항식을 평가한 것임을 말합니다.

따라서, 집합에서 각 r에 대해, r이 실제로 다항식의 근인 것과 P(r)=0인 것은 필요충분 조건입니다.

이것은 다항식의 정수 및 유리수 근을 찾기 위해 어떤 나눗셈 또는 루피니의 규칙의 응용을 요구하지 않음을 보여줍니다.

어쨌든, 한번 유효한 근이 구해지면, 그것을 r₁이라고 놓으십시오: 다음을 구하기 위해 루피니의 규칙을 적용할 수 있습니다:

Q(x)=P(x)/(x–r₁).

이것은 다음과 같은 부분적으로 인수화하는 것을 허용합니다:

P(x)=(x–r₁)·Q(x)

다항식의 임의의 추가적인 (유리) 근은 역시 Q(x)의 근이고, 물론, 아직 확인되지 않은 이전에 결정된 가능한 근 중에서 여전히 발견될 것입니다 (이미 근이 아닌 것으로 결정된 P(x)의 임의의 값은 마찬가지로 Q(x)의 근이 아닙니다; 보다 공식적으로, P(r)≠0 → Q(r)≠0 ).

따라서, P(r) 대신에 Q(r)를 평가하는 것, 그리고 (다른 근, r₂을 찾으려고 하는 한) Q(r)를 (x–r₂)로 나누는 것으로 과정을 진행할 수 있습니다.

비록 오직 근을 검색하는 경우에도, 이것은, 인수분해가 진행됨에 따라, 연속적으로 더 작은 차수의 다항식을 평가하는 것을 허용합니다.

만약, 자주 그렇듯이, 차수 n의 다항식을 인수분해하려면,

만약 p = n 유리 해를 찾았으면 p = n 선형 인수를 갖는 완전한 인수분해가 끝납니다 (아래 참조하십시오).
만약 p<n 유리 해를 찾았으면 p 선형 인수를 갖는 부분적 인수분해가 끝나고, 다음으로, 차수 n–p의 다른 비-선형 인수가 무리수 또는 복소 근을 가질 수 있습니다.

Examples

Finding roots without applying Ruffini's Rule

P (x)= x ³+2 x ²- x -2

가능한 근들 = {1, –1, 2, -2}

P(1) = 0 → x₁ = 1
P(-1) = 0 → x₂ = -1
P(2) = 12 → 2은 다항식의 근이 아닙니다.

그리고 $(x ³+2 x ²- x -2)/(x -2)$ 의 나머지는 12입니다.

P(-2) = 0 → x₃ = -2

Finding roots applying Ruffini's Rule and obtaining a (complete) factorization

P (x) = x ³+2 x ²- x -2

가능한 근들 = {1, -1, 2, -2}

P(1) = 0 → x₁ = 1

그런 다음, 루피니의 규칙을 적용하십시오:

(x ³+2 x ²- x -2)/(x -1) = (x ²+3 x +2)

x ³+2 x ²- x -2 = (x -1)(x ²+3 x +2)

여기서, r₁=-1 및 $Q (x) = x ²+3 x +2$

Q(-1) = 0 → x₂ = -1

다시, 루피니의 규칙을 적용하십시오:

(x ²+3 x +2)/(x +1) = (x +2)

x ³+2 x ²- x -2 = (x -1)(x ²+3 x +2) = (x -1)(x +1)(x +2)

다항식을 완전히 인수분해할 수 있었으므로, 마지막 근이 -2임이 분명합니다 (이전 과정은 1의 마지막 몫을 갖는 같은 결과를 냈습니다).

Polynomial factoring

특정 다항식의 모든 실수 유리 근을 찾기 위해, 위의 "p/q" 결과 (또는 공정하게, 다른 임의의 방법)를 사용했으므로, 그들의 근을 사용하여 다항식을 부분적으로 인수화(factor)하는 것은 사소한 단계일 뿐입니다. 잘-알려진 것처럼, 주어진 다항식을 나누는 각각의 선형 인수 (x − r)은 근 r에 대응하고, 그 반대도 마찬가지입니다.

그래서 만약

P(x)=a_{n}x^{n}+a_{n-1}x^{n-1}+\cdots +a_{1}x+a_{0}\,\!

가 주어진 다항식이고;

R=\left\{{\mbox{roots of }}P(x)\in \mathbb {Q} \right\}\,\!

이 찾은 근이면, 다음 곱으로 생각할 수 있습니다:

R(x)=a_{n}{\prod (x-r)}{\mbox{ for all }}r\in R.\,\!

대수학의 기본 정리(fundamental theorem of algebra)에 의해, 만약 P(x)의 모든 근이 유리수이면, R(x)는 P(x)와 같아야 합니다. 그러나 사용된 방법은 오직 유리 근을 찾기 때문에, R(x)는 P(x)와 같지 않을 가능성이 높습니다; P(x)는 R이 아닌 일부 무리수 또는 복소수 근을 가질 가능성이 높습니다.

S(x)={\frac {P(x)}{R(x)}}\,\!

, 이것은 다항식의 긴 나눗셈을 사용하여 계산될 수 있습니다.

만약 S(x) = 1이면, R(x) = P(x)임을 알 수 있고 절차는 완료되었습니다. 그렇지 않으면, S(x)는 다항식 그 자체가 될 것입니다; 이것은 실수 유리 근을 가지지 않는 P(x)의 또 다른 인수입니다. 그래서 다음 방정식이 오른쪽 변을 완전히 작성하십시오:

P(x)=R(x)\cdot S(x).\,\!

만약 S(x) = 1이면, 이를 Q (유리수)에 걸쳐 P(x)의 완전한 인수분해라고 부를 수 있습니다. 그렇지 않으면, Q에 걸쳐 P(x)의 오직 부분적 인수분해가 있으며, 이것은 유리수에 걸쳐 추가적인 인수분해가 가능, 불가능할 수 있습니다; 그러나 실수에 걸쳐 또는 최악의 경우 복소 평면에서 확실히 더 인수분해될 수 있습니다. (참고: Q에 걸쳐 P(x)의 "완전 인수분해"는 유리수 계수를 갖는 다항식의 곱으로서의 인수분해를 의미하며, 따라서 각 인수는 Q에 걸쳐 기약임을 만족합니다. 여기서 "Q에 걸쳐 기약"은 인수가 유리 계수와 더 낮은 차수를 가진 두 개의 비-상수 다항식의 곱으로 쓸 수 없음을 의미합니다.)

Example 1: no remainder

다음 방정식을 생각하십시오.

P(x)=x^{3}+2x^{2}-x-2.\,\!

위에서 묘사된 방법을 사용하여, P(x)의 유리 근은 다음과 같습니다:

R=\left\{+1,-1,-2\right\}.\,\!

그런 다음, (x − 각각의 근)의 곱으로 나타내십시오:

R(x)=1(x-1)(x+1)(x+2).\,\!

그리고 P(x)/R(x):

S(x)=1.\,\!

그러므로 인수화된 다항식은 P(x) = R(x) · 1 = R(x)입니다:

P(x)=(x-1)(x+1)(x+2).\,\!

Example 2: with remainder

다음 방정식을 생각하십시오.

P(x)=2x^{4}-3x^{3}+x^{2}-2x-8.\,\!

위에서 묘사된 방법을 사용하여, P(x)의 유리 근은 다음과 같습니다:

R=\left\{-1,+2\right\}.\,\!

그런 다음, (x − 각각의 근)의 곱으로 나타내십시오:

R(x)=(x+1)(x-2).\,\!

그리고 P(x)/R(x)

S(x)=2x^{2}-x+4.\,\!

$S(x){\neq }1$ 이기 때문에, 인수화된 다항식은 P(x) = R(x) · S(x)입니다:

P(x)=(x+1)(x-2)(2x^{2}-x+4).\,\!

Factoring over the complexes

복소수, C에 걸쳐 주어진 다항식을 완전히 인수분해하기 위해, 그의 모든 근이 알려져야 합니다 (무리수 및/또는 복소수를 포함할 수 있습니다). 예를 들어, 위의 다항식을 생각해 보십시오:

P(x)=2x^{4}-3x^{3}+x^{2}-2x-8.\,\!

유리수 근을 추출하고 그것을 인수분해하면, 다음과 같은 결과가 나타납니다:

P(x)=(x+1)(x-2)(2x^{2}-x+4).\,\!

그러나 그것은 C에 걸쳐 완전히 인수분해된 것이 아닙니다. 만약 다항식의 인수분해가 선형 인수의 곱으로 반드시 끝나려면, 이차 인수는 반드시 처리되어야 합니다:

{2x^{2}-x+4}=0.\,\!

가장 쉬운 방법은 이차 공식(quadratic formula)을 사용하는 것인데, 다음을 산출합니다:

x={\frac {-b\pm {\sqrt {b^{2}-4ac}}}{2a}}={\frac {1\pm {\sqrt {(-1)^{2}-4\cdot 2\cdot 4}}}{2\cdot 2}}={\frac {1\pm {\sqrt {-31}}}{4}}\,\!

그리고 해는

x_{1}={\frac {1+{\sqrt {-31}}}{4}}\,\!

x_{2}={\frac {1-{\sqrt {-31}}}{4}}.\,\!

그래서 C에 걸쳐 완전히 인수화된 다항식은 다음일 것입니다:

P(x)=2(x+1)(x-2)\left(x-{\frac {1+i{\sqrt {31}}}{4}}\right)\left(x-{\frac {1-i{\sqrt {31}}}{4}}\right).\,\!

어쨌든, 모든 경우에서 그렇게 쉽게 되는 것을 기대할 수는 없습니다; 사-차 다항식에 대해 이차 공식의 대응은 매우 복잡하고 오차 이상의 다항식에 대해 그러한 대응은 존재하지 않습니다. 이것이 왜 그런지에 대한 이론적 설명은 갈루아 이론(Galois theory)을 참조하고, 다항식의 근을 수치적으로 근사화하는 방법에 대해 수치 해석학(numerical analysis)을 참조하십시오.

Limitations

주어진 다항식의 근을 찾을 때, S(x)에 대해 뒤얽힌 고차 다항식을 얻을 수 있으며, 이것은 심지어 무리수 또는 복소수 인수분해를 고려하기 전에도 유리수에 걸쳐 추가적인 인수분해될 수 있음을 전적으로 고려해야 합니다. 다항식 x⁵ − 3x⁴ + 3x³ − 9x² + 2x − 6을 생각해 보십시오. 루피니의 방법을 사용하여 오직 하나의 근이 (x = 3) 발견됩니다; 그것을 인수분해하십시오: P(x) = (x⁴ + 3x² + 2)(x − 3).

위에서 설명한 것처럼, 만약 언급된 작업이 "C에 걸쳐 기약으로 인수분해 하는 것"이면, 사차를 상세히 분석하고 무리수 및/또는 복소수 근을 찾는 어떤 방법이 필요합니다. 그러나 만약 작업이 "Q에 걸쳐 기약으로 인수분해 하는 것"이면, 그것은 이미 완료된 것으로 생각할 수 있습니다; 그러나 이것이 반드시 그런 것이 아님을 인식하는 것이 중요합니다.

이 예제에서 사차는 실제로 두 이차의 곱 (x² + 1)(x² + 2)으로 인수분해될 수 있습니다. 이것들은 결국 유리수 (그리고, 사실, 이 예제에서 마찬가지로 실수)에 걸쳐 기약입니다; 이것으로 방법을 끝냅니다; P(x) = (x² + 1)(x² + 2)(x − 3). 이 경우에서, 사차를 복이차 방정식(biquadratic equation)으로 취급함으로써 인수분해하는 것은 실제로 쉽습니다; 그러나 더 높은 차수 다항식의 그러한 인수분해를 찾는 것은 매우 어려울 수 있습니다.

History

이 방법은 파올로 루피니(Paolo Ruffini)가 발명했습니다. 그는 이탈리아 과학 협회가 주최한 (40회) 대회에 참여했습니다. 대답해야 할 질문은 임의의 다항식의 근을 찾는 방법이었습니다. 다섯 개의 제안서가 접수되었습니다. 1804년에 루피니의 것은 1등을 획득했고 그 방법이 출판되었습니다. 루피니는 1807년과 1813년에 이 방법의 개선사항을 발표했습니다.

호너의 방법은 1819년에 출판되었고 1845년에 개선된 버전을 출판되었습니다.

References

^ Cajori, Florian (1911). "Horner's method of approximation anticipated by Ruffini" (PDF). Bulletin of the American Mathematical Society. 17 (8): 389–444. doi:10.1090/s0002-9904-1911-02072-9.

External links

Weisstein, Eric W. "Ruffini's rule". MathWorld.
Media related to Ruffini's rule at Wikimedia Commons

[1] Cajori, Florian (1911). "Horner's method of approximation anticipated by Ruffini" (PDF). Bulletin of the American Mathematical Society. 17 (8): 389–444. doi:10.1090/s0002-9904-1911-02072-9.

[1]