Очікує на перевірку

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

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

Інтерполяцій́ний многочле́н Лагра́нжамногочлен мінімального степеня, що приймає дані значення у даному наборі точок. Для пар чисел , де всі різні, існує єдиний многочлен степеня не більшого від , для якого .

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

Визначення

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

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

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

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

  • Це поліноми степеня
  • при

Звідси випливає, що , як лінійна комбінація , може мати степінь не більший від , та .

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

[ред. | ред. код]

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

Нехай для функції відомі значення у деяких точках. Тоді ця функція може інтерполюватися як

Зокрема,

Значення інтегралів від не залежать від , тож їх можна обчислювати заздалегідь, знаючи послідовність .

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

[ред. | ред. код]

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

,

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

.

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

.

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

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

Приклади

[ред. | ред. код]

Приклад 1

[ред. | ред. код]

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

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

Приклад 2

[ред. | ред. код]

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

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

Зауваження

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

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

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

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

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

[ред. | ред. код]

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

Див. також

[ред. | ред. код]

Література

[ред. | ред. код]