Глава1. Проблема аппроксимации

Глава1. Проблема аппроксимации

 

Полиномиальная апппроксимация

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

Из теорем математического анализа известно, что всякая непрерывная на отрезке [a;b] функция f(x) может быть хорошо приближена полиномом P_n(x).

Теорема Вейерштрасса:

Однако эта теорема не дает ответа на вопрос о существовании хорошего интерполяционного полинома для заданного множества точек {(x_i, y_i)}.

x	x0	…	xn
y	y0	…	yn

Пусть функция f(x) известна только в узлах некоторой сетки x_i, т.е. задана таблицей: (x_k≤x_k+1)

 

 

Задача нахождения значений функции:

a) между узлами () – задача интерполяции

б) вне узлов () – задача экстраполяции

Теорема:

Для всякой дискретной функции f(x), заданной предыдущей таблицей существует многочлен P_n(x) степени n, совпадающий в узлах с этой функцией (P_n(x_k)=y_k ) и он единственен. (1)

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

Будем искать этот полином в виде: P_n(x)=a₀+a₁x+..+a_nxⁿ.

Запишем условие (1) в виде системы:

(2)

Будем считать, что все узлы – разные, т.е x_k< x_k+1.

В данной системе неизвестные – a_k. Определитель системы – отличный от нуля определитель Вандермонда:

Т.о. решение системы (2) существует, а значит существует многочлен P_n(x).

Докажем его единственность. Предположим противное: существует Q_n(x):

. Тогда полином P_n(x)-Q_n(x) равен 0 в (n+1) точке P_n(x)-Q_n(x)≡0 P_n(x)≡Q_n(x). Что и требовалось доказать.

 

Определение Полином P_n(x) – интеполяционный полином для функции f(x).

 

Пример Рунге Рассмотрим функцию f(x)= .

т.е. является аналитической функцией.

 

Рассмотрим на [-1;1] ее интерполяционный многочлен

(для значений по равномерным узлам): P_n(x_k)= .

C возрастанием n многочлен также возрастает,

увеличивая аксиляции колебаний.

 

 

Интерполяционный полином в форме Лагранжа

Из системы (2) получим систему следующего вида:

(3)

Будем считать неизвестными a₀,a₁..a_n, -1.

Полученная система имеет (n+1) порядок. Ее нетривиальное решение из предыдущей теоремы существует, следовательно, ее определитель равен 0 (иначе решение (3) было бы нулевым).

Разложим этот определитель по последнему столбцу:

где - многочлены n-ой степени, .

 

 

Перпишем последнее равенство в виде:

где .

 

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

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

2)

3)

Следовательно, многочлен определяется единственным образом.

Рассмотрим следующий многочлен (n+1)ой степени:

Обозначим .

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

Т.о. = , т.е. интерполяционный полином имеет вид:

- интерполяционный полином Лагранжа

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

Представим функцию f(x) в виде: f(x)=P_n(x)+R_n(x), где R_n(x) – погрешность интерполяции. Заметим, что R_n(x) зависит от свойств f(x) (так если f(x) линейна, то R_n(x)≡0 при n>2).

Будем считать априорно, что а

Запишем погрешность в виде: R_n(x)=kω_n+1(x)+φ(x).

Тогда φ(x)=f(x)-P_n(x)- kω_n+1(x) и φ(x_k)=0, . (4)

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

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

При таком выборе k φ(x’) и обращается в ноль в (n+2) точках: x₀…x_n,x’.

Тогда по т. Ролля обращается в ноль в по крайней мере (n+1) точке. И т.д.

По т. Ролля имеет хотя бы один нуль. Т.е.

Т.о. из (4) получим:

.

Тогда , а значит , т.к. точка x’ была выбрана произвольно.

 

Интерполяционный полином в форме Ньютона

Рассматривается функция f(х), заданная дискретно в узлах х₀...х_n. Ставится задача её аппроксимации по этим данным.

Введём понятие разделённых разностей:

1-ого порядка -

2-ого порядка -

k-ого порядка -

нулевого порядка -

 

Тогда:

,

 

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

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

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

 

Обозначим все слагаемые, кроме последнего как Р_n(х), последнее - R_n(х).

Р_n(х) – интерполяционный полином (т.к. он порядка n и совпадает в узлах с f(х)) Ньютона.

Следствие:

Аппроксимация сплайнами

Рассматривается задача приближения функции f(х) на некотором интервале по её значениям в узлах х₀...х_n (х_k< х_k+1

Кусочно-линейная функция, совпадающая в узлах с f(х) – линейный сплайн.

Обозначим разбиение {x₀…x_n} как Т.

 

Сплайн порядка m для функции f(х) по разбиению Т – кусочно-полиномиальная функция, если:

1) на каждом из отрезков [x_k-1, x_k] это многочлен m-ого порядка

2) в узлах совпадает с функцией f(х):

3) во внутренних узлах (х₁...х_n-1) эта функция непрерывна вместе со своими производными до (m-1)-ого порядка .

 

Построение сплайна

Обозначим многочлен, который необходимо найти на [x_k-1, x_k] как:

(m+1 коэффициент).

Из условия 2) для сплайна => (n+1) уравнение.

Из условия 3) => (n-1) уравнение для каждой из m функций.

Итого всего уравнений для сплайна: n+1+m(n-1)=n(m+1)+1-m

Всего неизвестных коэффициентов (m+1) для каждого из n отрезков, т.е. n(m+1).

Таким образом, число уравнений и искомых коэффициентов совпадает при m=1, иначе условий не хватает для нахождения коэффициентов, и требуются дополнительные условия.

 

Основные сплайны:

- 1-ого порядка – линейные;

- 2-ого порядка – кубические (m=3).

Для них 4n-2 уравнения и 4n коэффициентов.

В качестве двух дополнительных условий обычно задают значения производных в двух узлах.

Таким образом, функция f(х) может быть интерполирована на [x₀, x_n] сплайном заданного порядка.

 

 

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

Рассмотрим некоторую функцию . В полиномиальной аппроксимации она приближается по значениям в узлах х₀...х_n линейной комбинацией степеней х_k (полиномом k-ой степени).

Таким образом, функцию f(х) на [a,b], заданную в узлах х₀...х_n можно аппроксимировать некоторыми функциями φ_k(k), общее число которых (р+1), р≠n.

Рассмотрим некоторые употребляемые частные случаи:

1) Полиномиальная задача: найти для функции f(х) такую линейную комбинацию функций φ_k: что их разность в некотором определенном смысле минимальна (в случае полиномиальной аппроксимации разность рассматривается в узлах).

Рассмотрим следующее выражение:

Необходимое условие минимума функции

Таким образом, получим следующую систему уравнений:

 

 

Или:

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

Обозначим

Необходимое условие экстремума имеет вид:

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

Или:

т.к. - скалярное произведение φ_m на φ_k в L₂ (а, b), то:

Определитель с матрицей А=(а_km), где а_km= (φ_k, φ_m) – определитель Грамма.

 

Заметим, что det А≠0, если система линейно независима, следовательно, наилучшее средне квадратичное приближение существует и притом единственно.

Рассмотрим подпространство (натянутое на функции φ₀...φ_р в пространстве L₂ (а, b)).

- проекция f(х) на В_р+1. Приэтом она существует единственно, если φ_k линейно независима.

 

 

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

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

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

Отсюда, (1)

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

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

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

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

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

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

Тогда, по Т. Ролля φ⁽ⁿ⁺¹⁾(х) имеет хотя бы один нуль.

Т.е. существует g=g(х'): φ⁽ⁿ⁺¹⁾(g)=0.

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

Отсюда,

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

 

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

Обозначим:

Р_n(x)=P_n(x,A), где А=(а₀, а₁...а_n).

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

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

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

В системе n+2 неизвестных: h, а₀, а₁...а_n.

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

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

а) sgn Δ₀=sgn Δ₁

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

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

в х₂, х₃...х_n+1

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

б) sgn Δ₁ = sgn Δ₂

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

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

в х₀, х₃...х_n+1

Отсюда, sgn q₁(x₁)=sgn q₁(x₂). И т.д.

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

 

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

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

Определить:

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

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

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

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

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

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

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

.

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

При этом:

.

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

 

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

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

 

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

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

 

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

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

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

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

 

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

 

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

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

При n=1:

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

При n=2:

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

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

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

 

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

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

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

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

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

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

а - нечетная.

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

 

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

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

.

Обозначим .

Тогда .

Т.к. .

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

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

 

Экстремумы.

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

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

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

n·arccosx = πk,

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

Отсюда, .

Т.к. .

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

 

 

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

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

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

Обозначим

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

Лемма

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

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

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

.

 

Обозначим как Q_n(x) = T_n(x)-P_n(x).

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

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

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

 

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

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

 

 

Погрешность

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

 

Пусть значения функции известны с малой точностью ε. Ответим на вопрос: останется ли в решении исходной задачи хотьо один достоверный знак. Рассмотрим приближенное равенство: . При этом для достаточно гладких функций (погрешность первого порядка).

 

ρ определяет погрешность метода и неограниченно убывает при h→0. Но есть и неустранимая погрешность, связанная с погрешностью при вычислении функции f(x): . Она неограниченно возрастает при h→0.

Таким образом, полная погрешность не превосходит . А значит, оптимальным будет шаг метода, соответствующий минимуму g(h).

 

Меньший шаг невыгоден, а меньшая погрешность недостихима. Эта минимальная ошибка тем меньше, чем меньше погрешность входных данных.

 

 

Ортогональные матрицы

Ортогональные матрицы

Рассмотрим два ортонормированных базиса в пространстве Rⁿ: . Т.е. .

Разложим вектора второго базиса по векторам первого:

Обозначим как U=(u_ik).

Рассмотрим скалярное произведение:

Таким образом, сумма C_ik трактуется как произведение iой строки матрицы U на kый столбец матрицы U^T. C другой стороны, из свойств ортонормированного базиса матрица C=(c_ik)=E.

Отсюда получим: UU^T=E или U^TU=E.

 

Из выведенных формул следуют равенства:

1) U^-1 = U^T (из определения обратной матрицы)

2) (Ux,Uy) = (x,y) для любых векторов x,y из Rⁿ (т.е. скалярные произведения векторов и их образов относительно U совпадают).

Действительно, (Ux,Uy) = (UU^Tx,y) = (x,y)

3) Отсюда в частности следует: || x || = || Ux ||

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

 

Матрица V, удовлетворяющая любому из этих трех равенств, ортогональная. Она обладает следующими свойствами:

1) переводит ортогональный базис в ортонормиррованный

2) сохраняет углы между векторами, а также их нормы

 

Первый шаг

Пусть λ₁ – максимальное собственное число матрицы А, т.е. .

Обозначим как y¹ – собственный вектор матрицы А, отвечающий λ₁: || y¹ ||=1.

Второй шаг

Обозначим как L_n-1 – подпространство, ортогональное подпространству, образованному вектором y¹ (т.к. dim {y¹}=1, то dim L_n-1=n-1).

 

Очевидно, что L_n-1 инвариантное подпространство для А (т.е. если , то ).

Действительно, пусть

Обозначим . Тогда из Леммы 2:

.

Т.о. y² – собственный вектор матрицы А, ортогональный y¹.

 

Третий шаг

Будем рассматривать далее подпространство , повторим указанные в шаге два рассуждения.

 

В итоге получим набор собственных векторов матрицы А {y^k}: || y^k ||=1, ортогональных друг другу, соответствующих собственным числам {λ_k}.

Обозначим матрицу собственных векторов как:

.

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

Очевидно, что У – ортогональная матрица, т.к. ее столбцы нормированны и ортогональны друг другу.

Тогда запишем систему в виде: Y^TAY=diag(λ₁… λ_n) или A=Ydiag(λ₁… λ_n)Y^T.

Геометрически это означает, что:

Всякая симметричная матрица может быть приведена к диагональному виду, т.е. в некотором базисе соответствующий оператор представляется диагональной матрицей, а значит его действие состоит в растягивании на величину λ_к соответствующего базисного вектора. Базис состоит из собственных векторов, т.е. диагональная матрица нетривиальна.

 

 

Сопряженная матрица

Рассмотрим вещественную матрицу A=(a_ij). Тогда сопряженная к ней в пространстве Rⁿ матрица: A*=(a*_ij)=A^T.

В пространстве Rⁿ A – линейный оператор; А* - сопряженный к нему.

Образ Im A – область значений оператора А: Im A= A(Rⁿ).

Ядро ker A – множество элементов, обращаемых оператором А в ноль:

ker A={x | Ax=0}.

Im A, ker A – подпространства пространства Rⁿ.

Задача: доказать указанное выше утверждение.

 

Лемма .

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

Im A – подпространство пространства Rⁿ. Обозначим как L его ортогональное дополнение (множество всех элементов из Rⁿ, ортогональных каждому элементу из Im A). Тогда . Докажем, что L=ker A.

Т.е. .

Т.е. .

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

 

 

Частная спектральная задача

Частная спектральная задача – задача нахождения некоторых собственных чисел матрицы и соответствующих собственных векторов.

 

Вариационный метод

Пусть А – симметричная матрица. Найдем её максимальное собственное число. Т.к. из ранее доказанного , то задача сводится к нахождению стационарных точек функционала .

Степенной метод

Для матрицы А предположим, что:

а) её собственные вектора φ₁… φ_n образуют базис в Rⁿ.

б) её собственные числа удовлетворяют неравенствам | λ₁ |>| λ_k|, k=2..n.

Тогда всякий вектор х из Rⁿ может быть представим в виде: .

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

x⁽¹⁾=Ax, x⁽²⁾=Ax⁽¹⁾…x^(m)=Ax^(m-1)=A^mx.

Значит, . Преобразуем правую часть равенства:

при m>>1,

т.к. тогда .

Получим, что:

,

а - соответствующий собственный вектор

(т.к. он определяется с точностью до скалярного множителя).

Знак λ₁ найдем из следующего равенства:

- знак находится по первой компоненте.

Точность метода: .

 

 

Метод максимизации столбцов

Пусть A=(a_kp) – вещственная, квадратная матрица порядка n.

Обозначим как a_p – pый столбец матрицы.

Заметим, что ; .

 

Рассмотрим матрицу простого поворота U_p:

u₁₁ = u_pp= c =cosα, -u_p1 = u_1p= -s = - sinα, остальные диагональные элементы равны 1, а недиагональные – нулю. Из ранее доказанного матрица U_p осуществляет поворот на угол α против часовой стрелки.

 

Главное собственное число

 

Пусть А=(a_ij) – симметричная матрица. Метод максимизации столбцов дает следующее:

Перемножим равенства:

максимальное собственное число матрицы A² (из метода максимизации).

λ=±b – главное собственное число симметричной матрицы А.

 

 

Метод вращения

Рассмотрим симметричную матрицу А=(а_ij). Обозначим ортогональную матрицу вращения U_pq(α):

u_qq = u_pp= c =cosα, -u_pq = u_qp= -s = - sinα, остальные диагональные элементы равны 1, а недиагональные – нулю.

Рассморим вращение матрицы в плоскости O_pq:

Матрица В=AU_pq отличается от А столбцами b_p и b_q:

b_p=c·a_p+s·a_q

b_q= -s·a_p+c·a_q

b_j=a_j, j≠p,q

Матрица отличается от В р-ой и q-ой строками:

d_pj=c·b_pj+s·b_qj

d_qj= -s·b_pj+c·b_qj

Остальные строки не изменяют.

Тогда,

Разобьем S на диагональную и недиагональную части:

Заметим:

При элементарном вращении D недиагональные элементы а_pi, a_qi и а_ip, a_iq (i≠p,q) меняются так, что попарные суммы квадратов их модулей сохраняются.

Кроме этих элементов вне диагонали меняется элемент а_pq.

Т.е. величина S₂ меняется при элементарном вращении настолько, насколько изменится |a_pq|².

Будем подбирать вращения так, чтобы S₂ максимально уменьшалась.

Положим d_pq=0:

d_pq=c·b_pq+s·b_qq=c(-s·a_pp+c·a_pq)+s(-s·a_{q p}+c·a_qq)=

α выберем следующим образом:

1) при а_pp cos2α=0 => α=π/4

2) иначе

 

 

Глава1. Проблема аппроксимации