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

[g______d]

Я прошу прощения, если пишу какую-то тривиальщину.

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

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

Допустим, что заведомо известно, что ошибки округления не забивают требуемую точность. Все равно, в этом случае никто и никогда не будет писать "if (x==0) ...". Проверка условия $x=0$ означает, что этот случай надо рассмотреть отдельно, потому что какая-то часть алгоритма при этом разваливается; например, в процессе происходит деление на $x$. Но тогда очевидно, что алгоритм точно так же развалится при маленьком, но ненулевом $x$, потому что результат деления на $x$ не влезет в тип данных. Поэтому в любом алгоритме, работающем с вещественными числами, проверки $x=0$ заменяются на $abs(x)<\varepsilon$; при этом $\varepsilon$ выбирается так, чтобы алгоритм еще работал, например, при $x>\varepsilon/2$.

Насколько я понимаю, именно подобные вещи формализуются с помощью теории вычислимости.

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

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

Если найден достоверно, то да. Но это как раз вещь, которую, вообще говоря, нельзя найти достоверно. Т. е. нельзя придумать алгоритм, который за гарантированное число шагов отвечает "да/нет" на вопрос "верно ли, что $x<0.00000000001$". Тем более нельзя, вообще говоря, достоверно найти старший десятичный знак.

С другой стороны, существует алгоритм, который за гарантированное число шагов выдает один из двух ответов: "заведомо $x<0.00000000001$" или "заведомо $x>0.000000000005$". В этом случае есть интервал, в котором ответ может быть любым из двух, но это не проблема: при первом варианте алгоритм заругается на некорректные входные данные (что будет правильно, если это отразить в спецификации), а при втором варианте он запустится и выдаст правильный ответ с нужной погрешностью (если эту ветвь сделать с некоторым запасом).

[amarsianin]

(Оффтоп)

Brukvalub не разбирается в теме и сидит тут только чтоб убого потроллить. Не советую засорять тред спорами с ним

[amarsianin]

Цитата:

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

Хм. Это может сработать.

[Brukvalub]

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

(Оффтоп)

Brukvalub не разбирается в теме и сидит тут только чтоб убого потроллить. Не советую засорять тред спорами с ним

(Оффтоп)

Именно такое поведение описАл дедушка Крылов в своей басне "Свинья под дубом". Я пытаюсь обсуждать задачу тс, чтобы помочь ему, а, вместо благодарности, натыкаюсь на грубость и оскорбления.

[amarsianin]

(Оффтоп)

Я хорошо помню, кто тут начал с оскорблений. И никакой помощи тут не было, кроме как от g______d. Только не относящиеся к делу издёвки, которые уводят нить обсуждения.

[g______d]

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

Хм. Это может сработать.

Собственно, ссылка по теме

https://pdfs.semanticscholar.org/a669/d ... 9f0183.pdf

про полином там теорема 8 (в более общем варианте).

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

[amarsianin]

Благодарю, g______d. Вот это по делу.

На самом деле, и спектр, и собственные вектора, и подпространства, и проекции вычислимы, если мощность спектра известна наперёд (вы как раз привели статью, на которую я сам хотел сослаться).

Вычислимо также приближение, которое я привёл в первом посте. Но там ничего не сказано о собственных векторах и подпространствах.

Действительно, поскольку кратность корней невычислима, то возникает проблема с размерностями собственных подпространств. Но, я полагаю, можно взять приближённые собственные значения так, что они все будут (вычислимо) различны. И тогда можно взять одномерные подпространства и соотв. проекции. Либо взять проекции по типу $P_{\alpha^+_i} - P_{\alpha^-_i}, \alpha^+_i > \alpha^-_i$ для прибл. собств. значения в интервале $[\alpha^-_i}, \alpha^+_i]}$ и базис пространства $\text{range}\{P_{\alpha^+_i} - P_{\alpha^-_i}\}$ вычислим. Кстати, да, крастность внутри интервала должна быть вычислима. Насчёт приближённых собственных векторов пока не могу ничего сказать.

Цитата:

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

Вот отсюда бы поподробнее.

[g______d]

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

Вот отсюда бы поподробнее.

Ну я вроде бы все уже сказал. Предположим, что у вас есть кластер из $n$ собственных значений, все они находятся внутри отрезка $(\lambda-\varepsilon/2,\lambda+\varepsilon/2)$, и внутри отрезка $(\lambda-2\varepsilon,\lambda+2\varepsilon)$ других собственных значений нет. И вы не знаете, какие из собственных значений слипшиеся, а какие нет. В этом случае можно рассмотреть проектор $\frac{1}{2\pi i}\oint\limits_C (A-z I)^{-1}\,dz$, где $C$ — окружность радиуса $\varepsilon$ вокруг $\lambda$. Это будет ортогональный проектор на подпространство размерности $n$. Для любого $x$ из этого подпространства будет верно $\|Ax-\lambda x\|\le (\varepsilon/2)\|x\|$. Т. е. любой базис этого подпространства будет базисом из приближенных собственных векторов, если использовать ваше определение.

[amarsianin]

Вооооот. А если размерность известна, то базис подпространства должен быть, по идее, вычислим.

Вопрос глупый, но, как я понимаю, приближённое SVD матрицы можно вычислить по этому рецепту?

[g______d]

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

Вооооот. А если размерность известна, то базис подпространства должен быть, по идее, вычислим.

Собственно, если у вас есть проектор, то среди его столбцов есть базис.

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

Вопрос глупый, но, как я понимаю, приближённое SVD матрицы можно вычислить по этому рецепту?

SVD восстанавливается по спектральному разложению $AA^*$ и $A^*A$. Правда, надо понять, что там происходит с кратными с. з.

[amarsianin]

Цитата:

то среди его столбцов есть базис.

И как понять, какие именно столбцы?

По поводу SVD


Как я понял, матрицу $\Sigma$ можно взять втупую как есть, не решая, какие сингулярные значения кратные, а какие нет.

А вот базисы для $U$ и $V^*$, видимо должны отыскиваться по описанному вами выше принципу. Правда, тогда и в $\Sigma$ надо вставить приближённые собств. значения $A A^*$ и $A^* A$ для левых и, соотвественно, правых ортонормированных собств. векторов. Разве отсюда не вытекает оценка, аналогичная той, что у нас была выше?

[amarsianin]

g______d
А вы уверены, что проекторы, которые вы привели, являются приближёнными? Насколько я понял, эти интегралы и есть точные проекторы и док-во, что они являются проекторами на подпространства размерности, точно равной числу собств. значений в интервале, опирается на существование точной диагонализации/норм. формы Жордана. Получается порочный круг.

[g______d]

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

И как понять, какие именно столбцы?

Брать только те столбцы, норма которых больше $1-\varepsilon$ и которые ортогональны предыдущим взятым столбцам (с точностью до $\varepsilon$).

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

А вы уверены, что проекторы, которые вы привели, являются приближёнными?

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

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

док-во, что они являются проекторами на подпространства размерности, точно равной числу собств. значений в интервале, опирается на существование точной диагонализации/норм. формы Жордана. Получается порочный круг.

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

[amarsianin]

g______d

Цитата:

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

Понял. Вот тут, думаю, есть маленькая загвоздка. Ясно, что не хорошо здесь использовать порочный круг. Конечно, интеграл вычислим и то, что проектор находится в явном виде - хорошая идея. То, что это проектор, думаю, можно показать, не прибегая к спектральной теореме. Вот это свойство:

$$\|Ax-\lambda x\|\le (\varepsilon/2)\|x\|$$

тоже нехитро выводится. Остаётся, я так понял, загвоздка с размерностью пространства и его базисом. Это то, "что нужно", или вы другое имели ввиду?

Кстати, аналогичный результат можно найти здесь, стр. 53:



Кстати, нет идей, что такое характеристическая функция множества, применённая к оператору?

Такие дела.

Но, признаюсь, формула с циклическим интегралом мне понравилась.

P.S.

Цитата:

Брать только те столбцы, норма которых больше $1-\varepsilon$ и которые ортогональны предыдущим взятым столбцам (с точностью до $\varepsilon$).

Прошу прощения, вот это для меня что-то мутновато звучит.

[g______d]

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

Ясно, что не хорошо здесь использовать порочный круг.

Не ясно. И никакого порочного круга здесь, ещё раз, нет. Мы же говорим не о матлогике, а об обычной математике. Вычислимость -- понятие, определяемое в обычной математике: существует функция, которая каждому рациональному аргументу что-то сопоставляет с какой-то оценкой. Функция есть. Оценка есть. Я имею право доказывать оценку как хочу, в том числе и с использованием спектральной теоремы.

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

Кстати, нет идей, что такое характеристическая функция множества, применённая к оператору?

Почитайте более подробнее про спектральную теорему. Если $A=\sum \lambda_i P_i$ -- спектральное разложение, то $f(A)=\sum_i f(\lambda_i)P_i$. Если $f$ -- характерическая функция множества $S$, то получите $f(A)=\sum\limits_{i\colon \lambda_i\in S}P_i$.

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

Но, признаюсь, формула с циклическим интегралом мне понравилась.

Этой формуле, думаю, больше ста лет.

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

Прошу прощения, вот это для меня что-то мутновато звучит.

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