Методы ABS , аббревиатура которых содержит инициалы Йожефа Абаффи, Чарльза Г. Бройдена и Эмилио Спедикато , были разработаны с 1981 года для создания большого класса алгоритмов для следующих приложений:
- решение общих линейных алгебраических систем, детерминированных или недоопределенных,
- полное или неполное звание;
- решение линейных диофантовых систем , т. е. систем уравнений, в которых матрица коэффициентов и правая часть являются целочисленными и ищется целочисленное решение; это частный, но важный случай десятой проблемы Гильберта , единственной практически разрешимой;
- решение нелинейных алгебраических уравнений ;
- решение непрерывной неограниченной или ограниченной оптимизации .
В начале 2007 года литература по АБС состояла из более 400 статей и отчетов и двух монографий, одна из которых принадлежит Абаффи и Спедикато и опубликована в 1989 году, одна - Ся и Чжан и опубликована на китайском языке в 1998 году. Кроме того, были организованы три конференции. в Китае.
Исследования методов АБС явились результатом международного сотрудничества, координируемого Спедикато из Университета Бергамо , Италия. В нем приняли участие более сорока математиков из Венгрии, Великобритании, Китая, Ирана и других стран.
Центральным элементом в таких методах является использование специального матричного преобразования, созданного , по сути, венгерским математиком Йене Эгервари , который исследовал его основные свойства в некоторых статьях, которые остались незамеченными. Для основной задачи решения линейной системы m уравнений от n переменных, где, Методы ABS используют следующую простую геометрическую идею:
- Учитывая произвольную начальную оценку решения, найдите одно из бесконечных решений, определяющее линейное многообразие размерности n - 1 первого уравнения.
- Найти решение второго уравнения, которое также является решением первого, т.е. найти решение, лежащее на пересечении линейных многообразий решений первых двух уравнений, рассматриваемых по отдельности.
- Путем итерации описанного выше подхода после m ' шагов получается решение последнего уравнения, которое также является решением предыдущих уравнений, а значит, и всей системы. Более того, можно обнаружить избыточные или несовместимые уравнения.
Среди основных результатов, полученных к настоящему времени:
- унификация алгоритмов для линейных, нелинейных алгебраических уравнений и нелинейной оптимизации с линейными ограничениями, включая задачу LP как частный случай;
- усовершенствован метод Гаусса за счет уменьшения требуемой памяти и устранения необходимости поворота;
- новые методы для нелинейных систем со свойствами сходимости лучше, чем у метода Ньютона;
- вывод общего алгоритма десятой проблемы Гильберта, линейный случай, с распространением классической теоремы Эйлера с одного уравнения на систему;
- получены решатели, более устойчивые, чем классические, особенно для задачи, возникающей в прямодвойном методе внутренних точек;
- Методы ABS обычно работают быстрее на векторных или параллельных машинах;
- Методы ABS обеспечивают более простой подход к обучению различным классам задач, поскольку конкретные методы получаются только путем выбора определенных параметров.
Знания о методах ABS среди математиков все еще весьма ограничены, но они обладают большим потенциалом для улучшения методов, используемых в настоящее время.
Библиография
- Йожеф Абаффи, Эмилио Спедикато (1989): Алгоритмы проекции ABS: математические методы для линейных и нелинейных алгебраических уравнений , Эллис Хорвуд, Чичестер. Первая монография по теме
- Йожеф Абаффи, Чарльз Г. Бройден, Эмилио Спедикато (1984): класс прямых методов для линейных уравнений , Numerische Mathematik 45 , 361-376. Статья о методах АБС для непрерывных линейных систем .
- Х. Эсмаили, Н. Махдави-Амири, Эмилио Спедикато: класс алгоритмов ABS для диофантовых линейных систем , Numerische Mathematik 90 , 101-115. Статья, знакомящая с методами АБС для целочисленных линейных систем .