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

24 January, 2008 (20:18) | Решения упражнений

Итак, почему же эквивалентные алгебраические выражения дают разные результаты в построенной нами совместно с Лизой интервальной арифметике?

Собственно говоря, а почему они должны давать одинаковые результаты? Ведь интервалы – это не действительные числа. Даже простейшие свойства операций над числами не выполняются для интервалов (например, А/А не даст единицу, так же как А-А не будет равно точно нулю). Обобщая, для интервальной арифметики ни для сложения, ни для умножения не определена обратная операция (вычитание не обратно сложению, а деление не обратно умножению). Для того, чтобы выразить сказанное формально, нужно вводить понятия высшей алгебры (поле, группа, единичный элемент, обратная операция и т.д.), однако и на интуитивном уровне разница между числами и интервалами видится серьезной.

Важным моментом является и понятие эквивалентности интервалов. Пусть мы хотим разделить интервал А=[1, 2] на интервал B=[1, 2]. Мы получим интервал [1/2, 2]. Теперь разделим А на А. Очевидно, мы получим тот же результат. Мы никак не можем учесть при делении то, что теперь на самом деле делимое [1, 2] и делитель [1, 2] – это не просто интервалы с одинаковыми границами, а на самом деле представляют один и тот же объект.

Для того, чтобы пакет для работы с интервальной арифметикой подчинялся законам алгебры, необходимо вводить операции таким образом, чтобы для них выполнялись некоторые базовые свойства (это вновь затронет высшую алгебру). Это принципиально возможно и не представляет особой сложности. С другой стороны нам важна практическая сторона интервальной арифметики (работа с величинами, измеренными с некоторой погрешностью), а не чисто теоретическая система операций. Лиза вводила операции именно таким образом неспроста. Но у введенных таким образом операций нет шансов вписаться в алгебраические законы, поскольку они нарушают базовые принципы самой алгебры.

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

Comments

Comment from thror
Date: February 15, 2008, 12:26 am

Приведу некоторый подход иного сорта, чем основанный на понятии идентичности. Пока без комментариев—обещаю их в ближайшем будущем. Главное—обратите пока внимание на процедуру apply-formula.

Я опишу, как она работает подробно позже (а то уже %-)), а пока замечу только, что если бы не было всех этих интервалов, одна она заслуживала бы очень пристального внимания, поскольку это инструмент, сочетающий в себе простоту и настоящую мощность.

Можете не читать все остальное из комментария, но процедуру apply-formula (и соответственно используемую ею map-iterator) изучить стоит.

(define (make-interval lower upper)
  (list lower upper))

(define (lower-bound x)
  (car x))

(define (upper-bound x)
  (cadr x))

(define (make-center-width c w)
  (make-interval (- c w) (+ c w)))

(define (center i)
  (/ (+ (lower-bound i) (upper-bound i)) 2))

(define (width i)
  (/ (- (upper-bound i) (lower-bound i)) 2))

(define (make-center-percent c p)
  (let ((w (/ (* c p) 100.0)))
    (make-center-width c w)))

(define (percent i)
  (* (/ (width i) (center i)) 100.0))

;; %-)

(define (map-iterator functions values)
  (define (iter f r)
    (if (null? f)
        r
        (iter (cdr f) (append r (map (car f) values)))))
  
  (iter functions '()))

(define (apply-formula formula intervals)
  (if (null? intervals)
      formula
      (apply-formula (map-iterator formula (car intervals))
                     (cdr intervals))))

(define (max-value items)
  (define (iter i r)
    (if (null? i)
        r
        (iter (cdr i) (max (car i) r))))
  
  (iter items (car items)))

(define (min-value items)
  (define (iter i r)
    (if (null? i)
        r
        (iter (cdr i) (min (car i) r))))
  
  (iter items (car items)))

(define (calculate-interval formula intervals)
  (let ((vals-list (apply-formula (list formula) intervals)))
    (list (min-value vals-list)
          (max-value vals-list))))

;; %-)

(define (par1 r1 r2)
  (define formula (lambda (x) (lambda (y) (/ (* x y) (+ x y)))))
  
  (calculate-interval formula (list r1 r2)))

(define (par2 r1 r2)
  (define formula (lambda (x) (lambda (y) (/ 1.0 (+ (/ 1.0 x) (/ 1.0 y))))))
  
  (calculate-interval formula (list r1 r2)))

(define r1 (make-center-percent 6.8 10.0))
(define r2 (make-center-percent 4.7 5.0))

(par1 r1 r2)
(par2 r1 r2)

–thror

Comment from thror
Date: February 15, 2008, 4:42 pm

Итак, первый комментарий из нескольких.

Рассмотрим функцию F(x1,…,xn), аргументы которой принимают следующие значения

x1=a1_1,…,a1_k1
x2=a2_1,…,a2_k2

xn=an_1,…,an_kn

(далее я буду записывать более кратко xj=aj_1,…,aj_kj, j=1,…,n)

Поставим задачу следующим образом—пусть для заданной функции F и конечным множествам изменения аргументов требуется построить множество всех возможных значений функции на этих аргументах. Всего таких значений вообще говоря m=k1*…*kn, хотя не все могут быть различны.

Представим функцию F в виде набора из одной функции

(lambda (x1) (lambda (x2) (lambda (x3) (… (lambda (xn) (F x1 x2 … xn))))))

Шаг 1: Подставляя вместо x1 множество его значений получим набор из k1 функций

(lambda (x2) (… (lambda (xn) (F a1_1 x2 … xn))))
(lambda (x2) (… (lambda (xn) (F a1_2 x2 … xn))))

(lambda (x2) (… (lambda (xn) (F a1_k1 x2 … xn))))

Шаг 2: Подставляя вместо x2 множество его значений получим набор из k1*k2 функций

(lambda (x2) (… (lambda (xn) (F a1_1 a2_1 x3 … xn))))
(lambda (x2) (… (lambda (xn) (F a1_1 a2_2 x3 … xn))))

(lambda (x2) (… (lambda (xn) (F a1_k1 a2_k2 x3 … xn))))

На n-1 ом шаге получим набор из k1*…*k{n-1} функций одного аргумента.

На последнем шаге получаем набор из k1*…*kn уже не функций, а чисел—искомое множество значений функции на заданных аргументах.

Выполением каждого шага занимается map-iterator, apply-formula же реализует этот алгоритм целиком.

Далее я покажу зачем мне это нужно.

–thror

Comment from thror
Date: February 19, 2008, 4:17 pm

Итак, значит, к чему это? Вот к такой теореме:

Рассмотрим алгебраическую запись иньервальной формулы f — F(x1,…xn). Предположим для f можно построить эквивалентную ей алгебраически запись, содержащую только по одному вхождению каждой из переменных x1,…,xn и расмотрим произвольную такую запись — G(x1,…,xn). Тогда справедливы следующие утверждения:

[1] Результат вычисления f по любой записи H алгебраически эквивалентной F будет иметь погрешность большую или равную чем результат вычисления f по G.

[2] Зная только агебраическую запись F для формулы f можно тем не менее вычислить значение f по алгебраической записи G (т.е. с наименьшей погрешностью).

(Подчеркну, что предполагаем существование G).

Вот в этом смысле Ева (или Лиза, уж не помню =)) была права. Если удастся записать формулу f таким образом, чтоб каждая переменная входила в формулу только однажды, то

1. такая запись будет иметь наименьшую погрешность
2. и самое главное—даже не строя такой записи, мы тем не менее сможем вычислить по ней значение формулы.

Алгоритм такого вычисления и представлен выше.

Comment from thror
Date: February 19, 2008, 4:24 pm

Замечу, что это не попытка постоить идеальную систему интервальной арифметики =) Это вообще кажется комментарий к предыдущему упражнению…

–thror

Comment from Sergey Khenkin
Date: February 19, 2008, 4:44 pm

Да, точно. Но мысли интересные. Сейчас поставлю оттуда ссылку сюда :)

Comment from thror
Date: February 20, 2008, 12:57 am

существует строгое обоснование этого факта под номером 1, которое я скоро напишу сюда в свободное время. Факт 2 конечно доказан конструктивно приведением соответствующего алгоритма.–трор

Comment from gorilych
Date: July 18, 2008, 6:01 am

способ нахождения (приближённо) погрешностей можно найти в любом справочнике по проведению физ. экспериментов. Идеальный общий метод соответствовал бы нахождению максимума и минимума функции на области пространства, а такого нет даже для функции одной переменной..

Write a comment