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

• Автор: Германенко, Максим Игоревич
• Шифр специальности: 05.13.18
• Научная степень: Кандидатская
• Год защиты: 2009
• Место защиты: Челябинск
• Количество страниц: 131 с. : ил.

ВВЕДЕНИЕ

1. АЛГОРИТМЫ И ПРОГРАММНОЕ ОБЕСПЕЧЕНИЕ БЕЗОШИБОЧНЫХ ДРОБНО РАЦИОНАЛЬНЫХ ОПЕРАЦИЙ.

1.1. Целочисленные вычисления.

1.1.1. Сложение неотрицательных чисел

1.1.2. Вычитание неотрицательных чисел.

1Л .3. Сложение и вычитание целых чисел

1Л.4. Умножение целых чисел

1Л.5. Деление и остаток от деления целых чисел.

1Л .6. Наибольший общий делитель.

1Л .7. Класс v

1Л .8. Выводы и результаты.

1.2. Дробнорациональные вычисления.
1.2.1. Оценка вычислительной и пространственной сложностей арифметических операций с рациональными числами
1.2.2. Класс i
1.2.3. Арифметические операции с дробнорациональными числами
1.2.4. Выводы и результаты.
. Матричные вычисления
1.3.1. Оценка вычислительной и пространственной сложностей арифметических операций с матрицами
1.4. Выводы.
2. ПРИМЕНЕНИЕ БЕЗОШИБОЧНЫХ ВЫЧИСЛЕНИЙ ДЛЯ РЕШЕНИЯ ЛИНЕЙНЫХ СИСТЕМ
2.1. Определение гарантированной оценки погрешности решении систем линейных алгебраических уравнений, при приближенных исходных данных
2.2. Использование метода ЖорданаГаусса
2.2.1. Использование алгоритма ЖорданаГаусса для нахождения гарантированных оценок решения приближенно заданной системы линейных алгебраических уравнений
2.2.2. Оценка сложности определения гарантированной оценки решения приближенно заданной системы линейных алгебраических уравнений методом ЖорданаГаусса.
2.3. Безошибочное решение систем с трехдиагональными матрицам
2.3.1. Метод прогонки.
2.3.2. Оценка сложности безошибочного решения систем линейных алгебраических уравнений с трехдиагональной матрицей методом прогонки
2.4. Недоопределенные и переопределенные системы. Обобщенная
обратная матрица.
2.4.1. Обобщенная обратная матрица.
2.4.2. Приложение обратных матриц для решения систем линейных уравнений
2.4.3. Свойства обратных матриц
2.4.4. Метод Гревилла
2.4.5. Оценка сложности нахождения обобщенной обратной матрицы методом Г ревилла
2.4.6. Метод Эрмита
2.4.7. Оценка сложности нахождения обобщенной обратной матрицы методом Эрмита.
2.5. Практические эксперименты
2.5.1. Эксперимент
2.5.2. Эксперимент 2.
2.6. Выводы.
3. ПРОГРАММНОЕ ОБЕСПЕЧЕНИЕ ПАРАЛЛЕЛЬНЫХ ВЫЧИСЛЕНИЙ ПРИ РЕШЕНИИ ЛИНЕЙНЫХ СИСТЕМ.
3.1. Адаптация классов v и i к I
3.2. Метод ЖорданаГаусса.
3.2.1. Параллельный алгоритм
3.2.2. Ускорение параллельной реализации алгоритма ЖорданаГаусса при использовании параллельный вычислений.
3.2.3. Вычислительный эксперимент
3.3. Обобщенная обратная матрпца
3.3.1. Параллельный алгоритм
3.3.2. Коэффициент ускорения параллельной реализации алгоритма Эрмита
3.3.3. Вычислительный эксперимент
3.4. Интернет приложения для решения линейных систем.
3.5. Выводы
ЗАКЛЮЧЕНИЕ.
ЛИТЕРАТУРА


СанктПетербург, январь февраль г. Международная научная конференция Параллельные вычислительные технологии ПАВТ, г. Челябинск, январь февраль г. Третья российскогерманская школа по параллельным вычислениям на высокопроизводительных системах, г. Новосибирск, августсентябрь г. Всероссийский конкурс студенческих работ в области естественных наук, г. Москва, декабрь г. Российская молодежная научная и инженерная выставка Шаг в будущее, г. Москва, МГТУ им. Н. Э. Баумана, аир ель. Российская молодежная научная и инженерная выставка Шаг в будущее, г. Москва, МГТУ им. Н. Э. Баумана, февраль г. Седьмая научная конференция молодых исследователей Шаг в будущее, г. Москва, МГТУ им. Н. Э. Баумана, февраль г. Российская молодежная научная и инженерная выставка Шаг в будущее, г. Москва, МГТУ им. Н. Э. Баумана, апрель г. Кроме того, результаты работы были представлены на ежегодных научнопрактических конференциях ЮжноУральского государственного университета. Диплом 1 степени по итогам 2 тура Всероссийского конкурса студенческих работ в области естественных наук, Саратов год. Диплом министерства промышленности, науки и технологий РФ за первый приз в номинации Абсолютное первенство лучшая работа в области естественных наук, Москва, МГТУ им. Н.Э. Баумаиа, год. Диплом комитета общественных и межрегиональных связей Правитель ства Москвы за первый приз в номинации Лучшая работа вобласти Естественных наук, МГТУ им. Н.ЭБаумана,. Основания для выполнения работы Еранд губернатора Челябинской области г. Публикации Основные результаты диссертации опубликованы в печатных работах, получены свидетельства РосАПОюб официальной регистрации, программы, для ЭВМ Класс i и Библиотека классов x i. Во введении обоснована актуальность темы диссертационной работы, проведен обзор аналогов и описаны их недостатки, сформулирована цель работы, кратко охарактеризована научная новизна, возможности научного и практического применения, отмечена связь проблемы с планами научных исследований. Кроме того, приведено краткое изложение материала работы по главам и параграфам. В первой главе произведен обзор алгоритмов основных арифметических операций для целочисленных вычислений. Описан класс v , который существенно расширяет логические возможности целочисленных вычислений диапазон представимых чисел рас
ширяется до , . Таким образом, имеется возможность представлять целые числа, имеющие более 0 ООО десятичных разрядов. Описан класс i , который дает потенциальную возможность использовать в программах пользователя безошибочное выполнение основных арифметических операций над полем рациональных чисел. По определению, тип данных iпредставляет собой пару , . Здесь птг целочисленная переменная типа v, обозначающая числитель, целочисленная переменная типа v, обозначающая знаменатель. Минимальный шаг дискретизации представляемых чисел существенно лучше, чем у стандартных типов данных и равен . Для использования классов v и i достаточно подключить заголовочный файл x. Над объектами классов определены все основные арифметические операции, бинарные отношения, операторы вводавывода. Объем памяти, требуемый для представления объекта, зависит от значения представляемого чис
ла. Найдены битовая пространственная и вычислительная сложности сложения и умножения матриц. Разработанный класс ix , предназначен для облегчения программирования, а также улучшений визуального восприятия программ, использующих матричные вычисления. В данный класс встроены методы решения систем линейных уравнений с заданной матрицей, нахождения обратной матрицы и нахождения обобщенной обратной матрицы. Добавлена возможность использования параллельных вычислений. Во второй главе рассмотрен метод определения гарантированной оценки погрешности решения систем линейных алгебраических уравнений, при приближенно заданных исходных данных ,. Для безошибочного вычисления, как обратной матрицы А так и решения х можно использовать метод ЖорданаГаусса, а при использовании разработанного класса i возможно исключить все методические погрешности.