Решение упражнения 2.9 из SICP

19 January, 2008 (21:07) | Решения упражнений

Для удобства введем следующие краткие обозначения. Для интервала x будем обозначать его нижнюю границу l(x), верхнюю границу – u(x), а радиус – r(x) = (u(x)-l(x))/2.

Вначале покажем, что радиус суммы и разности интервалов зависит только от радиусов интервалов, которые складываются или вычитаются:

r(x+y) = [u(x+y) – l(x+y)] / 2 = [(u(x)+u(y)) – (l(x)+l(y))] / 2 = [(u(x)-l(x)) + (u(y)-l(y))] / 2 = [u(x)-l(x)]/2 + [u(y)-l(y)]/2 = r(x) + r(y),

r(x-y) = [u(x-y) – l(x-y)] / 2 = [(u(x)-l(y)) – (l(x)-u(y))] / 2 = [(u(x)-l(x)) – (u(y)-l(y))] / 2 = [u(x)-l(x)]/2 – [u(y)-l(y)]/2 = r(x) – r(y),

что и требовалось доказать.

Теперь покажем, что для умножения и деления интервалов зависимость радиуса результата исключительно от радиусов аргументов не выполняется. Для этого рассмотрим интервалы вида [n, n+1], где n – некое натуральное число. Радиусы всех таких интервалов независимо от величины n равны 1/2.

Вычислим [n, n+1]*[n, n+1] и [n, n+1]/[n, n+1]:

[n, n+1]*[n, n+1] = [n², (n+1)²], а значит r([n, n+1]*[n, n+1]) = [(n+1)² – n²]/2 = n + 1/2;

[n, n+1]/[n, n+1] = [n, n+1]*[1/(n+1), 1/n] = [n/(n+1), (n+1)/n], а значит r([n, n+1]/[n, n+1]) = [(n+1)/n – n/(n+1)]/2 = (2n+1)/[2n(n+1)].

При одинаковых радиусах исходных интервалов по вышеприведенным формулам для n=1 получим радиус для произведения равным 3/2, а для частного – 3/4; для для n=2 имеем радиус для произведения равным 5/2, а для частного – 5/12. Результаты разные, а значит зависят не только от радиусов множителей (в случае произведения) или делимого и делителя (в случае частного).

Comments

Comment from Dima
Date: June 22, 2008, 11:10 am

r(x-y) = r(x) + r(y), а не r(x) – r(y). Ошибка в алгебре. Да и как иначе? Точность не может увеличиватся с соличеством операций, а соовтветсвенно и радиус не может уменьшатся.

Comment from Sergey Khenkin
Date: June 22, 2008, 11:25 am

Да, все правильно. Опечатался при раскрытии знаков.
Правильно так:
r(x-y) = [u(x-y) – l(x-y)] / 2 = [(u(x)-l(y)) – (l(x)-u(y))] / 2 = [(u(x)-l(x)) + (u(y)-l(y))] / 2 = [u(x)-l(x)]/2 + [u(y)-l(y)]/2 = r(x) + r(y).
Спасибо.

Comment from vkolesnikov
Date: December 27, 2015, 9:01 pm

Это работает только для интервалов, нижняя граница которых строго меньше или равна верхней. При этом в книге об этом не упоминается, я также не нашел определений из интервальной арифметики, которые бы указывали на этот момент. Пример интервалов которые не удовлетворяют вышеизложенной логике: [1 0], [0 1]. Вообще если один из интервалов не будет удовлетворять уловию, что верхня граница больше нижней – свойства радиус не выполнятся.

Comment from Irv
Date: January 23, 2016, 1:27 pm

>> в книге об этом не упоминается

раздел 2.1.4 начинается с постановки задачи расчета сопротивлений резистров. сопротивления положительные, а интервалы определяются их погрешностью. отсюда следует, что нижняя граница меньше верхней.

если же мы пытаемся решать более общую задачу, тогда нужно правильно определять понятия верхней и нижней границы

(define (upper-bound interval) (max (car interval) (cdr interval))) 
(define (lower-bound interval) (min (car interval) (cdr interval))) 

Write a comment