Алгоритм собственных значений - Eigenvalue algorithm

В числовой анализ, одна из важнейших проблем - проектирование эффективных и стабильный алгоритмы для поиска собственные значения из матрица. Эти алгоритмы собственных значений может также найти собственные векторы.

Собственные значения и собственные векторы

Основные статьи: Собственные значения и собственные векторы и Обобщенный собственный вектор

Учитывая п × п квадратная матрица А из настоящий или же сложный числа, собственное значение λ и связанные с ним обобщенный собственный вектор v пара, подчиняющаяся соотношению^[1]

${\displaystyle \left(A-\lambda I\right)^{k}{\mathbf {v} }=0,}$

куда v ненулевой п × 1 вектор-столбец я это п × п единичная матрица, k положительное целое число, и оба λ и v разрешено быть сложным, даже когда А реально. Когда k = 1, вектор называется просто собственный вектор, и пара называется собственная пара. В этом случае, Аv = λv. Любое собственное значение λ из А имеет обычные^{[примечание 1]} собственные векторы, связанные с ним, если k это наименьшее целое число такое, что (А - λя)^k v = 0 для обобщенного собственного вектора v, тогда (А - λя)^k-1 v - обычный собственный вектор. Значение k всегда может быть меньше или равно п. Особенно, (А - λя)^п v = 0 для всех обобщенных собственных векторов v связана с λ.

Для каждого собственного значения λ из А, то ядро кер (А - λя) состоит из всех собственных векторов, связанных с λ (вместе с 0), называется собственное подпространство из λ, а векторное пространство кер ((А - λя)^п) состоит из всех обобщенных собственных векторов и называется обобщенное собственное подпространство. В геометрическая кратность из λ это размерность его собственного подпространства. В алгебраическая кратность из λ - это размерность его обобщенного собственного подпространства. Последняя терминология оправдывается уравнением

${\displaystyle p_{A}\left(z\right)={\rm {det}}\left(zI-A\right)=\prod _{i=1}^{k}(z-\lambda _{i})^{\alpha _{i}},}$

куда Det это детерминант функция, λ_я все различные собственные значения А и α_я - соответствующие алгебраические кратности. Функция п_А(z) это характеристический многочлен из А. Таким образом, алгебраическая кратность - это кратность собственного значения как нуль характеристического полинома. Поскольку любой собственный вектор также является обобщенным собственным вектором, геометрическая кратность меньше или равна алгебраической кратности. Алгебраические кратности в сумме составляют п, степень характеристического полинома. Уравнение п_А(z) = 0 называется характеристическое уравнение, так как его корни - в точности собственные значения А. Посредством Теорема Кэли – Гамильтона, А сам подчиняется тому же уравнению: п_А(А) = 0.^{[заметка 2]} Как следствие, столбцы матрицы ${\displaystyle \textstyle \prod _{i\neq j}(A-\lambda _{i}I)^{\alpha _{i}}}$ должны быть либо 0, либо обобщенными собственными векторами собственного значения λ_j, поскольку они уничтожаются ${\displaystyle \textstyle (A-\lambda _{j}I)^{\alpha _{j}}.}$ Фактически, пространство столбца является обобщенным собственным подпространством λ_j.

Любой набор обобщенных собственных векторов различных собственных значений линейно независим, поэтому базис для всех C ^п можно выбрать состоящим из обобщенных собственных векторов. В частности, эта основа {v_я}^п
_я=1 можно выбрать и организовать так, чтобы

• если v_я и v_j имеют такое же собственное значение, то v_k для каждого k между я и j, и
• если v_я не является обычным собственным вектором, и если λ_я - его собственное значение, то (А - λ_яя )v_я = v_я-1 (особенно, v₁ должен быть обычным собственным вектором).

Если эти базисные векторы размещены как векторы-столбцы матрицы V = [ v₁ v₂ ... v_п ], тогда V можно использовать для преобразования А к его Нормальная форма Джордана:

${\displaystyle V^{-1}AV={\begin{bmatrix}\lambda _{1}&\beta _{1}&0&\ldots &0\\0&\lambda _{2}&\beta _{2}&\ldots &0\\0&0&\lambda _{3}&\ldots &0\\\vdots &\vdots &\vdots &\ddots &\vdots \\0&0&0&\ldots &\lambda _{n}\end{bmatrix}},}$

где λ_я собственные значения, β_я = 1 если (А - λ_я+1)v_я+1 = v_я и β_я = 0 иначе.

В более общем смысле, если W - любая обратимая матрица, и λ является собственным значением А с обобщенным собственным вектором v, тогда (W⁻¹AW - λя )^k W^−kv = 0. Таким образом λ является собственным значением W⁻¹AW с обобщенным собственным вектором W^−kv. То есть, аналогичные матрицы имеют одинаковые собственные значения.

Нормальные, эрмитовы и вещественно-симметричные матрицы

Основные статьи: Присоединенная матрица, Нормальная матрица, и Эрмитова матрица

Сопряженным к матрице является матрица сомножителей транспонирования. Используйте другой термин. прилегающий M^* сложной матрицы M является транспонированием конъюгата M: M ^* = M ^Т. Квадратная матрица А называется нормальный если он коммутирует со своим соседом: А^*А = AA^*. Это называется эрмитский если он равен своему сопряженному: А^* = А. Все эрмитовы матрицы нормальные. Если А имеет только реальные элементы, то присоединенное - это просто транспонирование, а А является эрмитовым тогда и только тогда, когда оно симметричный. Применительно к векторам-столбцам сопряженное может использоваться для определения канонического внутреннего продукта на C^п: ш · v = ш^* v.^{[заметка 3]} Нормальные, эрмитовые и вещественно-симметричные матрицы обладают несколькими полезными свойствами:

• Каждый обобщенный собственный вектор нормальной матрицы является обычным собственным вектором.
• Любая нормальная матрица подобна диагональной матрице, поскольку ее жорданова нормальная форма диагональна.
• Собственные векторы различных собственных значений нормальной матрицы ортогональны.
• Нулевое пространство и изображение (или пространство столбцов) нормальной матрицы ортогональны друг другу.
• Для любой нормальной матрицы А, C ^п имеет ортонормированный базис, состоящий из собственных векторов А. Соответствующая матрица собственных векторов есть унитарный.
• Собственные значения эрмитовой матрицы действительны, поскольку (λ - λ)v = (А^* − А)v = (А − А)v = 0 для ненулевого собственного вектора v.
• Если А реально, существует ортонормированный базис для р^п состоящий из собственных векторов А если и только если А симметрично.

Реальная или комплексная матрица может иметь все действительные собственные значения, не будучи эрмитовскими. Например, настоящий треугольная матрица имеет собственные значения по диагонали, но в целом не является симметричным.

Номер условия

Любую задачу числового вычисления можно рассматривать как вычисление некоторой функции ƒ для некоторого ввода Икс. В номер условия κ(ƒ, Икс) Проблема заключается в соотношении относительной ошибки на выходе функции к относительной ошибке на входе, которое зависит как от функции, так и от входа. Номер условия описывает, как растет ошибка во время расчета. Его логарифм по основанию 10 показывает, на сколько цифр точности меньше, чем было во входных данных. Номер условия - это лучший сценарий. Он отражает нестабильность, заложенную в проблему, независимо от того, как она решается. Ни один алгоритм не может дать более точных результатов, чем указано в номере условия, за исключением случая. Однако плохо спроектированный алгоритм может дать значительно худшие результаты. Например, как упоминается ниже, проблема поиска собственных значений для нормальных матриц всегда хорошо обусловлена. Однако проблема нахождения корней многочлена может быть решена. в очень плохом состоянии. Таким образом, алгоритмы собственных значений, которые работают путем нахождения корней характеристического многочлена, могут быть плохо обусловлены, даже если проблема не в этом.

Для задачи решения линейного уравнения Аv = б куда А обратимо, число обусловленности κ(А⁻¹, б) дан кем-то ||А||_op||А⁻¹||_op, куда || ||_op это норма оператора подчиняться нормальному Евклидова норма на C ^п. Поскольку это число не зависит от б и то же самое для А и А⁻¹, его обычно называют просто числом условия κ(А) матрицы А. Это значение κ(А) также является абсолютным значением отношения наибольшего собственного значения А до самого маленького. Если А является унитарный, тогда ||А||_op = ||А⁻¹||_op = 1, так κ(А) = 1. Для обычных матриц часто бывает сложно вычислить операторную норму. По этой причине другие матричные нормы обычно используются для оценки числа обусловленности.

Для задачи на собственные значения Бауэр и Фике доказали что если λ является собственным значением для диагонализуемый п × п матрица А с матрица собственных векторов V, то абсолютная погрешность вычисления λ ограничен произведением κ(V) и абсолютная ошибка в А.^[2] Как результат, номер условия для нахождения λ является κ(λ, А) = κ(V) = ||V ||_op ||V ⁻¹||_op. Если А нормально, тогда V унитарен, и κ(λ, А) = 1. Таким образом, проблема собственных значений для всех нормальных матриц хорошо обусловлена.

Число обусловленности задачи нахождения собственного подпространства нормальной матрицы А соответствующему собственному значению λ было показано, что он обратно пропорционален минимальному расстоянию между λ и другие различные собственные значения А.^[3] В частности, проблема собственного подпространства для нормальных матриц хорошо обусловлена ​​изолированными собственными значениями. Когда собственные значения не изолированы, лучшее, на что можно надеяться, - это определить диапазон всех собственных векторов ближайших собственных значений.

Алгоритмы

Любой приведенный многочлен является характеристическим многочленом своего сопутствующая матрица. Таким образом, общий алгоритм поиска собственных значений может также использоваться для поиска корней многочленов. В Теорема Абеля – Руффини показывает, что любой такой алгоритм для размерностей больше 4 должен быть либо бесконечным, либо включать функции большей сложности, чем элементарные арифметические операции и дробные степени. По этой причине алгоритмы, которые точно вычисляют собственные значения за конечное число шагов, существуют только для нескольких специальных классов матриц. Для общих матриц алгоритмы итеративный, получая более приближенные решения с каждой итерацией.

Некоторые алгоритмы производят каждое собственное значение, другие - несколько или только одно. Однако даже последние алгоритмы можно использовать для нахождения всех собственных значений. Как только собственное значение λ матрицы А был идентифицирован, его можно использовать либо для направления алгоритма к другому решению в следующий раз, либо для сведения проблемы к той, которая больше не имеет λ как решение.

Перенаправление обычно выполняется смещением: заменой А с А - μя для некоторой постоянной μ. Найденное собственное значение А - μя должны быть μ добавлен обратно, чтобы получить собственное значение для А. Например, для итерация мощности, μ = λ. Степенная итерация находит наибольшее собственное значение по модулю, поэтому даже когда λ является лишь приблизительным собственным значением, степенная итерация вряд ли найдет его во второй раз. Наоборот, обратная итерация методы на основе находят наименьшее собственное значение, поэтому μ выбран далеко от λ и, надеюсь, ближе к какому-то другому собственному значению.

Уменьшение может быть достигнуто путем ограничения А в пространство столбцов матрицы А - λя, который А несёт себе. С А - λя сингулярно, пространство столбцов имеет меньшую размерность. Затем алгоритм собственных значений может быть применен к ограниченной матрице. Этот процесс можно повторять до тех пор, пока не будут найдены все собственные значения.

Если алгоритм собственных значений не создает собственные векторы, обычной практикой является использование алгоритма на основе обратной итерации с μ установить в близком приближении к собственному значению. Это быстро сведется к собственному вектору ближайшего собственного значения к μ. Для небольших матриц альтернативой является просмотр пространства столбцов произведения А - λ'я для каждого из других собственных значений λ'.

Формула для нормы составляющих единичного собственного вектора нормальных матриц была открыта Робертом Томпсоном в 1966 году и переоткрыта независимо несколькими другими. ^{[4][5][6][7][8]}Если А является ${\displaystyle \textstyle n\times n}$ нормальная матрица с собственными значениями λ_я(А) и соответствующие единичные собственные векторы v_я чьи компоненты записи v_{я, j}, позволять А_j быть ${\displaystyle \textstyle n-1\times n-1}$ матрица, полученная удалением я-я строка и столбец из А, и разреши λ_k(А_j) быть его k-е собственное значение. потом

${\displaystyle |v_{i,j}|^{2}\prod _{k=1,k\neq i}^{n}(\lambda _{i}(A)-\lambda _{k}(A))=\prod _{k=1}^{n-1}(\lambda _{i}(A)-\lambda _{k}(A_{j}))}$

Если ${\displaystyle p,p_{j}}$ - характеристические многочлены ${\displaystyle A}$ и ${\displaystyle A_{j}}$, формулу можно переписать как

${\displaystyle |v_{i,j}|^{2}={\frac {p_{j}(\lambda _{i}(A))}{p'(\lambda _{i}(A))}}}$

предполагая производную ${\displaystyle p'}$ не равно нулю в ${\displaystyle \lambda _{i}(A)}$.

Гессенберга и трехдиагональные матрицы

Основная статья: Матрица Гессенберга

Поскольку собственные значения треугольной матрицы являются ее диагональными элементами, для общих матриц не существует конечного метода, такого как гауссовское исключение для преобразования матрицы в треугольную форму с сохранением собственных значений. Но можно достичь чего-то близкого к треугольному. An верхняя матрица Гессенберга квадратная матрица, для которой все элементы ниже субдиагональный равны нулю. Нижняя матрица Хессенберга - это матрица, для которой все элементы выше супердиагональ равны нулю. Матрицы, которые являются как верхней, так и нижней Hessenberg, являются трехдиагональный. Матрицы Хессенберга и трехдиагональные матрицы являются отправными точками для многих алгоритмов собственных значений, поскольку нулевые элементы уменьшают сложность проблемы. Для преобразования общей матрицы в матрицу Хессенберга с теми же собственными значениями обычно используются несколько методов. Если исходная матрица была симметричной или эрмитовой, то полученная матрица будет трехдиагональной.

Когда нужны только собственные значения, нет необходимости вычислять матрицу подобия, поскольку преобразованная матрица имеет те же собственные значения. Если также необходимы собственные векторы, матрица подобия может потребоваться для преобразования собственных векторов матрицы Хессенберга обратно в собственные векторы исходной матрицы.

Метод	Относится к	Производит	Стоимость без матрицы сходства	Стоимость с матрицей сходства	Описание
Преобразования домовладельцев	Общий	Hessenberg	​2п^3⁄3 + О(п^2)[9](стр. 474)	​4п^3⁄3 + О(п^2)[9](стр. 474)	Отразите каждый столбец через подпространство, чтобы обнулить его нижние элементы.
Гивенса вращения	Общий	Hessenberg	​4п^3⁄3 + О(п^2)[9](p470)		Примените плоские вращения для обнуления отдельных записей. Вращения упорядочены так, чтобы последующие не заставляли нулевые записи снова становиться ненулевыми.
Итерация Арнольди	Общий	Hessenberg			Выполните ортогонализацию Грама – Шмидта на подпространствах Крылова.
Алгоритм Ланцоша	Эрмитский	Трехдиагональный			Итерация Арнольди для эрмитовых матриц с сокращениями.

Для симметричных трехдиагональных задач на собственные значения все собственные значения (без собственных векторов) могут быть вычислены численно за время O (n log (n)) с использованием пополам на характеристическом полиноме. ^[10]

Итерационные алгоритмы

Итерационные алгоритмы решают проблему собственных значений, создавая последовательности, сходящиеся к собственным значениям. Некоторые алгоритмы также создают последовательности векторов, которые сходятся к собственным векторам. Чаще всего последовательности собственных значений выражаются как последовательности аналогичных матриц, которые сходятся к треугольной или диагональной форме, что позволяет легко читать собственные значения. Последовательности собственных векторов выражаются в виде соответствующих матриц подобия.

Метод	Относится к	Производит	Стоимость за шаг	Конвергенция	Описание
Итерация мощности	Общее	собственная пара с наибольшим значением	О(п^2)	линейный	Многократно применяет матрицу к произвольному начальному вектору и перенормирует.
Обратная итерация	Общее	собственная пара со значением, ближайшим к μ		линейный	Итерация мощности для (А - μя )^−1
Итерация фактора Рэлея	Эрмитский	любая собственная пара		кубический	Итерация мощности для (А - μяя )^−1, куда μя для каждой итерации - это коэффициент Рэлея предыдущей итерации.
Предварительно обусловленная обратная итерация[11] или же Алгоритм LOBPCG	положительно определенный настоящий симметричный	собственная пара со значением, ближайшим к μ			Обратная итерация с использованием предварительный кондиционер (приблизительная обратная А).
Метод бисекции	действительный симметричный трехдиагональный	любое собственное значение		линейный	Использует метод деления пополам найти корни характеристического многочлена, поддерживаемого последовательностью Штурма.
Итерация Лагерра	действительный симметричный трехдиагональный	любое собственное значение		кубический[12]	Использует Метод Лагерра найти корни характеристического многочлена, поддерживаемого последовательностью Штурма.
QR-алгоритм	Hessenberg	все собственные значения	О(п^2)	кубический	Факторы А = QR, куда Q ортогонален и р является треугольным, затем применяет следующую итерацию к RQ.
		все собственные пары	6п^3 + О(п^2)
Алгоритм Якоби на собственные значения	настоящий симметричный	все собственные значения	О(п^3)	квадратичный	Использует вращения Гивенса, чтобы попытаться удалить все недиагональные записи. Это не удается, но усиливает диагональ.
Разделяй и властвуй	Эрмитова трехдиагональная	все собственные значения	О(п^2)		Делит матрицу на подматрицы, которые диагонализируются, а затем повторно объединяются.
		все собственные пары	(​^4⁄3)п^3 + О(п^2)
Гомотопический метод	действительный симметричный трехдиагональный	все собственные пары	О(п^2)[13]		Строит вычислимый гомотопический путь из диагональной задачи на собственные значения.
Метод свернутого спектра	настоящий симметричный	собственная пара со значением, ближайшим к μ			Предварительно обусловленная обратная итерация, примененная к (А - μя )^2
Алгоритм MRRR[14]	действительный симметричный трехдиагональный	некоторые или все собственные пары	О(п^2)		«Множественные относительно надежные представления» - выполняет обратную итерацию по ЛПНП^Т разложение сдвинутой матрицы.

Прямой расчет

Хотя не существует простого алгоритма прямого вычисления собственных значений для общих матриц, существует множество специальных классов матриц, в которых собственные значения могут быть вычислены напрямую. К ним относятся:

Треугольные матрицы

Поскольку определитель треугольная матрица является произведением его диагональных элементов, если Т треугольная, то ${\displaystyle \textstyle \det(\lambda I-T)=\prod _{i}(\lambda -T_{ii})}$. Таким образом, собственные значения Т - его диагональные элементы.

Факторизуемые полиномиальные уравнения

Если п - любой полином и п(А) = 0, тогда собственные значения А также удовлетворяют тому же уравнению. Если п имеет известную факторизацию, то собственные значения А лежат среди его корней.

Например, проекция квадратная матрица п удовлетворение п² = п. Корни соответствующего скалярного полиномиального уравнения, λ² = λ, равны 0 и 1. Таким образом, любая проекция имеет собственные значения 0 и 1. Кратность 0 как собственного значения - это ничтожность из п, а кратность 1 - ранг п.

Другой пример - матрица А это удовлетворяет А² = α²я для некоторого скаляра α. Собственные значения должны быть ± α. Операторы проекции

${\displaystyle P_{+}={\frac {1}{2}}\left(I+{\frac {A}{\alpha }}\right)}$

${\displaystyle P_{-}={\frac {1}{2}}\left(I-{\frac {A}{\alpha }}\right)}$

удовлетворить

${\displaystyle AP_{+}=\alpha P_{+}\quad AP_{-}=-\alpha P_{-}}$

и

${\displaystyle P_{+}P_{+}=P_{+}\quad P_{-}P_{-}=P_{-}\quad P_{+}P_{-}=P_{-}P_{+}=0.}$

В пространства столбцов из п₊ и п₋ являются собственными подпространствами А соответствующий + α и -α, соответственно.

2 × 2 матрицы

Для размерностей 2–4 существуют формулы с радикалами, которые можно использовать для нахождения собственных значений. В то время как обычная практика для матриц 2 × 2 и 3 × 3, для матриц 4 × 4 возрастающая сложность корневые формулы делает этот подход менее привлекательным.

Для матрицы 2 × 2

${\displaystyle A={\begin{bmatrix}a&b\\c&d\end{bmatrix}},}$

характеристический многочлен

${\displaystyle {\rm {det}}{\begin{bmatrix}\lambda -a&-b\\-c&\lambda -d\end{bmatrix}}=\lambda ^{2}\,-\,\left(a+d\right)\lambda \,+\,\left(ad-bc\right)=\lambda ^{2}\,-\,\lambda \,{\rm {tr}}(A)\,+\,{\rm {det}}(A).}$

Таким образом, собственные значения могут быть найдены с помощью квадратичная формула:

${\displaystyle \lambda ={\frac {{\rm {tr}}(A)\pm {\sqrt {{\rm {tr}}^{2}(A)-4{\rm {det}}(A)}}}{2}}.}$

Определение ${\displaystyle \textstyle {\rm {gap}}\left(A\right)={\sqrt {{\rm {tr}}^{2}(A)-4{\rm {det}}(A)}}}$ расстояние между двумя собственными значениями, легко вычислить

${\displaystyle {\frac {\partial \lambda }{\partial a}}={\frac {1}{2}}\left(1\pm {\frac {a-d}{{\rm {gap}}(A)}}\right),\qquad {\frac {\partial \lambda }{\partial b}}={\frac {\pm c}{{\rm {gap}}(A)}}}$

с аналогичными формулами для c и d. Отсюда следует, что расчет хорошо обусловлен, если собственные значения изолированы.

Собственные векторы можно найти, используя Теорема Кэли – Гамильтона. Если λ₁, λ₂ собственные числа, то (А - λ₁я )(А - λ₂я ) = (А - λ₂я )(А - λ₁я ) = 0, поэтому столбцы (А - λ₂я ) уничтожены (А - λ₁я ) наоборот. Предполагая, что ни одна из матриц не равна нулю, столбцы каждого должны включать собственные векторы для другого собственного значения. (Если любая из матриц равна нулю, то А является кратным единице, и любой ненулевой вектор является собственным вектором.)

Например, предположим

${\displaystyle A={\begin{bmatrix}4&3\\-2&-3\end{bmatrix}},}$

тогда tr (А) = 4 - 3 = 1 и det (А) = 4(-3) - 3(-2) = -6, поэтому характеристическое уравнение имеет вид

${\displaystyle 0=\lambda ^{2}-\lambda -6=(\lambda -3)(\lambda +2),}$

а собственные значения - 3 и -2. Сейчас же,

${\displaystyle A-3I={\begin{bmatrix}1&3\\-2&-6\end{bmatrix}},\qquad A+2I={\begin{bmatrix}6&3\\-2&-1\end{bmatrix}}.}$

В обеих матрицах столбцы кратны друг другу, поэтому можно использовать любой столбец. Таким образом, (1, -2) может быть взят как собственный вектор, связанный с собственным значением -2, и (3, -1) как собственный вектор, связанный с собственным значением 3, что можно проверить, умножив их на А.

3 × 3 матрицы

Если А является матрицей 3 × 3, то ее характеристическое уравнение может быть выражено как:

${\displaystyle {\rm {det}}\left(\alpha I-A\right)=\alpha ^{3}-\alpha ^{2}{\rm {tr}}(A)-\alpha {\frac {1}{2}}\left({\rm {tr}}(A^{2})-{\rm {tr}}^{2}(A)\right)-{\rm {det}}(A)=0.}$

Это уравнение может быть решено методами Кардано или же Лагранж, но аффинное изменение на А значительно упростит выражение и приведет непосредственно к тригонометрическое решение. Если А = pB + qI, тогда А и B имеют одинаковые собственные векторы, и β является собственным значением B если и только если α = pβ + q является собственным значением А. Сдача ${\displaystyle \textstyle q={\rm {tr}}(A)/3}$ и ${\displaystyle \textstyle p=\left({\rm {tr}}\left((A-qI)^{2}\right)/6\right)^{1/2}}$, дает

${\displaystyle {\rm {det}}\left(\beta I-B\right)=\beta ^{3}-3\beta -{\rm {det}}(B)=0.}$

Замена β = 2cos θ и некоторое упрощение с использованием тождества cos 3θ = 4cos³ θ - 3cos θ сводит уравнение к cos 3θ = det (B) / 2. Таким образом

${\displaystyle \beta =2{\rm {cos}}\left({\frac {1}{3}}{\rm {arccos}}\left({\rm {det}}(B)/2\right)+{\frac {2k\pi }{3}}\right),\quad k=0,1,2.}$

Если det (B) сложен или больше 2 по модулю, арккосинус следует брать по той же ветви для всех трех значений k. Эта проблема не возникает, когда А является действительным и симметричным, в результате получается простой алгоритм:^[15]

% Учитывая вещественную симметричную матрицу A 3x3, вычислить собственные значения% Обратите внимание, что acos и cos работают с углами в радианах.p1 = А(1,2)^2 + А(1,3)^2 + А(2,3)^2если (p1 == 0)    % A - диагональный.   eig1 = А(1,1)   eig2 = А(2,2)   eig3 = А(3,3)еще   q = след(А)/3               % trace (A) - это сумма всех диагональных значений   p2 = (А(1,1) - q)^2 + (А(2,2) - q)^2 + (А(3,3) - q)^2 + 2 * p1   п = sqrt(p2 / 6)   B = (1 / п) * (А - q * я)    % I - единичная матрица   р = Det(B) / 2   % В точной арифметике для симметричной матрицы -1 <= r <= 1   %, но ошибка вычислений может немного выйти за пределы этого диапазона.   если (р <= -1)       фи = число Пи / 3   elseif (р >= 1)      фи = 0   ещеphi = acos (r) / 3   конец% собственные значения удовлетворяют eig3 <= eig2 <= eig1   eig1 = q + 2 * п * потому что(фи)   eig3 = q + 2 * п * потому что(фи + (2*число Пи/3))   eig2 = 3 * q - eig1 - eig3     %, поскольку trace (A) = eig1 + eig2 + eig3конец

Еще раз, собственные векторы А можно получить, обратившись к Теорема Кэли – Гамильтона. Если α₁, α₂, α₃ являются различными собственными значениями А, тогда (А - α₁я)(А - α₂я)(А - α₃я) = 0. Таким образом, столбцы произведения любых двух из этих матриц будут содержать собственный вектор для третьего собственного значения. Однако если α₃ = α₁, тогда (А - α₁я)²(А - α₂я) = 0 и (А - α₂я)(А - α₁я)² = 0. Таким образом обобщенный собственное подпространство α₁ охватывает столбцы А - α₂я в то время как обычное собственное подпространство занято столбцами (А - α₁я)(А - α₂я). Обычное собственное подпространство α₂ охватывает столбцы (А - α₁я)².

Например, пусть

${\displaystyle A={\begin{bmatrix}3&2&6\\2&2&5\\-2&-1&-4\end{bmatrix}}.}$

Характеристическое уравнение:

${\displaystyle 0=\lambda ^{3}-\lambda ^{2}-\lambda +1=(\lambda -1)^{2}(\lambda +1),}$

с собственными значениями 1 (кратности 2) и -1. Расчет,

${\displaystyle A-I={\begin{bmatrix}2&2&6\\2&1&5\\-2&-1&-5\end{bmatrix}},\qquad A+I={\begin{bmatrix}4&2&6\\2&3&5\\-2&-1&-3\end{bmatrix}}}$

и

${\displaystyle (A-I)^{2}={\begin{bmatrix}-4&0&-8\\-4&0&-8\\4&0&8\end{bmatrix}},\qquad (A-I)(A+I)={\begin{bmatrix}0&4&4\\0&2&2\\0&-2&-2\end{bmatrix}}}$

Таким образом (-4, -4, 4) является собственным вектором для -1, а (4, 2, -2) является собственным вектором для 1. (2, 3, -1) и (6, 5, -3) являются обобщенными собственными векторами, связанными с 1, любой из которых может быть объединен с (-4, -4, 4) и (4, 2, -2) сформировать основу обобщенных собственных векторов А. Найденные собственные векторы при необходимости можно нормализовать.

Собственные векторы нормальных матриц 3 × 3

Если матрица 3 × 3 ${\displaystyle A}$ является нормальным, то перекрестное произведение можно использовать для нахождения собственных векторов. Если ${\displaystyle \lambda }$ является собственным значением ${\displaystyle A}$, то пустое пространство ${\displaystyle A-\lambda I}$ перпендикулярно пространству столбцов, перекрестное произведение двух независимых столбцов ${\displaystyle A-\lambda I}$ будет в пустом пространстве. То есть это будет собственный вектор, связанный с ${\displaystyle \lambda }$. Поскольку в этом случае пространство столбцов двумерно, собственное подпространство должно быть одномерным, поэтому любой другой собственный вектор будет параллелен ему.

Если ${\displaystyle A-\lambda I}$ не содержит двух независимых столбцов, но не 0, перекрестное произведение можно использовать. В этом случае ${\displaystyle \lambda }$ является собственным значением кратности 2, поэтому любой вектор, перпендикулярный пространству столбцов, будет собственным вектором. Предполагать ${\displaystyle \mathbf {v} }$ ненулевой столбец ${\displaystyle A-\lambda I}$. Выберите произвольный вектор ${\displaystyle \mathbf {u} }$ не параллельно ${\displaystyle \mathbf {v} }$. потом ${\displaystyle \mathbf {v} \times \mathbf {u} }$ и ${\displaystyle (\mathbf {v} \times \mathbf {u} )\times \mathbf {v} }$ будет перпендикулярно ${\displaystyle \mathbf {v} }$ и, таким образом, будут собственными векторами ${\displaystyle \lambda }$.

Это не работает, когда ${\displaystyle A}$ не является нормальным, поскольку пустое пространство и пространство столбцов не обязательно должны быть перпендикулярными для таких матриц.

Смотрите также

• Список алгоритмов собственных значений

Примечания

1. Термин «обычный» используется здесь только для того, чтобы подчеркнуть различие между «собственным вектором» и «обобщенным собственным вектором».
2. где постоянный член умножается на единичную матрицу я.
3. Такой порядок внутреннего произведения (с линейно-сопряженным положением слева) предпочитают физики. Алгебраисты часто ставят сопряженно-линейную позицию справа: ш · v = v^* ш.

Рекомендации

1. Акслер, Шелдон (1995), "Долой детерминанты!" (PDF), Американский математический ежемесячный журнал, 102 (2): 139–154, Дои:10.2307/2975348, JSTOR  2975348, заархивировано из оригинал (PDF) на 2012-09-13, получено 2012-07-31
2. Ф. Л. Бауэр; К. Т. Фике (1960), "Нормы и теоремы исключения", Нумер. Математика., 2: 137–141, Дои:10.1007 / bf01386217
3. S.C. Eisenstat; I.C.F. Ипсен (1998), «Результаты относительных возмущений для собственных значений и собственных векторов диагонализуемых матриц», КУСОЧЕК, 38 (3): 502–9, Дои:10.1007 / bf02510256
4. Томпсон, Р. К. (июнь 1966 г.). «Главные подматрицы нормальной и эрмитовой матриц». Иллинойсский журнал математики. 10 (2): 296–308. Дои:10.1215 / ijm / 1256055111.
5. Питер Найлен, Тин-Яу Там и Фрэнк Улиг (1993). «О собственных значениях главных подматриц нормальной, эрмитовой и симметричной матриц». Линейная и полилинейная алгебра. 36 (1): 69–78. Дои:10.1080/03081089308818276.
6. Н. Бебиано, С. Фуртадо, Ж. да Провиденсия (2011). «О собственных значениях главных подматриц J-нормальных матриц». Линейная алгебра и ее приложения. 435 (12): 3101–3114. Дои:10.1016 / j.laa.2011.05.033.
7. Форрестер П.Дж., Чжан Дж. (2019). «Проекции одного ранга и рандомизированная проблема Хорна». arXiv:1905.05314 [математика ].
8. Denton PB, Parke SJ, Tao T, Zhang X (2019). «Собственные векторы из собственных значений». arXiv:1908.03795 [math.RA ].
9. Press, William H .; Teukolsky, Saul A .; Веттерлинг, Уильям Т .; Фланнери, Брайан П. (1992). Числовые рецепты на C (2-е изд.). Издательство Кембриджского университета. ISBN  978-0-521-43108-8.
10. Коукли, Эд С. (май 2013 г.), «Быстрый алгоритм« разделяй и властвуй »для вычисления спектров вещественных симметричных трехдиагональных матриц», Прикладной и вычислительный гармонический анализ, 34 (3): 379–414, Дои:10.1016 / j.acha.2012.06.003
11. Неймейр, К. (2006), "Геометрическая теория для предобусловленной обратной итерации IV: О наиболее быстрых случаях сходимости.", Линейная алгебра Appl., 415 (1): 114–139, Дои:10.1016 / j.laa.2005.06.022
12. Li, T. Y .; Цзэн, Чжунган (1992), "Итерация Лагерра в решении симметричной трехдиагональной проблемы собственных значений - новый взгляд", Журнал SIAM по научным вычислениям
13. Чу, Муди Т. (1988), "Заметка о методе гомотопии для линейных алгебраических задач на собственные значения", Линейная алгебра Appl., 105: 225–236, Дои:10.1016/0024-3795(88)90015-8
14. Dhillon, Inderjit S .; Parlett, Beresford N .; Фемель, Кристоф (2006), «Разработка и реализация алгоритма MRRR» (PDF), Транзакции ACM на математическом ПО, 32 (4): 533–560, Дои:10.1145/1186785.1186788
15. Смит, Оливер К. (апрель 1961 г.), "Собственные значения симметричной матрицы 3 × 3", Коммуникации ACM, 4 (4): 168, Дои:10.1145/355578.366316

дальнейшее чтение

• Bojanczyk, Adam W .; Адам Лютоборски (январь 1991 г.). «Вычисление углов Эйлера симметричной матрицы 3x3». Журнал SIAM по матричному анализу и приложениям. 12 (1): 41–48. Дои:10.1137/0612005.