Многочлен Лагранжа

Інтерполяцій́ний многочле́н Лагра́нжа — многочлен мінімального степеня, що приймає дані значення у даному наборі точок. Для $n+1$ пар чисел $(x_0,y_0),(x_1,y_1)\dots (x_n,y_n)$, де всі $x_i$ різні, існує єдиний многочлен $L(x)$ степеня не більшого від $n$, для якого $L(x_i)=y_i$.

У найпростішому випадку $n=1$ - це лінійний многочлен, графік якого — пряма, що проходить через дві задані точки.

Визначення

Цей приклад представляє інтерполяційний многочлен Лагранжа для чотирьох точок (-9,5), (-4,2), (-1,-2) і (7,9), а також поліноми y_j l_j(x), кожний з яких проходить через одну з виділених точок, та приймає нульове значення в інших x_i

Лагранж запропонував спосіб обчислення таких многочленів:

$L(x)=\sum _{j=0}^n{y}_j{l}_j(x)$

де базисні поліноми визначаються за формулою:

$l_j(x)=\prod _{i=0,j\ne i}^n\frac{x-x_i}{x_j-x_i}=\frac{x-x_0}{x_j-x_0}\cdots \frac{x-x_{j-1}}{x_j-x_{j-1}}\frac{x-x_{j+1}}{x_j-x_{j+1}}\cdots \frac{x-x_n}{x_j-x_n}$

Очевидно, що $l_j(x)$ мають такі властивості:

• Це поліноми степеня $n$
• $l_j(x_j)=1$
• $l_j(x_i)=0$ при $i\ne j$

Звідси випливає, що $L(x)$, як лінійна комбінація $l_j(x)$, може мати степінь не більший від $n$, та $L(x_j)=y_j$.

Застосування

Поліноми Лагранжа використовуються для інтерполяції, а також для чисельного інтегрування.

Нехай для функції $f(x)$ відомі значення $y_j=f(x_j)$ у деяких точках. Тоді ця функція може інтерполюватися як

$f(x)\approx \sum _{j=0}^{n}f(x_j)l_j(x)$

Зокрема,

$\underset{a}{\overset{b}{\int }}f(x)dx\approx \sum _{j=0}^{n}f(x_j)\underset{a}{\overset{b}{\int }}{l}_j(x)dx$

Значення інтегралів від $l_j$ не залежать від $f(x)$, тож їх можна обчислювати заздалегідь, знаючи послідовність $x_i$.

Для випадку рівномірного розподілу на відрізку вузлів інтерполяції

У вказаному випадку можна виразити $x_i$ через відстань між вузлами інтерполяції h та початкову точку $x_0$:

$x_j\equiv x_0+jh$,

і, як наслідок,

$x_i-x_j\equiv (i-j)h$.

Якщо підставити ці вирази у формулу базисного полінома та винести h за знаки множення у чисельнику та знаменнику, отримаємо

$l_i(x)=\prod _{j=0,i\ne j}^n\frac{(x-x_j)}{(x_i-x_j)}=\frac{\prod _{j=0,i\ne j}^n(x-x_0-jh)}{h^{n-1}\prod _{j=0,i\ne j}^n(i-j)}=\frac{h^{n-1}\prod _{j=0,i\ne j}^n(\frac{x-x_0}{h}-j)}{h^{n-1}\prod _{j=0,i\ne j}^n(i-j)}$.

Після цього можна ввести заміну змінної

$y=\frac{x-x_0}{h}$

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

Приклади

Приклад 1

Ми бажаємо інтерполювати ƒ(x) = x² на діапазоні 1 ≤ x ≤ 3, із відомими трьома точками:

$\begin{array}{cccccc}{x}_0& =1& & & f(x_0)& =1\\ x_1& =2& & & f(x_1)& =4\\ x_2& =3& & & f(x_2)& =9.\end{array}$

Інтерполяційний многочлен такий:

$\begin{array}{cc}L(x)& =1\cdot \frac{x-2}{1-2}\cdot \frac{x-3}{1-3}+4\cdot \frac{x-1}{2-1}\cdot \frac{x-3}{2-3}+9\cdot \frac{x-1}{3-1}\cdot \frac{x-2}{3-2}\\ & =x^2.\end{array}$

Приклад 2

Ми бажаємо інтерполювати ƒ(x) = x³ на діапазоні 1 ≤ x ≤ 3, із відомими трьома точками:

$x_0=1$	$f(x_0)=1$
$x_1=2$	$f(x_1)=8$
$x_2=3$	$f(x_2)=27$

Інтерполяційний многочлен такий:

$\begin{array}{cc}L(x)& =1\cdot \frac{x-2}{1-2}\cdot \frac{x-3}{1-3}+8\cdot \frac{x-1}{2-1}\cdot \frac{x-3}{2-3}+27\cdot \frac{x-1}{3-1}\cdot \frac{x-2}{3-2}\\ & =6x^2-11x+6.\end{array}$

Зауваження

Приклад розбіжності інтерполяційного многочлена Лагранжа.

Як видно з побудови, кожен раз коли вузол $x_k$ змінюється, всі базові многочлени Лагранжа необхідно перерахувати. Найкращим варіантом інтерполяційного многочлена для практичних (або обчислювальних) цілей є барицентрична форма інтерполяції Лагранжа або поліном Ньютона.

Лагранжева та інші інтерполяції із рівновіддаленими точками, як у прикладах згори, породжують многочлен, що коливається навколо справжньої функції. Ця поведінка сильніше себе виявляє у випадку більшої кількості заданих точок, призводячи до розбіжності відомої як феномен Рунге; проблему можна усунути обравши для інтерполяції вузли Чебишова.

Базові многочлени Лагранжа можна використати у чисельному інтегруванні для виведення формул Ньютона—Котеса.

Приклад реалізації

Код в Oberon

TYPE Point=RECORD x,y:REAL END;

PROCEDURE PolynomLagrange(p:ARRAY OF Point;x:REAL):REAL;
VAR c,s:REAL;
	i,j:INTEGER;
BEGIN
	s:=0;
	FOR i:=0 TO LEN(p)-1 DO
		c := 1;
		FOR j:=0 TO LEN(p)-1 DO
			IF i#j THEN c:=c*(x-p[j].x)/(p[i].x-p[j].x)END
		END;
		s:=s+c*y[i]
	END;
	RETURN s
END PolynomLagrange;

Код в C#

double L_BI_MI(double x)
{
     double r = 0, ra, rb;
     for (int i = 0; i < n; i++)
     {
           ra = rb = 1;
           for (int j = 0; j < n; j++)
               if (i != j)
               {
                   ra *= x - x_[j];    //(x_[i],y_[i]) - інтерполяційні вузли
                   rb *= x_[i] - x_[j];
               }
            r += ra * y_[i] / rb;
    }
    return r;
}

Див. також

• Комбінаторна теорема про нулі
• Сплайн

Література

• Шаблон:Фіхтенгольц.укр
• Шаблон:Ляшко.Ємельянов.Боярчук.Математичний аналіз.ч1
• Шаблон:Дороговцев.Математичний аналіз.ч1
• ALGLIB Шаблон:Webarchive has an implementations in C++ / C# / VBA / Pascal.
• GSL Шаблон:Webarchive has a polynomial interpolation code in C
• SO Шаблон:Webarchive has a MATLAB example that demonstrates the algorithm and recreates the first image in this article
• Lagrange Method of Interpolation — Notes, PPT, Mathcad, Mathematica, MATLAB, Maple Шаблон:Webarchive at Holistic Numerical Methods Institute Шаблон:Webarchive
• Lagrange interpolation polynomial Шаблон:Webarchive on www.math-linux.com