2014 dxdy logo

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

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


Правила форума


В этом разделе нельзя создавать новые темы.

Если Вы хотите задать новый вопрос, то не дописывайте его в существующую тему, а создайте новую в корневом разделе "Помогите решить/разобраться (М)".

Если Вы зададите новый вопрос в существующей теме, то в случае нарушения оформления или других правил форума Ваше сообщение и все ответы на него могут быть удалены без предупреждения.

Не ищите на этом форуме халяву, правила запрещают участникам публиковать готовые решения стандартных учебных задач. Автор вопроса обязан привести свои попытки решения и указать конкретные затруднения.

Обязательно просмотрите тему Правила данного раздела, иначе Ваша тема может быть удалена или перемещена в Карантин, а Вы так и не узнаете, почему.



Начать новую тему Ответить на тему
 
 Собственные значения сложной системы
Сообщение28.02.2006, 13:52 


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

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

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

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

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

 Профиль  
                  
 
 
Сообщение28.02.2006, 14:58 
Заслуженный участник


09/02/06
4365
Москва
Может что то напутали, если из первого вычесть второе, то слева 0.

 Профиль  
                  
 
 
Сообщение28.02.2006, 15:17 


09/02/06
12
Все так и есть

 Профиль  
                  
 
 
Сообщение28.02.2006, 16:00 
Заслуженный участник


15/05/05
3444
USA
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 


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

 Профиль  
                  
 
 Re: Собственные значения сложной системы
Сообщение28.02.2006, 16:57 
Аватара пользователя


20/01/06
97
выпускник физфака МГУ
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 


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

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

 Профиль  
                  
 
 
Сообщение28.02.2006, 17:36 
Аватара пользователя


20/01/06
97
выпускник физфака МГУ
gobas писал(а):
Спасибо, это то, что я хотел услышать.

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


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

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

 Профиль  
                  
 
 
Сообщение28.02.2006, 20:29 
Заслуженный участник


15/05/05
3444
USA
AHOHbIMHO писал(а):
Вполне возможно, что я неправильно перевел

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

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

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

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

 Профиль  
                  
 
 
Сообщение01.03.2006, 15:13 
Заслуженный участник


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


20/01/06
97
выпускник физфака МГУ
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 
Заслуженный участник


15/05/05
3444
USA
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 
Заслуженный участник
Аватара пользователя


17/10/05
3709
: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 
Заслуженный участник


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

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

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

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 14 ] 

Модераторы: Модераторы Математики, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group