Направо към съдържанието

Формула на Хорнер

от Уикипедия, свободната енциклопедия

Формула на Хорнер, още известна като Метод на Хорнер или Схема на Хорнер е алгоритъм за изчисляване на многочлени (полиноми), който се състои от трансформирането на полинома с цел разлагането му на множители. Този метод е кръстен на британския математик Уилям Джордж Хорнър, въпреки че е бил известен преди него на Паоло Руфини, както и шестстотин години по-рано, на китайския математик Чин Жиушао.

Методът на Хорнер се описва чрез приложенията му: изчисляване на многочлени и разлагането им с бином.

Изчисляване на многочлен

[редактиране | редактиране на кода]

Имайки полинома

където са реални числа, трябва да се изчисли полинома за специална стойност на , нека тя да е .

За целта се полага

Тогава е стойността на .

Това се получава, като се запише полинома във вида

След това, замествайки с се получава

Да се пресметне за

Използва се методът на синтезирано деление, базиран на схемата на Хорнер, както следва:

  │ x³  x²  x¹  x⁰          │ x³  x²  x¹  x⁰
x₀│ a0  a1  a2  a3          3│ 2  −6   2  −1
  │ k0  k1  k2  k3           │     6   0   6  
  └───────────────          └───────────────
    b0  b1  b2  b3             2   0   2   5

На първия ред са означени степените на аргумента . Числата от втория ред са стойността на , означена с , и коефициентите на полинома: . Третият и четвърият ред се попълват паралелно, започвайки отляво с празна позиция () на третия ред. Числата от четвърия ред са сумите съответните числа във втория и третия ред . Всяко следващо число от третия ред е произведение от числото вляво от него от четвърия ред по стойността на (в случая 3): за . Така последователно се получава: , ;
, ;
, .
. Остатъкът на при деление на е 5.

По теорема остатъкът е равен на . Следователно .

Разлагане на многочлен с бином

[редактиране | редактиране на кода]

Зададеният бином може да участва в разложението като множител или знаменател на остатък.

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

При тези коефициенти резултатите от полиномите отговарят на следните отношения:

, .
По същия начин, може да се определи кратността на корените (използва се схема на Хорнер за нов полином). Може също да се използва схемата за намиране на коефициентите чрез разлагането на полинома с :

1. Да се разложи многочленът на :

x₀│ x³  x²  x¹  x⁰
2 │ 1  -6  11  -6
  │ 2  -8   6
  └────────────────
    1  -4   3   0

Получава се квадратният тричлен . Многочленът се разлага на множители във вида .

2. Нека и . Разлага се на чрез метода на Хорнер.

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

Третият ред е сумата от другите два реда, разделена на 2. Всяко число от втория ред е произведението на 1 с числото от ляво на третия ред. Отговорът е: