Многочлен Лагранжа
Інтерполяцій́ний многочле́н Лагра́нжа — многочлен мінімального степеня, що приймає дані значення у даному наборі точок. Для пар чисел , де всі різні, існує єдиний многочлен степеня не більшого від , для якого .
У найпростішому випадку - це лінійний многочлен, графік якого — пряма, що проходить через дві задані точки.
Лагранж запропонував спосіб обчислення таких многочленів:
де базисні поліноми визначаються за формулою:
Очевидно, що мають такі властивості:
- Це поліноми степеня
- при
Звідси випливає, що , як лінійна комбінація , може мати степінь не більший від , та .
Поліноми Лагранжа використовуються для інтерполяції, а також для чисельного інтегрування.
Нехай для функції відомі значення у деяких точках. Тоді ця функція може інтерполюватися як
Зокрема,
Значення інтегралів від не залежать від , тож їх можна обчислювати заздалегідь, знаючи послідовність .
У вказаному випадку можна виразити через відстань між вузлами інтерполяції h та початкову точку :
- ,
і, як наслідок,
- .
Якщо підставити ці вирази у формулу базисного полінома та винести h за знаки множення у чисельнику та знаменнику, отримаємо
- .
Після цього можна ввести заміну змінної
і отримати поліном від у, який будується з використанням лише цілочисленної арифметики. Недоліком цього підходу є факторіальна складність чисельника та знаменника, що вимагає використання алгоритмів з багатобайтним представленням чисел.
Ми бажаємо інтерполювати ƒ(x) = x2 на діапазоні 1 ≤ x ≤ 3, із відомими трьома точками:
Інтерполяційний многочлен такий:
Ми бажаємо інтерполювати ƒ(x) = x3 на діапазоні 1 ≤ x ≤ 3, із відомими трьома точками:
Інтерполяційний многочлен такий:
Як видно з побудови, кожен раз коли вузол змінюється, всі базові многочлени Лагранжа необхідно перерахувати. Найкращим варіантом інтерполяційного многочлена для практичних (або обчислювальних) цілей є барицентрична форма інтерполяції Лагранжа або поліном Ньютона.
Лагранжева та інші інтерполяції із рівновіддаленими точками, як у прикладах згори, породжують многочлен, що коливається навколо справжньої функції. Ця поведінка сильніше себе виявляє у випадку більшої кількості заданих точок, призводячи до розбіжності відомої як феномен Рунге; проблему можна усунути обравши для інтерполяції вузли Чебишова.
Базові многочлени Лагранжа можна використати у чисельному інтегруванні для виведення формул Ньютона-Котеса.
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;
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. — 2200+ с.(укр.)
- 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