Журнал вычислительной математики и математической физики, 2020, T. 60, № 11, стр. 1823-1841

Вычисление асимптотических спектральных распределений для последовательностей сеточных операторов

С. В. Морозов^1, 2, *, С. Серра-Капиццано^3, 4, **, Е. Е. Тыртышников^{1, 2, 5, 6, ***}

¹ МГУ
119991 Москва, Ленинские горы, 1, Россия

² ИВМ РАН им. Г.И. Марчука
119333 Москва, ул. Губкина, 8, Россия

³ Университет Инсубрии
22100 Комо, Виа Валеджио, 11, Италия

⁴ Университет Уппсалы
SE-751 05 Уппсала, 337 Уппсала, Швеция

⁵ Университет Седльце, Седльце
08-110 Седльце, ул. Житная, 17/19, Польша

⁶ Московский центр фундаментальной и прикладной математики
Москва, Россия

^* E-mail: stanis-morozov@yandex.ru
^** E-mail: stefano.serrac@uninsubria.it
^*** E-mail: eugene.tyrtyshnikov@gmail.com

Поступила в редакцию 23.03.2020
После доработки 11.05.2020
Принята к публикации 07.07.2020

DOI: 10.31857/S0044466920110095

Полный текст (PDF)

Аннотация

Изучаются асимптотические спектральные свойства матриц сеточных операторов на полигональных областях на плоскости при измельчении заданной треугольной сетки. Существующие методы анализа спектральных распределений во многом опираются на инструмент теории обобщенных локально-тёплицевых последовательностей (GLT-теория). В этой работе показано, что матрицы сеточных операторов на непрямоугольных областях не образуют GLT-последовательностей. Вместе с тем предложен метод вычисления спектральных распределений и для таких случаев. Введены обобщения GLT-последовательностей и предложены использующие их предобуславливатели. Библ. 22. Фиг. 6.

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

1. ВВЕДЕНИЕ

В последние десятилетия происходит активное развитие теории, связанной с изучением спектральных свойств матричных последовательностей. Большинство существующих статей на эту тему можно разделить на две категории: работы, изучающие общий характер распределения собственных значений и сингулярных чисел последовательности матриц [1], например, для последовательностей матриц, возникающих в результате дискретизации уравнений в частных производных, и работы, изучающие асимптотическое поведение отдельных собственных значений больших тёплицевых матриц (см. [1]–[10]). В последние годы распространение получил аппарат теории обобщенных локально-тёплицевых последовательностей матриц (GLT, Generalized Locally Toeplitz) [4]. Существует множество примеров использования GLT-теории для изучения спектральных свойств последовательностей матриц, возникающих при решении уравнений в частных производных, однако, вопрос о расширении области применимости теории GLT-последовательностей остается открытым. В этой работе мы предлагаем пример, демонстрирующий, что GLT-теория может быть недостаточна для описания спектральных распределений матриц дискретизации даже простейших операторов, заданных на непрямоугольных областях. В то же время мы обнаружили, что во многих случаях последовательности матриц могут быть сведены к GLT-последовательностям с помощью преобразований подобия. Последнее наблюдение позволило построить обобщение, дающее возможность работать с операторами, определенными на непрямоугольных областях. Для того чтобы не ограничивать результаты конкретными дифференциальными операторами и методами дискретизации, все рассуждения изложены в терминах сеточных операторов.

2. ПРЕДВАРИТЕЛЬНЫЕ СВЕДЕНИЯ

2.1. Спектральные свойства последовательностей тёплицевых матриц

Классически понятие распределения собственных значений для последовательности матриц ${{{\text{\{ }}{{A}_{n}}{\text{\} }}}_{n}}$, где размер ${{A}_{n}}$ равен $n$, определяется следующим образом:

Определение 1. Будем говорить, что последовательность матриц ${{{\text{\{ }}{{A}_{n}}{\text{\} }}}_{n}}$ имеет распределение собственных значений с символом $f$ в области $D$ ненулевой конечной меры $(\mu (D) \ne 0,\infty )$, если

(1)

$\mathop {lim}\limits_{n \to \infty } \frac{1}{n}\sum\limits_{j = 1}^n F ({{\lambda }_{j}}({{A}_{n}})) = \frac{1}{{\mu (D)}}\int\limits_D F (f(x))dx$

для любой непрерывной функции $F$ с компактным носителем $(F \in {{C}_{C}}(\mathbb{C}))$, где ${{\lambda }_{j}}(A)$ обозначает собственные значения матрицы $A$. Будем обозначать это ${{{\text{\{ }}{{A}_{n}}{\text{\} }}}_{n}}{{ \sim }_{\lambda }}f$.

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

Определение 2. Будем говорить, что последовательность матриц ${{{\text{\{ }}{{A}_{n}}{\text{\} }}}_{n}}$ имеет распределение сингулярных чисел с символом $f$ в области $D$ ненулевой конечной меры $(\mu (D) \ne 0,\infty )$, если

(2)

$\mathop {lim}\limits_{n \to \infty } \frac{1}{n}\sum\limits_{j = 1}^n F ({{\sigma }_{j}}({{A}_{n}})) = \frac{1}{{\mu (D)}}\int\limits_D {F\left( {\left| {f(x)} \right|} \right)} dx$

для любой непрерывной функции $F$ с компактным носителем $(F \in {{C}_{C}}(\mathbb{R}))$, где ${{\sigma }_{j}}(A)$ обозначает сингулярные числа матрицы $A$. Будем обозначать это как ${{{\text{\{ }}{{A}_{n}}{\text{\} }}}_{n}}{{ \sim }_{\sigma }}f$.

Пусть дана некоторая функция $f \in {{L}_{1}}( - \pi ,\pi )$. Разложим эту функцию в формальный ряд Фурье

(3)

$f(x) = \sum\limits_{j = - \infty }^\infty {{{f}_{j}}} {{e}^{{ijx}}}$

и определим элементы тёплицевой матрицы ${{T}_{n}}$ как ${{({{T}_{n}})}_{{i,j}}} = {{f}_{{i - j}}}$. Тогда последовательность матриц ${{{\text{\{ }}{{T}_{n}}{\text{\} }}}_{n}}$ будет иметь распределение сингулярных чисел с символом $\left| f \right|$, а если все матрицы в последовательности являются эрмитовыми, то и распределение собственных значений с символом $f$ в области $[ - \pi ,\pi ]$ (см. [2], [5], [6]).

2.2. Классы аппроксимирующих последовательностей

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

Определение 3. Пусть ${{{\text{\{ }}{{A}_{n}}{\text{\} }}}_{n}}$ является последовательностью матриц. Аппроксимирующим классом последовательностей для ${{{\text{\{ }}{{A}_{n}}{\text{\} }}}_{n}}$ называется последовательность матричных последовательностей ${{{\text{\{ \{ }}{{B}_{{n,m}}}{{{\text{\} }}}_{n}}{\text{\} }}}_{m}}$ со следующим свойством: для каждого $m$ существует ${{n}_{m}}$ такое, что при $n \geqslant {{n}_{m}}$

(4)

${{A}_{n}} = {{B}_{{n,m}}} + {{R}_{{n,m}}} + {{N}_{{n,m}}},$

(5)

$rank({{R}_{{n,m}}}) \leqslant c(m)n,\quad \left\| {{{N}_{{n,m}}}} \right\| \leqslant \omega (m),$

где величины ${{n}_{m}}$, $c(m)$, $\omega (m)$ зависят только от $m$ и

(6)

$\mathop {lim}\limits_{m \to \infty } c(m) = \mathop {lim}\limits_{m \to \infty } \omega (m) = 0.$

Для дальнейшего изложения полезным будет ввести метрическую формулировку понятия классов аппроксимирующих последовательностей [11]. Пусть $A \in {{\mathbb{C}}^{{n \times n}}}$. Тогда обозначим

(7)

${{p}_{n}}(A) = \mathop {min}\limits_{i = 0,\; \ldots ,\;n} \left( {\frac{i}{n} + {{\sigma }_{{i + 1}}}(A)} \right),$

где по определению положим ${{\sigma }_{{n + 1}}}(A) = 0$. Введем функцию

(8)

${{p}_{{a.c.s.}}}({{{\text{\{ }}{{A}_{n}}{\text{\} }}}_{n}}) = \mathop {lim\,sup}\limits_{n \to \infty } \,{{p}_{n}}({{A}_{n}}) = \mathop {lim\,sup}\limits_{n \to \infty } \mathop {min}\limits_{i = 0,\; \ldots ,\;n} \left( {\frac{i}{n} + {{\sigma }_{{i + 1}}}({{A}_{n}})} \right)$

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

(9)

${{d}_{{a.c.s.}}}({{{\text{\{ }}{{A}_{n}}{\text{\} }}}_{n}},{{{\text{\{ }}{{B}_{n}}{\text{\} }}}_{n}}) = {{p}_{{a.c.s.}}}({{{\text{\{ }}{{A}_{n}} - {{B}_{n}}{\text{\} }}}_{n}})$

является псевдометрикой на множестве матричных последовательностей [12], причем последовательность ${{{\text{\{ \{ }}{{B}_{{n,m}}}{{{\text{\} }}}_{n}}{\text{\} }}}_{m}}$ является классом аппроксимирующих последовательностей для ${{{\text{\{ }}{{A}_{n}}{\text{\} }}}_{n}}$ тогда и только тогда, когда

(10)

$\mathop {lim}\limits_{m \to \infty } {{d}_{{a.c.s.}}}({{{\text{\{ }}{{A}_{n}}{\text{\} }}}_{n}},{{{\text{\{ \{ }}{{B}_{{n,m}}}{{{\text{\} }}}_{n}}{\text{\} }}}_{m}}) = 0.$

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

Теорема 1. Пусть ${{{\text{\{ }}{{A}_{n}}{\text{\} }}}_{n}}$ – матричная последовательность. Предположим, что

1. ${{{\text{\{ \{ }}{{B}_{{n,m}}}{{{\text{\} }}}_{n}}{\text{\} }}}_{m}}$ является классом аппроксимирующих последовательностей для ${{\{ {{A}_{n}}\} }_{n}}$;

2. для любого $m$ ${{{\text{\{ }}{{B}_{{n,m}}}{\text{\} }}}_{n}}{{ \sim }_{\sigma }}{{f}_{m}}$ для некоторой измеримой функции ${{f}_{m}}:D \subset {{\mathbb{R}}^{k}} \to \mathbb{C}$;

3. ${{f}_{m}} \to f$ по мере в $D$, где $f:D \to \mathbb{C}$ – измеримая функция.

Тогда ${{{\text{\{ }}{{A}_{n}}{\text{\} }}}_{n}}{{ \sim }_{\sigma }}f$.

Теорема 2. Пусть ${{{\text{\{ }}{{A}_{n}}{\text{\} }}}_{n}}$ – последовательность эрмитовых матриц. Предположим, что

1. ${{{\text{\{ \{ }}{{B}_{{n,m}}}{{{\text{\} }}}_{n}}{\text{\} }}}_{m}}$ является классом аппроксимирующих последовательностей для ${{{\text{\{ }}{{A}_{n}}{\text{\} }}}_{n}}$, где все матрицы в ${{{\text{\{ \{ }}{{B}_{{n,m}}}{{{\text{\} }}}_{n}}{\text{\} }}}_{m}}$ эрмитовы;

2. для любого $m$ ${{{\text{\{ }}{{B}_{{n,m}}}{\text{\} }}}_{n}}{{ \sim }_{\lambda }}{{f}_{m}}$ для некоторой измеримой функции ${{f}_{m}}:D \subset {{\mathbb{R}}^{k}} \to \mathbb{C}$;

3. ${{f}_{m}} \to f$ по мере в $D$, где $f:D \to \mathbb{C}$ — измеримая функция.

Тогда ${{{\text{\{ }}{{A}_{n}}{\text{\} }}}_{n}}{{ \sim }_{\lambda }}f$.

Приведенные теоремы, в частности, позволяют доказать, что если имеются последовательности тёплицевых матриц ${{\left\{ {T_{n}^{{(1)}}} \right\}}_{n}},\; \ldots ,\;{{\left\{ {T_{n}^{{(k)}}} \right\}}_{n}}$ с символами ${{f}^{{(1)}}},\; \ldots ,\;{{f}^{{(k)}}}$ соответственно, то

(11)

${{\left\{ {T_{n}^{{(1)}} \cdot \ldots \cdot T_{n}^{{(k)}}} \right\}}_{n}}{{ \sim }_{\sigma }}\left| {{{f}^{{(1)}}} \cdot \ldots \cdot {{f}^{{(k)}}}} \right|$

(12)

${{\left\{ {T_{n}^{{(1)}} \cdot \ldots \cdot T_{n}^{{(k)}}} \right\}}_{n}}{{ \sim }_{\lambda }}{{f}^{{(1)}}} \cdot \ldots \cdot {{f}^{{(k)}}},$

если все матрицы эрмитовы.

2.3. Локально-тёплицевы матрицы

Пусть функция $a:[0,\;1] \to \mathbb{C}$ интегрируема по Риману и обозначим

(13)

${{D}_{n}}(a) = \mathop {diag}\limits_{i = 1,\; \ldots ,\;n} a\left( {\frac{i}{n}} \right).$

Известен следующий результат [13]:

Теорема 3. Пусть $a:[0,\;1] \to \mathbb{C}$ интегрируема по Риману, $f \in {{L}_{1}}( - \pi ,\pi )$. Тогда сингулярные числа последовательности матриц ${{{\text{\{ }}{{D}_{n}}(a){{T}_{n}}(f){\text{\} }}}_{n}}$ распределены с символом $\kappa (x,\theta ) = a(x)f(\theta )$, а если все матрицы в последовательности эрмитовы, то и собственные значения распределены с символом $\kappa (x,\theta ) = a(x)f(\theta )$ в области $[0,1] \times [ - \pi ,\pi ]$.

Замечание 1. Собственные значения последовательности ${{{\text{\{ }}{{A}_{n}}{\text{\} }}}_{n}}$ распределены с символом $\kappa (x,\theta ) = a(x)f(\theta )$ в области $[0,1] \times [ - \pi ,\pi ]$. Значит,

(14)

$\mathop {lim}\limits_{n \to \infty } \frac{1}{n}\sum\limits_{j = 1}^n F ({{\lambda }_{j}}({{A}_{n}})) = \frac{1}{{2\pi }}\int\limits_0^1 {\int\limits_{ - \pi }^\pi F (\kappa (x,\theta ))d\theta dx} .$

Аналогичные теоремы верны и для многоуровневых тёплицевых матриц и функций $a(x)$, зависящих от многих переменных. Данные результаты естественным образом приводят к идее GLT-последовательностей.

Здесь и далее для обозначения векторов будем использовать жирный шрифт. Также жирным шрифтом будем обозначать мультииндексы с естественной лексикографической нумерацией. Рассмотрим множество пар многоуровневых тёплицевых матриц, порожденных символами ${{e}^{{ij\theta }}}$, и соответствующих символов

(15)

$T = \left\{ {\left( {{{{\left\{ {{{T}_{n}}({{e}^{{ij\theta }}})} \right\}}}_{n}},{{e}^{{ij\theta }}}} \right):{\mathbf{j}} \in {{\mathbb{Z}}^{d}}} \right\},$

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

(16)

$\mathcal{D} = \left\{ {\left( {{{{\left\{ {{{D}_{n}}(a)} \right\}}}_{n}},a} \right):a \in {{C}^{\infty }}({{{[0,1]}}^{d}})} \right\}.$

Введем поэлементные операции на парах такого вида, а также поэлементную операцию сопряжения. Построим минимальную *-алгебру, содержащую множество $\mathcal{T} \cup \mathcal{D}$ и обозначим ее $\mathcal{A}$. Можно доказать, что если пара $({{{\text{\{ }}{{A}_{n}}\} }_{n}},g) \in \mathcal{A}$, то сингулярные числа последовательности ${{{\text{\{ }}{{A}_{n}}{\text{\} }}}_{n}}$ распределены с символом $g$ в области ${{[0,1]}^{d}} \times {{[ - \pi ,\pi ]}^{d}}$, а если все ${{A}_{n}}$ эрмитовы, то собственные значения распределены с тем же символом.

Построенную алгебру $\mathcal{A}$ можно расширить еще больше, используя теоремы 1, 2. А именно, введем на множестве пар матричных последовательностей $\mathcal{E}$ и измеримых функций $M$ псевдометрику

(17)

$d(({{{\text{\{ }}{{A}_{n}}{\text{\} }}}_{n}},\kappa ),({{{\text{\{ }}{{B}_{n}}{\text{\} }}}_{n}},\xi )) = {{d}_{{a.c.s.}}}({{{\text{\{ }}{{A}_{n}}{\text{\} }}}_{n}},{{{\text{\{ }}{{B}_{n}}{\text{\} }}}_{n}}) + {{d}_{\mu }}(\kappa ,\xi ),$

где ${{d}_{\mu }}$ – псевдометрика, соответствующая сходимости по мере:

(18)

${{d}_{\mu }}(\kappa ,\xi ) = q(\kappa - \xi ),$

(19)

$q(\psi ) = inf{\text{\{ }}\mu {\text{\{ }}\left| \psi \right| \geqslant \alpha {\text{\} }} + \alpha :\alpha > 0{\text{\} }}.$

Замыкание алгебры $\mathcal{A}$ по псевдометрике (9) называется классом GLT-последовательностей [4], [14], [15]. Если пара $({{{\text{\{ }}{{A}_{n}}{\text{\} }}}_{n}},g)$ принадлежит классу GLT-последовательностей, то $g$ называется GLT-символом последовательности ${{{\text{\{ }}{{A}_{n}}{\text{\} }}}_{n}}{{ \sim }_{{{\text{GLT}}}}}g$. Можно доказать, что GLT-символ определен единственным образом с точностью до меры нуль [13]. Несколько простых свойств вытекает из того, что класс GLT-последовательностей является алгеброй и замкнут относительно сходимости по псевдометрике (9). Кроме того, GLT-символ всегда соответствует распределению сингулярных чисел последовательности матриц, а в случае эрмитовой последовательности также и распределению собственных значений. Отметим три менее очевидных, но важных для дальнейшего свойства [13].

• ${{{\text{\{ }}{{Z}_{n}}{\text{\} }}}_{n}}{{ \sim }_{{{\text{GLT}}}}}0$ тогда и только тогда, когда ${{{\text{\{ }}{{Z}_{n}}{\text{\} }}}_{n}}{{ \sim }_{\sigma }}0$; в этом случае последовательность называется нуль-распределенной.

• Если ${{{\text{\{ }}{{A}_{n}}{\text{\} }}}_{n}}{{ \sim }_{{{\text{GLT}}}}}\kappa $ и $\kappa \ne 0$ почти всюду, то ${{\{ A_{n}^{\dag }\} }_{n}}{{ \sim }_{{{\text{GLT}}}}}{{\kappa }^{{ - 1}}}$.

• Если ${{{\text{\{ }}{{A}_{n}}{\text{\} }}}_{n}}{{ \sim }_{{{\text{GLT}}}}}\kappa $ и каждая матрица ${{A}_{n}}$ эрмитова, то ${{{\text{\{ }}f({{A}_{n}}){\text{\} }}}_{n}}{{ \sim }_{{{\text{GLT}}}}}f(\kappa )$ для любой непрерывной функции $f:\mathbb{R} \to \mathbb{C}$.

3. НАХОЖДЕНИЕ РАСПРЕДЕЛЕНИЯ СПЕКТРА МАТРИЦ ДИСКРЕТИЗАЦИИ В ТРЕУГОЛЬНЫХ ОБЛАСТЯХ

3.1. Постановка задачи

Пусть заданы некоторая область $\Omega $ и сетка ${{\Omega }_{h}}$. Пусть также определен сеточный оператор ${{\mathcal{L}}_{h}}:{{\Omega }_{h}} \to {{\Omega }_{h}}$, на пространстве функций, заданных на ${{\Omega }_{h}}$.

Для изучения спектральных свойств матрицы оператора ${{\mathcal{L}}_{h}}$ часто рассматривают последовательность измельчающихся сеток ${{{\text{\{ }}{{\Omega }_{{h(n)}}}{\text{\} }}}_{n}}$ и операторов ${{{\text{\{ }}{{\mathcal{L}}_{h}}_{{(n)}}{\text{\} }}}_{n}}$, заданных на них. Пусть задана некоторая нумерация узлов сетки ${{\Omega }_{h}}$ и ${{({{u}_{h}})}_{k}}$ обозначает значение сеточной функции ${{u}_{h}}$ в $k$-м узле. Введем следующее

Определение 4. Сеточный оператор ${{\mathcal{L}}_{h}}$ имеет размер шаблона $K$, если для любого $k$ ${{({{\mathcal{L}}_{h}}{{u}_{h}})}_{k}}$ зависит только от значений ${{u}_{h}}$ в тех узлах сетки, кратчайшее расстояние до которых по ребрам сетки не превосходит $K$. Последовательность сеточных операторов имеет размер шаблона $K$, если все операторы последовательности имеют размер шаблона не более $K$.

Будем считать, что последовательность сеточных операторов ${{{\text{\{ }}{{\mathcal{L}}_{h}}_{{(n)}}{\text{\} }}}_{n}}$ имеет конечный размер шаблона. Это предположение верно для большинства классических методов дискретизации уравнений в частных производных.

Последовательность операторов ${{{\text{\{ }}{{\mathcal{L}}_{{h(n)}}}{\text{\} }}}_{n}}$ естественным образом задает последовательность матриц операторов ${{{\text{\{ }}{{A}_{n}}{\text{\} }}}_{n}}$ с растущими размерами. Для широкого класса сеточных операторов спектральное распределение последовательности матриц ${{{\text{\{ }}{{A}_{n}}{\text{\} }}}_{n}}$ может быть получено с помощью GLT-теории [13] в случае, если ${{\Omega }_{h}}$ представляет из себя параллелепипед. В противном случае классическая GLT-теория предлагает строить сетки в области $\Omega $ с помощью методов изогеометрического анализа [16], [17], приводящего к сеткам, задаваемым отображением $G:{{[0,1]}^{d}} \to \bar {\Omega }$. Данный подход имеет ряд недостатков, в частности, он плохо позволяет строить адаптивные сетки и контролировать измельчение сетки в разных областях $\Omega $. Кроме того, при использовании метода конечных элементов для дискретизации уравнений в частных производных часто требуется аналитическое вычисление интегралов от базисных функций, что может оказаться невозможным для сложных отображений $G$. По этой причине далее рассмотрены задачи, в которых заранее задана последовательность измельчающихся сеток на областях, отличных от параллелепипеда.

3.2. Операторы с постоянными коэффициентами

В качестве области $\Omega $ рассмотрим треугольник (фиг. 1). Введем на $\Omega $ равномерную сетку ${{\Omega }_{h}}$, т.е. сетку, полученную в результате разбиения исходного треугольника на равные, подобные ему треугольники. Введем естественную нумерацию вершин, согласованную с образующими векторами.

Фиг. 1.

Равномерная сетка на треугольнике и нумерация, индуцируемая образующими.

Пусть оператор ${{\mathcal{L}}_{h}}$ действует на внутренние узлы сетки согласно шаблону, изображенному на фиг. 2, по формуле

(20)

${{({{\mathcal{L}}_{h}}{{u}_{h}})}_{k}} = {{t}_{0}}u_{k}^{{(0)}} + {{t}_{1}}(u_{k}^{{(3)}} + u_{k}^{{(6)}}) + {{t}_{2}}(u_{k}^{{(2)}} + u_{k}^{{(5)}}) + {{t}_{3}}(u_{k}^{{(1)}} + u_{k}^{{(4)}})$

одинаковой для всех внутренних узлов сетки. Будем считать, что $t_{2}^{2} + t_{3}^{2} > 0$. Оператор такого вида, в частности, получается при дискретизации оператора Лапласа на треугольной сетке методом конечных элементов.

Фиг. 2.

Шаблон сеточного оператора.

Для того чтобы выписать матрицу сеточного оператора (20), представим, для начала, что мы решаем задачу не в треугольнике, а в параллелограмме, натянутом на те же самые образующие векторы. Матрица ${{T}_{n}}$ дискретизации на параллелограмме будет иметь следующий вид:

(21)

${{T}_{4}} = \left[ {\begin{array}{*{20}{c}} {\begin{array}{*{20}{c}} {{{t}_{0}}}&{{{t}_{1}}}&{}&{}&\vline & {{{t}_{3}}}&{}&{}&{}&\vline & {}&{}&{}&{}&\vline & {}&{}&{}&{} \\ {{{t}_{1}}}&{{{t}_{0}}}&{{{t}_{1}}}&{}&\vline & {{{t}_{2}}}&{{{t}_{3}}}&{}&{}&\vline & {}&{}&{}&{}&\vline & {}&{}&{}&{} \\ {}&{{{t}_{1}}}&{{{t}_{0}}}&{{{t}_{1}}}&\vline & {}&{{{t}_{2}}}&{{{t}_{3}}}&{}&\vline & {}&{}&{}&{}&\vline & {}&{}&{}&{} \\ {}&{}&{{{t}_{1}}}&{{{t}_{0}}}&\vline & {}&{}&{{{t}_{2}}}&{{{t}_{3}}}&\vline & {}&{}&{}&{}&\vline & {}&{}&{}&{} \\ \hline {{{t}_{3}}}&{{{t}_{2}}}&{}&{}&\vline & {{{t}_{0}}}&{{{t}_{1}}}&{}&{}&\vline & {{{t}_{3}}}&{}&{}&{}&\vline & {}&{}&{}&{} \\ {}&{{{t}_{3}}}&{{{t}_{2}}}&{}&\vline & {{{t}_{1}}}&{{{t}_{0}}}&{{{t}_{1}}}&{}&\vline & {{{t}_{2}}}&{{{t}_{3}}}&{}&{}&\vline & {}&{}&{}&{} \\ {}&{}&{{{t}_{3}}}&{{{t}_{2}}}&\vline & {}&{{{t}_{1}}}&{{{t}_{0}}}&{{{t}_{1}}}&\vline & {}&{{{t}_{2}}}&{{{t}_{3}}}&{}&\vline & {}&{}&{}&{} \\ {}&{}&{}&{{{t}_{3}}}&\vline & {}&{}&{{{t}_{1}}}&{{{t}_{0}}}&\vline & {}&{}&{{{t}_{2}}}&{{{t}_{3}}}&\vline & {}&{}&{}&{} \\ \hline {}&{}&{}&{}&\vline & {{{t}_{3}}}&{{{t}_{2}}}&{}&{}&\vline & {{{t}_{0}}}&{{{t}_{1}}}&{}&{}&\vline & {{{t}_{3}}}&{}&{}&{} \\ {}&{}&{}&{}&\vline & {}&{{{t}_{3}}}&{{{t}_{2}}}&{}&\vline & {{{t}_{1}}}&{{{t}_{0}}}&{{{t}_{1}}}&{}&\vline & {{{t}_{2}}}&{{{t}_{3}}}&{}&{} \\ {}&{}&{}&{}&\vline & {}&{}&{{{t}_{3}}}&{{{t}_{2}}}&\vline & {}&{{{t}_{1}}}&{{{t}_{0}}}&{{{t}_{1}}}&\vline & {}&{{{t}_{2}}}&{{{t}_{3}}}&{} \\ {}&{}&{}&{}&\vline & {}&{}&{}&{{{t}_{3}}}&\vline & {}&{}&{{{t}_{1}}}&{{{t}_{0}}}&\vline & {}&{}&{{{t}_{2}}}&{{{t}_{3}}} \\ \hline {}&{}&{}&{}&\vline & {}&{}&{}&{}&\vline & {{{t}_{3}}}&{{{t}_{2}}}&{}&{}&\vline & {{{t}_{0}}}&{{{t}_{1}}}&{}&{} \\ {}&{}&{}&{}&\vline & {}&{}&{}&{}&\vline & {}&{{{t}_{3}}}&{{{t}_{2}}}&{}&\vline & {{{t}_{1}}}&{{{t}_{0}}}&{{{t}_{1}}}&{} \\ {}&{}&{}&{}&\vline & {}&{}&{}&{}&\vline & {}&{}&{{{t}_{3}}}&{{{t}_{2}}}&\vline & {}&{{{t}_{1}}}&{{{t}_{0}}}&{{{t}_{1}}} \\ {}&{}&{}&{}&\vline & {}&{}&{}&{}&\vline & {}&{}&{}&{{{t}_{3}}}&\vline & {}&{}&{{{t}_{1}}}&{{{t}_{0}}} \end{array}} \end{array}} \right],$

т.е. являться двухуровневой тёплицевой матрицей. Тогда матрица дискретизации $\hat {T}_{n}^{'}$ для треугольника получается из нее удалением последних строки и столбца из второго блока, последних двух строк и столбцов из третьего блока и т.д.:

(22)

$\hat {T}_{4}^{'} = \left[ {\begin{array}{*{20}{c}} {\begin{array}{*{20}{c}} {{{t}_{0}}}&{{{t}_{1}}}&{}&{}&\vline & {{{t}_{3}}}&{}&{}&\vline & {}&{}&\vline & {} \\ {{{t}_{1}}}&{{{t}_{0}}}&{{{t}_{1}}}&{}&\vline & {{{t}_{2}}}&{{{t}_{3}}}&{}&\vline & {}&{}&\vline & {} \\ {}&{{{t}_{1}}}&{{{t}_{0}}}&{{{t}_{1}}}&\vline & {}&{{{t}_{2}}}&{{{t}_{3}}}&\vline & {}&{}&\vline & {} \\ {}&{}&{{{t}_{1}}}&{{{t}_{0}}}&\vline & {}&{}&{{{t}_{2}}}&\vline & {}&{}&\vline & {} \\ \hline {{{t}_{3}}}&{{{t}_{2}}}&{}&{}&\vline & {{{t}_{0}}}&{{{t}_{1}}}&{}&\vline & {{{t}_{3}}}&{}&\vline & {} \\ {}&{{{t}_{3}}}&{{{t}_{2}}}&{}&\vline & {{{t}_{1}}}&{{{t}_{0}}}&{{{t}_{1}}}&\vline & {{{t}_{2}}}&{{{t}_{3}}}&\vline & {} \\ {}&{}&{{{t}_{3}}}&{{{t}_{2}}}&\vline & {}&{{{t}_{1}}}&{{{t}_{0}}}&\vline & {}&{{{t}_{2}}}&\vline & {} \\ \hline {}&{}&{}&{}&\vline & {{{t}_{3}}}&{{{t}_{2}}}&{}&\vline & {{{t}_{0}}}&{{{t}_{1}}}&\vline & {{{t}_{3}}} \\ {}&{}&{}&{}&\vline & {}&{{{t}_{3}}}&{{{t}_{2}}}&\vline & {{{t}_{1}}}&{{{t}_{0}}}&\vline & {{{t}_{2}}} \\ \hline {}&{}&{}&{}&\vline & {}&{}&{}&\vline & {{{t}_{3}}}&{{{t}_{2}}}&\vline & {{{t}_{0}}} \end{array}} \end{array}} \right].$

Будем называть матрицы такого вида усеченными тёплицевыми матрицами. Покажем, что последовательность матриц $\hat {T}_{n}^{'}$ не является GLT-последовательностью. Заметим, что последовательность матриц, составленная только из диагональных блоков матриц $\hat {T}_{n}^{'}$, образует GLT-последовательность. Действительно, мы можем “склеить” диагонали, содержащие величины ${{t}_{1}}$, добавив в матрицу $2(n - 1)$ элементов, где размер матрицы равен $\tfrac{{n(n + 1)}}{2}$. Поэтому такое дополнение является симметричным преобразованием малого ранга и не выводит из класса GLT. Но в силу того, что класс GLT-последовательностей образует алгебру, и трехдиагональные матрицы принадлежат GLT, диагональные блоки матриц $\hat {T}_{n}^{'}$ можно занулить и работать с последовательностью матриц ${{\hat {T}}_{n}}$ следующего вида:

(23)

${{\hat {T}}_{4}} = \left[ {\begin{array}{*{20}{c}} {}&{}&{}&{}&\vline & {{{t}_{3}}}&{}&{}&\vline & {}&{}&\vline & {} \\ {}&{}&{}&{}&\vline & {{{t}_{2}}}&{{{t}_{3}}}&{}&\vline & {}&{}&\vline & {} \\ {}&{}&{}&{}&\vline & {}&{{{t}_{2}}}&{{{t}_{3}}}&\vline & {}&{}&\vline & {} \\ {}&{}&{}&{}&\vline & {}&{}&{{{t}_{2}}}&\vline & {}&{}&\vline & {} \\ \hline {{{t}_{3}}}&{{{t}_{2}}}&{}&{}&\vline & {}&{}&{}&\vline & {{{t}_{3}}}&{}&\vline & {} \\ {}&{{{t}_{3}}}&{{{t}_{2}}}&{}&\vline & {}&{}&{}&\vline & {{{t}_{2}}}&{{{t}_{3}}}&\vline & {} \\ {}&{}&{{{t}_{3}}}&{{{t}_{2}}}&\vline & {}&{}&{}&\vline & {}&{{{t}_{2}}}&\vline & {} \\ \hline {}&{}&{}&{}&\vline & {{{t}_{3}}}&{{{t}_{2}}}&{}&\vline & {}&{}&\vline & {{{t}_{3}}} \\ {}&{}&{}&{}&\vline & {}&{{{t}_{3}}}&{{{t}_{2}}}&\vline & {}&{}&\vline & {{{t}_{2}}} \\ \hline {}&{}&{}&{}&\vline & {}&{}&{}&\vline & {{{t}_{3}}}&{{{t}_{2}}}&\vline & {} \end{array}} \right].$

Предположим, что ${{\hat {T}}_{n}}$ имеет некоторое GLT-распределение в области ${{[0,1]}^{2}} \times {{[ - \pi ,\pi ]}^{2}}$, т.е. ${{{\text{\{ }}{{\hat {T}}_{n}}{\text{\} }}}_{n}}{{ \sim }_{{{\text{GLT}}}}}f({{x}_{1}},{{x}_{2}},{{\theta }_{1}},{{\theta }_{2}})$.

Заметим, что матрица $\hat {T}$ имеет размерность $\tfrac{{n(n + 1)}}{2} \times \tfrac{{n(n + 1)}}{2}$. Введем жорданов блок ${{J}_{n}}$ размерности $n \times n$:

(24)

${{J}_{n}} = \left[ {\begin{array}{*{20}{c}} 0&1&{}&{}&{}&{} \\ 0&0&1&{}&{}&{} \\ {}&0&0&1&{}&{} \\ {}&{}& \ddots & \ddots & \ddots &{} \\ {}&{}&{}&0&0&1 \\ {}&{}&{}&{}&0&0 \end{array}} \right].$

Тогда обозначим ${{\hat {J}}_{n}} = {{J}_{{[n/\sqrt 2 ]}}} \otimes {{I}_{{[n/\sqrt 2 ]}}}$. Это двухуровневая тёплицева матрица, она принадлежит классу GLT-последовательностей, и для нее известно распределение ${{{\text{\{ }}{{\hat {J}}_{n}}{\text{\} }}}_{n}}{{ \sim }_{{{\text{GLT}}}}}{{e}^{{ - i{{\theta }_{1}}}}}$. Заметим, что $\mathop {\left[ {\tfrac{n}{{\sqrt 2 }}} \right]}\nolimits^2 - \tfrac{{n(n + 1)}}{2} = O(n)$, а это значит, что мы можем продолжить диагонали в матрице ${{\hat {J}}_{n}}$ до порядка матрицы $\tfrac{{n(n + 1)}}{2}$ малоранговым преобразованием. Полученную матрицу обозначим ${{R}_{n}}$. Она имеет то же самое распределение, что ${{\hat {J}}_{n}}$ и порядок $\tfrac{{n(n + 1)}}{2} \times \tfrac{{n(n + 1)}}{2}$.

Рассмотрим последовательность ${{{\text{\{ }}{{\hat {T}}_{n}}{{R}_{n}} - {{R}_{n}}{{\hat {T}}_{n}}{\text{\} }}}_{n}}$. В силу алгебраических свойств GLT-теории, эта последовательность должна быть нуль-распределенной. Наша ближайшая цель – доказать, что это не так.

Заметим, что умножение ${{\hat {T}}_{n}}{{R}_{n}}$ выполняет сдвиг элементов матрицы ${{\hat {T}}_{n}}$ вправо. Аналогично ${{R}_{n}}{{\hat {T}}_{n}}$ выполняет сдвиг элементов матрицы вверх. Матрицы ${{\hat {T}}_{n}}$ имеют блочную структуру. Вычислим номера столбцов, в которых начинаются блоки матрицы ${{\hat {T}}_{n}}$, а также куда они перейдут после умножений ${{\hat {T}}_{n}}{{R}_{n}}$ и ${{R}_{n}}{{\hat {T}}_{n}}$. Изначально номера столбцов, в которых начинаются блоки матрицы ${{\hat {T}}_{n}}$, – это $n$, $n + (n - 1)$ и т.д.; $k$-й блок имеет номер первого столбца

$\sum\nolimits_{j = 1}^k n - j + 1 = k(n + 1) - \frac{{k(k + 1)}}{2}$

После умножения ${{\hat {T}}_{n}}$ на ${{R}_{n}}$ номера всех столбцов увеличатся на $\left[ {\tfrac{n}{{\sqrt 2 }}} \right]$, в то время как при умножении ${{R}_{n}}$ на ${{\hat {T}}_{n}}$ номера столбцов не изменятся. Рассмотрим произвольный блок матрицы, лежащий выше главной диагонали и содержащий ${{t}_{3}}$. Будем считать, что ${{t}_{3}} \ne 0$, в противном случае доказательство можно провести аналогично для ${{t}_{2}} \ne 0$. Одновременно ${{t}_{2}}$ и ${{t}_{3}}$ нулями быть не могут, так как в противном случае треугольник выродится в отрезок или точку. Рассмотрим диагональ матрицы ${{\hat {T}}_{n}}$, лежащую выше главной диагонали и содержащую элементы ${{t}_{3}}$. Заметим, что эта диагональ матрицы ${{\hat {T}}_{n}}$ при сдвиге и вправо, и вверх на одинаковое количество элементов, перейдет в одну и ту же диагональ (в данном случае мы понимаем под диагональю множество элементов матрицы ${{[{{\hat {T}}_{n}}]}_{{ij}}}$ таких, что разность $i - j$ постоянна). Размер $k$-го наддиагонального блока равен $n - k$. Тогда диагональ рассматриваемого блока при сдвиге вверх будет иметь номера столбцов

с $k(n + 1) - \tfrac{{k(k + 1)}}{2}$ до $k(n + 1) - \tfrac{{k(k + 1)}}{2} + n - k.$

В то время как при сдвиге вправо номера

с $k(n + 1) - \tfrac{{k(k + 1)}}{2} + \left[ {\tfrac{n}{{\sqrt 2 }}} \right]$ до $k(n + 1) - \tfrac{{k(k + 1)}}{2} + \left[ {\tfrac{n}{{\sqrt 2 }}} \right] + n - k.$

Тогда при вычитании в матрице останутся значения ${{t}_{3}}$ на позициях

с $k(n + 1) - \tfrac{{k(k + 1)}}{2} + n - k + 1$ до $k(n + 1) - \tfrac{{k(k + 1)}}{2} + \left[ {\tfrac{n}{{\sqrt 2 }}} \right] + n - k$

(т.е. $\left[ {\tfrac{n}{{\sqrt 2 }}} \right]$ элементов) при условии, что

(25)

$k(n + 1) - \frac{{k(k + 1)}}{2} + n - k \geqslant k(n + 1) - \frac{{k(k + 1)}}{2} + \left[ {\frac{n}{{\sqrt 2 }}} \right],$

(26)

$n - \left[ {\frac{n}{{\sqrt 2 }}} \right] \geqslant k.$

Это будет верно для всех блоков, номера которых удовлетворяют неравенству выше и элементы которых не исчезают из матрицы при сдвигах вверх и вправо, т.е. таких, что номера $k$ этих блоков удовлетворяют неравенству

$2 \leqslant k \leqslant n - \left[ {\frac{n}{{\sqrt 2 }}} \right].$

Тогда в результирующей матрице ${{\hat {T}}_{n}}{{R}_{n}} - {{R}_{n}}{{\hat {T}}_{n}}$ останется, по крайней мере,

(27)

$\left( {n - \left[ {\frac{n}{{\sqrt 2 }}} \right] - 1} \right)\left[ {\frac{n}{{\sqrt 2 }}} \right] \geqslant {{C}_{0}}\frac{{n(n + 1)}}{2}$

элементов, равных ${{t}_{3}}$, где ${{C}_{0}} > 0$. Ясно, что в случае, когда ${{t}_{3}} = 0$, доказательство проводится полностью аналогично для элементов ${{t}_{2}}$.

Тогда $\left\| {{{{\hat {T}}}_{n}}} \right\|_{F}^{2} \geqslant C\frac{{n(n + 1)}}{2}$. Кроме того, очевидно, что ${{\left\| {{{{\hat {T}}}_{n}}} \right\|}_{1}} \leqslant 4\left( {\left| {{{t}_{2}}} \right| + \left| {{{t}_{3}}} \right|} \right)$ и ${{\left\| {{{{\hat {T}}}_{n}}} \right\|}_{\infty }} \leqslant 4\left( {\left| {{{t}_{2}}} \right| + \left| {{{t}_{3}}} \right|} \right)$, следовательно, ${{\left\| {{{{\hat {T}}}_{n}}} \right\|}_{2}} \leqslant 4\left( {\left| {{{t}_{2}}} \right| + \left| {{{t}_{3}}} \right|} \right)$. Мы имеем, что $\sum\nolimits_k^{} {\sigma _{k}^{2}} \geqslant C\tfrac{{n(n + 1)}}{2}$, но $\sigma _{1}^{2} \leqslant 16{{\left( {\left| {{{t}_{2}}} \right| + \left| {{{t}_{3}}} \right|} \right)}^{2}}$. Предположим, что хотя бы $\delta \tfrac{{n(n + 1)}}{2}$ сингулярных чисел меньше $\varepsilon $, $\sum\nolimits_1 {\sigma _{k}^{2}} + \sum\nolimits_2 {\sigma _{k}^{2}} \geqslant C\frac{{n(n + 1)}}{2}$, где $\sum\nolimits_2 {\kern 1pt} $ обозначает сумму по минимальным $\delta \tfrac{{n(n + 1)}}{2}$ элементам, а $\sum\nolimits_1 {\kern 1pt} $ – по всем оставшимся. Тогда $\sum\nolimits_1^{} {\sigma _{k}^{2}} \geqslant (C - \delta {{\varepsilon }^{2}})\frac{{n(n + 1)}}{2}$:

(28)

$\sigma _{1}^{2}(1 - \delta )\frac{{n(n + 1)}}{2} \geqslant \sum\limits_1 {\sigma _{k}^{2}} \geqslant (C - \delta {{\varepsilon }^{2}})\frac{{n(n + 1)}}{2},$

(29)

$16{{\left( {\left| {{{t}_{2}}} \right| + \left| {{{t}_{3}}} \right|} \right)}^{2}}(1 - \delta ) \geqslant C - \delta {{\varepsilon }^{2}},$

(30)

$\delta \leqslant \frac{{16{{{\left( {\left| {{{t}_{2}}} \right| + \left| {{{t}_{3}}} \right|} \right)}}^{2}} - C}}{{16{{{\left( {\left| {{{t}_{2}}} \right| + \left| {{{t}_{3}}} \right|} \right)}}^{2}} - {{\varepsilon }^{2}}}}.$

Причем из формул для ${{t}_{2}}$ и ${{t}_{3}}$ не могут быть равны нулю одновременно. Выбирая $\varepsilon = \tfrac{{\sqrt C }}{2}$, получаем, что больше, чем $\delta \tfrac{{n(n + 1)}}{2}$ (где $\delta < 1$), элементов меньше $\varepsilon $ быть не может, следовательно, хотя бы $(1 - \delta )\tfrac{{n(n + 1)}}{2}$ сингулярных чисел будут больше $\varepsilon $, а значит, последовательность не является нуль-распределенной. Значит, наше предположение о том, что последовательность ${{\{ {{\hat {T}}_{n}}{\text{\} }}}_{n}}$ является GLT-последовательностью, было неверно.

Из доказанного следует, что при дискретизации уравнения Пуассона в треугольной области с равномерной сеткой с помощью МКЭ полученная последовательность матриц не будет являться GLT-последовательностью.

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

Несмотря на то что рассмотренные матричные последовательности не являются GLT-последовательностями, они по-прежнему обладают некоторым распределением собственных значений и сингулярных чисел. Более того, оказывается, что функции распределения собственных значений и сингулярных чисел будут точно такими же, как если бы мы рассматривали задачу с тем же самым оператором в параллелограмме, где последовательности матриц дискретизации оказываются GLT-последовательностями.

Достроим треугольник с образующими до параллелограмма с теми же образующими, и возьмем в качестве области $\Omega $ построенный параллелограмм. Тогда, как отмечалось выше, матрица сеточного оператора будет иметь вид (21). Это двухуровневая тёплицева матрица, являющаяся GLT-последовательностью с символом ${{t}_{0}} + 2{{t}_{3}}cos{{\theta }_{1}} + 2{{t}_{1}}cos{{\theta }_{2}} + 2{{t}_{2}}cos({{\theta }_{1}} - {{\theta }_{2}})$. Введем новый оператор ${{\hat {\mathcal{L}}}_{h}}$, который совпадает с ${{\mathcal{L}}_{h}}$ из (20) всюду, кроме диагонали параллелограмма, а на диагонали равен $0$. С точки зрения матриц операторов это преобразование эквивалентно симметричному преобразованию малого ранга, поскольку затрагивает $O(n)$ столбцов при размере матрицы $O({{n}^{2}})$. Следовательно, оно не меняет GLT-символа последовательности. Теперь изменим нумерацию узлов в триангуляции области. Перенумеруем узлы таким образом, чтобы сначала нумеровался один треугольник, а затем другой (фиг. 3).

Фиг. 3.

Сетка на параллелограмме и разбиение параллелограмма на $2$ треугольника.

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

(31)

${{P}_{n}}{{T}_{n}}P_{n}^{{\text{т}}} = \left[ {\begin{array}{*{20}{c}} {{{{\hat {T}}}_{n}}}&0 \\ 0&{{{{\hat {T}}}_{n}}} \end{array}} \right],$

где ${{\hat {T}}_{n}}$ является матрицей дискретизации для соответствующего треугольника. Причем совершенные нами преобразования являются преобразованиями подобия, а следовательно, не меняют собственных значений и сингулярных чисел. Отсюда следует, что последовательности матриц ${{{\text{\{ }}{{T}_{n}}{\text{\} }}}_{n}}$ и ${{\{ {{\hat {T}}_{n}}{\text{\} }}}_{n}}$ имеют одинаковые распределения собственных значений и сингулярных чисел.

3.4. Обобщение на случай операторов с переменными коэффициентами

Утверждения, описанные и доказанные выше, в действительности верны для гораздо более широкого семейства операторов, в том числе для операторов, зависящих от значений некоторых функций в узлах сетки. Пусть $\Omega = {{\Omega }_{T}}$ – область, являющаяся равнобедренным прямоугольным треугольником с образующими ${{(0,1)}^{{\text{т}}}}$ и ${{(1,0)}^{{\text{т}}}}$. Пусть в этой области заданы некоторая непрерывная функция $a(x,y)$ и оператор ${{\mathcal{L}}_{h}}$, шаблон которого изображен на фиг. 2, действует следующим образом:

(32)

${{({{\mathcal{L}}_{h}}{{u}_{h}})}_{k}} = a({{x}_{k}},{{y}_{k}})({{t}_{0}}u_{k}^{{(0)}} + {{t}_{1}}(u_{k}^{{(3)}} + u_{k}^{{(6)}}) + {{t}_{2}}(u_{k}^{{(2)}} + u_{k}^{{(5)}}) + {{t}_{3}}(u_{k}^{{(1)}} + u_{k}^{{(4)}})),$

где $({{x}_{k}},{{y}_{k}})$ – координата $k$-го узла сетки.

Достроим треугольник до квадрата с образующими ${{(0,1)}^{{\text{т}}}}$ и ${{(1,0)}^{{\text{т}}}}$. На треугольнике, натянутом на эти образующие, функция $a(x,y)$ уже определена. Доопределим функцию $a(x,y)$ на всем квадрате, используя центральную симметрию относительно центра квадрата, т.е. определим

$a(x,y) = a(1 - x,1 - y),\quad y \geqslant 1 - x.$

Перейдем к оператору ${{\hat {\mathcal{L}}}_{h}}$, который совпадает с $\mathcal{L}$ во всех узлах, кроме диагонали параллелограмма и равен $0$ на диагонали $x + y = 1$, что будет соответствовать симметричному малоранговому преобразованию, а затем перенумеруем вершины так, что матрица будет иметь блочно-диагональную структуру с двумя равными блоками на диагонали. В результате получим, что распределение собственных значений матрицы оператора $\mathcal{L}$ (32) совпадает с распределением собственных значений для того же оператора в квадрате, где функция $a(x,y)$ продолжена по центральной симметрии на весь квадрат.

В общем случае техника выглядит следующим образом. Пусть имеется оператор $\mathcal{L}$ с конечным размером шаблона, возможно, зависящий от некоторых функций, заданных на области $\Omega $, где $\Omega $ – некоторый треугольник, заданный своими образующими. Построим параллелограмм, натянутый на эти образующие, и доопределим все функции по центральной симметрии на этом параллелограмме, таким образом, продолжив оператор $\mathcal{L}$ на весь параллелограмм. Введем сетку на треугольнике $\Omega $ и отобразим ее по центральной симметрии на весь параллелограмм. Тогда, если последовательность матриц сеточного оператора новой задачи имеет некоторое распределение собственных значений или сингулярных чисел, то последовательность матриц исходного сеточного оператора имеет то же самое распределение собственных значений или сингулярных чисел.

4. ОБОБЩЕНИЕ GLT-ПОСЛЕДОВАТЕЛЬНОСТЕЙ

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

Определение 5. Будем говорить, что последовательность матриц ${{{\text{\{ }}{{A}_{n}}{\text{\} }}}_{n}}$ принадлежит классу $GLT_{U}^{k}$ с символом $f(x,\theta )$ в области $D$, если существует последовательность унитарных матриц ${{{\text{\{ }}{{U}_{n}}{\text{\} }}}_{n}}$ и число $k$, том числе последовательность матриц $U_{n}^{ * }{{B}_{n}}{{U}_{n}}$ является GLT-последовательностью с символом $f(x,\theta )$ в области $D$, где ${{B}_{n}}$ – блочно-диагональная матрица, состоящая из $k$ блоков на диагонали, равных ${{A}_{n}}$:

(33)

${{B}_{n}} = \left[ {\begin{array}{*{20}{c}} {{{A}_{n}}}&0&0 \\ 0& \ddots &0 \\ 0&0&{{{A}_{n}}} \end{array}} \right].$

В частности, множество классических GLT-последовательностей в этих обозначениях будет совпадать с $GLT_{I}^{1}$.

Заметим, что последовательность матриц сеточных операторов ${{{\text{\{ }}{{A}_{n}}{\text{\} }}}_{n}}$ получалась следующим образом. Строилась последовательность

(34)

${{B}_{n}} = \left[ {\begin{array}{*{20}{c}} {{{A}_{n}}}&0 \\ 0&{{{A}_{n}}} \end{array}} \right],$

затем к ней применялось симметричное малоранговое преобразование, а затем преобразование подобия с матрицами перестановки. Ясно, что последние два преобразования можно поменять местами (в том смысле, что сначала можно применить преобразование подобия с матрицами перестановки, а потом применить симметричное малоранговое преобразование к другим строкам и столбцам). Но малоранговое преобразование не выводит из класса GLT-последовательностей, следовательно, если с его помощью мы приходили к матрице, являющейся GLT-последовательностью, то и без него мы получим матрицу из того же самого класса. Отсюда следует, что последовательность матриц дискретизации на треугольнике принадлежит классу $GLT_{P}^{2}$ для некоторой последовательности матриц перестановки ${{{\text{\{ }}{{P}_{n}}{\text{\} }}}_{n}}$.

Оказывается, что последовательности матриц каждого из классов $GLT_{U}^{k}$ обладают свойствами, аналогичными классическим GLT-последовательностям. Докажем некоторые из этих свойств.

Теорема 4. Пусть ${{{\text{\{ }}{{A}_{n}}{\text{\} }}}_{n}}$ и ${{{\text{\{ }}{{B}_{n}}{\text{\} }}}_{n}}$ принадлежат классу $GLT_{U}^{k}$ для некоторых ${{{\text{\{ }}{{U}_{n}}{\text{\} }}}_{n}}$ и $k$ с символами $f(x,\theta )$ и $g(x,\theta )$ соответственно в области $D$. Тогда последовательности матриц ${{{\text{\{ }}{{A}_{n}} + {{B}_{n}}{\text{\} }}}_{n}}$, ${{{\text{\{ }}{{A}_{n}}{{B}_{n}}{\text{\} }}}_{n}}$, ${{{\text{\{ }}\alpha {{A}_{n}}{\text{\} }}}_{n}}$ и ${{{\text{\{ }}A_{n}^{ * }{\text{\} }}}_{n}}$ принадлежат классу $GLT_{U}^{k}$ с символами $f(x,\theta ) + g(x,\theta )$, $f(x,\theta )g(x,\theta )$, $\alpha f(x,\theta )$ и $\bar {f}(x,\theta )$ соответственно в области $D$.

Доказательство. Докажем утверждение, например, для случая произведения матричных последовательностей. Остальные случаи доказываются аналогично. Так как последовательности ${{{\text{\{ }}{{A}_{n}}{\text{\} }}}_{n}}$ и ${{{\text{\{ }}{{B}_{n}}{\text{\} }}}_{n}}$ принадлежат $GLT_{U}^{k}$, то последовательности

(35)

${{\hat {A}}_{n}} = {{U}_{n}}\left[ {\begin{array}{*{20}{c}} {{{A}_{n}}}&0&0 \\ 0& \ddots &0 \\ 0&0&{{{A}_{n}}} \end{array}} \right]U_{n}^{ * }\quad {\text{и}}\quad {{\hat {B}}_{n}} = {{U}_{n}}\left[ {\begin{array}{*{20}{c}} {{{B}_{n}}}&0&0 \\ 0& \ddots &0 \\ 0&0&{{{B}_{n}}} \end{array}} \right]U_{n}^{ * }$

являются GLT-последовательностями с символами $f(x,\theta )$ и $g(x,\theta )$. Тогда последовательность ${{\{ {{\hat {A}}_{n}}{{\hat {B}}_{n}}{\text{\} }}}_{n}}$, с одной стороны, имеет GLT-распределение $f(x,\theta )g(x,\theta )$, а с другой стороны, равна ${{U}_{n}}\left[ {\begin{array}{*{20}{c}} {{{A}_{n}}{{B}_{n}}}&0&0 \\ 0& \ddots &0 \\ 0&0&{{{A}_{n}}{{B}_{n}}} \end{array}} \right]U_{n}^{ * }$. Откуда и следует, что ${{{\text{\{ }}{{A}_{n}}{{B}_{n}}{\text{\} }}}_{n}}$ принадлежит $GLT_{U}^{k}$ с символом $f(x,\theta )g(x,\theta )$.

Теорема 5. Пусть последовательность матриц ${{{\text{\{ }}{{A}_{n}}{\text{\} }}}_{n}}$ принадлежит классу $GLT_{U}^{k}$ с символом $f(x,\theta )$ в области $D$. Тогда ${{{\text{\{ }}{{A}_{n}}{\text{\} }}}_{n}}{{ \sim }_{\sigma }}f(x,\theta )$ в области $D$. Если матрицы ${{A}_{n}}$ эрмитовы, то ${{{\text{\{ }}{{A}_{n}}{\text{\} }}}_{n}}{{ \sim }_{\lambda }}f(x,\theta )$ в области $D$.

Доказательство. Очевидно из определения.

Теорема 6. Пусть последовательность матриц ${{{\text{\{ }}{{A}_{n}}{\text{\} }}}_{n}}$ принадлежит классу $GLT_{U}^{k}$ с символом $f(x,\theta ) \ne 0$ почти всюду. Тогда последовательность матриц ${{\{ A_{n}^{\dag }\} }_{n}}$ принадлежит классу $GLT_{U}^{k}$ с символом ${{f}^{{ - 1}}}(x,\theta )$.

Доказательство. Последовательность ${{\hat {A}}_{n}} = {{U}_{n}}\left[ {\begin{array}{*{20}{c}} {{{A}_{n}}}&0&0 \\ 0& \ddots &0 \\ 0&0&{{{A}_{n}}} \end{array}} \right]U_{n}^{ * }$ является GLT-последовательностью с символом $f(x,\theta ) \ne 0$ почти всюду, следовательно, ${{U}_{n}}\left[ {\begin{array}{*{20}{c}} {A_{n}^{\dag }}&0&0 \\ 0& \ddots &0 \\ 0&0&{A_{n}^{\dag }} \end{array}} \right]U_{n}^{ * } = \hat {A}_{n}^{\dag }$ имеет GLT-распределение ${{f}^{{ - 1}}}(x,\theta )$.

Теорема 7. Пусть последовательность матриц ${{{\text{\{ }}{{A}_{n}}{\text{\} }}}_{n}}$ принадлежит классу $GLT_{U}^{k}$ с символом $f(x,\theta )$ и все матрицы ${{A}_{n}}$ эрмитовы. Тогда последовательность матриц ${{{\text{\{ }}g({{A}_{n}}){\text{\} }}}_{n}}$ принадлежит классу $GLT_{U}^{k}$ с символом $g(f(x,\theta ))$ для любой непрерывной функции $g:\mathbb{R} \to \mathbb{C}$.

Доказательство. Последовательность ${{\hat {A}}_{n}} = {{U}_{n}}\left[ {\begin{array}{*{20}{c}} {{{A}_{n}}}&0&0 \\ 0& \ddots &0 \\ 0&0&{{{A}_{n}}} \end{array}} \right]U_{n}^{ * }$ является GLT-последовательностью с символом $f(x,\theta )$, следовательно, $g{{(\hat {A})}_{n}} = {{U}_{n}}\left[ {\begin{array}{*{20}{c}} {g({{A}_{n}})}&0&0 \\ 0& \ddots &0 \\ 0&0&{g({{A}_{n}})} \end{array}} \right]U_{n}^{ * }$ имеет GLT-распределение $g(f(x,\theta ))$.

Теорема 8. Последовательность матриц ${{{\text{\{ }}{{A}_{n}}{\text{\} }}}_{n}}$ принадлежит классу $GLT_{U}^{k}$ с символом $f(x,\theta )$ в области $D$ тогда и только тогда, когда существует последовательность матричных последовательностей ${{{\text{\{ \{ }}{{B}_{{n,m}}}{{{\text{\} }}}_{m}}{\text{\} }}}_{n}}$ такая, что ${{{\text{\{ }}{{B}_{{n,m}}}{\text{\} }}}_{n}}$ принадлежит классу $GLT_{U}^{k}$ с символом ${{f}_{m}}(x,\theta )$ в области $D$, ${{{\text{\{ \{ }}{{B}_{{n,m}}}{{{\text{\} }}}_{m}}{\text{\} }}}_{n}}$ является классом аппроксимирующих последовательностей для ${{{\text{\{ }}{{A}_{n}}{\text{\} }}}_{n}}$ и ${{f}_{m}} \to f$ по мере в $D$.

Доказательство. Если ${{{\text{\{ }}{{A}_{n}}{\text{\} }}}_{n}}$ принадлежит $GLT_{U}^{k}$, то в качестве ${{{\text{\{ }}{{B}_{{n,m}}}{\text{\} }}}_{n}}$ можно взять ${{{\text{\{ }}{{A}_{n}}{\text{\} }}}_{n}}$ при всех $m$ и утверждение очевидно. Пусть теперь существует последовательность матричных последовательностей ${{{\text{\{ \{ }}{{B}_{{n,m}}}{{{\text{\} }}}_{m}}{\text{\} }}}_{n}}$, являющаяся классом аппроксимирующих последовательностей для ${{{\text{\{ }}{{A}_{n}}{\text{\} }}}_{n}}$, каждая из последовательностей ${{{\text{\{ }}{{B}_{{n,m}}}{\text{\} }}}_{n}}$ принадлежит классу $GLT_{U}^{k}$ с символом ${{f}_{m}}(x,\theta )$ и ${{f}_{m}}$ сходится к некоторой измеримой функции $f$ по мере. Тот факт, что ${{{\text{\{ \{ }}{{B}_{{n,m}}}{{{\text{\} }}}_{m}}{\text{\} }}}_{n}}$ является классом аппроксимирующих последовательностей для ${{{\text{\{ }}{{A}_{n}}{\text{\} }}}_{n}}$ в терминах функции ${{p}_{{a.c.s.}}}$ (п. 2.2) записывается следующим образом:

(36)

${{p}_{{a.c.s.}}}({{{\text{\{ }}{{A}_{n}} - {{B}_{{n,m}}}{\text{\} }}}_{n}}) \to 0,\quad m \to \infty .$

Так как каждая из последовательностей ${{{\text{\{ }}{{B}_{{n,m}}}{\text{\} }}}_{n}}$ принадлежит классу $GLT_{U}^{k}$, матрицы ${{\hat {B}}_{{n,m}}} = {{U}_{n}}\left[ {\begin{array}{*{20}{c}} {{{B}_{{n,m}}}}&0&0 \\ 0& \ddots &0 \\ 0&0&{{{B}_{{n,m}}}} \end{array}} \right]U_{n}^{ * }$ образуют GLT-последовательности с символами ${{f}_{m}}$. Рассмотрим матрицу ${{\hat {A}}_{n}} = {{U}_{n}}\left[ {\begin{array}{*{20}{c}} {{{A}_{n}}}&0&0 \\ 0& \ddots &0 \\ 0&0&{{{A}_{n}}} \end{array}} \right]U_{n}^{ * }$. Вычислим сингулярные числа матрицы ${{\hat {A}}_{n}} - {{\hat {B}}_{{n,m}}}$. Они совпадают с сингулярными числами матрицы ${{A}_{n}} - {{B}_{{n,m}}}$, где каждое из сингулярных чисел повторено $k$ раз. Отсюда легко видеть, что ${{p}_{{kn}}}(\{ {{\hat {A}}_{n}} - {{\hat {B}}_{{n,m}}}\} ) \leqslant k{{p}_{n}}({{A}_{n}} - {{B}_{{n,m}}})$, следовательно,

(37)

${{p}_{{a.c.s.}}}(\{ {{\hat {A}}_{n}} - {{\hat {B}}_{{n,m}}}\} ) \to 0,\quad m \to \infty ,$

значит, ${{\{ {{\{ \mathop {\widehat B}\nolimits_{n,m} \} }_{m}}\} }_{n}}$ является классом аппроксимирующих последовательностей для ${{{\text{\{ }}{{\hat {A}}_{n}}{\text{\} }}}_{n}}$. Получаем, что ${{{\text{\{ }}{{A}_{n}}{\text{\} }}}_{n}}$ является GLT с символом $f$, откуда по определению ${{{\text{\{ }}{{A}_{n}}{\text{\} }}}_{n}}$ принадлежит классу $GLT_{U}^{k}$ с символом $f$.

5. ПОСТРОЕНИЕ РАСПРЕДЕЛЕНИЯ В СЛУЧАЕ ОПЕРАТОРОВ НА ПОЛИГОНАЛЬНЫХ ОБЛАСТЯХ

Рассмотрим более общую задачу, когда область $\Omega $ является произвольным многоугольником. Пусть последовательность сеток в этой области получена следующим образом. Строится некоторая произвольная (достаточно грубая) триангуляция многоугольника. Обозначим соответствующую ей матрицу дискретизации ${{A}_{1}}$. Затем каждый из треугольников дробится на некоторое (одинаковое у всех) количество равных, подобных базовому треугольников. Таким образом, порождается последовательность $\{ {{A}_{n}}\} $ (фиг. 4).

Фиг. 4.

Примеры сеток в полигональных областях.

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

(38)

$\left[ {\begin{array}{*{20}{c}} {\hat {B}_{n}^{{(1)}}}&0& \ldots &0&0 \\ 0&{\hat {B}_{n}^{{(2)}}}& \ldots &0&0 \\ \vdots & \vdots & \ddots & \vdots & \vdots \\ 0&0& \ldots &{\hat {B}_{n}^{{(k - 1)}}}&0 \\ 0&0& \ldots &0&{\hat {B}_{n}^{{(k)}}} \end{array}} \right],$

где $\hat {B}_{n}^{{(j)}}$ соответствуют матрицам дискретизации треугольников, последовательности которых принадлежат классам $GLT_{P}^{2}$ с известными распределениями. Более того, все матрицы имеют одно и то же количество собственных значений и сингулярных чисел, таким образом, распределения спектров матриц $\hat {B}_{n}^{{(j)}}$ хорошо характеризуют распределение спектра последовательности матриц дискретизации на многоугольнике. В частности, верна следующая

Теорема 9. Пусть ${\text{\{ }}{{A}_{n}}{\text{\} }}$ является последовательностью матриц сеточных операторов, заданных на сетках в области $\Omega $, являющейся многоугольником, где сетки получены описанным выше способом. Пусть каждая последовательность матриц ${{\{ B_{n}^{{(j)}}\} }_{n}}$, соответствующая последовательности матриц сеточных операторов на базовых треугольниках имеет $GLT_{P}^{2}$-распределение с символом ${{f}_{j}}(x,\theta )$ в области ${{[0,1]}^{2}} \times {{[ - \pi ,\pi ]}^{2}}$, и базовая триангуляция состоит из $k$ треугольников. Тогда последовательность матриц ${{{\text{\{ }}{{A}_{n}}{\text{\} }}}_{n}}$ имеет распределение собственных значений и сингулярных чисел с символом $f(x,\theta )$ в области ${{[0,1]}^{2}} \times {{[ - \pi ,\pi ]}^{2}}$, где

(39)

$f(x,{{\theta }_{1}},{{\theta }_{2}}) = {{f}_{j}}(x,k({{\theta }_{1}} + \pi ) - 2\pi (j - 1) - \pi ,{{\theta }_{2}}),$

(40)

${{\theta }_{1}} \in \left[ { - \pi + \frac{{2\pi (j - 1)}}{k},\; - \pi + \frac{{2\pi j}}{k}} \right],\quad j = 1,\;2,\; \ldots ,\;k.$

Доказательство. Докажем это утверждение для распределения собственных значений. Из описанного выше следует, что распределение собственных значений ${{{\text{\{ }}{{A}_{n}}{\text{\} }}}_{n}}$ совпадает с распределением собственных значений матричной последовательности вида (38). Пусть матрица ${{A}_{n}}$ имеет размерность ${{N}_{P}}(n) \times {{N}_{P}}(n)$, и каждая матрица $B_{n}^{{(j)}}$ имеет размерность ${{N}_{T}}(n) \times {{N}_{T}}(n)$, $j = 1,\;2,\; \ldots ,\;k$. Тогда

$\begin{gathered} \mathop {lim}\limits_{n \to \infty } \frac{1}{{{{N}_{P}}(n)}}\sum\limits_{i = 1}^{{{N}_{P}}(n)} F ({{\lambda }_{i}}({{A}_{n}})) = \mathop {lim}\limits_{n \to \infty } \frac{1}{{k{{N}_{T}}(n)}}\sum\limits_{j = 1}^k {\sum\limits_{i = 1}^{{{N}_{T}}(n)} F } ({{\lambda }_{i}}(B_{n}^{{(j)}})) = \\ = \;\frac{1}{k}\sum\limits_{j = 1}^k {\mathop {lim}\limits_{n \to \infty } \frac{1}{{{{N}_{T}}(n)}}} \sum\limits_{i = 1}^{{{N}_{T}}(n)} F ({{\lambda }_{i}}(B_{n}^{{(j)}})) = \frac{1}{k}\sum\limits_{j = 1}^k {\frac{1}{{\mu (D)}}} \int\limits_D F ({{f}_{j}}(x,\theta ))dxd\theta = \\ \end{gathered} $

(41)

$\begin{gathered} = \;\frac{1}{k}\sum\limits_{j = 1}^k {\frac{1}{{\mu (D)}}} \int\limits_{{{{[0,1]}}^{2}}} {\int\limits_{[ - \pi ,\pi ]} {\int\limits_{[ - \pi ,\pi ]} F } } ({{f}_{j}}(x,{{\theta }_{1}},{{\theta }_{2}}))d{{\theta }_{1}}d{{\theta }_{2}}dx = \\ \frac{1}{{\mu (D)}}\int\limits_{{{{[0,1]}}^{2}}} {\int\limits_{[ - \pi ,\pi ]} {\frac{1}{k}} } \sum\limits_{j = 1}^k {\left( {\int\limits_{[ - \pi ,\pi ]} F ({{f}_{j}}(x,{{\theta }_{1}},{{\theta }_{2}}))d{{\theta }_{1}}} \right)} d{{\theta }_{2}}dx = \\ \end{gathered} $

$\begin{gathered} = \;\frac{1}{{\mu (D)}}\int\limits_{{{{[0,1]}}^{2}}} {\int\limits_{[ - \pi ,\pi ]} {\frac{1}{k}} } \sum\limits_{j = 1}^k {\left( {k\int\limits_{\left[ { - \pi + \tfrac{{2\pi (j - 1)}}{k}, - \pi + \tfrac{{2\pi j}}{k}} \right]} F ({{f}_{j}}(x,k({{\theta }_{1}} + \pi ) - 2\pi (j - 1) - \pi ,{{\theta }_{2}}))d{{\theta }_{1}}} \right)} d{{\theta }_{2}}dx = \\ = \;\frac{1}{{\mu (D)}}\int\limits_{{{{[0,1]}}^{2}}} {\int\limits_{[ - \pi ,\pi ]} {\int\limits_{[ - \pi ,\pi ]} F } } (f(x,{{\theta }_{1}},{{\theta }_{2}}))d{{\theta }_{1}}d{{\theta }_{2}}dx = \frac{1}{{\mu (D)}}\int\limits_D F (f(x,\theta ))dxd\theta . \\ \end{gathered} $

6. ПРИМЕНЕНИЕ К ПОСТРОЕНИЮ ПРЕДОБУСЛАВЛИВАТЕЛЕЙ

Одним из практических применений спектральной теории матричных последовательностей является построение предобуславливателей для решения систем линейных алгебраических уравнений. Скорость сходимости метода сопряженных градиентов напрямую зависит от распределения собственных значений. В частности, если собственные значения кластеризованы в одной точке, скорость сходимости особенно высока. Предобуславливатели используются для улучшения сходимости этого метода. Популярными типами предобуславливателей являются циркулянтные предобуславливатели [16]–[18], поскольку многие операции, такие как обращение и умножение на вектор, могут быть реализованы очень быстро. Однако известно, что циркулянтные предобуславливатели не могут обеспечить собственный кластер для собственных значений в случае многоуровневых матриц [21].

Рассмотрим систему

(42)

$Ax = f.$

Хорошо известный метод для решения таких систем с использованием предобуславливания – это предобусловленный метод сопряженных градиентов (PCG). Скорость сходимости PCG с предобуславливателем $C$ эквивалентна применению метода сопряженных градиентов без пред-обуславливания к системе

(43)

${{C}^{{1/2}}}A{{C}^{{1/2}}}{{C}^{{ - 1/2}}}x = {{C}^{{1/2}}}f.$

Далее будет описан процесс построения предобуславливателя $C$. Мы будем использовать PCG с предобуславливателем $C$ для численных экспериментов и формулировку (43) для теоретического обоснования кластеризации собственных значений.

Пусть ${{W}_{n}} = [{{w}_{{i - j}}}]_{{i,j = 1}}^{n}$ является тёплицевой матрицей. Тогда простым циркулянтом ${{C}_{n}}$ для нее называется матрица

(44)

${{C}_{n}} = \left\{ \begin{gathered} circ({{w}_{0}},\;{{w}_{1}},\; \ldots ,\;{{w}_{m}},\;{{w}_{{ - m}}},\; \ldots ,\;{{w}_{{ - 1}}}),\quad n = 2m, \hfill \\ circ({{w}_{0}},\;{{w}_{1}},\; \ldots ,\;{{w}_{{m - 1}}},\;0,\;{{w}_{{ - m + 1}}},\; \ldots ,\;{{w}_{{ - 1}}}),\quad n = 2m - 1, \hfill \\ \end{gathered} \right.$

где

(45)

$circ({{c}_{0}},\; \ldots ,\;{{c}_{{n - 1}}}) = [{{c}_{{i - j(modn)}}}]_{{i,j = 1}}^{n}.$

Подобным образом определяются многоуровневые циркулянты, для которых те же самые свойства выполняются для блоков и внутри каждого блока. Можно доказать [6], что если ${{{\text{\{ }}{{W}_{n}}{\text{\} }}}_{n}}$ является последовательностью эрмитовых многоуровневых тёплицевых матриц, а ${{{\text{\{ }}{{C}_{n}}{\text{\} }}}_{n}}$ является последовательностью соответствующих простых циркулянтов, то ${{{\text{\{ }}{{W}_{n}}{\text{\} }}}_{n}}$ и ${{{\text{\{ }}{{C}_{n}}{\text{\} }}}_{n}}$ имеют одинаковое распределение собственных значений.

Рассмотрим процедуру построения эффективного предобуславливателя для усеченных тёплицевых матриц (22). Например, она может быть использована на практике при решении системы с матрицей дискретизации оператора Лапласа, заданного на треугольнике:

1. Построим по усеченной тёплицевой матрице $A$ вида (22) полную тёплицеву матрицу $\hat {A}$. Это всегда можно сделать единственным образом для достаточно больших матриц благодаря конечному размеру шаблона сеточного оператора. Кроме того, двухуровневая тёплицева матрица и усеченная тёплицева матрица порядка $N$ единственным образом определяются $O(N)$ элементами (первые строки и столбцы, а также первые строки и столбцы в блоках) и могут быть сконвертированы друг в друга за $O(N)$операций.

2. Построим по тёплицевой матрице $\hat {A}$ простой циркулянт $S$. Это также легко сделать за $O(N)$ операций (любой циркулянт, в частности многоуровневый, единственным образом определяется своим первым столбцом), основываясь на формулах (44).

3. Во многих практических задачах простой циркулянт оказывается вырожденным. В этом случае он может быть заменен на усовершенствованный циркулянт [22], в котором все нулевые собственные значения заменены на $\delta > 0$. Усовершенствованный циркулянт можно построить за $O(NlogN)$ операций. Обозначим новый циркулянт $\hat {S}$.

4. Обратим циркулянт $\hat {S}$ и получим ${{\hat {S}}^{{ - 1}}}$, что требует $O(NlogN)$ операций.

5. Ниже будет показано, что

(46)

$\hat {S} = P\left[ {\begin{array}{*{20}{c}} {{{A}^{{ - 1}}}}&0&0 \\ 0&{{{A}^{{ - 1}}}}&0 \\ 0&0&I \end{array}} \right]P{\kern 1pt} {\text{*}} + {{\hat {L}}_{n}} = P\left[ {\begin{array}{*{20}{c}} {{{A}^{{ - 1}}} + {{R}^{{(1)}}}}&{{{R}^{{(2)}}}}&{{{R}^{{(5)}}}} \\ {{{R}^{{(3)}}}}&{{{A}^{{ - 1}}} + {{R}^{{(4)}}}}&{{{R}^{{(6)}}}} \\ {{{R}^{{(7)}}}}&{{{R}^{{(8)}}}}&{{{R}^{{(9)}}}} \end{array}} \right]P{\kern 1pt} *,$

где ${{R}^{{(k)}}}$ – матрицы малого ранга. Таким образом, мы возьмем блок ${{A}^{{ - 1}}} + {{R}^{{(1)}}}$ в качестве предобуславливателя $C$. Однако мы не будем строить и хранить ${{A}^{{ - 1}}} + {{R}^{{(1)}}}$ в явном виде. На практике мы вычислим только ${{\hat {S}}^{{ - 1}}}$ и позже покажем, что этого достаточно, чтобы вычислять произведение ${{A}^{{ - 1}}} + {{R}^{{(1)}}}$ на вектор.

Теперь мы покажем, что последовательность матриц $C_{n}^{{1/2}}{{A}_{n}}C_{n}^{{1/2}}$, где ${{C}_{n}}$ получено из ${{A}_{n}}$ описанным выше способом, имеет распределение собственных значений с символом $1$. Как было установлено выше, последовательность матриц ${{{\text{\{ }}{{A}_{n}}{\text{\} }}}_{n}}$ принадлежит классу $GLT_{P}^{2}$ с некоторым $f$. Следовательно, ${{\hat {A}}_{n}}$ выглядит следующим образом:

(47)

${{\hat {A}}_{n}} = {{P}_{n}}\left[ {\begin{array}{*{20}{c}} {{{A}_{n}}}&0&0 \\ 0&{{{A}_{n}}}&0 \\ 0&0&{{{I}_{n}}} \end{array}} \right]P_{n}^{ * } + {{M}_{n}},$

где ${{M}_{n}}$ – самосопряженная матрица малого ранга. Здесь мы не будем удалять вершины, соответствующие диагонали параллелограмма, как это сделано в п. 3.3, а вместо этого перенумеруем вершины таким образом, чтобы переместить их на последние позиции в матрице. Тогда получим

(48)

${{\hat {A}}_{n}} = {{P}_{n}}\left[ {\begin{array}{*{20}{c}} {{{A}_{n}}}&0&{\hat {R}_{n}^{{(1)}}} \\ 0&{{{A}_{n}}}&{\hat {R}_{n}^{{(2)}}} \\ {\hat {R}_{n}^{{(3)}}}&{\hat {R}_{n}^{{(4)}}}&{\hat {R}_{n}^{{(5)}}} \end{array}} \right]P_{n}^{ * },$

где размер блока $\hat {R}_{n}^{{(5)}}$ мал по сравнению с размером матрицы. Следовательно, существует такая матрица ${{M}_{n}}$ малого ранга, что выполняется (47).

Заметим, что циркулянт ${{S}_{n}}$ для двухуровневой тёплицевой матрицы вида (21) получается из ${{\hat {A}}_{n}}$ с помощью самосопряженного малорангового преобразования, поэтому

(49)

${{S}_{n}} = {{P}_{n}}\left[ {\begin{array}{*{20}{c}} {{{A}_{n}}}&0&0 \\ 0&{{{A}_{n}}}&0 \\ 0&0&{{{I}_{n}}} \end{array}} \right]P_{n}^{ * } + {{\tilde {R}}_{n}}.$

Далее, любой циркулянт может быть представлен в виде $\tfrac{1}{N}F_{n}^{ * }{{\Lambda }_{n}}{{F}_{n}}$. Если матрица ${{S}_{n}}$ имеет независимое от $n$ количество нулевых собственных значений, то чтобы усовершенствовать циркулянт ${{S}_{n}}$, требуется добавить к ней матрицу вида $\tfrac{1}{N}F_{n}^{ * }{{\Lambda }_{n}}{{F}_{n}}$, где $\Lambda $ является диагональной матрицей и имеет независимое от $n$ количество ненулевых элементов. Следовательно, переход от ${{S}_{n}}$ к ${{\hat {S}}_{n}}$ снова может быть осуществлен с помощью самосопряженного малорангового преобразования. В результате приходим к тому, что

(50)

${{\hat {S}}_{n}} = {{P}_{n}}\left[ {\begin{array}{*{20}{c}} {{{A}_{n}}}&0&0 \\ 0&{{{A}_{n}}}&0 \\ 0&0&{{{I}_{n}}} \end{array}} \right]P_{n}^{ * } + {{\hat {R}}_{n}},$

где ${{\hat {R}}_{n}}$ является самосопряженной малоранговой матрицей, откуда следует, что ${{\{ {{\hat {S}}_{n}}\} }_{n}}$ является GLT-последовательностью с тем же самым символом $f$. Тогда из общей теории следует, что ${{\{ S_{n}^{{ - 1}}\} }_{n}}$ принадлежит классу GLT с символом $1{\text{/}}f$. Применяя тождество Вудбери, получаем

(51)

$\hat {S} = P\left[ {\begin{array}{*{20}{c}} {A_{n}^{{ - 1}}}&0&0 \\ 0&{A_{n}^{{ - 1}}}&0 \\ 0&0&{{{I}_{n}}} \end{array}} \right]P{\kern 1pt} {\text{*}} + {{\hat {L}}_{n}} = P\left[ {\begin{array}{*{20}{c}} {A_{n}^{{ - 1}} + R_{n}^{{(1)}}}&{R_{n}^{{(2)}}}&{R_{n}^{{(5)}}} \\ {R_{n}^{{(3)}}}&{A_{n}^{{ - 1}} + R_{n}^{{(4)}}}&{R_{n}^{{(6)}}} \\ {R_{n}^{{(7)}}}&{R_{n}^{{(8)}}}&{R_{n}^{{(9)}}} \end{array}} \right]P{\kern 1pt} *,$

где снова ${{\hat {S}}_{n}}$ и $R_{n}^{{(k)}}$, $k = 1,\;2,\; \ldots ,\;9$, являются матрицами малого ранга.

Как было сказано выше, мы берем ${{C}_{n}} = A_{n}^{{ - 1}} + R_{n}^{{(1)}}$. Из определения $GLT_{P}^{2}$ мы заключаем, что ${{{\text{\{ }}{{C}_{n}}{\text{\} }}}_{n}}$ принадлежит классу $GLT_{P}^{2}$ с символом $1{\text{/}}f$, откуда следует, что последовательность ${{\{ C_{n}^{{1/2}}{{A}_{n}}C_{n}^{{1/2}}\} }_{n}}$ принадлежит классу $GLT_{P}^{2}$ с символом $1$.

Таким образом, мы доказали, что описанная выше процедура предобуславливания позволяет получить кластер собственных значений в $1$. Еще один ингредиент, необходимый для эффективного предобуславливания — это быстрые итерации метода сопряженных градиентов. Для этого требуется эффективная процедура умножения ${{C}_{n}}$ на вектор.

Как уже было сказано выше, единственная матрица, которую мы строим явно – это $\hat {S}_{n}^{{ - 1}}$, что может быть сделано за $O(NlogN)$ операций. Нам также требуется матрица перестановки ${{P}_{n}}$, но, очевидно, она может быть построена за $O(N)$ операций, следуя рассуждениям, представленным в п. 3.3. Теперь пусть требуется умножить ${{C}_{n}} = A_{n}^{{ - 1}} + R_{n}^{{(1)}}$ на вектор $v$. Обозначим ${\hat {v}} = {{[{v},0,0]}^{{\text{т}}}}$. Тогда

(52)

$\left[ {\begin{array}{*{20}{c}} {A_{n}^{{ - 1}} + R_{n}^{{(1)}}}&{R_{n}^{{(2)}}}&{R_{n}^{{(5)}}} \\ {R_{n}^{{(3)}}}&{A_{n}^{{ - 1}} + R_{n}^{{(4)}}}&{R_{n}^{{(6)}}} \\ {R_{n}^{{(7)}}}&{R_{n}^{{(8)}}}&{R_{n}^{{(9)}}} \end{array}} \right]\left[ {\begin{array}{*{20}{c}} {v} \\ 0 \\ 0 \end{array}} \right] = \left[ {\begin{array}{*{20}{c}} {{{C}_{n}}{v}} \\ {R_{n}^{{(3)}}{v}} \\ {R_{n}^{{(7)}}{v}} \end{array}} \right] = P_{n}^{ * }\hat {S}_{n}^{{ - 1}}{{P}_{n}}{\hat {v}}.$

Умножение на матрицу перестановок требует $O(N)$ операций, а умножение на циркулянтную матрицу требует $O(NlogN)$ операций, поэтому один шаг PCG может быть сделан за $O(NlogN)$ операций.

Таким образом, была построена схема эффективного предобуславливания, а именно, построение предобуславливателя требует $O(NlogN)$ операций, одна итерация PCG требует $O(NlogN)$ операций, и матрица после предобуславливания имеет кластер собственных значений в $1$.

По описанной схеме были проведены численные эксперименты. Была сгенерирована усеченная тёплицева матрица (22) $A$ размерности $5050 \times 5050$. На фиг. 5 изображены собственные значения матрицы $A$ до предобуславливания и ${{C}^{{1/2}}}A{{C}^{{1/2}}}$ после него. В точке $k$ каждая кривая принимает значения $k$-го по величине собственного значения соответствующей матрицы. Этот эксперимент подтверждает, что ${{C}^{{1/2}}}A{{C}^{{1/2}}}$ имеет кластер собственных значений в $1$. Затем мы реализовали метод сопряженных градиентов для решения системы линейных алгебраических уравнений с матрицей $A$. В этом случае мы не строили матрицу $C$ явно, а только циркулянт ${{\hat {S}}^{{ - 1}}}$. Мы сгенерировали правую часть из стандартного нормального распределения и применили PCG с предобуславливателем $C$. На фиг. 6 изображена норма невязки на различных шагах метода сопряженных градиентов. Этот график показывает превосходную сходимость метода PCG с предложенным предобуславливателем.

Фиг. 5.

Распределение собственных значений с и без предобуславливания.

Фиг. 6.

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

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

7. ЗАКЛЮЧЕНИЕ

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

Список литературы

Avram F. On bilinear forms in gaussian random variables and toeplitz matrices // Probability Theory and Related Fields. 1988 V. 79. № 1. P. 37–45.
Grenander U., Szegö G. Toeplitz forms and their applications. Univ. California Press, Berkeley, 1985.
Parter S.V. On the distribution of the singular values of toeplitz matrices // Linear Algebra and its Applicat. 1986. V. 80. P. 115–130.
Serra-Capizzano S. Generalized locally toeplitz sequences: spectral analysis and applications to discretized partial differential equations // Linear Algebra and its Applicat. 2003 V. 366. P. 371–402. Special issue on StructuredMatrices: Analysis, Algorithms and Applications.
Tyrtyshnikov E., Zamarashkin N. Spectra of multilevel toeplitz matrices: Advanced theory via simple matrix relationships // Linear Algebra and its Applicat. 1998. V. 270. № 1 P. 15–27.
Tyrtyshnikov E.E. A unifying approach to some old and new theorems on distribution and clustering // Linear Algebra and its Applicat. 1996. V. 232. P. 1–43.
Barrera M., Böttcher A., Grudsky S.M., Maximenko E.A. Eigenvalues of even very nice toeplitz matrices can be unexpectedly erratic. In The Diversity and Beauty of Applied Operator Theory, Springer, 2018, P. 51–77.
Bogoya J., Böttcher A., Grudsky S. Asymptotics of individual eigenvalues of a class of large hessenberg toeplitz matrices. In Recent progress in operator theory and its applications. Springer, 2012. P. 77–95.
Bogoya J., Grudsky S., Maximenko E. Eigenvalues of hermitian toeplitz matrices generated by simple-loop symbols with relaxed smoothness. In Large Truncated Toeplitz Matrices, Toeplitz Operators, and Related Topics. Springer, 2017. P. 179–212.
Bogoya J.M., Böttcher A., Grudsky S.M., Maximenko E.A. Eigenvectors of hermitian toeplitz matrices with smooth simple-loop symbols // Linear Algebra and its Applicat. 2016. V. 493. P. 606–637.
Garoni C. Topological foundations of an asymptotic approximation theory for sequences of matrices with increasing size // Linear Algebra and its Applicat. 2017. V. 513. P. 324–341.
Serra-Capizzano S. Distribution results on the algebra generated by toeplitz sequences: a finite-dimensional approach // Linear Algebra and its Applicat. 2001 V. 328. № 1. P. 121–130.
Garoni C., Serra-Capizzano S. Generalized Locally Toeplitz Sequences: Theory and Applications (V. I). Springer, Cham, 2017.
Garoni C., Serra-Capizzano S. The theory of generalized locally toeplitz sequences: a review, an extension, and a few representative applications // Operator Theory: Adv. Applicat. 2017. V. 259. P. 353–394.
Serra-Capizzano S. The glt class as a generalized fourier analysis and applications // Linear Algebra and its Applicat. 2006. V. 419. № 1. P. 180–233.
Cottrell J.A., Hughes T.J., Bazilevs Y. Isogeometric analysis: toward integration of CAD and FEA. John Wiley & Sons, 2009.
Hughes T.J., Cottrell J.A., Bazilevs Y. Isogeometric analysis: Cad, finite elements, nurbs, exact geometry and mesh refinement // Comput. Meth. Appl. Mech. Engineer. 2005 V. 194. № 39–41. P. 4135–4195.
Chan T.F. An optimal circulant preconditioner for toeplitz systems // SIAM J. Sci. Statistic. Comput. 1988 V. 9. № 4. P. 766–771.
Chan T.F., Olkin J.A. Circulant preconditioners for toeplitz-block matrices // Numerical Algorithms. 1994. V. 6. № 1. P. 89–101.
Tyrtyshnikov E.E. Optimal and superoptimal circulant preconditioners // SIAM J. Matrix Analys. Applicat. 1992. V. 13. № 2. P. 459–473.
Serra-Capizzano S., Tyrtyshnikov E. Any circulant-like preconditioner for multilevel matrices is not superlinear // SIAM J. Matrix Analys. Applicat. 2000. V. 21. № 2. P. 431–439.
Tyrtyshnikov E. Circulant preconditioners with unbounded inverses // Linear Algebra and its Applicat. 1995. V. 216. P. 1–23.

Дополнительные материалы отсутствуют.

Инструменты

следующая статья выпуска предыдущая статья выпуска содержание выпуска

Журнал вычислительной математики и математической физики

Архивы выпусков Информация о журнале Отправить рукопись в журнал