Введение
1. Алгоритмы и программное обеспечение безошибочных дробно рациональных операций 15
1.1. Целочисленные вычисления 17
1.1.1. Сложение неотрицательных чисел . 18
1.1.2. Вычитание неотрицательных чисел 20
1.1.3. Сложение и вычитание целых чисел 20
1.1.4. Умножение целых чисел 22
1.1.5. Деление и остаток от деления целых чисел 25
1.1.6. Наибольший общий делитель 28
1.1.7. Класс overlong 32
1.1.8. Выводы и результаты 35
1.2. Дробно-рациональные вычисления 35
1.2.1. Оценка вычислительной и пространственной сложностей арифметических операций с рациональными числами 35
1.2.2. Класс rational 39
1.2.3. Арифметические операции с дробно-рациональными числами..41
1.2.4. Выводы и результаты 45
1.3. Матричные вычисления 46
1.3.1. Оценка вычислительной и пространственной сложностей арифметических операций с матрицами 46
1.4. Выводы 49
2. Применение безошибочных вычислений для решения линейных систем 50
2.1. Определение гарантированной оценки погрешностирешения систем линейных алгебраических уравнений, при приближенных исходных данных 52
2.2. Использование метода Жордана-Гаусса 54
2.2.1. Использование алгоритма Жордана-Гаусса для нахождения гарантированных оценок решения приближенно заданной системы линейных алгебраических уравнений 55
2.2.2. Оценка сложности определения гарантированной оценки решения приближенно заданной системы линейных алгебраических уравнений методом Жордана-Гаусса 56
2.3. Безошибочное решение систем с трехдиагональными матрицам 61
2.3.1. Метод прогонки 62
2.3.2. Оценка сложности безошибочного решения систем линейных алгебраических уравнений с трехдиагональной матрицей методом прогонки 63
2.4. Недоопределенные и переопределенные системы. Обобщенная обратная матрица 69
2.4.1. Обобщенная обратная матрица 69
2.4.2. Приложение -обратных матриц для решения систем линейных уравнений 70
2.4.3. Свойства -обратных матриц 71
2.4.4. Метод Гревилла 73
2.4.5. Оценка сложности нахождения обобщенной обратной матрицы методом Гревилла 74
2.4.6. Метод Эрмита 76
2.4.7. Оценка сложности нахождения обобщенной обратной матрицы методом Эрмита 78
2.5. Практические эксперименты 81
2.5.1. Эксперимент 1 81
2.5.2. Эксперимент 2. 81
2.6. Выводы 83
3. Программное обеспечение параллельных вычислений при решении линейных систем 85
3.1. Адаптация классов overlong и rational к MPI 86
3.2. Метод Жордана-Гаусса 90
3.2:1. Параллельный алгоритм 91
3.2.2. Ускорение параллельной реализации алгоритма Жордана-Еаусса при использовании параллельный вычислений. 94
3.2.3; Вычислительный эксперимент 95
3.3. Обобщенная обратная матрица. 98
3.3.1. Параллельный алгоритм 99
3.3.2. Коэффициент ускорения параллельной реализации алгоритма Эрмита 101
3.3.3. Вычислительный эксперимент ...103
3.4. Интернет приложения для решения линейных систем. ...103
3.5. Выводы 104
Заключение 105
Литература 107
Приложение 115
