Влияние ошибок округления на алгоритмы

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

Пусть — некоторая вещественная функция. Через обозначим непосредственно выбранный численный алгоритм для вычисления . Необходимо отметить, что результат содержит вычислительную погрешность. Предположим, что является обратно устойчивым алгоритмом для [53], т.е. для всякого найдется малое , такое, что:

 

.

 

Величина называется обратной ошибкой. Иначе говоря, - это точный ответ для слабо возмущенной задачи .

Для погрешности вычисленного значения , исходя из соотношения (2.8), становится возможной оценка:

 

,

 

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

При обратной устойчивости величина мала, тогда если абсолютное число обусловленности невелико, то мала будет и погрешность. Если же число обусловленности большое (или бесконечно большое), то несмотря на малое значение обратной ошибки [53] , результирующая погрешность может оказаться неприемлемо большой.

 

Программирование численных алгоритмов

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

· Простота использования,

· Надежность,

· Временные затраты.

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

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

Второй формой являются программные среды, значительно «более дружественные к пользователю» по сравнению с библиотеками типа LAPACK. Это достигается ценой утраты производительности. Эту форму представляет коммерческая система Matlab и ряд подобных ей систем. Matlab можно рассматривать как простую интерактивную программную среду, где большинство операций линейной алгебры реализованы как встроенные функции. Однако Matlab принимает ряд алгоритмических решений автоматически, не консультируясь с пользователем, поэтому получаемые этим путем программы могут работать медленнее, чем удачно выбранные библиотечные программы.

Третья форма – это шаблоны или, иначе говоря, рецепты для сборки сложных алгоритмов из более простых «строительных блоков». Шаблоны полезны в ситуации, когда алгоритм можно построить многими разными способами, но при этом отсутствует простое правило выбора наилучшей конструкции для конкретной входной задачи. Таким образом, значительная роль в конструировании оставлена пользователю. Примером подобного подхода может служить книга «Шаблоны для решения линейных систем. Строительные блоки для итерационных методов».

 

Вопросы

1. Какие алгоритмы называются численными, логическими?
2. Почему численным алгоритмом практически невозможно получить точное решение задачи?
3. Особенности машинной арифметики. С чем связаны эти особенности?
4. Как можно рассматривать приближенное решение вычислительной задачи?
5. Число обусловленности задачи. Абсолютное и относительное число обусловленности функции.
6. Вывести формулу абсолютного числа обусловленности функции одной переменной, многих переменных?
7. Какой алгоритм является обратно устойчивым?
8. Чем, как правило, руководствуются при машинной реализации численных алгоритмов или выборе готовой программы?

 

Литература

1. Дж. Макконнелл. Основы современных алгоритмов. 2-е дополненное издание. – М.: Техносфера, 2004. – 368 с.

2. Кобозєва А.А., Мачалін І.О., Хорошко В.О. Аналіз захищеності інформаційних систем. - К.: Вид. ДУІКТ, 2010. – 316 с.

3. Кобозева А.А., Хорошко В.А. Анализ информационной безопасности. - К.: Изд.ГУИКТ, 2009. – 251 с.

4. Деммель Дж. Вычислительная линейная алгебра / Дж.Деммель; пер.с англ. Х.Д.Икрамова. — М.: Мир, 2001. — 430 с.

5. Бахвалов Н.С. Численные методы / Н.С.Бахвалов, Н.П.Жидков, Г.М.Кобельков. — М.: БИНОМ. Лаборатория знаний, 2006. — 636 с.

6. Каханер Д. Численные методы и программное обеспечение / Д.Каханер, К.Моулер, С.Нэш; пер. с англ. Х.Д.Икрамова. — М.: Мир, 2001. — 575 с.

7. E.Anderson, Z.Bai, C.Bischof, J.Demmel, J.Dongarra, J.Du Croz, A.Greenbaum, S.Hammarling, A.McKenney, S.Ostrouchov, and D.Sorensen. LAPACK Users’ Guide (2^nd edition). SIAM, Philadelphia,PA, 1995.