методы АБС

Методы ABS , где аббревиатура содержит инициалы Йожефа Абаффи, Чарльза Г. Бройдена и Эмилио Спедикато , разрабатываются с 1981 года для создания большого класса алгоритмов для следующих приложений:

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

В начале 2007 года литература ABS состояла из более чем 400 статей и отчетов, а также двух монографий: одна принадлежит Абаффи и Спедикато и опубликована в 1989 году, другая принадлежит Ся и Чжану и опубликована на китайском языке в 1998 году. Кроме того, были проведены три конференции. организован в Китае.

Исследования методов ABS стали результатом международного сотрудничества, координируемого Spedicato из университета Бергамо , Италия. В нем приняли участие более сорока математиков из Венгрии, Великобритании, Китая, Ирана и других стран.

Центральным элементом таких методов является использование специального матричного преобразования, обязанного, по сути, венгерскому математику Йене Эгервари , который исследовал его основные свойства в некоторых работах, которые остались незамеченными. Для основной задачи решения линейной системы m уравнений от n переменных, где $\scriptstyle m\,\leq \,n$ Методы ABS используют следующую простую геометрическую идею:

Учитывая произвольную начальную оценку решения, найдите одно из бесконечных решений, определяющее линейное многообразие размерности n - 1 первого уравнения.
Найти решение второго уравнения, которое является также решением первого, т. е. найти решение, лежащее в пересечении линейных многообразий решений первых двух уравнений, рассматриваемых отдельно.
Повторяя описанный выше подход после m' шагов, можно получить решение последнего уравнения, которое также является решением предыдущих уравнений, а значит, и всей системы. Более того, можно обнаружить уравнения, которые являются либо избыточными, либо несовместимыми.

Среди основных результатов, полученных на данный момент:

унификация алгоритмов для решения линейных, нелинейных алгебраических уравнений и для линейно-ограниченной нелинейной оптимизации, включая задачу ЛП как частный случай;
метод Гаусса за счет уменьшения требуемой памяти и устранения необходимости поворота; усовершенствован
новые методы для нелинейных систем со свойствами сходимости лучше, чем у метода Ньютона;
вывод общего алгоритма для десятой задачи Гильберта, линейный случай, с распространением классической теоремы Эйлера с одного уравнения на систему;
получены более устойчивые, чем классические, решатели, особенно для задачи, возникающей в методе прямой-двойственной внутренней точки;
Методы ABS обычно работают быстрее на векторных или параллельных машинах;
Методы ABS обеспечивают более простой подход к обучению различным классам задач, поскольку конкретные методы получаются только за счет выбора определенных параметров.

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

Библиография

Йожеф Абаффи, Эмилио Спедикато (1989): Алгоритмы проецирования ABS: математические методы для линейных и нелинейных алгебраических уравнений , Эллис Хорвуд, Чичестер. Первая монография по этой теме.
Йожеф Абаффи, Чарльз Г. Бройден, Эмилио Спедикато (1984): Класс прямых методов для линейных уравнений , Numerische Mathematik 45 , 361–376. Статья, знакомящая с методами ABS для непрерывных линейных систем .
Х. Эсмаили, Н. Махдави-Амири, Эмилио Спедикато: класс алгоритмов ABS для диофантовых линейных систем , Numerische Mathematik 90 , 101–115. Статья, знакомящая с методами ABS для целочисленных линейных систем .