Teaching / Math

조립제법과 Horner 방법

Math Algebra Polynomial

NOTE 12-20-01 · 조립제법과 Horner 방법

1. 일반 사항

A. 목적

  1. 이 노트는 조립제법(synthetic division)을 긴 나눗셈(long division)에서 유도한다.
  2. 조립제법과 Horner 방법(Horner’s method)이 단계마다 같은 계산임을 보인다.
  3. 같은 계수 비교로 \((ax - b)\)와 이차식으로 나누는 경우를 다룬다.

참고 조립제법 아랫줄의 숫자는 두 가지 의미를 갖는다. 몫의 계수이면서, \(P(c)\)를 Horner 방법으로 계산할 때 차례로 나오는 중간값이다. 따라서 마지막 칸은 나머지이면서 \(P(c)\)이고, 나머지정리는 이 동치성으로 증명된다. 절차의 유도를 모르면 \((x-c)\) 꼴에는 적용할 수 있어도 \(2x-1\)이나 이차식으로 나누는 경우로 변형할 수 없다.

B. 적용 범위

  1. 다항식 \(P(x)\)를 일차식 \(x - c\), \(ax - b\), 이차식 \(x^2 - px - q\)로 나누는 경우에 적용한다.

C. 결과 요약

  1. 조립제법은 긴 나눗셈에서 변수, 소거되는 항, 빼기를 생략한 압축 표기다.
  2. 점화식 \(b_{k-1} = a_k + c\,b_k\)는 조립제법의 한 단계이자 Horner 방법의 한 단계다.
  3. 마지막 칸은 나머지 \(R\)이며 \(P(c)\)와 같다(나머지정리).
  4. 몫을 반복해서 나누면 \(x = c\) 중심의 전개를 얻는다.
  5. \(ax - b\)로 나눌 때는 몫만 \(a\)로 나누고 나머지는 그대로 둔다.

2. 준비 정보

A. 필요한 개념

  1. 다항식의 긴 나눗셈과 계수 비교를 알아야 한다.
  2. 3.C 는 다항식의 미분을 사용한다.

C. 사용 프로그램

항목 용도
Python Horner 방법 구현(3.B)
Python, matplotlib, Pillow 그림 GIF 생성(make_gifs.py)

D. 관련 파일

  • make_gifs.py — 위 GIF 한 개를 만드는 스크립트 (matplotlib, Pillow)
python make_gifs.py    # -> images/blog/synthetic-division-and-horner-method/*.gif

3. 절차

A. 긴 나눗셈에서 조립제법 유도

  1. \(P(x) = 2x^3 - 5x^2 + 3x - 7\)을 \(x-2\)로 긴 나눗셈한다. 세 단계가 나온다.
단계 몫에 붙는 항 빼는 식 빼고 남는 다음 계수
1 \(2x^2\) \(2x^3 - 4x^2\) \(-5 - (-4) = -1\)
2 \(-x\) \(-x^2 + 2x\) \(3 - (-2) = 1\)
3 \(1\) \(x - 2\) \(-7 - (-2) = -5\)
  1. 빼는 식의 최고차항을 생략한다. 매번 소거되도록 고른 항이다.
  2. 남는 둘째 항이 항상 “방금 구한 몫의 계수 × (−2)”임을 확인한다.
  3. 이 항을 빼는 연산을 “몫의 계수 × 2”를 더하는 연산으로 바꾼다.
  4. 변수 \(x\)를 생략하고 계수만 남긴다. 결과가 조립제법이다.
  2 −5 3 −7
\(c = 2\)   4 −2 2
  2 −1 1 −5
  1. 몫 \(2x^2 - x + 1\), 나머지 \(-5\)를 얻는다.

참고 조립제법은 별도의 알고리즘이 아니라 긴 나눗셈의 압축 표기다.

  1. 일반형으로 쓴다. \(P(x) = a_n x^n + \cdots + a_1 x + a_0\)을 \(x - c\)로 나눈 몫을 \(Q(x) = b_{n-1}x^{n-1} + \cdots + b_0\), 나머지를 \(R\)이라 한다.
\[P(x) = (x - c)\,Q(x) + R\]
  1. 양변의 \(x^k\) 계수를 비교한다. \(a_n = b_{n-1}\), \(a_k = b_{k-1} - c\,b_k\), \(a_0 = R - c\,b_0\)이다.
  2. 점화식으로 고쳐 쓴다.
\[b_{n-1} = a_n, \qquad b_{k-1} = a_k + c\,b_k, \qquad R = a_0 + c\,b_0\]

참고 “내리고, \(c\)를 곱해서 다음 칸에 더한다”는 절차가 이 점화식 그대로다.

경고 자주 발생하는 논리적 오류 두 가지가 이 점화식으로 설명된다. 첫째, 빠진 차수에는 0을 넣어야 한다. 점화식이 차수마다 칸을 하나씩 쓰기 때문이다. 둘째, \(x + 3\)으로 나눌 때 \(c = -3\)이다. \(c\)는 나누는 식의 상수항이 아니라 그 식을 0으로 만드는 값이다.

B. Horner 방법과의 동치성

  1. 같은 다항식을 안쪽부터 묶는다.
\[P(x) = \big((2x - 5)x + 3\big)x - 7\]
  1. \(x = 2\)를 넣어 안쪽부터 계산한다. \(2 \to 2\cdot 2 - 5 = -1 \to (-1)\cdot 2 + 3 = 1 \to 1\cdot 2 - 7 = -5\)이다.
  2. 결과가 조립제법 아랫줄 \(2, -1, 1, -5\)와 일치함을 확인한다. 이 계산법이 Horner 방법이다.
Synthetic division of 2x^3 - 5x^2 + 3x - 7 by x - 2, step by step, next to the matching Horner evaluation
조립제법의 내리기, 곱하기, 더하기가 Horner 방법의 중간값 2, −1, 1, −5 와 한 칸씩 대응한다. 마지막 칸이 나머지이자 P(2) 다.
  1. 점화식 \(b_{k-1} = a_k + c\,b_k\)가 Horner의 한 단계와 같음을 확인한다. 지금까지의 값에 \(c\)를 곱하고 다음 계수를 더한다.
  2. 마지막 칸이 나머지 \(R\)이면서 \(P(c)\)임을 확인한다. 이것이 나머지정리(remainder theorem) \(R = P(c)\)이다.

참고 나머지정리는 보통 \(P(x) = (x-c)Q(x) + R\)에 \(x = c\)를 넣어 증명한다. 조립제법과 Horner 방법의 동치성에서는 이 등식이 계산 과정에 직접 나타난다.

  1. 인수정리(factor theorem)를 적용한다. 마지막 칸이 0이면 \(x - c\)가 인수이고, 그 앞의 숫자들이 남은 인수의 계수다.
  2. \(x^3 - 6x^2 + 11x - 6\)에 \(c = 1\)을 적용한다. 아랫줄은 \(1, -5, 6, 0\)이다.
  3. 인수분해 결과 \((x-1)(x^2 - 5x + 6) = (x-1)(x-2)(x-3)\)을 얻는다.

참고 근을 찾을 때 조립제법이 대입보다 유리한 이유는 근의 확인과 동시에 차수가 하나 낮은 몫이 나오기 때문이다.

  1. 곱셈 횟수를 비교한다. \(n\)차 다항식 하나의 값을 구하는 경우다.
계산 방법 곱셈 횟수 \(n = 4\)
각 항의 거듭제곱을 매번 새로 계산 \(n(n+1)/2\) 10
\(x^2, x^3, \ldots\)을 차례로 저장해 재사용 \(2n - 1\) 7
Horner \(n\) 4
  1. 덧셈 횟수는 세 방법 모두 \(n\)번임을 확인한다.
  2. \(P(x) = 2x^4 - 3x^3 + 5x - 7\)에서 \(P(3)\)을 계산한다. 중간값은 \(2 \to 3 \to 9 \to 32 \to 89\)이다.
  3. 같은 계산에서 몫 \(2x^3 + 3x^2 + 9x + 32\)를 함께 얻는다.

참고 손으로 계산할 때는 \(3^4 = 81\) 같은 큰 거듭제곱을 쓰지 않는다는 점이 곱셈 횟수보다 더 큰 이득이다.

  1. Horner 방법을 코드로 구현한다.
def horner(coeffs, c):
    """coeffs from the highest degree down (zeros included).
    Returns (quotient coefficients, remainder) of division by (x - c)."""
    row = [coeffs[0]]
    for a in coeffs[1:]:
        row.append(a + c * row[-1])
    return row[:-1], row[-1]

horner([2, -3, 0, 5, -7], 3)   # -> ([2, 3, 9, 32], 89)

C. 반복 나눗셈과 x = c 중심 전개

  1. \(P(x) = (x-c)Q(x) + R\)을 미분한다. \(P'(x) = Q(x) + (x-c)Q'(x)\)이다.
  2. \(x = c\)를 넣어 \(Q(c) = P'(c)\)를 얻는다.
  3. 3.A 의 몫 \(Q(x) = 2x^2 - x + 1\)을 \(c = 2\)로 다시 나눈다. 아랫줄은 \(2, 3, 7\)이다.
  4. \(P'(x) = 6x^2 - 10x + 3\)에서 \(P'(2) = 7\)임을 확인한다.
  5. 몫이 상수가 될 때까지 나눗셈을 반복한다. 나머지는 차례로 \(-5, 7, 7\)이고 마지막에 2가 남는다.
  6. \(x = 2\) 중심의 전개를 적는다.
\[P(x) = 2(x-2)^3 + 7(x-2)^2 + 7(x-2) - 5\]

참고 이 예는 조립제법이 나눗셈 계산법에 그치지 않고 도함수 및 다항식의 중심 이동과 연결됨을 보인다.

D. (ax − b)로 나누는 경우

  1. 최고차 계수가 1이 아닌 나누는 식을 \(ax - b = a\left(x - \tfrac{b}{a}\right)\)로 쓴다.
\[P(x) = \left(x - \tfrac{b}{a}\right)\tilde{Q}(x) + R = (ax - b)\cdot\frac{\tilde{Q}(x)}{a} + R\]
  1. \(c = b/a\)로 조립제법을 한다.

경고 가장 흔한 논리적 오류는 나머지까지 \(a\)로 나누는 것이다. 몫만 \(a\)로 나누고 나머지는 그대로 둔다.

  1. 몫만 \(a\)로 나눈다. 나머지는 그대로 둔다.
  2. \(6x^3 - 7x^2 + 4x + 1\)을 \(2x - 1\)로 나눈다. \(c = 1/2\)에서 아랫줄은 \(6, -4, 2, 2\)이다.
  3. 몫 \((6x^2 - 4x + 2)/2 = 3x^2 - 2x + 1\), 나머지 2를 얻는다. 나머지를 1로 적으면 틀린다.

E. 이차식으로 나누는 경우

  1. \(x^2 - px - q\)에 대해 같은 계수 비교를 한다. \(P(x) = (x^2 - px - q)Q(x) + rx + s\)로 둔다.
  2. \(x^k\)의 계수를 비교해 점화식을 얻는다(범위를 넘는 \(b\)는 0).
\[b_{k-2} = a_k + p\,b_{k-1} + q\,b_k, \qquad r = a_1 + p\,b_0 + q\,b_1, \qquad s = a_0 + q\,b_0\]

참고 일차식에서는 “앞 칸 × \(c\)“를 더했고, 이차식에서는 “앞 칸 × \(p\)“와 “두 칸 앞 × \(q\)“를 더한다. 나머지가 두 항이므로 마지막 두 칸만 규칙이 다르다. 결과적으로 조립제법이 두 줄 표가 된다.

  1. \(x^4 - 3x^2 + 1\)을 \(x^2 + x - 1\)로 나눈다. \(p = -1\), \(q = 1\), 계수는 \(1, 0, -3, 0, 1\)이다.
  2. 몫의 계수를 계산한다. \(b_2 = 1\), \(b_1 = 0 + (-1)(1) = -1\), \(b_0 = -3 + (-1)(-1) + (1)(1) = -1\)이다.
  3. 나머지를 계산한다. \(r = 0 + (-1)(-1) + (1)(-1) = 0\), \(s = 1 + (1)(-1) = 0\)이다.
  4. 나머지가 0이므로 인수분해 결과를 적는다.
\[x^4 - 3x^2 + 1 = (x^2 + x - 1)(x^2 - x - 1)\]
  1. 최고차 계수가 1이 아니면 3.D 와 같은 방법으로 처리한다.
  2. \(6x^4 + 7x^3 - 14x^2 + 15x - 18\)을 \(2x^2 + 3x - 2 = 2\left(x^2 + \tfrac{3}{2}x - 1\right)\)로 나눈다. \(p = -3/2\), \(q = 1\)이다.
\[b_2 = 6,\quad b_1 = 7 - 9 = -2,\quad b_0 = -14 + 3 + 6 = -5,\quad r = 15 + \tfrac{15}{2} - 2 = \tfrac{41}{2},\quad s = -18 - 5 = -23\]
  1. 몫 \((6x^2 - 2x - 5)/2 = 3x^2 - x - \tfrac{5}{2}\), 나머지 \(\tfrac{41}{2}x - 23\)을 얻는다.

참고 이차식으로 나눌 때 두 줄 표는 계수만 쓰는 긴 나눗셈보다 손 계산에서 크게 빠르지 않다. 이 표의 의미는 속도가 아니라 구조에 있다. 조립제법, 긴 나눗셈, Horner 방법은 모두 \(P = BQ + R\)의 계수를 최고차부터 차례로 맞추는 같은 계산이다. 따라서 나누는 식이 \(2x - 1\)이든 이차식이든 계수 비교로 점화식을 다시 세우면 된다.

4. 시험 및 검사

A. 나머지정리에 의한 확인

  1. 3.D 의 나머지를 \(P(1/2)\)로 확인한다. \(P(1/2) = \tfrac{6}{8} - \tfrac{7}{4} + 2 + 1 = 2\)이다.
  2. 판정: \(x = 1/2\)에서 \(ax - b\)가 0이 되므로 \(a\)를 어떻게 묶든 나머지는 \(P(b/a)\)여야 한다. 값이 2로 일치하므로 합격이다.

B. 전개에 의한 확인

  1. 3.C 의 \(x = 2\) 중심 전개를 전개한다. 원래 식 \(2x^3 - 5x^2 + 3x - 7\)이 나오면 합격이다.
  2. 3.E 의 인수분해 \(x^4 - 3x^2 + 1 = (x^2 + x - 1)(x^2 - x - 1)\)을 긴 나눗셈으로 확인한다. 세 번째 단계에서 나머지 없이 끝난다.
  3. 3.E 의 \(6x^4 + 7x^3 - 14x^2 + 15x - 18\) 결과가 긴 나눗셈 결과와 같음을 확인한다.

C. 일반 검산 기준

  1. 어느 방법으로 풀었든 \(B \cdot Q + R\)을 전개해 원래 식이 나오는지 확인한다.
  2. \(R\)의 차수가 \(B\)의 차수보다 낮은지 확인한다.

5. 종료

A. 결과 정리

  1. 조립제법은 \(P(x) = (x - c)Q(x) + R\)의 계수 비교에서 얻는 점화식 \(b_{k-1} = a_k + c\,b_k\)의 표기다.
  2. 같은 점화식이 Horner 방법이므로 마지막 칸은 \(P(c)\)이고, 나머지정리와 인수정리가 직접 따라 나온다.
  3. \(ax - b\)와 이차식으로 나누는 경우도 같은 계수 비교로 점화식을 세워 처리한다.