Ql-алгоритм

Cтраница 3

Вариант PWK QL-алгоритма без квадратных корней ( § 8.15) не был опубликован в открытой литературе. Кроме того, скорейший путь вычисления полного набора ортонормированных собственных векторов состоит в выполнении QL-алгоритма на основе быстрых преобразований Гивенса при использовании ранее вычисленных собственных значений в качестве сдвигов. Кажется, эта комбинация методов никем до сих пор не была указана. [31]

Этот прием иногда называют неявным сдвигом и соответствующий алгоритм - QL-алгоритмом с неявным сдвигом. Франсис первоначально предложил прием неявного сдвига в связи с выполнением двух шагов QR-алгоритма для несимметрической матрицы; аналогичным образом можно выполнить единственный шаг QL-алгоритма. Соответствующая процедура описана в следующем алгоритме. [32]

Специалисты по численному анализу должны испытывать некоторое удовлетворение от того, что наилучшим методом оказался не какой-то очевидный способ вроде степенного метода либо характеристического многочлена, либо той или иной формы метода Ньютона, а последовательность сложных преобразований подобия. Понимание алгоритма улучшалось постепенно, и сейчас мы имеем элегантное объяснение того, почему он всегда работает. Сначала излагается теория, а затем не менее интересные схемы реализации процесса. Из соображений эффективности QL-алгоритм обычно применяют к матрицам с малой шириной ленты. [33]

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

Комментарии к алгоритму П-3 полностью относятся и к данному алгоритму с неявным сдвигом. Однако для обычного алгоритма было существенным, чтобы в трехдиагональных матрицах с большим разбросом значений элементов наибольшие из них располагались в нижнем правом углу. Этот алгоритм используется в основном в тех случаях, когда исходная матрица является трехдиагональной. Если же исходная матрица произвольна, то уже при выполнении преобразования Хаусхолдера существенно, чтобы наибольшие элементы располагались в правом нижнем углу, и если это условие выполнено, то для трехдиагональной матрицы можно применять обычный QL-алгоритм. Скорость вычислений по обоим алгоритмам почти одинакова. [35]

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