В интервальном анализе основным объектом исследования является интервал, представляющий собой замкнутый числовой промежуток. Так, интервал $$[a,b]$$ содержит все вещественные числа, заключенные между границами интервала, включая и сами границы $$a$$ и $$b$$. Когда говорят об интервальной неопределенности, подразумевают неполное знание о некоторой величине, т. е. невозможность указать ее точное значение, но возможность обозначить только границы ее изменения. Понятно, что ширина интервала есть мера неопределенности интересующей нас величины. Математическая теория, изучающая задачи с интервальными неопределенностями, получила название интервального анализа.
Ясно, что арифметические операции над величинами, имеющими интервальную неопределенность, будут давать результаты, также содержащие интервальную неопределенность.
Методы интервального анализа [4] [26], развитые к настоящему времени, базируются на использовании арифметических операций с вещественными и
Заметим, что источниками неопределенностей различных величин могут быть разнообразные факторы. В частности, таким источниками могут быть ограниченность разрядной сетки компьютера, ошибки различных преобразований, к примеру, преобразований чисел из одной системы счисления в другую, неточности измерений значений величин из-за естественного несовершенства измерительных приборов и т. п.
Необходимо отметить, что интервальный анализ - это не единственная теория, которая оперирует с величинами, содержащими неопределенности. Так, с подобного рода величинами имеют дело теории, использующие их размытые (нечеткие) или вероятностные описания. В связи с этим возникает естественный вопрос: имеет ли интервальный анализ какие-либо достоинства, которые отсутствуют, например, у теории вероятностей или теории нечетких множеств, нечетких графов и т. д.? Надо сказать, что такие достоинства у интервального анализа имеются. В частности, одно из них состоит в более высоком уровне развития математического аппарата для исследований. Так, ни в теории нечетких множеств, ни в теории вероятностей пока не достигнут тот качественный уровень методов решения систем уравнений с неопределенностями, который имеет место для интервальных систем уравнений.
Отметим также еще одно достоинство интервального анализа. Ранее все модели неопределенности, используемые при оценке параметров и идентификации, имели главным образом стохастический или вероятностный характер, базируясь на известных распределениях рассматриваемых величин и т. п. К сожалению, на практике часто бывает совершенно недостаточно информации, чтобы считать неопределенные факторы подчиняющимися какой-либо вероятностной модели, либо эти факторы не удовлетворяют тем или иным условиям, которые на них налагает вероятностная модель неопределенности. К примеру, таковыми могут быть условия независимости величин или специальный вид их распределения. С этой точки зрения интервальные неопределенности являются наименее ограничительными и более адекватны многим практическим задачам.
Укажем еще одну сферу применения интервального анализа - вычисления с приближенными числами, обеспечивающие достаточно точный учет ошибок округлений. Хорошо известно, что все современные компьютеры оперируют с числами, представленными в форме с плавающей запятой. Однако, к сожалению, они не вполне адекватны не только реальному физическому миру, но и его математическим моделям. Недостатками чисел с плавающей запятой является отсутствие информации о точности тех величин, которые они представляют. Недостатком их является невозможность представить многие используемые вещественные величины в виде чисел с конечной длиной мантиссы. Наконец, еще одним недостатком является отсутствие адекватности между свойствами арифметических операций над
Из сказанного следует, что вычисления с плавающей запятой не позволяют отслеживать вычислительных ошибок и потому не дают возможности произвести анализ точности результатов. Последнее чревато серьезными негативными последствиями при принятии критических решений на основе полученных приближенных результатов.
Обратимся теперь к рассматриваемым нами в курсе лекций линейным автоматам, задаваемым над конечным полем $$GF(p) $$. С физической точки зрения значения напряжений для входных и выходных сигналов, а также напряжений, которые связаны с представлениями сигналов в элементах памяти электронных устройств, описываемых моделями линейных автоматов, можно измерять в квантованных (калибровочных) единицах. Поскольку по техническим условиям значения напряжений имеют ограничения сверху, предельное значение этого напряжения, выраженное в квантованных единицах, можно принять в качестве характеристики p поля $$GF(p) $$. Такое постулирование приводит к необходимости оперировать с
Поскольку измерение значений входных и выходных сигналов из-за ограниченной точности измерительных приборов приводит к появлению интервалов, к которым принадлежат эти значения, возникает необходимость разработки фрагмента специфического интервального анализа. Основным объектом такого анализа является интервал с конечным числом элементов, границами которого являются элементы поля $$GF(p) $$. Заметим, что некоторые результаты такого анализа не имеют аналогов в интервальном анализе над вещественным полем $$R$$.
Отметим, наконец, что на первый взгляд конечность поля $$GF(p) $$ должна была бы привести к упрощению соответствующей арифметики, однако на самом деле произошло ее усложнение, что будет видно из результатов, изложенных в следующем разделе этой лекции.
Рассмотренные в предыдущих лекциях синхронизирующие, установочные и диагностические эксперименты с линейными автоматами предполагали возможность получения в процессе их проведения точных значений реакций автоматов. Но, как уже упоминалось ранее, из-за несовершенства измерительных приборов более адекватным является предположение, что реакции автоматов представлены в интервальной форме. Понятно, что методы теории экспериментов, изложенные в предыдущих лекциях, не могут быть непосредственно применены для решения соответствующих задач в интервальной постановке. Однако их решение становится возможным с применением интервальной арифметики над полем $$GF(p) $$ и специально разработанных для этих целей методов. В некоторых случаях такие методы являются аналогами "точных" методов, разработанных ранее, в иных же случаях "интервальные" методы таких аналогов не имеют. Таким образом,
Начнем с обозначений и основных определений. Строчные греческие буквы $$\alpha, \beta, \gamma, \dots$$, а также латинские с чертой снизу или сверху $$\underline a, \bar a, \underline b, \bar b, \dots$$ будут далее обозначать элементы поля $$GF(p)=\{0,1,\dots , p-1\}$$, где $$p$$ - простое число. Элемент этого поля представляет собой класс вычетов. Условимся далее считать, что каждый такой класс заменяется его представителем - наименьшим целым положительным числом, входящим в этот класс. На множестве классов вычетов определим отношения порядка $$(<, \le, \ge, >)$$, которые естественным образом индуцируются соответствующими отношениями порядка на множестве целых чисел.
Подмножество $$\subseteq GF(p)$$, такое, что $$a=[\underline a, \bar a]=\{\alpha \underline a \le \alpha \le \bar a; \underline a, \bar a \in GF(p)\}$$ будем называть правильным замкнутым интервалом, где $$\underline a$$ и $$\bar a$$ - соответственно его нижняя и верхняя границы.
Запись вида $$b=[\underline b, \bar b]$$, где $$\underline b > \bar b$$, будем интерпретировать как множество $$GF(p)\ [\bar b+1, \underline b-1]$$ и называть это множество неправильным интервалом.
Интервал вида $$[\underline a, \bar a]$$, где $$\underline a=\bar a$$, будем называть вырожденным и интерпретировать его как элемент поля $$GF(p) $$.
Множество всех интервалов над $$GF(p) $$ обозначим через $$IGF(p)$$, а латинские буквы зарезервируем для обозначения интервалов.
Исходя из интерпретации неправильного интервала $$[\underline b, \bar a]$$ как множества "внешних" элементов $$GF(p) $$ по отношению к правильному интервалу $$[\bar b+1, \underline b-1]$$, любой неправильный интервал может быть представлен в следующем виде:
$$[\underline b, \bar b]=[0, \bar b]\bigcup [\underline b, p-1]$$Определение 19.1. Два интервала $$a=[\underline a, \bar a]$$ и $$b=[\underline b, \bar b]$$ называются равными (и записывается это как $$a=b$$ ), если они равны в смысле теории множеств.
Из этого определения следует, что $$\underline a=\underline b \bar a=\bar b \to a=b$$, но обратная импликация, в отличие от случая вещественных интервалов, места не имеет. Например, при $$p=5$$ интервалы [2,1] и [3,2] равны как множества, однако их границы не совпадают. Легко видеть, что для любого $$\alpha \in GF(p)$$ справедливо равенство $$[\alpha, \alpha-1]=[0,p-1]$$
Очевидно, что отношение равенства в $$IGF(p)$$ рефлексивно, симметрично и транзитивно.
Введем операции над элементами $$IGF(p) $$. Далее знаками +, -, ., / будем обозначать соответствующие арифметические операции над вещественными числами, а знаками $$\oplus, \circleddash, \odot, \oslash$$ операции над элементами поля $$GF(p) $$.
Определение 19.2. Пусть $$\circledast \in \{ \oplus, \circleddash, \odot, \oslash \}$$ - бинарная арифметическая операция над элементами поля $$GF(p) $$. Если $$a,b \in IGF(p)$$, то
$$a \circledast b=\{\xi=\alpha \circledast \beta / \alpha \in \beta, \beta \in b\}$$определяет бинарную арифметическую операцию над $$IGF(p) $$. (В случае деления предполагаем, что $$0 \notin b$$.)
Очевидно, что операции сложения и умножения элементов $$IGF(p)$$ коммутативны.
Если интерпретировать поле $$GF(p) $$ как точки числовой оси, то каждый правильный интервал $$[\underline a, \bar a]$$ - это множество точек, расположенных вплотную одна за другой между $$\underline a$$ и $$\bar a$$.
Отметим, что результатом операции над интервалом может оказаться множество точек, не являющихся одним интервалом, а представляющее собой объединение нескольких интервалов, разбросанных по числовой оси. Например, для $$p=7, [1,2]*[2,3]=[2,4]\bigsup [6,6]$$.
Введем еще одно понятие. Подмножество $$A \subseteq GF(p)$$, такое, что
$$a=Y_{i \in I}a_i$$где $$a_i \in IGF(p), I$$ - конечное множество индексов и для $$I \ne j, a_i \bigcup a_j=\varnothing$$, назовем обобщенным интервалом поля $$GF(p)$$.
Обобщенный интервал будем обозначать строчной буквой. Понятно, что интервал из $$IGF(p) $$ есть частный случай обобщенного интервала. За множеством всех обобщенных интервалов сохраним обозначение $$IGF(p) $$, поскольку из контекста каждый раз ясно, какой именно интервал имеется в виду в конкретном случае.
Введем бинарные операции над обобщенными интервалами.
Определение 19.3. Пусть $$*\in \{+,-,\cdot, \ \}$$ - бинарная операция. Если
$$A=Y_{i \in I}a_i, B=Y_{j \in J}b_j,$$где $$a_i, b_j$$ - обычные интервалы поля $$GF(p) $$, то
$$A*B=(Y_{i\in I}a_i)*(Y_{j\in J}b_i)=Y_{i\in I, j\in J}a_i*b_j$$Заметим, что множество $$IGF(p) $$ обобщенных интервалов является замкнутым относительно введенных бинарных операций.
Как следует из формулы (19.4), любая бинарная операция над обобщенными интервалами сводится к соответствующей операции над обычными интервалами поля $$GF(p) $$.
Введем унарную операцию над обычным интервалом $$x=[\underline x,\bar x] \in IGF(p)$$:
$$-x=[-\underline x,-\bar x] $$где " $$\xi$$ " - это элемент поля $$GF(p) $$, обратный к элементу $$\xi$$ по сложению, т. е. такой, что $$\xi \oplus (-\xi)=0$$. Аналогичную операцию для обобщенного интервала $$X=Y_{i\in I}x_i$$ определим так:
$$-X=Y_{i\in I}(-x_i)$$С использованием этой операции бинарная операция вычитания выражается через операцию сложения:
$$A-B=A+(-B)$$Например, при $$p=5, a=[0,1], b=[4,1] $$, тогда $$[0,1] - [4,1] = [0,1] + (-[4,1]) = = [0,1] + [4,1] = [4,2]$$.
Введем операцию умножения элемента $$\alpha \in GF(p)$$ на обобщенный интервал $$X$$:
$$\alpha \cdot X=Y_{\xi \in X}[\alpha \odot \xi, \alpha \odot \xi]$$Используя эту операцию, бинарную операцию умножения обобщенных интервалов можно записать в виде
$$AB=Y_{\alpha \in A}\alpha B$$Например, если $$p=5, а=[2,4], b=[1,2] $$ то имеем
$$a \cdot b=2[1,2] \bigcup 3[1,2]\bigcup 4[1,2]=[2,2]\bigcup [4,4]\bigcup [3,3]\bigcup [1,1] \bigcup [3,4]=[1,4]$$И наконец, операцию деления обобщенных интервалов можно записать в виде
$$A/B=A(Y_{\beta \in B}1/\beta )$$где $$1/ \beta$$ - это элемент $$GF(p) $$, обратный элементу $$\beta$$ по умножению, т. е. такой, что $$\beta \cdot (1/ \beta)=1$$.
Например, если $$p=5, a=[1,3], b=[3,4] $$, то
$$[1,3]/[3,4]=[1,3](1/3 \bigcup 1/4)= [1,3]*(2 \bigcup 4)=2*[1,3]\bigcup 4*[1,3]=[1,2] \bigcup [4,4]\bigcup [2,4]=[1,4].$$Остановимся на свойствах арифметических операций в $$IGF(p) $$. Напомним, что в классической
где $$f(\xi, \eta)=\xi * \eta , *\in \{+,-, \cdot, /\}, \xi \in x, \eta \in y, x,y \in I(R)$$ (при делении предполагается, что $$0 \notin y$$ ) - непрерывные функции на
Введем понятие ширины обобщенного интервала $$X=Y_{i \in I}x_i$$ и обычного интервала $$x_i=[\underline x_i, \bar x_i]$$, обозначаемых далее как $$w(X)$$ и $$w(x_i)$$ соответственно:
$$w(X)-\sum_{i \in I}w(x_i),\\ w(x_i)= \begin {cases} \bar x_i- \underline x_i+1,\ \mbox{если} \ x_i \ \mbox {правильный интервал},\\ \bar x_i-x_i+p+1, \ \mbox{если} \ x_i \ \mbox {неправильный интервал} \end {cases} $$Понятно, что $$w(x_i)$$ и $$w(X)$$ - это число элементов в соответствующих интервалах. Очевидно также, что $$w(x_i)=\bar x_i \circleddash \underline x_i+1$$ в любом случае.
Пусть $$a=[\underline a, \bar a], b=[\underline b, \bar b]$$ - обычные интервалы поля $$GF(p) $$, тогда для сложения интервалов справедлива следующая формула
$$a+b= \left \{ \bedin {matrix} [\underline a \oplus \bar b, \bar a \oplus \underline b], \qquad \mbox{если} \qquad w(a)+w(b) \le p,\\ [0, p-1] \qquad \mbox{в противном случае} \qquad \end {matrix}$$Доказательство этой формулы приведено в [31].
Аналогично, для операции вычитания обычных интервалов справедлива следующая формула
$$a-b= \left \{ \begin {matrix} [\underline a \circleddash \bar b, \bar a \circleddash b], \ \mbox {если} \ w(a)+w(b) \le p,\\ [0, p-1] \ \mbox {в противном случае} \qquad \end {matrix}$$Произведение и частное интервалов представить через операции с границами сомножителей в общем случае не удается. Ситуация по сравнению с классической интервальной арифметикой осложняется в связи с тем, что, к примеру, для произведения интервалов не выполняется даже включение: $$ab \subseteq [\underline a \odot \underline b, \bar a \odot \bar b].$$
Следующее утверждение, доказательство которого приведено в [31], касается свойств введенных интервальных операций и самих интервалов.
Теорема 19.1. Пусть $$A,B,C \in IGF(p)$$, тогда:
Заметим, что $$IGF(p) $$ с введенными операциями сложения и умножения на число не является
где
$$\lambda , \mu \in GF(p), A \in IGF(p)$$Как и в классической
Рассмотрим уравнение относительно Х
$$f(A,X)=B$$зависящее от некоторых параметров $$(A_1, \dots, A_s)^T$$, где $$A_i, B \in IGF(p), i=\overline {1,s}, f(A,X)$$ - рациональное выражение, которое состоит из интервалов $$A,X$$ соединенных знаками арифметических операций.
Определение 19.4. Назовем алгебраическим решением уравнения (19.9) такой обобщенный интервал $$X \in IGF(p)$$, что при его подстановке в (19.9) получается точное равенство.
Пусть, например, $$p=5$$ и рассматривается уравнение $$[1,2]+X=[4,2]$$. Можно убедиться, что интервалы $$X_1=[0,0] \bigcup [3,3] $$ и $$X_2=[3,0] ([3,0]=[0,0] \bigcup [3,3] \bigcup [4,4])$$, подставленные в заданное уравнение, дают точное равенство, т. е. оба этих интервала являются алгебраическими решениями. Из этого примера следует, что алгебраическое решение уравнения $$A+X=B$$ в общем случае не единственно.
Следующие определения множеств решений были введены в [51] для множеств решений интервальных систем линейных алгебраических уравнений, здесь эти множества решений определяются для уравнений (19.9).
Определение 19.5. Назовем
Так, для уравнения $$[1,2]+X=[4,2]$$ объединенное множество решений есть $$X_{\exists \exists }=[0,4]$$.
Определение 19.6. Назовем
Для рассмотренного выше примера $$X_{\forall \exists }=[3,0]$$, т. е. для этого уравнения имеет место включение $$X_{\forall \exists } \subset X_{\exists \exists }$$. Легко показать, что такое включение справедливо и в общем случае. Кроме того, для этого же примера $$X_{\forall \exists }=X_2$$, т. е. допустимое множество решений совпадает с одним из алгебраических решений.
Определение 19.7. Назовем управляемым множеством решений уравнения (19.9) следующее множество:
$$X_{\forall \exists }=\{\xi \in GF(p)|(\forall \beta \in B)( \exists \alpha \in A) \vdots f(\alpha, \xi )=\beta \}$$Так, для $$р=5$$ уравнение $$[1,3]+X=[0,1]$$ управляемое множество решений есть $$X_{\exists \forall }=[3,4]$$.
Теорема 19.2. Линейное уравнение $$a+X=b$$, где $$a,b$$ - обычные интервалы над полем $$GF(p) $$, имеет алгебраическое решение $$X$$ в виде обобщенного интервала тогда и только тогда, когда $$w(a) \le w(b)$$.
Доказательство.
Необходимость. Докажем ее от противного. Пусть $$w(a)>w(b)$$. Покажем, что в этом случае рассматриваемое уравнение решений не имеет. Пусть $$a=\{\alpha_1, \dots, \alpha_{\mu}\}$$. Выберем произвольный элемент $$\xi \in GF(p)$$ и построим множество $$a_{\xi}=\{\alpha_1 \oplus \xi, \dots, \alpha_{\mu} \oplus \xi\}$$. Очевидно, что в $$a_{\xi}$$ все элементы попарно различны т. е. $$w(a_{\xi})=\mu$$. Элемент $$\xi \notin X$$ поскольку среди элементов $$A_{\xi}$$ существует по крайней мере один такой элемент $$a_i \oplus \xi \notin b$$ ибо $$w(b)< \mu$$. Из произвольности элемента $$\xi$$ следует, что в $$X$$ нет ни одного элемента $$GF(p),$$ т. е. алгебраическое решение пусто.
Достаточность. Пусть $$w(a) \le w(b)$$ тогда алгебраическое решение есть $$X=[\underline b \circleddash \underline a, \bar b \circleddash \bar a], a+X=[a,a]+[ \underline b \circleddash \underline a, \bar b \circleddash \bar a]= \underline a \oplus \underline b \circleddash \underline a, \bar a \oplus \bar b \circleddash \bar a]=[ \underline b, \bar b]=b$$. При этом по свойству 11 в теореме 19.1 $$w(b)=w(a +X)=w(a)+w(X)-1$$. Отсюда следует, что $$w(b)-w(a)=w(X)-1$$ Тогда, учитывая, что $$w(a) \le w(b)$$, получим $$w(X) \ge 1$$, т. е. множество $$X$$ не пусто.
Заметим, что теорема 19.2 для случая, когда в уравнении $$A+X=B$$ вместо обычных интервалов использованы обобщенные интервалы, неверна. В самом деле, пусть $$p=7, A+[1,1] \bigcup [3,3] \bigcup [5,5], B+[6,2]$$. Перебором можно проверить, что уравнение в этом случае алгебраического решения не имеет.
Для существования алгебраического решения уравнения $$AX=B$$ условие $$w(A) \le w(B)$$ является необходимым, но не является достаточным даже для случая, когда $$A$$ и $$B$$ - обычные интервалы. Например, при $$p=7$$ уравнение $$[2,4]*X=[2,5]$$ алгебраического решения не имеет, хотя $$w(A)=3 < w(B)=4$$. В то же время это уравнение имеет объединенное множество решений $$X_{\exists \exists }=[1,6]$$ и допустимое множество решений $$X_{\forall \exists }=[1,1] \bigcup [6,6]$$.
Для уравнения
$$A+X=B$$введенные множества решений определяются следующим образом:
$$X_{\exists \exists }=Y_{\alpha \in A}Y_{\beta \in B}(\beta \circleddash \alpha)=B_A$$ $$X_{\forall \exists }=I_{\alpha \in A}Y_{\beta \in B}(\beta \circleddash \alpha)$$ $$X_{\forall \exists }=I_{\beta \in B}Y_{\alpha \in A}(\beta \circleddash \alpha)$$Для уравнения
$$AX=B$$где
$$0 \notin A$$множество решений определяются аналогично:
$$X_{\exists \exists }=Y_{\alpha \in A}Y_{\beta \in B}(\beta \oslash \alpha)=B/A$$ $$X_{\forall \exists }=I_{\alpha \in A}Y_{\beta \in B}(\beta \oslash \alpha)$$ $$X_{\forall \exists }=I_{\beta \in B}Y_{\alpha \in A}(\beta \oslash \alpha)$$Равенства (19.10)-(19.12), (19.13)-(19.15) следуют из определения множеств $$X_{\exists \exists}, X_{\forall \exists }, X_{\exists \forall}$$ и определения
Рассмотрим пример. Пусть $$p=7$$ и уравнение имеет вид
$$[2,4]*X=[2,5]$$Для наглядности построим таблицу деления $$\beta \oslash \alpha$$, где $$\beta \in [2,5], \alpha \in [2,4]$$.
| $$\alpha \ \beta$$ | 2 | 3 | 4 | 5 |
|---|---|---|---|---|
| 2 | 1 | 5 | 2 | 6 |
| 3 | 3 | 1 | 6 | 4 |
| 4 | 4 | 6 | 1 | 3 |
Объединение всех элементов строк (столбцов) таблицы составляет объединенное множество решений $$X_{\exists \exists}=[1,6]$$. Пересечение элементов строк таблицы составляет допустимое множество решений $$X_{\forall \exists }=[1,1] \bigsup [6,6]$$. Пересечение элементов столбцов таблицы пусто, поэтому $$X_{\exists \forall}= \varnothing$$ и управляемых решений уравнение не имеет.
Теорема 19.3. Все множество решений уравнений $$A+X=B$$ и $$AX=B$$ и алгебраическое решение, если оно существует, включаются в объединенное множество решений, т. е. в $$B-A$$ для уравнения $$A+X=B$$ и в $$B\A$$ для уравнения $$AX=B$$
Доказательство этой теоремы следует из равенств (19.10)-(19.12), (19.13)-(19.15) для множеств решений. Для алгебраического решения очевидно, что если оно существует, то все его элементы являются допустимыми решениями и, следовательно, принадлежат также и объединенному множеству решений.
В интервальном анализе основным объектом исследования является интервал, представляющий собой замкнутый числовой промежуток. Так, интервал $$[a,b]$$ содержит все вещественные числа, заключенные между границами интервала, включая и сами границы $$a$$ и $$b$$. Когда говорят об интервальной неопределенности, подразумевают неполное знание о некоторой величине, т. е. невозможность указать ее точное значение, но возможность обозначить только границы ее изменения. Понятно, что ширина интервала есть мера неопределенности интересующей нас величины. Математическая теория, изучающая задачи с интервальными неопределенностями, получила название интервального анализа.
Ясно, что арифметические операции над величинами, имеющими интервальную неопределенность, будут давать результаты, также содержащие интервальную неопределенность.
Методы интервального анализа [4] [26], развитые к настоящему времени, базируются на использовании арифметических операций с вещественными и
Заметим, что источниками неопределенностей различных величин могут быть разнообразные факторы. В частности, таким источниками могут быть ограниченность разрядной сетки компьютера, ошибки различных преобразований, к примеру, преобразований чисел из одной системы счисления в другую, неточности измерений значений величин из-за естественного несовершенства измерительных приборов и т. п.
Необходимо отметить, что интервальный анализ - это не единственная теория, которая оперирует с величинами, содержащими неопределенности. Так, с подобного рода величинами имеют дело теории, использующие их размытые (нечеткие) или вероятностные описания. В связи с этим возникает естественный вопрос: имеет ли интервальный анализ какие-либо достоинства, которые отсутствуют, например, у теории вероятностей или теории нечетких множеств, нечетких графов и т. д.? Надо сказать, что такие достоинства у интервального анализа имеются. В частности, одно из них состоит в более высоком уровне развития математического аппарата для исследований. Так, ни в теории нечетких множеств, ни в теории вероятностей пока не достигнут тот качественный уровень методов решения систем уравнений с неопределенностями, который имеет место для интервальных систем уравнений.
Отметим также еще одно достоинство интервального анализа. Ранее все модели неопределенности, используемые при оценке параметров и идентификации, имели главным образом стохастический или вероятностный характер, базируясь на известных распределениях рассматриваемых величин и т. п. К сожалению, на практике часто бывает совершенно недостаточно информации, чтобы считать неопределенные факторы подчиняющимися какой-либо вероятностной модели, либо эти факторы не удовлетворяют тем или иным условиям, которые на них налагает вероятностная модель неопределенности. К примеру, таковыми могут быть условия независимости величин или специальный вид их распределения. С этой точки зрения интервальные неопределенности являются наименее ограничительными и более адекватны многим практическим задачам.
Укажем еще одну сферу применения интервального анализа - вычисления с приближенными числами, обеспечивающие достаточно точный учет ошибок округлений. Хорошо известно, что все современные компьютеры оперируют с числами, представленными в форме с плавающей запятой. Однако, к сожалению, они не вполне адекватны не только реальному физическому миру, но и его математическим моделям. Недостатками чисел с плавающей запятой является отсутствие информации о точности тех величин, которые они представляют. Недостатком их является невозможность представить многие используемые вещественные величины в виде чисел с конечной длиной мантиссы. Наконец, еще одним недостатком является отсутствие адекватности между свойствами арифметических операций над
Из сказанного следует, что вычисления с плавающей запятой не позволяют отслеживать вычислительных ошибок и потому не дают возможности произвести анализ точности результатов. Последнее чревато серьезными негативными последствиями при принятии критических решений на основе полученных приближенных результатов.
Обратимся теперь к рассматриваемым нами в курсе лекций линейным автоматам, задаваемым над конечным полем $$GF(p) $$. С физической точки зрения значения напряжений для входных и выходных сигналов, а также напряжений, которые связаны с представлениями сигналов в элементах памяти электронных устройств, описываемых моделями линейных автоматов, можно измерять в квантованных (калибровочных) единицах. Поскольку по техническим условиям значения напряжений имеют ограничения сверху, предельное значение этого напряжения, выраженное в квантованных единицах, можно принять в качестве характеристики p поля $$GF(p) $$. Такое постулирование приводит к необходимости оперировать с
Поскольку измерение значений входных и выходных сигналов из-за ограниченной точности измерительных приборов приводит к появлению интервалов, к которым принадлежат эти значения, возникает необходимость разработки фрагмента специфического интервального анализа. Основным объектом такого анализа является интервал с конечным числом элементов, границами которого являются элементы поля $$GF(p) $$. Заметим, что некоторые результаты такого анализа не имеют аналогов в интервальном анализе над вещественным полем $$R$$.
Отметим, наконец, что на первый взгляд конечность поля $$GF(p) $$ должна была бы привести к упрощению соответствующей арифметики, однако на самом деле произошло ее усложнение, что будет видно из результатов, изложенных в следующем разделе этой лекции.
Рассмотренные в предыдущих лекциях синхронизирующие, установочные и диагностические эксперименты с линейными автоматами предполагали возможность получения в процессе их проведения точных значений реакций автоматов. Но, как уже упоминалось ранее, из-за несовершенства измерительных приборов более адекватным является предположение, что реакции автоматов представлены в интервальной форме. Понятно, что методы теории экспериментов, изложенные в предыдущих лекциях, не могут быть непосредственно применены для решения соответствующих задач в интервальной постановке. Однако их решение становится возможным с применением интервальной арифметики над полем $$GF(p) $$ и специально разработанных для этих целей методов. В некоторых случаях такие методы являются аналогами "точных" методов, разработанных ранее, в иных же случаях "интервальные" методы таких аналогов не имеют. Таким образом,
Начнем с обозначений и основных определений. Строчные греческие буквы $$\alpha, \beta, \gamma, \dots$$, а также латинские с чертой снизу или сверху $$\underline a, \bar a, \underline b, \bar b, \dots$$ будут далее обозначать элементы поля $$GF(p)=\{0,1,\dots , p-1\}$$, где $$p$$ - простое число. Элемент этого поля представляет собой класс вычетов. Условимся далее считать, что каждый такой класс заменяется его представителем - наименьшим целым положительным числом, входящим в этот класс. На множестве классов вычетов определим отношения порядка $$(<, \le, \ge, >)$$, которые естественным образом индуцируются соответствующими отношениями порядка на множестве целых чисел.
Подмножество $$\subseteq GF(p)$$, такое, что $$a=[\underline a, \bar a]=\{\alpha \underline a \le \alpha \le \bar a; \underline a, \bar a \in GF(p)\}$$ будем называть правильным замкнутым интервалом, где $$\underline a$$ и $$\bar a$$ - соответственно его нижняя и верхняя границы.
Запись вида $$b=[\underline b, \bar b]$$, где $$\underline b > \bar b$$, будем интерпретировать как множество $$GF(p)\ [\bar b+1, \underline b-1]$$ и называть это множество неправильным интервалом.
Интервал вида $$[\underline a, \bar a]$$, где $$\underline a=\bar a$$, будем называть вырожденным и интерпретировать его как элемент поля $$GF(p) $$.
Множество всех интервалов над $$GF(p) $$ обозначим через $$IGF(p)$$, а латинские буквы зарезервируем для обозначения интервалов.
Исходя из интерпретации неправильного интервала $$[\underline b, \bar a]$$ как множества "внешних" элементов $$GF(p) $$ по отношению к правильному интервалу $$[\bar b+1, \underline b-1]$$, любой неправильный интервал может быть представлен в следующем виде:
$$[\underline b, \bar b]=[0, \bar b]\bigcup [\underline b, p-1]$$Определение 19.1. Два интервала $$a=[\underline a, \bar a]$$ и $$b=[\underline b, \bar b]$$ называются равными (и записывается это как $$a=b$$ ), если они равны в смысле теории множеств.
Из этого определения следует, что $$\underline a=\underline b \bar a=\bar b \to a=b$$, но обратная импликация, в отличие от случая вещественных интервалов, места не имеет. Например, при $$p=5$$ интервалы [2,1] и [3,2] равны как множества, однако их границы не совпадают. Легко видеть, что для любого $$\alpha \in GF(p)$$ справедливо равенство $$[\alpha, \alpha-1]=[0,p-1]$$
Очевидно, что отношение равенства в $$IGF(p)$$ рефлексивно, симметрично и транзитивно.
Введем операции над элементами $$IGF(p) $$. Далее знаками +, -, ., / будем обозначать соответствующие арифметические операции над вещественными числами, а знаками $$\oplus, \circleddash, \odot, \oslash$$ операции над элементами поля $$GF(p) $$.
Определение 19.2. Пусть $$\circledast \in \{ \oplus, \circleddash, \odot, \oslash \}$$ - бинарная арифметическая операция над элементами поля $$GF(p) $$. Если $$a,b \in IGF(p)$$, то
$$a \circledast b=\{\xi=\alpha \circledast \beta / \alpha \in \beta, \beta \in b\}$$определяет бинарную арифметическую операцию над $$IGF(p) $$. (В случае деления предполагаем, что $$0 \notin b$$.)
Очевидно, что операции сложения и умножения элементов $$IGF(p)$$ коммутативны.
Если интерпретировать поле $$GF(p) $$ как точки числовой оси, то каждый правильный интервал $$[\underline a, \bar a]$$ - это множество точек, расположенных вплотную одна за другой между $$\underline a$$ и $$\bar a$$.
Отметим, что результатом операции над интервалом может оказаться множество точек, не являющихся одним интервалом, а представляющее собой объединение нескольких интервалов, разбросанных по числовой оси. Например, для $$p=7, [1,2]*[2,3]=[2,4]\bigsup [6,6]$$.
Введем еще одно понятие. Подмножество $$A \subseteq GF(p)$$, такое, что
$$a=Y_{i \in I}a_i$$где $$a_i \in IGF(p), I$$ - конечное множество индексов и для $$I \ne j, a_i \bigcup a_j=\varnothing$$, назовем обобщенным интервалом поля $$GF(p)$$.
Обобщенный интервал будем обозначать строчной буквой. Понятно, что интервал из $$IGF(p) $$ есть частный случай обобщенного интервала. За множеством всех обобщенных интервалов сохраним обозначение $$IGF(p) $$, поскольку из контекста каждый раз ясно, какой именно интервал имеется в виду в конкретном случае.
Введем бинарные операции над обобщенными интервалами.
Определение 19.3. Пусть $$*\in \{+,-,\cdot, \ \}$$ - бинарная операция. Если
$$A=Y_{i \in I}a_i, B=Y_{j \in J}b_j,$$где $$a_i, b_j$$ - обычные интервалы поля $$GF(p) $$, то
$$A*B=(Y_{i\in I}a_i)*(Y_{j\in J}b_i)=Y_{i\in I, j\in J}a_i*b_j$$Заметим, что множество $$IGF(p) $$ обобщенных интервалов является замкнутым относительно введенных бинарных операций.
Как следует из формулы (19.4), любая бинарная операция над обобщенными интервалами сводится к соответствующей операции над обычными интервалами поля $$GF(p) $$.
Введем унарную операцию над обычным интервалом $$x=[\underline x,\bar x] \in IGF(p)$$:
$$-x=[-\underline x,-\bar x] $$где " $$\xi$$ " - это элемент поля $$GF(p) $$, обратный к элементу $$\xi$$ по сложению, т. е. такой, что $$\xi \oplus (-\xi)=0$$. Аналогичную операцию для обобщенного интервала $$X=Y_{i\in I}x_i$$ определим так:
$$-X=Y_{i\in I}(-x_i)$$С использованием этой операции бинарная операция вычитания выражается через операцию сложения:
$$A-B=A+(-B)$$Например, при $$p=5, a=[0,1], b=[4,1] $$, тогда $$[0,1] - [4,1] = [0,1] + (-[4,1]) = = [0,1] + [4,1] = [4,2]$$.
Введем операцию умножения элемента $$\alpha \in GF(p)$$ на обобщенный интервал $$X$$:
$$\alpha \cdot X=Y_{\xi \in X}[\alpha \odot \xi, \alpha \odot \xi]$$Используя эту операцию, бинарную операцию умножения обобщенных интервалов можно записать в виде
$$AB=Y_{\alpha \in A}\alpha B$$Например, если $$p=5, а=[2,4], b=[1,2] $$ то имеем
$$a \cdot b=2[1,2] \bigcup 3[1,2]\bigcup 4[1,2]=[2,2]\bigcup [4,4]\bigcup [3,3]\bigcup [1,1] \bigcup [3,4]=[1,4]$$И наконец, операцию деления обобщенных интервалов можно записать в виде
$$A/B=A(Y_{\beta \in B}1/\beta )$$где $$1/ \beta$$ - это элемент $$GF(p) $$, обратный элементу $$\beta$$ по умножению, т. е. такой, что $$\beta \cdot (1/ \beta)=1$$.
Например, если $$p=5, a=[1,3], b=[3,4] $$, то
$$[1,3]/[3,4]=[1,3](1/3 \bigcup 1/4)= [1,3]*(2 \bigcup 4)=2*[1,3]\bigcup 4*[1,3]=[1,2] \bigcup [4,4]\bigcup [2,4]=[1,4].$$Остановимся на свойствах арифметических операций в $$IGF(p) $$. Напомним, что в классической
где $$f(\xi, \eta)=\xi * \eta , *\in \{+,-, \cdot, /\}, \xi \in x, \eta \in y, x,y \in I(R)$$ (при делении предполагается, что $$0 \notin y$$ ) - непрерывные функции на
Введем понятие ширины обобщенного интервала $$X=Y_{i \in I}x_i$$ и обычного интервала $$x_i=[\underline x_i, \bar x_i]$$, обозначаемых далее как $$w(X)$$ и $$w(x_i)$$ соответственно:
$$w(X)-\sum_{i \in I}w(x_i),\\ w(x_i)= \begin {cases} \bar x_i- \underline x_i+1,\ \mbox{если} \ x_i \ \mbox {правильный интервал},\\ \bar x_i-x_i+p+1, \ \mbox{если} \ x_i \ \mbox {неправильный интервал} \end {cases} $$Понятно, что $$w(x_i)$$ и $$w(X)$$ - это число элементов в соответствующих интервалах. Очевидно также, что $$w(x_i)=\bar x_i \circleddash \underline x_i+1$$ в любом случае.
Пусть $$a=[\underline a, \bar a], b=[\underline b, \bar b]$$ - обычные интервалы поля $$GF(p) $$, тогда для сложения интервалов справедлива следующая формула
$$a+b= \left \{ \bedin {matrix} [\underline a \oplus \bar b, \bar a \oplus \underline b], \qquad \mbox{если} \qquad w(a)+w(b) \le p,\\ [0, p-1] \qquad \mbox{в противном случае} \qquad \end {matrix}$$Доказательство этой формулы приведено в [31].
Аналогично, для операции вычитания обычных интервалов справедлива следующая формула
$$a-b= \left \{ \begin {matrix} [\underline a \circleddash \bar b, \bar a \circleddash b], \ \mbox {если} \ w(a)+w(b) \le p,\\ [0, p-1] \ \mbox {в противном случае} \qquad \end {matrix}$$Произведение и частное интервалов представить через операции с границами сомножителей в общем случае не удается. Ситуация по сравнению с классической интервальной арифметикой осложняется в связи с тем, что, к примеру, для произведения интервалов не выполняется даже включение: $$ab \subseteq [\underline a \odot \underline b, \bar a \odot \bar b].$$
Следующее утверждение, доказательство которого приведено в [31], касается свойств введенных интервальных операций и самих интервалов.
Теорема 19.1. Пусть $$A,B,C \in IGF(p)$$, тогда:
Заметим, что $$IGF(p) $$ с введенными операциями сложения и умножения на число не является
где
$$\lambda , \mu \in GF(p), A \in IGF(p)$$Как и в классической
Рассмотрим уравнение относительно Х
$$f(A,X)=B$$зависящее от некоторых параметров $$(A_1, \dots, A_s)^T$$, где $$A_i, B \in IGF(p), i=\overline {1,s}, f(A,X)$$ - рациональное выражение, которое состоит из интервалов $$A,X$$ соединенных знаками арифметических операций.
Определение 19.4. Назовем алгебраическим решением уравнения (19.9) такой обобщенный интервал $$X \in IGF(p)$$, что при его подстановке в (19.9) получается точное равенство.
Пусть, например, $$p=5$$ и рассматривается уравнение $$[1,2]+X=[4,2]$$. Можно убедиться, что интервалы $$X_1=[0,0] \bigcup [3,3] $$ и $$X_2=[3,0] ([3,0]=[0,0] \bigcup [3,3] \bigcup [4,4])$$, подставленные в заданное уравнение, дают точное равенство, т. е. оба этих интервала являются алгебраическими решениями. Из этого примера следует, что алгебраическое решение уравнения $$A+X=B$$ в общем случае не единственно.
Следующие определения множеств решений были введены в [51] для множеств решений интервальных систем линейных алгебраических уравнений, здесь эти множества решений определяются для уравнений (19.9).
Определение 19.5. Назовем
Так, для уравнения $$[1,2]+X=[4,2]$$ объединенное множество решений есть $$X_{\exists \exists }=[0,4]$$.
Определение 19.6. Назовем
Для рассмотренного выше примера $$X_{\forall \exists }=[3,0]$$, т. е. для этого уравнения имеет место включение $$X_{\forall \exists } \subset X_{\exists \exists }$$. Легко показать, что такое включение справедливо и в общем случае. Кроме того, для этого же примера $$X_{\forall \exists }=X_2$$, т. е. допустимое множество решений совпадает с одним из алгебраических решений.
Определение 19.7. Назовем управляемым множеством решений уравнения (19.9) следующее множество:
$$X_{\forall \exists }=\{\xi \in GF(p)|(\forall \beta \in B)( \exists \alpha \in A) \vdots f(\alpha, \xi )=\beta \}$$Так, для $$р=5$$ уравнение $$[1,3]+X=[0,1]$$ управляемое множество решений есть $$X_{\exists \forall }=[3,4]$$.
Теорема 19.2. Линейное уравнение $$a+X=b$$, где $$a,b$$ - обычные интервалы над полем $$GF(p) $$, имеет алгебраическое решение $$X$$ в виде обобщенного интервала тогда и только тогда, когда $$w(a) \le w(b)$$.
Доказательство.
Необходимость. Докажем ее от противного. Пусть $$w(a)>w(b)$$. Покажем, что в этом случае рассматриваемое уравнение решений не имеет. Пусть $$a=\{\alpha_1, \dots, \alpha_{\mu}\}$$. Выберем произвольный элемент $$\xi \in GF(p)$$ и построим множество $$a_{\xi}=\{\alpha_1 \oplus \xi, \dots, \alpha_{\mu} \oplus \xi\}$$. Очевидно, что в $$a_{\xi}$$ все элементы попарно различны т. е. $$w(a_{\xi})=\mu$$. Элемент $$\xi \notin X$$ поскольку среди элементов $$A_{\xi}$$ существует по крайней мере один такой элемент $$a_i \oplus \xi \notin b$$ ибо $$w(b)< \mu$$. Из произвольности элемента $$\xi$$ следует, что в $$X$$ нет ни одного элемента $$GF(p),$$ т. е. алгебраическое решение пусто.
Достаточность. Пусть $$w(a) \le w(b)$$ тогда алгебраическое решение есть $$X=[\underline b \circleddash \underline a, \bar b \circleddash \bar a], a+X=[a,a]+[ \underline b \circleddash \underline a, \bar b \circleddash \bar a]= \underline a \oplus \underline b \circleddash \underline a, \bar a \oplus \bar b \circleddash \bar a]=[ \underline b, \bar b]=b$$. При этом по свойству 11 в теореме 19.1 $$w(b)=w(a +X)=w(a)+w(X)-1$$. Отсюда следует, что $$w(b)-w(a)=w(X)-1$$ Тогда, учитывая, что $$w(a) \le w(b)$$, получим $$w(X) \ge 1$$, т. е. множество $$X$$ не пусто.
Заметим, что теорема 19.2 для случая, когда в уравнении $$A+X=B$$ вместо обычных интервалов использованы обобщенные интервалы, неверна. В самом деле, пусть $$p=7, A+[1,1] \bigcup [3,3] \bigcup [5,5], B+[6,2]$$. Перебором можно проверить, что уравнение в этом случае алгебраического решения не имеет.
Для существования алгебраического решения уравнения $$AX=B$$ условие $$w(A) \le w(B)$$ является необходимым, но не является достаточным даже для случая, когда $$A$$ и $$B$$ - обычные интервалы. Например, при $$p=7$$ уравнение $$[2,4]*X=[2,5]$$ алгебраического решения не имеет, хотя $$w(A)=3 < w(B)=4$$. В то же время это уравнение имеет объединенное множество решений $$X_{\exists \exists }=[1,6]$$ и допустимое множество решений $$X_{\forall \exists }=[1,1] \bigcup [6,6]$$.
Для уравнения
$$A+X=B$$введенные множества решений определяются следующим образом:
$$X_{\exists \exists }=Y_{\alpha \in A}Y_{\beta \in B}(\beta \circleddash \alpha)=B_A$$ $$X_{\forall \exists }=I_{\alpha \in A}Y_{\beta \in B}(\beta \circleddash \alpha)$$ $$X_{\forall \exists }=I_{\beta \in B}Y_{\alpha \in A}(\beta \circleddash \alpha)$$Для уравнения
$$AX=B$$где
$$0 \notin A$$множество решений определяются аналогично:
$$X_{\exists \exists }=Y_{\alpha \in A}Y_{\beta \in B}(\beta \oslash \alpha)=B/A$$ $$X_{\forall \exists }=I_{\alpha \in A}Y_{\beta \in B}(\beta \oslash \alpha)$$ $$X_{\forall \exists }=I_{\beta \in B}Y_{\alpha \in A}(\beta \oslash \alpha)$$Равенства (19.10)-(19.12), (19.13)-(19.15) следуют из определения множеств $$X_{\exists \exists}, X_{\forall \exists }, X_{\exists \forall}$$ и определения
Рассмотрим пример. Пусть $$p=7$$ и уравнение имеет вид
$$[2,4]*X=[2,5]$$Для наглядности построим таблицу деления $$\beta \oslash \alpha$$, где $$\beta \in [2,5], \alpha \in [2,4]$$.
| $$\alpha \ \beta$$ | 2 | 3 | 4 | 5 |
|---|---|---|---|---|
| 2 | 1 | 5 | 2 | 6 |
| 3 | 3 | 1 | 6 | 4 |
| 4 | 4 | 6 | 1 | 3 |
Объединение всех элементов строк (столбцов) таблицы составляет объединенное множество решений $$X_{\exists \exists}=[1,6]$$. Пересечение элементов строк таблицы составляет допустимое множество решений $$X_{\forall \exists }=[1,1] \bigsup [6,6]$$. Пересечение элементов столбцов таблицы пусто, поэтому $$X_{\exists \forall}= \varnothing$$ и управляемых решений уравнение не имеет.
Теорема 19.3. Все множество решений уравнений $$A+X=B$$ и $$AX=B$$ и алгебраическое решение, если оно существует, включаются в объединенное множество решений, т. е. в $$B-A$$ для уравнения $$A+X=B$$ и в $$B\A$$ для уравнения $$AX=B$$
Доказательство этой теоремы следует из равенств (19.10)-(19.12), (19.13)-(19.15) для множеств решений. Для алгебраического решения очевидно, что если оно существует, то все его элементы являются допустимыми решениями и, следовательно, принадлежат также и объединенному множеству решений.
Для получения официальных документов о завершении программы дополнительного профессионального образования (удостоверения о повышении квалификации, дипломов о профессиональной переподготовке и MBA) необходимо предоставить:
Внимание! Вы можете не заказывать доставку бумажной версии официального документы, а скачать его в электронном виде и распечатать самостоятельно. Информация о выданном документе в течение 1 месяца загружается в Федеральную информационную систему «Федеральный реестр сведений о документах об образовании и (или) о квалификации, документах об обучении» - ФИС ФРДО.
Доступ на новый сайт осуществляется с использованием адреса электронной почты, который был указан вами при регистрации на "старом". Мы постарались перенести все ваши данные с прежнего ресурса, однако не исключена вероятность потери части информации.
При возникновении проблемы со входом, воспользуйтесь функцией сброса пароля
Если вы обнаружите несоответствия, пожалуйста, сообщите нам.