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

ЛЕКЦИЯ №9

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

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

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

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

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

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

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

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

n=0: T₀(x)=cos0=1;

n=1: T₁(x)=cos(arccos x)=x;

n=2: T₂(x) =cos(2arccos x);

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

T_n(x)=cos2α ;

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

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

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

T_n+1(x)+ T_n-1(x)=2 T₁(x) T_n(x);

T_n+1(x)= 2xT_n(x)- T_n-1(x); (9.2)

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

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

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

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

Проверим:

T₂(x) =2х²-1

T₃(x) =2х (2х²-1) =4х³-2х

T₄(x) = 2х (4х³-3х)-2х²+1=2³х⁴-3х²+1

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

Докажем:

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

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

T_n(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), т.е ошибку аппроксимации.

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

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

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

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

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

Связь: x= Ct+D

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

Если t=1

Если t=-1

Тогда:

(9.4)

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

t_kÎ[-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] найдется полином Q_n(x), что |f(x)- Р_n(x)| < ξ для любой ξ>0 , любое хÎ[a;b].

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

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

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

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

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

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

ЛЕКЦИЯ №10,11

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

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

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

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

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

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

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

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

Необходимо: φ(x_i)=y_i=f(x_i),

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

Определим a_i и b_i.

x=x₀: φ(x₀)=f(x₀)=y₀ a₁x₀+b₁=y₀

x=x₁: φ(x₁)=f(x₁)=y₁ a₁x₁+b₁=y₁

a₂x₁+b₂=y₁

x₀ x₁ x₂

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

а₀x₀+b₁=y₀ (решаем по отдельности каждую систему)

a₂x₁+b₂=y₁

a₂x₁+b₂=y₁

a₂x₂+b₂=y₂ (10.2)

a_nx_n-1+b_n=y_n

a_nx_n +b_n= y_n

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

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

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

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

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

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

.

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

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

k=1

[x₀;x₂]

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

(10.4)

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

можем построить систему линейных уравнений для a_k,b_k,c_k;

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