Интерполяционная функция Ньютона.

Пусть, как и в случае многочлена Лагранжа, известны n + 1 значений функции y = φ(x) y₀, y₁, …y_n при n + 1 значениях аргумента x₀, x₁, …, x_n. Причем разность между двумя соседними значениями постоянна и равна h. Таким образом, имеем таблицу значений неизвестной функции при соответствующих значениях аргумента.

x	x0	x1 = x0 + h	x2 = x0 + 2h	…	xn = x0 + n h
y	y0	y1	y2	…	yn

Составим многочлен P(x) )степени n такой, что P(x _i) = y_i. Этот многочлен будет приближенно представлять функцию y = φ(x).

Введем обозначения

Δy₀ = y₁ – y₀, Δy₁ = y₂ – y₁, Δy₂ = y₃ – y₂, ….

Δ²y₀ = Δy₁ − Δy₀ = y₂ – 2y₁ + y₀, Δ²y₁ = Δy₂ – Δy₁= y₃ – 2y₂ + y₁, ….

Δ³y₀ = Δ²y₁ – Δ²y₀ = y₃ – 3 y₂ + 3y₁- y₀, …

Δⁿ y₀ = Δ^{n - 1}y₁ – Δ^{n - 1}y₀

Напишем многочлен, принимающий значения y₀ и у₁ при х = х₀ и х = х₁ .

P₁(x) = y₀ +

Действительно, P₁(x₀) = y₀, P₁(x₁) = y₀ + Δy₀ ^h/_h = y₀ + y₁ – y₀ = y₁.

Напишем, далее многочлен, принимающий значения y₀, y₁, y₂ при x₀, x₁, x₂. Непосредственной проверкой доказывается, что это будет многочлен второй степени

Наконец, многочлен n – го порядка, принимающий значения y₀, y₁, …, y_n при x₀, x₁, …, x _n , будет иметь вид

Это и есть интерполяционная формула Ньютона. По существу многочлен Лагранжа и многочлен Ньютона тождественны,. но по-разному записаны. Во многих случаях многочлен Ньютона более удобен, чем многочлен Лагранжа. Особенность этого многочлена состоит в том, что при переходе от многочлена k – й степени к многочлену k + 1 – й степени первые k + 1 членов не изменяются, а только добавляется новый член, который обращается в нуль при предыдущих значениях аргумента.

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

Пусть на основании экспериментов получена зависимость функции y = φ(x), представленная в виде таблицы.

x	x1	x2	…	x n
y	y1	y2	…	yn

Задача состоит в аналитическом представлении функции

y = φ(x) 1)

Возможным вариантом решения является интерполирование с помощью многочлена Ньютона или Лагранжа. Однако, этот способ, требующий обязательного совладения табличных и теоретических значений функции не всегда удобен. При большом количестве узлов интерполяции потребует либо отыскания многочлена большой степени, либо другой «извилистой» функции, график которой проходил бы через все указанные точки. Поэтому рассматривается метод аппроксимации», т.е. приближенного представления искомой функции. Вид функции y = φ(x) устанавливается либо из теоретических соображений, либо на основании расположения на координатной плоскости точек, соответствующих экспериментальным данным. Например, если экспериментальные точки расположены так, как на рис.1, то функцию следует искать в виде y = a x + b, а на рис.2 в виде y = ax² + bx + c.

y •

•

•

•

• •

х

x₁ x₂ x₃ x₄ …. x_n

Рис. 1

у

• • •

• • • •

• • •

•

х

Рис. 2.

При выбранном виде функции

y = φ(x, a₀, a₁, a₂, …a _k )

следует подобрать параметры a₀, a₁, a₂, …k так, чтобы эта функция в каком-то смысле наилучшим образом описывала рассматриваемый процесс. Наиболее распространенным методом решения данной задачи является метод наименьших квадратов. Этот метод заключается в следующем. Рассмотрим сумму квадратов разностей между экспериментальными значениями и теоретическими значениями функции y = φ(x, a, b, c, …) в соответствующих точках.

(2)

Подберем параметры a₀, a₁, a₂, … так, чтобы эта сумма имела наименьшее значение. Таким образом, задача сведется к нахождению значений параметров a₀, a₁, a₂, …, при которых сумма S(a₀, a₁, a₂, …) имеет минимум.

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

(3)

Или в развернутом виде

(4)

Получили систему уравнений относительно a₀, a₁, a₂, …. . Здесь столько уравнений, сколько неизвестных. В каждом отдельном случае исследуется вопрос о существовании решения этой системы и о существовании минимума функции y = φ(x, a₀, a₁, a₂, …a _k ) при найденных значениях a₀, a₁, a₂, ….a_k. В математическом анализе доказывается, что если в качестве аппроксимирующей функции y = φ(x, a₀, a₁, a₂, …a _k ) берется многочлен

y = φ(x, a₀, a₁, a₂, …,a _k ) = a₀ x^k+ a₁x^k−1 + a ₂x^{k -2} + …+ a₁x + a_k, (5)

то решение a₀, a₁, a₂, … системы (4) дает минимум функции y = φ(x, a₀, a₁, a₂, …a _k ).

Будем искать аппроксимирующую функцию в виде (5). Тогда система (4) примет вид

(6)

Раскрывая скобки, получим

(7)

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

Получаем систему линейных уравнений для определения неизвестных коэффициентов , a₀, a₁, a₂, …a_n.. Из характера задачи следует, что система имеет единственное решение и что при полученных значениях параметров a₀, a₁, a₂, …a _k.

Запишем систему (7) в матричном виде AX = B. Здесь А – матрица системы (матрица, составленная из коэффициентов при неизвестных параметрах a₀, a₁, a₂, …a _k), Х – столбец неизвестных, В – столбец свободных членов.

B =

Решение системы (7) в матричном виде запишется X0 = A ^-1 B.

П р и м е р . Для функции, заданной таблично

x	2.0	2.2	2.4	2.6	2.8	3.0
y	0.3010	0.3424	0.3802	0.4150	0.4472	0.4771

подобрать многочлен второй степени y = a ₀ x² + a₁ x + a ₂, найдя значения параметров методом наименьших квадратов.

Имеем n =6, k = 2. Блок-схема программы имеет вид.

Ввод x(i),y(i), i = 0,n n – число точек, в которых даны

значения функции.

i = 0, k k – степень аппроксимирующего

многочлена

j =0, k

да

l = 1, n

A(i, j) = A(i, j) + x(l)^(i + j)

Вывод A(i, j )

i = 0, k

да

l1 = 1, n

B(i) = B(i) + y(l1)* x(l1)^(-i + k)

да

Вывод B(i)