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

9

МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ УКРАИНЫ

Севастопольский национальный технический университет

МЕТОДИЧЕСКИЕ УКАЗАНИЯ

к выполнению лабораторной работы «ИНТЕРПОЛИРОВАНИЕ ФУНКЦИЙ ПОЛИНОМАМИ» по дисциплине «Вычислительные

методы» для самостоятельной работы студентов специальности

7.0914.01 «Системы управления и автоматики»

Севастополь - 2000


Методические указания утверждены на заседании кафедры технической кибернетики, протокол № 8 от 16.06.2000

Методическое указание составил: ст. преп. Захаров В.В.

Рецензент: к.т.н., доцент Карапетьян В.А.


  1. ЦЕЛЬ РАБОТЫ

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

  1. ОБЪЕКТ ИССЛЕДОВАНИЯ

Интерполирование - это приближённое определение значений функции f(x) в промежуточных точках заданного замкнутого интервала xB x xE изменения её аргумента x по известным значениям f(x1), f(x2),…, f(xm). Значения аргумента xi[xB, xE] , i=1,2…,m интерполируемой функции f(x) называются узлами интерполяции.

Интерполирование функции f(x) полиномом означает построение такого полинома минимальной степени Fm(x), который в m узлах интерполяции удовлетворяет условиям:

f(k)(xi) = Fm(k)(xi) , i = 1,2,…,m , k = 0,1,…,mi-1 . (1)

Здесь f(k)(xi) – известные значения функции f(x) и её производных k- ого порядка f(k)(x) в узлах интерполяции, а mi – кратность i- ого узла. Если mi=1, i-тый узел называется простым.

Интерполирование функций f(x) полиномом с простыми узлами (mi=1, i =1,2,…,m) означает построение такого полинома минимальной степени Fm(x), который в m узлах интерполяции удовлетворяет условиям:

f(xi) = Fm(xi) , i = 1,2,…,m .

Легко показать [], что из определения (1) интерполированого полинома Fm(x) следует его единственность. Позтому различные численные методы интерполирования функций полиномами позволяют построить суть разные формы представления единственного интерполированого полинома. В данной работе рассматриваются два наиболее известных из них - методы Лагранжа и Ньютона.

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

Функция

, (2)

для которой необходимо построить интерполяционный полином Fm(x) в форме Лагранжа или Ньютона на интервале 0 x 1 изменения аргумента x, задана аналитически. Это даёт возможность при любом значении x[0,1] вычислить величину абсолютной ошибки интерполирования

(3)

и, таким образом, провести полное исследование зависимости точности интерполирования от количества узлов интерполирования m и расположения точки x относительно узлов интерполирования xi. Значения коэффициентов c1, c2, c3, c4, c5 и форма представления интерполяционного полинома определены вариантом задания. Таблица вариантов приведена в разделе «Приложение».

В работе предполагается, что узлы xi - простые и расположены равномерно на интервале [0,1]. При этом первый x1 и последний xm узлы находятся на концах интервала (x1=0, xm=1), так что шаг интерполирования h (расстояние между двумя соседними узлами) является величиной постоянной на интервале [0,1] и определяется формулой

h = 1/(m1) ,

а узлы - формулой

xi = (i1) h , i=1,2,…,m . (4)

Интерполяционный полином Лагранжа [1,2] может быть представлен в виде

Fm (x) = , (5)

где

, (6)

qi = f (xi) /i (xi) , (7)

а интерполяционный полином Ньютона [1,2] - в виде

Fm (x) = , (8)

где

, i (x,0) = 1 . (9)

Коэффициенты аi интерполяционного полинома Ньютона определяются как решение системы линейных алгебраических уравнений с нижней треугольной матрицей коэффициентов, которая получается при подстановке (8) в (1). В случае равномерного расположения узлов коэффициенты аi определяются аналитически через конечные разности значений функции f(x) в узлах интерполирования (4) формулой

. 10)

Поскольку коэффициенты (7),(10) интерполяционного полинома Fm(x) для обоих форм (5),(8) не зависят от x, они могут быть вычислены один раз и запомнены в памяти ПК. Затем подсчитанные значения коэффициентов могут многократно использоваться при вычислении приближенных значений функции f(x) c помощью полинома Fm(x) при разных значениях аргумента x[0,1]. Однако, следует заметить, что при изменении границ интервала интерполирования, либо количества узлов m или их разпололожения коэффициенты (7),(10) приходится вычислять заново.

Из (5),(6) и (8),(9) соответственно следует, что представление интерполяционного полинома Fm(x) в форме Лагранжа (5) суть линейная комбинация m полиномов i(x) степени m-1, а в форме Ньютона (8) - m полиномов (x,i), i{0,1,…,m-1} разных степеней i. Кроме того, полиномы (x,i) допускают возможность их рекуррентного вычисления по формуле

(x, i) = (x, i-1)·(x-xi) , i=1,2,…, m-1 , (x,0) = 1 ,

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

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

zi = (i-1)·0,01 , i = 1,2,…,101 (11)

и определить оценку ошибки интерполирования функции (2) на заданном интервале [0,1], как

e = |E(zi)| . (12)

Ошибка интерполирования (3) полиномом с m простыми узлами может быть также представлена в виде [1]:

. (13)

Вычислить величину ошибки по формуле (13) не удаётся, так как значение

точно не определено [1]. Кроме того, для применения (13) необходимо получить формулу или алгоритм вычисления m -той производной от функции f(x).

Обычно (13) заменяется приближенной оценкой [2]

. (14)

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

xm+1 = m·h .

  1. ПРОГРАММА ИССЛЕДОВАНИЙ

При выполнении лабораторной работы необходимо, в соответствии с вариантом индивидуального задания, составить и отладить программу для ПК. Язык программирования (Паскаль или Си) и номер варианта задания определяет ведущий преподаватель. Варианты заданий приведены в таблице раздела «Приложение».

С помощью составленной программы необходимо выполнить следующие расчеты и исследования:

3.1. Исследовать зависимость поведения интерполяционного полинома Fm(x) и ошибки интерполирования (3) при разных значениях m от:

  1. кривизны функции f(x) на разных участках интервала [0,1] ;
  2. расположения значения аргумента x относительно узлов интерполирования (4).

Для этого следует посчитать при нескольких значениях m и вывести на печать для каждого m таблицу значений функции f(zi), интерполяционного полинома Fm(zi) и ошибки интерполирования E(zi) (3) в точках zi = (i-1) 0,05 , i=1,2,…,21 интервала интерполирования [0,1]. По таблицам необходимо построить графики функции f(x), а также графики полиномов Fm(x) и ошибок интерполирования (3) при нескольких значениях m.

  • Дополнительное задание по НИРС.

Вычислить в точках zi=(i-1)·0,05, i=1,2,…,21 интервала интерполирования [0,1] и вывести на печать также значения приближенной оценки (14) ошибки оценивания и исследовать степень ее близости к точной оценке (3). Для сравнения (3) и (14) построить соответствующие графики.

3.2. Исследовать зависимость поведения ошибки интерполирования (3) и ошибки интерполирования на интервале (12) от m.

Для этого необходимо воспользоваться таблицами и графиками подраздела 3.1, а также подсчитать и построить график зависимости ошибки интерполирoвания на интервале (12) от количества узлов интерполирования m.

  • Дополнительное задание по НИРС.

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

Для выполнения исследований рекомендуется составить программу в соответствии со следующим алгоритмом:

  1. ввод с терминала значения m и вывод его на печать;
  2. подсчёт и запоминание в массиве значений коэффициентов интерполяционного полинома Fm(x);
  3. вычисление в цикле при zi=(i-1)·0,01 , i = 1,2,…,101 значений функции, полинома и ошибки интерполирования (3). На каждом шаге цикла пересчитывается оценка ошибки интерполирования на интервале (12), а через каждые пять шагов выводится строка таблицы, описанной в подразделе 3.1 с соответствующим значением аргумента;
  4. после окончания цикла выводится на печать значение оценки ошибки интерполирования на интервале (12).

При проведении расчетов на ПК рекомендуется вначале взять m=2. Затем нужно повторить вычисления с большими значениями m, пока оценка ошибки интерполирования на интервале (12) не станет меньшей, чем величина 10 -3. Вычисления следует повторить не более трех-пяти раз.

  1. ВАРИАНТЫ ЗАДАНИЙ

№ варианта

С1

С2

С3

С4

С5

Форма

Fm(x)

1

0

0,5

4,6

-1,87

0,65

Лагранжа

2

0

0,5

0,4

-2,47

1,46

-'-

3

0

0,5

4

-4,688

1,56

-'-

4

0,2

0

-2,5

1,87

-0,559

-'-

5

0,2

0

-3,5

2,79

-0,725

-'-

6

0,2

0

-2,9

1,054

-0,136

-'-

7

0,205

-0,1

-2,6

0,942

-0,1375

-'-

8

0,205

-0,1

-1,5

0,542

-0,113

-'-

9

0

0,5

4,6

-1,87

0,65

Ньютона

10

0

0,5

0,4

-2,47

1,46

-'-

11

0

0,5

4

-4,688

1,56

-'-

12

0,2

0

-2,5

1,87

-0,559

-'-

13

0,2

0

-3,6

2,79

-0,725

-'-

14

0,2

0

-2,9

1,054

-0,136

-'-

15

0,205

-0,1

-2,6

0,942

-0,1375

-'-

16

0,205

-0,1

-1,5

0,542

-0,113

-'-

17

0

0,5

4,6

-1,87

0,65

Лагранжа

18

0

0,5

0,4

-2,47

1,46

-'-

19

0

0,5

4

-4,688

1,56

-'-

20

0,2

0

-2,5

1,87

-0,559

-'-

21

0,2

0

-3,5

2,79

-0,725

-'-

22

0

0,5

4,6

-1,87

0,65

Ньютона

23

0

0,5

0,4

-2,47

1,46

-'-

24

0

0,5

4

-4,688

1,56

-'-

25

0,2

0

-2,5

1,87

-0,559

-'-

26

0,2

0

-3,6

2,79

-0,725

-'-

  1. СОДЕРЖАНИЕ ОТЧЕТА

Отчёт составляется один на бригаду на бумаге формата А4. Схемы программ должны соответствовать ГОСТ 19.002-80Б 19.003-80(3). Графики желательно выполнять на миллиметровой бумаге формата A4. На титульном листе должны быть приведены номера группы, бригады, фамилии и инициалы авторов. Отчет должен содержать:

  1. Постановку задачи, основные формулы и исходные данные.
  2. Описание алгоритма программы в виде схемы.
  3. Описание назначения переменных программы.
  4. Черновик текста программы с подписями преподавателя о допуске к отладке и выполнению расчетов нам ПК.
  5. Распечатки текста отлаженной программы и результатов вычислений.
  6. Графики, перечисленные в подразделах 3.1, 3.2.
  7. Выводы по результатам исследований, предусмотренных программой раздела 2.

  1. КОНТРОЛЬНЫЕ ВОПРОСЫ

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

  1. ЛИТЕРАТУРА

  1. Бахвалов Н.С. Численные методы, т.1. - М.: Наука, 1976. - 631 с.
  2. Хемминг Р.В. Численные методы для научных работников и инженеров .-М.: Наука, 1968. - 400 с.
  3. Пантелеева З.Т. Графика вычислительных процессов . - М.: Финансы и статистика, 1983. - 167 с.

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