Контрольная работа: Интерполирование функций
💣 👉🏻👉🏻👉🏻 ВСЯ ИНФОРМАЦИЯ ДОСТУПНА ЗДЕСЬ ЖМИТЕ 👈🏻👈🏻👈🏻
2. Интерполирование по схеме Эйткена
3. Интерполяционные формулы Ньютона для равноотстоящих узлов
4. Формула Ньютона с разделенными разностями
Цель работы: изучение и сравнительный анализ методов интерполяции функций; реализация этих методов в виде машинных программ на языке высокого уровня и практическое решение задач интерполяции на ЭВМ.
При разработке математического обеспечения САПР часто приходится иметь дело с функциями f
( x
), заданными в виде таблиц, когда известны некоторое конечное множество значений аргумента и соответствующие им значения функции. Аналитическое выражение функции f
( x
) при этом неизвестно, что не позволяет определять ее значения в промежуточных точках аргумента, отсутствующих в таблице. В таком случае решается задача интерполирования, которая формулируется следующим образом.
На отрезке [ a
, b
] заданы n
+ 1 точки x
0
, x
1
, ..., x n
, которые называются узлами интерполяции, и значения некоторой функции f
( x
) в этих точках f
( x
0
) =
y
0
, f
( x
1
) =
y
1
, ..., f
( x
n
) =
y
n
. Требуется построить интерполирующую функцию F
( x
), принимающую в узлах интерполяции те же значения, что и f
( x
), т.е. такую, что F
( x
0
) =
y
0
, F
( x
1
) =
y
1
, ..., 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
0
, 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) включают два этапа: выбор интервала ( x i
, x i
+1
), которому принадлежит значение аргумента х
; собственно вычисление значения y
= F
( x
) по формуле (1).
На практике в качестве интерполирующей функции F
( x
) обычно используется алгебраический многочлен
P n
( x
) =
a
0
+
a
1
x
+
a
2
x
2
+ ... + a n
x n
степени не выше n
, такой, что P n
( x
0
) = y
0
, P n
( x
1
) = y
1
,..., P n
( x n
) = y n
. Наиболее известными методами построения интерполяционного многочлена P n
( x
)являются метод Лагранжа, итерационные и разностные методы.
Интерполяционная формула Лагранжа обеспечивает построение алгебраического многочлена P n
( x
) для произвольно заданных узлов интерполирования. Для n
+ 1 различных значений аргумента x
0
, x
1
, ..., x n
и соответствующих значений функции f
( x
0
) =
y
0
, f
( x
1
) =
y
1
, ..., f
( x
n
) =
y
n
интерполяционная формула Лагранжа имеет вид
где х
- значение аргумента функции, расположенного в интервале [ x
0
, x n
].
Необходимо отметить, что формула Лагранжа, в отличие от других интерполяционных формул, содержит явно y i
( i =
), что бывает иногда важно.
Пример 1.
Построить интерполяционный многочлен Лагранжа для функции, заданной следующей таблицей.
Заменив переменные x i
, y i
( i =
)их числовыми значениями, получим интерполяционный многочлен
Интерполирование по формуле Лагранжа связано с большим объемом вычислений, значительная часть которых повторяется при получении нескольких значений P n
( x
) для одной функции f
( x
) .
В том случае, когда формула Лагранжа используется для многократного получения значений одной функции при различных значениях аргумента, можно значительно уменьшить объем вычислений. Для этого формула Лагранжа представляется в виде
Произведение элементов i
-й строки обозначается через K i
. Отсюда лагранжевы коэффициенты вычисляются по формуле
где П n
+1
( x
) =
( x - x
0
)( x - x
1
)…( x - x n
) - произведение элементов главной диагонали таблицы (эти элементы подчеркнуты). Тогда формула Лагранжапринимает вид:
Использование формулы (2) позволяет сократить значительную часть вычислений по определению лагранжевых коэффициентов L i
( n
)
( x
)при различных значениях аргумента. Для этого произведение элементов i
-й строки таблицы разностей представляется как K i
= ( x
– x i
) D i
, где D i
- произведение всех элементов строки, кроме расположенного на главной диагонали. Величина D i
( i=
)не зависит от значения аргумента x
и может быть вычислена для заданной функции только один раз.
2. Интерполирование по схеме Эйткена
Итерационные методы интерполирования основаны на повторном применении некоторой простой интерполяционной схемы. Наиболее известным из итерационных методов является метод Эйткена, в основе которого лежит многократное применение линейной интерполяции.
В соответствии со схемой Эйткена линейная интерполяция по точкам 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.
3. Интерполяционные формулы Ньютона для равноотстоящих узлов
Узлы интерполирования x
0
, x
1
, ..., x n
называются равноотстоящими, если , где h
- шаг интерполирования. При этом для некоторой функции f
( x
) таблично задаются значения y i
= f
( x i
), где x i
= x
0
+ ih
.
Существуют две формулы Ньютона для случая равноотстоящих узлов интерполирования, которые называются соответственно первой и второй интерполяционными формулами Ньютона и имеют вид:
В этих формулах D i
y j
- конечные разности, где i
- порядок разности, j
- ее порядковый номер, а параметры t
и q
определяются следующим образом:
t
=
( x
-
x
0
) /
h
; q
=
( x
-
x n
) /
h
.
Конечные разности первого порядка вычисляются как D y j
= y j
+1
– y j
, где
j
=
, для более высоких порядков используется известная формула
Получаемые конечные разности удобно представлять в табличной форме записи, например, в виде табл. 1, которая называется горизонтальной таблицей конечных разностей.
Пepвая формула Ньютона применяется для интерполирования вперед и экстраполирования назад, т.е. в начале таблицы разностей, где строки заполнены и имеется достаточное число конечных разностей. При использовании этой формулы для интерполирования значение аргумента x
должно лежать в интервале [ x
0
, x
1
]. При этом за x
0
может приниматься любойузел интерполяции x k
с индексом , где m
- максимальный порядок конечных разностей.
Вторая формула Ньютона применяется для интерполирования назад и экстраполирования вперед, т.е. в конце таблицы конечных разностей. При этом значение аргумента x
должно находиться в интервале [ x n
-1
, x n
], причем за x n
может приниматься любой узел интерполирования .
Одно из важнейших свойств конечных разностей заключается в следующем. Если конечные разности i
–го порядка ( i < n
) постоянны, то функция представляет собой полином i
–й степени. Следовательно, формула Ньютона должна быть не выше i
-й степени. При использовании ЭВМ вычисление конечных разностей завершается при выполнении условий
где L
- число значащих цифр после запятой в представлении значений функции.
Необходимо отметить, что формулы Ньютона являются видоизменениямиформулы Лагранжа. Однако в формуле Лагранжа нельзя пренебречь ни одним из слагаемых, так как все они равноправны и представляют многочлены n
-й степени. В формулы Ньютона в качестве слагаемых входят многочлены повышающихся степеней, коэффициентами при которых служат конечные разности, разделенные на факториалы. Конечные разности, как правило, быстро уменьшаются, что позволяет в формулах Ньютона пренебречь слагаемыми, коэффициенты при которых становятся малыми. Это обеспечивает вычисление промежуточных значений функции достаточно точно спомощью простых интерполяционных формул.
4. Формула Ньютона с разделенными разностями
Первая и вторая формулы Ньютона предполагают, что узлы интерполирования являются равноотстоящими. Однако, в общем случае функция f
( x
) может быть задана таблицей, в которой узлы находятся на произвольном расстоянии друг от друга , где значения h i
( i
= ) являются различными.
При таких условиях первая и вторая интерполяционные формулы Ньютона неприменимы. В данном случае, для решения задачи интерполяции применяются не конечные, а разделенные разности.
Разделенная разность первого порядка определяется:
Для вычисления разделенных разностей высших порядков используется формула:
Разделенные разности удобно представлять диагональной таблицей, вид которой для n
= 4 соответствует табл. 2.
Представленная формула позволяет повышать точность вычислений постепенно, добавляя разделенные разности более высоких порядков. Следует отметить, что при этом все полученные результаты сохраняются, т.е. не вычисляются заново, а только наращиваются. Это следует из соотношения
Оценка погрешности интерполирования выполняется по формуле
Пусть задана таблица значений функции f
( x i
) = y i
( ), в которой они расположены по возрастанию значений аргумента: x
0
< x
1
< … < x n
. Чтобы построить кубический сплайн, требуется определить коэффициенты a i
0
, a i
1
, a i
2
, a i
3
, которые задают интерполяционный кубический многочлен
на каждом интервале интерполирования [ x i
-1
, x i
], .
Таким образом, необходимо определить 4 n
коэффициентов a ij
( , ), для чего требуется 4 n
уравнений. Необходимые уравнения определяются следующими условиями.
2. Условия непрерывности 1-х и 2-х производных функции:
Часто используются граничные условия вида Получаемый при этом сплайн называется естественным кубическим сплайном.
Задача определения кубического сплайна существенно упрощается при использовании многочлена Эрмита. Кубический многочлен Эрмита на интервале [ x i-
1
, x i
] определяется с помощью значений функции y i
-1
, y i
и ее производных y
¢ i
-1
, y
¢ i
. Так как значения производных в общем случае могут быть неизвестны, обозначим их как y
¢ i
-1
= S i
-1
; y
¢ i
= S i
. При построении сплайна переменные S
i
называются наклонами сплайна в соответствующих точках x i
.
Запишем многочлен Эрмита для интервала [ x i-
1
, x i
], где h i
= x i
- x i-
1
:
При таком выборе кубического многочлена автоматически выполняются условия непрерывности функции и ее первых производных:
Чтобы определить сплайн, нужно задать условия непрерывности второй производной:
Для записи этих условий в развернутом виде определим кубический многочлен Эрмита на интервале [ x i
, x i
+1
], где h i
+1
= x i
+1
- x i
:
Определим вторые производные многочленов Q i
( x
) и Q i
+1
( x
) в точке x
= x i
:
Отсюда условие непрерывности вторых производных имеет вид:
Это условие порождает систему линейных уравнений относительно наклонов сплайна S i
, которая содержит n
- 1 уравнение и n
+ 1 переменную. Чтобы определить два недостающих уравнения используются граничные условия. Например, для естественного кубического сплайна:
Указанные граничные условия могут быть получены из уравнения (5) для i
= 0 и из уравнения (4) для i
= n
соответственно. В развернутом виде:
Решение системы линейных уравнений, образованной условиями (6) и (7), позволяет вычислить наклоны сплайна S i
( i
= ) и определить кубический сплайн путем записи многочлена Эрмита для каждого интервала [ x i-
1
, x i
], i
= .
В вычислительной математике существенную роль играет интерполяция функций, т.е. построение по заданной функции другой (как правило, более простой), значения которой совпадают со значениями заданной функции в некотором числе точек. Причем интерполяция имеет как практическое, так и теоретическое значение. На практике часто возникает задача о восстановлении непрерывной функции по ее табличным значениям, например полученным в ходе некоторого эксперимента. Для вычисления многих функций оказывается эффективно приблизить их полиномами или дробно-рациональными функциями. Теория интерполирования используется при построении и исследовании квадратурных формул для численного интегрирования, для получения методов решения дифференциальных и интегральных уравнений.
1. В.В. Иванов. Методы вычислений на ЭВМ. Справочное пособие. Изд-во "Наукова думка". Киев. 1986.
2. Н.С. Бахвалов, Н.П. Жидков, Г.М. Кобельков. Численные методы. Изд-во "Лаборатория базовых знаний". 2003.
3. И.С. Березин, Н.П. Жидков. Методы вычислений. Изд. ФизМатЛит. Москва. 1962.
4. К. Де Бор. Практическое руководство по сплайнам. Изд-во "Радио и связь". Москва. 1985.
5. Дж. Форсайт, М.Мальком, К. Моулер. Машинные методы математических вычислений. Изд-во "Мир". Москва. 1980.
Название: Интерполирование функций
Раздел: Рефераты по математике
Тип: контрольная работа
Добавлен 22:42:53 07 января 2011 Похожие работы
Просмотров: 3372
Комментариев: 17
Оценило: 3 человек
Средний балл: 4.3
Оценка: неизвестно Скачать
Срочная помощь учащимся в написании различных работ. Бесплатные корректировки! Круглосуточная поддержка! Узнай стоимость твоей работы на сайте 64362.ru
Привет студентам) если возникают трудности с любой работой (от реферата и контрольных до диплома), можете обратиться на FAST-REFERAT.RU , я там обычно заказываю, все качественно и в срок) в любом случае попробуйте, за спрос денег не берут)
Да, но только в случае крайней необходимости.
Контрольная работа: Интерполирование функций
Владимир Короленко Сочинение
Квалификации Преступления Реферат
Дипломная работа: Облік аналіз і контроль оподаткування прибутку підприємства
Пример Славы Из Жизни Для Сочинения
Курсовая работа по теме Слухання музики як ефективний засіб розвитку музичних здібностей дітей дошкільного віку
Курсовая Работа На Тему Правовой Статус Некоммерческих Организаций
Курсовая работа по теме Стратегическое управление и его виды на примере компании "МЦ"
Реферат по теме Модель оптимизации структуры привлеченных ресурсов банка
Дипломная работа по теме Типология характеров и их экспериментальное исследование
Цивильное право, преторское право, право народов
Курсовая работа по теме Подсистема автоматизированного формирования маршрута обработки детали
Реферат: The Australian Stock Exchange Essay Research Paper
Реферат по теме Суть та види відтворення
Итоговое Сочинение Кого Можно Назвать Белой Вороной
Индивидом Рождаются Личностью Становятся Индивидуальность Отстаивают Сочинение
Сочинение Рассуждение Не Пускайте Рыжую На Озеро
Реферат: Формы развития научных знаний. Скачать бесплатно и без регистрации
Ответ на вопрос по теме Электроника
Реферат: Формирование системы мотивации трудовой деятельности подсистемы трудовых отношений
Сочинение О Чехове 10 Класс
Реферат: Способы получения сложных эфиров. Конденсации формальдегида с изобутиленом. Различные способы получения фенола
Дипломная работа: Проблемы и перспективы развития социальных отношений в современной России
Реферат: Кризис 1998 года