Я же предлагаю не случайно выбрать начальный набор точек отстоящих друг от друга. Это позволяет сократить время в разы и ошибку до 37-40%
Во-первых, никаких разов тут нет. Вы выкидываете всего 3 итерации из N. Это ускорение на какие-то проценты. Быстрее у вас, потому что вы перебираете только куда вставлять очередную (случайную) точку, когда как в cheapest insertion heuristic перебирают еще и точку и потом также перебирают, куда ее вставлять.
Во-вторых, сокращение ошибки зависит от того, как вы выберете "скелет". Вы просто берете какие-то "по краям диапазона" не очень это формализовав. Никаких рассуждений на тему почему это как-то помогает вы не привели.
Это позволяет сократить время в разы и ошибку до 37-40%
Голословное утверждение.
и как следствие коррекция скелета
Первый раз это словосочетание вижу. В статье никакой коррекции скелета нет. Вы про то, что вы добавляете новую точку в список, который был скелетом? Тогда тоже самое есть у cheapest insertion heuristic.
замыкание маршрута или не ухудшает ошибку либо увеличивает ее на 3-5%.
Опять же, голословное утверждение.
Еще раз, ваш метод отличается от известного в двух местах:
1) вы начинаете не с 1 а с 4 точек.
2) Вы перебираете только куда вставлять, а не еще и что.
Я уверен, что пункт 2 делает ваш метод гораздо хуже Cheapest insertion heuristic, потому что доказательство границы ошибки в 50% не применимо к вашему методу.
Статья тоже о библиотеке, но там выводится и объясняется алгоритм, которой фиг где нагуглишь. Приведенный код относится к реализации, а не к использованию библиотеки.
Главная же проблема в том, что на Википедии нет доказательства
Если бы я просто описал уже расписанный в википедии алгоритм - то да, этой статье было бы не место на хабре. Но нет, эта статья о доказательстве, которого в свободном доступе в интернете на тот момент вообще нигде и не было. Эта статья выросла из спора в комментариях. Мне тогда не удалось найти ни одного источника, чтобы убедить оппонента, пришлось публиковать доказательство самому.
Получается ваши статьи это буквально реферат студента который разобрался в конкретном алгоритме
Если бы у вас был хотя бы реферат по алгоритму разложения на LU матрицы, то это было бы в тысячу раз лучше. Но до моей статьи все равно было бы далеко, потому что это уникальный материал.
Остальные мои статьи про алгоритмы расписывают далеко не попсовые алгоритмы, которые есть даже на википедии. Там или разбор задач, решения которых в интернете вообще нет, или оно встречается только на считанных олимпиадных сайтах, но при этом фокус статьи на личном опыте применения в боевых условиях в индустрии. Это не тупо очередной разбор очередной задачи, это личный опыт.
Одна статья, кстати, как раз про библиотеку pet-проект. Вот вам пример, как надо делать.
Во-первых, там не "курсовое" описание проекта в академическом пассивном залоге и со списком литературы, с парой примеров применения, а объяснение алгоритма и его вывод. И этого алгоритма в википедии нет. Он, конечно, не новый, но встречается только в специальной литературе.
У вас же статья в хабах "алгоритмы" и "математика", а из алгоритмов и математики там только упоминание стандартных алгоритмов, даже без их описания или доказательства, да одна единственная математическая формула, скопированная из википедии.
Во-вторых, у меня там как раз "промышленная", готовая к применению библиотека, без прямых аналогов для такого же случая. И на библиотеку есть ссылочка и все. Описание ее интерфейса и примеры использования должны быть в readme.md. А не в статье на хабре, если только не в хабе "я пиарюсь". Это не алгоритмы и не математика.
А какая временная сложность у предподсчета и у самих запросов? Я правильно понимаю, что там O(n log n) на предподсчет и O(log n) на запросы из-за дерева, но скорость достигается за счет SIMD и впихивания основных структур в кэш процессора?
Как оно сравнивается с O(n) предподсчетом и O(1) запросах в оффлайн алгоритме о котором я писал тут?
ГА обрабатывает этот случай за 517 секунд. С ошибкой 24,7% (так себе точность мягко говоря).
Кстати, откуда ошибка взята? Оптимальное решение для теста уже известно? Как долго и чем оно искалось, интересно?
А собственно по алгориму: Это жадный алгоритм с очень простой эвристикой: добавляем точки по одной в список на позицию, минимизирующую длину пути. Такой простой алгоритм ожидаемо будет работать очень быстро. Но вот с оптимальностью ответа у него большие проблемы.
При чем есть более сильная версия, где перебирается не только, куда воткнуть вершину, а и какую из них добавлять. Каждый раз выбирается локально лучший вариант. И это даже гарантирует точность 50% (максимум 2 раза длинее чем в оптимальном пути).
Далее, в задачае коммивояжора обычно надо вернуться в изначальную точку, у вас это не учитывается, судя по коду и картинкам. Похоже, это сильно испортит вашу эвристику, ведь она локальна.
Edit: В литературе это называется cheapest insertion heuristic.
Да я думаю смысла нет это публиковать. Практического применения нет. Кому вдруг надо считать определитель матрицы при замене столбцов, они просто возьмут матричную лемму и все. Это очевидное решение если лемму знать, а она вылезает даже при поверхностном гуглеже. И считать обратную матрицу проще и понятнее.
Теоретической ценности тоже нет. Это буквально один маленький и весьма напрашивающийся шаг от очень широко известной леммы. Думаю, при попытке опубликовать в профильном журнале вам рецензенты источники и дадут.
Но если хотите, используйте на здоровье. Можете сослаться прям на комментарий в интернете со сноской, что другой источник не нашли.
Для повышения эффективности применяются специализированные структуры данных и алгоритмы с оптимизированной вычислительной сложностью.
Ну вот вообще не интересно читать про АПИ вашей библиотеки. Это должно быть в документации а не статье на хабре. Тем более в хабе "математика".
Вместо этого было бы интересно почитать собственно про быстрые алгоритмы пересечения объектов. Что за структуры данных и при каких условиях используются. Какие алгоритмы, какая у них сложность.
Как создание копий одного и того же объекта позволяет что-то соптимизировать? Ведь если структура данных пространственная, то она и должна быть привязана к пространству и разным копиям объектов, а не к их образцу? Вот об этом стоит писать статью, а не о том, какие у вас функции есть.
Нет, никакой проверки на ошибки нет. Иногда есть только фильтр здравого смысла, т.е. что-то совсем скандальное и фриковое печатать не будут, но не потому, что там ошибки, а потому что это слишком очевидный бред и может создать слишком много негативной публичности. Но и это редкость. Большинство нерецензируемых журналов - тупо заработок на альтернативщиках. Печатай что хочешь, только денюжку занеси.
Странно, я думал, что там в итоге должны те же скорости получатся. Но оказывается нет.
И вообще задача одновременного столкновения нескольких тел неразрешима. Там надо найти N импульсов, а у нас всего 2 уравнения: сохранение энергии и импульса.
И проблема в том, что при попарных столкновениях мы считаем что импульс сохраняется в паре, но при троичном столкновении импульсом обмениваются все три тела сразу, поэтому применять формулы для двух тел нельзя.
А почему при столкновении нескольких объектов нельзя их обрабатывать попарно? Просто считать, что одна пара столкнулась на епсилон микросекунд раньше других? Ведь в пределе должно получиться тоже самое.
Надо только не двигать атомы, пока все столкновения не разрешатся.
Вот выхлоп gemini с доказательством обобщенной формулы. Я все проверил, все рассуждения правильные:
1. Введение обозначений и постановка задачи
Пусть дана невырожденная квадратная матрица .
Мы хотим найти определитель новой матрицы , в которой изменены k столбцов.
Пусть — индексы заменяемых столбцов.
Пусть — новые векторы, которые встанут на эти места.
Обозначим через оригинальный j-й столбец матрицы A.
Мы можем представить как сумму исходной матрицы и матрицы ранга $k$:
Где :
Матрица V содержит стандартные базисные векторы для выбора нужных столбцов: ее s-й столбец равен .
Матрица U содержит приращения столбцов: ее s-й столбец равен .
Тогда произведение — это матрица , у которой в столбцах с индексами стоят векторы , а остальные столбцы нулевые.
2. Матричная лемма об определителях
Применим лемму об определителе (Matrix Determinant Lemma) для матрицы A и возмущений U, V:
Наша задача сводится к вычислению определителя матрицы размерности .
3. Вычисление элементов матрицы M и сокращение
Рассмотрим элемент матрицы , стоящий на пересечении r-й строки и s-го столбца (где ).
Строки матрицы — это транспонированные базисные векторы .
Столбцы матрицы U — это векторы приращений .
Поскольку — это -й столбец самой матрицы A, то по определению обратной матрицы .
Тогда второе слагаемое превращается во внутреннее произведение двух базисных векторов, что дает символ Кронекера:
Получаем:
Теперь подставим это в матрицу M:
Единицы на диагонали из идеально сократились с , возникшими из-за вычитания оригинальных столбцов.
4. Переход к определителям с одним измененным столбцом
Разберем выражение .
Умножение просто "вытаскивает" -ю строку из матрицы .
Вспомним формулу элементов обратной матрицы через алгебраические дополнения (кофакторы). Если C — матрица алгебраических дополнений для A, то
.
Значит, элемент обратной матрицы равен:
Элемент i из -й строки матрицы — это .
Умножим эту строку на вектор :
Сумма представляет собой классическое разложение определителя по
-му столбцу. Причем элементы этого столбца берутся из вектора , а все алгебраические дополнения — из оригинальной матрицы A.
Это в точности равно определителю матрицы A, у которой только один-й столбец заменен на вектор
Обозначим такую матрицу как .
5. Итоговая формула
Матрица M размерности полностью состоит из элементов вида
.
Вынесем скаляр из каждой из k строк (или столбцов) матрицы M при вычислении ее определителя:
Обозначим эту матрицу определителей как , где .
Подставляем в исходную лемму:
Итоговая формула:
Где D — это матрица , элемент которой равен определителю исходной матрицы A, в которой -й столбец заменен на новый вектор .
Примечание: Обрати внимание, что элементы вне главной диагонали матрицы D — это определители матриц "смешанных" замен (мы ставим вектор , предназначенный для s-го столбца, на место r-го столбца).
Нет это прямое обобщение вашей формулы. При подстановке k=2 она и получается.Определитель матрицы с k замененными столбцами пересчитывается через определители матрицы, где один из изменяемых столбцов заменен на один из новых столбцов.
Источников не знаю, сам только что придумал. Думаю они где-то есть, но найти не могу. Вот берем тот вывод вашей формулы из матричной леммы, который я привел выше. И тупо вместо замены 2 столбцов заменяем 3. Матрицы V и U будут n x 3 а не n x 2. Опять же V^T= (I|0), а U - содержит 3 столбца q-A_i, q'-A_j, q''-A_k.
Расписываем матричную лемму, делаем те же самые замены A^-1 на миноры и оттуда матрица 3x3 из леммы, от которой надо подсчитать определитель, получится состоящая из F_i(q_j)/det(A). 1/det(A) выносим из определителя, оно вылезет со степенью 3, одна степень сократится с det(A) из матричной леммы.
Матрица B 2x2 состоит из 4 чисел: F_i(q), F_j(q), F_i(q'), F_j(q'). Ее определитель как раз даст вашу формулу F_i(q) * F_j(q') - F_j(q) * F_i(q'). А справа как раз будет F_ij(q,q') det(A).
Т.е. при обобщении тождества на замену 3 столбцов будет F_ijk(q,q',q'') det(A)^2 = F_i(q)F_j(q')F_k(q'') + F_j(q)F_k(q')F_i(q'') + ... - F_k(q)F_j(q')F_k(q'') - 6 слагаемых как в определители матрицы 3x3.
Кстати, на заметку. Точно так же выводится еще более обобщенное тождество: Пусть матрица k x k (в позиции ij сидит определитель матрицы A, где i-ый столбец заменен на j-ый вектор q). Тогда
Т.е. определитель A при замене k столбцов можно пересчитать через определители A при замене каждого из столбцов на один из новых.
В случае k=2 det(B) как раз дает вашу штуку вида AB-CD.
Для k=1 получается тривиальное тождество F_i(q) = F_i(q).
На практике это даст алгоритм пересчета определителя при замене любых k столбцов за O(k^3n) при O(n^3) предподсчете.
Т.к. когда выводил свои теоремы - ничего не знал о матричной лемме
Раз уж вы адепт ИИ, спросили бы у него задачу быстро пересчитать определитель матрицы, оно сразу выдает метод через лемму, заодно и ссылки на нее. В 50% случаев тупит и говорит, что оно работает за O(n^2), хотя на самом деле там O(n).
“очень похожи на высчитывание определителя через миноры” В формуле из теоремы 1 миноры вообще не используются. В формуле из теоремы 3 - также.
Как не используются? Как вы считаете F_i(q)? Это разложение определителя по столбцу. Коэффициенты перед q_i какие? Миноры же и есть. Ну там какие-то минусы где-то еще расставить надо, но это не принципиально.
В теореме 3 разложение на миноры второго порядка будет.
Во-первых, никаких разов тут нет. Вы выкидываете всего 3 итерации из N. Это ускорение на какие-то проценты. Быстрее у вас, потому что вы перебираете только куда вставлять очередную (случайную) точку, когда как в cheapest insertion heuristic перебирают еще и точку и потом также перебирают, куда ее вставлять.
Во-вторых, сокращение ошибки зависит от того, как вы выберете "скелет". Вы просто берете какие-то "по краям диапазона" не очень это формализовав. Никаких рассуждений на тему почему это как-то помогает вы не привели.
Голословное утверждение.
Первый раз это словосочетание вижу. В статье никакой коррекции скелета нет. Вы про то, что вы добавляете новую точку в список, который был скелетом? Тогда тоже самое есть у cheapest insertion heuristic.
Опять же, голословное утверждение.
Еще раз, ваш метод отличается от известного в двух местах:
1) вы начинаете не с 1 а с 4 точек.
2) Вы перебираете только куда вставлять, а не еще и что.
Я уверен, что пункт 2 делает ваш метод гораздо хуже Cheapest insertion heuristic, потому что доказательство границы ошибки в 50% не применимо к вашему методу.
Что? Вот та простыня чуть выше, где я по пунктам опровергаю ваш тезис о моих статьях - это "нечего сказать по существу"?
Вот уж похоже, это вам "нечего сказать" и вы скатываетесь в игнорирование аргументов.
Вот вам еще пример, как надо: https://habr.com/ru/articles/1055008/
Статья тоже о библиотеке, но там выводится и объясняется алгоритм, которой фиг где нагуглишь. Приведенный код относится к реализации, а не к использованию библиотеки.
Про решето Эратосфена, я же там в статье написал:
Если бы я просто описал уже расписанный в википедии алгоритм - то да, этой статье было бы не место на хабре. Но нет, эта статья о доказательстве, которого в свободном доступе в интернете на тот момент вообще нигде и не было. Эта статья выросла из спора в комментариях. Мне тогда не удалось найти ни одного источника, чтобы убедить оппонента, пришлось публиковать доказательство самому.
Если бы у вас был хотя бы реферат по алгоритму разложения на LU матрицы, то это было бы в тысячу раз лучше. Но до моей статьи все равно было бы далеко, потому что это уникальный материал.
Остальные мои статьи про алгоритмы расписывают далеко не попсовые алгоритмы, которые есть даже на википедии. Там или разбор задач, решения которых в интернете вообще нет, или оно встречается только на считанных олимпиадных сайтах, но при этом фокус статьи на личном опыте применения в боевых условиях в индустрии. Это не тупо очередной разбор очередной задачи, это личный опыт.
Одна статья, кстати, как раз про библиотеку pet-проект. Вот вам пример, как надо делать.
Во-первых, там не "курсовое" описание проекта в академическом пассивном залоге и со списком литературы, с парой примеров применения, а объяснение алгоритма и его вывод. И этого алгоритма в википедии нет. Он, конечно, не новый, но встречается только в специальной литературе.
У вас же статья в хабах "алгоритмы" и "математика", а из алгоритмов и математики там только упоминание стандартных алгоритмов, даже без их описания или доказательства, да одна единственная математическая формула, скопированная из википедии.
Во-вторых, у меня там как раз "промышленная", готовая к применению библиотека, без прямых аналогов для такого же случая. И на библиотеку есть ссылочка и все. Описание ее интерфейса и примеры использования должны быть в readme.md. А не в статье на хабре, если только не в хабе "я пиарюсь". Это не алгоритмы и не математика.
А какая временная сложность у предподсчета и у самих запросов? Я правильно понимаю, что там O(n log n) на предподсчет и O(log n) на запросы из-за дерева, но скорость достигается за счет SIMD и впихивания основных структур в кэш процессора?
Как оно сравнивается с O(n) предподсчетом и O(1) запросах в оффлайн алгоритме о котором я писал тут?
Осталась самая мелочь: доказать, что всегда наткнешься на 2^N.
Кстати, откуда ошибка взята? Оптимальное решение для теста уже известно? Как долго и чем оно искалось, интересно?
А собственно по алгориму: Это жадный алгоритм с очень простой эвристикой: добавляем точки по одной в список на позицию, минимизирующую длину пути. Такой простой алгоритм ожидаемо будет работать очень быстро. Но вот с оптимальностью ответа у него большие проблемы.
Во-первых, это известная эвристика с 1974 года: https://www2.isye.gatech.edu/~mgoetsch/cali/VEHICLE/TSP/TSP011__.HTM
При чем есть более сильная версия, где перебирается не только, куда воткнуть вершину, а и какую из них добавлять. Каждый раз выбирается локально лучший вариант. И это даже гарантирует точность 50% (максимум 2 раза длинее чем в оптимальном пути).
Далее, в задачае коммивояжора обычно надо вернуться в изначальную точку, у вас это не учитывается, судя по коду и картинкам. Похоже, это сильно испортит вашу эвристику, ведь она локальна.
Edit: В литературе это называется cheapest insertion heuristic.
Да я думаю смысла нет это публиковать. Практического применения нет. Кому вдруг надо считать определитель матрицы при замене столбцов, они просто возьмут матричную лемму и все. Это очевидное решение если лемму знать, а она вылезает даже при поверхностном гуглеже. И считать обратную матрицу проще и понятнее.
Теоретической ценности тоже нет. Это буквально один маленький и весьма напрашивающийся шаг от очень широко известной леммы. Думаю, при попытке опубликовать в профильном журнале вам рецензенты источники и дадут.
Но если хотите, используйте на здоровье. Можете сослаться прям на комментарий в интернете со сноской, что другой источник не нашли.
В связи с этим вспомнилась история, как неизвестный аноним с форчана доказал какую-то комбинаторную теорему, обсуждая как правильно смотреть аниме: https://www.wired.com/story/how-an-anonymous-4chan-post-helped-solve-a-25-year-old-math-puzzle/
Ну вот вообще не интересно читать про АПИ вашей библиотеки. Это должно быть в документации а не статье на хабре. Тем более в хабе "математика".
Вместо этого было бы интересно почитать собственно про быстрые алгоритмы пересечения объектов. Что за структуры данных и при каких условиях используются. Какие алгоритмы, какая у них сложность.
Как создание копий одного и того же объекта позволяет что-то соптимизировать? Ведь если структура данных пространственная, то она и должна быть привязана к пространству и разным копиям объектов, а не к их образцу? Вот об этом стоит писать статью, а не о том, какие у вас функции есть.
Нет, никакой проверки на ошибки нет. Иногда есть только фильтр здравого смысла, т.е. что-то совсем скандальное и фриковое печатать не будут, но не потому, что там ошибки, а потому что это слишком очевидный бред и может создать слишком много негативной публичности. Но и это редкость. Большинство нерецензируемых журналов - тупо заработок на альтернативщиках. Печатай что хочешь, только денюжку занеси.
Странно, я думал, что там в итоге должны те же скорости получатся. Но оказывается нет.
И вообще задача одновременного столкновения нескольких тел неразрешима. Там надо найти N импульсов, а у нас всего 2 уравнения: сохранение энергии и импульса.
И проблема в том, что при попарных столкновениях мы считаем что импульс сохраняется в паре, но при троичном столкновении импульсом обмениваются все три тела сразу, поэтому применять формулы для двух тел нельзя.
А почему при столкновении нескольких объектов нельзя их обрабатывать попарно? Просто считать, что одна пара столкнулась на епсилон микросекунд раньше других? Ведь в пределе должно получиться тоже самое.
Надо только не двигать атомы, пока все столкновения не разрешатся.
Вот выхлоп gemini с доказательством обобщенной формулы. Я все проверил, все рассуждения правильные:
1. Введение обозначений и постановка задачи
Пусть дана невырожденная квадратная матрица
.
Мы хотим найти определитель новой матрицы
, в которой изменены k столбцов.
Пусть
— индексы заменяемых столбцов.
Пусть
— новые векторы, которые встанут на эти места.
Обозначим через
оригинальный j-й столбец матрицы A.
Мы можем представить
как сумму исходной матрицы и матрицы ранга $k$:
Где
:
Матрица V содержит стандартные базисные векторы для выбора нужных столбцов: ее s-й столбец равен
.
Матрица U содержит приращения столбцов: ее s-й столбец равен
.
Тогда произведение
— это матрица 
, у которой в столбцах с индексами 
стоят векторы 
, а остальные столбцы нулевые.
2. Матричная лемма об определителях
Применим лемму об определителе (Matrix Determinant Lemma) для матрицы A и возмущений U, V:
Наша задача сводится к вычислению определителя матрицы
размерности 
.
3. Вычисление элементов матрицы M и сокращение
Рассмотрим элемент матрицы
, стоящий на пересечении r-й строки и s-го столбца (где 
).
Строки матрицы
— это транспонированные базисные векторы 
.
Столбцы матрицы U — это векторы приращений
.
Поскольку
— это 
-й столбец самой матрицы A, то по определению обратной матрицы 
.
Тогда второе слагаемое превращается во внутреннее произведение двух базисных векторов, что дает символ Кронекера:
Получаем:
Теперь подставим это в матрицу M:
Единицы на диагонали из
идеально сократились с 
, возникшими из-за вычитания оригинальных столбцов.
4. Переход к определителям с одним измененным столбцом
Разберем выражение
.
Умножение
просто "вытаскивает" 
-ю строку из матрицы 
.
Вспомним формулу элементов обратной матрицы через алгебраические дополнения (кофакторы). Если C — матрица алгебраических дополнений для A, то
Значит, элемент обратной матрицы равен:
Элемент i из
-й строки матрицы 
— это 
.
Умножим эту строку на вектор
:
Сумма
представляет собой классическое разложение определителя по
-му столбцу. Причем элементы этого столбца берутся из вектора 
, а все алгебраические дополнения 
— из оригинальной матрицы A.
Это в точности равно определителю матрицы A, у которой только один
-й столбец заменен на вектор 
Обозначим такую матрицу как
.
5. Итоговая формула
Матрица M размерности
полностью состоит из элементов вида
.
Вынесем скаляр
из каждой из k строк (или столбцов) матрицы M при вычислении ее определителя:
Обозначим эту матрицу определителей как
, где 
.
Подставляем
в исходную лемму:
Итоговая формула:
Где D — это матрица
, элемент которой 
равен определителю исходной матрицы A, в которой 
-й столбец заменен на новый вектор 
.
Примечание: Обрати внимание, что элементы вне главной диагонали матрицы D — это определители матриц "смешанных" замен (мы ставим вектор
, предназначенный для s-го столбца, на место r-го столбца).
Нет это прямое обобщение вашей формулы. При подстановке k=2 она и получается.Определитель матрицы с k замененными столбцами пересчитывается через определители матрицы, где один из изменяемых столбцов заменен на один из новых столбцов.
Источников не знаю, сам только что придумал. Думаю они где-то есть, но найти не могу. Вот берем тот вывод вашей формулы из матричной леммы, который я привел выше. И тупо вместо замены 2 столбцов заменяем 3. Матрицы V и U будут n x 3 а не n x 2. Опять же V^T= (I|0), а U - содержит 3 столбца q-A_i, q'-A_j, q''-A_k.
Расписываем матричную лемму, делаем те же самые замены A^-1 на миноры и оттуда матрица 3x3 из леммы, от которой надо подсчитать определитель, получится состоящая из F_i(q_j)/det(A). 1/det(A) выносим из определителя, оно вылезет со степенью 3, одна степень сократится с det(A) из матричной леммы.
Чуть позже скину формализованное доказательство
Матрица B 2x2 состоит из 4 чисел: F_i(q), F_j(q), F_i(q'), F_j(q'). Ее определитель как раз даст вашу формулу F_i(q) * F_j(q') - F_j(q) * F_i(q'). А справа как раз будет F_ij(q,q') det(A).
Т.е. при обобщении тождества на замену 3 столбцов будет F_ijk(q,q',q'') det(A)^2 = F_i(q)F_j(q')F_k(q'') + F_j(q)F_k(q')F_i(q'') + ... - F_k(q)F_j(q')F_k(q'') - 6 слагаемых как в определители матрицы 3x3.
Кстати, на заметку. Точно так же выводится еще более обобщенное тождество:
(в позиции ij сидит определитель матрицы A, где i-ый столбец заменен на j-ый вектор q).
Пусть матрица k x k
Тогда
Т.е. определитель A при замене k столбцов можно пересчитать через определители A при замене каждого из столбцов на один из новых.
В случае k=2 det(B) как раз дает вашу штуку вида AB-CD.
Для k=1 получается тривиальное тождество F_i(q) = F_i(q).
На практике это даст алгоритм пересчета определителя при замене любых k столбцов за O(k^3n) при O(n^3) предподсчете.
Раз уж вы адепт ИИ, спросили бы у него задачу быстро пересчитать определитель матрицы, оно сразу выдает метод через лемму, заодно и ссылки на нее. В 50% случаев тупит и говорит, что оно работает за O(n^2), хотя на самом деле там O(n).
Как не используются? Как вы считаете F_i(q)? Это разложение определителя по столбцу. Коэффициенты перед q_i какие? Миноры же и есть. Ну там какие-то минусы где-то еще расставить надо, но это не принципиально.
В теореме 3 разложение на миноры второго порядка будет.
Нет же. Наверняка эта формула опубликована еще в прошлом веке.
Там же тоже надо лишь скалярно умножить вектора q, q' на 2 строки обратной матрицы. Будь там числа или символы - все так же как в вашем методе.