Решение сис. линейных уравнений методом Чебышева.

[ha]

Если имеется разряженная матрица с собственными значениями в интервале от $[m;M]$, то для решения системы линейных уравнений можно применить метод Чебышева - построить многочлен $p_n$ n-той степени, такой, что $p_n(0)=1$ и $|p_n(x)|\le c$ при $x\in[m;M]$ с минимально возможным $c=e^{O(-\sqrt{m/M}n)}$. Если есть уравнение $Ax=0$, $x_0$ - первое приближение, то $x_n=p_n(A)(x_0)$ дает приближение к решению (которое равно нулю в данном случае - на практике нужно еще аккуратно учесть правую часть).

Но у меня есть проблема - реальное m может быть на много больше имеющейся у меня оценки. Соотвественно вопрос, как строить многочлены с минимальным (или по крайней мере небольшим) значением \sup_{x\in[m;M]}\frac{-\ln(|p_n(x)|)}{\sqrt{x/M}n}. Желательно иметь для этих многочленов при этом рекурсивную формулу, чтобы их можно было легко рассчитывать для последовательных n.

Меня удивляет, что несмотря на насущность проблемы (M определить сколько-нибудь точно на много проще, чем m), эта задача нигде не упоминается.

[Really]

Цитата:

Но у меня есть проблема - реальное m может быть на много больше имеющейся у меня оценки. Соотвественно вопрос, как строить многочлены с минимальным (или по крайней мере небольшим) значением $\sup_{x\in[m;M]}\frac{-\ln(|p_n(x)|)}{\sqrt{x/M}n}$

Насколько я понял у вас есть какой-то итерационный метод и
вы пытаетесь подобрать параметры. Тогда вопрос: почему вас
не устраивают полиномы Чебышева?

Или вы пытаетесь точнее оценить границы спектра?

[ha]

У меня есть только очень неточная оценка на нижнюю границу спектра (взятая чуть ли не с потолка) - соотвественно метод сходится медленно, хотя мог бы сходится на много быстрее, если бы я знал чему равно m. Поскольку оценить m сколько-нибудь быстро нельзя (по крайней мере я не знаю как), то хочется чтобы метод сам подстраивался под все (ну или хотя бы в широком диапозоне (от $m$ до $\sqrt{Mm}$)) возможные значения реального наименьшего собственного значения.

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

[Really]

Если матрица несимметрична, то спектра вообще говоря невещественен. Вы написали

Цитата:

Если имеется разряженная матрица с собственными значениями в интервале от $[m;M]$...

Вещественность собственных значений следует из каких-то иных соображений?

И как вы ищете нижнюю границу $m$?

[Eugeen1948]

ha писал(а):

Если имеется разряженная матрица с собственными значениями в интервале от $[m;M]$, то для решения системы линейных уравнений можно применить метод Чебышева - построить многочлен $p_n$ n-той степени, такой, что $p_n(0)=1$ и $|p_n(x)|\le c$ при $x\in[m;M]$ с минимально возможным $c=e^{O(-\sqrt{m/M}n)}$. Если есть уравнение $Ax=0$, $x_0$ - первое приближение, то $x_n=p_n(A)(x_0)$ дает приближение к решению (которое равно нулю в данном случае - на практике нужно еще аккуратно учесть правую часть).

Но у меня есть проблема - реальное m может быть на много больше имеющейся у меня оценки. Соотвественно вопрос, как строить многочлены с минимальным (или по крайней мере небольшим) значением \sup_{x\in[m;M]}\frac{-\ln(|p_n(x)|)}{\sqrt{x/M}n}. Желательно иметь для этих многочленов при этом рекурсивную формулу, чтобы их можно было легко рассчитывать для последовательных n.

Меня удивляет, что несмотря на насущность проблемы (M определить сколько-нибудь точно на много проще, чем m), эта задача нигде не упоминается.

Я знаю только одного знатока Чебышевских ускорений итераций - это Лебедев В.И., доктор физмат наук, главный нс ИАЭ им. И.В. Курчатова. Фактически, в конце 60-х он первый теретически обосновал и практически реализовал двухслойные Чебышевские итерационные схемы с оптимальным набором параметров для решения систем ЛУ, что в то время было очень важно для физических расчетов активных зон ВВЭР (ЭВМ тогда были слабенькие, с малой памятью, не то что сейчас!). Я имел честь лично быть знаком с Вячеславом Ивановичем, пользовался его ценнейшими советами при разработке программного комплекса РЕЗАК, где реализовывались его идеи Чебышевских ускорений (в процессе итераций попутно определялись границы спектра СЗ, которые затем использовались для ускорения итераций в нелинейныз задачах).
Основные результаты можно найти в книге:Марчук Г..И., Лебедев В.И.// Численные методы в теории переноса нейтронов, М.: Атомиздат, 1981.
Но, конечно, надо смотреть более поздние публикации:
Лебедев В.И. Функциональный анализ и вычислительная математика.
Лебедев В.И., Ушаков К.В. Явные и неявные чебышевские фильтры и их приложения.

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

[worm2]

ha писал(а):

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

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