Собственные числа матрицы

[zykov]

vpb в сообщении #1537204 писал(а):

Вы взяли матрицу с элементами $\lambda_{ij}=51-|i-j|$, да ?

Да. Взято для проверки работоспособности (не важно, какие там рациональные числа). Никакого глубокого смысла тут нет. Предполагается, что ТС сюда вставит свою матрицу.

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

Всё замечательно, но считать через характеристический многочлен - не самый точный способ...

В общем случае да (если считать приближенно через числа с плавающей точкой). В случае ТС, если использовать символьные вычисления (как это делает Maxima), то сам многочлен будет абсолютно точен. А уж искать корни многочлена с целыми коэффициентами очень легко с любой точностью. ТС упоминал, что точность важна, но не написал о примерном порядке. Здесь можно получить спектр с любой точностью (в практических пределах), хоть 100 десятичных знаков.

[vpb]

zykov в сообщении #1537205 писал(а):

Взято для проверки работоспособности (не важно, какие там рациональные числа)

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

[zykov]

vpb в сообщении #1537206 писал(а):

Такой тест проверяет не работоспособность программы, а правильность её формального написания

Боюсь, не вижу причин для такого странного утверждения. Там совершенно не важно, какие рациональные числа стоят в матрице.
Вот прогнал вашу матрицу:

Используется синтаксис Text

m: genmatrix(lambda([i,j], (1+abs(i-j))^(-2)), n, n);

Вот её спектр с точностью 25 десятичных знаков (могу и 100 знаков дать, если надо):

6.45171160318028198592124b-1
6.458831200656652284330236b-1
6.470720303669286325873533b-1
6.487412956685580868370221b-1
6.508958737012136426184717b-1
6.535419251926757229090185b-1
6.566874675858464933506263b-1
6.603415203858068234057661b-1
6.645154323239113984235085b-1
6.692212605920331236994043b-1
6.744740555511478316467155b-1
6.802891763563998433504928b-1
6.866858632357615308554659b-1
6.936831405222135856629578b-1
7.013050709755362620478293b-1
7.09574825631577380122504b-1
7.185221033421130501517574b-1
7.281748486318186800125885b-1
7.385694410596802926432993b-1
7.497394078429108543437276b-1
7.617291543819830435587833b-1
7.74578833462349265451877b-1
7.883426192690293779935474b-1
8.030686378696253280526082b-1
8.188231113005154436311896b-1
8.35663891359211431157174b-1
8.536722634089700679906785b-1
8.729181044059196435209551b-1
8.935018113649682989884977b-1
9.155083389177231999707279b-1
9.390627271621322161906184b-1
9.642691187895846030700249b-1
9.912849166624298959515991b-1
1.020239081145894176169545b0
1.051332431211300002627372b0
1.084726610919897538353381b0
1.120682187088424919685225b0
1.15940473815122573917094b0
1.201239676074432101011821b0
1.246453045913704571827655b0
1.29551566857675757825802b0
1.348779093600930040755181b0
1.406909680407312753447938b0
1.470383544308682560874245b0
1.540195891687304458003764b0
1.61700894088595936503678b0
1.702439682319068012094779b0
1.797420187067563730937935b0
1.905020977936741408516063b0
2.026300962075795186373192b0
2.170435052924737379634229b0

[vpb]

zykov в сообщении #1537208 писал(а):

от прогнал вашу матрицу:

Это не моя матрица. В моей $a_{ij}=1/(1+(i-1)+51(j-1))$.

-- 01.11.2021, 07:05 --

Было же написано:

vpb в сообщении #1537204 писал(а):

Попробуйте что-нибудь другое ... ну , например, обратные величины чисел от $1$ до $51^2$, расположенные в естественном порядке (как в книжке).

то есть в первой строке $1/1, 1/2, \ldots, 1/51$, во второй $1/52,1/53,\ldots,1/102$, и т.д. И вплоть до $1/51^2$ в правом нижнем углу. По-моему, всё ясно было написано.

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

Говорят, некогда адмирал Крылов уволил начальника верфи за то, что инженеры у него вели расчёты с двумя знаками больше, чем требовалось. Может быть, определиться сперва, какая точность нужна?
Безусловно, рациональная арифметика позволит посчитать характеристический многочлен абсолютно точно. Но вот корни у него уже рациональными числами, вообще говоря, не будут. И вычислены будут с некоторой погрешностью. И мне отчего-то кажется, что погрешность результата будет обусловлена не погрешностью вычисления корней, а погрешностью исходных данных. Так что характеристический многочлен, вычисленный в целых числах и расчёт корней до 100 знаков могут оказаться не особо полезными.
В общем, хорошо бы что-то узнать о задаче, исходя из этого, выработать требования к точности ("абсолютной точности", в принципе достижимой для СЛАУ, тут абсолютно точно не будет), и, возможно, окажется, что вполне хватает самых стандартных пакетов. А для перестраховки - повторить расчёт, используя, кроме обычной "двойной", одинарную и расширенную точность. Если разница результатов окажется меньше желаемой точности - значит, пользоваться стандартными методами.

[zykov]

Евгений Машеров
Да, для инженерных рассчётов такая точность обычно не требуется. Но иногда надо точно проанализировать какой-то математический объект. Для этого символьные вычисления подходят лучше. Для этого и сделаны символьные мат. пакеты.
ТС сразу написал, что матрица содержит точные рациональные значения. Похоже скорее на какой-то математический анализ, чем на инженерное приложение.

Вот у меня недавно была похожая задача. Матрица вероятностей для Марковского процесса - это была матрица с точными рациональными значениями. И нужно было проанализировать - найти поточнее наибольшие собственные значения под единицей. Там правда размер поменьше, где-то 10-20. Но в принципе могло бы быть и 50.

-- 01.11.2021, 09:23 --

vpb в сообщении #1537209 писал(а):

Это не моя матрица. В моей $a_{ij}=1/(1+(i-1)+51(j-1))$.

В теме речь про симметричную матрицу, а эта не симметричная.
Впрочем характеристический многочлен считается точно так же. Вышел довольно большой - 330кб.
Но корни уже не обязаны быть действительными.
Поискал его корни функцией 'realroots'. Она ищет только действительные корни действительного многочлена методом Штурма (подробнее смотри первый том трёхтомника Кострикина "Введение в алгебру").
Нашлись 51 действительных корей.
Вот спектр этой матрицы (25 десятичных знаков):

1.512731216738014950319543b-123
4.53819365021404485095863b-123
1.858844119127672770952655b-119
7.613825511946947669822074b-116
3.118622929693469765559121b-112
6.386939760012226079865081b-109
1.308045262850503901156369b-105
2.678876698317831989568243b-102
5.486339478154919914635761b-99
5.618011625630637992587019b-96
5.752843904645773304409108b-93
5.890912158357271863714926b-90
6.032294050157846388444085b-87
6.177069107361634701766743b-84
6.325318765938313934609144b-81
3.238563208160416734519882b-78
1.65814436257813336807418b-75
1.69793982728000856890796b-72
8.693451915673643872808755b-70
4.451047380824905662878082b-67
2.278936258982351699393578b-64
5.83407682299482035044756b-62
2.987047333373348019429151b-59
1.529368234687154185947725b-56
3.915182680799114716026176b-54
1.002286766284573367302701b-51
5.13170824337701564058983b-49
1.313717310304516003990996b-46
3.363116314379560970216951b-44
8.609577764811676083755395b-42
1.102025953895894538720691b-39
2.821186441973490019124968b-37
7.222237291452134448959917b-35
9.244463733058732094668694b-33
2.366582715663035416235186b-30
3.029225876048685332781038b-28
3.877409121342317225959728b-26
6.022908835151732757657445b-24
7.559655316910404484879484b-22
8.740861476817885319961403b-20
9.261708027974116779448735b-18
8.952658552087665242183209b-16
7.850867160151621343301122b-14
6.202194631245282786396207b-12
4.37447022135205048141473b-10
2.721585236815438334292548b-8
1.469852491479289212081521b-6
6.690265552902578670173314b-5
2.542681093656581059281802b-3
6.315664480832848582426907b-2
1.020162845136022105312749b0

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

Ну так в любом случае как только ставится задача нахождения собственных чисел, корней некоего многочлена, рациональность куда-то убегает. И даже выписать выражение с радикалами, говорят, нельзя... А численно - тут вопрос о точности важен, но решаем. Скажем, если для нас принципиально, что максимальное собственное значение меньше единицы, мы его вычислили, меньше, но не в силу ошибки ли? - вполне можно оценить ошибку и придти к выводу, что с учётом ошибки всё равно меньше.

[zykov]

Евгений Машеров
Да, точно корни многочлена не выразить обычно. Даже через радикалы.
Но, как я писал выше, если есть точный многочлен с целыми коэффициентами, то задача найти его корни приближенно - это уже элементарно. Хоть методом Ньютона можно быстро найти хоть 100, хоть 1000 знаков.

Или вот для примера возьмите матрицу 51x51 которую привёл vpb.
Ради любопытства в Octave её забил - просто численные методы с double float.
Там функция 'eigs' (help: "This function is based on the ARPACK package") ерунду выдаёт.
Максимальное значение около 1, но отличается во втором знаке после запятой.
Второе значение 5e-4 вместо нужного 6e-2.
В хвосте идут степени 1e-19 - 1e-23, что совсем не похоже на правильный результат.

А вот символьные вычисления в Maxima выдали все 51 собственных значений с заказанной точностью (25 знаков).

-- 01.11.2021, 10:02 --

vpb в сообщении #1537204 писал(а):

Для несимметрических же матриц ситуация совершенно другая, их с.з. считать гораздо труднее.

Если имеется эффективный метод для симметричных матриц, то для несимметричной можно провести Polar decomposition - $A=UP$.
Сначала нужно найти собственные значения матрицы $A^* A$, которые равны квадратам модулей собственных значений исходной матрицы (что уже даёт модули собственных значений исходной матрицы).
Потом матрицу $P=(A^* A)^{1/2}$. Потом матрицу $U=A P^{-1}$.

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

Не работает. Простой связи с.з. исходной матрицы с собственными значениями матрицы $A^TA$ нет, увы. Для симметричной есть, а для несимметричной нет.

[zykov]

Да, поспешил.
Там, про полярное разложение, другое утверждается.
В разделе "Relation to the SVD" получается спектральное разложение, если матрица нормальная.
Матрица будет нормальной, если она например самосопряженная, но не только.

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

Так сингулярные числа ищут. Которые иногда связаны простым образом с собственными, а чаще нет.

[zykov]

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

Ради любопытства в Octave её забил - просто численные методы с double float.
Там функция 'eigs' (help: "This function is based on the ARPACK package") ерунду выдаёт.
Максимальное значение около 1, но отличается во втором знаке после запятой.
Второе значение 5e-4 вместо нужного 6e-2.
В хвосте идут степени 1e-19 - 1e-23, что совсем не похоже на правильный результат.

Нет, тут я напутал, зачем-то в квадрат возвёл.
В начале нормально идёт 1.0202, 0.0632, 0.00254 и т.д.
Первые 10 более менее совпадают (до 1e-16), правда в 10ом большая ошибка уже.
А в хвосте идёт 1e-19, 1e-20, что совсем далеко от правильных.

[vpb]

zykov в сообщении #1537214 писал(а):

В теме речь про симметричную матрицу, а эта не симметричная.

Верно. Извиняюсь за невнимательность.

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

[zykov]

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

-- 01.11.2021, 15:21 --

vpb в сообщении #1537258 писал(а):

Тут отлично работает и обычный.

Который из них?
Просто численные методы на double float могут и не очень хорошо работать. Опять же, зависит от требований.

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

zykov в сообщении #1537249 писал(а):

А в хвосте идёт 1e-19, 1e-20, что совсем далеко от правильных.

А вот тут надо смотреть, какая точность вычислений. Возможно, double, и попросту вышли на машинную погрешность. И надо что-то использовать поточнее, ну хоть extended. Или вообще длинную "немашинную" арифметику.