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

Вычисление многочленов от Ньютона до наших дней Вычисление многочленов — от Ньютона до наших дней Э. Г. Бeлага §1. Многочлены — инструмент вычислителя Ну, начнём! Когда мы доберёмся до конца этой истории, будем знать больше, чем теперь. Г. X. Андерсен В необозримом царстве функций многочлены занимают, на первый взгляд, очень скромное место. Однако это первое впечатление обманчиво. Многочлены, действительно, предельно просты: алгебраическая запись f (x) = xn + a1xn–1 + a2xn–2 + ... + an–1x + an (1) является одновременно и формулой для вычисления значений многочлена 1. Хотя выражения типа cos x, 5√ x , 10x, log 2 x намного лаконичнее, с вычислительной точки зрения они бессодержательны: для вычисления, скажем чисел cos 17°, 5√ 2 , 100,13 или log 2 7 нужны специальные приближённые формулы (или таблицы, составленные с помощью тех же формул). Как правило, в таких формулах появляются многочлены: например, cos x  1 – x2 2! + x4 4! – x6 6! + x8 8! (ошибка в интервале 0≤x≤π/4 меньше одной десятимиллионной!). А ведь тригонометрические, степенные и т. п. (элементарные) функции — это самые простые из функций анализа, изучаемых и используемых математиками, физиками, инженерами. Известный математик-вычислитель Р. В. Хемминг в своей книге «Численные методы» (М., «Наука», 1972) пишет: «Поскольку с многочленами легко обращаться, большая часть классического численного анализа основывается на приближении многочленами». Так как вычислять многочлены приходится часто, то важно научиться делать это как можно проще. Мы расскажем об эволюции методов вычисления значений многочленов с момента зарождения (XVII век). Впрочем, слово «эволюция» здесь не вполне уместно: история этих методов — скорее очень длинный роман с интересной, но краткой завязкой, однообразным действием и неожиданной развязкой. По правде говоря, здесь возникает сомнение, или вернее вопрос, которого миновать нельзя, не поставив его и на него не ответив. А. Данте. Пир (1303 г.) из формулы (1) вынесением за скобки x всюду, где это возможно: f (x) = (...(((x + a1)·x + a2)·x + a3)...)·x + an. (2) Порядок действии при вычислении f (x) определяется скобками в (2): сначала сложение внутри самой внутренней пары скобок (его результат обозначим через p1), затем умножение и сложение внутри следующей пары скобок (результат p2) и т. д.:  p1 = x + a1;  p2 = p1x + a2;  p3 = p2x + a3;   (3) всего n–1 умножений и n сложений 2. отрицательным) имела важные и неожиданные последствия. §3. Индивидуальные схемы — Вы позволите мне записать эту романтическую историю, сэр? — спросил потрясенный мистер Снодграсс. — Сколько угодно, сэр, сколько угодно, ещё пятьдесят таких, если они вам по вкусу. Уже в курсе школьной алгебры мы встречаемся с примерами многочленов, для которых существуют необычайно экономные схемы; единственный их недостаток — они не универсальны. Сравнивая разные схемы по числу операций, мы будем объединять операции сложения и вычитания в группу «(+, –)-операций», а гораздо более трудоёмкие операции умножения и деления — в группу «(×, :)-операций». 3 Примеры. (а) Многочлен f (x) = x2^k можно вычислить за k умножений (а не за 2k по Горнеру): p1 = x·x = x2, p2 = p1·p1 = x4, ..., pk = pk–1·pk–1, f (x) = pk. (б) Многочлен f (x) = x15 можно вычислить за пять (×, :)-операций, так как f (x) = x15 = x16 : x = x2^4 : x. (в) Многочлен f (x) = xn + xn–1 + ... + x + 1 вычисляется по формуле геометрической прогрессии: f (x) = (xn+1 – 1) : (x – 1). (г) Многочлен ( n 1 ) xn–1 + ... + ( n n–1 ) x + 1; есть бином Ньютона: f (x) = (x + 1)n. Упражнения 2. В «Задачнике «Кванта» № 12 за 1973 год была помещена задача (М240): доказать, что многочлен f (x) = xn может быть вычислен не более чем за 3/2 log2 n + 1 (×, :)-операций (n — натуральное число). Пользуясь результатом этой задачи, оцените число операций для вычисления многочленов (в) и (г). Для многочлена (в) — не более 3/2 log2 (n+1) + 2 (×, :)-операции и два вычитания; для многочлена (г) — не более 3/2 log2 n + 1 (×, :)-операция и одно сложение. 3. Постройте экономные схемы для многочленов: (I) f (x) = x8 + x6 – x5 + 2x4 – x3 + x2 – x + 1; (II) ( 2n 2 ) x2n–2 + ( 2n 4 ) x2n–4 + ... + ( 2n 2n–2 ) x2 + 1; (IV) f (x) = 1 – x2 2! + x4 4! – x6 6! + x8 8! . Решение (I) p1 = x·x = x2, p2 = x2·x2 = x4, f (x) = (p2 + p1 + 1)(p2 – x + 1). (II) Заметим, что отсюда f (x) = [xn+1 + xn + ... + x + 1 – (n + 2)] : (x – 1) = = [(xn+2 – 1) : (x – 1) – (n + 2)] : (x – 1). (III) f (x) = (x + 1)2n + (x – 1)2n 2 . (IV) f (x) = ((( 1 8! p1 – 1 6! ) p1 + 1 4! ) p1 – 1 2! ) p1 + 1. §4. Каждому многочлену — свою схему? Тогда я решил тем же способом разделаться и с остальными медведями. А что если для каждого многочлена существует своя схема, гораздо более экономная, чем схема Горнера? Такие схемы можно было бы искать либо исходя из особенностей отдельного многочлена (искусно комбинируя его коэффициенты), либо сконструировав универсальный метод построения схем, намного более экономных, чем схема Горнера, но, возможно, для некоторых многочленов не наилучших. Недостаток первого подхода в том, что для каждого многочлена придется придумывать свои приёмы, и нет никакой гарантии, что нам это всегда удастся; позже (в §10) мы увидим, что второй путь надёжнее во всех отношениях. Само собой разумеется, что оба эти метода уместны лишь в тех случаях, когда конкретный многочлен приходится вычислять так часто, что стоит потратить и время, и усилия, чтобы построить для него хорошую схему. Многочлены же «разового пользования» проще вычислять, скажем, по схеме Горнера. схемы — для многочленов степени 4. Пусть (4)  p1 = x(x + A),  p2 = (p1 + B)(p1 + x + C) + D,  f (x) = p2, (5) где A, B, C и D — параметры. Пример. Многочлен x4 + 3x3 + 6x2 + 3x + 2 можно вычислять по схеме: p1 = x(x + A), f (x) = (p1 – 1)(p1 + x + 5) + 7, содержащей два умножения (вместо трёх по Горнеру) и пять (вместо четырёх) (+, –)-операций; здесь A=1, B=–1, C=5, D=7. Выпишем явное выражение для p2(x): p2(x) = x4 + (2A + 1)·x3 + (A2 + A + B + C)·x2 + приравняв коэффициенты f (x) и p2(x), выразим параметры, входящие в формулу (5), через коэффициенты (4): A = (a – 1)/2; B = c – bA + A2(A + 1); C = b – B – A(A + 1); D = d – BC. (6) Из этих формул ясно, что схема (5) универсальна. а наша задача — научиться быстро считать значения произвольного, но фиксированного многочлена при разных x. — Я думаю, — сказал глубокомысленно Пятачок, — что если бы Иа встал под деревом, а Пух встал к нему на спину, а я встал на плечи Пуха... — И если бы спина Иа-Иа неожиданно треснула, то мы бы все здорово посмеялись, — сказал Иа. (в её «прочности» мы уже убедились), содержащаяся в схеме степени 6, которая содержится в схеме степени 8 и т. д.:  p1 = x(x + b1),  p2 = (p1 + b2)(p1 + x + b3) + b4,    pk = pk–1(p1 + b2k–1) + b2k, f (x) = pk, k≥2. (7. k) схема (7. 2) — это и есть схема (5). Результат схемы (7. k) — многочлен pk(x) степени n = 2k; многочлен же нечётной степени n = 2k + 1 можно представить в таком виде: f (x) = x(x2k + a1x2k–1 + ... + a2k) + a2k+1; (8) степени n = 2k + 1 (с учётом (7. k) и (8) ). Упражнения 4. Найдите формулы предварительной обработки коэффициентов, аналогичные формулам (6), для схемы (7. 3) вычисления многочленов шестой степени. 5. Докажите индукцией по k≥2 универсальность схемы (7. k). Решение Нам нужно по коэффициентам a1, ..., a2k многочлена f (x) найти параметры b1, ..., b2k, превращающие последнюю строку схемы (7. k) в тождество. Параметр b1 — единственный, для которого существует формула, причём простая. Лемма 1. Справедливо соотношение (I) Доказательство проводится индукцией по k≥2. Если k=2, то a1 = kb1 + 1 согласно (6) (роль b1 играет в (6) параметр A). Пусть k≥3, и пусть в схеме (7. k) αx2k–3 + ... ; тогда pk = pk–1(p1 + b2k–1) + b2k = = (x2k–2 + αx2k–3 + ...)(x2 + b1x + b2k–1) + b2k = = x2k + (α + b1)x2k–1 + ... , α = (k – 1)b1 + 1, то a1 = α + b1 = kb1 + 1. Возможность вычисления значении остальных параметров по значениям коэффициентов также доказывается индукцией по k≥2. База индукции. k=2, n=4. Схема (5), формулы (6). Посылка индукции. Пусть при некотором j=k–1≥2 схема (7. k–1) универсальна, то есть любому набору чисел A1, A2, ..., A2k–2 соответствуют значения b1, b2, ..., b2k–2 параметров, подставив которые в схему (7. k–1), мы получим многочлен pk–1(x) = x2k–2 + A1x2k–3 + ... + A2k–2. (II) Шаг индукции. Тогда схема (7. k) также универсальна. Выпишем предпоследнюю строку этой схемы: pk(x) = pk–1(x)·(x2 + b1x + b2k–1) + b2k. (III) нам достаточно найти такой многочлен 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: a1 = A1 + b1, a2 = A2 + b1·A1 + b, a3 = A3 + b1·A2 + b·A1, . . . . . . . . . . a2k–1 = b1·A2k–2 + b·A2k–3, a2k = b1·A2k–2 + b2k. (IV) Условимся обозначать уравнение системы (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)) A2j–1 = (–1) j–1[(k – j)b1 + 1]b j–1 + + S1, j(a1, a2, a3)b j–2 + ... + Sj–1, j(a1, a2, ..., a2j–1), (V) A2j = (–1) jb j + T1, j(a1, a2)b j–1 + ... + Tj, j(a1, a2, ..., a2j). (VI) Посылка индукции — формулы (V), (VI) при 1≤j<k–1. Шаг индукции: (a) A2j+1 = –bA2j–1 – b1A2j + a2j+1 = = (–1) j[(k – j)b1 + 1]b j – S1, j(a1, a2, a3)b j–1 – ... – – b1(–1) jb j – b1T1, j(a1, a2)b j–1 – ... + a2j+1 = = (–1) j[(k – j – 1)b1 + 1]b j + S1, j+1(a1, a2, a3)b j–1 + ... ; (b) Лемма 3. Полученное после всех подстановок уравнение относительно b = b2k–1 имеет степень k–1 и единичный коэффициент при старшем члене (то есть при bk–1). Доказательство. Предположим, что в правой части уравнения (IV)-(2k–1) на левом крайнем месте (там, где сейчас пробел) стоит неизвестное A2k–1, и выразим его через b, a1, ..., a2k–1 по формуле (V) (она по-прежнему применима здесь): A2k–1 = (–1)k [(k – k) + 1]bk–1 + ... = (–1)k bk–1 + .... (VII) Вспомним, что на самом деле 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. О схемах вообще... — Минуточку, минуточку — раздались протестующие голоса. — Избегайте, пожалуйста, научных терминов, объясняйте популярно... Я. Осенка. Загородная прогулка в 2050 году Пришло время спросить, нет ли схем, более экономных, чем схема (7. k)? Но тогда неизбежен и вопрос — что такое схема? Определение. (I). Схема с предварительной обработкой коэффициентов — это последовательность арифметических операций, в которых участвуют переменная x, параметры b1, b2, ..., bm и результаты предшествующих операций. Результат последней операции назовем результатом схемы. (II). Если при некотором наборе значений параметров b1, ..., bm результат схемы есть данный многочлен степени n, то мы скажем, что схема представляет этот многочлен. (III). Если схема представляет многочлен, то процесс вычисления по его коэффициентам соответствующего набора значений параметров назовем предварительной обработкой коэффициентов. (IV). Схема называется универсальной степени n, если она представляет любой многочлен степени n вида (1). Примеры. 1. Схема (7. k) — универсальная (степени n=2k); то же верно и для схемы Горнера (параметры — сами коэффициенты). 2. Схема p(x) = (xn+1 – b1)/(x – b2) представляет многочлен (в) §3 при b1 = b2 = 1. Упражнение 6. Докажите, что общее число SN схем (всех степеней), содержащих не более N операций, конечно и не превосходит числа 6 [(3N – 1)!/(2N – 1)!]2. Решение Так как в каждой операции участвует не более двух параметров, то общее число параметров в схеме с N операциями не больше 2N–1 (хотя бы в одной операции должна участвовать переменная x). В первой операции участвуют два числа. Каждое из них есть либо x, либо один из не более чем 2N–1 параметров; всего не более (2N)2 возможностей. Во второй операции могут участвовать те же числа и результат первой операции; всего не более (2N+1)2 возможностей, и так далее. Наконец, в последней операции могут участвовать не более 3N–1 чисел (в том числе N–1 результат предыдущих операций); всего не более (3N–1)2 возможностей. Общее число различных вариантов не больше произведения этих чисел, то есть SN ≤ (2N)2 (2N + 1)2... (3N – 1)2 = [(3N – 1)!/(2N – 1)!]2. §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. Параметры в операциях Дама сдавала в багаж диван, чемодан, саквояж, картину, картонку и маленькую собачонку. С. Я. Маршак Наше определение схемы не накладывало никаких ограничений на форму её записи. Мы назовём элементарной запись схемы типа «одна строка — одна операция», когда запоминается (и обозначается своим символом) результат каждой операции схемы; примеры: эпиграф (хотя это и не схема, а скорее багажная квитанция), схема для многочлена x2^k (§3) — в ней каждый результат используется больше одного раза и потому нуждается в запоминании. Не для всех схем элементарная форма записи является единственной: если результат какой-то операции используется лишь однажды, то эту операцию можно сразу включить в ту строку, в которой участвует её результат. (Примеры: каждая строка схемы (3), начиная со второй, включает две операции, а схемы (7. k) — не менее трёх.) Интересно, что схема (7. k) не допускает записи меньше, чем в две строки, так как результат первого умножения используется многократно, а схема (3) — допускает (формула (2) ). ×, :)-операций. Перепишем схему в «(×, :)-форме»: «одна строка — одна (×, :)-операция». При этом число (+, –)-операций может заметно возрасти — мы ведь не запоминаем их результаты; но сейчас нас интересует только число (×, :)-операций, а оно остаётся прежним. Первые r строк схемы в «(×, :)-форме» имеют вид × : (Cj ± Dj ± ...), 1 ≤ j ≤ r, (9) где Aj, Bj, ..., Cj, Dj, ... — это либо bi, либо x, либо qs, где s<j. Если (×, :)-операция из qr не была заключительной операцией исходной схемы, то мы объединим в строку qr+1 = A ± B ± ... (10) все те (+, –)-операции, которые ещё остаётся выполнить. Обозначим теперь через d'j и d"j алгебраические суммы всех параметров bi в левой и правой скобках (9), а через dr+1 — в (10) (даже если их кое-где в (9) и (10) нет вовсе). Перепишем теперь (9) и (10), пользуясь новыми параметрами d'j, d"j (1≤j≤r), dr+1. Полученная схема будет универсальной, и предварительная обработка коэффициентов состоит в вычислении параметров bi для исходной схемы (9), (10), а затем уже параметров d'j, d"j. Новая схема представляет все многочлены, что и исходная, и содержит по два параметра d', d" на каждую (×, :)-операцию плюс, возможно, ещё один параметр dr+1. Доказательство для (+, –)-операций аналогично; соответствующие построения выполните самостоятельно. §9. Параметры универсальной схемы Я нарочно заостряю, упрощаю и карикатурю мысль. В. В. Маяковский. Как писать стихи «Причина» справедливости неравенства m≥n для универсальных схем очень проста: если схема степени n универсальна, то есть представляет все многочлены степени n, то каждому такому многочлену должен соответствовать свой набор параметров; поэтому «число» различных наборов параметров должно быть не меньше «числа» разных многочленов. Однако, пожелай мы придать этому объяснению точный смысл, нам не хватило бы этого номера «Кванта». Удовлетворимся же тем, что разберём иллюстративный пример. Пусть n=2, f (x) = x2 + a1x + a2. Каждый конкретный многочлен можно изобразить точкой на плоскости с координатами a1, a2. Если для схемы m<n=2, то она либо совсем не содержит параметров (m=0), либо содержит один параметр (m=1). В первом случае схема представляет единственный многочлен (точка на плоскости), во втором — семейство многочленов, которое изобразится на «плоскости многочленов» в виде некоторой «хорошей» кривой. Скажем, схема p = (x + b)(x – b) + bx = x2 + bx – b2 представляет все многочлены, изображаемые точками параболы (a1 = b, a2 = –b2) или a2 = –a12. Вся тонкость в том, что коэффициенты выражаются через параметры (согласно схеме) арифметическими средствами — поэтому-то наша кривая многочленов, представимых схемой, и будет «нормальной» кривой, содержащей лишь «ничтожную часть» точек плоскости. Возможно, читателям известно, что существуют кривые, которые заполняют всю плоскость (см. книгу Г. Штейнгауза «Математический калейдоскоп», с. 78), так что соответствующие схемы (существование их в принципе невозможно!) представляли бы все многочлены степени 2 и были бы универсальными. Девочке четырех с половиной лет прочли «Сказку о рыбаке и рыбке». — Вот глупый старик, — возмутилась она, — просил у рыбки то новый дом, то новое корыто. Попросил бы сразу новую старуху. К. Чуковский. От двух до пяти для него получить, используя (7. k)–(8) или какую-нибудь другую универсальную схему. Правда, девочка из эпиграфа, убеждённая в силе универсальных методов, предостерегает нас от увлечения поисками всё новых и новых сверхэкономных индивидуальных схем для отдельных многочленов (вроде схем §3); сейчас мы покажем бесполезность таких поисков. Отметим, прежде всего, что индивидуальную схему степени n разумно считать «сверхэкономной», если она содержит «ненормально мало» (по сравнению с универсальными схемами) либо (×, :)-операций, либо (+, –)-операций и если общее число её операций не больше, скажем, 100n (для сравнения: общее число операций схемы Горнера равно 2n–1). Пример. Схема многочлена (в) из §3 после замены чисел 1, 1 буквами b1, b2 превращается в схему p(x) = (xn+1 – b1) : (x – b2), представляющую все многочлены вида f (x) = xn + axn–1 + a2xn–2 + ... + an–1x + an степени n. Итак, многочлены, которые могут быть вычислены быстрее, чем за ½(n–1) (×, :)-операций или n–1 (+, –)-операций, — исключение из общего правила. Тем не менее, при построении схемы для конкретного многочлена стóит использовать его особенности, если они бросаются в глаза.