Cтраница 2
Потребность именно в простом тесте связана с тем обстоятельством, что QL-алгоритм может преобразовать Т в матрицу Т, более близкую к диагональной, ценой приблизительно 11 п умножений и п квадратных корней. [16]
В [18] приведены программы, реализующие метод вращений Якоби для симметричных матриц, QR-алгоритм и QL-алгоритм, а также QR-алгоритм со сдвигом. [17]
В общем случае наддиагональный элемент ( As) ij матрицы As на s - ом шаге QL-алгоритма асимптотически равен ki / ( Я 7Л -) 5, где ki / - постоянная величина. Скорость сходимости алгоритма, определенного соотношениями ( 4), вообще говоря, недостаточна. [18]
Никому еще не удалось построить матрицу Alt такую, чтобы в точной арифметике последовательность As, порождаемая QL-алгоритмом со сдвигами (8.7.1), не сходилась и в то же время была нестационарна, хотя такие матрицы и должны существовать. Простая стратегия сдвигов по отношениям Релея превращает QL в мощное средство диагонализации матрицы. В § 8.9 будет описана несколько более сложная стратегия, дающая еще лучшие результаты. [19]
Преимущество вычисления собственных значений QL-алгорит-мом перед методом Ньютона состоит не столько в числе операций, сколько в гарантированной сходимости QL-алгоритма со сдвигом по Уилкинсону. Чтобы заставить метод Ньютона сходиться во всех ситуациях, требуется гораздо более тщательная реализация. [20]
Если нужны 4 собственных значения матрицы А порядка 400 с шириной ленты 41, то было бы не очень эффективно приводить А к трехдиагональной форме в соответствии с § 7.5. Поскольку ширина ленты сохраняется, QL-алгоритм со сдвигами можно реализовать, экономя как память, так и количество операций. Алгоритм оформлен как алгоритм П / 7 Справочника. Это-хороший образец математического обеспечения, далекий от слепой реализации преобразования, описанного в § 8.2. Мы не станем входить в детали, однако у. [21]
Неясно, чем матрица В лучше В; никаких нулевых элементов в ней не появилось. Тем не менее QL-алгоритм со сдвигами упорно повторяет преобразование В - - В. [22]
В контексте обратной итерации единственный вектор, которым мы располагаем на fe - м шаге, - - это текущее приближение uk к собственному вектору; естественно поэтому брать в качестве сдвига отношение Релея. Однако в случае QL-алгоритма имеется матрица Ал, и потому можно вычислить более точное приближение к A.J. Более того, если А1 трехдиагональная, то это уточненное значение можно получить очень малой ценой. Прежде чем подробно обсудить такие сдвиги, посмотрим на результат одного QL-преобразования с произвольным сдвигом а для трехдиагональной матрицы А. [23]
Именно это происходит в трех-диагональном QL-алгоритме гл. Подобные преобразования продолжают до тех пор, пока матрица не окажется приведенной ( с рабочей точностью), после чего исчерпывание происходит естественным образом. [24]
Если отказаться от привычки аннулировать матричный элемент на каждом шаге, то можно выполнить плоское вращение в плоскости ( п - 1, п) с углом, отличающимся от якобиева. Это позволит включить сдвиги в QL-алгоритм и тем самым очень сильно ускорить сходимость. [25]
При использовании QL-алгоритма без операции извлечения квадратного корня с разумными сдвигами все 0 - могут быть вычислены примерно за 9 / 2 умножений. С другой стороны, комбинируя QL-алгоритм с делением спектра, можно вычислить р экстремальных собственных чисел в каждом конце спектра приблизительно за Збр / умножений. При этом мы отводим 1.8 QL-итераций на одно собственное число и 10 / умножений на одну QL-итерацию. [26]
Предполагать, что для вычисления 2v собственных чисел Т применяется ленточный QL-алгоритм ( см. § 8.16) и тратится в среднем два QL-преобразоваиия на одно собственное число. [27]
Этот прием иногда называют неявным сдвигом и соответствующий алгоритм - QL-алгоритмом с неявным сдвигом. Франсис первоначально предложил прием неявного сдвига в связи с выполнением двух шагов QR-алгоритма для несимметрической матрицы; аналогичным образом можно выполнить единственный шаг QL-алгоритма. Соответствующая процедура описана в следующем алгоритме. [28]
Хотя до 1958 г. ничего похожего на алгоритмы QR и QL не было и в помине, появившись, они быстро утвердились как самый эффективный способ нахождения всех собственных значений малой симметричной матрицы. Вначале посредством последовательности отражений ( § 7.4) заполненная матрица приводится к трех-диагональной форме, а затем QL-алгоритм быстро уменьшает величину внедиагональных элементов, пока они не станут пренебрежимо малыми. На каждом шаге алгоритма применяется довольно сложное подобное преобразование, чем порождается последовательность матриц, сходящаяся к диагональной матрице. Более того, сохраняется трехдиагональная форма. [29]
Если подлежат определению лишь некоторые из всех собственных значений, то методы предыдущего параграфа становятся неэффективными. Однако следует отметить, что сочетание процедур tredl и tqll ( или imtqll), либо tredZ и tql2 ( или imtql2) эффективно даже при вычислении 40 % от общего числа собственных значений. К сожалению, QL-алгоритм не приспособлен для вычисления отдельных собственных значений и, кроме того, представляется затруднительным предложить способ задания сдвига, который позволял бы выделить некоторые из наименьших собственных значений, что часто требуется на практике. [30]