Трехдиагональные матрицы

8. Возвратимся к вычислению где А — трехдиагональная матрица. Обозначим

и пусть главные ведущие миноры порядка Раскладывая по его последней строке, получим

где

Произведения ргуг могут быть вычислены раз и навсегда. Можно предполагать, что так как иначе мы можем иметь дело с трехдиагональными матрицами более низкого порядка. Для каждого вычисления необходимо умножений.

Если требуются значения производных то они могут быть вычислены одновременно с вычислением значений самого определителя. В самом деле, дифференцируя (8.2), имеем

и

Так как точность вычисленных корней определяется по существу точностью вычисленных значений самой функции, мы ограничимся анализом ошибок алгорифма, описанного в (8.2). На практике почти необходимо использование арифметики с плавающей запятой. Вычисленные величины удовлетворяют соотношениям

где

Следовательно, как в симметричном случае (гл. 5, § 40), вычисленная последовательность является точной для трехдиагональной матрицы с элементами где

Поэтому можно предположить, что

так что соответствуют малым относительным ошибкам. С другой стороны, имеем

и мы не можем гарантировать, что это соответствует малым относительным ошибкам в Однако, мы можем ограничиться лишь такими значениями что

так что возмущения аг малы по сравнению с нормой А.

9. Заметим, что если А — какая-либо матрица, полученная при помощи диагонального преобразования подобия матрицы А, то и произведения для совпадают, хотя числа обусловленности собственных значений, вообще говоря, будут различны. Вычисленные последовательности будут одинаковыми для всех таких А. Следовательно, если мы имеем, например, матрицу А вида

то при анализе ошибок мы можем использовать матрицу А вида

Конечно, мы должны ограничить исследуемые значения z областью а не . В общем случае мы будем считать А уравновешенной матрицей (гл. 6, § 10).

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

В гл. 6, § 49 мы рекомендовали использовать арифметику с двойной точностью при приведении матрицы Хессенберга к трехдиагональному виду, даже если матрица Хессенберга была получена из матрицы общего вида с использованием обычной точности. Это было направлено против возможного возникновения «неустойчивых» стадий при приведении к трехдиагональному виду. Естественно поставить вопрос, можем ли мы вернуться к вычислениям с обычной точностью при вычислениях Если при приведении к трехдиагональному виду не было неустойчивых стадий, то это сделать возможно, но если неустойчивые стадии были, то возвращение к работе с обычной точностью было бы ошибкой. Следующий элементарный анализ показывает, почему это так.

Мы видели в гл. 6, § 46, что в случае появления неустойчивости соответствующая трехдиагональная матрица имеет элементы, типичный порядок величин которых выражен в матрице

но собственные значения которой порядка 1, а не как можно предположить по величине нормы. Мы показали, что соответствующие правый и левый собственные векторы, нормированные так, что имеют компоненты порядка

Далее, наш анализ ошибок § 8 показал, что эквивалентное возмущение, соответствующее вычислению с использованием -значной арифметики, имеет порядок величин

Следовательно, из гл. 2, § 9, следует, что порядок величины возмущения собственного значения будет, вообще говоря, равен порядку величины и мы имеем

Это показывает, что при вычислении следует использовать ту же точность, что и при приведении. Однако, как показано в гл. 6, § 49, можно ожидать, что, вообще говоря, двойной точности будет достаточно, если только исходная матрица не слишком плохо обусловлена. Это значительно более удовлетворительная ситуация, чем в случае, связанном с формой Фробениуса.