My source

home

Допустимо свободное использование материалов данного раздела, в том числе и для создания законченных коммерческих программ с указанием источника. http://drobotenko.com/ . Для написания платных книг, библиотек и плагинов требуется разрешение автора.

Метод формальных манипуляций для обращения матриц.

Линейные системы основа всех численных методов. Решение линейных систем проходят еще в школе. Предлагаемый алгоритм обращения матриц отличается просто более тщательной группировкой членов и совмещением операций. Как и LU разложение он обращает матрицу “на месте” , без дополнительной памяти, но более быстрый. Все операции выполняются в одном цикле, нет декомпозиций, прямого-обратного прохода. Число операций ровно N³ - столько же сколько и умножение матриц. Коды много лет используются в коммерческих проектах.

Примерный алгоритм

Заводятся 2 целых вектора длинной N. Векторы расписываются номерами строк, столбцов.
Среди всех непомеченных строк, столбцов ищется максимальный элемент M_pq
Вычисления
- Для всех элементов
  M_jk-= M_pk*M_jq/M_pq
- Для строк и столбцов ведущего элемета
  M_jq/= M_pq
  M_pj/= M_pq
- сам ведущий
  M_pq= -1/ M_pq
строка и столбец ведущего помечаются как обработанные (значение -1) и производятся перестановки
Если остались необработанные - возврат к новому поиску ведущего

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

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

В этих кодах производится полный разбор всех случаев. И обращение, и решение СЛАУ возвращают дефект линейного преобразования, детерминант и частичное решение в том случае если детерминант равен 0. Частичное решение - это решение на подпространстве, где детерминант еще не равен 0. Это частичное решение, например, подходит для метода наименьших квадратов, даже в том случае если ищется приближение функциями, которые линейно зависимы.

Здесь две версии кодов. Шаблонная версия кодов отличается тем, что может работать с родными массивами c++ и любыми контейнерами. При этом допустимо их смешение в одном вызове. Для подключения любого контейнера достаточно дописать пару строчек. Реализован оператор определения типа в шаблонах – typeof. Это решение соответствует последним стандартам и проверено в VC6 – VC8. Версия доубле содержит удобные контейнеры, также совместима с простыми массивами.

Новая версия VC6-VC8

КОДЫ - какаято старая версия