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

[amarsianin]

g______d

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

Цитата:

Вычислимость -- понятие, определяемое в обычной математике: существует функция, которая каждому рациональному аргументу что-то сопоставляет с какой-то оценкой.

У вас в "эффективном" алгоритме есть невычислимые фрагменты.

-- 25.04.2016, 08:25 --

Цитата:

Почитайте более подробнее про спектральную теорему

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

[g______d]

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

Неа. Там вводится это понятие без спектральной теоремы.

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

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

не ясно, как из вашей формулы (вычислимо) следует размерность подпространства.

Во-первых, следует так, где $p(z)=\det(A-zI)$:

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

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

Во-вторых, если $P$ — проектор, то размерность подпространства равна его следу. След вычислим, причем точно, т. к. является целым.

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

У вас в "эффективном" алгоритме есть невычислимые фрагменты.

Какие именно?

[amarsianin]

Цитата:

А на предыдущую страницу заглядывали?

В смысле, $f(A)$ - это предел аппроксимации $f$ полиномом, применённым к $A$?

Цитата:

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

Свойство 3 даёт эффективную верхнюю оценку на подынтегральное выражение и все его производные.

А зачем нам это если мы и так знаем суммарную кратность корней в интервалах?

Цитата:

$P$ — проектор, то размерность подпространства равна его следу

Собственно, если опираться на классический результат (в частности теорема Теорема 6.17 книжки Като), то смысл всей этой байды с эффективным алгоритмом нулевой. Я не знаю, какую модель вычислимости вы держите в голове, но если взять стандартную TTE, то такие рассуждения некорректны. У нас сейчас и получается, что мы сразу подразумеваем, что наши проекторы на самом деле и являются точными классическими проекторами. Отсюда и следует размерность/базис подпространства и разделимость спектра. Либо укажите, пож-та, точно где вы именно используете спектральную теорему.

[g______d]

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

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

Когда я записываю проектор в виде интеграла, этот интеграл нужно эффективно вычислить. Для этого нужна оценка модуля непрерывности выражения под интегралом. Для достаточно оценить производную этого выражения. Для этого нужна оценка типа $\|(A-zI)x\|\ge \mathrm{dist}(z,\sigma(A))\|x\|$, которая следует из спектральной теоремы.

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

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

Я не знаю, какую модель вычислимости вы держите в голове, но если взять стандартную TTE, то такие рассуждения некорректны.

Я на первой странице описывал процедуру по пунктам. Из ваших вопросов мне не очевидно, что вы ее прочитали полностью. Прочитайте, пожалуйста, процедуру полностью и объясните, какой именно пункт некорректен с точки зрения TTE. Я мог бы и сам ее здесь повторить, но мне уже жалко на это тратить время.

[amarsianin]

Цитата:

Я мог бы и сам ее здесь повторить, но мне уже жалко на это тратить время.

Мне не надо одолжений. Не хотите - просто не пишите.

Но пару ремарок я всё-таки сделаю.

Цитата:

Для этого нужна оценка модуля непрерывности выражения под интегралом

Модуль непрерывности не может быть функцией от спектра, который не вычислим и не located (не знаю, как перевести). В смысле, множество собств. значений (не спектр) не located (нельзя вычислить расстояние от него до произвольного$z$. Но я, если честно, не вижу никакого смысла приплетать тут спектральную теорему. Такую оценку можно было и с множеством собств. значений $\{ \lambda_1, ... \lambda_n \}$ построить ... наверно. Я думаю, вы её используете не в этом, а в том, что ваши проекторы на самом деле классические или вы классически полагаете, что они проецируют на подпространства с нужными размерностью и базисом.

Цитата:

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

Не понял вас тут.

Я думаю, в вашем алгоритме будет нечто, вроде, "если эта бинарная посл-ть не может состоять из одних нулей, то где-то в ней в конечном итоге есть единица". Это сейчас касается вычисления базиса. У вас есть некоторое классическое утверждение, на которое вы полагаетесь и поэтому уверены, что алгоритм остановится. Но я не знаю, какая модель вычислимости такое допускает.

[g______d]

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

Модуль непрерывности не может быть функцией от спектра, который не вычислим и не located (не знаю, как перевести). В смысле, множество собств. значений (не спектр) не located (нельзя вычислить расстояние от него до произвольного$z$. Но я, если честно, не вижу никакого смысла приплетать тут спектральную теорему. Такую оценку можно было и с множеством собств. значений $\{ \lambda_1, ... \lambda_n \}$ построить ... наверно. Я думаю, вы её используете не в этом, а в том, что ваши проекторы на самом деле классические или вы классически полагаете, что они проецируют на подпространства с нужными размерностью и базисом.

Короче говоря, ни черта вы так и не прочитали. Модуль непрерывности будет вычислимой функцией от матрицы благодаря этой лемме, примененной к $p(z)=\det(A-zI)$

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

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

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

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

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

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

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

Что значит "думаю"? У меня описана процедура; мне кажется, довольно подробно. Если вы не хотите в ней разобраться, а тыкаете пальцем в случайные места и называете их нестыковками, я не знаю, как я могу вам помочь.

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

Это сейчас касается вычисления базиса.

Давайте вопрос с базисом временно отложим и договоримся об остальной части. Согласны ли вы, что построен эффективный набор из чисел $\lambda'_1,\ldots,\lambda'_k$ и взаимно ортогональных проекторов $P_1,\ldots,P_k$, таких что $\|A-\sum_j\lambda'_j P_j\|\le\varepsilon$?

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

-- Пн, 25 апр 2016 11:55:54 --

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

У вас есть некоторое классическое утверждение, на которое вы полагаетесь и поэтому уверены, что алгоритм остановится. Но я не знаю, какая модель вычислимости такое допускает.

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

[amarsianin]

Цитата:

Давайте вопрос с базисом временно отложим и договоримся об остальной части. Согласны ли вы, что построен эффективный набор из чисел $\lambda'_1,\ldots,\lambda'_k$ и взаимно ортогональных проекторов $P_1,\ldots,P_k$, таких что $\|A-\sum_j\lambda'_j P_j\|\le\varepsilon$?

Разумеется. Я же сам и привёл такую оценку в ОП. И для этого вам не нужна спектральная теорема. А те три свойства множества $S$, можно показать и так.

Цитата:

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

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

Вобщем, давайте лучше всё-таки к базису и размерностям подпространств перейдём. Вот я, если честно, так и не понял, используете ли вы ТУТ спектральную теорему или нет. Потому что один раз вы сказали, что да, а потом сказали, что используете только при построении модуля непрерывности интегранда.

-- 25.04.2016, 20:05 --

Кстати, насчёт $f(A)$ я прав или нет?

[g______d]

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

Кстати, насчёт $f(A)$ я прав или нет?

Если $f$ непрерывна, то да. Если разрывна (как характеристическая функция), то нужно аккуратнее с приближением полиномами. Но если $f$ и $g$ совпадают на спектре $A$, то $f(A)=g(A)$, и для матриц любая функция определяется своими значениями на спектре, т. е. на конечном множестве точек.

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

Потому что один раз вы сказали, что да, а потом сказали, что используете только при построении модуля непрерывности интегранда.

Ну так это и означает "да". Мне же нужен этот интеграл, чтобы построить проекторы.

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

Вобщем, давайте лучше всё-таки к базису и размерностям подпространств перейдём.

Хорошо, давайте начнем с размерностей. Проекторы $P_k$ вычислимы, след $P_k$ целочисленный и равен размерности. Осталось только найти базис, правильно?

[amarsianin]

Цитата:

Если $f$ непрерывна, то да

Характеристические функции в конструктивной/вычислимой математике немного иначе определяются, чем классические. Строго говоря, не непрерывных функций вообще не бывает в этом контексте. Впрочем, проехали, я понял.

Цитата:

Ну так это и означает "да". Мне же нужен этот интеграл, чтобы построить проекторы.

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

Цитата:

Хорошо, давайте начнем с размерностей. Проекторы $P_k$ вычислимы, след $P_k$ целочисленный и равен размерности. Осталось только найти базис, правильно?

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

[g______d]

Про базис. Наверняка есть существенно более эффективный алгоритм, но:

Лемма: существует вычислимая функция $f(n,k)>0$, такая что у любого $n\times n$ - проектора на подпространство размерности $k$ хотя бы один минор размерности $k$ больше либо равен $f(n,k)$. Опять же, мне лень ее выписывать, но я могу, если надо.

После этого, если вам дан проектор, можно сначала вычислить его размерность (через след), потом перебрать все миноры.

-- Пн, 25 апр 2016 12:48:45 --

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

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

Да, возможно, здесь можно без нее, просто оценка будет более грубой, чем с ней.

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

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

Я не понимаю, при чем здесь принцип Маркова и в чем проблема. Есть алгоритм, на входе рациональные числа, на выходе рациональные числа, можно написать формулу (очень длинную) для числа его шагов при $\varepsilon=1/N$ как функцию $N$. Какие именно факты я использую при доказательстве оценки количества шагов — не должно никого волновать.

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

[amarsianin]

g______d


Благодарю за участие.
Завтра посмотрю, что с этим можно сделать. Но, скорее всего, если размерность известна, то такая функция существует. Я не понимаю, откуда следует эта размерность (кроме как из классического проектора).

-- 25.04.2016, 20:49 --

Цитата:

просто оценка будет более грубой, чем с ней.

Что совершенно не проблематично.

[amarsianin]

Цитата:

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

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

[g______d]

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

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

Ну формально говоря в том, что эти контурные интегралы будут ортогональными проекторами с нужными свойствами: т. е. что они проектируют на подпространства, инвариантные относительно $A$, и сужение оператора $A$ на соответствующее подпространство близко по операторной норме к оператору умножения на $\lambda_i$.

На самом деле, если подумать

1) Тот факт, что они являются проекторами, коммутирующими с $A$, — верен и в несамосопряженном случае, поэтому спектральная теорема не нужна (см. Като, раздел I.5.4).

2) Тот факт, что это ортогональные проекторы, следует из самосопряженности $A$ (так же, как и их взаимная ортогональность друг другу).

3) Дальше, пусть $P_i$ — проектор, построенный с помощью интеграла по контуру $C_i$, и $\lambda_i$ — любая точка внутри этого контура. Я использую тот факт, что $\|P_i(A-\lambda_i)P_i\|\le \mathrm{diam}(C_i)$ — вот здесь уже нужна спектральная теорема.
Более грубую оценку (и тоже достаточную, если мы не следим за степенями), наверное, можно получить без нее.

Проблема в том, что конечномерная спектральная теорема — не такой сложный факт и фактически следует из первых двух пунктов: спектр оператора $A$ конечен, окружим каждую точку спектра контуром, тогда оператор будет ортогональной суммой самосопряженных операторов, спектр каждого их которых состоит из одной точки. Далее, доказать, что самосопряженный оператор, у которого спектр состоит из одной точки, скалярный.

[amarsianin]

Цитата:

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

Вот именно. Вот об этом я и говорил выше.

Впрочем,

Цитата:

Тот факт, что они являются проекторами, коммутирующими с $A$

2) Тот факт, что это ортогональные проекторы, следует из самосопряженности $A$ (так же, как и их взаимная ортогональность друг другу).

Можно доказать без спектральной теоремы.

Цитата:

Дальше, пусть $P_i$ — проектор, построенный с помощью интеграла по контуру $C_i$, и $\lambda_i$ — любая точка внутри этого контура. Я использую тот факт, что $\|P_i(A-\lambda_i)P_i\|\le \mathrm{diam}(C_i)$ — вот здесь уже нужна спектральная теорема.
Более грубую оценку (и тоже достаточную, если мы не следим за степенями), наверное, можно получить без нее.

Но ведь контур мы задали в явном виде как окружность радиуса $\varepsilon$ с центром в центре интервала.

Цитата:

если мы не следим за степенями

Какими степенями? Хар. полинома?

Цитата:

Проблема в том, что

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

[g______d]

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

Но ведь контур мы задали в явном виде как окружность радиуса $\varepsilon$ с центром в центре интервала.

Ну хорошо, замените $\mathrm{diam}{C_i}$ на $2\varepsilon$. Как вы будете доказывать эту оценку нормы? Т. е. что $\|P_i (A-\lambda_i) P_i\|\le 2\varepsilon$.

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

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

Плохо понимаю, в чем проблема. Если мы доказали, что $P_i$ — ортогональные проекторы, то их следы являются целыми,
это стандартный факт из линейной алгебры; например, инвариантность следа и существование ортогонального базиса в подпространстве. В этом месте безразлично, вычислим этот базис или нет, поскольку след вычислим сам по себе.

Базис я тоже предложил выше, как находить, перебором всех миноров:

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

Лемма: существует вычислимая функция $f(n,k)>0$, такая что у любого $n\times n$ - проектора на подпространство размерности $k$ хотя бы один минор размерности $k$ больше либо равен $f(n,k)$. Опять же, мне лень ее выписывать, но я могу, если надо.