Лабораторная работа 3.2

ИНТЕРПОЛИРОВАНИЕ И АППРОКСИМАЦИЯ ФУНКЦИЙ

В точках

заданы значения функции

Аналитическое выражение для функции не известно. Требуется приближенно вычислить значение функции в точке .

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

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

. (1)

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

Мы в качестве базисных будем выбирать степенные функции

Существуют два подхода к определению коэффициентов в выражении (1). Соответственно этому определяются методы приближения функции - интерполирование и аппроксимация:

интерполирование (интерполяция) - коэффициенты определяются из условия

(2)

В этом случае . Функция называется интерполирующей, точки - узлами интерполяции;

аппроксимация - условие (2) заменяется более мягким условием: функция должна минимально отличаться от функции на отрезке . В этом случае . Функция называется аппроксимирующей функцией.

Рассмотрение вопросов интерполирования и аппроксимации следует ниже.

ПОЛИНОМИАЛЬНАЯ ИНТЕРПОЛЯ ЦИЯ

Интерполирующая функция ищется в виде полинома степени

. (3)

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

НЕ нашли? Не то? Что вы ищете?

(4)

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

Для вычисления значений интерполяционного полинома не обязательно решать систему (4). Существует множество различных формул для полиномиальной интерполяции. Наиболее общей из них является формула Лагранжа

;

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

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

Вычисляем конечные разности первого порядка

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

Затем вычисляем конченые разности третьего порядка и т. д. Разности k – го порядка определяются выражениями

Таблица конечных разностей имеет вид

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

(6)

где - обобщенная степень:

Введем переменную . Выражение (6) можно переписать в виде

. (7)

Выражения (6), (7) называются первой интерполяционной форму-

лой Ньютона или формулой Ньютона для интерполирования вперед.

Вторая интерполяционная формула Ньютона (формула Ньютона для интерполирования назад) имеет вид

где

При обе интерполяционные формулы Ньютона переходят в разложение функции по формуле Тейлора.

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

Подчеркнем еще раз: существует единственный многочлен степени , принимающий в заданных точках заданные значения. Таким образом, при одних и тех же формулы Ньютона (6), (7), (8), формула Лагранжа (5) есть разные формы записи одного и того же многочлена (3).

Запись интерполяционного многочлена в форме Ньютона позволяет сделать некоторые выводы о степени многочлена. Имеем

При достаточно малом конечные разности убывают по абсолютной величине с ростом порядка разности.

С другой стороны, величины заданы в компьютере с некоторой погрешностью. Пусть погрешность не превосходит . Тогда погрешность разностей может достигать величины 2, погрешность разностей - величины 22 и т. д. Погрешность разностей может достигать величины 2k. Возможна ситуация, когда конечные разности могут стать меньше величины возможной погрешности. Пусть для некоторого k выполняются условия

по крайней мере для некоторых ;

для всех (9)

В этом случае использование в формулах Ньютона конечных разностей порядка выше k лишено смысла - они практически не содержат информации о функции . Иными словами, использование интерполяционного многочлена степени выше k в описанных условиях не имеет смысла. Более того, повышение степени интерполяционного многочлена может ухудшить точность интерполяции, т. к. разности порядка выше k практически содержат только погрешности.

Разности в условиях (9) называются практически равными нулю, разности - практически постоянными.

КУСОЧНАЯ ИНТЕРПОЛЯ ЦИЯ.

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

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

Интерполяционные формулы Ньютона (6), (7), (8) разработаны в первую очередь для такого способа интерполирования. Пусть мы используем для интерполяции конечные разности по включительно (m<n). Т. е. степень интерполяционного многочлена равна m.

Для функцию вычисляем по формуле для интерполирования вперед, аналогичной формуле (7). Для "роль" "выполняет" узел , вычисления проводятся по формуле, аналогичной (7), и т. д. Для заданного х определяем i из условия . Для функцию вычисляем по формулам

(10)

С ростом х полином (10) "движется" вдоль отрезка .

Выражения (10) определены для , при разность не определена. Для функцию вычисляем по формуле для интерполирования назад: определяем j из условия ; для функцию вычисляем по формулам (см. (8)):

; (11)

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

СПЛАЙН - ИНТЕРПОЛЯ ЦИЯ

Сплайнами (полиномиальными сплайнами) называют функции, "склеенные" из "кусков" многочленов, непрерывные на отрезке и имеющие на этом отрезке непрерывные производные. Точнее, непрерывная на отрезке функция называется полиномиальным сплайном (или просто сплайном) порядка m с узлами

если:

- на каждом из отрезков есть алгебраический многочлен степени m ;

- в узлах интерполяции функция имеет непрерывные производные по включительно;

- в каждой точке производная может иметь разрыв.

Говорят, что сплайн порядка m имеет дефект k. Множество всех таких сплайнов на отрезке обозначают .

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

(12)

(13)

(14)

На отрезке функция будет иметь вид:

. (15)

Коэффициенты определяются из условий (12)-(14). Т. о. для задания функции необходимо решить систему из линейных алгебраических уравнений с неизвестными. (Отметим, что условия (дают нам только уравнения). Задача резко упрощается, если использовать специальную форму записи полинома (15).

Если на отрезке функцию искать в виде:

, (16)

где

, (17)

то условия (12) и (14) выполняются автоматически. Условия (13) дают нам систему уравнений для определения коэффициентов

.(18)

Система (18) дает нам уравнение для определения неизвестных коэффициентов . Для обеспечения единственности решения необходимы дополнительные условия. Эти условия могут определяться, например, условиями задачи. Обычно при интерполировании используются условия, называемые естественными:

(19)

Уравнения (18) и (19) образуют систему с трехдиагональной матрицей. Система легко решается методом прогонки.

Для вычисления значений необходимо определить i из условия и затем вычислить значение полинома (16).

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

АППРОКСИМАЦИЯ ФУНКЦИЙ

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

Итак, функцию ищем в виде линейной комбинации базисных функций (см. (1))

(20)

коэффициенты определяются из условия

(21)

Функция называется аппроксимирующей. Метод определения коэффициентов функции называется методом наименьших квадратов.

Если , то функция превращается в интерполирующую: .

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

Перейдем к определению коэффициентов . Из (20) и (21) получаем

Необходимым условием минимума функции является обращение в нуль ее первых производных: , . Имеем:

или, изменив порядок суммирования,

Приравняв это выражение к нулю, получаем систему линейных уравнений для определения коэффициентов

, (22)

где

(23)

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

. (24)

Итак, коэффициенты аппроксимирующего многочлена ищутся как решение системы (22), коэффициенты которой даются выражениями (24). Значение полинома вычисляется по формуле

ЧИСЛЕННОЕ ДИФФЕРЕНЦИРОВАНИЕ И ИНТЕГРИРОВАНИЕ

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

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

Для приближенного вычисления интегралов методы интерполирования и аппроксимации являются основными методами.

Для приближенного вычисления интеграла

функция на отрезке заменяется интерполирующей (аппроксимирующей) функцией и вычисляется интеграл от этой функции.

Рассмотрим один из наиболее часто встречающихся методов численного интегрирования - метод Симпсона. Схема метода заключается в следующем:

- интервал разбиваем на подинтервалов, имеем

- на отрезке функцию заменяем интерполяционным полиномом Лагранжа степени , получаем

;

где

; .

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

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

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

ЗАДАНИЯ

1. Проинтерполировать функцию Рунге

на отрезке многочленом степени по равностоящим узлам

Использовать многочлен Лагранжа. Вычислить среднюю квадратическую погрешность по точек.

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

УКАЗАНИЕ: средней квадратической погрешностью называется корень квадратный из среднего квадрата отклонения приближенного значения функции в узлах от точного

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

2. Выполнить кусочную интерполяцию функции Рунге

на отрезке . Для этого:

- вычислить значения функции в точках

;

- для отрезков построить свои интерполяционные полиномы.

Использовать подпрограмму вычисления значений многочлена Лагранжа по узлам . Вычислить среднюю квадратическую погрешность по точек.

Повторить расчеты для отрезков .

Сравнить с интерполяционным полиномом степени по всем узлам интерполяции.

Представить графики исходной и интерполирующей функций.

3. Вычислить значения функции Рунге

в точках .

Используя схему "движущегося" (по узлам ) полинома Лагранжа проинтерполировать функцию Рунге на отрезке полиномом степени m. Определить среднюю квадратическую погрешность по точек.

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

4. Вычислить значения функции Рунге

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

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

5. Вычислить значения функции Рунге

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

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

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

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

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

"Естественные" условия (19) заменить на реальные (для функции ) условия и повторить расчет.

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

8. Числа вещественного типа представляют в компьютере как числа "с плавающей точкой"

, где , - целое.

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

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

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

Примечание: В компьютере ищется как решение уравнения итерационным методом Ньютона.

9. В компьютере числа вещественного типа представляются в виде "с плавающей точкой"

, где , - целое.

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

Для вычисления достаточно вычислить и к порядку результата прибавить . Для вычисления используем интерполяционный полином степени n по n+1 равноотстоящим узлам. Для оценки погрешности интерполяции используем среднюю квадратическую погрешность по точек.

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

10. В компьютере числа вещественного типа представляются в виде "с плавающей точкой"

, где , - целое.

Для вычисления функцию преобразуем к виду

Для вычисления используем интерполяционный полином степени n по n+1 равностоящим узлам. Для оценки погрешности интерполяции используем среднюю квадратическую погрешность по точек.

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

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

11. В ходе химического эксперимента получены следующие семь пар данных

t	-1.000	-0.960	-0.860	-0.790	0.220	0.500	0.930
y	-1.000	-0.151	0.894	0.986	0.895	0.500	-0.306

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

12. По данным задачи 11 построить аппроксимирующие полиномы степеней 2, 3, 4, построить кубический сплайн. Представить графики полиномов и сплайна, отметить на графике заданные точки. Проанализировать графики.

13. Моделируем получение экспериментальных данных:

- в точках вычисляем значения функции

;

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

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

Выполнить расчеты для n=10 и d=0.1, 0.05, 0.01.

14. То же, что в задаче 13. Расчеты выполнить для и .

15. Смоделировать получение экспериментальных данных (см. задачу 13). По полученным данным построить аппроксимирующие полиномы 2-й и 3-й степени и кубический сплайн. Определить средние квадратические погрешности по точек. Представить графики функции , аппроксимирующих и интерполирующих функций, отметить на графике заданные точки.

Выполнить расчеты для и .

16. То же, что в задаче 15. Расчеты выполнить для и .

17. В точках вычислить значения функции

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

Расчеты провести для n=10, 20, 50.

18. Дано n экспериментальных точек . С помощью метода наименьших квадратов найти параметры наилучшего приближения a, b для аппроксимирующих функций

a) y=ax+b; b) y=aebx; c) y=a+b/x;

d) y=axb; e) y=a ln x+b; f) y=1/(ax+b).

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

19. В узлах xi = -10 + i, i = 0, 1, ¼ , 20 заданы значения функции

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

20. В узлах xi = -10 + i, i = 0, 1, ¼ , 20 заданы значения функции

21. Вычислить по методу Симпсона с точностью до e интеграл

Сравнить с точным значением. Указать шаг и число точек, при которых достигается заданная точность.

Выполнить расчеты для e=10-2, 10-3, 10-4, 10-5.

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

построив кубический сплайн и взяв интеграл от сплайна. Вычислить интеграл по формуле Симпсона. Указать погрешности вычислений.

Выполнить расчеты для .

23. Для приближенного решения интегрального уравнения

применим метод интерполирования.

Решение ищем в точках . Для x=xi имеем

или

На отрезке функцию заменяем полиномом Лагранжа степени 2. Имеем

Вычислив интегралы

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

Используя предложенную методику найти приближенное решение интегрального уравнения

Точное решение уравнения: . Вычислить среднюю квадратическую погрешность по точек.

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

24. Для приближенного решения интегрального уравнения

используем кубический сплайн.

Решение ищем в точках . Заменив под знаком интеграла функцию u(t) сплайном S(t) для x = xi (i=0, 1, ¼ , n) получаем

где .

Решив полученную систему линейных уравнений совместно с системой, определяющей коэффициенты сплайна, относительно неизвестных ui (i=0, ¼ , n) и si (i=0, ¼ , n) получим приближенные значения функции в заданных точках и коэффициенты сплайна. Значения функции в промежуточных точках вычисляются сплайн-интерполяцией.

Используя предложенную методику найти приближенное решение интегрального уравнения

Точное решение уравнения . Вычислить среднюю квадратическую погрешность по точек.

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

25. Приближенное (довольно грубое) решение задачи Коши

y'=f(x, y), y(a)=ya

в точках xi=a+ih, i=0, 1, ¼ можно получить методом Эйлера

y0=ya; yi+1=yi+h f(xi, yi), (yi=y(xi)), i=0, 1, ¼ .

Используя метод Эйлера найти приближенное решение задачи Коши

у' = - у, у(0)=1

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

Точное решение задачи: .

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

Выполнить расчеты для n=10, 20, 50.

26. Применим метод Эйлера (см. задачу 25) для приближенного решения задачи Коши

Для этого дифференциальное уравнение второго порядка представим в виде системы уравнений

К системе уравнений применим метод Эйлера. Ищем приближенное решение в точках полагаем

Используя метод Эйлера найти приближенное решение задачи

на отрезке в точках . Проинтерполировать по полученным точкам функцию многочленом Ньютона 2-й степени. Вычислить среднюю квадратическую погрешность по точек.

Выполнить расчеты для n=20, 50, 100. Представить графики функций. Отметить на графиках полученные точки.

27. Разработать программу приближенного решения краевой задачи

на отрезке с помощью кубического сплайна.

Указание: ищем решение в точках

Подставив сплайн в уравнение и положив получим систему линейных уравнений относительно неизвестных yi и коэффициентов сплайна. Дополнительные уравнения дают граничные условия: y0=ya, yn=yb. Решив полученную систему уравнений совместно с системой, определяющей коэффициенты сплайна, получим значения функции yi и коэффициентов сплайна si. "Естественные" условия из системы отбрасываются – они заменяются граничными условиями.