PROOF 76
증명하라.
어림값을 더하면 오차가 쌓인다
실수 ℝ 위에서.
한 줄씩, 이유를 따라가 봅시다
먼저 이미 주어진 것과 앞으로 보여야 할 것을 나누어 읽어 보세요. 다음 줄로 넘어갈 때마다 어떤 정의나 앞의 결과를 사용했는지 묻습니다. 연결이 보이지 않으면 결론을 외우기보다 그 전제로 잠시 돌아가도 좋습니다.
정의 D1
실수 x₁, …, xₙ 에 대하여 S = x₁ + ⋯ + xₙ, T = round(x₁) + ⋯ + round(xₙ), eᵢ = round(xᵢ) − xᵢ 라 한다.
증명.
(1)eᵢ 는 i 번째 항을 어림하며 생긴 오차다.약속
(2)round(xᵢ) = xᵢ + eᵢ(1), E
∎
보조정리 L1
T − S = e₁ + ⋯ + eₙ
증명.
(1)T = (x₁ + e₁) + ⋯ + (xₙ + eₙ)D1, E
(2)덧셈의 결합과 교환을 거듭 적용하면 xᵢ 끼리, eᵢ 끼리 모을 수 있다.A4, A5, R
(3)T = S + (e₁ + ⋯ + eₙ)(1), (2)
(4)양변에서 S 를 빼면 T − S = e₁ + ⋯ + eₙ(3), E
∎
보조정리 L2
모든 n 에 대하여 |a₁ + ⋯ + aₙ| ≤ |a₁| + ⋯ + |aₙ|
증명.
(1)n = 1 일 때 양변은 |a₁| 로 같다.약속
(2)n = k 에서 성립한다고 하자.가정
(3)|(a₁ + ⋯ + aₖ) + aₖ₊₁| ≤ |a₁ + ⋯ + aₖ| + |aₖ₊₁|A1
(4)|a₁ + ⋯ + aₖ| + |aₖ₊₁| ≤ (|a₁| + ⋯ + |aₖ|) + |aₖ₊₁|(2), A2
(5)|a₁ + ⋯ + aₖ₊₁| ≤ |a₁| + ⋯ + |aₖ₊₁|(3), (4), A3
(6)그러므로 모든 n 에 대하여 성립한다.(1), (5), R
∎
정리 T1
n 개의 실수를 각각 반올림해 더하면 |T − S| ≤ n/2
증명.
(1)T − S = e₁ + ⋯ + eₙL1
(2)|T − S| ≤ |e₁| + ⋯ + |eₙ|(1), L2
(3)각 i 에 대하여 |eᵢ| ≤ 1/2D1, A8
(4)|e₁| + ⋯ + |eₙ| ≤ 1/2 + ⋯ + 1/2(3), A2
(5)1/2 을 n 번 더한 값은 n/2 이다.A6
(6)|T − S| ≤ n/2(2), (4), (5), A3
∎
따름정리 C
모든 i 에 대하여 xᵢ = 1/2 이면 |T − S| = n/2 이다.
증명.
(1)모든 i 에 대하여 xᵢ = 1/2 이라 하자.가정
(2)S 는 1/2 을 n 번 더한 값이므로 S = n/2(1), D1, A6
(3)round(1/2) = 1 이므로 T 는 1 을 n 번 더한 값이고 T = n(1), D1, A9, A6
(4)T − S = n − n/2(2), (3), E
(5)n − n/2 = n(1 − 1/2) = n/2A7
(6)n/2 ≥ 0 이므로 |T − S| = n/2(4), (5), A10
(7)그러므로 T1 의 상한 n/2 는 더 줄일 수 없다.(6), T1
∎
비고
A1 은 이 증명에서 제거할 수 있는가.
한 항의 오차가 1/2 이하라는 것은 이미 주어져 있다. 그것을 합의 오차로 옮기는 줄이 어느 것인지 확인하라.