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

Матеріал з Вікіпедії — вільної енциклопедії.
Перейти до: навігація, пошук

Інтерполяцій́ний многочле́н Лагра́нжамногочлен мінімального степеня, що приймає дані значення у даному наборі точок. Для 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), а також поліноми yj lj(x), кожний з яких проходить через одну з виділених точок, та приймає нульове значення в інших xi

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

L(x) = \sum_{j=0}^n y_j l_j(x)

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

\ l_j(x)=\prod_{i=0, j\neq 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)

Зокрема,

\int_a^b f(x)dx \approx \sum_{j=0}^n f(x_j) \int_a^b 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\limits_{j=0,i \ne j}^n {(x - x_j) \over  (x_i - x_j)}} = 
                {\prod\limits_{j=0,i \ne j}^n (x - x_0 - jh) \over h^{n-1} \prod\limits_{j=0,i \ne j}^n (i - j)} =
                {{{h^{n-1}}\prod\limits_{j=0,i \ne j}^n ({{x - x_0} \over h} - j)} \over {h^{n-1} \prod\limits_{j=0,i \ne j}^n (i - j)}}\,\!.

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

y = {\frac {x - x_0}{h}\,\!}

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

Приклад реалізації[ред.ред. код]

Код на 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;
}

Дивіться також[ред.ред. код]