Поиск собственных значений матрицы методом бисекции

[Strelok42]

Доброго времени суток.
Пишу программу по нахождению собственных значений симметричной матрицы методом бисекции и хотел бы уточнить некоторые моменты, ато что то меня сомнения терзают в правильности моих мыслей по поводу решения данной задачки.
Если я правильно понял, то сначала надо привести матрицу к трехдиагональному виду, далее найти ее характеристический многочлен, а метод бисекции применить в нахождени корней этого многочлена. Верно мыслю? матрицу к трехдиагональному виду я привел, и далее окончательно запутался. Подкиньте идею куда дальше мыслить.

[Евгений Машеров]

Характеристический многочлен здесь не нужен. В явном виде, в смысле.
Число собственных значений матрицы $A-\lambda I$, больших$\lambda$ равно числу совпадений знаков в последовательности главных миноров матрицы $A-\lambda I$. При этом для трёхдиагональной существуют очень простые выражения для них.
http://num-anal.srcc.msu.ru/lib_na/int_ae/int_ae6.htm
Меняя $\lambda$, определяют интервал, которому принадлежит собственное значение, сокращая его до необходимой точности.

[Strelok42]

так насколько я разобрался:
собственных значений будет столько, сколько порядок матрицы.
Берем произвольную вещественную лямбду, считаем по рекурентным формулам.
Хотел бы уточнить, в рекурентной формуле для Pi 1 и 2 перед лямбдой обычные числа?
Далее смотрим кол-во одинаковых знаков, что и будет означать сколько у нас собственных чисел больших выбранной лямбды. Далее подбираем такую лямбду, чтобы было одно собственное значение большее лямбды. Вот только как правильнее определить вторую границу интервала? С одной стороны у нас будет границей лямбда, а вот сколько вторую границу брать(ибо ноль знаков то в Pi у нас не получится, чтобы точно вторую границу определить)

[sergei1961]

А как Вы произвольную симметрическую матрицу к 3-диагональной приводите?
А для численного решения проблемы собственных чисел есть специализированные книги.

[Strelok42]

я привожу ее методом вращений.
Специализированную книгу только одну нашел (Парлетт "Симметричная проблема собственных значений"), а так статьи только и главы книг.
Вот статья метод Хаусхолдераhttp://www.cyberguru.ru/programming/programming-theory/matrix-vectors-values-page8.html, а из книг, к примеру, можно взять Вержбицкий "Основы численных методов".

[Евгений Машеров]

(Оффтоп)

Цитата:

А для численного решения проблемы собственных чисел есть специализированные книги.

Здравия желаю товарищ капитан!
Рота по случаю Вашего прибытия построена!
Докладывал старшина роты прапорщик Ясненько!

1. Да. С.З. будет ровно столько, каков порядок матрицы. Слава Гауссу, никаких "жордановых ящиков" у симметричных матриц не бывает, кратность только алгебраическая.
2. Перед лямбдой никаких коэффициентов, равных 1 или 2 нет, есть индексы $\alpha_i$ и $p_{i-1}, p_{i-2}$
3. 0 совпадающих знаков? Отчего же не может быть? +, -, +, -...
Ни одного совпадения.

[ewert]

Strelok42 в сообщении #479431 писал(а):

Специализированную книгу только одну нашел (Парлетт "Симметричная проблема собственных значений"), а так статьи только и главы книг.

Полистайте замечательную книжку Воеводина и Кузнецова "Матрицы и вычисления" (из серии "Справочная математическая библиотека"; есть в сети). Она маленькая (порядка 300 страниц), поскольку там вообще никаких доказательств нет, а есть лишь набор очень большого количества фактов. Однако их расположение насколько хорошо продумано, что в большинстве случаев доказательство и не требуется -- каждый следующий факт или непосредственно вытекает из предыдущих, или предыдущие дают хороший намёк на следующие, так что логическая структура доказательства становится понятной хотя бы в принципе. При этом там помимо изложения собственно численных методов приводится и сравнительный анализ их эффективности, достоинств и недостатков.

[Евгений Машеров]

Да книг немало. Просто в большинстве симметричный случай рассмотрен наряду с несимметричным, в разных главах. Отдельно для симметричной - да, одна, по крайней мере на русском.
А так - Уилкинсон, "Алгебраическая проблема собственных значений" (и в пандан к ней Уилкинсон и Райнш, "Справочник алгоритмов на яызке Алгол"), Фадеев и Фадеева, "Вычислительные методы линейной алгебры", Воеводин "Вычислительные основы линейной алгебры" и др.

[Strelok42]

что то я тогда с совпадающими знаками не уяснил, получается так:
+, +, -,+ - 1 совпадение;
+,-,+,- - 0 совпадений;
+,0,-,+ -1 совпадение;
так чтоли выходит? Получается, знак сравнивается только с предыдущим? а ноль выступает как + либо -.

[Евгений Машеров]

Именно так. 0 можно волевым решением объявлять "+" или "-", но при следующем сравнении считать знак тем же, что и выбранный.