1611688890-f641c9ec8276824e4686da772eb56520 (826652), страница 14
Текст из файла (страница 14)
Очень важное значение имеют,к примеру, разложения функций в ряды по полиномам Чебышёва.2.4Алгебраическая интерполяцияс кратными узламиКратным узлом называют, по определению, узел, в котором информация о функции задаётся более одного раза. Помимо значенияфункции это может быть какая-либо дополнительная информация оней, например, значения производных и т. п. К задаче интерполяции скратными узлами мы приходим, в частности, если степень интерполяционного полинома, который нужно однозначно построить по некоторым узлам, равна либо больше количества этих узлов.Далее задачей алгебраической интерполяции с кратными узламимы будем называть следующую постановку.
Даны несовпадающие точки xi , i = 0, 1, . . . , n, — узлы интерполирования, в которых заданы792.4. Интерполяция с кратными узлами(k)значения yi , k = 0, 1, . . . , Ni − 1, — их принимают интерполируемаяфункции f и её производные f (k) (x). При этом число Ni называюткратностью узла xi .
Требуется построить полином Hm (x) степени m,такой что(k)(k)Hm(xi ) = yi ,i = 0, 1, . . . , n,k = 0, 1, . . . , Ni − 1.(2.40)Иными словами, в узлах xi , i = 0, 1, . . . , n, как сам полином Hm (x), так(k)и все его производные Hm (x) вплоть до заданных порядков (Ni − 1)(k)должны принимать предписанные им значения yi .Теорема 2.4.1 Решение задачи алгебраической интерполяции с кратными узлами при m = N0 +N1 +.
. .+Nn −1 существует и единственно.Доказательство. В канонической форме полином Hm (x) имеет видHm (x) =mXal xl ,l=0и для определения коэффициентов a0 , a1 , . . . , am станем подставлять в′′′(x), . . . , аргументы xi и использо(x), Hmнего и в его производные Hmвать условия (2.40). Получим систему линейных алгебраических уравнений относительно a0 , a1 , . . . , am , в которой число уравнений равноN0 + N1 + . .
. + Nn . При m = N0 + N1 + . . . + Nn − 1 оно совпадает счислом неизвестных, равным m + 1.Обозначим получившуюся систему линейных уравнений какGa = y,(2.41)где G — квадратная (m + 1)×(m + 1)-матрица,a = (a0 , a1 , . . . , am )⊤ ∈ Rm+1 — вектор неизвестныхкоэффициентов интерполяционного полинома,(0) (1)(N −1) (0) (1)(N −1) ⊤y = y0 , y0 , . . . , y0 0 , y1 , y1 , . . . , yn n∈ Rm+1— вектор, составленный из интерполяционных данных (2.40).Матрица G зависит только от узлов x0 , x1 , .
. . , xn , и никак не зависит(k)от данных yi , i = 0, 1, . . . , n, k = 0, 1, . . . , Ni − 1. Хотя эту матрицудаже можно выписать в явном виде, её прямое исследование весьмасложно, и для доказательства Теоремы мы пойдём окольным путём.802. Численные методы анализаДля определения свойств матрицы G рассмотрим однородную систему уравнений, отвечающую нулевой правой части y = 0, т. е.Ga = 0.Вектор правой части y образован значениями интерполируемой функ(k)ции и её производных yi в узлах xi , i = 0, 1, .
. . , n. Однородная си(k)стема Ga = 0 отвечает случаю yi = 0 для всех i = 0, 1, . . . , n иk = 0, 1, . . . , Ni − 1. Каким является вектор решений a этой системы?Если правая часть в (2.41) — нулевая, то это означает, что полиномHm (x) с учётом кратности имеет N0 + N1 + . . .+ Nn = m + 1 корней, т. е.больше, чем его степень. Следовательно, он необходимо равен нулю, асоответствующая однородная линейная система Ga = 0 имеет поэтомулишь нулевое решение a = (a0 , a1 , .
. . , an )⊤ = (0, 0, . . . , 0)⊤ .Итак, линейная комбинация столбцов матрицы G, равная нулю, может быть только трививальной, т. е. с нулевыми коэффициентами. Следовательно, матрица G должна быть неособенной, а потому неоднородная линейная система (2.41) однозначно разрешима при любой правойчасти y. Это и требовалось доказать.Задачу алгебраической интерполяции с кратными узлами в исследуемой нами постановке часто называют также задачей эрмитовой интерполяции, а сам полином Hm (x) решающий эту задачу, называютинтерполяционным полиномом Эрмита.
Использованные при доказательстве Теоремы 2.4.1 рассуждения, в которых построение интерполяционного полинома сводится к решению системы линейных алгебраических уравнений, носят конструктивный характер и позволяют практически решать задачу интерполяции с кратными узлами. Тем не менее, аналогично случаю интерполяции с простыми узлами, желательноиметь аналитическое решение в виде обозримого конечного выражениядля интерполянта.
Он может иметь форму Лагранжа либо форму Ньютона (см. подробности, к примеру, [3, 59]). Наметим способ построенияего лагранжевой формы.Аналогично §2.2б, при фиксированном наборе узлов x0 , x1 , . . . , xnрезультат решения рассматриваемой задачи интерполяции линейно за(0)(1)(N −1)(0)(1)(N −1)висит от значений y0 , y0 , . . . , y0 0 , y1 , y1 , . . . , yn n . Болееточно, если полином P (x) решает задачу интерполяции по значениям(0) (1)(N −1) y = y0 , y0 , . .
. , yn n, а полином Q(x) решает задачу интерпо(0) (1)(N −1) ляции с теми же узлами по значениям z = z0 , z0 , . . . , zn n, то2.4. Интерполяция с кратными узлами81для любых вещественных чисел α и β полином αP (x) + βQ(x) решает(0)(0)(1)задачу интерполяции для значений αy + βz = αy0 + βz0 , αy0 +(1)(Nn −1)(Nn −1) на той же совокупности узлов.βz0 , . . . , αyn+ βznОтмеченное свойство можно также усмотреть из выписанного придоказательстве Теоремы 2.4.1 представления вектора коэффициентовa = (a0 , a1 , . .
. , an )⊤ интерполяционного полинома как решения системы (2.41). Из него следует, что a = G−1 y, т. е. a линейно зависит от(k)вектора данных y, образованного значениями yi , k = 0, 1, . . . , Ni − 1,i = 0, 1, . . . , n.Итак, свойством линейности можно воспользоваться для решениязадачи интерполяции с кратными узлами «по частям», которые удовлетворяют отдельным интерполяционным условиям, а затем собратьэти части воедино. Иными словами, как и в случае интерполированияс простыми узлами, можно представить Hm (x) в виде линейной комбинацииn Ni −1XX(k)Hm (x) =yi · φik (x),i=0 k=0где внешняя сумма берётся по узлам, внутренняя — по порядкам производной, а φik (x) — специальные «базисные» полиномы степени m,удовлетворяющие условиям(0, при i 6= j или k 6= l,(l)φik (xj ) =(2.42)1, при i = j и k = l.У полинома φik (x) в узле xi не равна нулю лишь одна из производных, порядок которой k, тогда как производные всех других порядковзануляются в xi .
Кроме того, полином φik (x) и все его производныеравны нулю во всех остальных узлах. Фактически, полином φik (x) отвечает линейной системе (2.41) с вектор-столбцом правой части y вида(0, . . . , 0, 1, 0, . . . , 0)⊤ , в котором все элементы нулевые за исключениемодного.Каков конкретный вид этих базисных полиномов φik (x)? Перепишем условия (2.42) в виде(l)k = 0, 1, . . . , Ni − 1,(2.43)(l)j = 0, 1, . . .
, i − 1, i + 1, . . . , n,l = 0, 1, . . . , Ni − 1.(2.44)φik (xi ) = δkl ,φik (xj ) = 0,822. Численные методы анализаИз второго условия следует, чтоφik (x) = (x − x0 )N0 . . . (x − xi−1 )Ni−1 (x − xi+1 )Ni+1 . . . (x − xn )Nn Qik (x),где Qik (x) — полином степени Ni − 1. Для его определения привлечёмпервое условие (2.43). И так далее.Мы не будем завершать этого построения, так как дальнейшие выкладки весьма громоздки, а алгоритм нахождения полинома из приведённых рассуждения вполне ясен . .
.Какова погрешность алгебраической интерполяции с кратными узлами?Теорема 2.4.2 Пусть f ∈ Cm+1 [a, b], т. е. функция f непрерывно дифференцируема m + 1 раз на интервале [a, b]. Погрешность Rm (f, x) еёинтерполирования по попарно различным узлам x0 , x1 , . . . , xn ∈ [a, b]с кратностями N0 , N1 , . . . , Nn полиномом Hm (x) степени m приусловии m = N0 + N1 + . . .
+ Nn − 1 может быть представлена в виде nf (m+1) ξ(x) Y(2.45)(x − xi )Ni ,Rm (f, x) = f (x) − Hm (x) =·(m + 1)!i=0где ξ(x) — некоторая точка из ]a, b[ , зависящая от x.Доказательство. Обозначим для удобства через Ω(x) произведениелинейных множителей со степенями из правой части равенства (2.45),т. е.nY(x − xi )Ni .Ω(x) :=i=0Это — аналог функции ωn (x), введённой в §2.2д и широко используемойв различных рассуждениях.Если x = xi для одного из узлов интерполирования, i = 0, 1, . . .
, n,то Rm (f, x) = 0, но в то же время и Ω(x) = 0. Поэтому в (2.45) вкачестве ξ можно взять любую точку из открытого интервала ]a, b[ .Предположим теперь, что точка x из интервала интерполирования[a, b] не совпадает ни с одним из узлов xi , i = 0, 1, . . . , n. Введём вспомогательную функцию переменной zψ(z) := f (z) − Hm (z) − KΩ(z),832.4.
Интерполяция с кратными узламигде при фиксированном x числовая константа K равнаK=f (x) − Hm (x).Ω(x)Функция ψ(z) имеет нули в узлах x0 , x1 , . . . , xn и, кроме того, по построению обращается в нуль при z = x, так что общее число нулей этойфункции равно n + 2. На основании теоремы Ролля можно заключить,что производная ψ ′ (z) обращается в нуль по крайней мере в n + 1 точках, расположенных в интервалах между x, x1 , . . . , xn . Но в узлах x0 ,x1 , . . .
, xn функция ψ(z) имеет нули с кратностями N0 , N1 , . . . , Nn соответственно, и потому в них производная ψ ′ (z) имеет нули кратностиN0 − 1, N1 − 1, . . . , Nn − 1 (нулевая кратность означает отсутствие нуляв узле). Таким образом, всего эта производная ψ ′ (z) имеет с учётомкратности (N0 + N1 + . . . + Nn − n − 1) + (n + 1) = m + 1 нулей на [a, b].Продолжая аналогичные рассуждения, получим, что вторая производная ψ ′′ (z) будет иметь с учётом кратности по крайней мере m нулейна интервале [a, b] и т. д.
При каждом последующем дифференцировании нули у производных функции ψ(z) могут возникать или исчезать,но их суммарная кратность уменьшается всякий раз на единицу. Наконец, (m + 1)-ая производная зануляется на [a, b] хотя бы один раз.Итак, на интервале [a, b] обязательно найдётся по крайней мере однаточка ξ, такая что ψ (m+1) (ξ) = 0. Ноψ (m+1) (z) = f (m+1) (z) − K (m + 1)!,(m+1)поскольку Hm (x) — полином степени m и Hm(z) зануляется, а Ω(z)есть многочлен степени m + 1 со старшим коэффициентом 1. Итак,K =f (m+1) (ξ)(m + 1)!для некоторой точки ξ, зависящей от x. Этим завершается доказательство теоремы.Отметим, что при наличии одного узла кратности m интерполяционный полином Эрмита должен совпасть с полиномом Тейлора, аформула (2.45) превращается в известную формулу остаточного членадля полинома Тейлора.
Если же все узлы интерполяции простые, то(2.45) совпадает с полученной ранее формулой погрешности простойинтерполяции (2.25).842.52. Численные методы анализаОбщие фактыалгебраической интерполяцииКак с теоретической, так и с практической точек зрения интересенвопрос о том, насколько малой может быть сделана погрешность интерполирования при возрастании числа узлов. Вообще, имеет ли местосходимость интерполяционных полиномов к интерполируемой функции при неограниченном возрастании количества узлов?Чтобы строго сформулировать соответствующие вопросы и общиерезультаты о сходимости алгебраических интерполянтов, необходимоформализовать некоторые понятия.Определение 2.5.1 Пусть для интервала [a, b] задана бесконечнаятреугольная матрица узлов (1)x0000 ··· (2)(2) xx100 ··· 0, (3)(3)(3) xx1x20 ··· 0...............такая что в каждой её строке расположены различные точки интер(n)вала [a, b], т.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
