|
Эта публикация цитируется в 1 научной статье (всего в 1 статье)
МАТЕМАТИЧЕСКИЕ ОСНОВЫ И ЧИСЛЕННЫЕ МЕТОДЫ МОДЕЛИРОВАНИЯ
Прямые мультипликативные методы для разреженных матриц. Квадратичное программирование
А. Б. Свириденко ФГБОУ ВПО «Кубанский государственный университет» филиал в г. Новороссийске,
Россия, 353922, г. Новороссийск, ул. Героев Десантников, д. 87
Аннотация:
Рассматривается численно устойчивый прямой мультипликативный метод решения систем линейных уравнений, учитывающий разреженность матриц, представленных в упакованном виде. Преимущество метода состоит в расчете факторов Холесского для положительно определенной матрицы системы уравнений и ее решения в рамках одной процедуры, а также в возможности минимизации заполнения главных строк мультипликаторов без потери точности результатов, причем изменения в позиции очередной обрабатываемой строки матрицы не вносятся, что позволяет использовать статические форматы хранения данных. Решение системы линейных уравнений прямым мультипликативным алгоритмом — это, как и решение с помощью $LU$-разложения, просто другая схема реализации метода исключения Гаусса.
Расчет факторов Холесского для положительно определенной матрицы системы и ее решение лежит в основе построения новой математической формулировки безусловной задачи квадратичного программирования и новой формы задания необходимых и достаточных условий оптимальности, которые достаточно просты и в данной работе используются для построения новой математической формулировки задачи квадратичного программирования на многогранном множестве ограничений, которая представляет собой задачу поиска минимального расстояния между началом координат и точкой границы многогранного множества ограничений средствами линейной алгебры и многомерной геометрии.
Для определения расстояния предлагается применить известный точный метод, основанный на решении систем линейных уравнений, размерность которых не выше числа переменных целевой функции. Расстояния определяются построением перпендикуляров к граням многогранника различной размерности. Для уменьшения числа исследуемых граней предлагаемый метод предусматривает специальный порядок перебора граней. Исследованию подлежат только грани, содержащие вершину, ближайшую к точке безусловного экстремума, и видимые из этой точки. В случае наличия нескольких ближайших равно-удаленных вершин исследуется грань, содержащая все эти вершины, и грани меньшей размерности, имеющие с первой гранью не менее двух общих ближайших вершин.
Ключевые слова:
математическое программирование, квадратичное программирование, разреженные матрицы, прямой мультипликативный алгоритм, новые математические формулировки, необходимые и достаточные условия оптимальности, квадратичная задача, линейное программирование, многомерная геометрия.
Поступила в редакцию: 01.11.2017 Исправленный вариант: 07.05.2018 Принята в печать: 08.05.2018
Образец цитирования:
А. Б. Свириденко, “Прямые мультипликативные методы для разреженных матриц. Квадратичное программирование”, Компьютерные исследования и моделирование, 10:4 (2018), 407–420
Образцы ссылок на эту страницу:
https://www.mathnet.ru/rus/crm454 https://www.mathnet.ru/rus/crm/v10/i4/p407
|
Статистика просмотров: |
Страница аннотации: | 172 | PDF полного текста: | 107 | Список литературы: | 22 |
|