H Интерполяция формулы Ньютона в черновиках

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

Интерполяционные формулы используются также при вычислении интегралов, при написании разностных аппроксимаций для дифференциальных уравнений, на основе интегральных тождеств.
Часто требуется восстановить функцию f(x) на отрезке a ≤ x ≤ b, если известны её значения в некотором конечном числе точек этого отрезка.



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

В таблице 1 приведены данные временной сложности алгоритмов.

Таблица 1


Входные данные:
x — координата, в которой необходимо вычислить.
n – Количество узлов.
Step – шаг интерполяции
Множество MasX – Значения x.
Множество MasY – Значения f(x).

Выходные данные:
res – значение полинома в точке x.

Алгоритмическая модель метода Ньютона:

Множество mas мощностью |n + 2, n + 1|;
            Для всех i от 0..2:
                Для всех j от 0..n+1:
                    Если i = 0:
                        masi,j = MasXj;
                    иначе Если i = 1:
                        masi,j = MasYj;
            m = n;
            Для всех i от 2..n+2:
                Для всех j от 0..m:
                    masi,j = mas(i-1),(j+1) – mas(i–1),j;
                m = m-1;

	Множество dy0 мощностью |n + 1|;

            Для всех i от 0..n+1:
                dy0i = mas(i + 1),0;

            res = dy00;
	Множество xn мощностью |n|;
            xn0 = x - mas0,0;

            Для всех i от 1..n:
                ans = xni - 1 * (x - mas0, i);
                xni = ans;
                ans = 0;

            m1 = n + 1;
            fact = 1;
            Для всех i от 1..m1:
                fact = fact * i;
                res = res + (dy0i * xni - 1) / (fact * stepi);

На рисунке 1 изображена схема интерполяции метода Ньютона.


Рисунок 1 — интерполяция метода Ньютона

        // x - координата, в которой необходимо вычислить значение полинома Ньютона; n - количество узлов; MasX - массив x; MasY - массив значений x; step - шаг
        public double Newton(double x, int n, double[] MasX, double[] MasY, double step)
        {
            double[,] mas = new double[n + 2, n + 1];
            for (int i = 0; i < 2; i++)
            {
                for (int j = 0; j < n + 1; j++)
                {
                    if (i == 0)
                        mas[i, j] = MasX[j];
                    else if (i == 1)
                        mas[i, j] = MasY[j];
                }
            }
            int m = n;
            for (int i = 2; i < n + 2; i++)
            {
                for (int j = 0; j < m; j++)
                {
                    mas[i, j] = mas[i - 1, j + 1] - mas[i - 1, j];
                }
                m--;
            }

            double[] dy0 = new double[n + 1];

            for (int i = 0; i < n + 1; i++)
            {
                dy0[i] = mas[i + 1, 0];
            }

            double res = dy0[0];
            double[] xn = new double[n];
            xn[0] = x - mas[0, 0];

            for (int i = 1; i < n; i++)
            {
                double ans = xn[i - 1] * (x - mas[0, i]);
                xn[i] = ans;
                ans = 0;
            }

            int m1 = n + 1;
            int fact = 1;
            for (int i = 1; i < m1; i++)
            {
                fact = fact * i;
                res = res + (dy0[i] * xn[i - 1]) / (fact * Math.Pow(step, i));
            }

            return res;
        }

Составим таблицу значений для f(x) = x^3.


Найдем полимер в точке 2.1: f(2.1) = 2.1^3=9,261

С помощью программной функции мы получили такой же результат (Рисунок 2).

Рисунок 2 — применение функции

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

Мы построили математическое описание методов, после чего приступили к разработке схемы программы.

Разработали программу реализующую интерполяцию метода Ньютона, на языке C# в Visual Studio 2012.

Протестировали программу, все тесты на основе заданных нами данных были успешно пройдены.