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

В интерполяционном методе мы находили явное выражение для характеристического многочлена только затем, чтобы иметь способ экономного вычисления этого многочлена при заданных X. Однако для трехдиагональных матриц (даже очень высокого порядка) есть способ быстрого вычисления без нахождения явного выражения характеристического многочлена. Это существенно, ибо матрицы общего вида можно привести к трехдиагольной форме преобразованием подобия.

Рис. 30.

Рассмотрим этот способ. Обозначим главный минор порядка матрицы через . Разложим такой минор по элементам последней строки; в ней всего два ненулевых элемента (рис. 30), так что получим

где через обозначен минор, дополняющий элемент Этот минор содержит в последнем столбце только один ненулевой элемент поэтому его целесообразно разложить по элементам последнего столбца:

Подставляя (12) в (11), найдем рекуррентное соотношение, выражающее минор высшего порядка через низшие:

Для начала расчета по рекуррентной формуле надо задать два первых минора. Удобно формально положить

Подставляя эти значения в (13) и вычисляя легко убедиться, что результат получается правильным. Следовательно, такой способ начала счета приемлем.

Однократный расчет величины определителя по формулам (11)-(14) требует всего арифметических действий, причем среди них нет делений, и вычисления очень быстрые и устойчивые. Таким образом, имеется быстрый способ нахождения характеристического многочлена при заданном значении X.

Имеется способ нахождения характеристического многочлена, более экономичный при многократных вычислениях. Преобразуя рекуррентное соотношение (13), можно получить коэффициенты характеристического многочлена в форме Горнера. Однократное же вычисление многочлена по схеме Горнера требует всего действий. Однако устойчивость этого процесса для высоких порядков матрицы, по-видимому, хуже, а формулы расчета более сложны.

Еще один несложный способ вычисления характеристического многочлена заключается в следующем. Вычтем заданное значение X из диагональных элементов а затем найдем определитель получившейся трехдиагональной матрицы по формулам прямого хода прогонки (5.12) — (5.13). Однако этот способ менее экономичен и устойчив, чем расчет по формуле (13).

Корни многочлена удобнее всего находить методом парабол (см. § 2 главы V). Этот метод для многочленов не слишком высокой степени достаточно устойчив и позволяет найти все корни с 5 — 7 верными знаками, даже если среди корней есть кратные. В библиотеках многих ЭВМ имеются стандартные программы вычислений всех корней многочлена методом парабол.

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

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

Поскольку явного выражения характеристического многочлена мы не выписываем, то для вычисления надо находить отдельно числитель и знаменатель при требуемых значениях Я. Это немного увеличивает объем расчетов.

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