Численные методы. Корнюшин П.Н. - 30 стр.

                                                                30


                        2.2.8. Вычисление значений алгебраического полинома

       Пусть задан алгебраический полином n-й степени с действительными коэффициентами
                         Pn ( x) = a 0 x n + a1 x n −1 + ... + a n −1 x + a n. (13)
       Требуется определить значение этого полинома в точке x0. Подсчитаем число операций,
необходимых для решения этой задачи. Операций умножения: n+(n-1)+(n-2)+…+1=n(n+1)/2;
операций сложения: n. Нельзя ли предложить метод, сокращающий число операций?
Рациональный процесс подсчета значения многочлена основан на теореме Безу.
       Теорема. Остаток от деления многочлена Pn (x) на двучлен (x-x0) равен значению
многочлена в точке x0.
       Доказательство
       Запишем результат деления Pn (x) на ( x − x 0 ) в виде суммы остатка от деления R и
многочлена (n-1)-й степени Q n−1 ( x), т.е.
                                     Pn ( x) = ( x − x 0 )Q n −1 ( x) + R. .              (14)
        Положим в этом выражении x=x0:
                                       Pn ( x 0 ) = ( x 0 − x 0 )Q n −1 ( x 0 ) + R = R. .
        Вычислим Q n−1 ( x) :
                              Q n −1 ( x) = b0 x n =1 + b1 x n − 2 + ... + bn − 2 x + bn −1 .    (15)
        Подставив этот результат в (14), получим
                          Pn ( x) = ( x − x 0 )(b0 x n −1 + b1 x n − 2 + ... + bn − 2 x + bn −1 ) + R. .
       Выразим коэффициенты многочлена Qn-1 через коэффициенты Pn.
       Теорема. Два многочлена тождественно равны тогда и только тогда, когда их
коэффициенты при одинаковых степенях x совпадают.
       Имеем:
      a 0 = b0 , a1 = b1 − b0 x 0 , a 2 = b2 − b1 x 0 ,..., a k = bk − bk −1 x 0 ,..., a n = bn − bn −1 x 0 , откуда
            b0 = a 0 , b1 = a1 + b0 x 0 , b2 = a 2 + b1 x 0 ,..., bk = a k + bk −1 x 0 ,..., bn = a n + bn −1 x 0 .
       Преобразование коэффициентов удобно представить в виде так называемой схемы Горнера
(таблица 1).

        Таблица 1
                         a0           a1             a2              …              ak            …              an
                                     b0x0           b1x0             …            bk-1 x0         …             bn-1x0
              x0         b0           b1             b2              …              bk            …              bn

      В соответствии с теоремой Безу bn = R = Pn ( x 0 ). При этом выполнено n действий
умножения и n действий сложения.
      Пример. P ( x) = 3 x 5 − 4 x 4 + 2 x 2 − x + 10, P(2) − ?

        Таблица 2
                                3              -4              0              2             -1             10
                                               6               4              8             20             38
                    2           3              2               4             10             19             48