Статья: Вычисление многочленов от Ньютона до наших дней

Шаг индукции. Тогда схема (7.k) также универсальна. Выпишем предпоследнюю строку этой схемы:

Согласно нашему предположению (посылка индукции), для нахождения значений параметров b1, b2, ..., b2k, превращающих многочлен pk(x) из (7.k) в многочлен f (x) с данными коэффициентами a1, a2, ..., a2k нам достаточно найти такой многочлен pk–1(x) (точнее, его коэффициенты A1, A2, ..., A2k–2 — см. (II)) и такие значения параметров b2k–1, b2k, чтобы после их подстановки в (III) выполнялось тождество pk(x) = f (x). Перемножив многочлены в правой части равенства (III) и приравняв коэффициенты полученного многочлена и многочлена f (x) = xk + a1xk–1 + ... + a2k, мы сможем выписать систему 2k уравнений с неизвестными A1, A2, ..., A2k–2, b2k–1, b2k, (a1, ..., a2k заданы, b1 находится из равенства (I)); чтобы сократить запись формул, заменим параметр b2k–1 символом b:

Условимся обозначать уравнение системы (IV) с номером j (1≤j≤2k) через (IV)-j. Тогда процесс решения системы (IV) можно описать в нескольких словах: A1 выражается через a1 из (IV)-1 и (I), A2 выражается через a1, a2 и b из (IV)-2, A3 выражается через a1, a2, a3 и b из (IV)-3 и т.д. Последним из уравнения (IV)-(2k–2) мы выразим неизвестное A2k–2; затем, подставив в уравнение (IV)-(2k–1) найденные выражения для A2k–2 и A2k–3, мы получим уравнение относительно b.

Лемма 2. Неизвестные A2j–1 и A2j выражаются из системы (IV) через параметр b и коэффициенты a1, a2, ..., a2k–2; согласно формулам (b1 выражается через a1 согласно (I))

Доказательство. База индукции: j=1, A1 = a1 – b1 = [(k – 1)b1 + 1]b, A2 = –b + T1,1(a1, a2).

Посылка индукции — формулы (V), (VI) при 1≤j<k–1.

Шаг индукции:

Лемма 3. Полученное после всех подстановок уравнение относительно b = b2k–1 имеет степень k–1 и единичный коэффициент при старшем члене (то есть при bk–1).

Доказательство. Предположим, что в правой части уравнения (IV)-(2k–1) на левом крайнем месте (там, где сейчас пробел) стоит неизвестное A2k–1, и выразим его через b, a1, ..., a2k–1 по формуле (V) (она по-прежнему применима здесь):

Вспомним, что на самом деле A2k–1 ≡ 0; умножив правую и левую части (VII) на (–1)k, получим требуемое уравнение относительно b.

Решив это уравнение *), мы найдём значение параметра b = b2k–1, а затем по формулам (V), (VI) вычислим неизвестные A2, A3, ..., A2k–2; параметр b2k находится из уравнения [IV]-(2k).

*) Так называемая «основная теорема алгебры», открытая великим К. Ф. Гауссом, утверждает, что многочлен степени n>0 всегда имеет хотя бы один корень. Несмотря на то, что при n≥5 формул для нахождения этого корня и не существует, разработаны методы нахождения всех корней многочлена с любой точностью.

Начиная с третьей строки, схема (7.k) очень напоминает схему Горнера (3); разница лишь в том, что теперь после каждого умножения степень увеличивается не на единицу, а на два.

Итак, нам удалось уменьшить число умножений по сравнению со схемой Горнера вдвое. Какой ценой? Из решения упражнения 5 видно, что процесс вычисления параметров b1, b2, ..., b2n по коэффициентам a1, a2, ..., a2n очень сложен, — он включает в себя решение серии уравнений с одним неизвестным степени k–1, k–2, ... Это означает, в частности, что при k≥6 (n≥12) формул вычисления параметров нет 4, хотя, разумеется, их значения могут быть найдены приближёнными методами с любой степенью точности.

Здесь возникает ещё одно затруднение, оказавшееся, правда, преодолимым. До сих пор мы не уточняли, значения каких — действительных или комплексных — многочленов мы вычисляем. Схема Горнера применима и в том, и в другом случае, схема же (7.k) преимущественно «комплексная» — действительным коэффициентам могут соответствовать комплексные параметры. Появление комплексных чисел при вычислении действительных многочленов намного увеличивает число арифметических операций 5. К счастью, в 1960 году схему (7.k) небольшим усложнением удалось превратить в действительную; однако полные доказательства в этом случае уже очень непросты.

§6. О схемах вообще...