ЛЕКЦИЯ №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 -1} x_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_n x_n-1 +b_n =y_n

a_n x_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 ;

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

Кусочно- квадратичная φ(x) вида (10.3) внутри интервала (x_{2 n -2} -x_{2 n} ), является непрерывной и дифференцируемой два раза, а в точках x_{2 i}

является непрерывной, но не дифференцируемой.

Определение Сплайна

Пусть на отрезке [a;b] задана некоторая система узлов a ₀ ≤ x ₀ < x ₁ <…< x_n ≤ b

Сплайном S_n ( x ) называется функция, которая определена на [a;b], l раз непрерывна и дифференцируема на нем, при этом на каждом из отрезков

[х_к-1 ; х_к ], к = , представляет собой многочлен степени m.

Разность (m-1) называется дефектом Сплайна (показывает разность между степенью составляющих его многочленов и степенью гладкости общей функции).

Если сплайн построен по некоторой таблично заданной функции f(x) таким образом, что S(х_i )= f(x_i ); x_i , i= - узлы интерполяции, то сплайн называют интерполяционным. Узлы сплайна и узлы интерполяции функции могут не совпадать.

Очевидно, что функция (10.1) является интерполяционным сплайном степени 1, дефекта 1, а кусочно-квадратичная функция (10.3) является интерполяционным сплайном, степени 2, дефекта 2.

Интерполяционный сплайн степени 3, дефекта 1.

Дважды непрерывно – дифференцируемый – сплайн.

Пусть задана табличная функция на [a;b], причем a= χ₀ ≤ χ₁ <…< χ_n =b (узлы сплайна совпадают с узлами интерполяции). Общий вид:

Условия:

1.) g(x_i ) = f(x_i )=y_i , i=

2.) g(x) = c² (дважды дифференцируема) [a;b]

3.) – краевые условия

Для нахождения неизвестных коэффициентов введем функцию

g_n (x) = a_k (x-x_k )³ + b_k (x-x_k )² +c₁ (x-x_k )+d_k , xÎ[ x_{k -1} ;x_k ]

1.) g₁ (x₀ ) = y₀ , g₁ (x₁ ) = y₁ , g₂ (x₂ ) = y₂ ,… g_n (x_n ) = y_n

2.) первое условие (сплайн интерполяционный)

3.)

Краевые условия:

Таким образом, для нахождения 4n неизвестных мы построим 4n условий.

Теорема(10.1). Интерполяционный сплайн вида (10.5) для функции f(x) единственен.

Теорема(10.2). Пусть g(x)- интерполяционный сплайн степени 3 дефекта 1, построенный для функции f(x) С⁴ на отрезке [a;b], тогда для найдется такая константа C>0, что:

|f(x)- g(x)|<C ⁴ , [a ;b],

= max(x_k -x_k-1 ), 1≤ k ≤ n

- максимальное расстояние между узлами интерполяции.

Линейный фильтр

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

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

Квадратичный сплайн дефекта один

Узлы этого сплайна не совпадают с узлами интерполяции функции.

Пусть узлы интерполяции заданы на [a;b]

- узлы сплайна, f(x_i )=y_i

, ,

Для сплайна n+2 узлов

Квадратичный сплайн дефекта 1 имеет вид:

Условия:

1.)

2.) P(x) ÎC'[a;b], первая непрерывная производная во всех точках [a;b]

3.) Краевые условия:

P''(a)=A; P''(b)=B;

A и B- константы и желательно разные;

Чтобы построить сплайн необходимо найти 3n+3 неизвестных коэффициента. С этой целью сформирую функцию:

P_n (x)= a_k ² +b_n +c_k

Условия:

1.) P_i+1 =y_i , i= - n+1 условий

2.) P_k = P_k+1 ,

P'_k =P'_k+1 ,

3.) P₁ =A, P''_{n +1} -B – краевые условия;

Теорема 11.1. Квадр. Сплайн дефекта один, вида (11.1) для функции существует и единственен.

Теорема 11.2 . Пусть функция f(x) дважды непрерывна и дифференцируема на [a;b], а P(x)- сплайн вида (11.1), тогда для , (n- связано с числом узлов интерполяции) такие constc₀ , c₁ , c₂ ; что для из [a;b] выполняются следующие неравенства:

| f(x)-P(x) | ≤ C₀ ∆²

| f '(x)-P' (x)| ≤C∆

| f ''(x)-P'' (x)| ≤C₂

где ∆- максимальное расстояние между узлами интерполяции, т.е ∆= max(x_k -x_{k -1} ) 1≤k≤n

Метод наименьших квадратов

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

2. Типовые способы преобразования нелинейной функции к линейной.

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

4. Ряды и полиномы Фурье с использованием метода наименьших квадратов.

Пусть аппроксимируемая функция представляет собой функции n переменных y= f(x₁ …x_n ), которая задана таблицей своих значений:

информационная матрица

Такие таблицы формируются в ходе эксперимента для реальных объектов, у которых есть одна выходная переменная (отклик), которая зависит от нескольких выходных переменных (факторов).

необходимо аппроксимировать нашу функцию при помощи построения линейной функции (приближающей).

Необходимо построить приближение данной функции f(x₁ …x_n ), заданной инфо - матрицей посредством функции φ (x₁ …x_n )=y, которая должна быть линейной, т.е. ее общий вид:

y= φ (x₁ …x_n )=b₀ +b₁ x₁ +…+b_n x_n (11.2)

b_i – неизвестные коэффициенты (параметры)

Задача аппроксимации состоит в определении b_i .

Каков критерий для выбора этих параметров?

Пусть f(x)-функция одной переменной и точки, в которой она определена, изображены на координатной плоскости.

Проводим прямую, минимизируем сумму квадратов расстояний.

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

Необходимо минимизировать сумму квадратов отклонений аппроксимирующей функции от исходных в заданных точках:

(11.3)

Для данной задачи критерий (11.3) будет иметь вид:

(11.4)

Функция квадратичная, параболоид. Точка, в которой производные частные все будут равны 0

(11.5)

Так как функция (11.4) является квадратичной относительно переменных b_i , то для нахождения ее минимума по этим переменным достаточно решить систему (11.5)

(11.6)

В системе (11.6) каждое уравнение делим на 2 и раскрываем сумму; перенося сумму с частью y_j знак равенства:

(11.7)

Система (11.7) представляет собой СЛАУ относительно b_i и может быть решена одним из известных методов.

Для упрощения записи и решения представим систему (11.7) в матричном виде. Введем матрицы:

Столбец из 1 добавили в U с целью универсализации решений, так как линейную функцию можно представить в виде:

y= b₀ x₀ +b₁ x₁ +…+ b_n x_n , где x₀ =1

(n+1)1

Тогда система (11.7) может быть записана в следующем виде:

[U^T U]B=U^T Y(11.8)

Системы (11.7) и (11.8) называются нормальными. Используя, метод обратной матрицы система (11.8) имеет вид:

B= [U^T U]^-1 U^T Y(11.9)

( 11.9) - метод наименьших квадратов для линейной функции.