Многочлен Лагранжа
Інтерполяцій́ний многочле́н Лагра́нжа — многочлен мінімального степеня, що приймає дані значення у даному наборі точок. Для пар чисел , де всі різні, існує єдиний многочлен степеня не більшого від , для якого .
У найпростішому випадку - це лінійний многочлен, графік якого — пряма, що проходить через дві задані точки.
Визначення
ред.Лагранж запропонував спосіб обчислення таких многочленів:
де базисні поліноми визначаються за формулою:
Очевидно, що мають такі властивості:
- Це поліноми степеня
- при
Звідси випливає, що , як лінійна комбінація , може мати степінь не більший від , та .
Застосування
ред.Поліноми Лагранжа використовуються для інтерполяції, а також для чисельного інтегрування.
Нехай для функції відомі значення у деяких точках. Тоді ця функція може інтерполюватися як
Зокрема,
Значення інтегралів від не залежать від , тож їх можна обчислювати заздалегідь, знаючи послідовність .
Для випадку рівномірного розподілу на відрізку вузлів інтерполяції
ред.У вказаному випадку можна виразити через відстань між вузлами інтерполяції 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;
}
Див. також
ред.Література
ред.- Григорій Михайлович Фіхтенгольц. Курс диференціального та інтегрального числення. — 2024. — 2403 с.(укр.)
- ALGLIB [Архівовано 10 січня 2016 у Wayback Machine.] has an implementations in C++ / C# / VBA / Pascal.
- GSL [Архівовано 9 червня 2005 у Wayback Machine.] has a polynomial interpolation code in C
- SO [Архівовано 4 березня 2016 у Wayback Machine.] 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 [Архівовано 1 вересня 2006 у Wayback Machine.] at Holistic Numerical Methods Institute [Архівовано 6 вересня 2006 у Wayback Machine.]
- Lagrange interpolation polynomial [Архівовано 5 березня 2013 у Wayback Machine.] on www.math-linux.com