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

  • Просмотров 2664
  • Скачиваний 29
  • Размер файла 30
    Кб

заменим параметр 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, ... Это