Все выпуски

Многомерные данные, при использовании значительно большего количества признаков относительно меньшего числа наблюдений, порождают хорошо известную проблему переопределённой задачи. В связи с этим, представляется целесообразным описание данных в терминах меньшего числа мета-признаков, которые вычисляются при помощи так называемых матричных факторизаций. Такие факторизации способствуют уменьшению случайного шума при сохранении наиболее существенной информации. Три новых и взаимосвязанных метода предложены в этой статье: 1) факторизационный механизм градиентного спуска с двумя (согласно размерности микрочипа) гибкими и адаптируемыми параметрами обучения, включая явные формулы их автоматического пересчета, 2) непараметрический критерий для отбора количества факторов, и 3) неотрицательная модификация градиентной факторизации, которая не требует дополнительных вычислительных затрат в сравнении с базовой моделью. Мы иллюстрируем эффективность предложенных методов в приложении к задаче направляемой классификации данных в области биоинформатики.

В настоящее время для численного моделирования начально-краевых задач для систем гиперболических уравнений в частных производных (например, уравнения газовой динамики, МГД, деформируемого твердого тела и т. д.) применяются различные нелинейные численные схемы пространственной аппроксимации. Это связано с необходимостью повышения порядка аппроксимации и расчета разрывных решений, часто возникающих в таких системах. Необходимость в нелинейных схемах связана с ограничением, следующим из теоремы С. К. Годунова о невозможности построения линейной схемы порядка больше первого для монотонной аппроксимации уравнений такого типа. Одними из наиболее точных нелинейных схем являются схемы типа ENO (существенно не осциллирующие схемы и их модификации), в том числе схемы WENO (взвешенные, существенно не осциллирующие схемы). Последние получили наибольшее распространение, поскольку при одинаковой ширине шаблона имеют более высокий порядок аппроксимации чем ENO-схемы. Плюсом ENO- и WENO-схем является сохранение высокого порядка аппроксимации на немонотонных участках решения. Исследование данных схем затруднительно в связи с тем, что сами схемы нелинейны и применяются для аппроксимации нелинейных уравнений. В частности, условие линейной устойчивости ранее было получено только для схемы WENO5 (пятого порядка аппроксимации на гладких решениях) и является приближенным. В настоящей работе рассматриваются вопросы построения и устойчивости схем WENO5, WENO7, WENO9, WENO11 и WENO13 для конечно-объемной схемы для уравнения Хопфа. В первой части статьи рассмотрены методы WENO в общем случае и приведены явные выражения для коэффициентов полиномов и весов линейных комбинаций, необходимых для построения схем. Доказывается ряд утверждений, позволяющих сделать выводы о порядках аппроксимации в зависимости от локального вида решения. Проводится анализ устойчивости на основе принципа замороженных коэффициентов. Рассматриваются случаи гладкого и разрывного поведения решения в области линеаризации при замороженных коэффициентах на гранях конечного объема и анализируется спектр схем для этих случаев. Доказываются условия линейной устойчивости для различных методов Рунге–Кутты при применении со схемами WENO. В результате приводятся рекомендации по выбору максимально возможного параметра устойчивости, которое наименьшим образом влияет на нелинейные свойства схем. Следуя полученным ограничениям, делается вывод о сходимости схем.

Малая практическая ценность многих численных методов решения несимметричных систем линейных уравнений с плохо обусловленными матрицами объясняется тем, что эти методы в реальных условиях ведут себя совсем иначе, чем в случае точных вычислений. Исторически вопросам устойчивости не отводилось достаточного внимания, как в численной алгебре «средних размеров», а делался акцент на решении задач максимального порядка при данных возможностях вычислительной машины, в том числе за счет некоторой потери точности результатов. Поэтому главными объектами исследования были: наиболее целесообразное хранение информации, заключенной в разреженной матрице; поддержание наибольшей степени ее разреженности на всех этапах вычислительного процесса. Таким образом, разработка эффективных численных методов решения неустойчивых систем относится к актуальным проблемам вычислительной математики.

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

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

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