2014 dxdy logo

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

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


Правила форума


В этом разделе нельзя создавать новые темы.

Если Вы хотите задать новый вопрос, то не дописывайте его в существующую тему, а создайте новую в корневом разделе "Помогите решить/разобраться (М)".

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

Не ищите на этом форуме халяву, правила запрещают участникам публиковать готовые решения стандартных учебных задач. Автор вопроса обязан привести свои попытки решения и указать конкретные затруднения.

Обязательно просмотрите тему Правила данного раздела, иначе Ваша тема может быть удалена или перемещена в Карантин, а Вы так и не узнаете, почему.



Начать новую тему Ответить на тему На страницу 1, 2  След.
 
 Ленточный определитель
Сообщение26.11.2015, 09:16 


07/10/15

2400
Известно, что определитель трёхдиагональной матрицы (определитель Якоби) находится как сумма произведения элементов главной диагонали и всех возможных произведений, получаемых заменой соседних пар элементов главной диагонали боковыми элементами
$$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 


07/10/15

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

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


15/08/09
1437
МГУ
Andrey_Kireew

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

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

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

 Профиль  
                  
 
 Re: Ленточный определитель
Сообщение26.11.2015, 13:28 


07/10/15

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

 Профиль  
                  
 
 Re: Ленточный определитель
Сообщение26.11.2015, 14:30 
Заслуженный участник
Аватара пользователя


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

 Профиль  
                  
 
 Re: Ленточный определитель
Сообщение26.11.2015, 21:28 


07/10/15

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


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

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

 Профиль  
                  
 
 Re: Ленточный определитель
Сообщение27.11.2015, 11:17 
Заслуженный участник
Аватара пользователя


11/03/08
7938
Москва
Ну, оценил бы я так: всего в выражении для определителя 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 
Аватара пользователя


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

 Профиль  
                  
 
 Re: Ленточный определитель
Сообщение27.11.2015, 14:55 
Заслуженный участник


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

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

 Профиль  
                  
 
 Re: Ленточный определитель
Сообщение27.11.2015, 17:47 


07/10/15

2400
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 
Заслуженный участник
Аватара пользователя


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

 Профиль  
                  
 
 Re: Ленточный определитель
Сообщение27.11.2015, 20:18 


07/10/15

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


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

 Профиль  
                  
 
 Re: Ленточный определитель
Сообщение27.11.2015, 20:36 
Заслуженный участник


08/04/08
8519
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 


07/10/15

2400
я сразу что то не сообразил, но в действительности $$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 
Заслуженный участник


08/04/08
8519
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