gifts2017

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

Опубликовал Андрей Захаров (zaxarovsky) в раздел Программирование - Практика программирования

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

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

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

Описание

Исходная матрица А порядка 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 за разработку консоли запросов http://infostart.ru/public/72969/ , без которой бы данная работа не состоялась.

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

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

См. также

Подписаться Добавить вознаграждение

Комментарии

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