Главная Случайная страница Контакты | Мы поможем в написании вашей работы! | ||
|
Для метода Ричардсона (см. раздел 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. Поведение двух ветвей функции для случаев (а) и (б) , и определение ОП сходимости МОПИ
Дата публикования: 2014-11-02; Прочитано: 884 | Нарушение авторского права страницы | Мы поможем в написании вашей работы!