2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




На страницу 1, 2  След.
 
 Ленточный определитель
Сообщение26.11.2015, 09:16 
Известно, что определитель трёхдиагональной матрицы (определитель Якоби) находится как сумма произведения элементов главной диагонали и всех возможных произведений, получаемых заменой соседних пар элементов главной диагонали боковыми элементами
$$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 $$

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

 
 
 
 Re: Ленточный определитель
Сообщение26.11.2015, 11:19 
Подскажите хотя бы как оценить количество слагаемых в зависимости от размера матрицы и ширины ленты

 
 
 
 Re: Ленточный определитель
Сообщение26.11.2015, 11:37 
Аватара пользователя
Andrey_Kireew

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

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

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

 
 
 
 Re: Ленточный определитель
Сообщение26.11.2015, 13:28 
спасибо
но к сожалению у меня на диагоналях не одинаковые элементы, разностные уравнения тут не помогут

 
 
 
 Re: Ленточный определитель
Сообщение26.11.2015, 14:30 
Аватара пользователя
Привести к трёхдиагональному виду ортогональными преобразованиями. Далее считать, как приведено...
А можно проявить пустое любопытство - зачем ныне определитель считать принято?

 
 
 
 Re: Ленточный определитель
Сообщение26.11.2015, 21:28 
Евгений Машеров в сообщении #1076992 писал(а):
А можно проявить пустое любопытство - зачем ныне определитель считать принято?


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

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

 
 
 
 Re: Ленточный определитель
Сообщение27.11.2015, 11:17 
Аватара пользователя
Ну, оценил бы я так: всего в выражении для определителя 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$ интерполяционных полиномов (для каждого элемента алгебраического дополнения и для определителя), получаем решение в виде отношения полинома для алгебраического дополнения и полинома для определителя.

 
 
 
 Re: Ленточный определитель
Сообщение27.11.2015, 13:08 
Аватара пользователя
Я в лоб посчитал первые восемь определителей вашего вида. Число слагаемых в них образует последовательность Фибоначчи. Может быть это не случайно и это можно как-то обосновать? Я даже абсолютно уверен, что это можно обосновать по индукции.

 
 
 
 Re: Ленточный определитель
Сообщение27.11.2015, 14:55 
B@R5uk в сообщении #1077297 писал(а):
Я в лоб посчитал первые восемь определителей вашего вида. Число слагаемых в них образует последовательность Фибоначчи. Может быть это не случайно и это можно как-то обосновать? Я даже абсолютно уверен, что это можно обосновать по индукции.
Легко: раскладываем ленточный определитель $n$-го порядка ($LO(n)$) по последней строке или столбцу, получаем после сокращения на еще одну строку: $LO(n)=LO(n-1)+LO(n-2)$. ($LO$ - не функция)

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

 
 
 
 Re: Ленточный определитель
Сообщение27.11.2015, 17:47 
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 мономов, мне кажется интерполяцию такими большими полиномами будет выполнить весьма проблематично

 
 
 
 Re: Ленточный определитель
Сообщение27.11.2015, 19:09 
Аватара пользователя
Для Вашей матрицы будет 64 полинома 8 порядка для алгебраических дополнений и ещё один 8 порядка для определителя.

 
 
 
 Re: Ленточный определитель
Сообщение27.11.2015, 20:18 
Евгений Машеров в сообщении #1077409 писал(а):
Для Вашей матрицы будет 64 полинома 8 порядка для алгебраических дополнений и ещё один 8 порядка для определителя


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

 
 
 
 Re: Ленточный определитель
Сообщение27.11.2015, 20:36 
Andrey_Kireew в сообщении #1077379 писал(а):
т.е. определяем количество слагаемых в определителе $l\times l$ как $l!$
да, для $l=2;3$
Andrey_Kireew в сообщении #1077379 писал(а):
затем как то находим кол-во слагаемых в определителе $(l+1)\times(l+1)$ (у которого только два нуля - в верхнем правом и нижнем левом углах)
не просто как-то, а с помощью разложения определителя по строке или столбцу (нули в верхнем правом и нижнем левом углу роли не играют. Играет роль то, что в крайней строке всего 2 ненулевых элемента)
Andrey_Kireew в сообщении #1077379 писал(а):
а количество слагаемых в определителях большего размера уже находим по рекуррентной формуле,
я правильно понимаю?
да

(Оффтоп)

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

 
 
 
 Re: Ленточный определитель
Сообщение28.11.2015, 16:21 
я сразу что то не сообразил, но в действительности $$LO(n)=LO(n-1)+LO(n-2)$$ это не ответ на мой вопрос, так как формула справедлива только для трёхдиагональной матрицы, и об этом подробно написано в материале http://www.apmath.spbu.ru/ru/staff/utes ... lg0407.pdf, любезно предоставленном maxmatem

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

 
 
 
 Re: Ленточный определитель
Сообщение28.11.2015, 18:04 
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-ленточный с одним выколотым элементом.

 
 
 [ Сообщений: 24 ]  На страницу 1, 2  След.


Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group