Главная > Математика > Алгебраическая проблема собственныx значений
<< Предыдущий параграф
Следующий параграф >>
<< Предыдущий параграф Следующий параграф >>
Макеты страниц

Анализ ошибок

65. Используя симметрию, мы предполагаем, что элементы которые были бы равны нулю при точных вычислениях, на самом деле будут пренебрежимо малыми. Важно оправдать это предположение, и, к счастью, это почти следует из нашего общего анализа § 45 гл. 3. Если вычисленная матрица (с точными нулями под диагональю), а точные матрицы отражения, соответствующие последовательным вычисленным приведенным матрицам, то имеем

где мала. На самом деле, вычисляя только часть мы используем в точности те же арифметические операции, какие использовались бы при вычислении всей этой матрицы.

Умножим теперь вычисленную последовательно на вычисленные матрицы отражения Несмотря на все возможные ошибки округления, результирующая матрица наверняка имеет только поддиагональных элементов в каждом столбце. При условии, что были проведены полные вычисления, общий анализ показывает, что удовлетворяет соотношению

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

Для вычислений с плавающей запятой и накоплением скалярных произведений можно показать, что

с некоторой постоянной К, так что можно ожидать очень высокую точность.

На одном шаге QR приблизительно в три раза больше работы, чем на одном шаге LR Холецкого, хотя мы видели (§ 51), что если не используется сдвиг, один шаг QR эквивалентен двум шагам LR Холецкого. Выбор сдвига значительно проще для Если брать то сходимость обязательно будет кубическая. Если брать равным наименьшему собственному значению матрицы второго порядка из нижнего правого угла, то получим даже лучшую сходимость. Обычно на практике требуется очень мало итераций. Нет гарантии, что собственные значения будут

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

Выбор сдвига в LR Холецкого значительно сложнее, если используется техника Рутисхаузера с неудачными разложениями, но тем не менее эта схема весьма эффективна. Собственные значения всегда находятся в возрастающем порядке, и это важно, так как ленточные матрицы обычно возникают в конечноразностных приближениях дифференциальных уравнений, а там существенны только малые собственные значения. В целом кажется, что техника Рутисхаузера предпочтительнее, хотя можно многое сказать в пользу обоих методов.

<< Предыдущий параграф Следующий параграф >>
Оглавление