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

  назад | оглавление | вперед

 

Глава 3.Приближение функций многочленами

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

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

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

(1)

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

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


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


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

(2)

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

(3)

Подставляя (3) в (2), находим, что

(4)

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

Можно доказать, что многочлен Лагранжа единственен.

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

(5)

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

(6)

Пример 1:

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

xi

0

2

3

5

f(xi)

1

3

2

5

Согласно (4) при n = 3 имеем

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

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

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

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


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

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

Введем понятие конечных разностей. Составим разности значений функции:

Эти значения называются разностями первого порядка. Можно составить разности второго порядка . Аналогично составляются разности k-го порядка .

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

Пример 1: Найти конечные разности для функции f(x)=2x3–2x2+3x–1,

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

x

y

Δy

Δ2y

Δ3y

Δ4y

0

-1

3

8

12

0

1

2

11

20

12

 

2

13

31

32

   

3

44

63

     

4

107

       

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

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

(7)

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

(8)

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

(9)

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

(10)

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

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

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

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

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

(11)

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

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

С учетом этих соотношений формулу (11) можно переписать в виде:

(12)

Полученное выражение носит название первого интерполяционного многочлена Ньютона для интерполяции вперед. Эту формулу используют для вычисления значений функции в точках левой половины отрезка (x0, xn) и для экстраполяции левее x0. Для правой половины отрезка (x0, xn) разности лучше вычислять справа налево, поэтому вводят переменную , т.е. q < 0 и интерполяционный многочлен Ньютона можно получить в виде

(13)

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

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

(14)

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

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

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

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

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

. Тогда приближенное значение функции

.

.


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

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

(15)

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

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

(16)

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

(17)

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

(18)

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

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

(19)

Для формулы (18) оценка погрешности та же самая, только в этом случае .

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

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

. Тогда, приближенное значение функции

Оценим погрешность вычисления по формуле (16):

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

. Тогда приближенное значение функции:

.

Оценим погрешность вычисления по формуле (19):

3.2. Аппроксимация функции методом наименьших квадратов

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

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

(20)

Функцию j (x) подбирают таким образом, чтобы такая сумма была минимальна. Заметим, что в отличие от интерполяции на функцию j (x) не накладываются условия: .

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

. (21)

Тогда формула (19) примет вид:

(22)

Параметры a0, a1, ј , am найдем из условия минимума функции
S(a0, a1,ј, am). Для этого приравняем нулю частные производные по этим переменным:

(23)

Найдем частные производные функции S(a0, a1,ј , am).

………………………………………………….

Приравнивая эти выражения нулю в соответствии с уравнениями (23), и группируя коэффициенты при неизвестных a0, a1, ј, am, получаем следующую систему уравнений:

(24)

Решая эту систему, находим коэффициенты многочлена (21), который приближает функцию f(x).

Систему (24) можно записать в более компактном виде:

(25)

где . (26)

Если аппроксимирующая функция j (x) выбирается среди всевозможных линейных функций, т.е. функций вида , система (25) будет иметь следующий вид:

, (27)

где .

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

x

0

1

2

3

y

1

1

2

4

В нашем случае n = 3,

Составим систему вида (27) для нахождения коэффициентов аппроксимирующей функции:

, решая которую, находим, что a = 1, b = 0.5. Следовательно, уравнение аппроксимирующей функции имеет вид y = x + 0.5. Самостоятельно постройте эту прямую и отметьте на этом же чертеже точки с координатами
(xi, yi).