2014 dxdy logo

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

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


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


Посмотреть правила форума



Начать новую тему Ответить на тему На страницу Пред.  1, 2, 3  След.
 
 Re: Алгоритм диагонализации матрицы
Сообщение04.08.2024, 18:45 
Заслуженный участник
Аватара пользователя


11/03/08
9874
Москва
B3LYP в сообщении #1648384 писал(а):
Какими свойствами должен обладать столбец справа, если на диагонали после диагонализации остаются только собственные значения?

Блистать своим отсутствием.

-- 04 авг 2024, 18:46 --

B3LYP в сообщении #1648384 писал(а):
И что такое вообще собственные значения матрицы?

Нет, это даже не "Если ничего не получается, прочтите, наконец, инструкцию!" Это сильнее. чем фаустпатрон Гёте.

-- 04 авг 2024, 18:47 --

dgwuqtj в сообщении #1648388 писал(а):
Ну и если вам нужны не эффективные алгоритмы, а просто что-то работающее, то можно всё считать как учат студентов: посчитать характеристический многочлен матрицы, найти его корни (а это численное решение полиномиальных уравнений!), потом собственно решение систем линейных уравнений.

Не, мне тоже приходилось троллить, но так виртуозно...

 Профиль  
                  
 
 Re: Алгоритм диагонализации матрицы
Сообщение05.08.2024, 19:31 


14/11/21
141
Цитата:
тоже приходилось троллить, но так виртуозно...


Тут надо бы еще разобраться, кто кого тут на самом деле троллит... Может так статься, что ТС :mrgreen:

 Профиль  
                  
 
 Re: Алгоритм диагонализации матрицы
Сообщение05.08.2024, 20:47 


07/01/23
415
Прочитал эту статью:

https://ru.wikipedia.org/wiki/Собственный_вектор

Пока к сожалению мало что понял. Но я вспомнил что в прошлом уже реализовывал диагонализацию матрицы методом Якоби (находил оси инерции и три момента инерции молекулы). Вроде это то что мне подходит, для симметричной матрицы метод Якоби вычисляет собственные значения. Только смущает такой момент: алгоритм Якоби итерационный, значит он считается заведомо дольше, чем алгоритм с прибавлением строк в оп. Это так и должно быть? Т.е. найти быстрый неитерационный алгоритм для исходной задачи сложновато?

 Профиль  
                  
 
 Re: Алгоритм диагонализации матрицы
Сообщение05.08.2024, 20:51 
Заслуженный участник


07/08/23
1055
B3LYP в сообщении #1648579 писал(а):
Т.е. найти быстрый неитерационный алгоритм для исходной задачи сложновато?

В некотором смысле тут вообще нет неитерационных методов. Характеристический многочлен может оказаться неразрешимым в радикалах.

 Профиль  
                  
 
 Re: Алгоритм диагонализации матрицы
Сообщение05.08.2024, 21:00 
Заслуженный участник
Аватара пользователя


26/01/14
4834
B3LYP в сообщении #1648579 писал(а):
Прочитал эту статью:
https://ru.wikipedia.org/wiki/Собственный_вектор
Пока к сожалению мало что понял.
Закройте википедию уже и откройте учебник.
Например:
Ильин, Ким. Линейная алгебра и аналитическая геометрия
или
Кострикин. Введение в алгебру

А после этого (но не вместо!) можно открыть ещё
Бахвалов, Жидков, Кобельков. Численные методы
или
Калиткин. Численные методы
и почитать про алгоритмы решения задач линейной алгебры

И да, не торопитесь быстро посмотреть и сразу всё понять. Алгебру надо именно что изучать, и это не очень просто и не очень быстро.

И даже вне связи именно с диагонализацией - без хорошего понимания алгебры, в частности собственных значений и собственных векторов, не может идти и речи ни о какой квантовой физике.
B3LYP в сообщении #1648579 писал(а):
Пока к сожалению мало что понял. Но я вспомнил что в прошлом уже реализовывал диагонализацию матрицы методом Якоби (находил оси инерции и три момента инерции молекулы). Вроде это то что мне подходит
Ну вот как Вы можете говорить про какие-то алгоритмы, не разобравшись полностью и детально в том, что же именно они делают? Какой в этом смысл? Это как анекдот звучит. Вы же самых элементарных вещей не знаете, например того, что у матрицы не должно быть никакого "столбца справа". Даже если Вы что-то прочитаете нужное Вам, Вы этого не поймёте или поймёте неправильно. Так что беритесь серьёзно за учебники и читайте их с самого начала.

 Профиль  
                  
 
 Re: Алгоритм диагонализации матрицы
Сообщение05.08.2024, 22:12 


14/11/21
141
-> dgwuqtj
Цитата:
Характеристический многочлен может оказаться неразрешимым в радикалах.

Выше Евгений Машеров счел вот это ваше предложение за троллинг:
Цитата:
посчитать характеристический многочлен матрицы, найти его корни

Видимо, имея в виду то, что задача нахождения корней многочлена сводится к задаче на собственные значения для сопровождающей матрицы данного многочлена:
https://ru.wikipedia.org/wiki/%D0%A1%D0%BE%D0%BF%D1%80%D0%BE%D0%B2%D0%BE%D0%B6%D0%B4%D0%B0%D1%8E%D1%89%D0%B0%D1%8F_%D0%BC%D0%B0%D1%82%D1%80%D0%B8%D1%86%D0%B0

 Профиль  
                  
 
 Re: Алгоритм диагонализации матрицы
Сообщение05.08.2024, 22:18 
Заслуженный участник


07/08/23
1055
Alex Krylov в сообщении #1648588 писал(а):
Видимо, имея в виду то, что задача нахождения корней многочлена сводится к задаче на собственные значения для сопровождающей матрицы данного многочлена

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

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


01/09/13
4656
dgwuqtj в сообщении #1648589 писал(а):
А корни многочленов же двоичным поиском и методом Ньютона ищутся.

Все?

 Профиль  
                  
 
 Re: Алгоритм диагонализации матрицы
Сообщение05.08.2024, 23:26 
Заслуженный участник


07/08/23
1055
Как я понимаю, матрица симметричная, все собственные значения вещественные. От кратных корней можно избавиться, если сначала рекурсивно найти корни производной... Про проблемы с численной устойчивостью я ничего не утверждаю, это наивный плохой алгоритм, специально для велосипедирования.

 Профиль  
                  
 
 Re: Алгоритм диагонализации матрицы
Сообщение06.08.2024, 06:07 
Заслуженный участник
Аватара пользователя


11/03/08
9874
Москва
B3LYP в сообщении #1648579 писал(а):
Т.е. найти быстрый неитерационный алгоритм для исходной задачи сложновато?


Если получится - запасайтесь святой водой. А то придут призраки Абеля и Руффини и скелет Галуа с ними, всей группой перестановок, радикально побьют.

 Профиль  
                  
 
 Re: Алгоритм диагонализации матрицы
Сообщение06.08.2024, 07:58 
Заслуженный участник
Аватара пользователя


30/01/09
7060
B3LYP
А каков примерно у вас размер матрицы? Тут в соседней теме приведён пример матрицы размером шесть на шесть. Для такого размера наверно выбор метода не сильно и критичен. Можно и самому на коленке что-то запрограммировать.

 Профиль  
                  
 
 Re: Алгоритм диагонализации матрицы
Сообщение06.08.2024, 08:40 
Заслуженный участник
Аватара пользователя


11/03/08
9874
Москва
Я за тонкий троллинг почёл предложение считать через характеристический многочлен не потому, что корни такого многочлена может быть практичнее считать через собственные значения (правда, уже несимметричной матрицы), а потому, что такой расчёт включает два этапа. Первый, построение характеристического многочлена, при реализации "в лоб" требует $n!$ слагаемых (и "!" это не знак восторга...). И хотя в попытках упростить задачу было предложено много достаточно нетривиальных по идее и сложных по реализации алгоритмов (можно ознакомится, скажем, в классической книге Фадеева и Фадеевой, но имея в виду, что все они представляют исторический интерес, а книга вышла, когда QR-алгоритм ещё не придумали, а "ручная" реализация метода Якоби оказалась для компьютеров непрактичной, и как обойти нежданную трудность с тем, что герр Якоби выбирал для зануления отражениями максимальный элемент матрицы, что для посильных ручному расчёту размерностей составляло пренебрежимо малую затрату труда сравнительно с умножениями, а при компьютерной реализации поиск максимума требовал$O(n^2)$ операций, тогда как собственно вращение $O(n)$, тогда только соображали), самый быстрый из алгоритмов требовал $O(n^4)$ шагов.
Второй этап, нахождение корней характеристического полинома, достаточно быстр, но возможна численная неустойчивость (хотя спасает то, что для симметричной матрицы они действительны, и можно делить пополам, в общем случае всё довольно грустно).
Ну и присоединяюсь к вопросу о размере матрицы. Может, "возьмите транспортир"?

 Профиль  
                  
 
 Re: Алгоритм диагонализации матрицы
Сообщение06.08.2024, 13:32 
Заслуженный участник
Аватара пользователя


23/07/08
10887
Crna Gora
Евгений Машеров в сообщении #1648610 писал(а):
в классической книге Фадеева и Фадеевой
Да зовется Фадеев Фаддеевым, жена же Фадеева — Фаддеевой, в знак признания их научных заслуг!

 Профиль  
                  
 
 Re: Алгоритм диагонализации матрицы
Сообщение06.08.2024, 15:34 
Заслуженный участник
Аватара пользователя


11/03/08
9874
Москва
Спасибо за поправку, очепятался.

 Профиль  
                  
 
 Re: Алгоритм диагонализации матрицы
Сообщение06.08.2024, 16:02 
Заслуженный участник


29/09/14
1239
Евгений Машеров в сообщении #1648610 писал(а):
Ну и присоединяюсь к вопросу о размере матрицы.

Числовые значения (они вещественные) элементов симметричной матрицы $F$ силовых постоянных приведены топикстартером в этой его теме:

post1644851.html#p1644851

Размер этой матрицы: 9х9.

Но задачу ТС там ставит как физическую, а с точки зрения физики в этой матрице должны присутствовать равные нулю три строки и три столбца.

И в ней действительно видны "почти равные нулю" три строки и три столбца. Для решения физической задачи можно их смело вычеркнуть. Тогда остаётся матрица $F$ размером 6х6.

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

Т.е. актуальные с физической точки зрения собственные значения $\lambda$ матрицы $F$ в физической задаче ТС легко находятся вообще без громоздких численных расчётов, а просто как корни двух квадратных уравнений. Всё это уже написано топикстартеру в ответ на его просьбу помочь решить задачу в одной из его тем, вот здесь:

post1648449.html#p1648449

Заодно там в следующем сообщении дано сравнение с результатами численного счёта собственных значений для матрицы $F$ в её 6х6- и 9х9-вариантах.

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 33 ]  На страницу Пред.  1, 2, 3  След.

Модераторы: Модераторы Математики, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group