АНАЛИЗ МОДИФИКАЦИЙ ДЛЯ ПРЯМОГО И ПРОЕКЦИОННОГО МЕТОДА РЕШЕНИЯ ЗАДАЧИ НАИМЕНЬШИХ КВАДРАТОВ С РАЗРЕЖЕННЫМИ МАТРИЦАМИ

Цель работы заключается в анализе разработанных численно устойчивых алгоритмов решения плохо обусловленных систем линейных алгебраических уравнений (СЛАУ) большой размерности, возникающих при решении задачи наименьших квадратов, которые должны учитывать структуру разреженных матриц, быть численно устойчивыми без значительного увеличения числа арифметических операций.

Успешное решение большинства научно-технических задач в значительной степени зависит от умения быстро и точно получать решение систем линейных алгебраических уравнений. Многие методы решения нелинейных задач также сводятся к решению некоторой последовательности линейных систем. В настоящее время разработано большое количество численных методов решения линейных алгебраических уравнений на ЭВМ [1]. Для многих методов разработан математический аппарат, позволяющий оценить точность полученного решения.

Задачи наименьших квадратов часто возникают как составная часть некоторой более обширной вычислительной проблемы. Почти любая задача, в которой исходных данных достаточно для того, чтобы переопределить решение, требует применения того или иного метода аппроксимаций. Наиболее часто в качестве критерия аппроксимации выбирают метод наименьших квадратов.

При расчетах по методу наименьших квадратов часто встречаются дополнительные ограничения. Задача, зачастую, может требовать обработки столь большого объема информации, что главной проблемой становится распределение машинной памяти [2]. Математические модели многих практических задач приводят к системам линейных алгебраических уравнений с большими и разреженными матрицами коэффициентов, в которых большинство элементов равны нулю.

Приписывание матрице свойства разреженности эквивалентно утверждению о существовании алгоритма, использующего её разреженность. Когда большая доля коэффициентов матрицы состоит из нулей, вполне очевидно, что нам не хотелось бы хранить в памяти компьютера все эти нули. Поэтому матричные алгоритмы должны проектироваться таким образом, чтобы обрабатывались только ненулевые элементы и чтобы на основании предварительного знания о расположении ненулевых элементов избегались операции типа сложения с нулем или умножения на нуль. Таким образом, число операций, производимых машиной при исполнении алгоритма, пропорционально числу ненулевых элементов, а не числу всех элементов матрицы.

Серьезную проблему при хранении и обработке разреженных матриц представляет заполнение, т. е. возникновение новых ненулевых элементов в процессе вычисления. Хороший алгоритм для разреженных матриц пытается сохранить разреженность, по возможности уменьшая заполнение.

Конечно, не все алгоритмы для разреженных матриц достигают этих целей, а только наиболее изощренные. Многие схемы хранения допускают определенную долю нулей, и алгоритм обрабатывает их, как если бы они не были нулями. Алгоритм, хранящий и обрабатывающий меньшее число нулей, более сложен, труднее программируется и целесообразен только для достаточно больших матриц.

Разреженные матрицы, возникающие при решении задач наименьших квадратов, являются, как правило, плюс ко всему еще и плохо обусловленными. Решение систем уравнений с плохо обусловленными матрицами остается по-прежнему большой проблемой, сложность которой связана с сильной чувствительностью решения к точности задания элементов матрицы и компонент вектора правой части системы.

На данный момент в области исследований нет алгоритмов решения систем линейных алгебраических уравнений для задачи наименьших квадратов с большими разреженными плохо обусловленными матрицами, которые были бы численно устойчивыми без значительного числа арифметических операций, обладали достаточной универсальностью и простотой реализации.

Поэтому разработка таких алгоритмов является актуальной на сегодняшний день.

Все методы решения систем линейных алгебраических уравнений можно разделить на два класса: прямые и итерационные [3]. В дальнейшем мы будем рассматривать прямые методы решения систем линейных алгебраических уравнений. В частности рассматривается метод Холецкого, метод QR-разложения. В применение к решению расширенных систем актуальны метод Гаусса и метод LU-разложения.

Модифицируем данные методы, применив прямой проекционный подход.

Рассмотрим численные эксперименты для разработанного алгоритма прямого проекционного метода с выбором ведущего элемента для решения плохо обусловленных задач наименьших квадратов с разреженными матрицами.

Входными данными являлись: матрица коэффициентов системы линейных уравнений, вектор правой части и вектор точного решения. Поскольку матрица коэффициентов разреженная и неструктурированная, использовалась следующая структура хранения: храним только ненулевые элементы, и каждый элемент сопровождается дополнительной информацией о его местоположении. Это значит, что кроме числового значения коэффициента  мы должны знать номер строки  и номер столбца . Эту информацию можно разместить в трех одномерных массивах, первый из которых содержит значения коэффициентов , а второй и третий, соответственно, номера строк и столбцов.

В качестве вектора точного решения брался вектор .

Для того чтобы рассмотреть работу алгоритма на реальных задачах, в качестве тестовых матриц использовались матрицы из коллекции Harwell-Boeing. В таблице приведен список рассмотренных матриц вместе с их размерами, числом ненулевых элементов и областью применения.

Таблица 1.

Тестовые матрицы и их характеристики

На рисунках 1, 2, 3, 4 представлены профили некоторых тестовых матриц.

Рисунок 1. Профиль тестовой      Рисунок 2. Профиль тестовой

матрицы FS 183 3                        матрицы HOR 131         

Рисунок 3. Профиль тестовой      Рисунок 4. Профиль тестовой

      матрицы WEST 0167                   матрицы ORSIRR 2                   

Проводилась серия экспериментов на матрицах из коллекции Harwell-Boeing, в которой для выбора ведущего элемента параметр  из условия

изменялся в интервале , и наблюдалась зависимость заполнения и точности решения от значения параметра.

Проиллюстрируем результаты эксперимента на примере тестовой матрицы HOR 131. Значение числа обусловленности выбранной матрицы: . На рисунках 5 и 6 представлены графики зависимости точности получаемого решения и заполнения от выбора параметра .

Рисунок 5. Зависимость точности решения от выбора параметра u

Рисунок 6. Зависимость заполнения от выбора параметра u

Из графиков видно, что при выборе , близкого к значению  мы получаем заполнение на 5% меньше, чем при . При таком выборе  сохраняется и устойчивость алгоритма, из чего можно сделать вывод, что выбор параметра , близкого к значению  является оптимальным с точки зрения нахождения компромисса между точностью получаемого решения и сохранением разреженности.

Следующим этапом численного исследования алгоритма являлось сравнение прямого проекционного метода с нестандартным выбором ведущего элемента с параметром  с ППМ без выбора ведущего элемента и ППМ со стандартной стратегией выбора ведущего элемента.

При решении задачи наименьших квадратов прямым проекционным методом с нестандартной стратегией выбора ведущего элемента точность получаемого решения оказывается на 1-2 порядка выше, чем при использовании ППМ без выбора ведущего элемента и ППМ со стандартной стратегией выбора. Заполнение в процессе выполнения алгоритма ППМ с нестандартной стратегией выбора ведущего элемента оказывается на 1-7% меньше.

Полученные результаты показывают, что разработанный алгоритм прямого проекционного метода с нестандартным выбором ведущего элемента с параметром , близким к значению  является эффективным для плохо обусловленных задач наименьших квадратов с разреженными матрицами, так как позволяет повысить точность получаемого решения и уменьшить заполнение.

Численное исследование включало в себя также рассмотрение прямого проекционного метода с нестандартным выбором ведущего элемента для расширенных СЛАУ в сравнении с разложением Холецкого для нормальных систем.

При решении задачи наименьших квадратов прямым проекционным методом с нестандартной стратегией выбора ведущего элемента точность получаемого решения оказывается на 1-3 порядка выше, чем при использовании разложения Холецкого, причем, с ростом числа обусловленности входной матрицы, значительно увеличивается разница в точности получаемого решения.

Анализ полученных данных показывает, что с точки зрения заполнения, прямой проекционный метод с разработанной стратегией выбора ведущего элемента проигрывает по сравнению с методом Холецкого. Это связано с тем, что ППМ применяется для решения расширенной СЛАУ, размерности , в то время как метод Холецкого применен с использованием нормальной СЛАУ (размерность ).

В процессе проведения эксперимента было проведено сравнение эффективности разложения Холецкого и ППМ с нестандартной стратегией выбора ведущего элемента в зависимости от начального процента заполненности матрицы. На рисунке 7 представлена графическая интерпретация зависимости логарифма отношения заполнения, получаемого при решении задачи наименьших квадратов методом разложения Холецкого к заполнению, полученному в результате выполнения алгоритма прямого проекционного метода с нестандартной стратегией выбора ведущего элемента от начального значения заполнения тестовой матрицы в процентах.

Рисунок 7. Сравнение эффективности методов в зависимости от заполненности матрицы

Анализ представленных данных показывает, что с точки зрения заполнения метод Холецкого эффективен при начальном числе ненулевых элементов менее 5%. При начальном заполнении матрицы более 5% лучший результат дает использование прямого проекционного метода с нестандартной стратегией выбора ведущего элемента.

Ортогональные методы для сравнения не приводились, так как, хотя они и являются численно устойчивыми, но требуют больших вычислительных затрат.

В результате проделанных численных исследований можно сделать вывод, что примененный алгоритм прямого проекционного метода с выбором ведущего элемента для решения плохо обусловленных задач наименьших квадратов с использованием расширенной СЛАУ по сравнению с разложением Холецкого с методом нормальных систем уравнений позволяет получить значительно более точное решение.

Список литературы:

1. Голуб Дж., Ван Лоун Ч.  Матричные вычисления. М.: Мир, 1999. 548с.
2. Лоусон Ч., Хенсон Р. Численное решение задач метода наименьших квадратов. М.: Наука. Гл. ред. физ.-мат. лит., 1986. 232 с.
3. Беклемишев Д.В. Дополнительные главы линейной алгебры. М.: Наука, 1983. 336 c.