644_Galkina_M.JU._Vychislitel'naja_matematika_

Федеральное агентство связи

Федеральное государственное бюджетное образовательное учреждение высшего образования «Сибирский государственный университет телекоммуникаций и информатики» (СибГУТИ)

М. Ю. Галкина

Вычислительная математика

Практикум

Новосибирск

2016

1

УДК 519.6 (075.8)

Утверждено редакционно-издательским советом СибГУТИ

Рецензент доц. Т.Э. Захарова

Галкина М.Ю. Вычислительная математика: Практикум / Сибирский государственный университет телекоммуникаций и информатики. – Новосибирск, 2016. – 41 с.

В практикуме содержатся 5 лабораторных и курсовая работа для самостоятельного выполнения студентами. К каждой работе имеются методические указания по выполнению.

Пособие предназначено для студентов заочной формы обучения, обучающихся по направлению 09.03.01 «Информатика и вычислительная техника» и изучающих дисциплину «Вычислительная математика».

В авторской редакции

©Галкина М.Ю., 2016

©Сибирский государственный университет телекоммуникаций и информатики, 2016

3

1. ИНТЕРПОЛЯЦИЯ

1.1.Задача интерполяции

Пусть известны значения функции f в n + 1 различной точке х0, х1, х2… хn

(х0 < х1 < х2 < … < хп): у0 = f(х0), у1 = f(х1), … уn = f(хn). Например, эти значения найдены из эксперимента или найдены с помощью достаточно сложных вычислений. Возникает задача приближенно восстановить функцию f в произвольной точке x. Для решения такой задачи строится алгебраический многочлен Ln(x)

степени n, который в точках xi принимает те же значения yi, что и функция f(x), т.е.

Ln(xi) f (xi), i 0,1,2, n. (1)

Такой многочлен называется интерполяционным. Точки xi (i = 1, 2, n) на-

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

Интерполяционный многочлен может строиться с использованием всех узлов интерполяции, тогда говорят о глобальной интерполяции. Если интерполяционные многочлены строятся отдельно для разных интервалов изменения x, то в этом случае имеем кусочную или локальную интерполяцию. Как правило, интерполяционные многочлены используются для нахождения значений функции в промежуточных точках между крайними узлами интерполяции, т.е. при x ( x0, xn). Но иногда эти многочлены используются для вычисления значений функции вне отрезка (x0, xn). Такое приближение называют экстраполяцией.

1.2.Интерполяционный многочлен Лагранжа

Будем искать многочлен в виде линейной комбинации многочленов степени n:

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

Интерполяционный многочлен, представленный в виде (4), называется ин-

терполяционным многочленом Лагранжа, а функции pi(x), представленные в виде (3) – лагранжевыми коэффициентами.

Можно доказать, что многочлен Лагранжа единственен. При n = 1 (интерполируем по двум точкам)

При n = 2 (интерполируем по трем точкам)

4

Пример 1

Построить интерполяционный многочлен Лагранжа по заданной таблице значений функции и с его помощью приближенно найти f(4).

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

погрешности интерполяции на всем отрезке [x0, xn]:

Пример 2

Оценить погрешность приближения функции f (x) x в точке x = 116 с помощью интерполяционного многочлена Лагранжа, построенного с узлами x0=100, x1=121, x2=144.

По формуле (6) имеем

12 (116 121)(116 100) 10.7694. (144 100)(144 121)

5

Rусеч M3 (116 100)(116 121)(116 144) 3!

1 10 5 16 5 28 1.4 10 3 2 10 3. 16

Если значения функции в узлах интерполяции заданы с погрешностью, то при интерполяции возникает погрешность округления. Если Е – максимальная погрешность одного вычисления f(xi), то при n >1 погрешность округления

можно оценить по формуле: Rокруг E (2n 1). Тогда полная погрешность интерполяции R Rусеч Rокруг.

1.3.Интерполяционный многочлен Ньютона

До сих пор не делалось никаких предположений о законе распределения узлов интерполяции. Сейчас рассмотрим случай равноотстоящих узлов, т.е. xi xi 1 h const, i 1,2, ,n. Величина h называется шагом интерполяции.

Введем понятие конечных разностей. Составим разности значений функции: y0 y1 y0, y1 y2 y1, , yn 1 yn yn 1. Эти значения называются

разностями первого порядка. Можно составить разности второго порядка

2y0 y1 y0, 2y1 y2 y1, . Аналогично составляются разности k-го

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

Пример 3

Найти конечные разности для функции f(x)=2x3–2x2+3x–1, x0 = 0, h = 1, i = 0, 1, 2, 3, 4.

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

6

2y0 y1 y0 (y2 y1) (y1 y0) y2 2y1 y0,

3y0 2y1 2y0 (y3 2y2 y1) (y2 2y1 y0) y3 3y2 3y1 y0.

Для любого k можно получить формулу:

Аналогичная формула имеет место для значения разности в узле xi:

Можно определить значение yk, используя конечные разности:

Перейдем к построению интерполяционного многочлена Ньютона. Будем искать его в виде:

для нахождения коэффициентов многочлена:

Nn(x0) a0 y0,

Nn(x1) a0 a1(x1 x0) a0 a1h y1,

Nn(x2) a0 a1(x2 x0) a2(x2 x0)(x2 x1) a0 2a1h 2a2h2 y2,

……………………………………………………

Nn(xn) a0 a1(xn x0) a2(xn x0)(xn x1) an(xn x0)(xn x1) (xn xn 1).

Найдем неизвестные коэффициенты:

Аналогично можно найти и остальные коэффициенты. Общая формула для коэффициента ak имеет следующий вид:

ak k y0 , k 0,1,2, ,n. k!hk

Подставляя выражения для ak в формулу (10), находим интерполяционный многочлен Ньютона:

Конечные разности могут быть вычислены по формуле (7).

7

Формулу (11) часто записывают в другом виде. Для этого вводится пере-

Полученное выражение носит название первого интерполяционного много-

члена Ньютона для интерполяции вперед. Эту формулу используют для вычис-

ления значений функции в точках левой половины отрезка (x0, xn) и для экстраполяции левее x0. Для правой половины отрезка (x0, xn) разности лучше

вычислять справа налево, поэтому вводят переменную q x x0 , т.е. q < 0 и

Полученная формула называется вторым интерполяционным многочленом Ньютона для интерполяции назад. Формула (13) используется также для экстраполяции правее xn.

Если имеется дополнительный узел xn+1, то погрешность первого интерполяционного многочлена Ньютона можно оценить по формуле:

Следует подчеркнуть, что существует один и только один интерполяционный многочлен при заданном наборе узлов интерполяции. Формулы Лагранжа и Ньютона порождают один и тот же многочлен. Разница лишь в алгоритме их построения. Выбор способа интерполяции определяется различными соображениями: точностью, временем вычислений, погрешностью округлений и др. В некоторых случаях предпочтительней может оказаться локальная интерполяция.

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

Пример 4

Составить таблицу значений функции f(x) = 2x3 – 2x2 + 3x – 1 на интервале [0; 4] с шагом h = 1. По составленной таблице построить интерполяционный многочлен Ньютона и найти f (0.5).

x0 = 0, h = 1, i = 0, 1, 2, 3, 4.

8

Используя таблицу конечных разностей из примера 1 и формулу (12), получаем (точка 0.5 лежит в левой половине отрезка [0, 4]):

f (0.5) 1 3 0.5 4 0.5 (0.5 1) 2 0.5 (0.5 1) (0.5 2) 0.25.

1.4.Линейная и квадратичная интерполяция

Если x [xi, xi+1], то при n = 1 из формулы (12) получаем формулу линейной интерполяции:

Геометрически линейная интерполяция означает замену графика функции на отрезке [xi, xi+1] хордой, соединяющей точки (xi, fi) и (xi+1, fi+1) (рис.1).

y

y= N1 (x)

y=f (x)

f (xi) f (xi+1)

Рис. 1. Линейная интерполяция Погрешность формулы (15) определяется неравенством:

Если x [xi, xi+1], при n = 2 из формулы (12) получаем формулу квадратичной интерполяции (для интерполяции используем точки xi, xi+1, xi+2):

Если для интерполяции используем точки xi-1, xi, xi+1, то получаем форму-

лу:

В первом случае квадратичная интерполяция геометрически означает замену графика функции на отрезке [xi, xi+2] параболой, проходящей через точки (xi, fi), (xi+1, fi+1) и (xi+2, fi+2). Во втором случае парабола проходит через точки

(xi-1, fi-1), (xi, fi) и (xi+1, fi+1).

Погрешность формулы (17) определяется неравенством:

Пример 5

Составить таблицу значений функции f(x) = 2x3 – 2x2 + 3x – 1 на интервале [0; 4] с шагом h = 1. По составленной таблице с помощью линейной интерполяции найти f (3.5), а с помощью квадратичной интерполяции найти f (1.5). Оцените погрешности приближенных вычислений.

Используя таблицу конечных разностей из примера 3 п.1.2 и формулу (15), получаем формулу линейной интерполяции (точка x = 3.5 лежит между точка-

ми x3 = 3 и x4 = 4):

Точка x = 1.5 лежит между точками x1 = 1 и x2 = 2, поэтому квадратичную интерполяцию можно делать по точкам x0, x1, x2 или x1, x2, x3. Выберем второй вариант. Используя таблицу конечных разностей из примера 3 п.1.2 и формулу (17), получаем формулу квадратичной интерполяции:

10