Алгоритм диагонализации матрицы

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

B3LYP в сообщении #1648384 писал(а):

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

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

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

B3LYP в сообщении #1648384 писал(а):

И что такое вообще собственные значения матрицы?

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

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

dgwuqtj в сообщении #1648388 писал(а):

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

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

[Alex Krylov]

Цитата:

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

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

[B3LYP]

Прочитал эту статью:

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

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

[dgwuqtj]

B3LYP в сообщении #1648579 писал(а):

Т.е. найти быстрый неитерационный алгоритм для исходной задачи сложновато?

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

[Mikhail_K]

B3LYP в сообщении #1648579 писал(а):

Прочитал эту статью:
https://ru.wikipedia.org/wiki/Собственный_вектор
Пока к сожалению мало что понял.

Закройте википедию уже и откройте учебник.
Например:
Ильин, Ким. Линейная алгебра и аналитическая геометрия
или
Кострикин. Введение в алгебру

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

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

И даже вне связи именно с диагонализацией - без хорошего понимания алгебры, в частности собственных значений и собственных векторов, не может идти и речи ни о какой квантовой физике.

B3LYP в сообщении #1648579 писал(а):

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

Ну вот как Вы можете говорить про какие-то алгоритмы, не разобравшись полностью и детально в том, что же именно они делают? Какой в этом смысл? Это как анекдот звучит. Вы же самых элементарных вещей не знаете, например того, что у матрицы не должно быть никакого "столбца справа". Даже если Вы что-то прочитаете нужное Вам, Вы этого не поймёте или поймёте неправильно. Так что беритесь серьёзно за учебники и читайте их с самого начала.

[Alex Krylov]

-> 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

[dgwuqtj]

Alex Krylov в сообщении #1648588 писал(а):

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

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

[Geen]

dgwuqtj в сообщении #1648589 писал(а):

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

Все?

[dgwuqtj]

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

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

B3LYP в сообщении #1648579 писал(а):

Т.е. найти быстрый неитерационный алгоритм для исходной задачи сложновато?

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

[мат-ламер]

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

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

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

[svv]

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

в классической книге Фадеева и Фадеевой

Да зовется Фадеев Фаддеевым, жена же Фадеева — Фаддеевой, в знак признания их научных заслуг!

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

Спасибо за поправку, очепятался.

[Cos(x-pi/2)]

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

Ну и присоединяюсь к вопросу о размере матрицы.

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

post1644851.html#p1644851

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

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

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

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

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

post1648449.html#p1648449

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