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

У 1 1-,0 а=О 1=1 1= 2 1=3 в'=4 Согласно (6.2), можно использовать яг„( Охз ж=й,щ=ю аппроксимации 2е;,— е; 1 — еь1 (6.7) Определим Л; и х;(х) из этих условий. Легко видеть, что х;(х) должна быть функцией вида а э1п(~/Л;х) +;9 сов(~/Л;х) для некоторых констант а и р. Траничное условие х;(0) = 0 дает 6 = О, а из граничного условия 3;(1) = 0 следует, что ~/Л; есть целое кратное числа з-, можно положить его равным 1я. Тогда Л; = 1~я~ и 3,(х) = аэ1п(Ых), где а — произвольная ненулевая константа (можно положить а = 1). Таким образом, собственный вектор х; точно равен собственной функции х;(х), вычисляемой на множестве точек х.

= у6 (после масштабирования функции множителем Л/ — ). Кроме того, для малых 1 число Л; = Ря~ хорошо аппроксимируется величиной 6 г Л; = (Х+ 1)з 2(1 — соэ — ') = Ряз+ 0((Я+ 1) з). Итак, мы видим, что между матрицей Тгг (или 6 тТн) и оператором — 2-,т имеется тесная связь. Эта связь будет мотивировать построение и анализ последующих алгоритмов. Для сомножителей 111-разложения и разложения Холесского матрицы Тн также можно вывести простые формулы; по поводу деталей см. вопрос 6.2.

284 Глава б. Итерационные методы для линейных систем и дгн(х,у) Дя,г 2н;, — н« . 1 — н1и.»1 Ьг х=х„я=ю (6.8) Складывая их, можем написать а ,(х,Ы) агн(х,„) ДХг Лнг 4е1. — н1 1 — н1»1,, — н«,. 1 — н1,+1 тп, (6.9) или Т 1 +Ъ'-Т = Ьгг. (6.11) Это линейная система уравнений относительно неизвестных элементов матрицы Ъ', хотя она и не записана в обычном формате «Ах = 5», где неизвестные образуют вектор х. (Ниже мы представим эту систему и в формате «Ах = Ьм) Все же и такой записи вполне достаточно, чтобы определить собственные значения и собственные векторы соответствующей матрицы А, поскольку равенство Ах = Лх эквивалентно равенству Тг«Ъ'+ ЪтТг« = ЛЪ'. Предположим теперь, что взяты две собственные пары матрицы Тн, так что Тнг1 = Л;21 и Тнг, = Луг,", положим Ъ' = 21% Тогда т Тнр+Ъ'Т11 = (Тнг1)2 +21(2 Тм) = (Л121)гт+ 21(ятЛ ) = (Л1+ Л,)гогам = (Л1+ Л1)Ъ' (6.12) где погрешность аппроксимации тп снова ограничена величиной 0(Ь~).

Жир- ный крест посреди упомянутого выше рисунка называется (5-точечным) ша- блоном данного уравнения, поскольку он связывает все пять значений функ- ции н, присутствующих в уравнении (6.9). Согласно граничному условию, име- ем ног = н1«+1И = н.,о = н1,1ч+1 = О, поэтому (6.9) определяет систему из н = г»'г линейных уравнений относительно и неизвестных н„, где 1 < 1, у < Х: г 4нй — е1 1п — нь»1,. — о,,г 1 — и14»1 — — Ь ~1,. (6.10) Имеются два способа записать п уравнений, представляемых форму- лой (6.10), единым матричным уравнением; оба этих способа будут исполь- зованы в дальнейшем. Первый способ состоит в том, чтобы рассматривать неизвестные об как элементы Х х М-матрицы Ъ', а правые части Ьг~„аналогично как элемен- ты Ю х М-матрицы Ьгт'. Затем используется трюк, позволяющий матрицу, элемент (г„у) которой равен 4нб — н1 19 — н1+1 — н1 . 1 — н1 +1, несложным образом выразить через Ъ' и Тг«, .именно, заметим, что 2ий — н« 11 — и«ь1 — — (Т1«Ъ')6, 2нИ вЂ” н»и — 1 — нй1.1-1 = (Ъ' Тгт)И.

Сложение этих уравнений дает (Тг«1'+Ъ' Ти)6 =4нб — н1 11 — н1»1 — с1 1 — н11»1 = Ь Д. = (Ь г)И, 2 2 285 6.3. Уравнение Пуассона Таким образом, матрица Ъ' = хгхт является «собственным вектором», а число Л, + Лу — собственным значением. Поскольку в Г имеется Юэ элементов, следует ожидать, что задача имеет Х» собственных значений и собственных векторов, по одному для каждой пары собственных значений Л, и Л, матрицы Т!«.

В частности, наименьшее и наибольшее собственные значения равны соответственно 2Л! и 2Лм, поэтому число обусловленности остается тем же, что н в одномерном случае. Ниже мы выведем этот результат заново, используя формат «Ах = 6». На рис. 6.3 приведены изображения некоторых собственных векторов, представленных как поверхности, определяемые элементами матрицы х»х Собственные значения и собственные векторы матрицы Ь ~Тгг были хорошими приближениями к собственным значениям и собственным функциям одномерного уравнения Пуассона. То же самое верно для двумерного уравнения, чьи собственные значения и собственные функции видны из соотношения (см.

вопрос 6.3) с лг Вэ Л вЂ” — 1 эш(Ых) яп(~ту) дхэ дух = (»ох~ + у х ) яп(мтх) яп(!ту). (6.13) Второй способ записать п уравнений, представленных формулой (6.10), одним матричным уравнением предполагает объединение неизвестных с! в длинном векторе размерности Хэ. Это требует задания упорядочения для неизвестных; мы выберем (достаточно произвольно) упорядочение, показанное на рис. 6.4: нумерация неизвестных производится по столбцам при движении от левого верхнего узла к нижнему правому. Например, при 1'»' = 3 получаем вектор-столбец с = (ег,..., сэ)т, При аналогичной нумерации правых частей Д.

уравнения (6.10) преобразуются к виду Ю! ьт Тэхэ ' у! »2 (6.14) Минус единицы рядом с главной диагональю соответствуют вычитанию верхнего и нижнего соседей — сг; ! — с«,1+!. Минус единицы, удаленные от главной 286 Глава б. Итерационные методы для линейных систем Собственный вектор 1, 1 1 Собственный вектор 1, 2 1 0.6 0 1О -1 10 10 10 0 0 Собственный вектор 2, 1 0 0 Собственный вектор 2, 2 -1 10 -1 10 1О 10 2 4 6 8 Рис. 8.3. Трехмерные н контурные изображения первых четырех собственных век- торов уравнения Пуассона на сетке 10 х 10.

диагонали, соответствуют вычитанию левого и правого соседей — и! 1, — и,+1,, В следующем разделе мы убедимся, что для произвольного Ж получается линейная Лт х 1т'т-система 2ч и Н=П~Л (6.15) где матрица Ти„м имеет на диагонали Ю блоков размера Х х Х и вида Tи + 0 0 Собственный вектор 1, 1 10 2 4 8 8 Собственный вектор 2, 1 10 0 0 Собственный вектор 1, 2 10 2 4 6 8 Собственный вектор 2, 2 10 287 6.3. Уравнение Пуассона Рис. 6.4. Нумерация неизвестных в уравнении Пуассона. 21л, а иа диагоналях, соседних с главной, блоки — 1ч: Тгг + 21,ч — 1н (6.16) — 1~ч Тн + 21н 6.3.3.

Запись уравнении Пуассона посредством кроиекеровых произведений Познакомимся с систематическим способом вывода уравнений (6.15) и (6.16), а также вычисления собственных значений и собственных векторов матрицы Тгг„гг. Этот способ столь же хорошо работает для уравнения Пуассона в случае трех и более измерений. Определение 6.1. Пусть Х вЂ” матрица размера т х и. Тогда чес(Х) опредгллетсл как вектор-столбец размерности тп, получаемый последовательной записью столбцов матрицы Х при их упорлдочении слева направо. Заметим, что вектор о, определяемый рис.

6.4, может быть записан как о = чес(ч'). Чтобы найти выражение для матрицы Тн„н, а также вычислить ее собственные значения и собственные векторы, мы должны ввести понятие кронекгрова произведения. Определение 6.2. Пусть А — матрица размера т хи, а  — матрица размера р х о. Тогда кроиекерово произведение А 3 В матриц А и  — это матрица азг В ... аг„В ~ а г В ... а „В размера тр х по Следующая лемма показывает, как записать уравнение Пуассона в термииах кроиекеровых произведений и оператора чес( ).

288 Глава б. Итерационные методы для линейных систем Лемма 6.2. Пусть А — матрица размера т х т,  — матрица размера и х п, Х и С вЂ” матрицы размера т х и. Тогда выполняются следующие свойства: 1. чес(АХ) = (1„З А) чес(Х). 2. чес(ХВ) = (В З 1„,) чес(Х). 3. Уравнение Пуассона Т)чЪ'+ЪгТ(ч = 112г моокет быть эквивалентным образом записано кан Т(ч к)ч чес(Ъг) и— и (1ч З Т)ч + Туч З 1ч) . чес(Ъ') = г12 чес(Е). Доказательство. Мы докажем только третье утвери(ление, отнеся два других к вопросу 6.4.

Согласно (6.11), уравнение Пуассона может быть записано в форме Тл Ъ'+ ЪгТд = уутг", которая, очевидно, эквивалентна равенству чес(Т)чЪг + Ъ'Тг() = чес(ТнЪ') + чес(УТуч) = чес(1(~Е). Согласно первому утверждению леммы, чес(Т)ч Ъг) = (1)ч З Тн) чес(Ъ'). Используя второе утверждение леммы и симметрию матрицы Т)ч, имеем чес("ч'Туг) = (Тд З 1ч) чес(Ъ') = (Т)ч З 1м) чес(Ъ').

Сложение двух последних равенств завершает доказательство утверждения 3. (3 Читатель может проверить, что выражение Т „)ч =1нЗТ +Т З1аг — 1)ч — 1)ч 21)ч из уравнения (6.17) находится в согласии с формулой (6.17)'. Для вычисления собственных значений матриц, определяемых кронекеровыми произведениями, таких, как матрица Т)чх(ч, нам понадобится следующая лемма (ее доказательство также составляет часть вопроса 6.4): Лемма 6.3.

Справедливы следующие утверзкдсния отпоситсльно кронсксро- вых произведений: 1. Пусть определены произведения А С и В ° Р. Тогда (АЗВ) . (СЗР) = (А С) З(В .О). 2. Если матрицы А и В обратимы, то (А З В) 1 = А 1 З В 3 (А З В)т Ат З Вт 1 С помощью этого равенства матрицу Тякл можно вычислить в две строки текста на Ма1)аь'е: ТИ рлеуе(И) - а1ая(овее(И-1,1),1) - 61аИ(овее(И-1,1),-1); Твхв = Мхов(еуе(И),ТИ) + Игои(еуе(ТИ),И)); 6.4. Краткая сводка методов для решення уравнения Пуассона 289 Предложение 6.1. Пусть тгг = ллем~ есть спектральное разложение матрицы Тн, где л = [гы...,гм] — ортогональная матрица, составленная по столбцам из собственных векторов матрицы Тм, а Л = 61а8(Лы...,Лм).

Тогда спектральное разлозюение матрицы тм„м = 1 З Тн + Тм З 1 имеет вид 1Зт +Т„З1=(гвг).(1ЗЛ+ЛЗ1) (гвг)т. (6А8) В диагональной матрице 1ЗЛ+ЛЗ1 диагональный элемент с номером гЛ'+1 есть собственное значение матрицы Тггхгг, соответствующее паре индексов (г,з) и равное Л, = Л;+ Л . Отвечающий этому собственному значению собственный вектор г; З яд являетсл столбцом с номером гХ+ 1 в ортогональной матрице Я З Я. Доказательство. Из утверждений 1 и 3 леммы 6.3 легко выводится ортогональность матрицы ЯЗЯ. Действительно, (ЯЗВ)(ЯЗЯ) = (лЗЯ)(о ЗЯ ) = (Я Ят) З (В Ят) =1З1 = 1.