Содержание
Введение
Интерполяция многочленами
Методы интерполяции Лагранжа и Ньютона
Сплайн-аппроксимация
Метод наименьших квадратов
Полиномы Чебышева
Практическое задание
Допустим, задана функция y (x), это означает, что любому допустимому значению х сопоставлено значение у. Но иногда оказывается, что найти это значение очень трудно. Например, у (х) может быть определено как решение сложной задачи, в которой х играет роль параметра или у (х) измеряется в дорогостоящем эксперименте. В этом случае можно вычислить небольшую таблицу значений функции, но прямое нахождение этой функции при большом числе значений аргумента будет практически невозможно. Функция у (х) может существовать в каких-нибудь физико-технических или математических расчётах, где её необходимо будет многократно вычислять. В этой ситуации удобно заменить функцию у (х) приближённой формулой, то есть подобрать некоторую функцию j (х), которая приближается в некотором смысле к у (х) и просто вычисляется. Затем при всех значениях аргумента полагать, что у (х)" j (х)
Основная часть классического численного анализа основывается на приближении многочленами, потому как с ними легче работать. Однако для большинства целей используются другие классы функций.
Выбрав значимые точки и класс приближающих функций, нам необходимо ещё выбрать одну определённую функцию из этого класса посредством какого-то критерия - некоторой меры приближения или "равенства". До того как начать вычисления, мы должны решить также, какую точность нам надо в ответе и какой критерий мы выбираем для измерения этой точности
Всё изложенное выше можно сформулировать в виде четырёх вопросов:
Какие значимые точки мы будем использовать?
Какой класс приближающих функций будет нами использован?
Какой критерий согласия-"равенства" мы применим?
Какая точность нам необходима?
Существуют три группы функций, которые широко применяемых в численном анализе. Первая группа включает в себя линейные комбинации функций 1, х, х 2, …, х n, что совпадает с классом всех многочленов степени n (или меньше). Второй класс - включает в себя функции cos a i x, sin a i x. Этот класс имеет непосредственное отношение к рядам Фурье и интегралу Фурье. Третья группа образована функциями e - az. Эти функции часто встречаются в реальных ситуациях, к ним, например, часто приводят задачи накопления и распада. Что касается критерия согласия или "равенства", то классическим критерием согласия является "точное совпадение в значимых - узловых точках". Этот критерий обладает преимуществами простоты теории и выполнения вычислений, но он также имеет неудобство из-за игнорирования шума (погрешности, возникающей при измерении или вычислении значений в значимых (узловых) точках). Другой достаточно хороший критерий - есть "наименьшие квадраты". Это означает, что сумма квадратов отклонений в узловых точках должна быть наименьшей возможной или, другими словами, приведена к минимуму. Этот критерий использует неточную информацию, чтобы получить наименьшее количество шума. Третий критерий напрямую связан с именем Чебышева. Основная идея его заключается в том, чтобы привести максимальное отклонение к минимуму. Конечно, могут быть возможны и другие критерии
Более точно ответить на поставленные нами четыре вопроса можно лишь исходя из условий и цели каждой задачи в отдельности.
Цель задачи о приближении (интерполяции): данную функцию у (х) необходимо приблизительно заменить некоторой функцией j (х), свойства которой нам известны так, чтобы отклонение в заданной области было минимальным. Интерполяционные формулы применяются, в первую очередь, при замене графически заданной функции аналитической, а также для интерполяции в таблицах
Один из подходов к задаче интерполяции - метод Лагранжа. Идея этого метода является в том, чтобы в первую очередь найти многочлен, который принимает значение 1 в одной узловой точке и 0 во всех остальных. Легко можно увидеть, что функция является требуемым многочленом степени n, который равен 1, если x = x j и 0, когда x = x i, i № j. Многочлен L j (x) Ч y j принимает значения y i в i - й узловой точке и равен 0 во всех других узлах. Из чего следует, что имеется многочлен степени n, проходящий через n +1 точку (x i, y i)
Другой подход - метод Ньютона (метод разделённых разностей). Этим методом можно получить аппроксимирующие значения функции без построения в явном виде аппроксимирующего полинома. В результате чего получаем формулу для полинома P n, аппроксимирующую функцию f (x):
P (x) =P (x 0) + (x-x 0) P (x 0,x 1) + (x-x 0) (x-x 1) P (x 0,x 1,x 2) +…+
(x-x 0) (x-x 1) … (x - x n) P (x 0,x 1,…, x n);
разделённая разность 1-го порядка;
разделённая разность 2-го порядка и т. д
Значения P n (x) в узлах совпадают со значениями f (x)
Фактически формулы Лагранжа и Ньютона порождают один и тот же полином, разница является только в алгоритме его построения
Ещё один метод аппроксимации - сплайн-аппроксимация - отличается от полиномиальной аппроксимации Лагранжем и Ньютоном. Сплайном называется функция, которая вместе с несколькими производными непрерывна на отрезке [a, b], а на каждом частном интервале этого отрезка [x i, x i +1] в отдельности являются некоторым многочленом невысокой степени. В настоящее время используют кубический сплайн, то есть на каждом локальном интервале функция приближается к полиному третьего порядка. Трудности такой аппроксимации связаны с низкой степенью полинома, поэтому сплайн плохо аппроксимируется с большой первой производной. Сплайновая интерполяция может напоминать лагранжевую тем, что требует только значения в узлах, но не её производных
Допустим, что требуется заменить некоторую величину и делается n измерений, результаты которых равны x i = x + e i (i =1, 2, …, n), где e i - это ошибки (или шум) измерений, а х - истинное значение. Метод наименьших квадратов утверждает, что наилучшее приближённое значение есть такое число, для которого минимальна сумма квадратов отклонений от:
Один из наиболее частых случаев применения этого метода заключается в том, что имеющиеся n наблюдений (x i, y i) (i =1, 2, …, n) требуется приблизить многочленом степени m < n
y (x) =a 0 +a 1 x+a 2 x 2 +…+ a m x m
Вычисленная кривая у (х) в некотором смысле создаёт сложное множество значений у i. Метод наименьших квадратов утверждает, что следует выбирать многочлен, который приводит функцию к минимуму
Для нахождения минимума дифференцируем � по каждой из неизвестных a k. В результате получим:
Определитель этой системы отличен от нуля и задача имеет единственное решение. Но система степеней не ортогональна, и при больших значениях n задача плохо обусловлена.
Эту трудность можно обойти, используя многочлены ортогональные с заданным весом на заданной системе точек, но к этому прибегают только в задачах, связанных с особенно тщательной статической обработкой эксперимента
Критерии согласия данного метода - минимизация максимальной ошибки Полиномы Чебышева определяются следующим образом: T n (x) = cos (n Ч arccos (x))
Например: T 0 (x) = cos (0) =1,T 1 (x) = cos (q) = x,
T 2 (x) = cos (2 q) =cos 2 (q) - sin 2 (q) =2x 2 - 1
Можно было бы и дальше использовать тригонометрические соотношения для нахождения полиномов Чебышева любого порядка, но будет лучше установить для них рекурентное соотношение, связывающее T n +1 (x), T n (x) и T n - 1 (x):
T n+1 (x) = cos (n q + q) = cos (n q) cos (q) - sin (n q) sin (q),
T n-1 (x) = cos (n q - q) = cos (n q) cos (q) - sin (n q) sin (q)
Складывая эти неравенства, получим:
T n +1 (x) + T n - 1 (x) =2 cos (n q) cos (q) =2 xT n (x);
T n+1 (x) =2xT n (x) - T n-1 (x)
Применяя полученные формулы можно найти любой полином Чебышева. Например, Т 3 (x) =2 xT 2 (x) - T 1 (x). Подставляя значения T 2 (х) и Т 1 (х) имеем Т 3 (х) =2х (2х 2 - 1) - х=4х 3 - 3х. Графически первые 10 полиномов Чебышева изображены ниже. Последующие полиномы по-прежнему колеблются между +1 и - 1, причём период колебания уменьшаются с ростом порядка полинома
Преобразования q = arccos (x) можно рассмотреть как проекцию пересечений полукруга с множеством прямых, имеющих углы равные между собой (рис.1). Таким образом, множество точек x j, на котором система чебышевских многочленов T n (x) ортогональна, есть:
(j =0, 1, 2, …, N - 1)
Так как T n (x) есть, по существу, cos (n q), то они являются равноколеблющимися функциями, и так как они многочлены, то обладают всеми свойствами, которые имеют ортогональные многочлены
Чебышев доказал, что из всех многочленов Р n (x) степени n старшим коэффициентом 1, у многочлена точная верхняя грань абсолютных значений на интервале - 1 Ј x Ј 1 наименьшая. Так как верхняя грань T n (x) =1, указанная верхняя грань равна
На практике нам необходимо было изучить приближение нашей функции полиномами Тейлора.
Как уже упоминалось выше, многочлены Тейлора легко вычисляются, а так же превращаются в степенные ряды. В этом нам удалось убедится на практике.
Ниже приведена таблица коэффициентов первых двенадцати полиномов Чебышева, а также таблица коэффициентов перед полиномами Чебышева, выражающие первые двенадцать степеней.
Эти данные мы получили, используя программы на страницах.
В этих программах были использованы следующие алгоритмы: Преобразование коэффициентов полинома Чебышева в коэффициенты традиционного многочлена.
Вводим коэффициенты a 0, a 1, …, a n многочлена T (x) и образуем массив a i. Для j =2, 3, …, n и k = n, n - 1, …, j в первом случае поднимаясь, а во втором спускаясь, осуществляем преобразование коэффициентов по следующим формулам:
а) a k-1 =a k-2 - a k
б) a k =2a k
В результате получаем коэффициенты полинома P n (x)
Преобразование коэффициентов полинома P n (x) в коэффициенты полинома T n (x)
Вводим коэффициенты полинома P n (x) - а i.
Для j = n, n - 1, …, 2 и k = j, j +1, …, n в первом случае спускаясь, а во втором поднимаясь, проводим преобразование коэффициентов по следующим формулам: