- •Глава1. Проблема аппроксимации
- •§1. Полиномиальная апппроксимация
- •§2. Интерполяционный полином в форме Лагранжа
- •§3. Интерполяционный полином в форме Ньютона
- •§4. Аппроксимация сплайнами
- •§5. Метод наименьших квадратов
- •§6. Полиномиальная интерполяция с кратными узлами
- •§7. Свойства разделенных разностей
- •§8. Задача Чебышева. Разрешимость системы
- •§9. Теорема Чебышева
- •§10. Многочлены Чебышева
- •Глава2. Численное дифференцирование
- •Глава3. Численное интегрирование
- •§1. Интерполяционные квадратурные формулы
- •1.Интерполяционные квадратурные формулы
- •2.Интерполяционные квадратурные формулы наилучшей алгебраической точности
- •3.Ортогональные многочлены и их свойства
- •§2. Применение квадратурных формул
- •§3. Метод Монте-Карло (метод статистических испытаний)
- •§4. Правило Рунге практической оценки погрешности
- •Глава4. Алгебраическая проблема собсвенных значений
- •§1. Ортогональные матрицы
- •1.Ортогональные матрицы
- •2.Матрица элементарного поворота
- •§2. Вариационное свойство собственных значений
- •§3. Приведение симметричной матрицы к диагональному виду
- •§4. Сингулярное разложение матрицы
- •§5. Сопряженная матрица
- •§6. Частная спектральная задача
- •1.Вариационный метод
- •2.Степенной метод
- •§7. Метод максимизации столбцов
- •1.Максимизация первого столбца
- •2.Алгоритм сингулярного разложения
- •3.Главное собственное число
- •§8. Метод вращения
Глава1. Проблема аппроксимации
§1. Полиномиальная апппроксимация
Постановка задачи
Из теорем математического анализа известно, что всякая непрерывная на отрезке [a;b] функция f(x) может быть хорошо приближена полиномом Pn(x).
Теорема Вейерштрасса:
Однако эта теорема не дает ответа на вопрос о существовании хорошего интерполяционного полинома для заданного множества точек {( xi , yi )}.
x |
x0 |
… |
xn |
y |
y0 |
… |
yn |
Задача нахождения значений функции:
a) между узлами ( ) – задача интерполяции
б) вне узлов ( ) – задача экстраполяции
Теорема:
Для всякой дискретной функции f(x), заданной предыдущей таблицей существует многочлен Pn(x) степени n, совпадающий в узлах с этой функцией (Pn(xk)=yk ) и он единственен. (1)
Доказательство
Будем искать этот полином в виде: Pn(x)=a0+a1x+..+anxn.
Запишем условие (1) в виде системы:
(2)
Будем считать, что все узлы – разные, т.е xk< xk+1.
В данной системе неизвестные – ak. Определитель системы – отличный от нуля определитель Вандермонда:
Т.о. решение системы (2) существует, а значит существует многочлен Pn(x).
Докажем его единственность. Предположим противное: существует Qn(x):
. Тогда полином Pn(x)-Qn(x) равен 0 в (n+1) точке Pn(x)-Qn(x)≡0 Pn(x)≡Qn(x). Что и требовалось доказать.
Определение Полином Pn(x) – интеполяционный полином для функции f(x).
П ример Рунге Рассмотрим функцию f(x)= .
т.е. является аналитической функцией.
Рассмотрим на [-1;1] ее интерполяционный многочлен
(для значений по равномерным узлам): Pn(xk)= .
C возрастанием n многочлен также возрастает,
увеличивая аксиляции колебаний.
§2. Интерполяционный полином в форме Лагранжа
Из системы (2) получим систему следующего вида:
(3)
Будем считать неизвестными a0,a1..an , -1.
Полученная система имеет (n+1) порядок. Ее нетривиальное решение из предыдущей теоремы существует, следовательно, ее определитель равен 0 (иначе решение (3) было бы нулевым).
Разложим этот определитель по последнему столбцу:
где - многочлены n-ой степени, .
Перпишем последнее равенство в виде:
где .
Заметим, что:
1) - многочлен n-ой степени
2)
3)
Следовательно, многочлен определяется единственным образом.
Рассмотрим следующий многочлен (n+1)ой степени:
Обозначим .
Заметим, что:
Т.о. = , т.е. интерполяционный полином имеет вид:
- интерполяционный полином Лагранжа
Погрешность интерполяции
Представим функцию f(x) в виде: f(x)=Pn(x)+Rn(x), где Rn(x) – погрешность интерполяции. Заметим, что Rn(x) зависит от свойств f(x) (так если f(x) линейна, то Rn(x)≡0 при n>2).
Будем считать априорно, что а
Запишем погрешность в виде: Rn(x)=kωn+1(x)+φ(x).
Тогда φ(x)=f(x)-Pn(x)- kωn+1(x) и φ(xk)=0, . (4)
Выберем k из условия φ(x’)=0, где x’ – точка, в которой оценивается погрешность:
Из уравнения φ(x’)=0 получим: .
При таком выборе k φ(x’) и обращается в ноль в (n+2) точках: x0…xn,x’.
Тогда по т. Ролля обращается в ноль в по крайней мере (n+1) точке. И т.д.
По т. Ролля имеет хотя бы один нуль. Т.е.
Т.о. из (4) получим:
.
Тогда , а значит , т.к. точка x’ была выбрана произвольно.