Інтерполяцій́ний многочле́н Лагра́нжа — многочлен мінімального степеня, що приймає дані значення у даному наборі точок. Для пар чисел , де всі різні, існує єдиний многочлен степеня не більшого від , для якого .
У найпростішому випадку - це лінійний многочлен, графік якого — пряма, що проходить через дві задані точки.
Визначення
Лагранж запропонував спосіб обчислення таких многочленів:
де базисні поліноми визначаються за формулою:
Очевидно, що мають такі властивості: Це поліноми степеня
при
Звідси випливає, що , як лінійна комбінація , може мати степінь не більший від , та .
Застосування
Поліноми Лагранжа використовуються для інтерполяції, а також для чисельного інтегрування.
Нехай для функції відомі значення у деяких точках. Тоді ця функція може інтерполюватися як
Зокрема,
Значення інтегралів від не залежать від , тож їх можна обчислювати заздалегідь, знаючи послідовність .
Для випадку рівномірного розподілу на відрізку вузлів інтерполяції У вказаному випадку можна виразити через відстань між вузлами інтерполяції 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; }
Див. також Комбінаторна теорема про нулі Сплайн
Література
ALGLIB has an implementations in C++ / C# / VBA / Pascal. GSL has a polynomial interpolation code in C SO 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 at Holistic Numerical Methods Institute Lagrange interpolation polynomial on www.math-linux.com