АвтоАвтоматизацияАрхитектураАстрономияАудитБиологияБухгалтерияВоенное делоГенетикаГеографияГеологияГосударствоДомДругоеЖурналистика и СМИИзобретательствоИностранные языкиИнформатикаИскусствоИсторияКомпьютерыКулинарияКультураЛексикологияЛитератураЛогикаМаркетингМатематикаМашиностроениеМедицинаМенеджментМеталлы и СваркаМеханикаМузыкаНаселениеОбразованиеОхрана безопасности жизниОхрана ТрудаПедагогикаПолитикаПравоПриборостроениеПрограммированиеПроизводствоПромышленностьПсихологияРадиоРегилияСвязьСоциологияСпортСтандартизацияСтроительствоТехнологииТорговляТуризмФизикаФизиологияФилософияФинансыХимияХозяйствоЦеннообразованиеЧерчениеЭкологияЭконометрикаЭкономикаЭлектроникаЮриспунденкция

QR- алгоритм нахождения собственных значений

Читайте также:
  1. I. Случайные величины с дискретным законом распределения (т.е. у случайных величин конечное или счетное число значений)
  2. I.2.4. Алгоритм симплекс-метода.
  3. II. 4.1. Алгоритм метода ветвей и границ
  4. LU – алгоритм нахождения собственных значений для несимметричных задач
  5. SALVATOR - это переход физического явления в семантико-нейронный алгоритм (инструкцию) освобождения человека от негативных последствий этого явления.
  6. XII. ЭЛЕМЕНТЫ ТЕОРИИ АЛГОРИТМОВ
  7. Абсолютная и условная сходимость несобственных интегралов.
  8. Алгоритм
  9. Алгоритм
  10. Алгоритм
  11. Алгоритм

 

К исходной матрице A строится последовательность подобных матриц {Ak } по формулам Ak=QkRk; Ak+1= RkQk., где Q – ортогональная матрица, R – правая треугольная матрица.

Можем записать А=Q1Q2…Qn ∙Ak+1 ∙Qn-1… Q2-1Q1-1 или Ak=QkAk+1QkT любая их матриц {Ak} ортогонально - подобна A. Это процесс преобразование подобия, при этом собственные числа матриц Ak и Ak+1 совпадают.

Доказано, что при ряде ограничений (все собственные значения по модулю различны) на матрицу A, итерационный процесс осуществим и формируемая последовательность {Ak} сходится к матрицам треугольного вида, где на диагонал и стоят собственные значения.

Чаще всего QR - алгоритм применяется не к исходной матрице, а к подобной ей матрице почти треугольного вида.

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

→

Сведение матрицы к почти треугольному виду происходит путем преобразования Хаусхолдера за n-2 - шага с помощью элементарных преобразований отражения B=QAQT к исходной матрице, где Q=E-2UUT (U -вектор, Q -ортогональная матрица).

1 шаг. Обнуляем элементы первого столбца B1=QB0Q-1.

2 шаг. Обнуляем элементы второго столбца B2=QB1Q-1 и т.д.

 

Нам нужно найти элементы вектора U, на первом шаге задаем вектор следующем образом

где

 

 

Вектор U2T строится аналогично, только формируются нулевыми не одна, а первые две его координаты и определяющую роль играет второй столбец матрицы и его третий элемент.

 

Пример.

 

 


1 | 2 | 3 | 4 | 5 | 6 |

Поиск по сайту:

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