Сложение и умножение полиномов

При рассмотрении полинома Лагранжа возникала необходимость в нахождении суммы полиномов одинаковой степени, заданных своими коэффициентами. Пусть P(x) и Q(x) - полиномы степени n и m, соответственно, заданные своими коэффициентами, и пусть для определенности . Тогда суммой полиномов называется полином R(x) степени n, коэффициенты которого вычисляются следующим образом:

Пусть полиномы P(x) и Q(x) заданы, подобно полиному Лагранжа, точками, через которые они проходят:

Тогда нетрудно найти подобное представление и для полинома R(x), представляющего сумму полиномов:

В этом случае понадобится вычислить значения полинома Q(x) в n точках.

Если полиномы P(x) и Q(x) заданы своими корнями, то определить корни полинома суммы не удается, более того, у суммы вообще может не быть корней. В этом случае для каждого полинома по корням можно вычислить коэффициенты, а затем определить коэффициенты полинома суммы. Можно также рассматривать корни как частный случай задания множества точек, через которые проходит полином, и применить предыдущую схему для определения множества точек, через которые проходит полином суммы.

Рассмотрим теперь операцию умножения полиномов:

Нетрудно понять, что полином S(x) является полиномом степени и имеет коэффициент. Как вычисляется произведение, если заданы полиномы сомножители P(x) и Q(x)? Замечу, что произведение полиномов часто встречается на практике и имеет специальное имя - свертка полиномов.

В отличие от сложения полиномов проще всего найти свертку, если заданы корни обоих полиномов. В этом случае никаких вычислений не требуется, поскольку n корней P(x) и m корней Q(x) будут корнями S(x). Если у полиномов P(x) и Q(x) есть совпадающие корни, то у S(x) появятся кратные корни.

Если исходные полиномы P(x) и Q(x) заданы своими точками, то нетрудно получить набор точек для полинома произведения. Схема во многом похожа на ту, что имеет место при сложении полиномов, заданных точками:

Для получения множества точек, задающих представление полинома S(x), приходится вычислять значение полинома Q(x) в n точках и значение полинома P(x) в m точках, а затем выполнять соответствующее умножение значений двух полиномов.

Если исходные полиномы P(x) и Q(x) заданы своими коэффициентами, то имеем:

Каждый член первой суммы приходится умножать на все члены второй суммы и затем приводить подобные члены при одинаковых степенях x. Нетрудно заметить, что в результате коэффициенты полинома S(x) определяются следующими соотношениями:

Суммирование идет по всем наборам k и r, дающим в сумме значение i. Понятно, что для крайних значений (i=0 и i=n+m) сумма состоит из одного члена, поскольку подобные члены для x в нулевой степени и степени n+m отсутствуют. Число членов суммирования увеличивается при приближении к середине интервала [0, n+m].