Моделирование интерполяции

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

Пусть на отрезке задана сетка со и в ее узлах заданы значения функции , равные .

Требуется построить функцию , совпадающую с функцией в узлах сетки: .

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

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

Часто не возникает необходимости иметь коэффициенты многочлена, а надо лишь найти значения функции в промежуточных точках. В этом случае удобно использовать многочлен Лагранжа. Пусть в точках х₀, х₁,… х_n заданы значения функции y₀, y₁,… y_n. Надо найти значения функции в любой промежуточной точке x. Многочлен Лагранжа имеет вид:

y = L(x) и будет искомым значением функции в точке х. Эту формулу можно записать в общем виде:

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

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

R(x) = f(x) - ?(x),

R(x) - называется остаточным членом интерполяционной формулы. Оценим его значение. Если функция f(x) непрерывна и имеет непрерывные производные до n+1 порядка включительно, то остаточный член многочлена Лагранжа степени n имеет вид:

Здесь f ⁽ⁿ⁺¹⁾(x.) - производная n+1 порядка функции f(x) в некоторой точке, принадлежащей интервалу [x₀; x_n]. Эта точка неизвестна. Если максималное значение производной этого порядка на интервале равно M _n+1, то можно записать:

Посмотрим, от чего зависит эта погрешность. С одной стороны, чем выше степень многочлена, меньше погрешность, так во многих случаях и есть. Но иногда значения производной высокого порядка бывают велики. Такую ситуацию впервые обнаружил Рунге. Он строил на отрезке [-1; 1] интерполяционный многочлен с равномерным распределением узлов для функции

1 / (1+25 x²). Оказалось, что с увеличением степени многочлена его значения расходятся с функцией для любой точки 0,7<|x|<1.

Кроме того, на погрешность влияет расположение узлов. При очень близком расположении некоторых точек может возникнуть разность близких чисел, что может привести к большим погрешностям.

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

Методы и алгоритмы глобальной, локальной и линейной интерполяций

Глобальная интерполяция. Построим многочлен на отрезке [x₀; x_n], график которого должен проходить через все заданные точки:

ф(x)=a₀ + a₁x + a₂x² + … + a_nxⁿ

Многочлен имеет n+1 коэффициент и степень n, т.е. многочлен должен иметь степень на единицу меньше количества точек. Задача состоит в нахождении коэффициентов многочлена. Из условий равенства f(x_i)=ф(x_i)? для всех точек можно записать этот многочлен для каждой точки:

a₀ + a₁x₀ + a₂x₀²+ … +a_nx₀ⁿ = y₀;

a₀ + a₁x₁ + a₂x₁²+ … +a_nx₁ⁿ = y₁;

a₀ + a₁x_n + a₂x_n²+ … +a_nx_nⁿ = y_n;

Получили систему n+1 линейных уравнений. Система имеет единственное решение, если определитель неравен нулю. Определитель системы имеет вид:

1 x₀ x₀² … x₀ⁿ

1 x₁ x₁² … x₁ⁿ

1 x_n x_n² … x_nⁿ

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

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

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

Локальная интерполяция.

При локальной интерполяции для каждого интервала строится своя функция. Рассмотрим линейную интерполяцию. Задана точка x (i=1, 2, 3….n) на отрезке [a; b] и значения функции в этих точках y(i). Запишем уравнение прямой на i - том интервале, проходящей через точки (x_i-1, y_i-1) и (x_i, y_i):

(y-y_i-1) / (y_i-y_i-1) = (x-x_i-1) / (x_i-x_i-1)

Отсюда

y = y_i-1 + (y_i-y_i-2) * (x-x_i-1) / (x_i-x_i-1)

По этой формуле можно определить функцию y в лубой точке. Но сначала надо определить в какой интервал отрзка [a; b] попадет искомая точка, т.е. определитель i.

Линейную интерполяцию применяют, если функция близка к линейной или узлы интерполяции находится достаточно близко между собой.

Алгоритм локальной интерполяции по формуле Лагранжа

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

n - количество узлов интерполяции;

a, b - соответственно левый и правый концы интервала;

x (n), y (n) - массивы узлов интерполяции;

xk - точка, в которой надо найти значение функции;

yk - значение интерполяционного многочлена в точке xk;

nn, nk - соответственно номера 1 - ой и последней точек интерполяционного многочлена.

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

2. Инструкция пользования программой

Для запуска программы необходимо открыть лист EXCEL, затем нажать на клавишу ALT и F11 одноременно. Затем появится окно для напиcания программы для языке Visual Basic.

Сначала рассмотрим запись на Visual Basic по методу глобальной интерполяции:

· вводим массивы узлов интерполяции, количество узлов интерполяции и точку, в которой надо найти промежуточное значение;

· переводим формулу Лагранжа (2) на язык программирования для Visual Basic и записываем;

· вводим адрес ячейки для вывода на лист EXCEL, в которую выйдет значение промежуточной точки (уk).

Теперь рассмотрим запись по методу линейной интерполяции:

· вводим массивы узлов интерполяции, количество узлов интерполяции и точку, в которой надо найти промежуточное значение;

· находим номера точек;

· записываем формулу для нахождения промежуточной точки (уk);

· вводим адрес ячейки для вывода на лист EXCEL.

Запись по методу локальной интерполяции:

· обращаем формулу Лагранжа для локальной интерполяции к функции и записываем;

· вводим массивы узлов интерполяции, количество узлов интерполяции и точку, в которой надо найти промежуточное значение;

· находим номера точек;

· вводим условия для значений nn и nk;

· вводим адрес ячейки для вывода на лист EXCEL.

Исходные данные и результат решения контрольного примера

1. Вводные данные:

Задача:

Вычислить значение функции между всеми точками методами:

1. Лагранжа как глобальную интерполяцию;

2. Лагранжа как локальную интерполяцию;

3. линейной интерполяции.

2. График функции вводных данных:

Рис. 1