x +2x -3x x - x + 2

-x +0x + 7x

-x - 2x + 3x

2x + 4x - 6

2x + 4x - 6

0

Отже, x + x - 3x + 7x - 6 =(x + 2x - 3)(x - x + 2).Таким чином ми розклали многочлен на множники.У цьому випадку многочлен поділився націло, тобто без остачі.Тепер розглянемо випадок, коли многочлен націло не ділиться:

x - 5x + x + 8x - 20 x - 2x + 3

x - 2x +3x x - 3x - 8

-3x - 2x + 8x

-3x +6x - 9x

-8x +17x - 20

-8x +16x - 24

x + 4

Отже, x - 5x + x + 8x - 20 =(x - 2x + 3)(x - 3x - 8) + x + 4.Так розкладають многочлен, який при діленні дає остачу (тобто вкінці додаєм остачу від ділення).

-5-

Метод невизначених коефіцієнтів.

Нехай дано многочлени

Pn(X)=p0x + p1x + ... + pn-1x + pn і

Qm(X)=q0x + q1x + ... + qm-1x + qm ... , m <= n.Тоді

Kn-m(X)=p0/q0x + c1x + ... + cn-m і остача

R m-1(X)=d0x + d1x + ... + dm-1, (2)

c1, c2, ... , cn-m і d0, d1, ... ,dm-1 - невідомі коефіцієнти.

Запишемо тотожну рівність:

Pn(X)=Qm(X)*Kn-m(X) + R m-1(X). (3)

Перемноживши многочлени Qm(X) і Kn-m(X) і звівши подібні члени в правій частині рівності (3), дістанемо многочлен n-го степеня, який запишемо в канонічному вигляді. Прирівнюючи коефіцієнти при однакових степенях x цього многочлена і многочлена Pn(X), дістанемо систему n рівнянь відносно n невідомих c1, c2, ... , cn-m і d0, d1, ... ,dm-1.

Може виявитися, що всі числа d0, d1, ... ,dm-1 дорівнюють нулю. Це означає, що многочлен Pn(X) ділиться націло на многочлен Qm(X). Якщо хоча б один з коефіцієнтів d0, d1, ... ,dm-1 відмінний від нуля , то многочлен Pn(X) ділиться на многочлен Qm(X) з остачею. При цьому степінь остачі дорівнює максимальному степеню двочлена з (2), при якому коефіцієнт не дорівнює нулю.

Запишемо далі алгоритм ділення многочленів методом невизначених коефіцієнтів та його реалізацію на прикладі ділення многочлена -12x + 4x - 3x + 4x + 8x - 1 на двочлен x +1. Алгоритм не є складний і користуватися ним дуже легко та корисно.

-6-

Алгоритмічний Реалізація алгоритміч-

припис ного припису

1.Записати многочлен- -12x + c1x + c2x + c3x + c4

частку з відомим стар-

шим коефіцієнтом

2.Записати остачу d0x + d1

3.Записати тотожну -12x + 4x - 3x + 4x + 8x - 1=

рівність =(-12x + c1x + c2x + c3x + c4 )x

x(x + 1)+ d0x + d1

4.Звести подібні члени -12x + c1x + (c2 - 12)х +

в правій частині рівно- +(c3+ c1)х +(c4+ c2)х +

сті +(c3+d0 )x+ c4+ d1

5.Прирівняти коефіці- c1=4

єнти при однакових c2 - 12= -3

степенях х у лівій і пра- c4+ c2=8

вій частинах рівності c3+d0=0

c4+ d1= -1

6.Розв'язати систему c1=4; c2=9; c3=0; c4= -1;

d0=0; d1=0;

7.Записати частку -12x + 4х + 9х - 1

8.Записати остачу 0

Отже -12x + 4x - 3x + 4x + 8x - 1= (x +1)( -12x + 4х+ + 9х - 1).Таким чином ми розклали многочлен на множники методом невизначених коефіцієнтів.У цьому випадку многочлен поділився націло.

-7-

Схема Горнера.

При діленні многочлена An(X)=a0x + a1x + ... + +an-1x + an, поданого в канонічному вигляді, на двочлен (х - а) для визначення коефіцієнтів частки застосовується схема Горнера - за ім'ям англійського математика Горнера (1786 - 1837).

Спосіб обчислення за цією семою грунтується на методі невизначених коефіцієнтів.

Нехай при діленні многочлена степеня n

An(X)=a0x + a1x + ... + an-1x + an

на двочлен х - а дістали многочлен-частку Bn-1(X)= =a0x + b1x + ... + bn-1x степеня n - 1, а в остачі -число (зокрема нуль).За методом невизначених коефіцієнтів маємо:

a0+ a1x + a2x + ... +an-2 x + an-1x + an=(a0x + b1x + ... + + bn-2x + bn-1)(x - a) + r ,

тобто a0+ a1x + a2x + ... +an-2 x + an-1x + an=a0x + +b1x + b2x + ... + bn-2x + bn-1x - a0aх - b1ax - ... - - bn-2ax - bn-1a + r .

Прирівнюючи коефіцієнти при однакових степенях х у лівій і правій частинах рівності, знаходимо:

a1=b1 - aa0,

a2=b2 - ab1,

.....................

an-1=bn-1 - abn-2 ,

an=r - abn-1,

Звідки дістаємо рекурентні співвідношення для

-8-

знаходження коефіцієнтів b1,b2, ... ,bn-1 і остачі r :

b1=a1 + aa0,

b2=a2 + ab1,

.....................

bn-1=an-1 + abn-2,

r = an + abn-1.

Відповідний алгоритм обчислення коефіцієнтів часткимBn-1(X) і остачі r зручно записати у вигляді схеми ,яка і носить ім'я Горнера:

a0 a1 a2 ... an-1 an

+ + ... + +

aa0 ab1 ... abn-2 abn-1

a0 b1 b2 ... bn-1 r

Як бачимо, в цій схемі кожне число третього рядка, починаючи з коефіцієнта b1 , дістаємо з попереднього числа цього рядка множенням на число а і додаванням до утвореного результату відповідного числа першого рядка, яке стоїть над шуканим числом.

Приклади.

1.Використовуючи схему Горнера ,знайдемо частку та остачу від ділення многочлена 2х - 5х + 3