- •Глава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. Метод вращения
3.Ортогональные многочлены и их свойства
Многочлены Sn(x), n=0,1… ортогональны на (a;b) с весом q(x)≥0, если:
.
Ортогональные многочлены обладают следующими свойствами:
10. Всякий многочлен Pn(x) может быть представлен в виде , где Ck – коэффициенты разложения.
Доказательство
Докажем существование таких коэффициентов Ck.
Умножим последнее равенствоскалярно на qSm, m=0,1..n. Получим:
Единственность такого разложения следует из построения.
Что и требовалось доказать.
20. Всякий многочлен Pn ортогонален Sm с весом q(x), если n<m.
Доказательство
Пусть n<m.
Из свойства 1 многочлен Pn(x) представим в виде:
.
Умножим скалярно равенство на q(x)Sm(x). Получим: .
Что и требовалось доказать.
30. Sn(x) имеет на [a;b] все n нулей, более того все они – простые.
Доказательство
Предположим, что Sn(x) имеет на [a;b] лишь k<n нулей, которые являются простыми (x1..xk).
Тогда многочлен вида не меняет знак на [a;b], а значит .
С другой стороны, многочлен имеет степень k<n, а значит по свойству 2:
Противоречие доказывает требуемое.
Таким образом, выбирая для квадратурной формулы xk как нули многочлена степени n из некоторой ортогональной системы многочленов на [a;b], получим выполнение условия 2) Теоремы 2 (из свойства 2 ортогональных многочленов). А значит, интерполяционная квадратурная формула становится формулой наилучшей алгебраической точности.
Например, если необходиом найти интеграл на [-1;1], то узлы выгодно рассматривать, равные нулям многочлена Чебышева. Тогда интеграл примет вид:
. Вместо функции f(x) будем рассматривать функцию в квадратурной формуле.
§2. Применение квадратурных формул
Постановка задачи
Т.к. априорно треуется высокая гладкость функции, и вычисление интерполяционного многочлена сложно, а также сложно увеличивать число узлов (т.е. уменьшать шаг), то для вычисления интеграла используется следующий метод.
Отрезок [a;b] разбивается на узлы a=x0<..<xn=b (для простоты шаг h постоянен). Следовательно, исходный интеграл разбивается на сумму интегралов: .
Теперь достаточно построить интерполяционную квадратурную формулу для интеграла на малом отрезке [xk-1;xk], т.е. более низкого порядка m, чем для интеграла по всему отрезку [a;b].
1.Метод прямоугольников (m=0)
На отрезке [xk-1;xk] функция f(x) заменяется по некоторому определенному значению (по f(xk-1) – метод левых; по f(xk) – метод правых; по f((xk + xk-1)/2) – метод cрединных прямоугольников) многочленом P0(x,k).
Р ассмотрим метод левых прямоугольников.
Применяется квадратурная формула:
, где h=xk –xk-1.
Получим общую квадратурную формулу:
Оценим погрешность данного метода. Вообще в задаче алгебраической интерполяции f(x) многочленом Рn(x) погрешность Rn(x) имеет вид O(hn+1)
1) Локальная погрешность аппроксимации
для многочлена Р0(х): R0(x)=O(h1)
2) Локальная погрешность интегрирования
3) Общая погрешность интегрирования
Т.е. метод прямоугольников - первого порядка точности.
2. Метод трапеций (m=1)
Н а отрезке [xk-1;xk] функция f(x) заменяется по значениям в узлах xk-1, xk многочленом P1(x,k).
Общая формула:
Погрешность:
1) O(h2) для Р1(х)
2)
3)
Т.е. метод - второго порядка точности.
3. Метод парабол (m=2)
Н а отрезке [xk-1;xk] функция f(x) аппроксимируется параболой. Для этого берутся значения функции в точках xk-1, xk , (xk + xk-1)/2).
Обозначим интерполяционный полином как P2(x,k).
Тогда:
.
Оценим погрешность данного метода.
1) Локальная погрешность аппроксимации
для многочлена Р2(х): R2(x)=O(h3)
2) Локальная погрешность интегрирования
3) Общая погрешность интегрирования
Т.е. метод прямоугольников - третьего порядка точности.
Коэффициенты a1k, a2k и a3k можно найти, воспользовавшись представлением функции приближенно в виде интерполяционнго многочлена Лагранжа:
.