Спектральная(ое) теорема/разложение в приближённом формате

[amarsianin]

Пусть $A: H \rightarrow H$ - самоспоряжённый оператор на $n-$мерном Гильбертовом пространстве $H$. Спектральная теорема утверждает, что $A$ может быть разложен в след. сумму:

$$ A = \sum_{i=1}^{m}\lambda_i P_i, $$

где $\lambda_i, i=1, \ldots m$ - $m$ различных собственных значений $A$, а $P_i$ - соответствующие им ортогональные проекции на собственные подпространства $H_i = \ker \{ \lambda_i I - A \}$. При этом само пространство раскладывается в прямую сумму:

$$ H= \displaystyle \underset{i=1}{\overset{m}{\oplus}} H_i. $$

Можно показать, что существует эффективный алгоритм, который вычисляет спектральное разложение в таком формате:

для любого $\varepsilon >0$ существуют проекции $P_i, i=1, \ldots n$, P_i, P_j = 0, i \neq j и (вычислимые) действительные числа $\alpha_1, \ldots \alpha_n$, что

$$ \big|\big| A - \displaystyle \sum_{i=1}^{n} \alpha_i P_i \big|\big| \leq \varepsilon $$

Эффективный алгоритм, в понятии теории вычислимости, состоит из конечного числа механических инструкций, всегда завершается, всегда выводит правильный ответ, не основан на эвристике. Подробнее смотри в Вики.

Ясно, что спектр оператора или матрицы в общем случае невычислим. Всвязи с чем некоторые алгоритмы испытывают сложности. Но в приближённом формате многое становится возможным.

Какие есть хорошие ссылки по предмету? В частности, интересует теорема в полном приближённом формате, то есть учитывающая вычисление приближённых собственных векторов, собственных подпространств (читай, базисов) и т. д. Приближение в смысле какой-либо метрики, лучше в смысле самых естественных метрик (с помощью операторной нормы, например, как это сделано выше).

[Brukvalub]

Возможно, я так и не понял, чего именно вы хотите, но должен отметить, что в любой книге по численным методам линейной алгебры есть глава "симметричная проблема собственных значений". На русский язык переведены книги:
1.Уилкинсон Алгебраическая проблема собственных значений,
2.Деммель Вычислительная линейная алгебра, см. гл. 5,
3. Голуб, Ван Лоун Матричные вычисления, см. гл. 8
4. Парлетт Симметричная проблема собственных значений.

[amarsianin]

Благодарю, но это не вопрос о численных методах.

[dsge]

amarsianin в сообщении #1116287 писал(а):

Ясно, что спектр оператора или матрицы в общем случае невычислим.

Некоторые по незнанию вычисляют корни характеристического многочлена.

[g______d]

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

Дальше не очень понятно, что нужно. Если я правильно понимаю логику вопроса, то нужно начать с книги Като "Теория возмущений линейных операторов", а потом уже смотреть.

Еще есть такая вещь "pseudospectrum", но в самосопряженном случае это довольно тривиальная вещь.

[amarsianin]

Цитата:

Корни вычислимы с любой точностью

Корни-то да, а вот их кратность не вычислима.

[g______d]

amarsianin в сообщении #1116555 писал(а):

Корни-то да, а вот их кратность не вычислима.

Во-первых, есть результант. Во-вторых, если в пределах погрешности два корня совпадают, то в самосопряженном случае это не отличается от ситуации с кратным корнем.

[amarsianin]

Цитата:

Во-первых, есть результант

И что?

Цитата:

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

Вообще ничего не понял. Можно пояснить, пожалуйста?

[g______d]

amarsianin в сообщении #1116572 писал(а):

И что?

Если результант положителен, это даёт вам нижнюю оценку на расстояние между корнями. Если $\varepsilon$ меньше этого расстояния, то можно указать интервалы, внутри которых ровно один корень с учётом кратности.

amarsianin в сообщении #1116572 писал(а):

Вообще ничего не понял. Можно пояснить, пожалуйста?

Для построения приближённых собственных векторов и спектральных проекторов не нужно знать точную кратность каждого корня, достаточно уметь определять суммарную кратность корней, находящихся в заданном интервале размера $\varepsilon$. Это делается с помощью интеграла по контуру.

Дальше, если $C$ - контур, окружающий несколько корней, то $\frac{1}{2\pi i}\oint\limits_C (A-zI)^{-1}\,dz$ -- это проектор на подпространство, порожденное всеми собственными векторами, отвечающими этим корням. Если все эти корни находятся внутри отрезка размера $\varepsilon$, то, с точностью до $\varepsilon$, можно считать, что у нас одно собственное значение суммарной кратности. Погрешность будет порядка $\varepsilon$ по операторной норме (я, правда, пока не услышал, что именно должно от чего отличаться по операторной норме, но в любом разумном смысле будет так).

[amarsianin]

Цитата:

Если результант положителен

То есть вы хотите сравнить действительное число с нулём? Не существует такого эффективного алгоритма.

Цитата:

достаточно уметь определять суммарную кратность корней, находящихся в заданном интервале размера $\varepsilon$.

И это тоже не вычислимо.

Цитата:

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

Ну одну метрику я привёл. Для собственных значений можно взять метрику

$$ | \det \{ A - \alpha I \} |, $$

где $ \alpha$ - приближённое собственное значение.

По векторам:

$$ || A v - \alpha v ||, $$

где $v$ - приближённый собственный вектор.

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

[Brukvalub]

Как я понял еще вчера, ТС желает поговорить о каком-то замороченном конструктивизме, а не о эффективных численных способах локализации собственных значений...

[g______d]

amarsianin в сообщении #1116621 писал(а):

И это тоже не вычислимо.

Ну не знаю, по-моему, вполне вычислимо. Докажите такую лемму: пусть дан полином $p$ степени $N$. Для любого $\varepsilon>0$ существует множество $S$, обладающее следующими свойствами:

1) $S$ является объединением $k\le N$ интервалов, концы каждого интервала вычислимы, и каждый интервал имеет длину $<\varepsilon$.

2) На каждом интервале множества $S$ имеется хотя бы один корень $p$.

3) $p(x)\ge (\varepsilon/3)^N$ для любого $x\notin S$.

По-моему, совершенно очевидно, как это $S$ строить, но точное доказательство опирается на определение слов "вычислимо" и "дан полином". Например, можно считать, что $\varepsilon$ и все концы интервалов рациональны.

Дальше, суммарная кратность корней внутри интервала равна $\frac{1}{2\pi i}\oint\limits_C\frac{p'(z)}{p(z)}\,dz$, где $C$ -- некоторый контур, окружающий этот интервал.

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

[Brukvalub]

g______d, о какой вычислимости тут может идти речь, если тс писАл выше:

amarsianin в сообщении #1116621 писал(а):

вы хотите сравнить действительное число с нулём? Не существует такого эффективного алгоритма.

Выходит, тс не умеет сравнивать действительное число с нулем, а вы ему предлагаете сравнивать длины интервалов с эпсилонами!

[g______d]

Дальше, если $p$ -- характеристический многочлен матрицы, то аппроксимация строится так:

1) Приближенные собственные значения -- середины интервалов множества $S$.

2) Кратности -- числа, полученные из контурного интервала.

3) Проекторы на собственные подпространства -- интегралы $\frac{1}{2\pi i}\oint\limits_C (A-zI)^{-1}\,dz$ по соответствующим контурам.

Если из этих новых собственных значений и спектральных проекторов составить новую матрицу $A'$, то будет верно $\|A-A'\|\le \varepsilon$ (по операторной норме).

-- Вт, 19 апр 2016 13:17:22 --

Brukvalub в сообщении #1116760 писал(а):

Выходит, тс не умеет сравнивать действительное число с нулем, а вы ему предлагаете сравнивать длины интервалов с эпсилонами!

Это не одно и то же. В программировании, действительно, никогда не пишут "if a==0", если $a$ вещественное, а пишут "abs(a)<epsilon". Потому что равенство нулю может случайно нарушиться из-за округления.

-- Вт, 19 апр 2016 13:24:56 --

Ну т. е. смысл в том, что понятие вычислимости $x$ означает, что есть черный ящик, который для любого рационального $\varepsilon>0$ выдает рациональное $q$, такое что $|q-x|<\varepsilon$. Понятно, что условие $x>y$ таким образом не проверить, а вот $x>y+0.00000000001$ уже можно.

[Brukvalub]

g______d в сообщении #1116761 писал(а):

Это не одно и то же. В программировании, действительно, никогда не пишут "if a==0", если $a$ вещественное, а пишут "abs(a)<epsilon". Потому что равенство нулю может случайно нарушиться из-за округления.

-- Вт, 19 апр 2016 13:24:56 --

Ну т. е. смысл в том, что понятие вычислимости $x$ означает, что есть черный ящик, который для любого рационального $\varepsilon>0$ выдает рациональное $q$, такое что $|q-x|<\varepsilon$. Понятно, что условие $x>y$ таким образом не проверить, а вот $x>y+0.00000000001$ уже можно.

Спасибо, но понятие вычислимости мне было известно и ранее, до ваших объяснений.
На мой взгляд, вы путаете вычислимость и ошибки округления. Если в ходе вычислений возникли ошибки округления, величина которых "забивает" требуемую точность, то и "abs(a)<epsilon" не поможет. Если же хотя бы один старший десятичный знак вычисляемого действительного числа найден достоверно, то сравнить это число с нулем может даже шестиклассник.