Система горнера онлайн

Система горнера онлайн

Задан многочлен

P(x)=a0+a1x+a2x2+a3x3++anxn,aiR.{\displaystyle P(x)=a_{0}+a_{1}x+a_{2}x^{2}+a_{3}x^{3}+\ldots +a_{n}x^{n},\quad a_{i}\in \mathbb {R} .}

 

Пусть требуется вычислить значение данного многочлена при фиксированном значении

x=x0{\displaystyle x=x_{0}}

 . Представим многочлен

P(x){\displaystyle P(x)}

  в следующем виде:

P(x)=a0+x(a1+x(a2+x(an1+anx))).{\displaystyle P(x)=a_{0}+x(a_{1}+x(a_{2}+\cdots x(a_{n-1}+a_{n}x)\dots )).}

 

Определим следующую последовательность:

bn=an,{\displaystyle b_{n}=a_{n},}

 

bn1=an1+bnx0,{\displaystyle b_{n-1}=a_{n-1}+b_{n}x_{0},}

 

bi=ai+bi+1x0,{\displaystyle b_{i}=a_{i}+b_{i+1}x_{0},}

 

b0=a0+b1x0.{\displaystyle b_{0}=a_{0}+b_{1}x_{0}.}

 

Искомое значение

P(x0){\displaystyle P(x_{0})}

  есть

b0{\displaystyle b_{0}}

 . Покажем, что это так.

В полученную форму записи

P(x){\displaystyle P(x)}

  подставим

x=x0{\displaystyle x=x_{0}}

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

bi{\displaystyle b_{i}}

 :

P(x0)=a0+x0(a1+x0(a2+x0(an1+anx0)))==a0+x0(a1+x0(a2+x0bn1))=  =a0+x0b1==b0.{\displaystyle {\begin{aligned}P(x_{0})&=a_{0}+x_{0}(a_{1}+x_{0}(a_{2}+\cdots x_{0}(a_{n-1}+a_{n}x_{0})\dots ))=\\&=a_{0}+x_{0}(a_{1}+x_{0}(a_{2}+\cdots x_{0}b_{n-1}\dots ))=\\&~~\vdots \\&=a_{0}+x_{0}b_{1}=\\&=b_{0}.\end{aligned}}}

 

Рассчитать

f(x)=2x36x2+2x1{\displaystyle f(x)=2x^{3}-6x^{2}+2x-1}

  для

x=3.{\displaystyle x=3.}

  Используем синтетическое деление:

 x₀│   x³    x²    x¹    x⁰  3 │   2    −6     2    −1    │         6     0     6    └────────────────────────        2     0     2     5 

Здесь в первой строке записано значение x0 и коэффициенты многочлена.

Значения (по столбцам) в третьей строке соответствуют сумме значений первой и второй строки (

bn1=an1+bnx0{\displaystyle b_{n-1}=a_{n-1}+b_{n}x_{0}}

 ), а значения второй строки произведению x на значение в третьей строке предыдущего столбца (

bnx0{\displaystyle b_{n}x_{0}}

 ).

Например, если

a3=2,a2=6,a1=2,a0=1{\displaystyle a_{3}=2,a_{2}=-6,a_{1}=2,a_{0}=-1}

  мы видим, что

b3=2,b2=0,b1=2,b0=5{\displaystyle b_{3}=2,b_{2}=0,b_{1}=2,b_{0}=5}

  — значения в третьей строке. Так синтетическое деление базируется на методе Горнера.

Разделим

x36x2+11x6{\displaystyle x^{3}-6x^{2}+11x-6}

  на

x2{\displaystyle x-2}

 :

 2 │   1    −6    11    −6    │         2    −8     6    └────────────────────────        1    −4     3     0 

Новый многочлен

x24x+3{\displaystyle x^{2}-4x+3}

 .

Пусть

f1(x)=4x46x3+3x5{\displaystyle f_{1}(x)=4x^{4}-6x^{3}+3x-5}

  и

f2(x)=2x1{\displaystyle f_{2}(x)=2x-1}

 . Разделим

f1(x){\displaystyle f_{1}(x)}

  на

f2(x){\displaystyle f_{2}\,(x)}

 , используя метод Горнера.

  2 │  4    −6    0    3   │   −5 ────┼──────────────────────┼───────   1 │        2   −2   −1   │    1     └──────────────────────┼───────        2    −2   −1    1   │   −4 

Tретья строка — сумма первых двух, деленная на два. Каждое значение второй строки совпадает с значением третьей строки в предыдущем столбце. Ответ на деление:

f1(x)f2(x)=2x32x2x+142x1.{\displaystyle {\frac {f_{1}(x)}{f_{2}(x)}}=2x^{3}-2x^{2}-x+1-{\frac {4}{2x-1}}.}

 

Также с помощью схемы Горнера можно вычислять значение числа в позиционной системе исчисления.



Источник: www.www-wikipediya.ru


Добавить комментарий