Метод интерполяции для построения характеристического многочлена

В основе метода интерполяции для построения характеристического многочлена лежит известная теорема алгебры о единственности интерполяционного многочлена. Задача об определении коэффициентов p_t (i = 1, …, п) характеристического многочлена степени п сводится к задаче построения интерполяционного многочлена степени п по известным значениям его в узловых точках. Коэффициент при неизвестном в степени п в уравнении (1.33) равен (-1)^л. Для этого задается п различных значений X = р., / = 1, 2, …, п, и для каждого из этих значений вычисляется значение определителя det (А — Р_}Е) = а. Значения Р^ могут выбираться произвольно, но для уменьшения влияния ошибок округления желательно узлы интерполяции располагать равномерно внутри интервала (X_min, X_max). Для оценки границ интервала можно использовать соотношение тах|Х| < ||А ||, где ||А||— любая норма матрицы А.

Для определения p_t (i = 1, …, п) записывается система п линейных уравнений.

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

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

Для применения метода интерполяции требуется вычислить п определителей порядка п. Вместе с построением интерполяционного многочлена по интерполяционной формуле метод требует примерно п⁴ операций, что приводит для больших значений п к довольно большому объему вычислений. Однако более серьезным обстоятельством, ограничивающим применение метода интерполяции, является то, что нули многочлена (т. е. искомые собственные значения) могут быть весьма чувствительны к погрешностям коэффициентов многочлена. Неизбежные и, возможно, достаточно большие погрешности вычисления коэффициентов Р_п в методе интерполяции приводят к существенному снижению точности определения собственных значений при больших п. По этой причине метод интерполяции редко используется при п > 10.

Последний недостаток метода интерполяции можно устранить, если использовать метод ЛОКАЛЬНОЙ ИНТЕРПОЛЯЦИИ. В нем восстанавливается не весь характеристический многочлен, а некоторая его часть вблизи корня. Вычислив det (А — ХЕ) в трех точках, можно построить в окрестности корня многочлен второй степени и далее, решая квадратное уравнение, определить корни. Для нахождения корня используется метод парабол. Метод локальной интерполяции обладает тем преимуществом, что избавляет от необходимости строить многочлен высших степеней. Он пригоден для матриц любых видов и может быть использован для решения частичной, полной, обобщенной и общей проблем.

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