Полином Лагранжа

Пусть на плоскости заданы точка: . Полиномом Лагранжа называется полином n-й степени, проходящий через все точки . Если точки не образуют возвратов, то такой полином существует и является единственным. Под возвратом понимается ситуация, когда существуют две точки и такие, что .

Как построить такой полином? Лагранж предложил следующий алгоритм. Полином строится как сумма полиномов n-й степени:

Каждый из полиномов , входящих в сумму, строится следующим образом. Корнями полинома являются все точки за исключением точки . Единственность обеспечивается за счет того, что коэффициент при старшем члене an подбирается так, чтобы полином проходил через точку . В записи Лагранжа полином выглядит следующим образом:

(6.6)

В записи 6.6 в числителе находится приведенный полином, построенный по корням, а , деленное на знаменатель в формуле 6.6, задает - старший коэффициент полинома.

Условия, накладываемые на полиномы , обеспечивают выполнение требований к полиному Лагранжа - сумма полиномов будет полиномом, проходящим через все заданные точки.

Поскольку алгоритм построения приведенного полинома по его корням уже разобран, то схема построения полинома Лагранжа может выглядеть так:

//Полином Лагранжа определяется как сумма из n+1//полиномов Pk, для которых известны корни. for(int k=0; k<=n; k++) { //Задание корней для полинома Pk for(int i =0; i<k; i++) roots[i] = X[i]; for(int i =k+1; i<=n; i++) roots[i-1] = X[i]; //Вычисление коэффициентов приведенного полинома по его корням coefk = CalcCoefFromRoots(roots); //вычисление An - старшего коэффициента полинома. An = Y[k] / HornerP(coefk,X[k]); //Добавление очередного полинома Pk к PL - сумме полиномов for(int i =0; i<=n; i++) { coefL[i]= coefL[i]+An*coefk[i]; } }

В этой схеме:

X и Y - массивы, задающие декартовы координаты точек, через которые проходит полином Лагранжа,
n - степень полинома,
roots - массив корней приведенного полинома ,
coefk - массив его коэффициентов,
An - старший коэффициент полинома, вычисляемый из условия прохождения полинома через точку с координатами X[k], Y[k],
coefL - массив коэффициентов полинома Лагранжа,
HornerP - метод, вычисляющий по схеме Горнера значение полинома по его коэффициентам и значению координаты x,
CalcCoefFromRoots - метод, вычисляющий массив коэффициентов приведенного полинома по его корням.