1626435584-7c6402f545ecf856225d6cf8d21519c9 (844233), страница 34
Текст из файла (страница 34)
Подобные лииейвые системы зачастую выгодно решать итерационными методами. Современные итерационные л~етоды мы рассмотрим в главе Х)1, посвященной эллиптическим уравнениям. Здесь упомянем только два старых метода, уже не используемых в практических вычислениях, но удобных для некоторых теоретических оценок. Один из них — стационарный метод простых итераций, основанный на приведении системы Ах=В к эквивалентной системе специального вида: х=Сх+г(. (50) Запись итерационного процесса очевидна. Для сходнмости итераций достаточно, если какая-нибудь норма )1 С 1! ~ 1. В этой задаче известно даже необходимое и достаточное условие сходимости †моду всех собственных аначений матрицы С должны быть меньше единицы; но на практике этим условием трудно воспользоваться, ибо найти собственные значения обычно сложнее, чел» решить линейную систему.
К виду (50) систему можно привести, например, выделением диагональных элементов хг, = — Ьа — ~ ааах!), 1 (В(п, (51) аа» ~ !да В этой записи легко учесть наличие нулей в матрице А н при умножении матрицы на вектор суммировать только по ненулевым элементам. При использовании различных норм ъ1атрицы достаточные условия сходимостн итераций принимают вид „) 1 — "'-)(,1, нли ~ ~ — '~(1, нли 1) ~~) ~- — -! (1, (52) гфа а ты а гэа что означает преобладание диагональных элемэнтоэ матрицы (сравните условия устойчивости метода прогонки (14)). Если метод сходится„то корень уравнения существует. Таким образом, преобладание диагональных элементов матрицы в смысле одного из неравенств (52) является признаком того, что система линейных уравнений (1) имеет решение, т.
е. бе( А ФО. Этим признаком мы будем часто пользоваться при исследовании разрешимости неявных разнастных схем. 155 ЗАДАЧИ Заметим, что чем меньше () С(1, тем быстрей сходятся итерации. Наилучшие современные методы основаны на специальных способах выбора матрицы С, при которых ее норма становится минимальной в некотором сл!ысле. Второй -метод Зейделя. Для уравнения (51) он имеет такой вид; Необходимое и достаточное условие его сходимости не совпадает с условием сходимости простых итерапий, и в разных условиях он может быть выгоден нли невыгоден.
Отметим один признак сходимости: если матрица Л вЂ” зрмигова и положительно определенная, то метод Зейделя в форме (53) совпадает с методом покоординатного спуска для решения задачи на минимум квадратичной формы (х, Лх) — 2(д, х)=ппп; как будет показано в главе Ъ'Н, метод по- координатного спуска сходится, что обеспечивает сходимость метода Зейделя в данном случае. 3 А Д А Ч И !. Записать для почти треугольной матрицы (рис, 25, д) формулы метода исключения Гаусса с обходом нулевых злементов. 2. Показать, что при преобразовании эрмитовь!х матриц, изображенных на рис. 25, а — г, в произведение (15) структура треугольных матриц подобна структуре исходных матриц.
3. Доказать„ что первый итерационный процесс (25) не сходится, а второй сходится при любом (положительнол!) нулевом приближении. 4. Найти асимптотическую скоргкть сходимости метода секуших (32) вблизи корня кратности р. 5. Доказать, что скорость сходимости метода парабол вблизи простого корня определяется формулой (37); исследовать сходимость вблизи кратного корня, 6. Доказать, что метод квадрирования сходится квадратично.
7. Вывести формулы не~ода квадрирования для случая, когда наибольший по модулю корень †двукратн. 8, Доказать, что итерационный процесс (49) для нахождения обратной матрицы сходится квадратично, ГЛАВА Хг! АЛГЕБРАИЧЕСКАЯ ПРОБЛЕМА СОБСТВЕННЪ|Х ЗНАЧЕНИЙ В главе и'! рассмотрены методы нахождения собственных значений и собственных векторов квадратных матриц. В 1 ! изложены необходимые сведения по линейной алгебре, рассмотрена устойчивость проблемы собственных значений н даны простые (но сравнительно медленные) численные методы решения.
Наиболее быстрые численные методы нахождения всех собственных значений и собственных векторов зрмитовых матриц разобраны в й 2, а неэрмитовых матриц — в 1 3. В 1 4 изложены методы, которые оказываются более выгодными при определении не всех, а некоторых собственных значений и собственных векторов. ф 1. Проблема и простейшие методы 1. Элементы теории. Напомним некоторые сведения яз курса линейной алгебры. Если А — квадратная матрица а-го порядка и Ах=Ах при хчаО, то число А называется собственным значением матрицы, а ненулевой вектор х — соответствующим ему собственным вектором.
Перепишем задачу в виде (А — АЕ)х=О, хФО. (1) Для существования нетривиального решения задачи (1) должно выполняться условие с1е| (А — ЛЕ) = О. (2) Этот определитель является многочленом п-й степени от А; его называют характеристическим многочленом. Значит, существует п собственных значений — корней этого многочлена, среди которых могут быть одинаковые (кратные). В принципе можно вычислить характеристический многочлен и найти все его корни.
Если найдено некоторое собственное значение, то, подставляя его в однородную систему (1), можно определить соответствующий собственный вектор. Будем нормировать собственные векторы *). Тогда каждому простому (не кратному) собственному *) Нормировкой (на единицу) вектора х называют умножение его иа ))х| э; нормированный вектор имеет единичную длину. ПРОБЛЕМА И ПРОСТЕЙШИЕ МЕТОДЫ э и значению соответствует один (с точностью до направления) собственный вектор, а совокупность всех собственных векторов, соответствующих совокупности простых собственных значений, линейно-независима. Таким образом, если все собственные значения матрицы простые, то она имеет л линейно-независимых собственных векторов, которые образуют базис пространства. Кратному собственному значению кратности р может соответствовать от 1 до р линейно-независимых собственных векторов. Например, рассмотрим такие матрицы четвертого порядка: 'а ! О О 10 а 1 О с,= ~~..., О О О а а О О О О а О О О О а О О О О а а О О О (3) ооа! О О О а У каждой из них характеристическое уравнение принимает вид де( (А — АЕ) = (а — А)' =- О, а следовательно, собственное значение ).=а и имеет кратность р= 4.
Однако у первой 'матрицы есть четыре линейно-независимых собственных вектора /1 О /О 'О (4) ',О' о~ '!О!' это легко проверить, поочередно подставляя векторы (4) в равен- ство (1). У второй же матрицы имеется только один собственный вектор е,. В самом деле, пусть ее собственный вектор х имеет компоненты хп тогда уравнение (1) примет для нее вид О!ОО ОО!О ооо! ОООО (б, — ЛЕ) х = откуда х,= хз = х, =-О, а х, = 1 в силу условия нормировки. Вторую матрицу называют простой жордановой (или классической) подматри!!ей.
Третья матрица имеет так называемую каноническую жорданову форму (по диагонали стоят либо числа, либо жордановы подматрицы, а остальные элементы равны нулю). Ее собственными векторами являются е, и е,; в этом легко убедиться при помощи выкдадки, аналогичной только что проделанной. Таким образом, если среди собственных значений матрицы есть кратные, то ее собственные векторы не всегда образуют базис. Однако и в этом случае собственные векторы; соответствующие различным собственным значениям, являются линейно- независимыми. !ой АЛГЕБРАИЧЕСКАЯ ПРОБЛЕМА СОБСТВЕННЪ|Х ЗНАЧЕНИИ !ГЛ тт Задача на собственные значения легко решается для некоторых простых форм матрицы: диагональной, трехдиагональной, треугольной или почти треугольной.
Например, определитель треугольной (в частности, диагональной) матрицы равен произведению диагональных элементов. В этом случае А — АЕ тоже треугольная или диагональная матрица. Поэтому собственные значения треугольной (диагональной) матрицы равны диагональным злеменгпам. Легко проверить, что диагональная матрица имеет и собственных ортонормированных векторов е, = 10, ..., О, 1, О, ..., О) г, соответствующих собственным значениям )и = ап, наоборот, матрица с такими собственными векторами диагональна.
Многие численные методы решения задач на собственные значения основаны на приведении матрицы к одной из перечисленных выше простых форм при помощи преобразования подобия. Матрица б=Р'-гАЕ называется подобной матрице А. Пусть т), у суть собственное значение и собственный вектор матрицы 6; тогда ту =бу=Е 'АЕу, что после умножения слева на матрицу Е дает т)(Еу) = А (Еу). Отсюда видно, что т) и Еу суть собственное значение и собственный вектор матрицы А. Следовательно, преобразование подобия не меняет собственных значений мал!рицы и по определенному закону преобразует ее собственные векторы.
Особенно удобны преобразования подобия при помощи унитарных матриц "). Если ортонормированный базис преобразовать унитарной матрицей, то он останется ортонормированиым. Если подобно преобразовать эрмптову матрицу при помощи унитарной, то она остается эрмитовой; в самом деле„ В = ()~А(), Вн = ((1"А())" = ()"Ан (()") = ()~А(У = В. Если А — нормальная матрица, то при подобном унитарном преобразовании она остается нормальной; читателям предлагается проверить это. Известно, что для любой матрицы А есть такое унитарное преобразование, что (/~А(г' является верхней треугольной матри- *) Напомним принятую терминологию. Матрица В называется зрмитово сопряженной к матрице А, если она получена из нее транспонированием (зеркальным отражением от главной диагонали) с последующей заменой элементов комплексно.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
