Ващенко Г.В., Добронец Б.С. Надежность информационных систем. Лабораторный практикум

Подождите немного. Документ загружается.

спроектирована. Эта идея на первый взгляд кажется экономичной, но обычно

дело обстоит совсем наоборот. Большинство опытных проектировщиков при-

знает, что проектирование программы — процесс итеративный. Редко пер-

вый проект оказывается совершенным. Нормальный стиль проектирования

структуры программы предполагает по окончании проектирования нижних

уровней вернуться назад и подправить верхний уровень, внеся в него неко-

торые усовершенствования или исправляя ошибки, либо иногда даже выбро-

сить проект и начать все сначала, потому что разработчик внезапно увидел

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

и оттестирована, то возникает серьезное сопротивление любым улучшени-

ям ее структуры. В конечном итоге за счет таких улучшений обычно можно

сэкономить больше, чем те несколько дней или недель, которые рассчитывает

выиграть проектировщик, приступая к программированию слишком рано.

Задания

Проведите нисходящее тестирование для следующего ПО.

1. Решение квадратного уравнения.

2. Площадь треугольника.

3. Интерполяционный полином Лагранжа.

4. Сортировка списка.

5. Интегрирование функции.

6. Редактор строки.

7. Сумма ряда.

Лабораторная работа № 8.

Надежные вычисления

Цель работы: Закрепление знаний по теме “Контроль и диагностика ИС”.

В результате выполнения работы, студенты учатся разрабатывать вы-

числительные алгоритмы с заданной точностью вычислений.

Самостоятельная работа студента под контролем преподавателя. Сту-

денты для решения вычислительных задач пишут программы на одном из

языков высокого уровня или используют пакеты прикладных программ для

математических и научных расчетов.

При выполнении данной работы используются следующие методы повы-

шения точности расчетов и методы вычислительной математики, позволяю-

щие получать результаты с заданной точностью: учет ошибок округления;

специальные алгоритмы для учета ошибок округления; оценки погрешности

вычислительных алгоритмов; оценки погрешности интегрирования систем

дифференциальных уравнений; использование правил Рунге; использование

интервальной математики; построение множеств решений систем линейных

алгебраических уравнений.

Форма отчетности: Решенные задачи и программы.

Правило Рунге

Одно из первых правил для практической оценки погрешности дискре-

тизации, позволяющее примерно оценить влияние этой погрешности, в начале

прошлого века предложил К.Д. Рунге. Это правило интенсивно использова-

лось сначала в области квадратур, а затем в разностных методах и методе

конечных элементов. Оно основано на разложении приближенного решения

в виде суммы

= u + h

v + O(h

k+m

), (1)

где u — искомое точное решение, v — неизвестная функция, а h — малый

параметр дискретизации, чаще всего шаг разностной сетки. Целое k харак-

теризует порядок точности приближенного решения, а m > 0 — малость оста-

точного члена в сравнении с главным членом погрешности h

v. Поскольку u

и v не зависят от h, для параметра h/2 справедливо разложение

h/2

= u +

v + O(h

k+m

Вычтем его из (1), избавляясь от u:

− u

h/2

= v

− 1) + O(h

k+m

Отсюда можно определить главный член погрешности:

h/2

− u ≈

− u

h/2

− 1

. (2)

Поскольку в формуле (2) отброшен остаточный член порядка O(h

), она не

приводит к гарантированной оценке, но при достаточно малых h действи-

тельно дает представление о величине погрешности численного решения.

Интервальные числа

Под интервальным числом a мы будем понимать вещественный отре-

зок [a, a], где a ≤ a. Множество интервальных чисел мы будем обозначать

через R. При a = a = a интервальное число будем отождествлять с веще-

ственным числом a, следовательно R ⊂ R. В дальнейшем мы будем называть

интервальные числа просто интервалами. Шириной a — это величина

wid(a) = a − a,

середина — полусумма

med(a) = (a + a)/2.

Если S — непустое ограниченное множество в R

, то его интервальной

оболочкой 2S определим наименьший по включению интервальный вектор,

содержащий S.

Арифметические операции над интервальными числами введем следую-

щим образом. Пусть a, b ∈ R, тогда положим

a ∗ b = {x ∗ y|x ∈ a, y ∈ b},

где знак (∗) — одна из операций +, −, ·, /. При делении интервал b = [b, b]

не должен содержать ноль. Введенные выше операции эквивалентны следу-

ющим:

a + b = [a, a] + [b, b] = [a + b, a + b],

a − b = [a, a] − [b, b] = [a − b, a − b],

a · b = [a, a] · [b, b] = [min(ab, ab, ab, ab), max(ab, ab, ab, ab)],

a/b = [a, a]/[b, b] = [a, a] · [1/b, 1/b], 0 /∈ [b, b].

Если a и b вырождаются в вещественные числа, то эти равенства сов-

падают с обычными арифметическими операциями. Интервальные операции

сложения и умножения остаются коммутативными и ассоциативными, т.е.

a,b,c ∈ R

a + b = b + a, a + (b + c) = (a + b) + c,

a · b = b · a, a · (b · c) = (a · b ) · c.

Если r(x) — непрерывная унарная операция на R, то

r(X) = [min

x∈X

r(x), max

x∈X

r(x)]

определяет соответствующую ей операцию на R. Примерами таких унарных

операций могут служить

exp(X), ln(X), sin(X), . . .

Теперь укажем отличия интервальной арифметики от обычной. Вместо дис-

трибутивности умножения относительно сложения для a, b, c ∈ R, т.е. a(b +

c) = ab + ac, выполняется субдистрибутивность

a(b + c) ⊂ ab + ac.

Заметим, что R не является полем: элементы R не имеют обратных элемен-

тов относительно сложения и умножения. В частности, a - a 6= 0 и a/a 6= 1.

Вместо этого действуют два других правила сокращения:

1. Из a + b = a + c следует b = c;

2. Из ab = ac и 0 /∈ a

следует b = c.

Интервальные арифметические операции обладают свойством монотон-

ности по включению: из условий a ⊂ c, b ⊂ d следуют включения

a + b ⊂ c + d, a − b ⊂ c − d,

ab ⊂ cd, a/b ⊂ c/d 0 /∈ d.

Унарные операции обладают сходными свойствами:

X ⊆ Y ⇒ r(X) ⊆ r(X),

x ∈ Y ⇒ r(x) ∈ r(X).

Мы расширим отношения порядка ∗ ∈ {<, ≤, >, ≥} на интервальные

переменные:

x ∗ y ⇔ ˜x ∗ ˜y для всех ˜x ∈ x, ˜y ∈ y.

Расстояние ρ между двумя интервалами a, b определяется следующим об-

разом

ρ(a, b) = max{|a − b|, |a − b|}.

Для вырожденных интервалов введенное расстояние сводится к обычному

расстоянию между вещественными числами:

ρ(a, b) = |a − b|.

Рассмотренная выше метрика на R является частным случаем хаусдорфовой.

Если U и V — непустые компактные множества вещественных чисел, то

хаусдорфово расстояние определяется как

ρ(U, V ) = max{sup

v∈V

inf

u∈U

ρ(u, v), sup

u∈U

inf

v∈V

ρ(u, v)}.

Вводя на множестве метрику, мы делаем его топологическим пространством.

При этом понятия сходимости и непрерывности могут быть использованы

обычным образом. Последовательности интервалов сходятся, если сходят-

ся последовательности границ интервалов. Метрическое пространство R с

метрикой ρ является замкнутым метрическим пространством, и введенные

арифметические операции непрерывны.

Интервальные расширения

В этом разделе мы будем рассматривать непрерывные вещественные

функции. Примем при этом, что все функции, с которыми мы будем иметь

дело, можно вычислить используя конечное число арифметических опера-

ций и операндов. Такие функции мы в дальнейшем будем называть рацио-

нальными. Одна и та же рациональная функция f может иметь несколько

аналитических представлений.

Интервально-значная функция f называется монотонной по включе-

нию, если для векторов a, b ∈ R

из соотношения a ⊂ b вытекает, что

f(a) ⊂ f(b).

Заметим, что согласно методу математической индукции из монотонности

по включению для интервальных операций это свойство справедливо для

любого рационального выражения f (x), содержащего переменные x

, ..., x

и интервальные константы c

, ..., c

Пусть f(x) — вещественная функция, непрерывная в области a ⊂ R

Объединенным расширением этой функции мы будем называть интервальную

функцию f

(x) переменных x = (x

, ..., x

) ⊂ a, задаваемую равенством

(x) =

[

x∈x

f(x). (3)

Непрерывность функции f является гарантией того, что при каждом x пра-

вая часть в (3) будет конечным отрезком.

Как видно из (3), объединенное расширение монотонно по включению.

Кроме того оно минимально из всех возможных интервальных расширений.

Назовем интервальным расширением вещественной функции f(x), x ∈

D ⊂ R

, интервальную функцию f, x ∈ R

такую, что

f(x) = f(x), ∀x ∈ D.

Тогда для любого монотонного по включению интервального расширения f

имеет место включение

(x) ⊂ f(x), x ⊂ D.

Рассмотрим вещественную рациональную функцию f(x), x ∈ R

. Для

нее интервальное расширение можно получить естественным путем, если за-

менить аргументы x

и арифметические операции соответственно интерваль-

ными числами и операциями. Как уже говорилось, полученное таким образом

естественное расширение f

(x) будет монотонно по включению. Поэтому

(x) ⊂ f

(x)

для любых x ∈ R

, для которых определена правая часть.

Отметим, что естественное интервальное расширение существенно зави-

сит от способа записи рационального выражения.

Существуют способы представления рациональных выражений когда есте-

ственное интервальное расширение совпадает с объединенным.

Теорема 1. Пусть f(x

, .., x

) — рациональное выражение, в котором

каждая переменная встречается не более одного раза и только в первой

степени, f

, ..., x

) — его естественное расширение. Тогда

, ..., x

) = f

, ..., x

)

для любого набора (x

, ..., x

), такого, что f

, ..., x

) имеет смысл.

В случае, когда не удается достигнуть ситуации, когда каждая пере-

менная встречается только один раз, по крайней мере надо стремиться к

уменьшению числа вхождений каждой переменной. Это обычно приводит к

уменьшению ширины интервального расширения.

Суперпозиции рациональных и элементарных функций охватывают по-

давляющую часть нужных нам применений. Мы будем называть естествен-

ным интервальным расширением таких выражений интервальные функции,

в которых вещественные аргументы заменены интервальными числами, а ве-

щественные арифметические операции — интервальными операциями.

Пусть F — множество вещественных функций, для которых мы можем

строить объединенные интервальные расширения. В это множество мы вклю-

чим все элементарные функции {sin, cos, ln, exp, . . .}, их рациональные ком-

бинации и суперпозиции.

Рассмотрим обобщение теоремы 1. Для f ∈ F предположим, что мы

можем представить f(x

, . . . , x

) как рациональное выражение от некоторых

функций g

, . . . , x

Пусть функции g

обладают следующими свойствами:

1) для каждой функции g

построено объединенное расширение;

2) наборы переменных для разных функций g

попарно не пересекаются.

Тогда, сделав замену переменных z

= g

, . . . , x

), мы попадаем в об-

ласть действия теоремы 1 и можем построить для f объединенное расшире-

ние.

Пример 1. Рассмотрим функцию двух переменных f(x, y) = xy+x+y+

1. Естественное интервальное расширение этой функции не будет совпадать

с объединенным, поскольку переменные x, y встречаются более одного раза.

В качестве функций g

можно взять g

(x) = x + 1, g

(y) = y + 1. Тогда

f(x, y) = g

(x)g

(y) и, соответственно, f(x, y) = g

(x)g

(y).

Заметим, что представление функции f со свойствами 1), 2) в большин-

стве случаев невозможно. Однако мы будем стремиться выполнить эти свой-

ства как можно полнее. Естественно предположить, что таких представлений

будет несколько. Обозначим через f

различные интервальные расширения,

порожденные этими представлениями. Тогда в качестве наилучшего из воз-

можных интервальных расширений мы можем взять

f(x

, . . . , x

) = ∩

, . . . , x

Этот простой прием на практике позволяет существенно снижать ширину

интервальных расширений.

Заметим, что естественные интервальные расширения, как правило, име-

ют значительно более широкие интервалы в сравнении с объединенными рас-

ширениями. Рассмотрим прием уменьшения ширины интервальных вычисле-

ний. Идею поясним на примере функций одной переменной.

Пусть f: a → R непрерывная функция, а f

(x) — ее естественное ин-

тервальное расширение. Разобьем a на p интервалов равной длины

a =

[

i=1

, wid(a

) = wid(a)/p.

Тогда интервал b =

i=1

) по-прежнему будет содержать объединен-

ное расширение f

(a), но, как правило, будет иметь меньшую ширину, чем

(a) ⊂ b ⊂ f

(a). (4)

Более того, при p → ∞

wid(b) − wid(f

(a)) = O(1/p). (5)

В принципе этот прием можно распространить и на большие размерно-

сти, в том числе останутся справедливыми свойства (4) и (5). Но для n пе-

ременных вектор (a

, ..., a

) будет подразделяться уже на p

равных частей.

Поэтому при практических вычислениях этот прием используется только для

небольших размерностей.

Если известны интервальные расширения первых производных, то мож-

но построить интервальные расширения следующим образом.

Пусть, например, f: R

→ R непрерывно дифференцируемая функция

на a ∈ R

и g

— интервальные расширения первых производных g

∂f/∂x

. Пусть c = med(x), где x ∈ R

. Тогда для всех x ∈ x

f(x) = f(c) +

j=1

(ξ)(x

− c

), ξ ∈ x.

Заменяя производные их интервальными расширениями, получим соотноше-

ние

f(x) ⊂ f(c) +

j=1

(x)(x

− c

его правая часть определяет интервальную функцию

(x) = f(c) +

j=1

(x)(x

− c

которая обычно называется mv-формой (mean value form). Справедлив сле-

дующий результат.

Теорема 2. Пусть производные g

для всех j = 1, ..., n удовлетворяют

условию Липшица на a, и при wid(x) → 0

wid(g

(x) − wid(g

j,un

(x)) = O(wid(x)) ∀j = 1, ..., n ∀x ⊂ a. (6)

Тогда

wid(f

(x) − wid(f

(x)) = O(wid

(x)) ∀x ⊂ a. (7)

Если вместо (6) справедлива более грубая оценка

wid(g

(x)) ≤ c ∀j = 1, ..., n, ∀x ⊂ a, (8)

то вместо (7) выполняется соотношение

wid(f

(x) − wid(f

(x)) = O(wid(x)) ∀x ⊂ a.

Таким образом, имея интервальные расширения производных, можно

получать mv-форму функции, обладающей большей асимптотической точ-

ностью, чем исходные расширения производных.

Ниже мы рассмотрим подход, позволяющий строить близкие к оптималь-

ным интервальные расширения для некоторых классов функций.

Интервальные расширения полиномов многих переменных

В этом разделе изложен алгоритм нахождения интервальных расшире-

ний полиномов многих переменных.

Пусть f(x), x ∈ R

— вещественная рациональная функция. Для нее ин-

тервальное расширение можно получить естественным путем, если заменить

переменные x

и арифметические операции — интервальными переменными

и операциями. Полученное таким образом интервальное расширение будет

монотонным по включению.

Рассмотрим метод нахождения интервальных расширений для функций

вида

f(x) =

i,j=0

где x

= 1 и a

∈ a

, x

∈ x

. Далее обозначим x = (x

, x

, . . . , x

). Необходи-

мость нахождения оптимальных расширений для полиномиальных функций

возникает в различных приложениях, например, при решении систем нели-

нейных уравнений методом простой итерации, при нахождении двусторон-

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

указанный вид. Наиболее часто такие задачи встречаются в химической ки-

нетике.

Заметим, что построение интервального расширения f можно свести к

нахождению min

f, max

f и представления

f = [min

f, max

f].

Найдем max

f. Основная идея метода заключается в том, чтобы попытаться

найти переменные x

, для которых

0 6∈ ∂

f(x). (9)

Тогда, в зависимости от знака ∂

f(x), значение max

f будет достигаться

для граничных значений x

. В силу приведенной выше теоремы , естественное

интервальное расширение для f будет совпадать с объединенным.

Пусть I: {i|wid(x

) 6= 0} — множество индексов, таких, что i ∈ I ⇒

wid(x

) 6= 0. Циклично проверяем переменные x

, i ∈ I. Для тех переменных

, по которым удалось установить условия (9), производим замену x

на x

или x

в соответствии со знаком ∂

f(x) и исключаем их индекс из I. Цикл

продолжается до тех пор, пока условие (9) выполняется хотя бы один раз

на множестве I и идет сужение интервалов. Тем самым мы окончательно

формируем x

∗

⊆ x.

Выберем переменные x

, по которым выполнены два условия:

а) f не содержит квадрат данной переменной;

б) x

∗

– имеет ненулевую ширину.

Преобразуем функцию f. При переменной такого вида можно привести

подобные члены так, чтобы она встречалась не более одного раза и только

в первой степени. Тогда она не будет давать вклада в ошибку при вычисле-

нии интервального расширения на интервале x

∗

. Может оказаться, что при

всех выделенных таким образом переменных одновременно привести подоб-

ные члены не удается. Тогда приводим подобные члены при тех переменных,

при которых это возможно сделать одновременно, и получаем функцию

Далее вычислим

f – оценку максимума функции

f на x

∗

. Эту оцен-

ку удобно сделать с помощью метода Волкова, так как в нем используются

оценки с помощью парабол по каждой переменной. В нашем случае парабо-

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

о вторых производных, которые для рассматриваемой функции f являются

фиксированными интервалами.

Зададимся точностью ε, нахождения максимума функции

f. Пусть f

–

значение функции

f в середине интервала x

∗

. Если

−

f| < ε,

то счет окончен. В противном случае мы можем воспользоваться алгоритмом

деления большей стороны интервала пополам или небольшой его модерниза-

цией: деление на три части, т.е. представление x

∗

= x

∪ x

. Далее для

каждого x

проделываем описанные выше процедуры и определяем, в каком

находится точка максимума функции. Алгоритм заканчивает свою работу

в одном из следующих случаев:

1) множество I пусто;

2) ширина большей грани x

∗

меньше ε —

max

i∈I

wid(x

∗

) < ε.

f содержит каждую переменную x

, i ∈ I только один раз и только в

первой степени.

Рассмотрим несколько примеров.

Пример 2. Пусть дана функция f = 2x

− 2xy + y + 2x. Требуется

найти ее интервальное расширение на интервале x = [0, 1] × [0, 1]. Найдем

естественные интервальные расширения производных f

= [0, 6], f

= [−1, 1].

Таким образом, для переменной x

на интервале x есть монотонность. Сле-

довательно, x

∗

= 1 ×[0, 1]. Вычисляя f

, получаем f

= −1. Новый интервал

∗

= 1 × 0 имеет нулевую ширину, точка (1, 0) — точка максимума функции

f. Аналогично находится точка минимума. Таким образом, f(x) = [0, 4].