КАТЕГОРИИ: Архитектура-(3434)Астрономия-(809)Биология-(7483)Биотехнологии-(1457)Военное дело-(14632)Высокие технологии-(1363)География-(913)Геология-(1438)Государство-(451)Демография-(1065)Дом-(47672)Журналистика и СМИ-(912)Изобретательство-(14524)Иностранные языки-(4268)Информатика-(17799)Искусство-(1338)История-(13644)Компьютеры-(11121)Косметика-(55)Кулинария-(373)Культура-(8427)Лингвистика-(374)Литература-(1642)Маркетинг-(23702)Математика-(16968)Машиностроение-(1700)Медицина-(12668)Менеджмент-(24684)Механика-(15423)Науковедение-(506)Образование-(11852)Охрана труда-(3308)Педагогика-(5571)Полиграфия-(1312)Политика-(7869)Право-(5454)Приборостроение-(1369)Программирование-(2801)Производство-(97182)Промышленность-(8706)Психология-(18388)Религия-(3217)Связь-(10668)Сельское хозяйство-(299)Социология-(6455)Спорт-(42831)Строительство-(4793)Торговля-(5050)Транспорт-(2929)Туризм-(1568)Физика-(3942)Философия-(17015)Финансы-(26596)Химия-(22929)Экология-(12095)Экономика-(9961)Электроника-(8441)Электротехника-(4623)Энергетика-(12629)Юриспруденция-(1492)Ядерная техника-(1748) |
Устойчивость и неустойчивость алгоритмов
Поскольку в системе чисел с плавающей точкой нарушаются основные законы арифметики, то при реализации алгоритмов на ЭВМ большую роль играет порядок организации вычислений, а именно: результат вычислений может сильно зависеть от порядка. Алгоритм, в котором погрешность, допущенная в начальных данных или допускаемая при вычислениях, с каждым шагом не увеличивается или увеличивается незначительно, называется устойчивым. В противном случае, если погрешность существенно увеличивается от шага к шагу, алгоритм называется неустойчивым. Чаще всего неустойчивость алгоритма связана с итерационными процессами, когда результат получается посредством последовательности итераций, причем на каждой итерации в качестве исходных данных используются значения, полученные на предыдущей итерации. Существуют неустойчивые алгоритмы, не связанные с итерационными процессами. Пример. Известно, что ряд Тейлора для функции
сходится для всех . Рассмотрим один из возможных алгоритмов суммирования этого ряда:
Шаг 1. Задать . ; . Шаг 2. Шаг 3. Если = , то вычисления закончены, результат - иначе =, , переход на шаг 2.
Проверка на шаге 3 учитывает то обстоятельство, что машинная арифметика является приближенной. Выражение будет иметь то же значение, что и , если число достаточно мало. Если провести вычисления по этому алгоритму для различных значений , получим числа, представленные в табл.1. Для эти числа соответствуют истинным значениям, но для картина неудовлетворительная: в некоторых случаях неверны даже знаки результатов. Это говорит о неустойчивости рассмотренного алгоритма. Таблица1 –
Пример. Необходимо вычислить При вычислении интеграла по частям получим:
,
т.е. . (10) Предположим, что вычисления проводятся в системе чисел с плавающей точкой, для которой :
Поскольку для любого при : , то истинное значение . Что привело к ошибке? Единственная ошибка округления, сделанная в приведенных выше вычислениях, - это ошибка в , когда округляется до шести значащих цифр. Последующие значения получены округлением результатов, вычисленных точно по содержащему ошибку округления значению . Формула (10) точна для действительной арифметики, следовательно явная ошибка в всецело обязана ошибке округления в . Ошибка в - , ,
т.е. ошибка в ― . Аналогично, ошибка в ― и т.д. Ошибка в ― . Истинное значение . Таким образом, возникающая вследствие неустойчивости алгоритма ошибка – абсолютная погрешность – при вычислении значительно больше искомого значения , что не даст возможности получить ни одного верного знака в записи числа , что и наблюдается при вычислении по абсолютно точной с точки зрения обычной арифметики формуле (10). Преобразуем формулу (10) эквивалентным образом:
. (20)
Теперь на каждом шаге вычислений ошибка в умножается на множитель . Таким образом, если начать вычисления с некоторого для и проводить вычисления в обратном порядке, то любая начальная ошибка или промежуточные ошибки округлений будут уменьшаться на каждом шаге, что говорит об устойчивости алгоритма, отвечающего (20). Оценим значения в общем виде. Поскольку при : , то на сегменте : , а значит: , (25)
а это значит, что .
Таким образом, если в качестве стартового значения для вычислений в соответствии с формулой (20) взять, например, , значение которого положить равным нулю
, (30)
то начальная ошибка, допущенная при этом в (30), не превосходит в соответствии с (25) . Эта ошибка умножится на при вычислении , так что ошибка в - . Вычисления, проведенные по ормуле (20), приведут к следующему результату:
,
что говорит об устойчивости алгоритма (20).
Дата добавления: 2014-01-11; Просмотров: 991; Нарушение авторских прав?; Мы поможем в написании вашей работы! Нам важно ваше мнение! Был ли полезен опубликованный материал? Да | Нет |