Ленточный определитель

[Andrey_Kireew]

Известно, что определитель трёхдиагональной матрицы (определитель Якоби) находится как сумма произведения элементов главной диагонали и всех возможных произведений, получаемых заменой соседних пар элементов главной диагонали боковыми элементами

$$det\begin{pmatrix} a_1&b_1&0 \\ -c_2&a_2&b_2\\ 0&-c_3&a_3 \end{pmatrix}=a_1\cdot a_2 \cdot a_3 +b_1\cdot c_2 \cdot a_3 +a_1\cdot b_2 \cdot c_3 $$

вопрос: как по аналогии вычислить определитель с лентой, состоящей более чем из трёх элементов?

[Andrey_Kireew]

Подскажите хотя бы как оценить количество слагаемых в зависимости от размера матрицы и ширины ленты

[maxmatem]

Andrey_Kireew

Почитайте там хорошо описан ваш вопрос.

http://www.apmath.spbu.ru/ru/staff/utes ... lg0407.pdf

Теорема 9.3 и после нее идут рассуждения про применение разностных уравнений к вычислению ленточных определителей

[Andrey_Kireew]

спасибо
но к сожалению у меня на диагоналях не одинаковые элементы, разностные уравнения тут не помогут

[Евгений Машеров]

Привести к трёхдиагональному виду ортогональными преобразованиями. Далее считать, как приведено...
А можно проявить пустое любопытство - зачем ныне определитель считать принято?

[Andrey_Kireew]

Евгений Машеров в сообщении #1076992 писал(а):

А можно проявить пустое любопытство - зачем ныне определитель считать принято?

необходимо выполнить обращение символьной матрицы (элементы - линейные многочлены)
элементарные преобразования матрицы приводят к дробным функциям, знаменатель которых как раз и есть её определитель
если его полностью раскрыть - получаются очень громоздкие многомерные полиномы, с которыми просто невозможно работать, поэтому думаю представить его в виде суммы произведений линейных многочленов, но пока не пойму как это лучше сделать
для произвольной матрицы такая сумма имеет $n!$ членов, но для ленточной матрицы очевидно оно значительно меньше

что касается приведения матрицы к верхнетреугольной путём элементарных преобразований, то это в итоге всё равно приведёт к полиному определителя в развёрнутом виде, так как этот полином неприводимый (по крайней мере я пришел к такому выводу), следовательно его нельзя представить как произведение многочленов меньшей степени

[Евгений Машеров]

Ну, оценил бы я так: всего в выражении для определителя n! слагаемых. Но в ленточном матрице полуширины l (в смысле у неё l ненулевых диагоналей выше и l ниже главной) все элементы, кроме $m=n+2l\frac {(n-1)+(n-l)} 2=n+l(2n-l-1)$ нулевые. Вероятность того, что случайно выбранный множитель в случайно выбранном слагаемом определителя "гарантированный ноль", и, следовательно, это слагаемое можно, не вычисляя, отбросить, равно $p=\frac {n^2-m} {n^2}$, а что все сомножители в данном слагаемом не являются "внеленточными нулями" - $(1-p)^n=\frac{m^n}{n^{2n}}$
Оценка, похоже, довольно грубая, поскольку тут никак не "независимые испытания". Для случая n=10 и l=5 получаем уменьшение с 3628800 слагаемых до примерно 389639, для l=2 (пятидиагональная матрица) - до примерно 987.
Ещё один способ (если элементы - полиномы не выше первой степени от одной и той же переменной) выглядит так: элементы обратной матрицы это алгебраические дополнения элементов транспонированной матрицы, делённые на определитель. По построению и те, и те полиномы степени не выше n. Подставляем в качестве аргумента x полиномов n разных чисел (не обязательно, но удобно равноотстоящих), получаем для каждого значения аргумента $n^2$ значений алгебраических дополнений и значение определителя. Строим $n^2+1$ интерполяционных полиномов (для каждого элемента алгебраического дополнения и для определителя), получаем решение в виде отношения полинома для алгебраического дополнения и полинома для определителя.

[B@R5uk]

Я в лоб посчитал первые восемь определителей вашего вида. Число слагаемых в них образует последовательность Фибоначчи. Может быть это не случайно и это можно как-то обосновать? Я даже абсолютно уверен, что это можно обосновать по индукции.

[Sonic86]

B@R5uk в сообщении #1077297 писал(а):

Я в лоб посчитал первые восемь определителей вашего вида. Число слагаемых в них образует последовательность Фибоначчи. Может быть это не случайно и это можно как-то обосновать? Я даже абсолютно уверен, что это можно обосновать по индукции.

Легко: раскладываем ленточный определитель $n$-го порядка ($LO(n)$) по последней строке или столбцу, получаем после сокращения на еще одну строку: $LO(n)=LO(n-1)+LO(n-2)$. ($LO$ - не функция)

Если бы Вы не написали, я бы и не заметил

[Andrey_Kireew]

Sonic86 в сообщении #1077330 писал(а):

B@R5uk в сообщении #1077297 писал(а):

$LO(n)=LO(n-1)+LO(n-2)$. ($LO$ - не функция)

Если бы Вы не написали, я бы и не заметил

т.е. определяем количество слагаемых в определителе $l\times l$ как $l!$, затем как то находим кол-во слагаемых в определителе $(l+1)\times(l+1)$ (у которого только два нуля - в верхнем правом и нижнем левом углах), а количество слагаемых в определителях большего размера уже находим по рекуррентной формуле,
я правильно понимаю?

-- 27.11.2015, 18:54 --

Евгений Машеров в сообщении #1077280 писал(а):

Ещё один способ (если элементы - полиномы не выше первой степени от одной и той же переменной) выглядит так: элементы обратной матрицы это алгебраические дополнения элементов транспонированной матрицы, делённые на определитель. По построению и те, и те полиномы степени не выше n. Подставляем в качестве аргумента x полиномов n разных чисел (не обязательно, но удобно равноотстоящих), получаем для каждого значения аргумента $n^2$ значений алгебраических дополнений и значение определителя. Строим $n^2+1$ интерполяционных полиномов (для каждого элемента алгебраического дополнения и для определителя), получаем решение в виде отношения полинома для алгебраического дополнения и полинома для определителя.

а зачем делать интерполяцию, если эти полиномы можно и так найти при обычном вычислении определителя?
я их вычислял в maple для матрицы $8\times 8$ и 5 ненулевых элементов в строке,
получилось примерно 200000 мономов, мне кажется интерполяцию такими большими полиномами будет выполнить весьма проблематично

[Евгений Машеров]

Для Вашей матрицы будет 64 полинома 8 порядка для алгебраических дополнений и ещё один 8 порядка для определителя.

[Andrey_Kireew]

Евгений Машеров в сообщении #1077409 писал(а):

Для Вашей матрицы будет 64 полинома 8 порядка для алгебраических дополнений и ещё один 8 порядка для определителя

так будет только если они одномерные, но этот случай не представляет интераса

[Sonic86]

Andrey_Kireew в сообщении #1077379 писал(а):

т.е. определяем количество слагаемых в определителе $l\times l$ как $l!$

да, для $l=2;3$

Andrey_Kireew в сообщении #1077379 писал(а):

затем как то находим кол-во слагаемых в определителе $(l+1)\times(l+1)$ (у которого только два нуля - в верхнем правом и нижнем левом углах)

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

Andrey_Kireew в сообщении #1077379 писал(а):

а количество слагаемых в определителях большего размера уже находим по рекуррентной формуле,
я правильно понимаю?

да

(Оффтоп)

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

[Andrey_Kireew]

я сразу что то не сообразил, но в действительности

$$LO(n)=LO(n-1)+LO(n-2)$$

это не ответ на мой вопрос, так как формула справедлива только для трёхдиагональной матрицы, и об этом подробно написано в материале http://www.apmath.spbu.ru/ru/staff/utes ... lg0407.pdf, любезно предоставленном maxmatem

вопрос про определители с большим числом ненулевых диагоналей, в последней строке у меня не 2 а от 5 до 7 элементов

[Sonic86]

Andrey_Kireew в сообщении #1077667 писал(а):

вопрос про определители с большим числом ненулевых диагоналей, в последней строке у меня не 2 а от 5 до 7 элементов

(я, правда, не очень понимаю, как это у Вас ширина ленты меняется в последней строке...)
Если $LO(n)$ - число слагаемых в определителе ленточной матрицы с шириной ленты $q=2k+1$, то из однократного разложения по строке получаем оценку $LO(n)\leqslant kLO(n-1)\leqslant k^{n-k} k!$. Для получения более точной оценки нужна мотивация посильнее. Для $q=5$ выписать у меня в точности пока не получилось - там кроме 5-ленточного определителя добавляется еще один 5-ленточный с одним выколотым элементом.