Собственные значения сложной системы

[gobas]

Может быть глупый вопрос, но я что-то не встречал таких задач в литературе.

Нужно найти спектр такой системы уравнений:

\lambda Ax+\lambda By=Cx+Dy
\lambda Ax+\lambda By=Ex+Fy

x,y- неизвестные векторы, A,B,С,D,E,F- некие матрицы

Кто-нибудь знает, хотя бы, как называются такие задачи?
Для каких матриц возможно найти решение?

[Руст]

Может что то напутали, если из первого вычесть второе, то слева 0.

[gobas]

Все так и есть

[Yuri Gendelman]

gobas писал(а):

Все так и есть

Ну если все так и есть, то:
1. Вычитаем 1-е уравнение из 2-го, откуда
y = (F-D)^-^1 (C-E) x
2. Подставляем в 1-е уравнение и получаем стандартную задачу на С.З.
\lambda [A + B (F-D)^-^1 (C-E)] x = [C + D (F-D)^-^1 (C-E)] x

Писал утром, так что возможны описки. Но принцип, надеюсь, понятен

[gobas]

Спасибо,
принцип, конечно ясен.
Ну а если мы ничего не знаем про обратимость F-D?

[AHOHbIMHO]

gobas писал(а):

Может быть глупый вопрос, но я что-то не встречал таких задач в литературе.

Нужно найти спектр такой системы уравнений:

\lambda Ax+\lambda By=Cx+Dy
\lambda Ax+\lambda By=Ex+Fy

x,y- неизвестные векторы, A,B,С,D,E,F- некие матрицы

Кто-нибудь знает, хотя бы, как называются такие задачи?
Для каких матриц возможно найти решение?

Сводится к обобщенной задаче на собственные значения для матриц с размерами в два раза больше чем у исходных.

$ \lambda \left( \begin{array} {cc} A & B \\ A & B \end{array} \right) \left( \begin{array} {c} x \\ y \end{array} \right)=\left( \begin{array} {cc} C & D \\ E & F \end{array} \right) \left( \begin{array} {c} x \\ y \end{array} \right) $

[gobas]

Спасибо, это то, что я хотел услышать.

ps. Хм. я тоже с физфака, но термин обобщенные задачи на собственные значения не слышал

[AHOHbIMHO]

gobas писал(а):

Спасибо, это то, что я хотел услышать.

ps. Хм. я тоже с физфака, но термин обобщенные задачи на собственные значения не слышал

Вполне возможно, что я неправильно перевел
"Generalized Eigenvalue Problem"

Смотрите MKL, LAPACK.

[Yuri Gendelman]

AHOHbIMHO писал(а):

Вполне возможно, что я неправильно перевел

Перевод правильный. В справочнике Уилкинсона и Райниша кратко описаны алгоритмы. А вот тексты программ действительно лучше брать из LAPACK. Они по крайней мере без опечаток. Подробнее теория изложена в книге Уилкинсона.

gobas писал(а):

Ну а если мы ничего не знаем про обратимость F-D?

... то и обобщенная проблема собственных значений не поможет.

Хотя о числненном решении разговора не было, насчет практического применения приведенной AHOHbIMHO ( ) системы у меня есть большие сомнения. Уж очень мне ранг матрицы слева не нравится.

[Yuri Gendelman]

К сожалению я ошибся при цитировании (по памяти) Уилкинсона и Райнша. Хотя термин обобщенная задача мне кажется правильнее, переводчик использовал другой: Полная проблема собственных значений для систем уравнений общего вида.
А вот в книге: Парлетт Б. Симметричная проблема собстенных значений. Численные методы М. Мир. 1983 (есть в Библиотеке) последняя глава - Обобщенная линейная проблема собстенных значений.

Кроме того, Уилкинсон и Райнш также рассматривают только симметрические матрицы. Точнее:
A x = \lambda B x
или
A B x = \lambda x ,
где A и B - симметрические матрицы и B положительно определена.

Кстати, и алгоритм, который я предложил, тоже приводит к обобщенной (полной) задаче на С.З., первый вариант.

Точные ссылки:
1. Уилкинсон, Райнш. Справочник алгоритмов на языке АЛГОЛ: Линейная алгебра. М., "Машиностроение", 1976.
2. J.H.Wilkinson, C.Reinsch. Handbook for Automatic Computation: Linear Algebra. Springer-Verlag. 1971.
3. Парлетт Б. Симметричная проблема собстенных значений. Численные методы. М. Мир. 1983.

[AHOHbIMHO]

Yuri Gendelman писал(а):

AHOHbIMHO писал(а):

Хотя о числненном решении разговора не было, насчет практического применения приведенной AHOHbIMHO ( ) системы у меня есть большие сомнения. Уж очень мне ранг матрицы слева не нравится.

Ничего страшного с рагном матрицы. Практическое применение сводится к определению корней полинома относительно $\lambda$.

Т.е. всего лишь ( ) нужно найти корни этого уравнения:
$ \det \left( \begin{array} {cc} \lambda A - C & \lambda B - D\\ \lambda A - E& \lambda B - F\end{array} \right) = 0$

или, что то же самое (вторая сторка заменяется на разность второй и первой строки):

$ \det \left( \begin{array} {cc} \lambda A - C & \lambda B - D\\ C - E& D - F\end{array} \right) = 0$

Видим, что максимальная степень полинома равна размерности матриц A,B,C,D,E,F.

[Yuri Gendelman]

To AHOHbIMHO

Да, ничего страшного, если непосредственно решать характеристическое уравнение. Т.е. задача может иметь решение. Или нет (если F=D и E != C). Я имел в виду несколько другое: как ее решать практически, используя LINPACK, LAPACK, etc.

Например, по аналогии с алгоритмом Уилкинсона для симметричных A и B:
0. Решаем задачу P x = \lambda Q x
1. Треугольное разложение по Крауту: Q = L U
2. Сведение к стандартной несиммертичной задаче на С.З.
(L^-^1 P U^-^1) (U x) = \lambda (U x)
Получаем С.З. и повернутые С.В. (y)
3. Решение системы U x = y

А матрица Q - это ведь и есть матрица \left( \begin{array} {cc} A & B \\ A & B \end{array} \right). Вот я и представил, как на 1-м этапе передаю ее в Unsoldet и получаю: "матрица вырождена"...

[незваный гость]

А не может помочь переписать
$ \lambda \left( \begin{array} {cc} A & B \\ A & B \end{array} \right) \left( \begin{array} {c} x \\ y \end{array} \right)=\left( \begin{array} {cc} C & D \\ E & F \end{array} \right) \left( \begin{array} {c} x \\ y \end{array} \right) $ как $ \left( \begin{array} {cc} C & D \\ E & F \end{array} \right)^{-1} \left( \begin{array} {cc} A & B \\ A & B \end{array} \right) \left( \begin{array} {c} x \\ y \end{array} \right)= \frac{1}{\lambda} \left( \begin{array} {c} x \\ y \end{array} \right) $. То есть, коли $\left( \begin{array} {cc} C & D \\ E & F \end{array} \right)$ невырождена, мы сводим к классической задаче о собственных значениях. Работает, конечно, не всегда.

[Yuri Gendelman]

Ну я бы лично использовал вариант из моего первого поста в этой теме.

Первоначально gobas спрашивал, как называются такие задачи и как их решать.
Т.к. исходная задача не стандартная, я предложил свести ее к обобщенной порядка N. Но оказалось, что память об обобщенных задачах на С.З. уже утеряна . АНОНЫМНО это понял, объяснил этот термин, но для простоты свел исходную к обобщенной задаче на С.З. порядка 2*N. Далее пошла академическая дискуссия.

Мое мнение как практика: система порядка 2*N объясняет суть дела лучше, чем мой вариант. Для чего-то вроде анализа NP-полноты этого достаточно. Для практических расчетов лучше использовать вариант с системой порядка N.
"Если конечно вас интересует результат" (Мих.Жван.)