1611688890-f641c9ec8276824e4686da772eb56520 (826652), страница 7
Текст из файла (страница 7)
Взаимная полиномиальная сводимость двух задач друг другуявляется отношением эквивалентности.Этим рассуждениям можно придать более строгую форму, что приводит к так называемой теории NP-трудности, получившей существенное развитие в последние десятилетия. Её основным понятием являетсяпонятие NP-трудной задачи (универсальной переборной задачи) [10]Таким образом, теория NP-полноты не отвечает напрямую на вопрос о трудоёмкости решения тех или иных задач, но позволяет утверждать, что некоторые задачи «столь же трудны», как и другие известные задачи. Нередко знание уже этого одного факта бывает существенным для ориентировки создателям вычислительных технологийрешения конкретных задач.
Если известно, к примеру, что некотораязадача не проще, чем известные «переборные» задачи, которые, повидимому, не могут быть решены лучше, чем полным перебором всехвозможных вариантов, то имеет смысл и для рассматриваемой задачине стесняться конструирования алгоритмов «переборного» типа, имеющих экспоненциальную трудоёмкость.Именно такова ситуация с некоторыми задачами, которые возникают в вычислительной математике.
К примеру, оценивание разброса решений систем линейных или нелинейных уравнений при варьированиипараметров этих систем в самом общем случае, когда мы не ограничиваем себя величиной возмущений, является NP-трудной задачей. Вчастности, таковы интервальные системы уравнений.1.9Доказательные вычисления на ЭВМТермин «доказательные вычисления» был введён в 70-е годы XXвека советским математиком К.И. Бабенко для обозначения вычислений, результат которых имеет такой же статус достоверности, как и результаты «чистой математики», полученные с помощью традиционныхдоказательств. В книге [3], где доказательным вычислениям посвящёнотдельный параграф, можно прочитать: «Под доказательными вычислениями в анализе мы понимаем такие целенаправленные вычисленияна ЭВМ, комбинируемые с аналитическими исследованиями, которыеприводят к строгому установлению новых фактов (теорем)».
В отношении задач, где ответом являются числа (набор чисел, вектор или391.9. Доказательные вычисления на ЭВМматрица и т.п.) доказательность означает свойство гарантированностиэтих числовых ответов.6 К примеру, если мы находим число π, то доказательным ответом может быть установление гарантированного неравенства π > 3.1415926 или π ≥ 3.1415926.Основная трудность, с которой сталкиваются при проведении доказательных вычислений на современных цифровых ЭВМ, вытекает изневозможности адекватно отобразить непрерывную числовую ось R ввиде множества машинно представимых чисел. Таковых может бытьлишь конечное число (либо потенциально счётное), тогда как вещественная ось R является непрерывным континуумом.
Как следствие,типичное вещественное число не представимо точно в цифровой ЭВМс конечной разрядной сеткой.R✲xРис. 1.5. Типичное вещественное число не представимо точнов цифровой ЭВМ с конечной разрядной сеткойСитуация, в действительности, ещё более серьёзна, так как неизбежными ошибками, как правило, сопровождаются ввод данных в ЭВМ ивыполнение с ними арифметических операций. Хотя эти ошибки могут быть очень малы, но, накапливаясь, они способны существенно исказить ответ к решаемой задаче.
Встаёт нетривиальная проблема ихучёта в процессе счёта на ЭВМ . . .R✲Xx∈XРис. 1.6. Интервальное решение проблемы представлениявещественных чисел в цифровой ЭВМОдним из средств доказательных вычислений на ЭВМ служит интервальная арифметика и, более общо, методы интервального анализа.В частности, вещественное число x в общем случае наиболее корректно6 Термин «доказательные вычисления на ЭВМ» является хорошим русским эквивалентом таких распространённых английских оборотов как verified computation,verification numerics и др.401.
Введениепредставляется в цифровых ЭВМ интервалом, левый конец которого —наибольшее машинно-представимое число, не превосходящее x, а правый — наименьшее машинно-представимое число, не меньшее x. Далеес получающимися интервалами можно выполнять операции по правилам интервальной арифметики, рассмотренным в §1.5.Концы интервалов, получающихся при расчётах по формулам (1.11)–(1.14), также могут оказаться вещественными числами, не представимыми в ЭВМ. В этом случае для обеспечения доказательности вычислений имеет смысл несколько расширить полученный интервал до ближайшего объемлющего его интервала с машинно-представимыми концами. Подобная версия интервальной арифметики называется машинной интервальной арифметикой с направленным округлением (см.Рис. 1.7).R✲R✲+Y⇐XR✲⇐ZR✲округление (Z)Рис.
1.7. Машинная интервальная арифметикас внешним направленным округлениемСуществует несколько подходов к организации доказательных вычислений на ЭВМ, из которых наиболее известными являются пошаговый способ оценки ошибок и апостериорное оценивание.В пошаговом способе доказательных вычислений мы разбиваем алгоритм вычисления решения на «элементарные шаги», оцениваем погрешности на каждом шаге вычислений. «Элементарными шагами»здесь могут быть как отдельные арифметические и логические опера-Литература к Главе 141ции, так и целые их последовательности, слагающиеся в крупные блокиалгоритма.
При этом полная погрешность получается из погрешностейотдельных «элементарных шагов» по правилам исчисления из §1.2.Очевидный недостаток такого способа организации оценки погрешностей состоит в том, что мы неявно привязываемся к конкретному алгоритму вычисления решения. При этом качество оценок, получаемыхс помощью пошаговой парадигмы, существенно зависит от алгоритма,и «хороший» в обычном смысле алгоритм не обязательно хорош приоценивании погрешностей.При оценивании погрешностей простых «элементарных шагов» алгоритмов с помощью таких несложных средств как классическая интервальная арифметика, получаемые оценки, как правило, отличаются невысоким качеством.
Но изощрённые варианты пошагового способа оценки погрешностей могут показывать вполне удовлетворительные результаты даже для довольно сложных задач. Таковы, к примеру,вычислительные алгоритмы для решения систем линейных алгебрических уравнений, развиваемые в [30].Напротив, при апостериорном оценивании погрешности мы оцениваем погрешность окончательного результата уже после его получения.Иными словами, мы разделяем способ получения двусторонней оценкирешения и установление её доказательности. Ниже в Главе 4 мы приведём примеры конкретных алгоритмов апостериорного оценивания длядоказательного решения некоторых популярных математических задач.Литература к главе 1Основная[1] Алефельд Г., Херцбергер Ю.
Введение в интервальные вычисления. –Москва: Мир, 1987.[2] Барахнин В.Б., Шапеев В.П. Введение в численный анализ. – СанктПетербург–Москва– Краснодар: Лань, 2005.[3] Бабенко К.И. Основы численного анализа. – Москва: Наука, 1986.[4] Бауэр Ф.Л., Гооз Г. Информатика. В 2-х ч. – Москва: Мир, 1990.[5] Бахвалов Н.С., Жидков Н.П., Кобельков Г.М. Численные методы. –Москва: Бином, 2003, а также другие издания этой книги.[6] Бахвалов Н.С., Корнев А.А., Чижонков Е.В. Численные методы. Решения задач и упражнения. – Москва: Дрофа, 2008.421.
Введение[7] Березин И.С., Жидков Н.П. Методы вычислений. Т. 1–2. – Москва: Наука,1966.[8] Вержбицкий В.М. Численные методы. Части 1–2. – Москва: «Оникс 21 век»,2005.[9] Волков Е.А. Численные методы. – Москва: Наука, 1987.[10] Гэри М., Джонсон Д. Вычислительные машины и труднорешаемые задачи.– Москва: Мир, 1982.[11] Демидович Б.П., Марон А.А. Основы вычислительной математики. –Москва: Наука, 1970.[12] Калиткин Н.Н.
Численные методы. – Москва: Наука, 1978.[13] Крылов В.И., Бобков В.В., Монастырный П.И. Вычислительные методы.Т. 1–2. – Москва: Наука, 1976.[14] Кунц К.С. Численный анализ. – Киев: Техника, 1964.[15] Кунцман Ж. Численные методы. – Москва: Наука, 1979.[16] Мацокин А.М., Сорокин С.Б. Численные методы. Часть 1. Численный анализ. – Новосибирск: НГУ, 2006.[17] Меньшиков Г.Г. Локализующие вычисления. Конспект лекций. – СанктПетербург: СПбГУ, Факультет прикладной математики–процессов управления, 2003.[18] Миньков С.Л., Миньков Л.Л. Основы численных методов. – Томск: Издательство научно-технической литературы, 2005.[19] Райс Дж. Матричные вычисления и математическое обеспечение.
– Москва:Мир, 1984.[20] Самарский А.А., Гулин А.В. Численные методы. – Москва:Наука, 1989.[21] Тыртышников Е.Е. Методы численного анализа. – Москва: Академия, 2007.[22] Успенский В.А., Семёнов А.Л. Теория алгоритмов: основные открытия иприложения. – Москва: Наука, 1987.[23] Хансен Э., Уолстер Дж.У. Глобальная оптимизация с помощью методовинтервального анализа.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
