2014 dxdy logo

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

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


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


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



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


11/03/08
9904
Москва
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
422
Прочитал эту статью:

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

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

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


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

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

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


26/01/14
4845
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
1095
Alex Krylov в сообщении #1648588 писал(а):
Видимо, имея в виду то, что задача нахождения корней многочлена сводится к задаче на собственные значения для сопровождающей матрицы данного многочлена

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

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


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

Все?

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


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

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


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


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

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


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

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


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

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


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

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


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

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


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

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

post1644851.html#p1644851

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

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

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

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

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

post1648449.html#p1648449

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

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

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



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

Сейчас этот форум просматривают: Mikhail_K


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

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