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

[g______d]

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

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

На входе матрица и число $k$. На выходе величина $\lambda_k(A)$. Вот вам прямое определение этой функции, если уж хотите (для вещественной матрицы)

https://en.wikipedia.org/wiki/Courant_minimax_principle

Это не имеет отношения к делу, просто я к тому, что фраза "спектр невычислим" не имеет смысла вне контекста и ее верность зависит от того, что именно вы называете спектром (множество или мультимножество) и какую топологию вы вводите на пространстве этих множеств/мультимножеств. В частности, отображение $A\mapsto (\lambda_1(A),\lambda_2(A),\ldots,\lambda_n(A))$ вычислимо как отображение из $A$ в $\mathbb R^n$.

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

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

Опять же, это стандартная терминология: если $\Delta\subset \mathbb R$ — отрезок, $A$ — самосопряженная матрица со спектральным разложением $A=\sum_i \lambda_i P_i$, то спектральным проектором $A$, отвечающим отрезку $\Delta$, называется проектор

$$E_A(\Delta)=\sum\limits_{i\colon \lambda_i\in \Delta} P_i.$$

[Toucan]

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

Цитата:

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

amarsianin, замечание за регулярное неправильное цитирование: в заголовке цитаты отсутствует ссылка на цитируемое сообщение.

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

[amarsianin]

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

https://en.wikipedia.org/wiki/Courant_minimax_principle

А вы уверены, что это вычислимая функция?

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

Опять же, это стандартная терминология

Вот интеграл по контуру как раз и равен этим проекторам.

[g______d]

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

Вот интеграл по контуру как раз и равен этим проекторам.

Ну так поэтому они и вычислимы.

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

А вы уверены, что это вычислимая функция?

Да.

[amarsianin]

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

Да.

Можете пояснить, пожалуйста?

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

Ну так поэтому они и вычислимы.

Хорошо. Что не вычислимо в спектральном разложении?

[g______d]

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

Можете пояснить, пожалуйста?

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

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

Хорошо. Что не вычислимо в спектральном разложении?

Не вычислимы отдельные точные собственные вектора. Но это факт из классического анализа: не существует непрерывной функции $f:M_n\to \mathbb R^n$, такой что $f(A)$ является нормированным собственным вектором матрицы $A$ (здесь $M_n$ обозначает множество всех самосопряженных матриц), и доказательство этого тоже тривиально: сколь угодно малым возмущением единичной матрицы можно расщепить пространство на собственные подпространства как угодно.

Вообще, вопросы наподобие вашего вопроса и вопроса по ссылке

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

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

[amarsianin]

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

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

Ничего там не очевидно. Там минимизация по произвольным матрицам. И вообще к чему это?

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

Не вычислимы отдельные точные собственные вектора.

А точные проекторы вычислимы причём конструктивно, это ваши слова. Ваши же слова, что для их вычисления нужна спектральная теорема. Что-то тут не сходится.

И статью я эту знаю прекрасно, и вопрос задал принципиально иной.

[g______d]

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

Там минимизация по произвольным матрицам.

Там условие $Cx=0$, которое масштабно инвариантно, поэтому можно считать, что $\|C\|\le1$.

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

И вообще к чему это?

К тому, что фраза "спектр невычислим" бессмысленна вне контекста.

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

А точные проекторы вычислимы причём конструктивно, это ваши слова.

Да. Точные проекторы, отвечающие отрезкам множества $S$, вычислимы, а проекторы на отдельные собственные вектора -- нет.

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

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

Что значит "нужна для вычисления"? Для вычислительной процедуры вообще никакие теоремы не нужны, это процедура. Для доказательства оценки сходимости этой процедуры -- да, нужна; и что? Оценка сходимости явные и никакой неконструктивной информации из спектральной теоремы не содержат.

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

вопрос задал принципиально иной.

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

-- Сб, 30 апр 2016 00:47:11 --

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

И статью я эту знаю прекрасно

Что-то сомневаюсь, учитывая ваши проблемы с функцией $\lambda_k$. Например, Corollary 9 из этой самой статьи говорит прямым текстом "спектр вычислим", ровно в том смысле, в котором я формулировал выше.

[amarsianin]

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

К тому, что фраза "спектр невычислим" бессмысленна вне контекста.

Я вас понял. Авторы утверждают, что спектр (как В ТОЧНОСТИ множество корней хар. полинома) вычислим. Невычислима его мощность. В данном случае здесь возникает двусмысленность формулировки. В другой литературе я видел, что, наоборот, нельзя доказать, что спектр совпадает с множеством корней хар. полинома.

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

Там условие $Cx=0$, которое масштабно инвариантно, поэтому можно считать, что $\|C\|\le1$.

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

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

Да. Точные проекторы, отвечающие отрезкам множества $S$, вычислимы, а проекторы на отдельные собственные вектора -- нет.

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

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

Оценка сходимости явные и никакой неконструктивной информации из спектральной теоремы не содержат.

Я не совсем понимаю, что имеется ввиду. Допустим, вы можете показать, что интеграл сходится как предел. Но вы не можете показать, что какой-то объект сходится к невычислимому классическмуо объекту. Оценка сходимости к пределу (как модулированной посл-ти Коши) вычислима. А вот доказать, что этот предел и есть классический предел - другое дело. Другими словами, у нас есть два вопроса:

1. Сходимость интеграла
2. Док-во свойств проектора:
2.1 идемпотентность (полагаю, просто)
2.2 коммутативность с данным оператором (тоже)
2.3 размерность подпространства равна числу корней хар. полинома оператора в отрезке
2.4 существование вычислимого базиса подпространства

С пункту 2.3 по хорошему надо смотреть классические теоремы и проверять на вычислительное (или конструктивное) содержание. Я не смотрел в детали, но беглый осмотр показал, что без точной диагонализации самого проектора там никак.

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

Я уже объяснил, как из проекторов получать приближенные собственные вектора.

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

[g______d]

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

Функция должна быть равномерно непрерывной по обоим аргументам.

И что, вам не очевидно, что она таковой является? Это вообще полином от матричных элементов.

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

На пространство, порождённое им?

Да.

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

А проектор, отв. отрезку, проецирует на прямую сумму точных собств. подпространств, отв. точным собств. значениям?

Да.

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

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

Я не знаю точно расстояния от контура до точного спектра, но я знаю оценку этого расстояния снизу (поскольку точный спектр содержится в множестве $S$, а контур от него отделён). Этого достаточно, чтобы написать оценку сверху на модуль непрерывности; никакого точного спектра в этой оценке не будет, будет только сколько-то $\varepsilon$.

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

Допустим, вы можете показать, что интеграл сходится как предел. Но вы не можете показать, что какой-то объект сходится к невычислимому классическмуо объекту. Оценка сходимости к пределу (как модулированной посл-ти Коши) вычислима. А вот доказать, что этот предел и есть классический предел - другое дело.

По-моему, вы создаёте проблему из ничего. Пусть $P_i$ -- классический проектор. Пусть $P_i^{(k)}$ -- его аппроксимация, являющаяся матрицей с рациональными элементами и полученная приближённым вычислением контурного интеграла. Мы можем выбрать процедуру построения $P_i^{(k)}$ так, чтобы

$$ \|P_i-P_i^{(k)}\|<2^{-k}. $$

(для этого достаточно вычислить интеграл с достаточной точностью; количество узлов для этой точности следует из оценки модуля непрерывности).

Эта формула доказывает, что $P_i$ вычислим, ровно по определению вычислимости.

[amarsianin]

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

По-моему, вы создаёте проблему из ничего

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

И вы уверены, что из этой аппроксимации следует мощность (= размерность подпространства) и вычислимость базиса без точной диагонализации проектора? Ведь он же содержит вырожденные собств. значения, если я правильно понимаю.

[g______d]

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

И вы уверены, что из этой аппроксимации следует мощность (= размерность подпространства) и вычислимость базиса без точной диагонализации проектора?

Ну да. Все матричные элементы $P_i$ вычислимы. Следовательно, след (сумма диагональных элементов) вычислим. Кроме того, он является целым числом, равным размерности классического проектора. Если классическое вещественное число вычислимо и про него заведомо известно, что оно является целым, то существует алгоритм, выдающий это целое число за гарантированное число шагов.

Пусть мы вычислили эту размерность и она равна $k$.

Про базис: вычислимы все столбцы проектора $P_i$. Среди этих столбцов есть базис. Следовательно, достаточно знать, какие именно столбцы нужно выбирать. Я уже выше писал, как это сделать: с помощью функции $f(n,k)$. Более подробно (я заменю переменную в следующей формуле, чтобы не обозначать той же буквой). У нас есть последовательность рациональных проекторов $P_i^{(m)}$:

$$ \|P_i-P_i^{(m)}\|<2^{-m}. $$

Выберем $m$ так, чтобы все миноры матриц $P_i^{(m)}$ заведомо отличались от соответствующих миноров $P_i$ не более чем на $f(n,k)/2$. Для этого не нужно знать $P_i$, достаточно иметь оценку из предыдущей формулы, разность миноров можно грубо оценить через норму разности матриц с большим (но фиксированным) коэффициентом. Один из миноров $P_i^{(m)}$ будет по абсолютной величине $\ge f(n,k)$ (по построению этой функции). Столбцы, из которых составлен этот минор, и будут нужными столбцами, которые можно пометить и больше не менять.

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

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

Без разницы. Мы же не мощность спектра считаем, а суммарную кратность=размерность.

[amarsianin]

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

Кроме того, он является целым числом, равным размерности классического проектора

Строго говоря, это ещё надо доказать.

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

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

Не совсем понимаю смысла этой фразы.

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

[g______d]

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

Строго говоря, это ещё надо доказать

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

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

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

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

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

1) Укажите первое (не все, а только первое) утверждение, которое вы считаете неправильным.
2) Объясните, что в этом утверждении вы считаете неправильным.
3) Изложите достаточно подробно своими словами всю процедуру до этого утверждения.

В противном случае игнор.

[amarsianin]

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

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

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

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

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

Ещё раз, мне одолжения не нужны.

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

1) Укажите первое (не все, а только первое) утверждение, которое вы считаете неправильным.

Ответьте на вопрос: вычислим ли базис линейного подпространства, если дана (вычислимая) матрица проекии на него?