Спецкурс: Hадеждни Изчисления

Хорариум: 30 часа лекции, 30 часа практикум (2+0+2), 4 кредита, зимен семестър

Разписание за зимен семестър 2011/2012:
Лекции/Упражнения: сряда, 17:00-20:00, зала 278 на ИМИ, блок 8 на БАН (4-ти км).

Лектори: ст.н.с. д-р Е. Попова, ст.н.с. дмн С. Марков - ИМИ, БАН,  тел.: 979-3823, e-mail: <>

Анотация:

Надеждни изчисления е съвременна интердисциплинарна област (обединяваща информатика и изчислителна математика), която се занимава с различни аспекти на числови пресмятания основани на крайно представяне на математическите обекти и осигуряващи гарантирана точност на резултатите, както и с методи и софтуерни средства за моделиране в условия на неточни (интервални) данни.

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

Курсът е предназначен за студенти от магистърските програми на специалностите информатика и приложна математика на ФМИ; може да бъде посещаван и от студенти по физика, химия и инженерни специалности. От студентите се изисква наличие на начални познания по алгебра и числени методи.

Курсът е необходима основа за разработване на дипломна работа по изчислителна информатика, продължаване на образованието в международни PhD програми, и участие в Българо-Немски/Френски проекти.

Програма:

  1.  Необходимост от надеждни изчисления - еволюция на аритметичните устройства, софтуера и числените методи.
  2. Математически формализъм на компютърната аритметика в скаларни пространства. Алгоритми за реализация на аритметичните операции с максимална точност.
  3. IEEE стандарт за аритметика с плаваща точка - цели, предмет, формати, режими на закръгляване.
  4. Възникване и обработка на изключителни ситуации съгласно IEEE Std. 854.
  5. Канцелиращ ефект. Извършване на векторни и матрични операции с максимална точност. Пресмятане на точно скаларно произведение в дълъг акумулатор.
  6. Интервална аритметика - основни свойства. Компютърна интервална аритметика.
  7. Интерполация и апроксимация при неточни данни.
  8. Интервални функции - интервална обвивка, интервални разширения. Непрекъснатост на интервални функции.
  9. Линейни и квадратични разширения на интервални функции. Методи за пресмятане на интервална обвивка.
  10. Локализиране нулите на функция на една реална променлива в даден интервал. Изолиране на нулите чрез подразделяне на интервала. Интервален Нютонов метод.
  11. Многомерен интервален Нютонов метод. Метод на Кравчик за решаване на система нелинейни уравнения. Компютърна реализация.
  12. Теорема за неподвижната точка. Основни принципи при разработване на алгоритми с автоматична верификация на резултата. Метод на Румп за гарантирано включване решението на точкова линейна система.
  13. Интервални линейни системи. Намиране на точната обвивка за множеството от решения. Метод на J. Rohn.
  14. Метод на Румп за намиране на интервално включване за множеството от решения на интервална линейна система.
  15. Софтуер за надеждни изчисления.

Литература:

  1. Д. Алнолд: Нещастни случаи дължащи се на грешки при числови пресмятания. (http://www.ima.umn.edu/~arnold/disasters/)
  2. M. Heath: SCIENTIFIC COMPUTING: An Introductory Survey, Second Edition, McGraw-Hill, New York, 2002. http://www.cse.uiuc.edu/heath/scicomp/
  3. Е. Попова: Компютърна аритметика - лекционен материал.
  4. IEEE стандарт за аритметика с плаваща точка.
  5. Упражнение/Домашно No. 1.
  6. E. Popova: Упражнения върху IEEE стандарт за аритметика с плаваща точка.
  7. Пресмятане на точно скаларно произведение в дълъг акумулатор. (PDF файл)
  8. Caprani, O.; Madsen, K.; Nielsen, H.: Introduction to Interval Analysis. http://www2.imm.dtu.dk/pubdb/views/edoc_download.php/1462/pdf/imm1462.pdf
  9. Е. Попова: Надеждни изчисления - лекционен материал.
  10. Упражнение: Използване на насочени закръглявания.
  11. E. Popova: Упражнения върху пресмятане на обхвати на функции.
  12. Метод на J. Rohn за намиране на точната обвивка за множеството от решения на интервална линейна система. (допълнителен материал)
  13. Neumaier, A.: Interval Methods for Systems of Equations, Cambridge Univ. Press, 1990.
  14. Hammer, R.; Hocks, M.; Kulisch, U.; Ratz, D.: C++ Toolbox for Verified Computing : Basic Numerical Problems. Springer - Verlag , Berlin / Heidelberg / New York, 1995.