Метод оптимальной простой итерации (оптимальный метод Ричардсона)

Для метода Ричардсона (см. раздел 1.2), использующего преобразование , коэффициенты матрицы следующие: , , , . Найдем спектр трехдиагональной матрицы (11), (12) из раздела 1.10 произвольного размера . Характеристическое уравнение приводит к уравнению с детерминантом Для упрощения записи в (1) сделаны следующие переобозначения

, , , (1)

(2)

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

, (3)

Из (1) следуют начальные значения: , . Далее, с помощью (3), получаем , и т.д.

Введем следующую замену переменной на переменную

(4)

Для детерминантов в новых пременных получаем

, , , , и т.д.

Легко заметить, что каждый нечетный детерминант, благодаря (3) имеет множитель , а каждый четный, благодаря замене переменной (4), увеличивает степень на единицу. Таким образом,

; ; (5)

где и - многочлены переменной степени . Для них, принимая во внимание (3), (4), получаем следующие рекуррентные формулы

(6)

Откуда легко получить одинаковые рекуррентные формулы для многочленов и

, (7)

но при этом с различными начальными условиями:

;

;

Заменим переменную

(8)

Многочлены из (7) переходят в следующие

, (9)

с начальными условиями

Это известные ортогональные многочлены Чебышева второго рода с корнями на интервале [1,2].

(10)

Следовательно, – тоже многочлены Чебышева второго рода, но с корнями на интервале .

Лемма 1.1. Корни многочленов (10) , задаются формулой

, . (11)

Действительно, уравнения и равносильны на открытом интервале . Раскрытие неопределенности в (10) при приводит к ненулевым значениям и . Т.о. из корней исключены значения при , откуда и следует (11).

Лемма 1.2. Корни многочленов ,

, . (12)

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

Таким образом, справедлива следующая теорема

Теорема 1.1. Собственные числа трехдиагональной матрицы (12) из раздела 1.10 размерности в модифицированном методе простой итерации (методе Ричардсона) (11) следующие:

1. (13)

где

, , (14)

2. Для нечетных есть ещё одно собственное число

.

Здесь - целая часть .

Доказательство. Ввиду первой части формулы (5), второй части (6), а также (7 - 9) корнями четных детерминантов по переменной являются корни уравнения . Учитывая Лемму 1.2 и получаем (14).

Для нечетных детерминантов ввиду (5),(7),(10) получаем , и поэтому и . Учитывая Лемму 1.1 и , получаем (14) и утверждение 2 Теоремы.

Далее, возвращаясь с помощью (4) и (2) к корням детерминантов по переменной , получаем утверждение (13) теоремы. Теорема доказана.

Задача ускорения сходимости состоит в минимизации спектрального радиуса как функции переменной , т.е. в определении оптимального параметра (ОП) , для которого наступает минимум

Рассмотрим поведение функции как функции переменной . Заметим, что и для и для . Таким образом, функция на монотонно возрастающая с максимумом в и

(15)

где максимальный из корней (14)

, (16)

Из (16) следует, что корень . Левое значение имеет место для , а правое является пределом в случае больших матриц при .

Собственное число при поиске максимума отброшено, в силу .

Из теоремы 1.1 и формулы (15)

Следствие. Спектральный радиус трехдиагональной матрицы (матрицы (12) из раздела 1.10) для обычного (при параметре =0) метода простой итерации (метода Ричардсона)

(17)

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

Теорема 1.2. ОП для сходимости модифицированного метода простой итерации (метода Ричардсона) с трехдиагональной матрицей (матрицей (12) из раздела 1.10) и спектральный радиус при этом ОП следующие:

1. Для : ;

2. Для :

; (18)

Доказательство. На рис. 8 показано типичное поведение двух ветвей функции из (15) как функции параметра в случаях и , а также способ определения ОП . В случае в качестве необходимо взять абсциссу точки пересечения двух ветвей функции как минимума по максимальной ветви и это приводит к пункту 1 в (18), а в случае обе ветви совпадают и необходимо найти минимум функции с помощью производной, что приводит к пункту 2 в (18). В точке обе ветви совпадают и для определения спектрального радиуса ОП подставлен в формулу (15). Здесь же представлено поведение функции .

Следствие. ОП для сходимости модифицированного метода Ричардсона (назовем этот метод – метод оптимальной простой итерации, сокращенно МОПИ) в случае не зависит от коэффициентов и задается простой формулой . Сходимость в этом случае имеет место при следующем соотношении между коэффициентами . В терминах матрицы A, учитывая, что в случае сходимость при ОП имеет место для любых , область сходимости

(19)

а) б)

Рис.8. Поведение двух ветвей функции для случаев (а) и (б) , и определение ОП сходимости МОПИ