Министерство образования и науки Российской Федерации
Федеральное государственное автономное образовательное учреждение высшего образования
«Нижегородский государственный университет им. Н.И. Лобачевского»
Арзамасский филиал
Физико-математический факультет
Кафедра физико-математического образования
Выполнил:
Боровец Д.С.
студент 2 курса
заочной формы обучения,
направление «Физико-математическое
образование»
профиль информатика
Курсовая работа
«Интерполяция и наилучшие приближения».
Руководитель:
к.п.н., доцент
Артюхина М.С.
Арзамас, 2014
Содержание.
Введение …………………………………………………………....................………..3
1. Разделенные разности
2. Интерполяционный многочлен Лагранжа
3Интерполирование по схеме Эйткена
4. Интерполяционный многочлен Ньютона
5Приближение и интерполирование функций,
6 Аппроксимация функций методом наименьших квадратов
Заключение………………....................……………………………………………….19
Список литературы…………………………………………...................……………20
Введение.
Если задана функция y(x), то это означает, что любому допустимому значению х сопоставлено значение у. Но нередко оказывается, что нахождение этого значения очень трудоёмко. Например, у(х) может быть определено как решение сложной задачи, в которой х играет роль параметра или у(х) измеряется в дорогостоящем эксперименте. При этом можно вычислить небольшую таблицу значений функции, но прямое нахождение функции при большом числе значений аргумента будет практически невозможно. Функция у(х) может участвовать в каких-либо физико-технических или чисто математических расчётах, где её приходится многократно вычислять. В этом случае выгодно заменить функцию у(х) приближённой формулой, то есть подобрать некоторую функцию j(х), которая близка в некотором смысле к у(х) и просто вычисляется. Затем при всех значениях аргумента полагают у(х)»j(х).
Большая часть классического численного анализа основывается на приближении многочленами, так как с ними легко работать. Однако для многих целей используются и другие классы функций.
Выбрав узловые точки и класс приближающих функций, мы должны ещё выбрать одну определённую функцию из этого класса посредством некоторого критерия — некоторой меры приближения или «согласия». Прежде чем начать вычисления, мы должны решить также, какую точность мы хотим иметь в ответе и какой критерий мы изберём для измерения этой точности.
Всё изложенное можно сформулировать в виде четырёх вопросов:
· Разделенные разности
· Интерполяционный многочлен Лагранжа
· Интерполяционный многочлен Ньютона
· Аппроксимация функций методом наименьших квадратов
Существуют 3 класса или группы функций, широко применяемых в численном анализе. Первая группа включает в себя линейные комбинации функций 1, х, х2, …, хn, что совпадает с классом всех многочленов степени n (или меньше). Второй класс образуют функции cos aix, sin aix. Этот класс имеет отношение к рядам Фурье и интегралу Фурье. Третья группа образуется функциями e-az. Эти функции встречаются в реальных ситуациях. К ним, например, приводят задачи накопления и распада.
Что касается критерия согласия, то классическим критерием согласия является «точное совпадение в узловых точках». Этот критерий имеет преимущество простоты теории и выполнения вычислений, но также неудобство из-за игнорирования шума (погрешности, возникающей при измерении или вычислении значений в узловых точках). Другой относительно хороший критерий — это «наименьшие квадраты». Он означает, что сумма квадратов отклонений в узловых точках должна быть наименьшей возможной или, другими словами, минимизирована. Этот критерий использует ошибочную информацию, чтобы получить некоторое сглаживание шума. Третий критерий связывается с именем Чебышева. Основная идея его состоит в том, чтобы уменьшить максимальное отклонение до минимума. Очевидно, возможны и другие критерии.
Более конкретно ответить на поставленные 4 вопроса можно лишь исходя из условий и цели каждой отдельной задачи.
1. Разделенные разности
Часто экспериментальные данные функциональной зависимости представляются таблицей, в которой шаг по независимой переменной не постоянен. Для работы с таким представлением функции конечные разности и конечно-разностные операторы не пригодны. В этом случае первостепенную роль играют разделенные разности.
Разделенную разность функции f(x) для некоторых двух точек и определяют следующей дробью:
Для построения степенного многочлена, проходящего через заданные точки, необходимо иметь число точек на единицу больше, чем степень многочлена. Согласно определению разделенной разности число их для n точек равно числу сочетаний из n по 2. Это во много раз больше, чем необходимо для построения кривых, проходящих через n точек. Из опыта работы с конечными разностями видно, что разделенных разностей из всего множества достаточно выбрать всего n, но выбрать так, чтобы в их образование входили все (n+1) точек таблицы.
Вполне разумно вычислять разделенные разности только для соседних значений функции в таблице. В этом случае говорят об упорядоченных разделенных разностях. Аргументу табличной функции присваиваются индексы из чисел натурального ряда, начиная с нуля, в результате чего обозначения разделенных разностей для i-той строки таблицы будут .
Повторная разность от разделенной разности есть разделенная разность второго порядка:
В общем случае разделенная разность n-го порядка имеет вид:
2. Интерполяционный многочлен Лагранжа
Произведения из скобочных сомножителей в знаменателе каждого слагаемого напоминают своим видом некий степенной многочлен от переменной , который своими корнями имеет значения , исключая . Многочлен от x с корнями в этих же точках, включая и , будет иметь вид:
Удаляя тот или иной сомножитель из , можно по желанию исключить ненужный нуль многочлена. Если взять i-тое слагаемое без из выражения для разделенной разности n-го порядка и умножить его на , в котором отсутствует сомножитель , то многочлен степени n будет обладать следующими свойствами:
Если умножить на , то полученный многочлен степени n будет проходить через точку с координатами и будет равен нулю во всех точках . Сумма таких многочленов по всем определяет интерполяционный многочлен Лагранжа степени n.
.
3. Интерполирование по схеме Эйткена
Итерационные методы интерполирования основаны на повторном применении некоторой простой интерполяционной схемы. Наиболее известным из итерационных методов является метод Эйткена, в основе которого лежит многократное применение линейной интерполяции.
В соответствии со схемой Эйткена линейная интерполяция по точкам Mi(xi,yi) и Mi+1(xi+1,yi+1) сводится к вычислению определителя второго порядка
При интерполировании по трем и более точкам последовательно вычисляются многочлены
В общем случае интерполяционныймногочлен n-й степени, принимающий в точках xi значения yi (i = ), записываются следующим образом:
(3)
Основным достоинством схемы Эйткена является возможность постепенного увеличения числа используемых значений xi до тех пор, пока последовательные значенияP0,1,2,…,n(x) и P1,2,…,n-1(x) не совпадут в пределах заданной точности. Иначе говоря, вычисления прекращаются при выполнении условия
|P0,1,2,…,n(x) - P1,2,…,n-1(x)| < e (k £ n).
При использовании ЭВМ вычисления по формуле (3) реализуются в виде рекурсивной подпрограммы - функции РХ(I, J) с формальными параметрами I, J, определяющими индексы крайних узлов интерполирования, которые используются для получения значения соответствующего многочлена Pi,i+1,…, j (x).
Для хранения вычисленных значений P(x) используется двумерный массив M размером N*N элементов, где N- максимальное число узлов интерполирования. Каждому возможному значению P(x) соответствует один из элементов M(I, J), расположенный выше главной диагонали (I < J) и определяемый сочетанием индексов крайних узлов интерполирования.
Например, значению многочлена P1,2(x) соответствует элемент M(1,2), значению P2,3,4(x) - элемент M(2, 4) и т.д. Симметричные элементы M(J, I), расположенные ниже главной диагонали (J > I), показывают, вычислены ли соответствующие значения P(x) на данный момент, и определяются как
Схема рекурсивной процедуры PX приведена на рис. 1, где Х- массив значений узлов интерполирования, Y- массив значений функциивузлах интерполирования, Z- значение аргумента. Параметры X, Y, Z, M должны быть описаны как общие для главной программы и подпрограммы PX.
4. Интерполяционный многочлен Ньютона
Интерполяционный многочлен в форме многочлена Лагранжа не удобен в случаях, когда необходимо добавлять экспериментальные данные в таблицу с целью повышения точности интерполяции. При этом необходимо проводить все вычисления заново.
Если задачу поставить так, что добавление лишней точки требовало бы лишь добавки некоторого многочлена степени (n+1) к многочлену Лагранжа n-й степени, то эту добавку можно искать, выполнив в общем виде преобразование разности двух многочленов Лагранжа: степени (n+1) и n. Несложные преобразования приводят к следующему соотношению для добавочного многочлена степени (n+1):
,
где – многочлен степени (n+1),
– разделенная разность (n+1)-го порядка.
Если считать разделенную разность нулевого порядка равной значению функции в точке , то
Поступая аналогичным образом и находя последовательно , в конце концов, получим общее выражение для другой формы представления интерполяционного многочлена Лагранжа, которая в литературе называется интерполяционным многочленом Ньютона для неравных интервалов и записывается так:
Надо отметить, что дополнительную точку в таблицу необходимо записывать в самую нижнюю строку таблицы, чтобы не нарушить уже имеющегося упорядочения разностей и ускорить вычисление новых.
И, наконец, надо отметить, что и многочлен Лагранжа, и многочлен Ньютона удобны для вычислений, но после раскрытия скобок и приведения подобных дают один и тот же степенной многочлен.
5Приближение и интерполирование функций,
Приближение функций — нахождение для
данной
функции f функции g из некоторого определённого класса
(например, среди алгебраических многочленов заданной степени), в том или ином
смысле близкой к f, дающей её приближённое представление.
Существует много разных вариантов задачи о приближении функций в зависимости от
того, какие функции используются для приближения, как ищется приближающая
функция g, как понимается близость функций f и g. Интерполирование функций — частный
случай задачи приближения, когда требуется, чтобы в определённых точках (узлах
интерполирования) совпадали значения функции f и приближающей её функции g, а в более общем случае — и значения
некоторых их производных.
Для оценки близости исходной функции f и приближающей её функции g используются в зависимости от
рассматриваемой задачи метрики различных функциональных пространств.
Обычно это метрики пространств непрерывных функций С и функций, интегрируемых с р-й степенью, Lp, р ³1, в которых расстояние между функциями f и g определяется (для функций, заданных на
отрезке [а, b]) по формулам
и
Наиболее часто встречающейся и хорошо изученной
является задача о приближении функций полиномами, т. е. выражениями вида
akjk (x),
где (j1,..., jn—заданные
функции, a a1,...,
an — произвольные числа. Обычно это
алгебраические многочлены
akxk
или тригонометрические полиномы
а0 + (ak coskx +bk sinkx).
Рассматриваются также полиномы по ортогональным многочленам, по собственным функциям краевых задач
и т.п. Другим классическим средством приближения являются рациональные
дроби P (x)/Q (x), где в качестве Р и Q берутся алгебраические многочлены
заданной степени.
В последнее время (60—70-е гг. 20 в.)
значительное развитие получило приближение т. н. сплайн-функциями (сплайнами).
Характерным их примером являются кубические сплайн-функции, определяемые
следующим образом. Отрезок [a, b] разбивается точками a =x0 <x1 <... <xn =b, на каждом отрезке [xk, xk+1]
кубическая сплайн-функция является алгебраическим многочленом третьей степени,
причём эти многочлены подобраны так, что на всём отрезке [а, b]
непрерывны сама сплайн-функция и её первая и вторая производные. Оставшиеся
свободными параметры могут быть использованы, например, для того чтобы
сплайн-функция интерполировала в узлах xk приближаемую функцию. Улучшение
приближения достигается за счёт увеличения числа узлов xk правильного их расположения на
отрезке [а, b]. Сплайн-функции
оказались удобными в вычислительной математике, с их помощью удалось решить
также некоторые задачи теории функций.
Приближённые представления функций, а
также сами функции на основе их приближённых представлений изучает теория
приближений функций (употребляются также названия теория аппроксимации функций
и конструктивная теория функций). К теории приближений функций обычно относят
также задачи о приближении элементов в банаховых и общих метрических
пространствах.
Теория приближений функций берёт начало
от работ П. Л. Чебышева. Он ввёл одно из основных понятий
теории — понятие наилучшего приближения функции полиномами и получил ряд
результатов о наилучших приближениях. Наилучшим приближением непрерывной
функции f (x)полиномами akjk (x) в метрике С
называется величина
En = min || f - akjk (x)||c,
где минимум берётся по всем числам а1,..., an. Полином, для которого достигается этот
минимум, называется полиномом наилучшего приближения (для других метрик
определения аналогичны). Чебышев установил, что наилучшее приближение функции xn+1 на отрезке [—1, 1] в метрике С
алгебраическими многочленами степени n равно 1/2n, а многочлен
наилучшего приближения таков, что для него
xn+1 - = (1/2n) cos (n + 1) arccosx.
Следующая теорема Чебышева указывает
характеристическое свойство полиномов наилучшего приближения в пространстве
непрерывных функций: алгебраический многочлен , в том и только в том случае является
многочленом наилучшего приближения непрерывной функции f в метрике С [—1, 1], если существуют n +
2 точки -1 £ x1 < x2 <... < xn+2 £ 1, в которых разность f (x)— 2принимает максимальное значение своего
модуля с последовательно чередующимися знаками.
Одним из первых результатов теории
приближений является также теорема Вейерштрасса, согласно которой каждую
непрерывную функцию можно приблизить в метрике С как угодно хорошо
алгебраическими многочленами достаточно высокой степени.
С начала 20 в. началось систематическое
исследование поведения при n ® ¥ последовательности En — наилучших приближений функции f алгебраическими (или
тригонометрическими) многочленами. С одной стороны, выясняется скорость
стремления к нулю величин En в зависимости от свойств функции (т.
н. прямые теоремы теории приближений), а с другой — изучаются свойства функции
по последовательности её наилучших приближений (обратные теоремы теории
приближений). В ряде важных случаев здесь получена полная характеристика
свойств функций. Приведём две такие теоремы.
Для того чтобы функция f была
аналитической на отрезке (т. е. в каждой точке этого отрезка представлялась
степенным рядом, равномерно сходящимся к ней в некоторой окрестности этой
точки), необходимо и достаточно, чтобы для последовательности её наилучших
приближений алгебраическими многочленами выполнялась оценка
En £Aq n,
где q < 1 и А — некоторые положительные числа, не
зависящие от n (теорема С. Н. Бернштейна).
Для того чтобы функция f периода 2p имела
производную порядка r, r = 0, 1,2,..., удовлетворяющую условию
|f (r)(x +h) - f (r)(x)|
£ M|h|a,
0 < a < 1, М — некоторое положительное число, или
условию
|f (r)(x +h) - 2f (r)(x) + f (r)(x
- h)| £ M|h|a
(в этом случае a = 1), необходимо и
достаточно, чтобы для наилучших приближений функции f тригонометрическими полиномами была
справедлива оценка
Еп £ А/n r+a,
где А
— некоторое положительное
число, не зависящее от n. В этом утверждении прямая теорема была
в основном получена Д. Джексоном (США), а обратная является результатом
исследований С. Н. Бернштейна, Ш. Ж. Ла
Валле Пуссена и А.
Зигмунда (США). Характеристика подобных классов функций, заданных на отрезке, в
терминах наилучших приближении алгебраическими многочленами оказалась
невозможной. Её удалось получить, привлекая к рассмотрению приближение функций
с улучшением порядка приближения вблизи концов отрезка.
Возможность характеризовать классы
функций с помощью приближений их полиномами нашла приложение в ряде вопросов
математического анализа. Развивая исследования по наилучшим приближениям
функций многих переменных полиномами, С. М. Никольский построил теорию вложений важных
для анализа классов дифференцируемых функций многих переменных, в которой имеют
место не только прямые, но и полностью обращающие их обратные теоремы.
Для приближений в метрике L2 полином наилучшего приближения может
быть легко построен. Для других пространств нахождение полиномов наилучшего
приближения является трудной задачей и её удаётся решить только вотдельных случаях. Это привело
к разработке разного рода алгоритмов для приближённого нахождения полиномов
наилучшего приближения.
Трудность нахождения полиномов
наилучшего приближения отчасти объясняется тем, что оператор, сопоставляющий
каждой функции её полином наилучшего приближения, не является линейным: полином
наилучшего приближения для суммы f +g не обязательно равен сумме полиномов
наилучшего приближения функций f и g.Поэтому
возникла задача изучения (по возможности простых) линейных операторов,
сопоставляющих каждой функции полином, дающий хорошее приближение. Например,
для периодической функции f (x) можно брать частные
суммы её ряда Фурье Sn (f, х). При этом справедлива оценка (теорема
А. Лебега)
||f - Sn ||c£ (Ln + 1) En,
где Ln — числа, растущие при n ®¥ как (4/p2) lnn.
Они получили название констант Лебега. Эта оценка показывает, что полиномы Sn доставляют приближение, не очень
сильно отличающееся от наилучшего. Подобная оценка имеет место и для
приближений интерполяционными тригонометрическими полиномами с равноотстоящими
узлами интерполирования, а также для приближений интерполяционными
алгебраическими многочленами на отрезке [-1, 1] с узлами , k =1,
2,..., n, т. е. в нулях
полинома Чебышева cosn arccosx. Для основных встречающихся в анализе
классов функций известны такие линейные операторы, построенные с помощью рядов
Фурье или на основе интерполяционных полиномов, что значениями этих операторов
являются полиномы, дающие на классе тот же порядок убывания приближений при n ®
¥, что и наилучшие приближения.
А. Н. Колмогоров начал изучение нового вопроса теории
приближений — задачи о нахождении при фиксированном n такой системы функций j1,...,
jn, для которой
наилучшие приближения функций заданного класса полиномами были бы наименьшими (т. н.
задача о поперечнике класса функций). В этом направлении в дальнейшем было
выяснено, например, что для ряда важных классов периодических функций
наилучшими в указанном смысле системами являются тригонометрические полиномы.
Теория приближений функций является
одним из наиболее интенсивно разрабатываемых направлений в теории функций. Идеи
и методы теории приближений являются отправной точкой исследования в ряде
вопросов вычислительной математики. С 1968 в США издаётся специализированный
журнал «Journal of Approximation Theory».
6. Аппроксимация функций методом наименьших квадратов
Основным недостатком интерполяционных многочленов является наличие у них большого числа экстремумов и точек перегибов, что определяется суммированием в них многочленов , n раз меняющих свой знак. Кроме того, исходные табличные значения функции заданы неточно по разным причинам, поэтому строить многочлены выше 4-5-й степени, зная, что из теоретических исследований функция в интервале таблицы совсем не такая, не имеет особого смысла.
Если табличные значения функции можно интерпретировать как теоретическое значение плюс погрешность, то, задав некоторый критерий близости теоретической кривой к заданному множеству табличных точек, можно найти нужное число параметров этой кривой.
Наиболее популярным критерием близости является минимум среднего квадрата отклонения:
,
где – точка экспериментальных данных из таблицы,
– значение искомой зависимости в точке .
Если искомую зависимость желательно представить многочленом степени n, то (n+1) коэффициент в нем будут представлять неизвестные параметры. Подставив в сумму квадратов отклонений искомый многочлен, получим функционал, зависящий от этих параметров:
Чтобы функционал был минимален, необходимо все частные производные функционала по параметрам приравнять нулю и систему разрешить относительно неизвестных параметров . Эти действия приводят к следующей системе линейных уравнений
Здесь – постоянный коэффициент, равный сумме (j+k)-тых степеней всех значений аргументов. Для их ручного вычисления удобно к исходной таблице данных добавить еще столбцов. – числовые значения в правой части системы линейных алгебраических уравнений, для подсчета которых тоже
удобно к исходной таблице данных добавить еще n столбцов.
Демонстрацию метода наименьших квадратов проведем для данных с количеством точек в таблице, равным 4. Максимальная степень аппроксимирующего многочлена для такого набора равна 3, так как должно выполняться соотношение: . Для максимальной степени аппроксимирующий и интерполяционный многочлены равны.
Пусть таблица данных после добавления в нее дополнительных колонок выглядит следующим образом:
В нижней строке размещаем итоговые суммы по каждой колонке.
Система уравнений для полинома третьей степени:
Решив систему, найдем:
Эта же таблица без добавления чего-либо позволяет найти коэффициенты аппроксимирующего многочлена второй степени. Для этого достаточно в системе для полинома третьей степени убрать 4-е уравнение, а из остальных уравнений исключить слагаемые с неизвестной . В результате система уравнений для полинома второй степени будет:
Решив систему, найдем:
Аналогично можно уменьшать число уравнений для построения аппроксимирующих многочленов первой и нулевой степеней.
На рисунке 1 показаны графики двух аппроксимирующих многочленов второй и третьей степени. Многочлен третьей степени проходит через 4 заданные точки, а многочлен второй степени проходит сквозь множество заданных точек с минимумом суммы квадратов отклонений от них, что хорошо видно на графиках.
Рисунок 1.
Заключение
В вычислительной математике существенную роль играет интерполяция функций, т.е. построение по заданной функции другой (как правило, более простой), значения которой совпадают со значениями заданной функции в некотором числе точек. Причем интерполяция имеет как практическое, так и теоретическое значение. На практике часто возникает задача о восстановлении непрерывной функции по ее табличным значениям, например полученным в ходе некоторого эксперимента. Для вычисления многих функций оказывается эффективно приблизить их полиномами или дробно-рациональными функциями. Теория интерполирования используется при построении и исследовании квадратурных формул для численного интегрирования, для получения методов решения дифференциальных и интегральных уравнений.
Литература
1. Бахвалов Н.С., Жидков Н.П., Кобельков Г.М. Численные методы: Учеб. пособие. – М.: Наука, 1987. – 600 с.
2. Воеводин В.В. Численные методы алгебры. Теория и алгорифмы. - М.: Наука, 1966. – 248 с.
3. Воеводин В.В. Вычислительные основы линейной алгебры. – М.: Наука, 1977. – 304 с.
4. Волков Е.А. Численные методы. – М.: Наука, 1987. – 248 с.
5. Калашников В. И. Аналоговые и гибридные вычислительные устройства: Учеб. пособие. – Харьков: НТУ “ХПИ”, 2002. – 196 с.
6. Вержбицкий, В. М. Численные методы. Математический анализ и обыкновенные дифференциальные уравнения. М.: Высш.шк., 2001. 383 с.
7. Волков, Е. А. Численные методы. СПб.: Лань, 2004. 248 с.
8. Мудров, А. Е. Численные методы для ПЭВМ на языках Бейсик, Фортран и Паскаль. Томск: МП "РАСКО", 1991. 272 с.
9. Шуп, Т. Е. Прикладные численные методы в физике и технике. М.: Высш. шк., 1990. 255 с.
10. Бахвалов, Н. С. Численные методы в задачах и упражнениях / Н. С. Бахвалов, А. В. Лапин, Е. В. Чижонков. М.: Высш. шк., 2000. 192 с.
11.
Лит.: Монографии.
Ахиезер Н. И., Лекции по теории аппроксимации, 2 изд., М., 1965; Гончаров В.
Л., Теория интерполирования и приближения функций, 2 изд., М., 1954; Натансон
И. П., Конструктивная теория функций, М. — Л., 1949; Никольский С. М.,
Приближение функций многих переменных и теоремы вложения, М., 1969; Тиман А.
Ф., Теория приближения функций действительного переменного, М., 1960.
12.
Обзоры. Математика в СССР за
тридцать лет. 1917—1947, М. — Л., 1948, с. 288—318; Математика в СССР за сорок
лет. 1917—1957, т. 1, М., 1959, с. 295—379; История отечественной математики,
т. 3, К., 1968, с. 568—588.
С. А. Теляковский.