ТОП 10:

Полиномиальная интерполяция с кратными узлами



Пусть дана дискретная функция f(х) в узлах х0, х1...хmkk+1, ). А также заданы значения в узлах для производных функции f(х):

; S=0, 1...Sk-1. Причем

Требуется построить многочлен Qn(х) n-ой степени, совпадающий в узлах со всеми этими значениями, т.е. получим систему:

Интерполяционный многочлен Qn(х) определяется единственным образом. Действительно, предположим, что существует многочлен n-ой степени:

удовлетворяет условиям вышеописанной системы. Тогда их разность удовлетворяет следующим условиям:

Т.е. точки х0...хm – нули многочлена Рn(х) кратности S0...Sm соответственно. Получено: многочлен Рn(х)≠0 степени n имеет n+1 нулей (из кратности). Отсюда, Рn(х)≡0. Противоречие доказывает требуемое.

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

 

Погрешность интерполяции.

Обозначим f(х):=Qn(х)+Rn(х).

Представим погрешность Rn в виде:

Отсюда, (1)

где S=0...Sk-1; φ(хk)=0; k=0, 1...m (т.е. хk – нули кратности S0...Sm соответственно).

Выберем k из условия φ(х')=0, где х' – точка, в которой оценивается погрешность

Из уравнения φ(х')=0 получим:

Будем предполагать, что Тогда при таком выборе К и обращается в ноль в (n+2) точках (считая кратность): х0...хm, х'.

Следовательно, по Т. Ролля φ'(х) обращается в ноль в по крайней мере (n+1) точке.

...........................................................................

Тогда, по Т. Ролля φ(n+1)(х) имеет хотя бы один нуль.

Т.е. существует g=g(х'): φ(n+1)(g)=0.

Из равенства (1) получим:

Отсюда,

Т.к. х' выбрано произвольно, то последнее равенство верно при

 

Свойства разделенных разностей

Пусть задана дискретная функция f(х) в узлах х0...хnk < хk+1), а также её разделенная разность k-ого порядка:

Лемма:Справедливо равенство:

Доказательство(методом математической индукции):

При k=1:

Пусть верность равенства доказана при

Докажем для m-ого порядка:

Рассмотрим слагаемое для f(х1):

Аналогично для остальных слагаемых.

Что и требовалось доказать.

 

Числа αk.Пусть хii+1 при

Обозначим:

Данные числа обладают следующими свойствами:

1. - очевидно

2. Действительно, т.к.

1)

2) Умножим на (-1)n-i. Тогда знак числителя не зависит от i, значит знак каждого слагаемого такой же, отсюда, αi>0.

3.

Действительно:

 

Из ранее доказанной Леммы:

Что и требовалось доказать.

 

Задача Чебышева. Разрешимость системы

Пусть f(х) задана дискретно в узлах х0...хn+1 значениями у0...уn+1 соответственно (хi<xi+1). Требуется построить многочлен Рn(x), наилучшим образом аппроксимирующий в узлах значения функции.

Задача Чебышева.

Обозначим:

Рn(x)=Pn(x,A), где А=(а0, а1...аn).

Необходимо определить μ=inf max |Pn(xk)-yk| и минимизирующий многочлен Pn(x,A), если он существует.

Задачи такого типа называют минимальными.

Предварительно рассмотрим систему:

В системе n+2 неизвестных: h, а0, а1...аn.

Докажем, что определитель системы Δ≠0.

Заметим, что:

а) sgn Δ0=sgn Δ1

Действительно, рассмотрим функцию q0(x):

- многочлен n-ого порядка с нулями

в х2, х3...хn+1

Отсюда, sgn q0(x0)=sgn q0(x1), т.к. точки промежутку знакопостоянства функции.

б) sgn Δ1 = sgn Δ2

Рассмотрим следующую функцию:

- многочлен n-ого порядка с нулями

в х0, х3...хn+1

Отсюда, sgn q1(x1)=sgn q1(x2). И т.д.

Таким образом, получим: Δ≠0, следовательно, решение системы существует. Обозначим его как Pn(x,A*).

 

Теорема Чебышева

Решение задачи Чебышева:

Определить:

минимизирующий многочлен Pn(x,A), если он существует.

Теорема:Такой многочлен сущестует и совпадает с решением системы

т.е. Pn(x,A)=Pn(x,A*).

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

Не ограничивая общности будем считать, что

Если это не так, рассмотрим функцию -f(х) в системе все уравнения умножим на (-1), тогда решением будет многочлен –Pn(x,A*).

Перепишем систему следующим образом:

.

Воспользуемся свойствами чисел αk:

При этом:

.

Однако μ>h, т.к. иначе получим h<h. Значит, μ=h. И для всякого k максимум разницы между Pn(x) и f(x) не может быть меньше.

 

Далее нетрудно доказать, что многочлены Pn(x,A*) и Pn(x,A0) равны.

Что и требовалось доказать.

 

ЗамечаниеМожно рассмотреть континуальный аналог задачи Чебышева. Необходимо найти для и минимизирующий многочлен Pn(x,A0), если он существует.

Этот многочлен есть решение дискретной задачи при некотором наборе узлов.

 

Многочлены Чебышева

Постановка задачи:

Для многочленов Pn(x,A) степени n co старшим коэффициентом, равным 1, требуется определить для и минимизирующий многочлен Pn(x,Amin), если это возможно.

Таким образом, рассматривается задача о многочленах со старшим коэффициентом, равным 1, наименее отклоняющихся от нуля.

 

Рассмотрим многочлены Чебышева:

 

Теорема Tn(x) – многочлены степени n со старшим коэффициентом, равным 1, методом математической индукции.

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

При n=1:

- многочлен 1ой степени.

При n=2:

Пусть утверждение верно . Докажем для n = k.

Заметим, что Tk-1(x) – многочлен степени k-1 по предположению, Tk-2(x) – многочлен степени (k-2). Таким образом, Tk(x) – многочлен степени k со старшим коэффициентом, равным 1.

Что и требовалось доказать.

 

Теорема (свойство четности)Все многочлены T2n(x) являются четными функциями, а T2n+1(x) – нечетными.

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

При n = 0: T0=1 – четная функция; T1=x – нечетная.

Пусть утверждение верно . Докажем его справедливость для n = k.

Заметим, что из предположения T2k-1 – нечетная функция, T2k-2 – четная.

Тогда - четная функция,

а - нечетная.

Что и требовалось доказать.

 

Нули многочленов Чебышева

Заметим, что:

.

Обозначим .

Тогда .

Т.к. .

- нули многочлена Чебышева Tn(x) на [-1;1].

При этом других нулей нет (т.к. многочлен nой степени имеет не более n нулей).

 

Экстремумы.

Рассмотрим локальные экстремумы Тn(x) на [-1;1].

Т.к. то точками экстремума для Тn(х) на [-1;1] будут точки, где

Следовательно, cos(n·arccosx) = ±1

n·arccosx = πk,

Обозначим где

Отсюда, .

Т.к. .

- экстреальные точки для Tn(x) на [-1;1].

 

 

Ортогональность с весом

Функции f(x) и g(x) ортогональны на [a;b] с весом ρ(x), если (ортогональность в смысле Гильбертова пространства L2 [a;b]).

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

Обозначим

Что и требовалось доказать.

Лемма

Tn(x) – многочлены со старшим коэффициентом равным еденице, наименее отклоняющиеся от нуля на [-1;1]. Т.е. если Pn(x) – многочлен степени n со старшим коэффициентом равным единице, то:

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

Предположим противное:

.

 

Обозначим как Qn(x) = Tn(x)-Pn(x).

Заметим, что многочлен Qn(x):

1)имеет (n-1) степень

2) , т.к. из предположения .

 

Таким образом, получено, что между каждыми двумя точками многочлен Qn(x) меняет свой знак. Т.е. многочлен Qn(x), отличный от нуля (т.к. он ≠0 в точках ) имеет n нулей, а значит Qn(x)≡0.

Противоречие доказывает требуемое.

 

 







Последнее изменение этой страницы: 2016-04-26; Нарушение авторского права страницы

infopedia.su Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав. Обратная связь - 3.234.245.125 (0.015 с.)