Методы АБС - ABS methods - Wikipedia

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

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

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

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

Центральным элементом таких методов является использование специального матричного преобразования, созданного в основном венгерским математиком. Jen Egerváry, который исследовал его основные свойства в некоторых статьях, оставшихся незамеченными. Для основной задачи решения линейной системы м уравнения в п переменные, где ${\displaystyle \scriptstyle m\,\leq \,n}$В методах ABS используется следующая простая геометрическая идея:

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

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

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

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

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

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