1611688890-f641c9ec8276824e4686da772eb56520 (826652), страница 68
Текст из файла (страница 68)
. , n, так как хотя бы для одного из них непременно справедливы выполненные нами рассуждения. Потому в целом,если λ — какое-либо собственное значение рассматриваемой матрицыA, то должно выполняться хотя бы одно из неравенствX|λ − all | ≤|alj |,l = 1, 2, . . . , n.j6=lКаждое из этих соотношений на λ определяет на комплекснойплоскоPсти C круг с центром в точке all и радиусом, равным j6=l |alj |. Какследствие, мы приходим к результату, который был установлен в 1931году С.А.
Гершгориным:Теорема 3.16.2 (теорема Гершгорина) Для любой вещественной иликомплексной n × n-матрицы A = (aij ) все собственные значения λ(A)расположены в объединениикругов комплексной плоскости с центраPми aii и радиусами j6=i |aij |, i = 1, 2, . . . , n, т. е.λ(A) ∈n n[i=1oPz ∈ C |z − aii | ≤ j6=i |aij | .Фигурирующие в условиях теоремы круги комплексной плоскостиonPi = 1, 2, . .
. , n,z ∈ C |z − aii | ≤ j6=i |aij | ,называются кругами Гершгорина матрицы A = (aij ). Можно дополнительно показать, что если объединение кругов Гершгорина распадаетсяна несколько связных, но непересекающихся частей, то каждая такаячасть содержит столько собственных значений матрицы, сколько кругов её составляют (см.
подробности в [42, 50, 97]).Нетрудно продемонстрировать, что теорема Гершгорина равносильна признаку Адамара неособенности матриц (Теорема 3.2.2). В самомделе, если матрица имеет диагональное преобладание, то её круги Гершгорина не захватывают начала координат комплексной плоскости, апотому в условиях теоремы Гершгорина матрица должна быть неособенной. Обратно, пусть верен признак Адамара. Если λ — собственное4173.16. Проблема собственных значенийзначение матрицы A = (aij ), то матрица (A − λI) особенна и потому неможет иметь диагональное преобладание. Как следствие, хотя бы дляодного i = 1, 2, . . .
, n должно быть выполненоX|λ − aii | ≤|aij |,i = 1, 2, . . . , n.j6=iЭтими условиями и определяются круги Гершгорина.Im2-20246Re-2Рис. 3.24. Круги Гершгорина для матриц (3.14) и (3.15).Пример 3.16.5 Для 2 × 2-матрицы (3.14)1 2,3 4рассмотреннойв Примере 3.2.3 (стр. 228), собственные значения суть√1(5±33),ониприблизительно равны −0.372 и 5.372. На Рис. 3.24,2показывающем соответствующие матрице круги Гершгорина, эти собственные значения выделены крестиками.Матрица (3.15)1 2,−3 4которая отличается от матрицы (3.14) лишь противоположным знаком элемента на месте (2, 1), имеет те же самые круги Гершгорина.√Но собственные значения у неё комплексные, равные 12 (5 ± i 15), т.
е.4183. Численные методы линейной алгебрыприблизительно 2.5 ± 1.936 i . Они выделены на Рис. 3.24 звёздочками,целиком находясь в одном из кругов Гершгорина.Бросается в глаза «избыточность» кругов Гершгорина, которые вкачестве области локализации собственных значений очерчивают довольно большую область комплексной плоскости. Это характерно дляматриц с существенной внедиагональной частью. Но если недиагональные элементы матрицы малы сравнительно с диагональными, то информация, даваемая кругами Гершгорина, становится весьма точной.3.16дОтношение РэлеяОпределение 3.16.2 Для квадратной n × n-матрицы A, вещественной или комплексной, отношением Рэлея называется функционал R(x),задаваемый какhAx, xi,R(x) :=hx, xiкоторый определён на множестве ненулевых векторов из Rn или Cn .Область значений отношения Рэлея, т.
е. множество{ R(x) | x 6= 0 },называется полем значений матрицы A. Можно показать, что оно является выпуклым подмножеством комплексной плоскости C.Перечислим основные свойства отношения Рэлея.Для любого скаляра α справедливоR(αx) = R(x),что устанавливается непосредственной проверкой.Если v — собственный вектор матрицы A, то R(x) равен собственному значению матрицы, отвечающему v. В самом деле, если обозначитьэто собственное значение посредством λ, то Av = λv. По этой причинеR(v) =hAv, vihλv, viλ hv, vi=== λ.hv, vihv, vihv, viКак следствие доказанного свойства, можем заключить, что собственные числа матрицы принадлежат её полю значений.3.16.
Проблема собственных значений419Собственые векторы являются стационарными точками отношенияРэлея, т. е. точками зануления производной. Покажем это для вещественной симметричной матрицы, для которой отношение Рэлея рассматривается для всех ненулевых вещественных векторов:∂R(x)2 (Ax)i hx, xi − hAx, xi · 2xi∂hAx, xi==.∂xi∂xihx, xihx, xi2Если x = v = (v1 , v2 , . . . , vn )⊤ — собственный вектор матрицы A, точислитель последней дроби равен 2λvi hv, vi − hλv, vi · 2vi = 0.Практическое значение отношения Рэлея для вычислительных методов состоит в том, что с его помощью можно легко получить приближение к собственному значению, если известен приближённый собственный вектор матрицы.Хотя отношение Рэлея имеет смысл и практическое значение дляпроизвольных матриц, особую красоту и богатство содержания оноприобретает для эрмитовых (симметричных в вещественном случае)матриц.Если A — эрмитова n × n-матрица, то, как известно,A = U DU ∗ ,где D = diag {λ1 , λ2 , .
. . , λn } — диагональная матрица с вещественными собственными значениями матрицы A по диагонали, U — некотораяунитарная n × n-матрица (ортогональная в вещественном случае). ТогдаPn2hU DU ∗ x, xihDU ∗ x, U ∗ xihAx, xii=1 λi |yi |,===R(x) =hx, xihx, xihU ∗ x, U ∗ xikyk22где y = U ∗ x. ПосколькуnnX|yi |21 X2|y|== 1,i2kyk2 i=1kyk22i=1то для эрмитовых матриц отношение Рэлея есть выпуклая комбинация, с коэффициентами |yi |2 /kyk22, её собственных значений. В целомже из проведённых выше выкладок следует, что область значения отношения Рэлея для эрмитовой матрицы — это интервал [λmin , λmax ] ⊂ R,коль скоро все λi вещественны.
Кроме того, для эрмитовых матриц отношение Рэлея позволяет легко находить нетривиальные границы для4203. Численные методы линейной алгебрынаименьшего собственного значения сверху и наибольшего собственного значения снизу.В теории на основе отношения Рэлея нетрудно вывести полезныеоценки для собственных и сингулярных чисел матриц. В частности, изсвойств отношения Рэлея следует (см. подробности в [40, 50])Теорема 3.16.3 (теорема Вейля) Пусть A и B — эрмитовы n × nматрицы, причём λ1 ≥ λ2 ≥ . . . ≥ λn — собственные значения матрицы A и λ̃1 ≥ λ̃2 ≥ .
. . ≥ λ̃n — собственные значения матрицыà = A + B. Тогда |λ̃i − λi | ≤ kBk2 .Следствие. Пусть A и B — произвольные матрицы одинакового размера, причём σ1 ≥ σ2 ≥ . . . ≥ σn — сингулярные числа матрицы A, аσ̃1 ≥ σ̃2 ≥ . . . ≥ σ̃n — сингулярные числа матрицы à = A + B. Тогда|σ̃i − σi | ≤ kBk2 .Следствие из теоремы Вейля показывает, что сингулярные числанепрерывно зависят от элементов матрицы, и зависимость эта имеетдовольно плавный характер. В этом состоит важное отличие сингулярных чисел матрицы от её собственных чисел, которые могут изменяться в зависимости от элементов матрицы сколь угодно быстро (см.Пример 3.16.3).3.16еПредварительное упрощение матрицыЕстественной идеей является приведение матрицы, для которой решается проблема собственных значений, к некоторой, по-возможности,простейшей форме, для которой собственные значения и/или собственные векторы могут быть найдены проще, чем для исходной.
В частности, идеальным было бы приведение матрицы к диагональной илитреугольной форме, по которым собственные числа находятся непосредственно. Элементарными преобразованиями, с помощью которыхможет быть выполнено это приведение, в данном случае должны быть,очевидно, такие, которые сохраняют неизменным спектр матрицы, т. е.преобразования подобия матрицы A 7→ S −1AS. Они существенно сложнее действуют на матрицу, чем преобразования линейного комбинирования строк, которые использовались в прямых методах решения систем линейных алгебраических уравнений. Невозможность полной реализации идеи упрощения матрицы следует из теоремы Абеля-Руффини,4213.16.
Проблема собственных значенийкоторую мы обсуждали в §3.16а: если бы это упрощение было возможным, то оно привело бы к конечному алгоритму решения алгебраических уравнений произвольной степени, что в общем случае невозможно.Тем не менее, в некоторых частных случаях идея предварительного упрощения матрицы для решения проблемы собственных значенийможет оказаться полезной. Её наиболее популярное воплощение — этотак называемая почти треугольная (хессенбергова) форма для общихматриц, а также её частные случаи — трехдиагональные симметричныеи эрмитовы матрицы.Определение 3.16.3 Матрица H = (hij ) называется верхней почтитреугольной или хессенберговой матрицей (в форме Хессенберга), еслиhij = 0 при i > j + 1.Наглядный «портрет» хессенберговой матрицы выглядит следующим образом:× × ··· × ×× × · · · × ×....
...×.. .H=... × ×0××Симметричная хессенбергова матрица — это, очевидно, трёхдиагональная матрица.Предложение 3.16.2 Любую n × n-матрицу A можно привести кортогонально подобной хессенберговой матрице H = QAQ⊤ , где Q —произведение конечного числа отражений или вращений.Доказательство. Рассмотрим для определённости преобразования спомощью матриц отражения.Возьмём матрицу отражения Q1 = I − 2uu⊤ так, чтобы первая компонента вектора Хаусхолдера u была нулевой и при этом a11a11 a a′ 21 21 a Q1 31 = 0 , .. ..