Квадратные корни

Возможность вычисления значении остальных параметров по значениям  коэффициентов также доказывается индукцией по k≥2.

База индукции. k=2, n=4. Схема (5), формулы (6).

Посылка индукции. Пусть при некотором j=k–1≥2 схема (7.k–1) универсальна, то есть любому набору чисел A₁, A₂, ..., A_2k–2 соответствуют значения b₁, b₂, ..., b_2k–2 параметров, подставив которые в схему (7.k–1), мы получим многочлен

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

Согласно нашему предположению (посылка индукции), для  нахождения значений параметров b₁, b₂, ..., b_2k, превращающих многочлен p_k(x) из (7.k) в многочлен f(x) с данными коэффициентами a₁, a₂, ..., a_2k нам достаточно найти такой многочлен p_k–1(x) (точнее, его коэффициенты A₁, A₂, ..., A_2k–2 — см. (II)) и такие значения параметров b_2k–1, b_2k, чтобы после их подстановки в (III) выполнялось тождество p_k(x) = f(x). Перемножив многочлены в правой части равенства (III) и приравняв коэффициенты полученного многочлена и многочлена f(x) = x^k + a₁x^k–1 + ... + a_2k, мы сможем выписать систему 2k уравнений с неизвестными A₁, A₂, ..., A_2k–2, b_2k–1, b_2k, (a₁, ..., a_2k заданы, b₁ находится из равенства (I)); чтобы сократить запись формул, заменим параметр b_2k–1 символом b:

Условимся обозначать уравнение системы (IV) с номером j (1≤j≤2k) через (IV)-j. Тогда процесс  решения системы (IV) можно описать  в нескольких словах: A₁ выражается через a₁ из (IV)-1 и (I), A₂ выражается через a₁, a₂ и b из (IV)-2, A₃ выражается через a₁, a₂, a₃ и b из (IV)-3 и т.д. Последним из уравнения (IV)-(2k–2) мы выразим неизвестное A_2k–2; затем, подставив в уравнение (IV)-(2k–1) найденные выражения для A_2k–2 и A_2k–3, мы получим уравнение относительно b.

Лемма 2. Неизвестные A_2j–1 и A_2j выражаются из системы (IV) через параметр b и коэффициенты a₁, a₂, ..., a_2k–2; согласно формулам (b₁ выражается через a₁ согласно (I))

Доказательство. База индукции: j=1, A₁ = a₁ – b₁ = [(k – 1)b₁ + 1]b,  A₂ = –b + T_1,1(a₁, a₂).

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

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

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

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

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

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

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

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

Итак, нам удалось  уменьшить число умножений по сравнению со схемой Горнера вдвое. Какой ценой? Из решения упражнения 5 видно, что процесс вычисления параметров b₁, b₂, ..., b_2n по коэффициентам a₁, a₂, ..., a_2n очень сложен, — он включает в себя решение серии уравнений с одним неизвестным степени k–1, k–2, ... Это означает, в частности, что при k≥6 (n≥12) формул вычисления параметров нет⁴ , хотя, разумеется, их значения могут быть найдены приближёнными методами с любой степенью точности.

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

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

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

— Верно! — подтвердили  остальные. — Говорите понятнее... Что  такое лес?

Я. Осенка. Загородная прогулка в 2050 году

Пришло время  спросить, нет ли схем, более экономных, чем схема (7.k)? Но тогда неизбежен  и вопрос — что такое схема?

Определение. (I). Схема с предварительной обработкой коэффициентов — это последовательность арифметических операций, в которых участвуют переменная x, параметры b₁, b₂, ..., b_m и результаты предшествующих операций. Результат последней операции назовем результатом схемы. (II). Если при некотором наборе значений параметров b₁, ..., b_m результат схемы есть данный многочлен степени n, то мы скажем, что схема представляет этот многочлен. (III). Если схема представляет многочлен, то процесс вычисления по его коэффициентам соответствующего набора значений параметров назовем предварительной обработкой коэффициентов. (IV). Схема называется универсальной степени n, если она представляет любой многочлен степени n вида (1).

Примеры. 1. Схема (7.k) — универсальная (степени n=2k); то же верно и для схемы Горнера (параметры — сами коэффициенты).

2. Схема p(x) = (xⁿ⁺¹ – b₁)/(x – b₂) представляет многочлен (в) §3 при b₁ = b₂ = 1.

Упражнение6. Докажите, что общее число S_N схем (всех степеней), содержащих не более N операций, конечно и не превосходит числа⁶   [(3N – 1)!/(2N – 1)!]².

Решение

Так как в  каждой операции участвует не более  двух параметров, то общее число  параметров в схеме с N операциями не больше 2N–1 (хотя бы в одной операции должна участвовать переменная x). В  первой операции участвуют два числа. Каждое из них есть либо x, либо один из не более чем 2N–1 параметров; всего не более (2N)² возможностей. Во второй операции могут участвовать те же числа и результат первой операции; всего не более (2N+1)² возможностей, и так далее. Наконец, в последней операции могут участвовать не более 3N–1 чисел (в том числе N–1 результат предыдущих операций); всего не более (3N–1)² возможностей. Общее число различных вариантов не больше произведения этих чисел, то есть

S_N ≤ (2N)² (2N + 1)² ... (3N – 1)² = [(3N – 1)!/(2N – 1)!]².

§7. ... И о наилучшей  из них, в частности

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

Платон

Теперь наш  вопрос о наилучших схемах степени n приобрёл точный смысл, и можно  дать на него точный ответ: схема из §5 почти наилучшая — любая универсальная схема степени n содержит не менее ½(n–1) (×,:)-операций и не менее n–1 (+,–)-операций.

Справедливость  этого утверждения можно вывести  из двух важных свойств схем:

число m параметров универсальной схемы степени n не меньше числа коэффициентов, то есть m≥n;

в промежутке между  двумя (×,:)-операциями любой (не обязательно  универсальной) схемы может появиться  не более двух по-настоящему новых  параметров (все остальные будут  «лишними»), а между двумя (+,–)-операциями — не более одного.

Второе свойство стоит сформулировать более строго: если схема содержит r (×,:)-операций (или s (+,–)-операций), то число m параметров либо сразу не больше 2r+1 (соответственно s+1), либо без ущерба для свойств  схемы может быть уменьшено до 2r+1 (соответственно, s+1), то есть m ≤ 2r + 1 и m ≤ s + 1.

Итак, n ≤ m ≤ 2r + 1 и n ≤ m ≤ s + 1, отсюда ½(n – 1) ≤ r и n – 1 ≤ s.

— Но вы совсем забыли о схеме Горнера! — прервёт  нас читатель, которому больше по душе классическая ясность схем без предварительной возни с коэффициентами. — Ведь она не зря кажется предельно экономной!

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

А теперь займёмся двумя сформулированными выше свойствами схем, сначала вторым.

§8. Параметры в операциях

Дама сдавала  в багаж

диван, чемодан, саквояж,

картину, корзину, картонку

и маленькую собачонку.

С. Я. Маршак

Наше определение  схемы не накладывало никаких  ограничений на форму её записи. Мы назовём элементарной запись схемы  типа «одна строка — одна операция», когда запоминается (и обозначается своим символом) результат каждой операции схемы; примеры: эпиграф (хотя это и не схема, а скорее багажная квитанция), схема для многочлена x^{2^k} (§3) — в ней каждый результат используется больше одного раза и потому нуждается в запоминании.

Не для всех схем элементарная форма записи является единственной: если результат какой-то операции используется лишь однажды, то эту операцию можно сразу включить в ту строку, в которой участвует её результат. (Примеры: каждая строка схемы (3), начиная со второй, включает две операции, а схемы (7.k) — не менее трёх.) Интересно, что схема (7.k) не допускает записи меньше, чем в две строки, так как результат первого умножения используется многократно, а схема (3) — допускает (формула (2) ).

Переходя к  доказательству свойства 2), рассмотрим элементарную форму записи схемы и обозначим через q₁, ..., q_r результаты (×,:)-операций. Перепишем схему в «(×,:)-форме»: «одна строка — одна (×,:)-операция». При этом число (+,–)-операций может заметно возрасти — мы ведь не запоминаем их результаты; но сейчас нас интересует только число (×,:)-операций, а оно остаётся прежним. Первые r строк схемы в «(×,:)-форме» имеют вид

где A_j, B_j, ..., C_j, D_j, ... — это либо b_i, либо x, либо q_s, где s<j. Если (×,:)-операция из q_r не была заключительной операцией исходной схемы, то мы объединим в строку