Статья: Вычисление многочленов от Ньютона до наших дней
Шаг индукции. Тогда схема (7.k) также универсальна. Выпишем предпоследнюю строку этой схемы:
| pk(x) = pk–1(x)·(x2 + b1x + b2k–1) + b2k. | (III) |
Согласно нашему предположению (посылка индукции), для нахождения значений параметров 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:
|
a1 = A1 + b1, a2 = A2 + b1·A1 + b, a3 = A3 + b1·A2 + b·A1, . . . . . . . . . . a2k–2 = A2k–2 + b1·A2k–3 + b·A2k–4, 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) |
Доказательство. База индукции: j=1, A1 = a1 – b1 = [(k – 1)b1 + 1]b, A2 = –b + T1,1(a1, a2).
Посылка индукции — формулы (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) | A2j+2 = –bA2j – b1A2j+1 + a2j+2 = (–1) j+1b j+1 + T1, j+1(a1, a2)b j + ... |
Лемма 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. О схемах вообще...
|
К-во Просмотров: 819
Бесплатно скачать Статья: Вычисление многочленов от Ньютона до наших дней
|