Явный нестационарный метод простой итерации. Теорема о точном решении при известном спектре

Явный нестационарный метод простой итерации для решения СЛАУ с невырожденной квадратной матрицей

(1)

имеет вид:

, (2)

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

, , (3)

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

Теорема (о точном решении при известном спектре):

Пусть - матрица простой структуры размером . Выберем в качестве набора параметров различных матриц перехода из (3) набор различных собственных чисел матрицы : , . Тогда процесс итераций (2), (3) приведет к точному решению СЛАУ не более, чем за шагов.

Доказательство.

Матрица простой структуры имеет линейно-независимую систему собственных векторов , . Любой вектор -мерного пространства можно разложить по этому базису:

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

Рассматривая последовательно ошибки решения на каждой итерации, получаем

…

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

(4)

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

(5)

Наименьшая среди норм матрицы простой структуры есть подчиненная евклидовая норма, которая совпадает со спектральным радиусом матрицы. Для записи неравенства с этой нормой рассмотрим спектральное множество матриц.

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

,

,

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

, (6)

Таким образом, запись неравенства (5) через подчиненную евклидовую норму (спектральный радиус)

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

,

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

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

Следовательно, на ой итерации вектор решения совпадает с точным решением, ч.т.д.

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

Теорема о точном решении доказана в случае матрицы простой структуры, однако доказательство может быть проведено в более общем случае, лишь в предположении единственности решения (1). При этом можно показать, что матрица суть нулевая матрица в общем случае лишь при независимо от наличия базиса из собственных векторов и числа различных собственных значений, опираясь на теорему Кели-Гамильтона [1].

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

где - собственные числа . Тогда, согласно теореме,

- нулевая матрица. Отсюда в (4) , ч.т.д.

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

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

(7)

Справа в (7) стоит Чебышевская норма полинома ой степени , который можно рассматривать как интерполяционный полином ошибки , принимающий нулевые значения при . Известно (См. 2.2.8), что чебышевская норма такого полинома минимальна, если это полином Чебышева 1 рода (т.е., если - корни полинома Чебышева). Это будет использовано в разделе 2.3 и 2.4 для построения быстро сходящегося явного нестационарного итерационного метода решения СЛАУ со спектром матрицы перехода как на вещественном, так и на комплексном отрезке.

Нестационарный итерационный метод с Чебышевским набором параметров для матрицы с комплексным спектром на отрезке, в частности для положительно определенной симметричной матрицы [4] предполагает лишь знание границ спектра матрицы, определение которых в ряде случаев является вполне приемлемой по трудоемкости задачей. Кроме того, границы спектра могут быть известны заранее, например, из физической постановки задачи. Так, например, в квазистатической трехмерной задаче электромагнитного рассеяния на диэлектрике, которая описывается объемным сингулярным интегральным уравнением, известно [13], что непрерывный спектр оператора перехода лежит на отрезке , где - значение диэлектрической проницаемости среды. Прежде, чем перейти к описанию этого метода, который существенно опирается на знание корней и свойств многочленов Чебышева, кратко рассмотрим теорию ортогональных многочленов.