Размещено на http://www.allbest.ru/

Московский государственный горный университет

Кафедра САПР

Реферат

на тему: «Интерполяция»

по дисциплине: «Численные методы»

Выполнила:

студентка группы

АСП-Б-11

Терехова С.С.

Проверил:

Рябов Л.П.

Москва 2014

Оглавление

Введение

1. Интерполирование

2. Эрмитова интерполяция

3. Интерполирование по схеме Эйткена

4. Интерполяционные формулы для функций двух переменных

5. Численное дифференцирование

6. Погрешность численного дифференцирования

Заключение

Список литературы

Введение

численный метод интерполирование

При разработке математического обеспечения САПР часто приходится иметь дело с функциями f(x), заданными в виде таблиц, когда известны некоторое конечное множество значений аргумента и соответствующие им значения функции. Аналитическое выражение функции f(x) при этом неизвестно, что не позволяет определять ее значения в промежуточных точках аргумента, отсутствующих в таблице. В таком случае решается задача интерполирования, которая формулируется следующим образом.

На отрезке [a, b] заданы n + 1 точки x₀, x₁, ..., x_n, которые называются узлами интерполяции, и значения некоторой функции f(x) в этих точках f(x₀) = y₀, f(x₁) = y₁, ..., f(x_n) = y_n. Требуется построить интерполирующую функцию F(x), принимающую в узлах интерполяции те же значения, что и f(x), т.е. такую, что F(x₀) = y₀, F(x₁) = y₁, ..., F(x_n) = y_n.

Геометрически это означает, что нужно найти кривую y = F(x) некоторого определенного типа, проходящую через заданную систему точек M_i(x_i, y_i) для i = . Полученная таким образом интерполяционная формула y = F(x) обычно используется для вычисления значений исходной функции f(x) для значений аргумента x, отличных от узлов интерполяции. Такая операция называется интерполированием функции f(x). При этом различают интерполирование в узком смысле, когда x принадлежит интервалу [x₀, x_n], и экстраполирование, когда x не принадлежит этому интервалу.

В такой общей постановке задача интерполирования может иметь бесчисленное множество решений. Чтобы получить единственную функцию F(x), необходимо предположить, что эта функция не произвольная, а удовлетворяет некоторым дополнительным условиям.

В простейшем случае предполагается, что зависимость y = f(x) на каждом интервале (x_i, x_i+1) является линейной. Тогда для каждого участка (x_i, x_i+1) в качестве интерполяционной формулы y = F(x) используется уравнение прямой, проходящей через точки M_i(x_i, y_i) и M_i+1(x_i+1, y_i+1), которое имеет вид

. (1)

При программировании процедур линейной интерполяции следует учитывать, что процесс решения задачи интерполирования с использованием формулы (1) включают два этапа: выбор интервала (x_i, x_i+1), которому принадлежит значение аргумента х; собственно вычисление значения y = F(x) по формуле (1).

На практике в качестве интерполирующей функции F(x) обычно используется алгебраический многочлен

P_n(x) = a₀ + a₁x + a₂x² + ... + a_nxⁿ

степени не выше n, такой, что P_n(x₀) = y₀, P_n(x₁) = y₁, ..., P_n(x_n) = y_n. Наиболее известными методами построения интерполяционного многочлена P_n(x) являются метод Лагранжа, итерационные и разностные методы.

1. Интерполирование

Опр. Пусть функция f(х) задана таблично на [a,b]:

x₀ = a, x_n = b , x₀ <x₁ < x₂ < .... < x_n , y_i = f(x_i) i = 0,..., n

Тогда построение непрерывной на [a,b] функции j (x) , такой что j (x_i) = y_i называется интерполяцией функции f(x) на [a,b].

Опр. Пусть полином степени n L_n(x) = a₀ xⁿ + a₁ x^n-1 + ... + a_n интерполирует y=f(x) на [a,b], т.е. L_n(x_i) = y_i= f(x_i). Тогда L_n(x) называется интерполяционным полиномом.

Утверждение. Интерполяционный многочлен степени n для функции y=f(x), заданной таблично в n+1 точках, существует и единственен.

Данное утверждение следует из того, что определитель Вандермонда отличен от нуля.

Существуют некоторые стандартные формы записи интерполяционных полиномов. Интерполяционный многочлен в форме Лагранжа имеет вид

.

Интерполяционный многочлен в форме Ньютона имеет вид

Где

выражения такого вида называются разделенными разностями.

Теорема

Пусть функция y=f(x) имеет n+1 непрерывную производную на [a,b], и L_n(x) - интерполяционный многочлен, L_n(x_i) = f(x_i) , i=0,1,...,n. Тогда для погрешности интерполяции y (x) = п L(x) - f(x)п справедлива оценка

Где

2. Эрмитова интерполяция

Эрмитова интерполяция - метод полиномиальной интерполяции, названный в честь французского математика Шарля Эрмита. Многочлены Эрмита тесно связаны с многочленами Ньютона.

В отличие от интерполяции Ньютона, эрмитова интерполяция строит многочлен, значения которого в выбранных точках совпадают со значениями исходной функции в этих точках, и производные многочлена в данных точках совпадают со значениями производных функции (до некоторого порядка m). Это означает, что n(m + 1) величин

должны быть известны, тогда как для ньютоновской интерполяции необходимы только первые n значений. Полученный многочлен может иметь степень не более, чем n(m + 1) ? 1, максимальная степень многочлена Ньютона же равна n ? 1. (В общем случае m не обязательно должно быть фиксировано, то есть в одних точках может быть известно значение большего количества производных, чем в других. В этом случае многочлен будет иметь степень N ? 1, где N - число известных значений.)

Простой случай

При использовании разделенных разностей для вычисления многочлена Эрмита, первым шагом является копирование каждой точки m раз. (Здесь мы рассмотрим простой случай, когда для всех точек .) Поэтому, дана точка , и значения и функции f, которую мы хотим интерполировать. Определим новый набор данных

такой, что

Теперь определим таблицу разделенных разностей для точек . Однако, для некоторых разделенных разностей

что есть неопределенность! В этом случае заменим эту разделенную разность значением , а другие вычислим обычным способом. 6

Общий случай

В общем случае полагаем, что в данных точках известны производные функции f до порядка k включительно. Тогда набор данных содержит k копий . При создании таблицы, разделенных разностей при одинаковые значения будут вычислены как

.

Например,

и так далее.

Пример

Рассмотрим функцию . Вычислив значения функции и ее первых двух производных в точках , получим следующие данные:

Так как мы работаем с двумя производными, строим множество . Таблица разделенных разностей тогда имеет вид:

и получаем многочлен

взятием коэффициентов диагонали таблицы разделенных разностей, и умножением коэффициента с номером k на

как при получении многочлена Ньютона.

3. Интерполирование по схеме Эйткена

Итерационные методы интерполирования основаны на повторном применении некоторой простой интерполяционной схемы. Наиболее известным из итерационных методов является метод Эйткена, в основе которого лежит многократное применение линейной интерполяции.

В соответствии со схемой Эйткена линейная интерполяция по точкам M_i(x_i, y_i) и M_i+1(x_i+1, y_i+1) сводится к вычислению определителя второго порядка

При интерполировании по трем и более точкам последовательно вычисляются многочлены

В общем случае интерполяционный многочлен n-й степени, принимающий в точках x_i значения y_i (i = ), записываются следующим образом:

Основным достоинством схемы Эйткена является возможность постепенного увеличения числа используемых значений x_i до тех пор, пока последовательные значения P_0,1,2,…,n(x) и P_1,2,…,n-1(x) не совпадут в пределах заданной точности. Иначе говоря, вычисления прекращаются при выполнении условия

|P_0,1,2,…,n(x) - P_1,2,…,n-1(x)| < e (k Ј n).

При использовании ЭВМ вычисления по формуле (3) реализуются в виде рекурсивной подпрограммы - функции РХ(I, J) с формальными параметрами I, J, определяющими индексы крайних узлов интерполирования, которые используются для получения значения соответствующего многочлена P_{i,i+1,…, j} (x).

Для хранения вычисленных значений P(x) используется двумерный массив M размером N*N элементов, где N - максимальное число узлов интерполирования. Каждому возможному значению P(x) соответствует один из элементов M(I, J), расположенный выше главной диагонали (I < J) и определяемый сочетанием индексов крайних узлов интерполирования.

Например, значению многочлена P_1,2(x) соответствует элемент M(1,2), значению P_2,3,4(x) - элемент M(2, 4) и т.д. Симметричные элементы M(J, I), расположенные ниже главной диагонали (J > I), показывают, вычислены ли соответствующие значения P(x) на данный момент, и определяются как

Схема рекурсивной процедуры PX приведена на рис. 1, где Х - массив значений узлов интерполирования, Y - массив значений функции в узлах интерполирования, Z - значение аргумента. Параметры X, Y, Z, M должны быть описаны как общие для главной программы и подпрограммы PX.

4. Интерполяционные формулы для функций двух переменных

На практике возникает необходимость построения интерполяционных формул для функций нескольких переменных. Для простоты ограничимся функцией двух переменных z=f(x,у). Пусть ее значения заданы на множестве равноотстоящих узлов (xi,yi) (i, j = 0,1,2). Введем обозначения

, , .

Построим многочлен, аналогичный многочлену Ньютона для случая одной переменной. Здесь нужно вычислять разности двух видов - по направлениям х и у. Эти частные разности первого порядка определяются формулами

Запишем также выражения для частных разностей второго порядка:

Интерполяционный многочлен второй степени можно записать в виде

+

Можно также построить линейную интерполяционную формулу. Геометрически это означает, что нужно найти уравнение плоскости, проходящей через три заданные точки , (i = 1, 2, 3), где zi = f(xi,yi). Из курса аналитической геометрии известно, что уравнение плоскости, проходящей через три точки, можно записать в виде

Отсюда можно найти:

(2.58)

Пример. Вычислить приближенное значение функции z = f(x,y) в точке (1,0), если известны ее значения

z1 = f(0,0) = 0, z2 = f (2,4) = -3, z3= f(4, -2) = 1.

Воспользуемся формулой линейной интерполяции (2.58). Вычислим значения определителей

Таким образом,

или

Это и есть формула линейной интерполяции для данного примера. При х = 1, у =0 получим z?-0.1.

5. Численное дифференцирование

6. Погрешность численного дифференцирования

Основной источник погрешности, возникающей при численном дифференцировании, связан с аппроксимацией функции . При использовании интерполяционных полиномов для аппроксимации функции имеем

,

где - ошибка интерполяции. Следовательно, погрешность вычисления производной функции по формуле (5.3) будет определяться производной от ошибки интерполяции

.

Анализ погрешности формул численного дифференцирования, опирающийся на непосредственно дифференцирование ошибки интерполяции затруднен в силу математических сложностей. Поэтому мы познакомимся с другим подходом к анализу точности формул численного дифференцирования.

Прежде всего заметим, что все рассмотренные нами формулы для приближенного вычисления производной в конкретной точке имеют следующую структуру:

, (5.9)

где - постоянные коэффициенты; суммирование производится по некоторому диапазону табличных данных.

Анализ погрешности формулы (5.9) сводится к следующему. Заменяем все входящие в правую часть (5.9) значения разложением по формулам Тейлора относительно точки, для которой рассматривается приближение (5.9). После проведения несложных арифметических преобразований в качестве главного члена правой части получаем приближенное значение производной. Остальные члены будут характеризовать погрешность.

В качестве примера рассмотрим оценку погрешности формулы (5.5) для точки . Заменим значения и по формулам Тейлора относительно точки x:

,

.

Подставляя эти выражения в правую часть (5.5) получим

Таким образом, погрешность (ошибка) формулы (5.5) для произвольной точки будет определяться следующим выражением

Для точки получаем

, т.е. ,

следовательно, для формула (5.5) является формулой первого порядка точности. Можно показать, что для любой точки формула (5.5) также будет иметь первый порядок точности [12]. Исключение составляет точка - середина интервала , для которой

, т.е.

Следовательно, в этом случае формула (5.5) является формулой второго порядка точности.

Мы рассмотрели лишь один из источников погрешности численного дифференцирования - погрешность аппроксимации, которая определяется величиной остаточного члена. Как уже отмечалось выше, анализ остаточного члена нетривиален. Отметим, лишь, что погрешность аппроксимации при уменьшении шага h, как правило, уменьшается. Рассмотренный пример, позволяет также сделать вывод о том, что погрешность формул численного дифференцирования зависит от того, в какой точке вычисляется производная.

Другой источник погрешности численного дифференцирования связан с погрешностями вычисления значений функции в узлах и с погрешностями округлений при проведении расчетов на компьютере. Обусловленные этими причинами погрешности, в отличие от погрешности аппроксимации, возрастают с уменьшением шага h. Действительно, если при вычислении значения функции абсолютная погрешность равна , то при вычислении дробей в (5.4) и (5.5) она составит . Поэтому суммарная погрешность численного дифференцирования может убывать при уменьшении шага лишь до некоторого предельного значения, после чего дальнейшее уменьшение шага не повысит точности результата.

Заключение

В вычислительной математике существенную роль играет интерполяция функций, т.е. построение по заданной функции другой (как правило, более простой), значения которой совпадают со значениями заданной функции в некотором числе точек. Причем интерполяция имеет как практическое, так и теоретическое значение. На практике часто возникает задача о восстановлении непрерывной функции по ее табличным значениям, например полученным в ходе некоторого эксперимента. Для вычисления многих функций оказывается эффективно приблизить их полиномами или дробно-рациональными функциями. Теория интерполирования используется при построении и исследовании квадратурных формул для численного интегрирования, для получения методов решения дифференциальных и интегральных уравнений.

Список литературы

1. Н.С. Бахвалов, Н.П. Жидков, Г.М. Кобельков. Численные методы. Изд-во "Лаборатория базовых знаний". 2003.

2. И.С. Березин, Н.П. Жидков. Методы вычислений. Изд. ФизМатЛит. Москва. 1962.

3. А.А. Самарский, А.В. Гулин. Численные методы. М., Наука, 1989

4. http://ru.wikipedia.org/wiki

Размещено на Allbest.ru