velikol.ru
  1 ... 21 22 23 24 25
^

Лекция 2. Разложение на множители


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

Мы рассмотрим метод факторизации, основанный на преобразовании, которое используется в методе Бернулли (см., например, [1]). Метод Бернулли предназначен в основном для нахождения одного наибольшего по модулю корня, итерации в нем сходятся достаточно быстро, если этот корень заметно отличается по модулю от остальных корней. Рассматриваемый метод факторизации обладает быстрой сходимостью в том случае, если существует группа корней, заметно отличающихся по модулю от остальных корней полинома. Число корней в этой группе и степень получающегося делителя заранее знать не требуется, они определяются в процессе факторизации.

Рассмотрим приведенный полином:

Pn(x) = xn + a1xn – 1 + ... + an

(10.2.1)

Построим последовательность

μk = x1k + x2k + ... + xnk, k = 1, 2, ...

(10.2.2)

где xi, i = 1, 2, ..., n, – корни Pn(x).

Вычисление μk для k = 1, 2, ..., n производится по формулам (3.1.5). Для вычисления следующих значений μk для k = n + 1, n + 2, ... используется соотношение

μk + a1μk – 1 +...+ anμk – n = 0,

(10.2.3)

которое позволяет рекуррентно определить очередное значение μk через предыдущие.

Предположим теперь, что среди корней xi найдется группа корней x1x2,…, xs заметно превосходящих по модулю остальные корни ïxiï ³ qïxjï, i £ s, j > s, q > 1. Тогда начиная с некоторого значения k0 (по порядку величины такого, что qk0 @ 1 / d c) значения μk с точностью машинного представления будут равны

μk = x1k + x2k + ... + xsk, ³ k0.

Если среди корней x1x2,…, xs есть равные, то группируя их и изменяя, если нужно, нумерацию перепишем это соотношение в виде

μk = r1x1k + r2x2k + ... + rmxmk

(10.2.4)

Здесь rj – кратность корня xj, rj ³ 1. Отметим также, что все представленные здесь корни, очевидно отличны от нуля.

Рассматриваемый нами метод дает возможность, как мы увидим ниже, построить полином,

Qm(x) = xm + b1xm – 1 + ... + bm

(10.2.5)

корни которого суть x1x2,…, xm. Все они являются корнями P(x), следовательно, Q(x) является делителем P(x), что и решает задачу факторизации (второй делитель определяется путем деления P(x) на Q(x)).

Дадим определение: полином P(x) = xs + c1xs  1 + ... + cs будем называть аннулирующим полиномом для последовательности μk, если найдется такое k0, что для всех ³ k0 выполняется равенство

μk + c1μk – 1 +...+ сs μk – s = 0.

(10.2.6)

Полином будем называть l-аннулирующим, если равенство (10.2.6) справедливо для l последовательных значений k = k0, k0 + 1,…, k0 + – 1.

Очевидно, что аннулирующим полиномом является исходный полином Pn(x), при этом в качестве k0 можно взять значение k0 = n + 1, так чтобы выполнялось соотношение (10.2.3).

Покажем, что полином Qm(x), корнями которого служат x1x2,…, xm также является аннулирующим, если в качестве k0 взять значение, начиная с которого выполняется соотношение (10.2.4). Действительно, обозначая b0 = 1, перепишем условие (10.2.6) применительно к полиному Qm(x) в виде



Докажем теперь обратное: если полином Qm(x) является l-аннулирующим и ³ m, то он имеет корни x1x2,…, xm. Используя аналогичные преобразования, приведем равенство

b0μk + b1μ 1 +...+ bm μ m = 0

к виду

.

Запишем теперь систему однородных уравнений,

,

(10.2.7)

которая получается из этого равенства, если положить

yj = rj xjk0  mQm(xj), k = k0k0 + 1,…, k0 + m – 1.

В системе (10.2.7) xi будем считать коэффициентами, yj – неизвестными.

Определитель системы является определителем Ван-дер-Монда, он отличен от нуля, так как x1x2,…, xm мы предполагали различными. Но в этом случае система (10.2.7) имеет единственное решение yj = 0, откуда следует Qm(xj) = 0, что и требовалось доказать.

Следствие. Из доказанных теорем следует, что l-аннулирующий полином при условии ³ m является аннулирующим.

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

b0μk + b1μ 1 +...+ bm μ m = 0

(10.2.8)

с неизвестными b0, b1,, bm, причем k = k0k0 + 1,… .

Условием совместности такой системы является линейная зависимость столбцов матрицы



(10.2.9)

В силу сформулированного выше следствия, достаточно проверять линейную зависимость столбцов конечной матрицы, содержащей ³ m строк. Действительно, в этом случае будет линейно зависима и система столбцов матрицы, содержащей < n строк, следовательно, система линейных уравнений (10.2.8), содержащая m уравнений будет совместна и определит коэффициенты полинома Qm(x).Из приведенного выше доказательства тогда следует, что корни Qm(x) совпадают с x1x2,…, xm, т.е. он является искомым делителем. Так как число m заранее не известно, то в качестве ³ m можно взять степень исходного полинома: l = n.

Важно отметить, что поскольку число m нам заранее неизвестно, было бы неправильно при проверке линейной зависимости столбцов матрицы (10.2.9) ограничиваться квадратными матрицами размера 2 ´ 2, 3 ´ 3 и т.д. Так, к примеру, для P4(x= x – 1 последовательность μk имеет вид: μ1 = 0, μ2 = 0, μ3 = 0, μ4 = 4. При этом , но полином Q1(x) = x не является аннулирующим.

В конечном счете, метод поиска делителя сводится к следующему:

  1. Рассчитываем некоторое число членов последовательности μk, k ³ 2n + 1.

  2. Проверяем линейную зависимость n – мерных столбцов матрицы (10.2.9) для m = 2, 3, …, n – 1. Если ни для одного m линейную зависимость обнаружить не удалось, то продолжаем счет последовательности μk, например, расчитываем еще 2n + 1 членов, после чего повторяем проверку матрицы (10.2.9).

  3. Если зависимость столбцов при некотором m ³ 2 обнаружена, составляем и решаем систему (10.2.8) для m + 1 уравнения. Найденный полином Qm(x) является искомым делителем.

Если после заданного числа итераций (повторений пункта 1) линейную зависимость обнаружить не удается, от данного метода следует отказаться, так как это означает, что корни Pn(x) мало отличаются по модулю. В PolyLab в этом случае выдается предупреждение. Число итераций выдается в окне X. При практической реализации необходимо учитывать следующие моменты. Члены последовательности μk время от времени следует нормировать во избежание переполнения или, наоборот, образования машинного нуля. Для проверки линейной зависимости векторов и решения системы линейных уравнений необходимо пользоваться достаточно точными методами. В PolyLab для этой цели применяется очень надежный метод двойной ортогонализации [10]. Система векторов считается линейно зависимой, если для одного из столбцов выполняется неравенство, связывающее нормы этого столбца

    ||pj|| < ||p0j|| * 100d c, (10.2.10)

причем p0jвектор до ортогонализации, pj – он же после ортогонализации. Множитель 100 при относительной погрешности представления чисел отражает типичную вероятную потерю точности в алгоритме ортогонализации при длине вектора и числе векторов порядка нескольких десятков.

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

Потеря точности в линейно–алгебраических операциях тем значительнее, чем больше m. Если в последовательности модулей корней имеется несколько ступенек, то желательно остановиться на первой из них. С этой целью в PolyLab фиксируется первое значение , при котором ||pj|| << ||p0j||, хотя (10.2.10) еще не выполняется. После этого итерации продолжаются до тех пор, пока не выполнится неравенство (10.2.10) для этого, или меньшего значения m.

В PolyLab обращение к методу разложения на множители осуществляется с помощью пункта меню Polynom_Decomposition. Исходный полином должен находиться в окне P, делители выдаются в P и Q. В окне X выдается число итераций, в окне Y – оценка величины остатка от деления P на Q. Если эта оценка оказывается очень грубой, то деление P на Q не проводится, т.е. в окне P остается исходный полином. В этом случае целесообразно попытаться уточнить Q с помощью метода Берстоу. А затем уже разделить P на Q с помощью команды меню. Впрочем, пример с полиномом Clust, о котором мы уже упоминали в примере 9.2.1, показывает, что дело может быть не в погрешности делителя (он выделяется практически точно на первой же итерации), а в погрешности самой операции деле




<< предыдущая страница   следующая страница >>