Смекни!
smekni.com

Численные методы 6 (стр. 1 из 3)

ЛЕКЦИЯ №9

МНОГОЧЛЕНЫ ЧЕБЫШЕВА

1. Определение и свойства

2. Интерполяция по Чебышевским узлам

3. Многочлены равномерных приближений

4. Экономизация степенных рядов

Многочленом Чебышева n-ой степени называется функция

Tn(x)=cos (narccos) n=0,1,2 …,xÎ[-1;1] ; (9.1)

Докажем, что при любом n=0,1,2

n=0: T0(x)=cos0=1;

n=1: T1(x)=cos(arccos x)=x;

n=2: T2(x) =cos(2arccos x);

Обозначимα=arccosx

Tn(x)=cos2α ;

Tn+1(x)=cos((n+1)α) ;

Tn-1(x)=cos((n-1)α) ;

cos((n+1)α)+ cos((n-1)α)-2cos(2nα/ α)cos(2α/ α)=2 cosnα cosα;

Tn+1(x)+ Tn-1(x)=2 T1(x) Tn(x);

Tn+1(x)= 2xTn(x)- Tn-1(x); (9.2)

Свойства многочлена Чебышева:

1. Все функции Tn(x) являются многочленами при n=0,1,2,…

2. Степени этих многочленов возрастают с увеличением n, причем старший член Tn(x)=2n-1xn

3. Многочлены Tn(x) при четных n выражаются через четные функции , при нечетных n-через нечетные функции.

Проверим:

T2(x) =2х2-1

T3(x) =2х (2х2-1) =4х3-2х

T4(x) = 2х (4х3-3х)-2х2+1=23х4-3х2+1

4. На отрезке [-1;1] многочлен Tn(x) имеет ровно n различных действительных корней, которые рассчитываются по формуле:

Докажем:

Так как arccosxÎ[0; Π];k=0,1,…n-1,чтобы туда попадал arcos

5. Корни многочлена Чебышева перемножаются, чередуются с точками их экстремума, причем максимум

Tn(x) на [-1;1] равен 1,т.е

Для точек экстремума существует связь:

Введем нормированный многочлена Чебышева (старший коэффициент =1, перед х в максимальной степени)

(9.3)

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

Из всех многочленов степени n со старшим коэффициентом = 1, нормированный многочлен Чебышева отклоняется от нуля на отрезке [-1;1] , т.е не существует многочлена Рn *(x), что :

max | Рn*(x)| < max | T^n(x)|

[-1;1][-1;1] Доказательство не нужно.

Интерполяция по Чебышевским узлам

Задача: Пусть есть некоторая функция f(x), определенная на отрезке [a;b]. Как расположить на отрезке [a;b] n+1 узел интерполяции таким образом, чтобы минимизировать максимальное отклонение интерполяционного полинома Лагранжа от f(x), т.е ошибку аппроксимации.

Остаточный член полинома Лагранжа

Необходимо минимизировать этот максимум, т.е необходимо найти такие узлы xk ,

которые минимизировали бы

Сведем [a;b] к отрезку [-1;1]

Должна существовать связь хÎ[a;b] с tÎ[-1;1]

Связь: x= Ct+D

C-коэффициент сжатия (растяжения, D-параллельный перенос)

Если t=1

Если t=-1

Тогда:

(9.4)

Для того чтобы минимизировать (9.4), необходимо найти такие корни

tkÎ[-1;1],

, при котором Πn+1(t) будет минимальным.

По теореме Чебышева полином Тn+1нормирован многочленом Чебышева, наименее отклонен от нуля на [-1;1], поэтому в качестве искомых корней необходимо взять корни многочлена Чебышева на [-1;1]

(рассмотрим полином n+1-ой степени)

(9.5)

Узлы интерполяции, определим по формуле (9.5) обеспечивают min, max ошибку аппроксимации при помощи интерполяционных полиномов.

Многочлены равномерных приближений

Если функция f(x) ∞-но дифференцируема на [a;b] и в качестве узлов интерполяции берутся корни многочленов Чебышева, приведенные к [a;b], то справедливо:

Т.е имеет место равномерная сходимость последовательности интерполяционного полинома Лагранжа функции f(x).

Теорема Вейерштрасса: для любой непрерывной функции f(x) на [a;b] найдется полином Qn(x), что |f(x)- Рn(x)| < ξ для любой ξ>0 , любое хÎ[a;b].

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

К сожалению, общий вид таких полиномов и способы построения не известны.

Экономизация степенных рядов

Ряд Тейлора представляет собой локальную аппроксимацию для f(x) степенной функции вида xn можно заменить многочлен Чебышева и получить разложение по этим многочленам вместо степенного ряда:

Такой процесс называется экономизацией степенного ряда.

Разложение по многочленам Чебышева имеет меньшую максимальную погрешность.

ЛЕКЦИЯ №10,11

ИНТЕРПОЛЯЦИОННЫЕ СПЛАЙНЫ

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

Связано это с тем, что у многочлена n-ой степени может быть n-1 точка экстремума. При n→∞ график многочлена начинает сильно колебаться

Такое явление называют феноменом Рунге.

Поэтому более перспективным является применение кусочно-полиномиальной аппроксимации, при которой аппроксимирующая функция составляется из отдельных многочленов (сплайнов). Каждый из которых (одинаковы и наибольшей степени) определен на своем участке отрезка [a;b].

Рассмотрим аппроксимацию кусочно-линейной функции (линейный сплайн).

Пусть f(x) задана таблично на [a;b], т. е определены некоторые узлы интерполяции a≤x0<x1<…<xn≤b

кусочно-линейная функция

Необходимо: φ(xi)=yi=f(xi),

для приближения функции.

Определим ai и bi.

x=x0: φ(x0)=f(x0)=y0 a1x0+b1=y0

x=x1: φ(x1)=f(x1)=y1 a1x1+b1=y1

a2x1+b2=y1

x0 x1 x2

Получим систему:


а0x0+b1=y0 (решаем по отдельности каждую систему)

a2x1+b2=y1

a2x1+b2=y1

a2x2+b2=y2 (10.2)

anxn-1+bn=yn

anxn +bn= yn

Таким образом, получена система из 2n уравнений для поиска 2n неизвестных. Причем, система (10.2) образована из n систем линейных уравнений для 2-х неизвестных, каждая из которых может решаться независимо от остальных.

Кусочно-линейная функция φ(x) вида (10.1) внутри интервала (хi-1;xi),

непрерывна и дифференцируема, а в точках xi,
непрерывна, но не дифференцируема(в этих точках к графику функции невозможно построить касательную).

Кусочно-квадратичная аппроксимация

Пусть f(x) задана таблично на [a;b], но n=2m (четно) a≤x0<x1<…<xn≤b

Чтобы функция приближала f(x) наложим ограничения φ(xi)=yi=f(xi),

.

Общее число узлов 2n+1, если n-четное.

Для нахождения неизвестных коэффициентов ak,bk,ckнеобходимо построить 3m условий.

k=1

[x0;x2]

Обобщим, получим систему:

(10.4)

Для нахождения неизвестных имеем 3m условий. При каждом значении

можем построить систему линейных уравнений для ak,bk,ck;

Решать ее можем независимо от остальных условий.