Содержание
Введение
Интерполяция многочленами
Методы интерполяции Лагранжа и Ньютона
Сплайн-аппроксимация
Метод наименьших квадратов
Полиномы Чебышева
Практическое задание
Введение
Допустим, задана функция 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,x1,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
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, на котором система чебышевских многочленов Tn (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 в первом случае спускаясь,а во втором поднимаясь, проводим преобразование коэффициентов по следующим формулам:
а) a k =a k /2
б) a k-2 =a k-2 +a k
с) a 0 =2 a 0
В результате получаем коэффициенты полинома Т n (x). Интереснобыло бы узнать, какую ошибку мы получаем при разложении степенной функции по полиномамЧебышева. Для этого, используя выше описанные алгоритмы, мы сначала представляемфункцию y = x n (где n берем от 1 до 10) через полиномы Чебышева (T n), а затем,чтобы оценить ошибку, чебышевское разложение снова превращаем в многочлен. Выполнивэти операции, мы получаем очень необычные результаты. Для нечётных n ошибка настолькомала, что её едва можно различить на графиках. Для чётных же степеней мы можем наблюдатьсмещение графика, полученного в результате преобразования, вниз относительно оригинала.Это можно объяснить следующим образом. За смещение графика несёт ответственностькоэффициент перед x 0. Вспомним алгоритмы, они построены так, что каждый предыдущийкоэффициент вычисляется через последующий. В результате накапливающаяся ошибка вычислениябольше всего влияет на коэффициент при x 0. Следствием этого является смещение графиковчётных степеней, так как в их разложении присутствует этот коэффициент. Можно отметитьтакже, что смещение при разложении функции y = x 2 больше, чем при разложении функцииy = x 10. Этот тоже можно легко объяснить, так как при увеличении степени вкладT 0 в разложении степенной функции значительно уменьшается. Что же будет, если коснутьсянечётных степеней. Тогда мы получим такое хорошее совпадение, так как чётные коэффициентыв разложении нечётных степеней равны 0, а коэффициенты при всех степенях x, кроменулевой, влияют только на отклонение ветвей. Подтверждением этого служат графики
Следующим этапом работы являлось приближение полиномами Чебышевапроизвольной функции. В качестве начальной функции мы взяли функцию y = sin (4 x/3). Используемая в работе программа имела нижеприведенный алгоритм:
Приближение функции f (x) по Чебышеву
Задаём степень n многочлена T n (x) и пределы [a; b] измененияаргумента функции f (x)
Для i =0, 1, …, n на отрезке [-1; 1] формируем сетку оптимальныхзначений аргумента в узлах чебышевской интерполяции:
Переводим в отрезок [a; b]: и вычисляем f (x i)
Для k =0, 1, …, n и i =0, 1, …, n вычисляем:
В результате получаем коэффициенты a 0, a 1, …, a n многочлена T (), приближающего функцию f (x)
Вычисление значений T (x) выполняется по следующему алгоритму:
Считая заданным массив a k, необходимо задать память под массивиз n +2 вспомогательных коэффициентов b k. Полагаем b n +2 =0, b n +1 =0
Задаём значения x на [a; b] и переводим их в отрезок [-1; 1]с помощью преобразований:
Для k = n, n — 1, …, 1 вычисляем b k = a k — b k +2 +2 xb k +1
Находим T () =a 0 /2 — b 2 +xb 1
Также в программе было использовано разложение в ряд Тейлорадля сравнения с разложением по полиномам Чебышева. Прежде всего, было рассмотреноприближение на интервале [-1; 1]. Наложив на график sin (4 x /3) график его приближенияполиномами Чебышева и график, построенный с помощью разложения в ряд Тейлора, получаемочень точное совпадение. Визуально невозможно различить три кривых. Рассматриваемграфик ошибок. В соответствии с теорией ошибка Чебышева знакопеременна и распределенаболее или менее равномерно по всему интервалу. Ошибка же Тейлора небольшая около0 и сильно увеличивается при приближении к 1 (заметим, что в этом и в других случаяхряд Тейлора содержит те же степени x, но с иными коэффициентами). Наиболее интереснорассмотреть приближение на более длинных интервалах. На интервале [-1; 1] приближениеполиномами Чебышева седьмой степени достаточно хорошее, но уже на интервале [-10;10] приближение этой же степенью очень плохое. Рассмотрим приближение на этом жеинтервале полиномом более высокой степени (T 11). Получим достаточно неплохое приближение,причём на графике очень отчётливо видно, что ошибка распределена равномерно. Здесьопять хочется сравнить с разложением в ряд Тейлора. Если посмотреть на графики,мы увидим, что приближение с помощью рядов Тейлора очень хорошее в середине интервала,но имеет сильное отклонение от эталона на концах. Сравним ошибки чебышевского приближенияи приближения с помощью рядов Тейлора. При таком сравнении ясно проявляются свойстваполиномов Чебышева — максимальная ошибка меньше, чем при использовании ряда Тейлора
В итоге, мы получили, что на большом интервале хорошее приближениеможно построить только, используя достаточно большие степени. В действительности,трудно представить себе приближение нескольких периодов синуса с помощью полиномов3-й, 4-й, 5-й степеней, и тем более — невозможно 1-й и 2-й степени
Полиномы Чебышева дают великолепное приближение функции в томсмысле, что максимальная ошибка этого приближения очень мала, но эти приближениядостаточно сложно вычисляются. Обычно относительно малое уменьшение ошибки не стоиттого труда, который необходимо потратить на нахождение этого приближения. Именнопоэтому полиномы Чебышева используют для корректировки разложения в ряд Тейлора.Нахождение исправленных коэффициентов не составляет особой сложности, поэтому этотметод, называемый экономизацией степенного ряда легко может применяться для повседневногопрограммирования.