Хаусхолдер

Cтраница 2

В этом и заключается двушаговый Q - алгоритм Фрэнсиса [26, 95], который не содержит операций над комплексными числами ни на одном шаге. Теперь остается лишь рассмотреть преобразование Хаусхолдера для приведения матрицы вида ( 12) к форме Хессенберга. [16]

Однако предлагаемый вариант наиболее эффективен по времени счета, поскольку требует выполнения малого числа вращений и операций умножения. Однако исключительная слож ность организации преобразования Хаусхолдера для этого случая не дает своего обычного превосходства над методой Гивенса. [17]

Метод был впервые предложен в 1958 г. Хаусхолдером. [18]

Зато, если на каком-либо шаге внедиагональный элемент e ( s оказывается пренебрежимо малым, то матрица расщепляется на прямую сумму трехдиагональ-ных матриц меньшего порядка, причем собственные значения каждой подматрицы вычисляются независимо. Если трехдиагональная матрица AJ получена с помощью преобразования Хаусхолдера из исходной матрицы с кратными или очень близкими собственными значениями [52], то уже в процессе приведения она расщепляется на прямую сумму подматриц. При этом существенно упрощаются вычисления. Если исходная матрица имеет кратные собственные значения, то при точных расчетах трехдиагональная матрица должна расщепляться сразу, но в действительности так происходит не всегда. [19]

Процедура imtql 2 позволяет найти все собственные значения и собственные векторы симметрической трехдиагональной матрицы. Если трехдиагональная матрица Т получена с помощью преобразования Хаусхолдера из произвольной симметрической матрицы А, применением процедуры tred 2 ( алг. [20]

В том случае, когда матрица AI симметрическая и трехдиагональная, процесс особенно прост. Поэтому произвольную действительную симметрическую матрицу целесообразно привести к трехдиагоналыюй форме с помощью преобразования Хаусхолдера. [21]

Элементы вектора Ui размещаются в 1-ой строке массива п X п; целесообразно также запоминать величины u / А / в 1-ом столбце того же массива. Если необходимо сохранить исходную матрицу для последующего вычисления невязок, то перед выполнением преобразования Хаусхолдера и перемножением матриц преобразования ее следует переписать в рабочий массив г. Если матрица At при дальнейших вычислениях не требуется, то дополнительный массив памяти размера пХ п можно не использовать, если положить г а. В этом случае все промежуточные матрицы размещаются в массиве, где первоначально располагалась матрица А. [22]

Теория нахождения сразу всех собственных значений сложна и ее нельзя как следует изложить в элементарном курсе. В настоящее время для симметричных матриц, по-видимому, лучшим из прямых методов является модификация Хаусхолдера метода Гивенса. [23]

В результате получаем - ту двухдиагональную форму, о которой говорили. Итак, мы проиллюстрировали снова, как можно быстро получить нули на нужных местах при помощи преобразований Хаусхолдера. [24]

Только нижняя треугольная часть массива а совместно с массивом е используется в процедуре trbak 1; в них содержится информация о преобразовании Хаусхолдера. [25]

Метод Хаусхолдера позволяет привести матрицу к трехдиагональному виду, выполнив почти вдвое меньше вычислений по сравнению с другими методами. Это обусловлено тем, что при его применении становятся нулевыми сразу все элементы строк и столбцов, стоящие вне трех диагоналей матрицы. Метод Хаусхолдера позволяет получить требуемый результат быстрее, чем метод Гивенса, так как связан с выполнением меньшего числа, хотя и более сложных преобразований. Это его свойство особенно ярко проявляется применительно к большим матрицам. [26]

То обстоятельство, что любую ортогональную матрицу можно представить произведением матриц отражения, кажется, не слишком широко известно. Таким образом класс отражений достаточно богат для любого случая; при этом каждый его член характеризуется единственным вектором, указывающим положение соответствующего зеркала. Этим матрицам по праву принадлежит высокий статус, хотя им совершенно не уделяли внимания до 1958 года, когда Хаусхолдер выступил с предложением использовать их в численной алгебре. [27]

Тщательное изучение матриц ведется уже давно, и про них известно очень много. Они встречаются и во многих различных физических задачах. В результате на эту тему имеется огромная литература и многочисленные методы для различных задач. Рассмотрим лишь несколько примеров и отошлем читателя за дальнейшими сведениями к следующим книгам: Ральстон и Уилф [37], Современные вычислительные методы [29] и Хаусхолдер [16], главным образом к библиографии в двух последних. [28]

Мы предполагаем, что вычисленное К - очень близкое приближение к искомому числу Я. Для того чтобы найти следующее собственное значение, Q - алгоритм продолжают с меньшей матрицей ( порядка три на рисунке) в верхнем левом углу. Это дает систематическую процедуру для нахождения всех собственных значений. Теперь QR-алгоритм полностью описан и осталось определить только собственные векторы, что делается за один шаг обратного степенного метода, и пользоваться обращением в нуль соответствующих элементов матрицы в процедуре Хаусхолдера. [29]

Собственные значения матриц X и Х -, вычисленные с помощью процедуры. [30]

Страницы: 1 2 3