Приближение функций

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

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

Федеральное агентство по образованию РФ

Белгородский Государственный университет

Кафедра информатики и вычислительной техники

Курсовая работа на тему

«ПРИБЛИЖЕНИЕ ФУНКЦИЙ»

Белгород 2007г.

Содержание

Введение

1. Постановка задачи приближения функции

2. Интерполяционный многочлен Лагранжа

3. Интерполяционный многочлен Ньютона для равноотстоящих узлов

3.1. Первая интерполяционная формула Ньютона

3.2. Вторая интерполяционная формула Ньютона

4. Итерационный метод интерполяции (по Эйткену)

5. Программная реализация методов в среде Mathcad

Заключение

Литература

Введение

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

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

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

Существуют 3 класса или группы функций, широко применяемых в численном анализе. Первая группа включает в себя линейные комбинации функций 1, х, х², …, хⁿ, что совпадает с классом всех многочленов степени n (или меньше). Второй класс образуют функции cos a_ix, sin a_ix. Этот класс имеет отношение к рядам Фурье и интегралу Фурье. Третья группа образуется функциями e^-az. Эти функции встречаются в реальных ситуациях. К ним, например, приводят задачи накопления и распада.

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

1. Постановка задачи приближения функции

Пусть известные значения некоторой функции f образуют некоторую таблицу

Таблица 1.1

			…
			…

При этом требуется получить значение функции f для такого значения аргумента x, которое входит в отрезок [; ], но не совпадает ни с одним из значений , (i=0,1, ..., п).

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

f(x)=F(x). (1.1)

Классический подход к решению задачи построения приближающей функции основывается на требовании строгого совпадения значений f(х) и F(x) в точках , (i=0,1, ..., п ), т. е.

F () = , F () = , …, F () = (1.2)

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

Будем искать интерполирующую функцию F(x) в виде многочлена степени п

(x)= + + … + x+ (1.3)

Этот многочлен имеет n+1 коэффициент. Естественно предполагать, что n+1 условия (1.2), наложенные на многочлен, позволят однозначно определить его коэффициенты. Действительно, требуя для (x) выполнения условий (1.2), получаем систему n+1 уравнений с n+1 неизвестными

= , (i=0,1, ..., п)

Решая эту систему относительно неизвестных , …, , мы и получим аналитическое выражение полинома (1.3). Система (1.4) всегда имеет единственное решение, так как ее определитель известный и алгебре как определитель Вандермонда, отличен от нуля.

. . . . . . . . . . . . . . . . .

Отсюда следует, что интерполяционный многочлен (x)для функции f, заданной таблицей 1.1, существует и единствен (может случиться, что какие-то коэффициенты в (x), в том числе и равны нулю; поэтому интерполяционный полином при рассмотренных условиях в общем случае имеет степень, не большую, чем n).

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

2. Интерполяционный многочлен Лагранжа

Пусть функция f задана таблицей 4.1. Построим интерполяционный многочлен L_n(x), степень которого не больше n и для которого выполнены условия (1.2). Будем искать L_n(x), в виде

L_n(x) = l₀ (х)+ l₁ (х)+…+ l_n (х). (2.1)

где l_i (x) -многочлен степени n, причем

l_i(x_k) = (2.2)

Очевидно, что требование (2.2) с учетом (2.1) вполне обеспечивает выполнение условий (4.2).

Многочлены l_i (x) составим следующим способом

l_i (x) = c_i (x-x₀)(x-x₁)…(x-x_i-1)(x-x_i+1)…(x-x_n) (2.3)

где с_i - постоянный коэффициент, значение которого найдем из первой части условия (2.2)

с_i =

( ни один множитель в знаменателе не равен нулю).

Подставим с_i в (2.3) и далее с учетом (2.1) окончательно имеем:

L_n(x) = (2.4)

Эго и есть интерполяционный многочлен Лагранжа. По таблице исходной функции f формула (2.4) позволяет весьма просто составить «внешний вид» многочлена.

Пример 1. Построить интерполяционный многочлен Лагранжа для функции, заданной таблицей:

x	1	2	3
f(x)	12	4	6

Из таблицы 2 следует, что n=2(степень многочлена будет не выше, чем вторая); здесь x₀ =1, x₁ =3, x₂ =4. Используя формулу (2.4), получаем

L₂ (x) = 12 +4 + 6 = 2 (x² -7x+12) -

- 2(x² - 5x+4)+2(x² -4x+4)= 2x² -12x+22.

Используя обозначение ( x-x₀)(x-x₁)…(x-x_n), формуле Лагранжа можно придать более сжатый вид. Продифференцируем по x:

= …(x-x_i-1)(x-x_i+1)…(x-x_n)

При x = x_i имеем, (i=0,1, ..., п):

= .

Тогда формула Лагранжа принимает вид

L_n(x) = =

Алгоритм вычисления значения интерполяционного многочлена Лагранжа

Для составления программы вычисления одного значения интерполяционного многочлена Лагранжа на ЭВМ воспользуемся формулой (2.4).Основная рабочая часть искомого алгоритма состоит из двойного цикла во внутреннем цикле вычисляются n+1 значений многочленов-слагаемых вида (i=0,1, ..., п)

L_n(x) =

(в числителе и знаменателе n сомножителей), а во внешнем -- накапливается общая сумма

L_n(x) = (x)

Работа внутреннего цикла контролируется с помощью индекса j. Изменяясь в пределах от 0 до n, индекс j принимает все-таки ровно п значений, «проскакивая» текущее значение индекса i, определяемого во внешнем цикле. Тем самым обеспечивается правильное составление многочленов-слагаемых l_i(x) формулы Лагранжа. Носителем окончательного результата является переменная f. Схема алгоритма изображена на рис. 1.

Рис. 1. Схема алгоритма

да нет

3. Интерполяционный многочлен Ньютона для равноотстоящих узлов

Часто интерполирование ведется для функций, заданных таблицами с равноотстоящими значениями аргумента. В этом случае шаг таблицы h =x_i+1 -x_i (i=0,1,2…) является величиной постоянной. Для таких таблиц построение интерполяционных формул, а также проведение расчетов по ним заметно упрощается.

Для построения формулы Ньютона необходимо ввести понятие конечных разностей.

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

y_i = y_i+1 - y_i , (i=0, 1, 2 ...)

Из конечных разностей первого порядка образуются конечные разности второго порядка

² y_i = y_i+1 - y_i , (i=0, 1, 2...)

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

² y_i = y_i+1 - y = ( y_i+2 - y_i+1 ) - ( y_i+1 - y_i ) = y_i+2 - 2y_i+1 + ^yi _.

Аналогично для разностей третьего порядка

³ y_i =² y_i+1 - ²y =( y_i+3 - 2y_i+2 + y_i+1 ) - ( y_i+2 - 2y_i+1 + y_i ) = y_i+3 - 3y_i+2 +

+ 3 y_i+1 - y_i и т.д.

Методом математической индукции можно доказать, что

^k y_i = y_i+k - k y_i+k + y_i+k-2 - … + (-1) ^k y_i. (3.1)

Таблица 3.1

x	y	?yi	2yi	3yi	…
x0	y0	?y0	2y0	3y0
x1	y1	?y1	2y1	3y1
x2	y2	?y2	2y2	…
x3	y3	?y3	…
x4	y4	…
…	…

3.1. Первая интерполяционная формула Ньютона

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

(x)= + + a₂ + … + …

Это многочлен п-й степени. Значения коэффициентов a₀, a₁ ..., а_n найдем из условия совпадения значений исходной функции и многочлена в узлах. Полагая х=х₀ из (3.2)находим у₀=Р_п(х₀) =а₀ , откуда а₀ = у₀. Далее, придавая х значения х₁ и х₂, последовательно получаем

y₁ = (x₁)= + , откуда ;

y₂ = (x₂)= + , т.е.

, или = 2откуда

Далее, проведя аналогичные выкладки, можно получить:

в общем случае выражение для a_k будет иметь вид

Подставим теперь (3.3) в выражение для многочлена (3.2)

(x)=y₀ + + +…+

…

Практически эта формула применяется в несколько ином виде.

Положим = t, т.е. x= x₀ + ht. Тогда: = = t - 1,

= = t - 2, и т.д.

Окончательно имеем

(x)=(x₀ +th)=y₀ + t+

\

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

3.2 Вторая интерполяционная формула Ньютона

Когда значение аргумента находится ближе к концу отрезка интерполяции, применять первую интерполяционную формулу становиться невыгодно. В этом случае применяется формула для интерполирования назад вторая интерполяционная формула Ньютона, которая отыскивается в виде

(x)= + a₂ + … +

Как и для первой формулы Ньютона, коэффициенты a_0, a₁ , …a_n находятся из условия совпадения значений функции и интерполяционного многочлена в узлах

Подставляя (3.6) в (3.5) и переходя к переменной t = , получим окончательный вид второй интерполяционной формулы Ньютона

(x)=(x_n + th)=y_n +t?y_n-1 +

4. Итерационный метод интерполяции (по Эйткену)

Особенности метода.

Он позволяет определить значение функции y=f(x) в заданной точке х на сегменте [а, b], если исходный интерполяционный многочлен У_ijk, определяется парами величин (х_i, у_j), (x_j, y_j), (х_k, у_k)..., отвечающих узлам интерполяции i,j, k... Таким образом, в отличие от рассмотренных ранее методов интерполяции здесь не требуется описывать аналитически интерполяционный многочлен для интерполяции его значения в заданной точке х.

Расчетные соотношения.

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

между нулевым и первым узлом

где х -- абсцисса искомой точки; x₀ и y₀-- пара величин, отвечающая нулевой точке; x₁ и y₁ -- то же для точки 1;

между первым и вторым узлом

между нулевым и вторым узлом

между нулевым и k-м узлом

5. Программная реализация методов в среде Mathcad

Метод Лагранжа

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

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

Метод Эйткена (1 вариант)



Метод Эйткена (2 вариант)

Заключение

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

интерполяционный многочлен приближение функция

Литература

1. Заварыкин В.М., Житомирский В.Г., Лапчик М.П. Численные методы.- М.: Просвещение, 1991

2. Калиткин Н.П. Численные методы.- М.: Наука, 1978.

3. Лапчик М.П., Рагулина М.И., Стукалов В.А. Численные методы: Учеб. пособие для пед. вузов.-М.: Академия, 2001.

4. Ракитин В.И., Первушкин В.Е. Практическое руководство по методам вычислений с приложением программ для персональных компьютеров: Учеб. пособие.- М.: Высш. шк., 1998.

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

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