Реферат 3
Введение 4
1. Реализация метода сопряженных градиентов на Julia 5
1.1 Конфигурационный файл 7
1.2 Главная часть программы 8
1.3 Результаты работы программы 14
2. Сравнение скорости работы программы godunovMatrix с
использованием типа BigFloat с программой использующей тип Float64 14
3. Реализация различных версий метода сопряженных градиентов 15
4. Сравнение скорости работы программы godunovMatrix реализованной на julia с программой МСГ реализованной на C++ 22
5. Универсальная интерполяция орбит ГЛОНАСС и GPS по данным IGS 25
6. Чтение и запись файлов в Julia 30
6.1 Сравнение методов чтения и записи в Julia 30
6.2 Метод записи и чтения бинарного файла в Julia 32
7. Сравнение времени работы алгоритма метода сопряженных
градиентов и оператора “AB” в Julia 34
Заключение 37
Список сокращений 38
Список использованных источников 39
Приложения А - В 41 -47
При решении задач космической навигации появляются большие системы линейных алгебраических уравнений (СЛАУ). К примеру, задача определения координат приемника GPS/ГЛОНАСС. По сигналам навигационных спутников получаем разряженную систему из 4 миллионов ненулевых элементов. Требуется найти быстрый и точный способ решения таких систем в числах высокой точности. Один из методов решения СЛАУ - «Метод сопряженных градиентов» (МСГ).
Метод сопряженных градиентов [10] - предназначен для решения систем линейных алгебраических уравнений вида: А ■ х = b, где A - матрица размерности M*N, b - вектор размерности M.
Метод сопряженных градиентов при точных вычислениях приводит к ответу за конечное число шагов, но по сути является итерационным процессом, слабым местом которого является критерий остановки - определение номера шага процесса, после которого точность приближения к решению системы линейных уравнений на данном компьютере не может быть существенно улучшена.
Для тестирования алгоритма МСГ была выбрана СЛАУ Годунова. Эта система является плохо обусловленной. Для размерности равной 200, число обусловленности для СЛАУ Годунова составляет 7.76e16. Эту систему удобно использовать для проведения тестов корректности работы программ для решения СЛАУ, так как её решение для любой размерности легко можно вычислить по формулам. СЛАУ Годунова приведена в приложении А.
Выяснилось, что у МСГ есть множество вариантов реализации алгоритма. В работе будут рассмотрены все найденные варианты алгоритма с целью выявления наиболее быстрого и при этом не уступающего другим алгоритмам в точности нахождения решения. МСГ будет применен для решения СЛАУ, полученной из задачи определения положения спутников по их навигационным сигналам. В процессе исследования МСГ оказалось, что МСГ требователен к точности представления чисел в ЭВМ.
На сегодняшний день набирает популярность язык программирования Julia. Так как в Julia есть специальный тип данных (BigFloat) для работы с числами высокой точности, где мантисса числа указывается пользователем, то в целях ознакомления и изучения языка, алгоритм МСГ будет реализован на Julia. В процессе изучения языка, возникали вопросы, которые не описываются в официальной документации.
Julia[5] — высокоуровневый высокопроизводительный свободный язык программирования с динамической типизацией, созданный для математических вычислений. Эффективен также и для написания программ общего назначения. Julia написана на Си, C++ и Scheme.
На официальном сайте языка программирования Julia указано, что Julia практически не уступает в скорости языку C++. В работе будет проведено сравнение скорости работы программы на языке Julia с подобной программой, написанной на C++.
Необходимо проверить, как изменяется скорость работы программы при использовании чисел высокой точности. Сравниваться будут 2 подобные программы. В одной будет использоваться тип данных BigFloat, в другой - Float64.
Считывание координат спутников из текстовых файлов формата “txt” и составление матрицы в Julia занимает много времени и оперативной памяти. Поэтому поднимается вопрос о наиболее эффективном способе чтения и записи на жесткий диск.
У метода сопряженных градиентов есть различные вариации алгоритма, но нельзя точно определить, какой работает быстрее и точнее других одновременно. МСГ работает приемлемо, но он требователен к точности представления чисел. Рекомендуется использовать числа большой точности, что замедляет работу программы. Например, для размерности СЛАУ Годунова равной 400 время работы программы при использовании чисел большой точности увеличилось в 57 раз. Но, как показывает практика, для системы размерностью 26004x6 время работы алгоритма МСГ меньше в 1,5 раза, чем время работы встроенного в Julia оператора “AB” при одинаковой точности представления чисел.
Среди всех возможных вариантов чтения-записи в Julia определен наиболее быстрый. Разработана методика быстрого чтения-записи файлов, хранящих координаты, время и названия спутников. Эта методика ускоряет время считывания в 660 раз.
