2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




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

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

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

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

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

 
 
 
 
Сообщение28.02.2006, 14:58 
Может что то напутали, если из первого вычесть второе, то слева 0.

 
 
 
 
Сообщение28.02.2006, 15:17 
Все так и есть

 
 
 
 
Сообщение28.02.2006, 16:00 
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

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

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

 
 
 
 Re: Собственные значения сложной системы
Сообщение28.02.2006, 16:57 
Аватара пользователя
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) $

 
 
 
 
Сообщение28.02.2006, 17:05 
Спасибо, это то, что я хотел услышать.

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

 
 
 
 
Сообщение28.02.2006, 17:36 
Аватара пользователя
gobas писал(а):
Спасибо, это то, что я хотел услышать.

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


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

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

 
 
 
 
Сообщение28.02.2006, 20:29 
AHOHbIMHO писал(а):
Вполне возможно, что я неправильно перевел

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

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

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

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

 
 
 
 
Сообщение01.03.2006, 15:13 
К сожалению я ошибся при цитировании (по памяти) Уилкинсона и Райнша. Хотя термин обобщенная задача мне кажется правильнее, переводчик использовал другой: Полная проблема собственных значений для систем уравнений общего вида.
А вот в книге: Парлетт Б. Симметричная проблема собстенных значений. Численные методы М. Мир. 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.

 
 
 
 
Сообщение01.03.2006, 19:35 
Аватара пользователя
Yuri Gendelman писал(а):
AHOHbIMHO писал(а):
Хотя о числненном решении разговора не было, насчет практического применения приведенной AHOHbIMHO ( :D ) системы у меня есть большие сомнения. Уж очень мне ранг матрицы слева не нравится.


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

Т.е. всего лишь ( :wink: ) нужно найти корни этого уравнения:
$  \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.

 
 
 
 
Сообщение01.03.2006, 21:29 
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 и получаю: "матрица вырождена"...

 
 
 
 
Сообщение01.03.2006, 23:11 
Аватара пользователя
:evil:
А не может помочь переписать
$ \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)$ невырождена, мы сводим к классической задаче о собственных значениях. Работает, конечно, не всегда.

 
 
 
 
Сообщение01.03.2006, 23:43 
Ну я бы лично использовал вариант из моего первого поста в этой теме.

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

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

 
 
 [ Сообщений: 14 ] 


Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group