о спектре симметричной матрицы

anton-burduev

Пусть есть вещественная симметричная матрица A размера N*N. N большое (к примеру, 10000000). Известно, что существует такое λ, что матрица A+aI (где I — единичная матрица) будет положительно определенной для любого a>λ. Вопрос в том, как быстро получить приблизительную оценку для λ. Чем меньше оценка — тем лучше, главное не меньше настоящего λ. :)
Извините за некоторую корявость формулировки.
Мехмат, выручай!

griz_a

Если у матрицы собственные значения t_1,....,t_n, то у A+aI они очевидно t_1+a,....,t_n+a
Положительная определенность - это положительность всех собственных значений.
Значит задача по факту о том, как найти\оценить минимальное собственное значение.
Это можно гуглить

griz_a

Прямо быстро и грубо - наверное, теорема Гершгорина сгодится http://en.wikipedia.org/wiki/Gershgorin_circle_theorem

elenchik

Зачем тогда в условии симметричность матриц?

griz_a

Для вещественности с.з, например.

elenchik

Это понятно, но вот может оценки на минимум этих чисел есть проще,
сходу не гуглится.

furi

Если не ошибаюсь, про спектры и диагонализации любых комплексных симметричных матриц есть вроде такое разложение Такаги

anton-burduev

Предлагаю рассмотреть пример. Код ниже рассчитывает энергию основного состояния атома водорода:

#!/usr/bin/python2

from itertools import *
from scipy.sparse import *
from scipy.sparse.linalg import *
from math import *

L = 100
N = L*L*L

def idx(c):
return L*L*c[2] + L*c[1] + c[0]

def coord_ok(c):
for i in xrange(3):
if c[i] < 0 or c[i] >= L:
return False
return True

def myadd(xs, ys):
return tuple(x + y for x, y in izip(xs, ys

offs = [[1, 0, 0], [-1, 0, 0], [0, 1, 0], [0, -1, 0], [0, 0, 1], [0, 0, -1]]

c0 = 2283.6
c1 = 380.6

rows = []
cols = []
elts = []

mindiag = 1e10
maxradius = 0

print "Setting up the matrix", N, "x", N

for coord in product(xrange(L xrange(L xrange(L:
#init diagonals
l1 = idx(coord)

rows.append(l1)
cols.append(l1)

r = sqrtcoord[0] - L/2 + 0.5)**2 + (coord[1] - L/2 + 0.5)**2 + (coord[2] - L/2 + 0.5)**2)
phi = -1.45/(0.01*r)

mindiag = min(mindiag, c0+phi)
elts.append(c0 + phi)

#init subdiagonals
radius = 0
for n in xrange(6):
c2 = myadd(coord, offs[n])
if coord_ok(c2):
l2 = idx(c2)
rows.append(l1)
cols.append(l2)
elts.append(-c1)
radius += abs(c1)
if radius > maxradius:
maxradius = radius

A = coo_matrixelts, (rows, cols shape=(N, N.tocsc

print "Mindiag =", mindiag, "maxradius =", maxradius, "lambda_est =", mindiag - maxradius

print "Solving eigenvalue problem"
print "lambda_exact =", (eigs(A, 1, which = 'SR')[0][0]).real

Вот что он выдает на печать:

Setting up the matrix 1000000 x 1000000
Mindiag = 2116.16842194 maxradius = 2283.6 lambda_est = -167.431578065
Solving eigenvalue problem
lambda_exact = -13.6885029103

То есть оценка с помощью кругов Гершгорина, кмк, fails epically.
Продолжаю наблюдение.

anton-burduev

разложение Такаги
А можете поподробнее рассказать, как оно поможет в моем случае? Википедия толком ничего не объясняет.
Оставить комментарий
Имя или ник:
Комментарий: