Дж. Деммель - Вычислительная линейная алгебра, страница 70

1. Из согласованной упорядоченности следует, что собственные значения матрицы Вз(о) не зависят от о, поэтому матрицы Вз = Вз(1) и Вз( — 1) = — В,г(1) имеют одни и те же собственные значения, которые, таким образом, составляют ~ пары. 2. Если Л = О и справедливо (6.27), то ш = 1 и число О действительно является собственным значением матрицы ВяощИ = Вс в = (1 — 1) 1(л', поскольку Воз — вырожденная матрица. В противном случае, О = бес(Л1 — Взощ,„л) = де1((1 — ш1)(Л1 — Взонл л)) = с1еС((Л+ ш — 1)1 — шЛ1 — шУ) = л л ( л (( ) л — лл — — лл)) =лл(( " )л-л — о)( л Г.

ЗО7 6.5. Основные ятерааяоляые методы Сетка 16 х 16 е Сетха 16 х 16 о.в ю' о.в ю' ол СО" 1О о оя 1 та г ю' о О О.в 1 1.6 г Сетка 64 х 64 ав ю' о.в ю 0.4 ю о.г о ю о оя 1 16 г О Оз 1 !.в г % к Рис. 6.5. Сходимость методов Якоби, Гаусса — Зейделя и БОК (ш) в зависимости от ш для модельной задачи яа сетке 16 х 16 и сетке 64 х 64. Спектральный радиус р(Я) для каждого метода (т.

е. р(йз), р(хсоз) и р(11зояс 1)) изображен ва левых рисунках, а функция 1 — р(Н) изображена иа правых рисунках. Последнее равенство выполняется в силу предложения 6.2. Итак, число «ф= — '- = сс есть собственное значение матрицы Е+ У = 41з., при чС«ш этом (Л + ш — 1)г = ргшгЛ. 3.

Если Л О6 О, то цепочку равенств в 2) можно пройти в обратном иаправлеиии. П Следствие 6.1. Если А — согласованно упорядоченная матприца, то р(Япз) = (р(Вз))г. Это означает, чтпо метод Гаусса — Зейде л вдвое быстрее метпода Якоби. Доказатпельстпво. Выбор ш = 1 эквивалентен методу Гаусса — Зейделя. Из (6.2Т) получаем Лг = Лрг, или Л = рг. П Чтобы получить наибольшую выгоду от верхней релаксации, хотелось бы найти значение ш,рс, минимизирующее р(Взои( )) [249].

Теорема 6.7. Предполооссим, что матрица А согласованно упорядочена, матрица Вз имеетп веилественные собственные значен я и сс = р(Лз) < 1. Тогда Шара ка ш,рс < ш < 2, О«,С <ше,с. р(Язоп1ш.„,>) = рФзоп(.>) = 2 1+,/Г- дг ' (1+ Ф вЂ” р'Р ш — 1, , + 1,г „г +, 1 „+ 1,г,г 308 Глава 6. Итерационные методы для линейных систем Доказательство. Достаточно решить относительно Л уравнение (Л+ ы — 1)з = 2 2 П Пример 6.10.

Модельная задача может служить примером: матрица Вз для нее симметрична и, следовательно, имеет вещественные собственные значения. На рис. 6.5 показан график р(Взощ,„1) как функции от ы, а также графики р(Коз) и р(Яз) для модельной задачи на сетке Х х Х, где Ю = 16 и 1У = 64. Левые рисунки — это графики функций р(В), а правые — полулогарифмнческие графики функций 1 — р(Я). Главный вывод, который можно сделать из этой иллюстрации, состоит в том, что вблизи точки минимума функция р(Язов ~) изменяется очень быстро, поэтому, если значение ы даже лишь немного отличается от ы,ры сходимость метода существенно замедляется.

Еще один вывод: если приближенное значение ы,„с приходится угадывать, то лучше переоценить его (указать значение, близкое к 2), чем недооценить. О 6.5.6, Чебышевское ускорение и симметричная последовательная верхняя релаксация (ББОГс) Если говорить об уже обсуждавшихся методах, то для использования методов Якоби и Гаусса — Зейделя не требуется никакой информации о матрице системы (хотя для доказательства сходимости этих методов некоторая информация о матрице все же нужна). Метод ЗОГс(ы) зависит от параметра ы, значение которого может быть выбрано в согласии с р(Вз) так, чтобы ускорить сходимость. Чебышевское ускорение полезно тогда, когда о спектре матрицы Вз известно большее, чем только значение р(Вз); в этом случае сходимость можно ускорить еще сильнее.

Предположим, что система Ах = б с помощью какого-либо метода (Якоби, Гаусса — Зейделя или ЗОН(ы)) преобразована в итерационный процесс х;~~ = Ах, + с. Тогда будет получена последовательность векторов (х,), где х; -э х при 1 -э оо, если р(В) < 1. Если все эти приближения х; имеются, то естественно спросить, не существует ли какой-либо их линейной комбинации у = 2 ',. о у~х,, которая еще лучше приближает решение х. Заметим, что коэффициенты у; должны удовлетвоРЯть Условию 2',,. р У; = 1, посколькУ, если хо — — х1 — — .

— — х, то мы хотели бы, чтобы и у~ было равно х. Таким образом, погрешность приближения у можно записать как тл Е 7нихз х ~ -«...(х, - х) 7т'Н (хо — х) 1=0 (6.28) р,„(В) (хо — х), 6.5. Основные итерационные методы 309 где р (В) = 2,'; а у гВ' есть многочлен степени тп, такой, что р (1) Емау»* =1. Пример 6.11. Если бы в качестве р,„мы могли взять характеристический многочлен матрицы В, то по теореме Гамильтона — Кзли мы имели бы ро,(В) = О, что означает сходимость в т шагов.

Этот способ, однако, не практичен, так как собственные значения матрицы В редко бывают известны, да и в любом случае мы хотели бы, чтобы метод сошелся быстрее, чем за т = дпп В шагов. О Вместо поисков многочлена р, для которого р (В) есть нулевая матрица, постараемся насколько возможно уменьшить значение спектрального радиуса матрицы р (В). Предположим, что известно следующее: ° все собственные значения матрицы В вещественны и ° эти собственные значения находятся в отрезке [ — р, р), не содержащем 1. Тогда можно попытаться найти многочлен р, такой, что 1. р (1) = 1 и 2.

число гпах р<,ел ~р (х) ~ имеет наименьшее возможное значение. Поскольку собственными значениями матрицы р (В) являются числа р (А(В)) (см. задачу 4.5), зти собственные значения будут малы, а потому будет мал и спектральный радиус (как наибольший из модулей собственных значений). Построение многочлена р, удовлетворяющего сформулированным условиям 1) и 2), — зто классическая задача теории приближений, решение которой опирается на многочлены Чебьпиева. Определение 6.15. Многочлен Чебышева Т (х) стпепени т определяется рекуррентным соотношением Т (х) ги 2хТ г(х) — Т г(х), где Та(х) = 1 и Тг(х) = х. Чебышевские многочлены обладают рядом интересных свойств (240].

Приведем несколько свойств, которые легко вывести из определения (см. вопрос 6.7). Лемма 6.7. Многочлены Чебышева имеют следующие свойства: ° Т (1) = 1. ° Т (х) = 2 'х + 0(х г). сое(т ° агссоех)„если ~х~ < 1, сЬ(т агссогх), если ~х~ > 1. и )Т„,(х)( < 1, если (х( < 1. ° Нулями многочлена Т (х) являются числа хг = сое((2г — 1)х/(2т)), г' = 1,...,гп. ° Т (х) = -г((х+~/хг — 1) +(х+ч/хг — 1) ), если ~х~ > 1. ° Т (1+ с) > .5(1+т~/2ее), если е > О. Глава б. Итерационные методы для линейных систем Т 6 Т 4 ТЗ 10 -10 1 -1 0 ! -4 1 -1 0 к10е т гО 1 те т1о 1О О.б -1О -1 о о 1 -1 о Рис. 6.6.

График Т,„(х) как функции от х. Пунктирные линии показывают, что ]Т,„(х)) < 1 для ]х] < 1. Приведем таблицу значений для Т (1+с). Обратим внимание на то, как быстро растут эти числа с увеличением гп, даже если е очень мало (см. рис. 6.6). Многочленом с теми свойствами, которые нам нужны, является р (х) = Т (х(р)(Т Яр), Чтобы убедиться в этом, заметим, что р (1) = 1 и если х Е ~ — р, р!, то ]р,„(х)] < ЦТ„„'11(р). Так, если р = 1/(1+с), то ]р„,(х)] < ЦТ,„(1+с).

Как мы только что видели, эта граница очень мала при малых е н умеренных значениях т. Для экономной реализации процесса воспользуемся трехчленной рекурсией Т (х) = 2хТ г(х) — Т т(х), использованной в определении многочленов Чебышева. Она позволяет хранить и комбинировать только три вектора у у 1 и у з, а не все предыдущие векторы х . Посмотрим, как это получается. 6.5. Основные итерационные методы Положим и = 17Т (1(р), тогда р (В) = и Т (В)~р) и, согласно трехчленной рекурсии в определении 6.15, †' = 2 — 1 . Далее, и РР— 1 и -2 у — х = р (В)(хо — х) согласно равенству (6.28) и Т вЂ” (хо — х) Рт 2 — . Т -1 — (хо — х) — Т 2 — (хо — х) по определению 6.15 с В Рп — 1 ( — ) (ХΠ— Х) Ртп-2 ( ) (ХΠ— Х) и 2.

Р Р ттт-2 В у 1 — х у 2 — Х1 и 2 — ° — ~ согласно равенству (6.28), Р Нт-1 1тт-2 или 2н В и Утп = Упт-1 Упт — 2 + 1(т~ Ит-1 Р Ит-2 где 2ат (В1 фт — х+ Х 2рт /х — с'1 Рт — ~ + — х так как х = Вх+ с ттт — 1 Р Рпт — 2 с 1 2 1 '~ 2н + х+ с Рт Ррт — 1 Ит — 2/ РР и-1 2нт с согласно определению числа и Ррт-1 В результате приходим к следующему алгоритму: Алгоритм 6.7. Чебышееское ускорение процесса х1е1 = Вхе + с: Ио = 1; Р1 = Р; Уо = хо ' У1 = Вхо + с уог гн = 2, 3,... Р =1!(,„',— — „',) Ри -т пт 1 и -2 т 2 епт1 уог Отметим, что на каждой итерации выполняется ровно одно матричновекторное умножение с матрицей В. Если стоимость такого умножения значительно выше, чем прочих скалярных и векторных операций, то шаг алгоритма 6.7 имеет тУ же сложность, что и шаг исхоДного пРоЦесса х +1 —— Вхтп + с.

К сожалению, описанный алгоритм нельзя непосредственно применить к методу ЯОВ(а1) при решении системы Ах = Ь. Дело в том, что матрица Взон1 > в общем случае имеет комплексные собственные значения, а чебышевское ускорение требует, чтобы собственные значения матрицы В были вещественны и принш1лежвли сегменту ( — р, р]. Однако ситуацию можно поправить с помощью следующего алгоритма.