Содержание
Методы интерполяции Лагранжа и Ньютона
Введение
Допустим, задана функция 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 в первом случае спускаясь, а во втором поднимаясь, проводим преобразование коэффициентов по следующим формулам:
а) 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-й степени
Полиномы Чебышева дают великолепное приближение функции в том смысле, что максимальная ошибка этого приближения очень мала, но эти приближения достаточно сложно вычисляются. Обычно относительно малое уменьшение ошибки не стоит того труда, который необходимо потратить на нахождение этого приближения. Именно поэтому полиномы Чебышева используют для корректировки разложения в ряд Тейлора. Нахождение исправленных коэффициентов не составляет особой сложности, поэтому этот метод, называемый экономизацией степенного ряда легко может применяться для повседневного программирования.