Определитель матрицы

15.12.13

Разработка - Математика и алгоритмы

Представлена программная реализация вычисления определителя матрицы посредством языка запросов 1С. Даны два метода:
1) прямой, на основе определения
2) метод Гаусса, приведение к диагональному виду с вычислением произведения диагональных элементов.

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

Скачать файлы

Наименование Файл Версия Размер
Определитель матрицы
.epf 24,83Kb
16
.epf 1.1 24,83Kb 16 Скачать

Не озабочиваясь областью применения,  предлагаю ознакомиться с прилагаемой Обработкой "Определитель матрицы".

Описание

Исходная матрица А порядка n задается естественным образом в виде квадратной таблицы элементов. Предусмотрена генерация случайных элементов с опциями: диапазон значений элементов, только неотрицательные, единичная матрица.

Матрицу можно выгрузить в формате Excel стандартным способом и загрузить обратно. (Я применял данную выгрузку для проверки правильности вычислений, загружая в пакет Mathematica.)

Расчет можно проводить двумя методами, для каждого из которых опционально рассмотрены 2 технических способа.

Предусмотрено сравнение результатов расчета.

Работа с матрицами ведется в формате временных таблиц структуры i,j,elem, где i,j - индексы элемента матрицы, elem - значение элемента. Начало данному представлению положено в статье  Умножение матриц пакетным запросом.

 Алгоритмы

 I. Прямой метод.

 Основной запрос,  формируемый (n-1)  раз в цикле, имеет вид

	"ВЫБРАТЬ  
	| Таб1.iA  Как iA, Таб1.jA  Как jA, Таб2.i КАК i, Таб2.j КАК j, Таб2.elem КАК elem , Таб1.Произведение * Таб2.elem Как Произведение,
	| Таб1.ПерестановкаИндексовСтрока + Таб1.jСтрока как ПерестановкаИндексовСтрока, Таб2.jСтрока как jСтрока,
	| Выбор Когда Таб2.jНовый > Таб1.jНовый Тогда Таб2.jНовый-1 Иначе Таб2.jНовый Конец  КАК jНовый,
	| Выбор Когда ВЫРАЗИТЬ((Таб1.jНовый)/2 КАК ЧИСЛО(15, 0)) = (Таб1.jНовый)/2 Тогда -1 Иначе 1 Конец * Таб1.Знак как Знак
	| Поместить Миноры 
	| ИЗ Миноры_Предок Как Таб1 Внутреннее соединение Миноры_Предок Как Таб2 
	| По Таб1.i = &i И Таб1.ПерестановкаИндексовСтрока = Таб2.ПерестановкаИндексовСтрока И Таб1.j <> Таб2.j И Таб1.i <> Таб2.i;"

Завершающий запрос, сумма произведений элементов строки на  их алгебраические дополнения:

	"Выбрать  Выбор Когда ВЫРАЗИТЬ((Миноры.iA)/2 КАК ЧИСЛО(15, 0)) = (Миноры.iA)/2 Тогда -1 Иначе 1 Конец * 
	| Сумма(Миноры.Знак * Миноры.Произведение * Миноры0.elem ) Как Значение 
	| Поместить Определитель
	| из Миноры как Миноры 
	| Левое соединение Миноры0 Как Миноры0 По Миноры.iA = Миноры0.iA И Миноры.jA = Миноры0.jA
	| Сгруппировать по Миноры.iA" 

В представленном коде соединение таблиц осуществляетя по строковому полю ПерестановкаИндексовСтрока, получаемому при помощи конкатенации строковых представлений индексов столбцов j:  Таб1.ПерестановкаИндексовСтрока + Таб1.jСтрока.
Опционально можно заменить Соединение на другое, по числовому полю ( Таб1.ПерестановкаИндексов *10 + Таб1.j)  как ПерестановкаИндексов. Но в этом случае вычисления ограничены 10-м порядком.

На самом деле, это некоторая комбинация прямого метода и метода разложения определителя по строке (с понижением порядка). Здесь можно задать начальную строку разложения исходной матрицы, что дает выделить алгебраические дополнения, соответствующие элементам этой строки.

Эффективность метода в интервале n < 11 (для матриц с единичными по модулю элементами; при увеличении модулей эффективный интервал уменьшается).  Около этой границы начинаются тормоза и переполнение памяти. Видимо, это связано с тем, что количество слагаемых, входящих в определение детерминанта, равно факториалу порядка матрицы n!. То есть 10! = 3 628 800, 11! =39 916 800  и т.п. операций\строк.

II. Метод Гаусса.

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

Данный метод сводит исходную матрицу к треугольной и подсчитывает произведение диагональных элементов.
На самом деле в результате преобразований получается "почти треугольная матрица", которую можно сделать треугольной, проведя перестановку строк в конце процедуры, за одним подсчитав число инверсий этой перестановки. Нам нужно даже не число этих инверсий, а четность\нечетность этого числа. И все для того, чтобы сделать последнюю операцию - коррекцию знака определителя (+\-), так как произведение диагональных элементов уже подсчитано в процессе "диагонализации".
Метод нахождения инверсий дан в статье Инверсии перестановок.

Оба метода должны работать для матриц с любыми вещественными элементами. (Однако в обработке стоит ограничение только на целые числа.)

Для порядков более 12 подсчет становится проблематичным и для метода Гаусса из-за "ошибки переполнения", хотя и дает в некоторых случаях лучшие результаты по сравнению с прямым методом.

Для частного случая целочисленных элементов матрицы можно еще несколько улучшить результат, используя вынесение общего множителя элементов строки, с последующим домножением в конце итерации. Для этого каждый из элементов строки раскладывается в произведение простых делителей.
Метод нахождения простых делителей числа дан в статье Факторизация числа.
В этом случае становятся ощутимо доступны для вычисления еще несколько порядков. (Все выводы даются на основе статистики только по матрицам с элементами -1,0,1,;  для больших величин результаты ухудшаются)

Благодаря этому становится возможным вычислить такие фантастические примеры как на нижепредставленном скрине, где n = 25, со временем вычисления 150 сек (105сек. в Версии 1.1). Однако, такие случаи редки.

 


 

Думаю, предложенные алгоритмы можно оптимизировать, улучшив показатели времени вычисления, читаемости кода и т.п. Однако, это дело времени и энтузиазма. А пока, кому интересно, прошу смотреть, эксперементировать, рационализировать!

Версия1.0. 
Рассчет определителя матрицы А прямым способом и методом Гаусса.
Для случая целочисленных элементов матрицы в методе Гаусса предусмотрена факторизация, с целью избежать ошибок переполения при больших порядках матрицы\больших значениях исходных элементов.
Факторизация проводится частично только для элементов преобразованной на каждом шаге матрицы.

Версия1.1. 
Добавлено сравнение результатов вычисления по методам Прямой - Гаусса, для отладки, с целью проверки правильности вычислений.
Факторизация в методе Гаусса проводится полностью для всех целых чисел, участвующих в вычислениях.

 

 


 

P.S.: Большой респект автору tezin за разработку консоли запросов //infostart.ru/public/72969/ , без которой бы данная работа не состоялась.

Определитель матрица

См. также

Метод Дугласа-Пойкера для эффективного хранения метрик

Математика и алгоритмы Платформа 1C v8.2 Конфигурации 1cv8 Россия Абонемент ($m)

На написание данной работы меня вдохновила работа @glassman «Переход на ClickHouse для анализа метрик». Автор анализирует большой объем данных, много миллионов строк, и убедительно доказывает, что ClickHouse справляется лучше PostgreSQL. Я же покажу как можно сократить объем данных в 49.9 раз при этом: 1. Сохранить значения локальных экстремумов 2. Отклонения от реальных значений имеют наперед заданную допустимую погрешность.

1 стартмани

30.01.2024    1756    stopa85    12    

33

Алгоритм симплекс-метода для решения задачи раскроя

Математика и алгоритмы Бесплатно (free)

Разработка алгоритма, построенного на модели симплекс-метода, для нахождения оптимального раскроя.

19.10.2023    4426    user1959478    50    

34

Регулярные выражения на 1С

Математика и алгоритмы Инструментарий разработчика Платформа 1С v8.3 Мобильная платформа Россия Абонемент ($m)

Что ж... лучше поздно, чем никогда. Подсистема 1С для работы с регулярными выражениями: разбор выражения, проверка на соответствие шаблону, поиск вхождений в тексте.

1 стартмани

09.06.2023    7464    4    SpaceOfMyHead    17    

56

Модель распределения суммы по базе

Математика и алгоритмы Платформа 1С v8.3 Россия Абонемент ($m)

Обычно под распределением понимают определение сумм пропорционально коэффициентам. Предлагаю включить сюда также распределение по порядку (FIFO, LIFO) и повысить уровень размерности до 2-х. 1-ое означает, что распределение может быть не только пропорциональным, но и по порядку, а 2-ое - это вариант реализации матричного распределения: по строкам и столбцам. Возможно вас заинтересует также необычное решение этой задачи через создание DSL на базе реализации текучего интерфейса

1 стартмани

21.03.2022    7856    7    kalyaka    11    

44

Изменения формата файлов конфигурации (CF) в 8.3.16

Математика и алгоритмы Платформа 1С v8.3 Бесплатно (free)

Дополнение по формату файлов конфигурации (*.cf) в версии 8.3.16.

16.12.2021    4446    fishca    13    

36

Интересная задача на Yandex cup 2021

Математика и алгоритмы Бесплатно (free)

Мое решение задачи на Yandex cup 2021 (frontend). Лабиринт. JavaScript.

12.10.2021    8843    John_d    73    

46

Механизм анализа данных. Кластеризация.

Математика и алгоритмы Анализ учета Платформа 1С v8.3 Анализ и прогнозирование Бесплатно (free)

Подробный разбор, с примером использования, встроенного механизма кластеризации 1С.

31.08.2021    7808    dusha0020    8    

70
Комментарии
В избранное Подписаться на ответы Сортировка: Древо развёрнутое
Свернуть все
1. WKBAPKA 214 28.11.13 13:13 Сейчас в теме
всегда даю плюсы за не понятные мне вещи :)
y22-k; bulpi; cleaner_it; +3 Ответить
2. bayce 45 01.03.14 22:19 Сейчас в теме
(1) WKBAPKA,
полностью с вами согласен
3. jigourt 31 01.03.14 22:47 Сейчас в теме
(1) WKBAPKA, (2) bayce, программисты не знающие математику? ))
LuxVeritatis; pumbaE; +2 Ответить
4. pumbaE 01.03.14 23:19 Сейчас в теме
(3) jigourt, программисты ли?
5. jigourt 31 01.03.14 23:35 Сейчас в теме
(4) pumbaE, ну я же спросил, если бы был уверен, что программисты, тогда утверждал бы )
6. LuxVeritatis 18.11.14 15:23 Сейчас в теме
В свое время делал на С++, ввод/вывод в командной строке. Потом кому-то помогал делать на Делфи. У одной знакомой видел в Excele. Нет, круто конечно, но бесполезно
7. zaxarovsky 111 18.11.14 15:41 Сейчас в теме
(6) Obscurus, ну может пригодится кому игрушечка :)
Оставьте свое сообщение