Пример: Транспортная логистика
Я ищу:
На главную  |  Добавить в избранное  

Математика /

Интерполяция многочленами



Скачать реферат


Введение

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

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

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

Всё изложенное можно сформулировать в виде четырёх вопросов:

1. Какие узлы мы будем использовать?

2. Какой класс приближающих функций мы будем использовать?

3. Какой критерий согласия мы применим?

4. Какую точность мы хотим?

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

Что касается критерия согласия, то классическим критерием согласия является «точное совпадение в узловых точках». Этот критерий имеет преимущество простоты теории и выполнения вычислений, но также не-удобство из-за игнорирования шума (погрешности, возникающей при из-мерении или вычислении значений в узловых точках). Другой относи-тельно хороший критерий — это «наименьшие квадраты». Он означает, что сумма квадратов отклонений в узловых точках должна быть наимень-шей возможной или, другими словами, минимизирована. Этот критерий использует ошибочную информацию, чтобы получить некоторое сглажи-вание шума. Третий критерий связывается с именем Чебышева. Основная идея его состоит в том, чтобы уменьшить максимальное отклонение до минимума. Очевидно, возможны и другие критерии.

Более конкретно ответить на поставленные 4 вопроса можно лишь исходя из условий и цели каждой отдельной задачи.

Интерполяция многочленами

Цель задачи о приближении (интерполяции): данную функцию у(х) требуется приблизительно заменить некоторой функцией (х), свойства которой нам известны так, чтобы отклонение в заданной области было наименьшим. интерполяционные формулы применяются, прежде всего, при замене графически заданной функции аналитической, а также для ин-терполяции в таблицах.

Методы интерполяции Лагранжа и Ньютона

Один из подходов к задаче интерполяции — метод Лагранжа. Основ-ная идея этого метода состоит в том, чтобы прежде всего найти много-член, который принимает значение 1 в одной узловой точке и 0 во всех других. Легко видеть, сто функция

является требуемым многочленом степени n; он равен 1, если x=xj и 0, ко-гда x=xi, ij. Многочлен Lj(x)yj принимает значения yi в i-й узловой точке и равен 0 во всех других узлах. Из этого следует, что есть многочлен степени n, проходящий через n+1 точку (xi, yi).

Другой подход — метод Ньютона (метод разделённых разностей). Этот метод позволяет получить аппроксимирующие значения функции без построения в явном виде аппроксимирующего полинома. В результате по-лучаем формулу для полинома Pn, аппроксимирующую функцию f(x):

P(x)=P(x0)+(x-x0)P(x0,x1)+(x-x0)(x-x1)P(x0,x1,x2)+…+

(x-x0)(x-x1)…(x-xn)P(x0,x1,…,xn);

— разделённая разность 1-го по-рядка;

— разделённая разность 2-го порядка и т.д.

Значения Pn(x) в узлах совпадают со значениями f(x)

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

Сплайн-аппроксимация

Другой метод аппроксимации — сплайн-аппроксимация — отличает-ся от полиномиальной аппроксимации Лагранжем и Ньютоном. Сплайном называется функция, которая вместе с несколькими производными непре-рывна на отрезке [a, b], а на каждом частном интервале этого отрезка [xi, xi+1] в отдельности являются некоторым многочленом невысокой степени. В настоящее время применяют кубический сплайн, то есть на каждом ло-кальном интервале функция приближается к полиному 3-го порядка. Трудности такой аппроксимации связаны с низкой степенью полинома, поэтому сплайн плохо аппроксимируется с большой первой производной. Сплайновая интерполяция напоминает лагранжевую тем, что требует только значения в узлах, но не её производных.

Метод наименьших квадратов

Предположим, что требуется заменить некоторую величину и делает-ся n измерений, результаты которых равны xi=x+i (i=1, 2, …, n), где i — это ошибки (или шум) измерений, а х — истинное значение. Метод наи-меньших квадратов утверждает, что наилучшее приближённое значение есть такое число, для которого минимальна сумма квадратов отклонений от :

Один из наиболее общих случаев применения этого метода состоит в том, что имеющиеся n наблюдений (xi, yi) (i=1, 2, …, n) требуется прибли-зить многочленом степени m




Copyright © 2005—2007 «Mark5»