RUS  ENG ЖУРНАЛЫ   ПЕРСОНАЛИИ   ОРГАНИЗАЦИИ   КОНФЕРЕНЦИИ   СЕМИНАРЫ   ВИДЕОТЕКА   ЛИЧНЫЙ КАБИНЕТ
Общая информация
Последний выпуск
Архив

Поиск публикаций
Поиск ссылок

RSS
Последний выпуск
Текущие выпуски
Архивные выпуски
Что такое RSS



Компьютерные исследования и моделирование:
Год:
Том:
Выпуск:
Страница:
Найти






Персональный вход:
Логин:
Пароль:
Запомнить пароль
Войти
Забыли пароль?
Регистрация


Компьютерные исследования и моделирование, 2017, том 9, выпуск 5, страницы 679–703 (Mi crm92)  

МАТЕМАТИЧЕСКИЕ ОСНОВЫ И ЧИСЛЕННЫЕ МЕТОДЫ МОДЕЛИРОВАНИЯ

Прямые мультипликативные методы для разреженных матриц. Ньютоновские методы

А. Б. Свириденко

ФГБОУ ВПО «Кубанский государственный университет», филиал в г. Новороссийске, Россия, 353922, г. Новороссийск, ул. Героев Десантников, д. 87

Аннотация: Рассматривается численно устойчивый прямой мультипликативный алгоритм решения систем линейных уравнений, учитывающий разреженность матриц, представленных в упакованном виде. Преимущество алгоритма состоит в возможности минимизации заполнения главных строк мультипликаторов без потери точности результатов, причем изменения в позиции очередной обрабатываемой строки матрицы не вносятся, что позволяет использовать статические форматы хранения данных. Решение системы линейных уравнений прямым мультипликативным алгоритмом — это, как и решение с помощью $LU$-разложения, просто другая схема реализации метода исключения Гаусса.
В данной работе этот алгоритм лежит в основе решения следующих задач.
Задача 1. Задание направления спуска в ньютоновских методах безусловной оптимизации путем интеграции одной из известных техник построения существенно положительно определенной матрицы. Такой подход позволяет ослабить или снять дополнительные специфические трудности, обусловленные необходимостью решения больших систем уравнений с разреженными матрицами, представленных в упакованном виде.
Задача 2. Построение новой математической формулировки задачи квадратичного программирования и новой формы задания необходимых и достаточных условий оптимальности. Они достаточно просты и могут быть использованы для построения методов математического программирования, например для поиска минимума квадратичной функции на многогранном множестве ограничений, основанного на решениях систем линейных уравнений, размерность которых не выше числа переменных целевой функции.
Задача 3. Построение непрерывного аналога задачи минимизации вещественного квадратичного многочлена от булевых переменных и новой формы задания необходимых и достаточных условий оптимальности для разработки методов их решения за полиномиальное время. В результате исходная задача сводится к задаче поиска минимального расстояния между началом координат и угловой точкой выпуклого многогранника (полиэдра), который является возмущением $n$-мерного куба и описывается системой двойных линейных неравенств с верхней треугольной матрицей коэффициентов с единицами на главной диагонали. Исследованию подлежат только две грани, одна из которых или обе содержат вершины, ближайшие к началу координат. Для их вычисления достаточно решить $4n-4$ систем линейных уравнений и выбрать среди них все ближайшие равноудаленные вершины за полиномиальное время. Задача минимизации квадратичного полинома является $NP$-трудной, поскольку к ней сводится $NP$-трудная задача о вершинном покрытии для произвольного графа. Отсюда следует вывод, что $P=NP$, в основе построения которого лежит выход за пределы целочисленных методов оптимизации.

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

DOI: https://doi.org/10.20537/2076-7633-2017-9-5-679-703

Полный текст: PDF файл (1660 kB)
Полный текст: http://crm.ics.org.ru/.../2616
Список литературы: PDF файл   HTML файл

Тип публикации: Статья
УДК: 519.85
Поступила в редакцию: 20.02.2017
Исправленный вариант: 22.09.2017
Принята в печать:29.09.2017

Образец цитирования: А. Б. Свириденко, “Прямые мультипликативные методы для разреженных матриц. Ньютоновские методы”, Компьютерные исследования и моделирование, 9:5 (2017), 679–703

Цитирование в формате AMSBIB
\RBibitem{Svi17}
\by А.~Б.~Свириденко
\paper Прямые мультипликативные методы для разреженных матриц. Ньютоновские методы
\jour Компьютерные исследования и моделирование
\yr 2017
\vol 9
\issue 5
\pages 679--703
\mathnet{http://mi.mathnet.ru/crm92}
\crossref{https://doi.org/10.20537/2076-7633-2017-9-5-679-703}


Образцы ссылок на эту страницу:
  • http://mi.mathnet.ru/crm92
  • http://mi.mathnet.ru/rus/crm/v9/i5/p679

    ОТПРАВИТЬ: VKontakte.ru FaceBook Twitter Mail.ru Livejournal Memori.ru


    Citing articles on Google Scholar: Russian citations, English citations
    Related articles on Google Scholar: Russian articles, English articles
  • Компьютерные исследования и моделирование
    Просмотров:
    Эта страница:57
    Полный текст:24
    Литература:7

     
    Обратная связь:
     Пользовательское соглашение  Регистрация  Логотипы © Математический институт им. В. А. Стеклова РАН, 2019