Преобразование - хаусхолдер
Cтраница 1
Преобразование Хаусхолдера и QL-алгоритм - наиболее эффективные методы для вычисления всех собственных значений и, если необходимо, собственных векторов. Соответствующие процедуры характеризуются большей скоростью в сравнении с процедурой jacobi, особенно когда требуется вычислять только собственные значения. В этом случае оптимальным является сочетание процедур tredl и tqll; если необходима экономия памяти, то процедуру tredl следует заменить процедурой tredS, поскольку в последней исходная симметрическая матрица записана в массиве лишь из Vg п ( я 1) элементов. Процедуры iredl и tql весьма эффективны, если требуется экономия памяти; лишь п2 0 ( п) ячеек памяти необходимо для решения полной проблемы. Ортогональность собственных векторов гарантирована с высокой точностью независимо от распределения собственных значений. [1]
В программе, представленной ниже, сначала исходная матрица будет приведена к двухдиагональной форме с помощью преобразования Хаусхолдера, а затем использован Q / - алгоритм для вычисления сингулярных чисел двухдиагональной матрицы. [2]
Поэтому оказывается, что первый шаг, состоящий в левом и правом умножении на Р1; имеет такой же вид, как шаги при преобразовании Хаусхолдера. [3]
Все три процедуры tred I, / red 2, tred 3 позволяют привести действительную симметрическую матрицу AJ к симметрической трехдиагональной форме An j с помощью преобразования Хаусхолдера. [4]
Матрица U - 1AU имеет удобный вид для нахождения собственных значений; здесь можно применить Q / J-алгоритм, но мы позволим себе небольшое отступление, чтобы обратить внимание на другие применения преобразования Хаусхолдера. [5]
В этом и заключается двушаговый Q - алгоритм Фрэнсиса [26, 95], который не содержит операций над комплексными числами ни на одном шаге. Теперь остается лишь рассмотреть преобразование Хаусхолдера для приведения матрицы вида ( 12) к форме Хессенберга. [6]
Однако предлагаемый вариант наиболее эффективен по времени счета, поскольку требует выполнения малого числа вращений и операций умножения. Однако исключительная слож ность организации преобразования Хаусхолдера для этого случая не дает своего обычного превосходства над методой Гивенса. [7]
Зато, если на каком-либо шаге внедиагональный элемент e ( s оказывается пренебрежимо малым, то матрица расщепляется на прямую сумму трехдиагональ-ных матриц меньшего порядка, причем собственные значения каждой подматрицы вычисляются независимо. Если трехдиагональная матрица AJ получена с помощью преобразования Хаусхолдера из исходной матрицы с кратными или очень близкими собственными значениями [52], то уже в процессе приведения она расщепляется на прямую сумму подматриц. При этом существенно упрощаются вычисления. Если исходная матрица имеет кратные собственные значения, то при точных расчетах трехдиагональная матрица должна расщепляться сразу, но в действительности так происходит не всегда. [8]
Процедура imtql 2 позволяет найти все собственные значения и собственные векторы симметрической трехдиагональной матрицы. Если трехдиагональная матрица Т получена с помощью преобразования Хаусхолдера из произвольной симметрической матрицы А, применением процедуры tred 2 ( алг. [9]
В том случае, когда матрица AI симметрическая и трехдиагональная, процесс особенно прост. Поэтому произвольную действительную симметрическую матрицу целесообразно привести к трехдиагоналыюй форме с помощью преобразования Хаусхолдера. [10]
Элементы вектора Ui размещаются в 1-ой строке массива п X п; целесообразно также запоминать величины u / А / в 1-ом столбце того же массива. Если необходимо сохранить исходную матрицу для последующего вычисления невязок, то перед выполнением преобразования Хаусхолдера и перемножением матриц преобразования ее следует переписать в рабочий массив г. Если матрица At при дальнейших вычислениях не требуется, то дополнительный массив памяти размера пХ п можно не использовать, если положить г а. В этом случае все промежуточные матрицы размещаются в массиве, где первоначально располагалась матрица А. [11]
В результате получаем - ту двухдиагональную форму, о которой говорили. Итак, мы проиллюстрировали снова, как можно быстро получить нули на нужных местах при помощи преобразований Хаусхолдера. [12]
Только нижняя треугольная часть массива а совместно с массивом е используется в процедуре trbak 1; в них содержится информация о преобразовании Хаусхолдера. [13]
 |
Собственные значения матриц X и Х -, вычисленные с помощью процедуры. [14] |
Комментарии к алгоритму П-3 полностью относятся и к данному алгоритму с неявным сдвигом. Однако для обычного алгоритма было существенным, чтобы в трехдиагональных матрицах с большим разбросом значений элементов наибольшие из них располагались в нижнем правом углу. Этот алгоритм используется в основном в тех случаях, когда исходная матрица является трехдиагональной. Если же исходная матрица произвольна, то уже при выполнении преобразования Хаусхолдера существенно, чтобы наибольшие элементы располагались в правом нижнем углу, и если это условие выполнено, то для трехдиагональной матрицы можно применять обычный QL-алгоритм. Скорость вычислений по обоим алгоритмам почти одинакова. [15]
Страницы: 1