Вычисление многочлена (ч1)

retweet
23.10.2011 12:00


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

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

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

Для начала рассмотрим формулировку и тривиальный способ решения. Пусть нам дан многочлен от одной переменной:

f(x) = \sum_{i=0}^{n}a_ix^i

В нем ровно n + 1 слагаемое и он однозначно задается вектором своих коэффициентов. Известный со школы метод вычисления значения этой функции называется схемой Горнера и заключается в том, что мы представляем исходный многочлен в виде:

f(x) = a_0 + x(a_1 + x(a_2 + \dots + x(a_{n-1} + xa_n)\dots)).

С точки зрения алгебраической сложности, можно трактовать это как программу, не содержащую инструкций ветвления (Straight Line Program, SLP), вычисляющую полином f за n умножений и n сложений. Формально:

\begin{array}{ll} u_0 & = a_n \\ u_1 & = x * u_0 \\ u_2 & = a_{n - 1} + u_1 \\ u_3 & = x * u_2 \\ u_4 & = a_{n - 2} + u_3 \\ \dots & \\ u_{2n-1} & = x * u_{2n-2} \\ u_{2n} & = a_0 + u_{2n-1} \end{array}

Оказывается, что, если в такой программе разрешить умножать на любые вещественные числа (а не только коэффициенты исходного многочлена), существуют гораздо более оптимальные варианты. Доказано, что нельзя сделать это быстрее чем за n/2 + 2 умножения (n/2 + 1 при n > 9), см. [1], результат Motzkin(1955), Belaga(1958), Winograd(1970), а так же, что задача требует n сложений.

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

Представим исходный полином в виде:
\begin{equation} f(x) = g(x^2) + xh(x^2) \quad\quad \end{equation}

Таким образом, g(x) многочлен на коэффициентах при четных степенях, а h(x) на нечетных:

\renewcommand{\ndivtwo}{\left\lfloor\frac{n}{2}\right\rfloor} \renewcommand{\nsubdivtwo}{\left\lfloor\frac{n - 1}{2}\right\rfloor} \begin{array}{ll} g(x) = & a_0 + a_2x + \dots + a_{\ndivtwo} * x^{\ndivtwo} \\ h(x) = & a_1 + a_3x + \dots + a_{\nsubdivtwo} * x^{\nsubdivtwo} \end{array}

Предположим, что многочлен h(x) имеет ровно deg(h) корней. Справедливо замечание, что для вещественных чисел это не всегда так, но эту проблему мы устраним позже. Возьмем первый корень t1 многочлена h и поделим g(x) на (x - t1):
\begin{array}{l} h(x) = (x - t_1)h_1(x) \\ g(x) = (x - t_1)g_1(x) + r_1 \\ f(x) = r_1 + (x^2 - t_1)(g_1(x^2) + xh_1(x^2)) = r_1 + (x^2 - t_1)f_1(x) \end{array}

Как видно, мы получили многочлен f1, который раскладывается аналогично (1) на сумму g1 и x*h1 в точке x^2. При этом корни h1 - это все оставшиеся корни h. Тогда продолжим процесс аналогично, до тех пор, пока многочлен hk не выродится в константу (и не будет иметь корней):
f(x) = r_1 + (x^2 - t_1)(r_2 + (x^2 - t_2)(r_3 + \dots + (x^2 - t_k)(xh_k + g_k(x^2))\dots))

Прослеживается аналогия со схемой Горнера. Осталось заметить, что левую часть можно вычислить за 2k сложений и k умножений, gk(x^2) вычисляется все той же схемой Горнера за n / 2 - k умножений и столько же сложений (деля g на (x^2 - ti), мы уменьшали степень хотя бы на один k раз), еще одно умножение от x * hk. И надо не забыть про вычисление x * x.
Итого не более (n / 2 + 2) умножения и n сложений. На стадии препроцессинга необходимо найти:

1. корни h(x) - (t1, t2, ..., tk)
2. остатки от деления g(x) - (r1, r2, ..., rk)
3. коэффициенты того, что осталось от g, т.е. gk

Если рассматривать поле комплексных чисел (или любое алгебраически замкнутое поле), то задача решена. Давайте разберемся с вещественным случаем, в котором многочлен h(x) может категорически не захотеть разлагаться. Тут все будет несколько сложнее, чем программа девятого класса.

Докажем вспомогательное утверждение: Если
1. коэффициенты p(x) и q(x) - вещественные.
2. все корни f(x) = p(x) + i * q(x) t1, t2, ..., tn такие, что их мнимая часть строго положительна.
То все корни p(x) и q(x) - вещественные.

Доказательство:
x - корень либо p(x), либо q(x). Тогда:
http://desmond.imageshack.us/Himg207/scaled.php?server=207&filename=img07.png&res=medium

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

Вернемся к исходной функции f. Рассмотрим ее смещение вдоль вещественной оси f1(x) = f(x + c). Понятно, что существует такое вещественное c, что все корни f1 будут в правой комплексной полуплоскости. Возьмем и будем вычислять f1 вместо f, для этого нам надо показать, что в разложении:
f_1(x) = g_1(x^2) + xh_1(x),
все корни h1(x) - вещественные.
Все корни f2(x) = f1(-ix) будут в верхней полуплоскости. (умножение комплексного на i - поворот на 90 град.).
Тогда f2(x) = f1(-i*x) = g1(-x^2) - i*x*h1(-x^2) и -x*h1(-x^2) имеет вещественные корни, тогда и h1(x) имеет вещественные корни.

Таким образом, у нас будет одно дополнительное сложение, чтобы вычислять x1 = x - c, по сравнению с предыдущим случаем.

А на стадии препроцессинга все совсем стало грустно:
1. необходимо вычислить комплексные корни f
2. по ним найти c (как минимум вещ. частей)
3. после этого пересчитать его коэффициенты в коэффициенты f1.
4. для f1 выполнить препроцессинг для предыдущего случая.

Вторую часть материала "Вычисление многочлена" можно прочитать тут.