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

[amarsianin]

Цитата:

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

Во-первых, я повторил ваши же слова. А во-вторых, если проблема возникает в этом месте, то посмотрите, например, здесь, стр. 380.

Цитата:

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

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

Цитата:

В этом месте безразлично, вычислим этот базис или нет

Вот эту фразу я не понял. Как это безразлично?

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

[g______d]

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

Во-первых, я повторил ваши же слова.

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

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

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

Я не понимаю, чего тут доказывать. Обе величины (число корней и след проектора) вычислимы и целочисленны. Из спектральной теоремы следует их равенство. Что еще нужно? Доказать это же равенство без спектральной теоремы? А зачем?

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

Вот эту фразу я не понял. Как это безразлично?

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

[amarsianin]

g______d

Да не получается у вас ничего. У вас есть чёрный ящик в виде интеграла, который считает проектор. В вашем алгоритме вы бы и использовали этот ящик как часть процедуры. Классически вам известно, что ящик когда-то должен выплюнуть целые числа в проекторе (даже, наверно, не так, вам ещё, скорее всего, классическая диагонализация проектора нужна), но эффективно вы не можете оценить, когда это произойдёт. Поэтому ваш подход, где вы несколькими постами выше предлагали сравнивать столбцы с $\varepsilon$ не подходит. Хоть конструктивизм, хоть TTE, вы себя за волосы не вытащите из болота. Потому что любое такое утверждение эквивалентно (и это легко показать) тому, что вы можете сравнить с нулём произвольное дйствительное число и на этом всё заканчивается.

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

[g______d]

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

эффективно вы не можете оценить, когда это произойдёт.

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

1) Есть множество $S$, внутри которого заведомо лежит точный спектр оператора.

2) Есть контур, отстоящий на $\varepsilon$ от множества $S$.

3) Есть матрица-функция (рациональная), которую мы интегрируем по этому контуру.

4) Есть эффективная оценка максимума этой функции и максимума ее производной на контуре через $\varepsilon$; в этой оценке используется только тот факт, что точный спектр оператора удален не менее чем на $\varepsilon$ от любой точки контура, что известно из пункта 1. Оценка не будет зависеть от того, где именно на множестве $S$ расположен точный спектр.

5) Из пункта 4 следует, что интеграл можно эффективно вычислить методом прямоугольников с любой наперед заданной точностью $\delta$.

6) Следствием пункта 5 будет матрица с рациональными элементами, которая отличается от точного спектрального проектора на величину $\delta$ по операторной норме. Следовательно, каждый элемент матрицы отличается от элемента точного проектора не более чем на $\delta$.

7) Выберем $\delta<1/3n$. Тогда след вычисленной матрицы будет отличаться от следа точного проектора (т. е. целого числа) не более чем на $1/3$. След точного проектора равен размерности.

[amarsianin]

Цитата:

Есть множество $S$, внутри которого заведомо лежит точный спектр оператора.

Не спектр, а множество корней характеристического полинома.

Цитата:

Есть контур, отстоящий на $\varepsilon$ от множества $S$.

Элементарно. Если каждый корень задан, скажем, рац. аппроксимацией вида $| \lambda_i(n) - \lambda_i(m)| \leq \frac{1}{n} + \frac{1}{m}$, и обозначим $\lambda_{\max}: = \max \{ \lambda_1, \ldots \lambda_n \}$ и $\lambda_{\min}: = \min \{ \lambda_1, \ldots \lambda_n \}$ (причём мы точно не знаем, какой именно корень минимальный, а какой максимальный), то таким контуром может являться окружность с центром в $\frac{\lambda_{\min}+\lambda_{\max}}{2}$ и радиусом $\frac{\lambda_{\min}(n)+\lambda_{\max}(n)}{2} + \frac{5}{n}$, где $\frac{1}{n} \geq \varepsilon$

Цитата:

Есть матрица-функция (рациональная), которую мы интегрируем по этому контуру.

Почему вдруг рац.? В интегранде же $z$ содержится. Или вы сразу хотите взять аппроксимации?

Цитата:

4) Есть эффективная оценка максимума этой функции и максимума ее производной на контуре через $\varepsilon$; в этой оценке используется только тот факт, что точный спектр оператора удален не менее чем на $\varepsilon$ от любой точки контура, что известно из пункта 1. Оценка не будет зависеть от того, где именно на множестве $S$ расположен точный спектр.

Что такое "эффективная оценка"? Не точный спектр, а множество корней хар. полинома. Если тут нужна спектр. теорема, то это как убить муху атомной бомбой.

Цитата:

5) Из пункта 4 следует, что интеграл можно эффективно вычислить методом прямоугольников с любой наперед заданной точностью $\delta$.

Я в этом не сомневался.

Цитата:

6) Следствием пункта 5 будет матрица с рациональными элементами, которая отличается от точного спектрального проектора на величину $\delta$ по операторной норме. Следовательно, каждый элемент матрицы отличается от элемента точного проектора не более чем на $\delta$.

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

Цитата:

7) Выберем $\delta<1/3n$. Тогда след вычисленной матрицы будет отличаться от следа точного проектора (т. е. целого числа) не более чем на $1/3$. След точного проектора равен размерности.

Второй классический факт: след проектора равен размерности подпространства, на который проектор проецирует. Требует точной диагонализации. И базис вы криво вычислите с такой аппроксимацией.

-- 28.04.2016, 08:09 --

Посмотрите, например, http://www.phil.pku.edu.cn/cllc/people/fengye/finitismAndTheLogicOfMathematicalApplications.pdf, страница 243.

[g______d]

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

Не спектр, а множество корней характеристического полинома.

Спектр это и есть множество корней характеристического полинома.

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

Почему вдруг рац.? В интегранде же $z$ содержится. Или вы сразу хотите взять аппроксимации?

Рациональная функция.

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

Что такое "эффективная оценка"?

Явно выписанная функция от $\varepsilon$.

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

Если тут нужна спектр. теорема, то это как убить муху атомной бомбой.

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

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

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

Точный проектор существует в классической математике. Данная процедура показывает (в рамках классической математики), что указанная последовательность проекторов сходится к точному проектору, причём скорость сходимости, если постараться, можно выписать явно. Следовательно, точный проектор как раз существует даже в смысле конструктивного анализа.

-- Чт, 28 апр 2016 00:36:35 --

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

Второй классический факт:

В "computable analysis" я имею право пользоваться классическими фактами. Главное чтобы в формулах для оценок не было ничего не вычислимого, но, как я уже говорил, все эти оценки можно выписать явно.

[amarsianin]

Цитата:

Спектр это и есть множество корней характеристического полинома.

Мы тут вообще-то о вычислимой математике говорим.

Цитата:

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

Ну и пользуйтесь, мне-то что. Только к задаче это не имеет отношения.

Цитата:

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

А это просто чушь.

Цитата:

В "computable analysis" я имею право пользоваться классическими фактами. Главное чтобы в формулах для оценок не было ничего не вычислимого, но, как я уже говорил, все эти оценки можно выписать явно.

Не знаю, какую именно модель вы используете. Ну откройте книжку Вайрауха тогда и найдите мне пример, где он использует такую же аргументацию как вы.

[g______d]

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

Не знаю, какую именно модель вы используете.

Ответьте мне для начала на такие вопросы: предположим, что дано классическое вещественное число $x$ (например, в рамках классического анализа доказано, что оно существует и единственно). Далее, задана последовательность $\{a_n\}$ рациональных чисел с явными формулами, причём средствами классического анализа показано, что $|a_n-x|<\frac{1}{n}$.

1) Является ли число $x$ вычислимым?

2) Если да, то чем это отличается от ситуации, описанной мной (числа -- это матричные элементы классического спектрального проектора)?

[amarsianin]

g______d

Я не понимаю, что вы имеете ввиду под "средствами классического анализа показано, что последовательность с ЯВНЫМИ формулами сходится ...". Если существует регулярная посл-ть Коши рац. чисел (заданная вычислимой функцией на натур. числах), то она сходится к вычислимому вещественному числу. Вы же имели нечто другое ввиду:

Предположим, что $x$ - невычислимое действительное число, сущ. классически. Пусть $\{y_n\}_n$ является (регулярным) представлением вычислимого действительного числа $y$. Тогда $\forall n. | y_n - y | \leq \frac{2}{n}$. Пусть $\forall n. | y_n - x | \leq \frac{2}{n}$. Тогда $y=x$. Получили противоречие.

Это именно то, что вы пытаетесь доказать. Известно, что спектр невычислим, если заранее не известна его мощность, как не вычислимы и собств. вектора, и проекторы, и соотвественно базисы собственных подпространств. Это факт не только из конструктивного, но и вычислимого анализа. У вас же получается, что базисы собственных подпространств вычислимы (через проекторы).

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

[g______d]

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

Предположим, что $x$ - невычислимое действительное число, сущ. классически. Пусть $\{y_n\}_n$ является (регулярным) представлением вычислимого действительного числа $y$. Тогда $\forall n. | y_n - y | \leq \frac{2}{n}$. Пусть $\forall n. | y_n - x | \leq \frac{2}{n}$. Тогда $y=x$. Получили противоречие.

.... следовательно предположение о том, что $x$ было невычислимым, неверно. В данном случае $x=\frac{1}{2\pi I}\oint_{C_i}(A-zI)^{-1}\,dz$.

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

Это именно то, что вы пытаетесь доказать. Известно, что спектр невычислим, если заранее не известна его мощность, как не вычислимы и собств. вектора, и проекторы, и соотвественно базисы собственных подпространств. Это факт не только из конструктивного, но и вычислимого анализа. У вас же получается, что базисы собственных подпространств вычислимы (через проекторы).

Это не то, что я пытаюсь доказать, и никаких базисов собственных подпространств у меня в процессе не получается. Из не-вычислимости базисов собственных подпространств не следует не-вычислимость спектрального проектора на прямую сумму нескольких таких подпространств.

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

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

2) Назовите первый шаг, на котором, по вашему мнению, доказательство вычислимости неправильное.

-- Чт, 28 апр 2016 10:58:16 --

P. S. Спектр вычислим в следующем смысле: функция $A\mapsto \lambda_k(A)$, где $\lambda_k$ обозначает $k$-тое собственное значение с учётом кратности, вычислима.

[amarsianin]

Цитата:

P. S. Спектр вычислим в следующем смысле: функция $A\mapsto \lambda_k(A)$, где $\lambda_k$ обозначает $k$-тое собственное значение с учётом кратности, вычислима.

Что? Можно, пожалуйста, сформулировать чётко? Спектр не вычислим. На входе алгоритма должна быть вычислимая матрица И мощность спектра.

Цитата:

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

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

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

[g______d]

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

Можно, пожалуйста, сформулировать чётко?

Я уже сформулировал достаточно чётко. Есть функция $\lambda_k\colon {\mathbb C}^{n(n-1)/2}\times \mathbb R^{n}\to \mathbb R$, которая самосопряжённой матрице $A$ сопоставляет $k$-тое собственное значение в порядке возрастания с учётом кратности.

(область определения этой функции не $\mathbb C^{n^2}$, потому что матрица должна быть самосопряжённой).

Теорема: функция $\lambda_k$ вычислима. Достаточно точная формулировка?

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

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

Да, заявил. Вы с этим согласны? Я даже формулу с интегралом написал, интеграл -- вычислимая процедура, и даже объяснил, как оценки числа шагов получить.

Если согласны, пойдём дальше. Если нет, объясните.

[amarsianin]

Цитата:

Теорема: функция $\lambda_k$ вычислима. Достаточно точная формулировка?

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

Цитата:

Да, заявил. Вы с этим согласны? Я даже формулу с интегралом написал, интеграл -- вычислимая процедура, и даже объяснил, как оценки числа шагов получить.

Короче говоря, классические проекторы в спектральном разложении вычислимы. Я правильно вас понял?

[g______d]

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

Я не знаю, как трактовать "с учётом кратности".

Стандартная трактовка, принятая в линейной алгебре. Например, если $A=\mathrm{diag}\{1,1,2,3\}$, то $\lambda_1(A)=\lambda_2(A)=1$, $\lambda_3(A)=2$, $\lambda_4(A)=3$.

-- Чт, 28 апр 2016 18:44:46 --

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

Короче говоря, классические проекторы в спектральном разложении вычислимы. Я правильно вас понял?

Классические проекторы на отрезки, составляющие множество $S$, вычислимы.

[amarsianin]

Цитата:

Стандартная трактовка, принятая в линейной алгебре

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

Цитата:

Классические проекторы на отрезки, составляющие множество S, вычислимы.

Что такое проектор на отрезок? Я понимаю только проектор на подпространство.