Полиномиальная интерполяция - Polynomial interpolation

В численном анализе , полиномиальная интерполяция является интерполяция заданного набора данных самая многочлен наименьшей возможной степени , которая проходит через точки набора данных.

Приложения

Полиномы можно использовать для аппроксимации сложных кривых, например формы букв в типографике , с учетом нескольких точек. Соответствующим приложением является оценка натурального логарифма и тригонометрических функций : выберите несколько известных точек данных, создайте справочную таблицу и выполните интерполяцию между этими точками данных. Это приводит к значительно более быстрым вычислениям. Полиномиальная интерполяция также формирует основу для алгоритмов в числовых квадратурных и числовых обыкновенных дифференциальных уравнений и схем безопасных многосторонних вычислений и совместного использования секретов.

Полиномиальная интерполяция также имеет важное значение для выполнения суб-квадратичная умножения и возведения в квадрат , такие как Карацубы умножения и умножения Тоом-Кука , где интерполяция через точки на многочлен , который определяет продукт дает сам продукт. Например, если a = f ( x ) = a ₀ x ⁰ + a ₁ x ¹ + ... и b = g ( x ) = b ₀ x ⁰ + b ₁ x ¹ + ..., произведение ab равно эквивалентно W ( x ) = f ( x ) g ( x ). Поиск точек вдоль W ( x ) путем замены x на малые значения в f ( x ) и g ( x ) дает точки на кривой. Интерполяция, основанная на этих точках, даст члены W ( x ), а затем произведение ab . В случае умножения Карацубы этот метод значительно быстрее, чем квадратное умножение, даже для входов небольшого размера. Это особенно актуально при реализации на параллельном оборудовании.

Определение

Принимая во внимание множество п + 1 точек данных ( х _я , у _я ) , где никакие два х _I не являются такими же, полином , называется интерполировать данные , если для каждого . ${\ displaystyle p: \ mathbb {R} \ rightarrow \ mathbb {R}}$${\ displaystyle p (x_ {j}) = y_ {j}}$${\ displaystyle j \ in \ {0,1, \ dotsc, n \}}$

Теорема интерполяции

Для различных точек и соответствующих значений существует уникальный многочлен степени не выше, который интерполирует данные . ${\ displaystyle n + 1}$${\ displaystyle x_ {0}, x_ {1}, \ dotsc, x_ {n}}$${\ displaystyle y_ {0}, y_ {1}, \ dotsc, y_ {n}}$${\ displaystyle n}$${\ displaystyle \ {(x_ {0}, y_ {0}), \ dotsc, (x_ {n}, y_ {n}) \}}$

Доказательство

Рассмотрим базисные функции Лагранжа, заданные формулой

${\ displaystyle L_ {n, j} (x) = \ prod _ {k \ neq j} {\ frac {x-x_ {k}} {x_ {j} -x_ {k}}}.}$

Обратите внимание, что это многочлен степени . Кроме того, для каждого мы имеем , где - дельта Кронекера . Отсюда следует, что линейная комбинация ${\ displaystyle L_ {n, j}}$${\ displaystyle n}$${\ displaystyle x_ {k}}$${\ displaystyle L_ {n, j} (x_ {k}) = \ delta _ {jk}}$${\ displaystyle \ delta _ {jk}}$

${\ displaystyle p (x) = \ sum _ {j = 0} ^ {n} y_ {j} L_ {n, j} (x)}$

- интерполирующий полином степени . ${\ displaystyle n}$

Чтобы доказать единственность, предположим, что существует еще один интерполяционный многочлен степени не выше . Так как для всех , то отсюда следует , что многочлен имеет различные нули. Однако имеет степень не выше и, согласно основной теореме алгебры , может иметь не больше нулей; поэтому . ${\ displaystyle q}$${\ displaystyle n}$${\ Displaystyle p (x_ {k}) = q (x_ {k})}$${\ Displaystyle к = 0, \ dotsc, n}$${\ displaystyle pq}$${\ displaystyle n + 1}$${\ displaystyle pq}$${\ displaystyle n}$${\ displaystyle n}$${\ displaystyle p = q}$

Следствие

Интересное следствие интерполяционной теоремы состоит в том, что если является многочленом степени не выше , то интерполяционный многочлен от в различных точках является самим собой. ${\ displaystyle f}$${\ displaystyle n}$${\ displaystyle f}$${\ displaystyle n + 1}$${\ displaystyle f}$

Теорема единственности

Учитывая набор из n + 1 точек данных ( x _i , y _i ), где нет двух одинаковых x _i , ищется многочлен p степени не выше n со свойством

${\ displaystyle p (x_ {i}) = y_ {i}, \ qquad i = 0, \ ldots, n.}$

Теорема о неразрывности утверждает, что такой многочлен p существует и единственен и может быть доказан с помощью матрицы Вандермонда , как описано ниже.

Теорема утверждает, что для n + 1 узлов интерполяции ( x _i ) полиномиальная интерполяция определяет линейную биекцию

${\ displaystyle L_ {n}: \ mathbb {K} ^ {n + 1} \ to \ Pi _ {n}}$

где Π _n - векторное пространство многочленов (определенных на любом интервале, содержащем узлы) степени не выше n .

Построение интерполяционного полинома

Предположим, что интерполяционный полином имеет вид

${\ displaystyle p (x) = a_ {n} x ^ {n} + a_ {n-1} x ^ {n-1} + \ cdots + a_ {2} x ^ {2} + a_ {1} x + a_ {0}. \ qquad (1)}$

Утверждение, что p интерполирует точки данных, означает, что

${\ displaystyle p (x_ {i}) = y_ {i} \ qquad {\ mbox {для всех}} i \ in \ left \ {0,1, \ dots, n \ right \}.}$

Если мы подставим сюда уравнение (1), мы получим систему линейных уравнений относительно коэффициентов a _k . Система в матрично-векторной форме считывает следующее умножение :

${\ displaystyle {\ begin {bmatrix} x_ {0} ^ {n} & x_ {0} ^ {n-1} & x_ {0} ^ {n-2} & \ ldots & x_ {0} & 1 \\ x_ {1 } ^ {n} & x_ {1} ^ {n-1} & x_ {1} ^ {n-2} & \ ldots & x_ {1} & 1 \\\ vdots & \ vdots & \ vdots && \ vdots & \ vdots \ \ x_ {n} ^ {n} & x_ {n} ^ {n-1} & x_ {n} ^ {n-2} & \ ldots & x_ {n} & 1 \ end {bmatrix}} {\ begin {bmatrix} a_ {n} \\ a_ {n-1} \\\ vdots \\ a_ {0} \ end {bmatrix}} = {\ begin {bmatrix} y_ {0} \\ y_ {1} \\\ vdots \\ y_ {n} \ end {bmatrix}}.}$

Мы должны решить эту систему с _к построить интерполянт р ( х ). Матрица слева обычно называется матрицей Вандермонда .

Число обусловленности матрицы Вандермонда может быть большим, вызывая большие ошибки при вычислении коэффициентов a _i, если система уравнений решается с использованием исключения Гаусса .

Поэтому несколько авторов предложили алгоритмы, которые используют структуру матрицы Вандермонда для вычисления численно устойчивых решений за O ( n ² ) операций вместо O ( n ³ ), требуемых методом исключения Гаусса. Эти методы основаны на построении сначала интерполяции Ньютона полинома, а затем преобразовании его в мономиальную форму, указанную выше.

В качестве альтернативы мы можем сразу записать многочлен в терминах многочленов Лагранжа :

${\ displaystyle {\ begin {align} p (x) & = {\ frac {(x-x_ {1}) (x-x_ {2}) \ cdots (x-x_ {n})} {(x_ { 0} -x_ {1}) (x_ {0} -x_ {2}) \ cdots (x_ {0} -x_ {n})}} y_ {0} + {\ frac {(x-x_ {0}) ) (x-x_ {2}) \ cdots (x-x_ {n})} {(x_ {1} -x_ {0}) (x_ {1} -x_ {2}) \ cdots (x_ {1} -x_ {n})}} y_ {1} + \ cdots + {\ frac {(x-x_ {0}) (x-x_ {1}) \ cdots (x-x_ {n-1})} { (x_ {n} -x_ {0}) (x_ {n} -x_ {1}) \ cdots (x_ {n} -x_ {n-1})}} y_ {n} \\ [5pt] & = \ sum _ {i = 0} ^ {n} {\ Bigg (} \ prod _ {\ stackrel {\! 0 \, \ leq \, j \, \ leq \, n} {j \, \ neq \, i}} {\ frac {x-x_ {j}} {x_ {i} -x_ {j}}} {\ Bigg)} y_ {i} \ end {выровнено}}}$

Для матричных аргументов эта формула называется формулой Сильвестра, а матричнозначные полиномы Лагранжа - ковариантами Фробениуса .

Единственность интерполирующего полинома

Доказательство 1

Предположим, мы интерполируем через n + 1 точки данных с помощью полинома p ( x ) не более n степени (нам нужно как минимум n + 1 точек данных, иначе полином не может быть полностью решен). Предположим также, что существует еще один многочлен степени не выше n, который также интерполирует n + 1 точку; назовем это q ( x ).

Подумайте . Мы знаем, ${\ Displaystyle г (х) = п (х) -q (х)}$

1. r ( x ) - многочлен
2. r ( x ) имеет степень не выше n , так как p ( x ) и q ( x ) не выше этой, и мы просто их вычитаем.
3. В n + 1 точках данных . Следовательно, r ( x ) имеет n + 1 корень.${\ displaystyle r (x_ {i}) = p (x_ {i}) - q (x_ {i}) = y_ {i} -y_ {i} = 0}$

Но r ( x ) - многочлен степени ≤ n . У него один корень слишком много. Формально, если г ( х ) является любой ненулевой многочлен, то он должен быть доступен для записи , как , для некоторой константы А . По принципу дистрибутивности n + 1 x умножаются вместе, чтобы получить главный член , то есть на один градус выше установленного нами максимума. Таким образом, r ( x ) может существовать только тогда, когда A = 0 , или, что эквивалентно, r ( x ) = 0 . ${\ Displaystyle г (х) = А (х-х_ {0}) (х-х_ {1}) \ cdots (х-х_ {п})}$ ${\ displaystyle Ax ^ {n + 1}}$

${\ Displaystyle r (x) = 0 = p (x) -q (x) \ подразумевает p (x) = q (x)}$

Итак, q ( x ) (который может быть любым многочленом, если он интерполирует точки) идентичен p ( x ), а q ( x ) уникален.

Доказательство 2

Учитывая матрицу Вандермонда, использованную выше для построения интерполянта, мы можем настроить систему

${\ displaystyle Va = y}$

Чтобы доказать невырожденность V, воспользуемся формулой определителя Вандермонда:

${\ Displaystyle \ Det (V) = \ prod _ {я, j = 0, я <j} ^ {n} (x_ {i} -x_ {j})}$

поскольку n + 1 точек различны, определитель не может быть равен нулю, поскольку никогда не равен нулю, поэтому V неособа и система имеет единственное решение. ${\ displaystyle x_ {i} -x_ {j}}$

В любом случае это означает, что независимо от того, какой метод мы используем для интерполяции: прямой, Лагранж и т. Д. (При условии, что мы можем выполнять все наши вычисления идеально), мы всегда будем получать один и тот же многочлен.

Решения, не связанные с Vandermonde

Мы пытаемся построить наш единственный интерполяционный многочлен в векторном пространстве Π _n многочленов степени n . При использовании мономиального базиса для Π _n мы должны решить матрицу Вандермонда, чтобы построить коэффициенты a _k для интерполяционного полинома. Это может быть очень дорогостоящей операцией (если считать в тактовых циклах компьютера, пытающегося выполнить эту работу). Выбирая другой базис для Π _n, мы можем упростить вычисление коэффициентов, но тогда нам придется выполнять дополнительные вычисления, когда мы хотим выразить интерполяционный полином через мономиальный базис .

Один из методов состоит в том, чтобы записать полином интерполяции в форме Ньютона и использовать метод разделенных разностей для построения коэффициентов, например алгоритм Невилла . Стоимость составляет O ( n ² ) операций, в то время как гауссовское исключение стоит O ( n ³ ) операций. Кроме того, вам нужно выполнить O ( n ) дополнительной работы, только если к набору данных добавлена ​​дополнительная точка, тогда как для других методов вам придется повторить все вычисления.

Другой метод - использовать форму Лагранжа интерполяционного полинома. Полученная формула сразу показывает, что интерполяционный полином существует при условиях, сформулированных в приведенной выше теореме. Формула Лагранжа предпочтительнее формулы Вандермонда, когда нас интересует не вычисление коэффициентов многочлена, а вычисление значения p ( x ) в заданном x, а не в исходном наборе данных. В этом случае мы можем снизить сложность до O ( n ² ).

Форма Бернштейна была использована в конструктивном доказательстве теоремы Вейерштрассы аппроксимации по Бернштейн и приобрела большое значение в компьютерной графике в виде кривых Безье .

Линейная комбинация заданных значений

Форма Лагранжа интерполяционного полинома представляет собой линейную комбинацию заданных значений. Во многих сценариях эффективная и удобная полиномиальная интерполяция представляет собой линейную комбинацию заданных значений с использованием ранее известных коэффициентов. Учитывая набор точек данных, где каждая точка данных является парой (позиция, значение) и где нет двух одинаковых позиций , полином интерполяции в форме Лагранжа представляет собой линейную комбинацию${\ displaystyle k + 1}$${\ Displaystyle (x_ {0}, y_ {0}), \ ldots, (x_ {j}, y_ {j}), \ ldots, (x_ {k}, y_ {k})}$${\ displaystyle x_ {j}}$

${\ Displaystyle у (х): = \ сумма _ {j = 0} ^ {k} y_ {j} c_ {j} (x)}$

данных значений с каждым коэффициентом, полученным путем оценки соответствующего базисного полинома Лагранжа с использованием данных позиций . ${\ displaystyle y_ {j}}$${\ displaystyle c_ {j} (x)}$${\ displaystyle k + 1}$${\ displaystyle x_ {j}}$

${\ displaystyle c_ {j} (x) = \ ell _ {j} (x, x_ {0}, x_ {1}, \ ldots, x_ {k}): = \ prod _ {\ begin {smallmatrix} 0 \ leq m \ leq k \\ m \ neq j \ end {smallmatrix}} {\ frac {x-x_ {m}} {x_ {j} -x_ {m}}} = {\ 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_ {k})} {( x_ {j} -x_ {k})}}.}$

Каждый коэффициент в линейной комбинации зависит от заданных позиций и желаемой позиции , но не от заданных значений . Для каждого коэффициента вставка значений заданных позиций и упрощение дает выражение , которое зависит только от . Таким образом, одни и те же выражения коэффициентов могут использоваться в полиномиальной интерполяции заданного второго набора точек данных в тех же заданных положениях , где вторые заданные значения отличаются от первых заданных значений . Используя те же выражения коэффициентов, что и для первого набора точек данных, полином интерполяции второго набора точек данных представляет собой линейную комбинацию ${\ displaystyle c_ {j} (x)}$${\ displaystyle x_ {j}}$${\ displaystyle x}$${\ displaystyle y_ {j}}$${\ displaystyle x_ {j}}$${\ displaystyle c_ {j} (x)}$${\ displaystyle x}$${\ displaystyle c_ {j} (x)}$${\ displaystyle k + 1}$${\ displaystyle (x_ {0}, v_ {0}), \ ldots, (x_ {j}, v_ {j}), \ ldots, (x_ {k}, v_ {k})}$${\ displaystyle x_ {j}}$${\ displaystyle v_ {j}}$${\ displaystyle y_ {j}}$${\ displaystyle c_ {j} (x)}$

${\ displaystyle v (x): = \ sum _ {j = 0} ^ {k} v_ {j} c_ {j} (x).}$

Для каждого коэффициента в линейной комбинации выражение, полученное на основе базисного полинома Лагранжа, зависит только от относительных промежутков между данными позициями, а не от индивидуального значения любой позиции. Таким образом, те же выражения коэффициентов можно использовать в полиномиальной интерполяции заданного третьего набора точек данных. ${\ displaystyle c_ {j} (x)}$${\ displaystyle \ ell _ {j} (x, x_ {0}, x_ {1}, \ ldots, x_ {k})}$${\ displaystyle c_ {j} (x)}$${\ displaystyle k + 1}$

${\ displaystyle (t_ {0}, w_ {0}), \ ldots, (t_ {j}, w_ {j}), \ ldots, (t_ {k}, w_ {k})}$

где каждая позиция связана с соответствующей позицией в первом наборе, а желаемые позиции связаны посредством , для постоянного масштабного коэффициента a и постоянного сдвига b для всех позиций. Используя те же выражения коэффициентов, что и для первого набора точек данных, полином интерполяции третьего набора точек данных представляет собой линейную комбинацию ${\ displaystyle t_ {j}}$${\ displaystyle x_ {j}}$${\ displaystyle t_ {i} = ax_ {i} + b}$${\ displaystyle t = ax + b}$${\ Displaystyle c_ {j} (т)}$

${\ displaystyle w (t): = \ sum _ {j = 0} ^ {k} w_ {j} c_ {j} (t).}$

Во многих приложениях полиномиальной интерполяции заданный набор точек данных находится в равноотстоящих позициях. В этом случае может быть удобно определить ось x позиций так, чтобы . Например, данный набор из 3 -х равномерно разнесенных точек данных затем . ${\ displaystyle k + 1}$${\ displaystyle x_ {i} = i}$${\ displaystyle (x_ {0}, y_ {0}), (x_ {1}, y_ {1}), (x_ {2}, y_ {2})}$${\ displaystyle (0, y_ {0}), (1, y_ {1}), (2, y_ {2})}$

Интерполяционный полином в форме Лагранжа представляет собой линейную комбинацию

${\ displaystyle {\ begin {align} y (x): = \ sum _ {j = 0} ^ {2} y_ {j} c_ {j} (x) = y_ {0} {\ frac {(x- 1) (x-2)} {(0-1) (0-2)}} + y_ {1} {\ frac {(x-0) (x-2)} {(1-0) (1- 2)}} + y_ {2} {\ frac {(x-0) (x-1)} {(2-0) (2-1)}} \\ = y_ {0} {\ frac {(x -1) (x-2)} {2}} + y_ {1} {\ frac {(x-0) (x-2)} {- 1}} + y_ {2} {\ frac {(x- 0) (x-1)} {2}}. \ End {выравнивается}}}$

Эта квадратичная интерполяция действительна для любой позиции x , рядом или далеко от данных позиций. Итак, учитывая 3 равноотстоящих точки данных при определении квадратичного полинома, в примерном желаемом положении , интерполированное значение после упрощения задается следующим образом:${\ Displaystyle х = 0,1,2}$${\ displaystyle x = 1,5}$${\ displaystyle y (1.5) = y_ {1.5} = (- y_ {0} + 6y_ {1} + 3y_ {2}) / 8}$

Это квадратичная интерполяция, обычно используемая в многосеточном методе. Опять же, учитывая 3 равноотстоящих точки данных при определении квадратичного многочлена, в следующей равноотстоящей позиции интерполированное значение после упрощения дается следующим образом: ${\ Displaystyle х = 0,1,2}$${\ displaystyle x = 3}$

${\ displaystyle y (3) = y_ {3} = y_ {0} -3y_ {1} + 3y_ {2}.}$

В приведенных выше полиномиальных интерполяциях с использованием линейной комбинации заданных значений коэффициенты определялись с использованием метода Лагранжа. В некоторых сценариях коэффициенты легче определить с помощью других методов. Примеры приведены ниже.

В соответствии с методом конечных разностей , для любого многочлена степени г или менее, любая последовательность значений в равномерно распределенных позициях имеет ю разницу в точности равна 0. Элемент сек _{D +-} из биномиального преобразования является таким я разность. Здесь исследуется эта территория. Биномиальное преобразование , Т , из последовательности значений { v _п }, является последовательностью { ы _п } определяется ${\ displaystyle d + 2}$${\ displaystyle (d + 1)}$${\ displaystyle (d + 1)}$

${\ displaystyle s_ {n} = \ sum _ {k = 0} ^ {n} (- 1) ^ {k} {n \ choose k} v_ {k}.}$

Игнорируя знаковый член , коэффициенты элемента s _n являются соответствующими элементами строки n Треугольника Паскаля. Треугольник биномиальных коэффициентов преобразования , как треугольник Паскаля. Запись в n- й строке и k- м столбце треугольника BTC предназначена для любого неотрицательного целого числа n и любого целого числа k от 0 до n . Это приводит к следующему примеру строк с n  = 0 по n  = 7, сверху вниз, для треугольника BTC: ${\ displaystyle (-1) ^ {k}}$${\ displaystyle n + 1}$${\ displaystyle n + 1}$${\ Displaystyle (-1) ^ {к} {\ tbinom {п} {к}}}$

								1									Ряд n = 0
							1		−1								Строка n = 1 или d = 0
						1		−2		1							Ряд n = 2 или d = 1
					1		−3		3		−1						Ряд n = 3 или d = 2
				1		−4		6		−4		1					Ряд n = 4 или d = 3
			1		−5		10		−10		5		−1				Ряд n = 5 или d = 4
		1		−6		15		−20		15		−6		1			Ряд n = 6 или d = 5
	1		−7		21 год		−35		35 год		−21		7		−1		Ряд n = 7 или d = 6

Для удобства каждая строка n приведенного выше примера треугольника BTC также имеет метку . Таким образом, для любого полинома степени d или меньше любая последовательность значений в равноотстоящих позициях имеет результат линейной комбинации 0 при использовании элементов строки d в качестве соответствующих линейных коэффициентов. ${\ displaystyle d = n-1}$${\ displaystyle d + 2}$${\ displaystyle d + 2}$

Например, 4 равноотстоящих точки данных квадратного полинома подчиняются линейному уравнению, заданному строкой треугольника BTC. Это то же линейное уравнение, которое получено выше с использованием метода Лагранжа. ${\ displaystyle d = 2}$${\ displaystyle 0 = y_ {0} -3y_ {1} + 3y_ {2} -y_ {3}}$

Треугольник BTC также можно использовать для получения других полиномиальных интерполяций. Например, приведенная выше квадратичная интерполяция

${\ displaystyle y (1.5) = y_ {1.5} = (- y_ {0} + 6y_ {1} + 3y_ {2}) / 8}$

можно получить за 3 простых шага следующим образом. Равно разнесенные точки квадратичного многочлена подчиняются строкам треугольника BTC со знаком или выше. Во-первых, строка охватывает заданные и желаемые точки данных с помощью линейного уравнения ${\ displaystyle d = 2}$${\ displaystyle d = 3}$${\ displaystyle y_ {0}, y_ {1}, y_ {1.5}, y_ {2}}$

${\ displaystyle 0 = 1y_ {0} -4y_ {0,5} + 6y_ {1} -4y_ {1.5} + 1y_ {2}}$

Во-вторых, нежелательная точка данных заменяется выражением с точки зрения требуемых точек данных. Строка представляет собой линейное уравнение с членом , который дает член путем умножения обеих сторон линейного уравнения на 4. В- третьих, два вышеуказанных линейных уравнения складываются, чтобы получить линейное уравнение, эквивалентное приведенной выше квадратичной интерполяции для .${\ displaystyle y_ {0,5}}$${\ displaystyle d = 2}$${\ displaystyle 1y_ {0,5}}$${\ displaystyle 4y_ {0,5}}$${\ displaystyle 0 = 1y_ {0,5} -3y_ {1} + 3y_ {1,5} -1y_ {2} = 4y_ {0,5} -12y_ {1} + 12y_ {1,5} -4y_ {2}}$${\ displaystyle y_ {1.5}}$${\ displaystyle 0 = (1 + 0) y_ {0} + (- 4 + 4) y_ {0,5} + (6–12) y_ {1} + (- 4 + 12) y_ {1.5} + (1- 4) y_ {2} = y_ {0} -6y_ {1} + 8y_ {1.5} -3y_ {2}}$

Подобно другим видам использования линейных уравнений, приведенный выше вывод масштабирует и добавляет векторы коэффициентов. В полиномиальной интерполяции как линейной комбинации значений элементы вектора соответствуют непрерывной последовательности регулярно расположенных позиций. В р ненулевых элементов вектора являются р коэффициентами линейного уравнения повиновались любой последовательностью р точек данных от любой степени d многочлена на любой рассто нии регулярно сетку, где д отмечаются индексом вектора. Для любого вектора коэффициентов подчиняется нижний индекс . При добавлении векторов с различными значениями нижнего индекса самый нижний индекс применяется к результирующему вектору. Итак, начиная с вектора строки и вектора строки треугольника BTC, приведенная выше квадратичная интерполяция для вычисляется векторным вычислением. ${\ displaystyle d \ leq p-2}$${\ displaystyle d = 3}$${\ displaystyle d = 2}$${\ displaystyle y_ {1.5}}$

${\ displaystyle (1, -4,6, -4,1) _ {3} +4 (0,1, -3,3, -1) _ {2} = (1,0, -6, + 8 , -3) _ {2}}$

Точно так же кубическая интерполяция, типичная для многосеточного метода ,

${\ displaystyle y_ {1.5} = (- y_ {0} + 9y_ {1} + 9y_ {2} -y_ {3}) / 16,}$

может быть получен путем вычисления вектора, начиная с вектора строки и вектора строки треугольника BTC. ${\ displaystyle d = 5}$${\ displaystyle d = 3}$

${\ displaystyle (1, -6,15, -20,15, -6,1) _ {5} +6 (0,1, -4,6, -4,1,0) _ {3} = ( 1,0, -9,16, -9,0,1) _ {3}}$

Ошибка интерполяции

При интерполяции заданной функции f полиномом степени n в узлах x ₀ , ..., x _n мы получаем ошибку

${\ displaystyle f (x) -p_ {n} (x) = f [x_ {0}, \ ldots, x_ {n}, x] \ prod _ {i = 0} ^ {n} (x-x_ { я})}$

где

${\ displaystyle f [x_ {0}, \ ldots, x_ {n}, x]}$

- обозначение разделенных разностей .

Если F является п + 1 раз непрерывно дифференцируемых на отрезке I и есть многочлен степени не выше п , который интерполирует F в п + 1 различных точек { х _я } ( я = 0,1, ..., п) в этого интервала, то для каждого x в интервале существует ξ в этом интервале, такое что ${\ Displaystyle p_ {п} (х)}$

${\ displaystyle f (x) -p_ {n} (x) = {\ frac {f ^ {(n + 1)} (\ xi)} {(n + 1)!}} \ prod _ {i = 0 } ^ {n} (x-x_ {i}).}$

Приведенная выше граница ошибки предлагает выбрать точки интерполяции x _i так, чтобы произведение было как можно меньше. Эти узлы Чебышева достижения этой цели. ${\ Displaystyle \ влево | \ прод (х-х_ {я}) \ вправо |,}$

Доказательство

Установите срок ошибки как

${\ Displaystyle R_ {п} (х) = е (х) -p_ {п} (х)}$

и настроить вспомогательную функцию:

${\ Displaystyle Y (t) = R_ {n} (t) - {\ frac {R_ {n} (x)} {W (x)}} W (t)}$

где

${\ Displaystyle W (т) = \ прод _ {я = 0} ^ {п} (т-х_ {я})}$

Поскольку x _i являются корнями и , имеем Y ( x ) = Y ( x _i ) = 0 , что означает, что Y имеет не менее n + 2 корня. Из теоремы Ролля , имеет по крайней мере п + 1 корней, то есть по крайней мере один корень £ , где ξ находится в интервале I . ${\ Displaystyle R_ {п} (т)}$${\ Displaystyle W (т)}$${\ Displaystyle Y ^ {\ prime} (т)}$${\ Displaystyle Y ^ {(п + 1)} (т)}$

Итак, мы можем получить

${\ displaystyle Y ^ {(n + 1)} (t) = R_ {n} ^ {(n + 1)} (t) - {\ frac {R_ {n} (x)} {W (x)} } \ (n + 1)!}$

Поскольку - многочлен степени не выше n , то ${\ Displaystyle p_ {п} (х)}$

${\ Displaystyle R_ {п} ^ {(п + 1)} (т) = е ^ {(п + 1)} (т)}$

Таким образом

${\ displaystyle Y ^ {(n + 1)} (t) = f ^ {(n + 1)} (t) - {\ frac {R_ {n} (x)} {W (x)}} \ ( п + 1)!}$

Поскольку ξ является корнем , поэтому ${\ Displaystyle Y ^ {(п + 1)} (т)}$

${\ Displaystyle Y ^ {(n + 1)} (\ xi) = f ^ {(n + 1)} (\ xi) - {\ frac {R_ {n} (x)} {W (x)}} \ (п + 1)! = 0}$

Следовательно,

${\ Displaystyle R_ {n} (x) = f (x) -p_ {n} (x) = {\ frac {f ^ {(n + 1)} (\ xi)} {(n + 1)!} } \ prod _ {i = 0} ^ {n} (x-x_ {i})}$.

Таким образом, остаточный член в форме Лагранжа теоремы Тейлора является частным случаем ошибки интерполяции, когда все узлы интерполяции x _i идентичны. Обратите внимание, что ошибка будет равна нулю, если для любого i . Таким образом, максимальная ошибка произойдет в некоторый момент в интервале между двумя последовательными узлами. ${\ displaystyle x = x_ {i}}$

Для равномерных интервалов

В случае равноотстоящих узлов интерполяции, где , для и где член произведения в формуле ошибки интерполяции может быть ограничен как ${\ displaystyle x_ {i} = a + ih}$${\ Displaystyle я = 0,1, \ ldots, п,}$${\ Displaystyle ч = (ба) / п,}$

${\ displaystyle \ left | \ prod _ {i = 0} ^ {n} (x-x_ {i}) \ right | = \ prod _ {i = 0} ^ {n} \ left | x-x_ {i } \ right | \ leq {\ frac {n!} {4}} h ^ {n + 1}}$.

Таким образом, граница ошибки может быть задана как

${\ displaystyle \ left | R_ {n} (x) \ right | \ leq {\ frac {h ^ {n + 1}} {4 (n + 1)}} \ max _ {\ xi \ in [a, b]} \ left | f ^ {(n + 1)} (\ xi) \ right |}$

Однако, это предполагает , что доминирует , то есть . В некоторых случаях это неверно, и ошибка фактически увеличивается при n → ∞ (см . Феномен Рунге ). Этот вопрос рассматривается в разделе « Свойства сходимости» . ${\ Displaystyle е ^ {(п + 1)} (\ хи)}$${\ displaystyle h ^ {n + 1}}$${\ Displaystyle е ^ {(п + 1)} (\ хи) час ^ {п + 1} \ ll 1}$

Константы Лебега

Смотрите основную статью: Константа Лебега .

Зафиксируем узлы интерполяции x ₀ , ..., x _n и интервал [ a , b ], содержащий все узлы интерполяции. Процесс интерполяции отображает функцию f в многочлен p . Это определяет отображение X из пространства C ([ a , b ]) всех непрерывных функций на [ a , b ] в себя. Отображение X линейно и является проекцией на подпространство Π _n многочленов степени n или меньше.

Константа Лебега L определяется как операторной норме от X . Имеется (частный случай леммы Лебега ):

${\ Displaystyle \ | FX (е) \ | \ Leq (L + 1) \ | fp ^ {*} \ |.}$

Другими словами, полином интерполяции не более чем на коэффициент ( L  + 1) хуже, чем наилучшее возможное приближение. Это говорит о том, что мы ищем набор узлов интерполяции, который делает L маленьким. В частности, для чебышевских узлов :

${\ displaystyle L \ leq {\ frac {2} {\ pi}} \ log (n + 1) +1.}$

Мы снова заключаем, что узлы Чебышева - очень хороший выбор для полиномиальной интерполяции, так как рост n экспоненциальный для равноотстоящих узлов. Однако эти узлы не оптимальны.

Свойства сходимости

Естественно спросить, для каких классов функций и для каких узлов интерполяции последовательность интерполирующих многочленов сходится к интерполированной функции при n → ∞ ? Сходимость можно понимать по-разному, например поточечную, равномерную или по некоторой интегральной норме.

Ситуация довольно плохая для равноудаленных узлов, поскольку равномерная сходимость не гарантируется даже для бесконечно дифференцируемых функций. Одним из классических примеров, предложенных Карлом Рунге , является функция f ( x ) = 1 / (1 + x ² ) на интервале [−5, 5] . Ошибка интерполяции || f - p _n || _{∞ неограниченно} растет при n → ∞ . Другой пример - функция f ( x ) = | х | на интервале [−1, 1] , для которого интерполирующие многочлены даже не сходятся поточечно, за исключением трех точек x = ± 1, 0.

Можно подумать, что лучшие свойства сходимости можно получить, выбирая разные узлы интерполяции. Следующий результат, кажется, дает довольно обнадеживающий ответ:

Теорема. Для любой функции f ( x ), непрерывной на интервале [ a , b ], существует таблица узлов, для которой последовательность интерполирующих многочленов сходится к f ( x ) равномерно на [ a , b ].${\ Displaystyle p_ {п} (х)}$

Доказательство . Ясно, что последовательность полиномов наилучшего приближения сходится к f ( x ) равномерно (в силу аппроксимационной теоремы Вейерштрасса ). Теперь нам осталось только показать, что каждый из них может быть получен путем интерполяции на определенных узлах. Но это верно из-за особого свойства полиномов наилучшего приближения, известного из теоремы о равных колебаниях . В частности, мы знаем, что такие многочлены должны пересекать f ( x ) не менее n + 1 раз. Выбирая точки пересечения в качестве узлов интерполяции, мы получаем интерполирующий полином, совпадающий с полиномом наилучшего приближения. ${\ Displaystyle р_ {п} ^ {*} (х)}$${\ Displaystyle р_ {п} ^ {*} (х)}$

Однако недостатком этого метода является то, что узлы интерполяции должны вычисляться заново для каждой новой функции f ( x ), но алгоритм трудно реализовать численно. Существует ли единая таблица узлов, для которой последовательность интерполирующих полиномов сходится к любой непрерывной функции f ( x )? К сожалению, ответ отрицательный:

Теорема. Для любой таблицы узлов существует непрерывная функция f ( x ) на интервале [ a , b ], для которой последовательность интерполирующих многочленов расходится на [ a , b ].

Доказательство существенно использует оценку снизу константы Лебега, которую мы определили выше как операторную норму X _n (где X _n - оператор проекции на Π _n ). Теперь ищем таблицу узлов, для которых

${\ displaystyle \ lim _ {n \ to \ infty} X_ {n} f = f, {\ text {для каждого}} f \ in C ([a, b]).}$

По теореме Банаха – Штейнгауза это возможно только в том случае, если нормы X _n равномерно ограничены, что не может быть истинным, поскольку мы знаем, что

${\ displaystyle \ | X_ {n} \ | \ geq {\ tfrac {2} {\ pi}} \ log (n + 1) + C.}$

Например, если в качестве узлов интерполяции выбраны эквидистантные точки, функция из явления Рунге демонстрирует расхождение такой интерполяции. Отметим, что эта функция не только непрерывна, но даже бесконечно дифференцируема на [−1, 1] . Однако для лучших чебышевских узлов такой пример найти гораздо сложнее из-за следующего результата:

Теорема. Для любой абсолютно непрерывной функции на [−1, 1] последовательность интерполяционных многочленов, построенная на узлах Чебышева, сходится к  f ( x ) равномерно.

Связанные понятия

Феномен Рунге показывает, что для высоких значений n полином интерполяции может сильно колебаться между точками данных. Эта проблема обычно решается с помощью сплайн-интерполяции . Здесь интерполянт - не полином, а сплайн : цепочка из нескольких полиномов более низкой степени.

Интерполяция периодических функций с помощью гармонических функций осуществляется с помощью преобразования Фурье . Это можно рассматривать как форму полиномиальной интерполяции с гармоническими базовыми функциями, см. Тригонометрическую интерполяцию и тригонометрический полином .

Задачи интерполяции Эрмита - это те, в которых заданы не только значения полинома p в узлах, но и все производные до заданного порядка. Это оказывается эквивалентным системе одновременных полиномиальных сравнений и может быть решено с помощью китайской теоремы об остатках для многочленов. Интерполяция Биркгофа - это дальнейшее обобщение, в котором предписаны только производные некоторых порядков, а не обязательно всех порядков от 0 до k .

Методы коллокации для решения дифференциальных и интегральных уравнений основаны на полиномиальной интерполяции.

Техника моделирования рациональных функций - это обобщение, которое рассматривает отношения полиномиальных функций.

Наконец, многомерная интерполяция для более высоких измерений.

Смотрите также

• Серия Ньютон
• Полиномиальная регрессия

Заметки

Рекомендации

• Бернштейн, Сергей Н. (1912). «Сюр лорд де ля мейлер приближение функций продолжается par les polynômes de degré donné» [О порядке наилучшего приближения непрерывных функций полиномами заданной степени]. Mem. Акад. Рой. Бельг. (На французском). 4 : 1–104.
• Фабер, Георг (1914). "Über die interpolatorische Darstellung stetiger Funktionen" [Об интерполяции непрерывных функций]. Deutsche Math. Яр. (на немецком). 23 : 192–210.
• Уотсон, Дж. Алистер (1980). Теория приближений и численные методы . Джон Вили. ISBN 0-471-27706-1.

дальнейшее чтение

• Аткинсон, Кенделл А. (1988). "Глава 3.". Введение в численный анализ (2-е изд.). Джон Уайли и сыновья. ISBN 0-471-50023-2.
• Брутман, Л. (1997). «Функции Лебега для полиномиальной интерполяции - обзор». Аня. Нумер. Математика . 4 : 111–127.
• Пауэлл, MJD (1981). "Глава 4". Теория и методы приближения . Издательство Кембриджского университета. ISBN 0-521-29514-9.
• Шацман, Мишель (2002). "Глава 4". Численный анализ: математическое введение . Оксфорд: Clarendon Press. ISBN 0-19-850279-6.
• Сули, Эндре ; Майерс, Дэвид (2003). "Глава 6". Введение в численный анализ . Издательство Кембриджского университета. ISBN 0-521-00794-1.

Внешние ссылки

• "Процесс интерполяции" , Энциклопедия математики , EMS Press , 2001 [1994]
• ALGLIB имеет реализации на C ++ / C #.
• GSL имеет код полиномиальной интерполяции в C
• Демонстрация полиномиальной интерполяции .