03.11.2017 admin

3.1. Метод Сергеева


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

Определение 1. Алгоритм Сергеева порождает матрицу X сигнатуры взвешенных столбцов векторов невязок, генерируемых некоторой парой (A, b) согласно следующей формуле

xk=sign(diag(ω)εk), εkk–1–Axk–1, ε0=b.


Осцилляции компонент вектора состояния порождаются динамикой линейной части в сочетании нелинейной функцией sign(), которая сопоставляет нулевым значениям компонент ее аргумента единицы.

Алгоритм стартует с x0=0 и, при подходящем выборе весового вектора ω, заканчивается нулевым вектором невязки. Матрица сигнатуры с элементами {1,–1} будет матрицей Адамара, если генерирующий ее процесс разворачивает вектор состояния на каждом шаге до вектора, ортогонального предыдущему множеству. Даже если это не происходит, сигнатурная матрица единичных по амплитуде осцилляций обладает некоторыми иными полезными качествами.

Такова, например, матрица X, дающая монотонно возрастающее по m-норме решение cистемы линейных алгебраических уравнений Ax=b суммированием элементов ее строк. Для микропроцессорной техники это достаточно важное преимущество ввиду простоты масштабирования удерживаемых разрядной сеткой переменных.

Положение 1. Решение cистемы линейных уравнений Ax=b, с матрицей диагонального преобладания, порождающей весовую матрицу diag(A), и вектором b с четными компонентами, дается отображением x=Xv единичного вектора v=[1 1 ... 1]T.

Метод интересен тем, что вычисляет не приближенное, а точное решение за гарантированное число шагов, равное m-норме (максимуму модуля компоненты) вектора решения. Диагональное преобладание понимается в смысле Σj=1:n, ji |aij| < q |aii|, 0 < q < 1.

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

Пример 1. Пусть даны следующие матрицы для сигнатурного анализа

A=
 –2 
 –1 
1
3
,
b=
 –7 
6


Монотонное падение норм вектора невязки, итерируемого от стартового его значения ε0=2b, связано со следующей сигнатурной матрицей

X=
1
1
1
1
  1 
  1 
1
1
1
1
 –1 
 –1 


Суммированием элементов строк она дает удвоенное значение точного решения x=(3 1)T системы Ax=b.


Пример 2. Пример четвертого порядка с матрицами

A=
 –13 
2
 –1 
3
 –6 
 19 
4
5
 –1 
 –5 
 –37 
7
 –5 
 –9 
8
 23 
b=
 –61 
 –217 
 233 
 520 


Вывод графиков частных сумм элементов строк генерируемой для пары (A,2b) сигнатурной матрицы показывает характерные "точки бифуркации", обеспечиваемые внутренней динамикой процесса, дающие итоговое решение 2x=(14 –28 –2 38)T.



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


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

Хаотические решения, порождаемые ввиду определенного сорта несовместности, интересны в том контексте, что обобщенные матрицы Адамара – фракталы, не всегда имеющие простую конфигурацию в пространстве состояний.

Разновидности такого сорта процессов с асимметричными функциями насыщения a=1, –b, b<a, могут рассматриваться как генераторы всех или части строк минимаксных матриц при соответствующих выборе матричного генератора и его настройке.

1. Сергеев М.Б. Гибридный разрядный метод решения систем уравнений в целочисленной арифметике. Журнал Информационно-управляющие системы. N 2-3, c. 16-18. 2003 г.

Hide

Rambler's Top100