Интерполяционный многочлен на произвольных функциях

в 9:33, , рубрики: Алгоритмы, график, интерполяционный многочлен, Лагранж, математика, многочлен, Ньютон, полином, точки, уравнения, функция

Введение

Приветствую, уважаемые читатели! Сегодня предлагаю поразмышлять о следующей задачке:

Дано $n$ пар точек на плоскости $(x_1;y_1),...,(x_n;y_n)$. Все $x_i$ различны. Необходимо найти многочлен $M(x)$ такой, что $M(x_i)=y_i$, где $iin{1,...,n}$

Переводя на русский язык имеем: Иван загадал $n$ точек на плоскости, а Мария, имея эту информацию, должна придумать функцию, которая (по меньшей мере) будет проходить через все эти точки. В рамках текущей статьи наша задача сводится к помощи Марии окольными путями.

«Почему окольными путями?» — спросите вы. Ответ традиционный: это статья является продолжением серии статей дилетантского характера про математику, целью которых является популяризация математического мира.

Процесс

Для начала стоит отметить, что некоторое кол-во интерполяционных многочленов уже, разумеется, существует. Оные полиномы как раз предназначены для решения искомой задачи. Среди них особенно известны такие как полином Лагранжа и Ньютона.

А также необходимо внести ясность, что такое «произвольные функции» (термин приходит из названия текущей статьи). Под ними понимается любая унарная функция, результат которой есть биективное отображение аргумента.

В рамках статьи предлагаю за такую функцию взять десятичный логарифм $lg$ и следующие точки:

$(0;0)\ (1;1)\ (2;3)\ (3;0)$

Представляя их на плоскости, должно получится нечто следующее:

image
Нетрудно заметить, что сейчас кол-во пар точек равно $n=4$.

При решении данной задачи приходит на ум некая системы уравнений, где кол-во линейно-независимых строк равно $n$. Что же это за система уравнений такая?

Давайте попробуем функцию записать в виде суммы десятичных логарифмов с коэффициентами про оных (да так, чтобы кол-во коэффициентов было равно $n$):

$f(x)=alg(x+3)+blg(x+2)+clg(x+1)+d$

Аргументы при $lg$ различные чтобы избежать линейной зависимости строк в будущем (можно придумать другие). А также, учитывая, что область определения функции как минимум $in[0;3]$ (на основе заданных условием точек), мы таким образом обеспечиваем существование области значений для функции $lg$ в этой области определения.

Так как нам известны $n$ пар точек, то обратимся к ним для того, чтобы построить следующую тривиальную систему:

$begin{cases}displaystyle{ f(0)=0 Rightarrow alg(3)+blg(2)+clg(1)+d=0\ f(1)=1 Rightarrow alg(4)+blg(3)+clg(2)+d=1\ f(2)=3 Rightarrow alg(5)+blg(4)+clg(3)+d=3\ f(3)=0 Rightarrow alg(6)+blg(5)+clg(4)+d=0 } end{cases} $

Тривиальность системы заключается в том, что мы просто найдем такие $a,b,c,d$, которые будет удовлетворять всему набору условия.

Собственно решая данную систему относительно $a,b,c,d$ получим следующее решение:

$begin{cases}displaystyle{ a=frac{(5 lg^2(2) - 5 lg(2) lg(3) + lg(8/3) lg(5)) lg(10)}{3 lg^3(2) - lg(9/5) lg^2(2) + lg^2(3) lg(20) - lg(2) lg(5) lg(243/5)}\ b=frac{lg(675/512) lg(2) lg(10)}{-3 lg^3(2) + lg(9/5) lg^2(2) - lg^2(3) lg(20) + lg(2) lg(5) lg(243/5)}\ c=frac{lg(10) (2 lg^2(2) + lg(2) (lg(3) - 7 lg(5)) + lg(5) lg(45))}{3 lg^3(2) - lg(9/5) lg^2(2) + lg^2(3) lg(20) - lg(2) lg(5) lg(243/5)}\ d=frac{-9 lg^3(2) + lg^2(2) lg(25/9) + lg^2(3) lg(5) + lg(243/125) lg(2) lg(3)} {3 lg^3(2) - lg(9/5) lg^2(2) + lg^2(3) lg(20) - lg(2) lg(5) lg(243/5)} } end{cases}$

На этом задача естественным образом подходит к концу, остается только записать это в единую функцию:

$f(x)=frac{(5 lg^2(2) - 5 lg(2) lg(3) + lg(8/3) lg(5)) lg(10)}{3 lg^3(2) - lg(9/5) lg^2(2) + lg^2(3) lg(20) - lg(2) lg(5) lg(243/5)}lg(x+3)\ +frac{lg(675/512) lg(2) lg(10)}{-3 lg^3(2) + lg(9/5) lg^2(2) - lg^2(3) lg(20) + lg(2) lg(5) lg(243/5)}lg(x+2)\ +frac{lg(10) (2 lg^2(2) + lg(2) (lg(3) - 7 lg(5)) + lg(5) lg(45))}{3 lg^3(2) - lg(9/5) lg^2(2) + lg^2(3) lg(20) - lg(2) lg(5) lg(243/5)}lg(x+1)\ +frac{-9 lg^3(2) + lg^2(2) lg(25/9) + lg^2(3) lg(5) + lg(243/125) lg(2) lg(3)} {3 lg^3(2) - lg(9/5) lg^2(2) + lg^2(3) lg(20) - lg(2) lg(5) lg(243/5)}$

Она, разумеется, будет проходить через заданный набор точек. А график функции будет выглядеть следующим образом:

image
Также, ради наглядности, можно привести аппроксимированную систему решений:

$begin{cases}displaystyle{aapprox-3428.6\ bapprox3789.2\ capprox-790.20\ dapprox495.22} end{cases}$

Тогда аппроксимированный вид функции будет следующий:

$f(x)=-3428.6lg(x+3)+3789.2lg(x+2)-790.20lg(x+1)+495.22$

Разумеется, никто не говорит о том, что полученная функция будет минимальной (тот же полином Лагранжа даст более короткую форму). Однако, данный метод позволяет выразить функцию через набор произвольных функций (правда, имея в виду ограничения, заданные выше по статье).

Различные примеры

На десерт аналогично построим функцию в радикалах:

$f(x)=ax^3+bx^2+cx+d$

Составим систему уравнения для нахождения коэффициентов:

$begin{cases}displaystyle{ f(0)=0 Rightarrow d=0\ f(1)=1 Rightarrow a+b+c+d=1\ f(2)=3 Rightarrow 8a+4b+2c+d=3\ f(3)=0 Rightarrow 27a+9b+3c+d=0 } end{cases} $

Её решение единственно и выглядит следующим образом:

$begin{cases}displaystyle{a=-1\ b=frac{7}{2}\ c=-frac{3}{2}\ d=0} end{cases}$

Тогда готовая функция выглядит следующим образом:

$f(x)=-x^3+frac{7}{2}x^2-frac{3}{2}x$

Что по совместительтву является полином Лагранжа для данного набора точек (т.к. оный в неявном виде реализует радикальную форму алгоритма из статьи). График на области заданных точек выглядит так:

image

Самым интересным в данной истории является то, что произвольные функции для построения конечной функции можно и нужно комбинировать. Иными словами, функция может быть построена сразу на радикалах и логарифмах, а может и на чем-то другом (показательные функции, факториалы, и т.п. ). Лишь бы полученный набор функций обеспечивал линейную независимость строк при подборе коэффициентов. В общем виде для заданных $n$ пар точек это выглядит так:

$f(x)=a_1*g_1(x)+...+a_n*g_n(x)$

Где $a_1,..,a_n$ — коэффициенты которые предстоит найти через систему уравнений (СЛАУ), а $g_1,...,g_n$ — некоторые функции, которые обеспечат линейную независимость при нахождении коэффициентов.

А дальше — по алгоритму выше, всё совершенно аналогично. Не забывая о том, что $g_1,...,g_n$ должны быть определены на заданных условием точках.

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

$f(x)=ax^2+b2^x+cx+d$

Дабы удовлетворить заданному набору точек, коэффициенты будут в таком случае следующие (найдены строго по алгоритму из статьи):

$begin{cases}displaystyle{a=frac{7}{2}\ b=-6\ c=frac{7}{2}\ d=6} end{cases}$

А сама функция будет такой:

$f(x)=frac{7}{2}x^2-6*2^x+frac{7}{2}x+6$

График же будет выглядит практически также как предыдущий (на области заданных точек).
Если хочется более «гладкий» график, то можно посмотреть в сторону факториальной формы, например такой:

$f(x)=a(x+2)!+b(x+1)!+cx!+d$

Найдем коэффициенты:

$$display$$begin{cases}displaystyle{2a+b+c+d=0\ 6a+2b+c+d=1\ 24a+6b+2c+d=3\ 120a+24b+6c+d=0} end{cases} Rightarrow begin{cases}displaystyle{a = -13/16\ b = 17/4\ c = -3/8\ d=-9/4} end{cases}$$display$$

Подставим оные в готовую функцию:

$f(x)=-frac{13}{16}(x+2)!+frac{17}{4}(x+1)!-frac{3}{8}x!-frac{9}{4}$

А также полюбуемся очень хорошим графиком:
image

Зачем это нужно?

Да хотя бы для того, чтобы представить себе пучок веревок, стянутых пластиковыми хомутами :)
image
(* Тут мы просто наложили все графики друг на друга)

На этом в рамках текущей статьи все, рекомендую поиграться самостоятельно.

Всего наилучшего,
с вами был Петр.

Автор: ParadoxFilm

Источник

Поделиться

* - обязательные к заполнению поля