Newton interpolation in python

Интерполяция функций методом Ньютона на Python

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

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

Алгоритм интерполяции функций методом Ньютона

1. Задать исходные точки интерполяции, которые будут использоваться для построения полинома.
2. Рассчитать разделенные разности второго порядка (то есть разность между значениями функции в двух точках, поделенная на разность соответствующих аргументов) для каждой пары точек. Разделенные разности второго порядка будут использоваться для расчета коэффициентов полинома.
3. Используя найденные разделенные разности, выразить полином в форме суммы произведений коэффициентов разделенных разностей на соответствующие множители, где каждый множитель представляет собой произведение аргументов и разностей между аргументами точек интерполяции.
4. Вычислить значения интерполяционного полинома в новых точках, подставив их в формулу, полученную на предыдущем шаге.

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

Пошаговое решение интерполяции функций на Python

• Определяются входные данные для задачи интерполяции: x_values , y_values и x . x_values и y_values являются списками точек, через которые нужно провести интерполяционный полином. x – это точка, для которой нужно вычислить значение интерполяционного полинома.

def newton_interpolation(x_values, y_values, x):

• Определяется длина списка x_values , который будет использоваться для определения количества разделенных разностей, которые нужно вычислить, чтобы построить интерполяционный полином.

• Создается двумерный массив f , который будет использоваться для хранения разделенных разностей. Этот массив инициализируется значениями из списка y_values. В первом столбце этого массива находятся значения функции f(x_i) = y_i .

f = [[None] * n for _ in range(n)]

• Вычисляются оставшиеся разделенные разности в массиве f . Для вычисления каждого элемента массива используются значения из предыдущего столбца и значения из соответствующих строк массива. Таким образом, элемент f[i][j] вычисляется как (f[i+1][j-1] — f[i][j-1]) / (x_values[i+j] — x_values[i]) .

for i in range(n): f[i][0] = y_values[i]

• Вычисляются оставшиеся разделенные разности в массиве f . Для вычисления каждого элемента массива используются значения из предыдущего столбца и значения из соответствующих строк массива. Таким образом, элемент f[i][j] вычисляется как (f[i+1][j-1] — f[i][j-1]) / (x_values[i+j] — x_values[i]) .

for j in range(1, n): for i in range(n - j): f[i][j] = (f[i+1][j-1] - f[i][j-1]) / (x_values[i+j] - x_values[i])

• Выводится таблица конечных разностей в формате, который позволяет увидеть все значения массива f . В таблице конечных разностей в первом столбце находятся значения функции f(x_i) = y_i , а в каждом следующем столбце находятся разделенные разности.

print("Таблица конечных разностей:") for row in f: for elem in row: if elem is not None: print("".format(elem), end="\t") else: print("\t", end="") print()

• Вычисляется значение интерполяционного полинома. Для этого сначала вычисляются все произведения вида (x — x_values[j]) , где j изменяется от 0 до i-1. Затем вычисляется сумма всех таких произведений, умноженных на соответствующие коэффициенты f[0][i] .

y = 0 for i in range(n): prod = f[0][i] for j in range(i): prod *= (x - x_values[j]) y += prod

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

Интерполяция функций методом Ньютона, полный код на Python

def newton_interpolation(x_values, y_values, x): """ :param x_values: список значений x :param y_values: список значений y :param x: значение, для которого нужно найти приближенное значение y :return: приближенное значение y, рассчитанное с помощью интерполяционного полинома Ньютона """ n = len(x_values) # Инициализация разделенных разностей f = [[None] * n for _ in range(n)] for i in range(n): f[i][0] = y_values[i] # Вычисление разделенных разностей for j in range(1, n): for i in range(n - j): f[i][j] = (f[i+1][j-1] - f[i][j-1]) / (x_values[i+j] - x_values[i]) # Вывод таблицы конечных разностей print("Таблица конечных разностей:") for row in f: for elem in row: if elem is not None: print("".format(elem), end="\t") else: print("\t", end="") print() # Вычисление значения интерполяционного полинома y = 0 for i in range(n): prod = f[0][i] for j in range(i): prod *= (x - x_values[j]) y += prod return y x_values = [1, 2, 3] y_values = [2, 7, 11] x = 1 y = newton_interpolation(x_values, y_values, x) print("Значение интерполяционного полинома в точке x = : ".format(x, y))

Результат выполнения программы в консоли:

Источник

Русские Блоги

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

2. Ньютоновская интерполяция:
Сначала необходимо составить таблицу отношений разностей. Когда таблица отношений разностей установлена, x [0], вычитаемое каждый раз, является диагональным элементом, поэтому вам следует обратить внимание.

Во-вторых, понять

''' Никто не ответил на вопрос? Редактор создал группу обмена QQ изучения Python: 579817333 Ищите друзей-единомышленников, помогайте друг другу, в группе есть хорошие видеоуроки и PDF-книги! ''' import matplotlib.pyplot as plt import math # ====================================================== == лагранжевая интерполяция ================================================== =================== def lagrange(x_, y, a): """ Получить лагранжеву интерполяцию : param x_: список значений x : param y: список значений y : param a: число для интерполяции : return: вернуть результат интерполяции """ ans = 0.0 for i in range(len(y)): t_ = y[i] for j in range(len(y)): if i != j: t_ *= (a - x_[j]) / (x_[i] - x_[j]) ans += t_ return ans # ====================================================== == Ньютоновская интерполяция ================================================= =================== def table(x_, y): """ Получить таблицу интерполяции Ньютона : param x_: значение списка x : param y: значение списка y : return: вернуть таблицу интерполяции """ quotient = [[0] * len(x_) for _ in range(len(x_))] for n_ in range(len(x_)): quotient[n_][0] = y[n_] for i in range(1, len(x_)): for j in range(i, len(x_)): # j-i определяет диагональные элементы quotient[j][i] = (quotient[j][i - 1] - quotient[j - 1][i - 1]) / (x_[j] - x_[j - i]) return quotient def get_corner(result): """ Получить диагональные элементы через таблицу интерполяции : param result: результат таблицы интерполяции : return: диагональный элемент """ link = [] for i in range(len(result)): link.append(result[i][i]) return link def newton(data_set, x_p, x_7): """ Результат интерполяции Ньютона : param data_set: диагональ решаемой задачи : param x_p: входное значение : param x_7: исходное значение списка x : return: результат интерполяции Ньютона """ result = data_set[0] for i in range(1, len(data_set)): p = data_set[i] for j in range(i): p *= (x_p - x_7[j]) result += p return result # ====================================================== ============= Нарисуйте картинку ================================== ================= def draw_picture(x_list, y_list, node): plt.title("newton") plt.xlabel("x") plt.ylabel("y") # plt.plot(x_list, y_list, color="red") for i in range(len(x_list)): plt.scatter(x_list[i], y_list[i], color="purple", linewidths=2) plt.scatter(node[0], node[1], color="blue", linewidth=2) plt.show() if __name__ == '__main__': x = 0.54 x_1 = [0.4, 0.5, 0.6, 0.7, 0.8] y_1 = [-0.9163, -0.6931, -0.5108, -0.3567, -0.2231] middle = table(x_1, y_1) n = get_corner(middle) newton = newton(n, x, x_1) lagrange = lagrange(x_1, y_1, 0.54) print(«Истинное значение: <>».format(math.log(0.54, math.e))) print("Лагранжева интерполяция: <>".format(lagrange)) print(«Интерполяция Ньютона: <>».format(newton)) # Рисование draw_picture(x_1, y_1, (x, newton)) 

3. Результаты

2. Результат рисования

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

Источник

Newton Interpolation Method in Python

Newton’s fractional difference interpolation formula is an interpolation technique used when the interval difference is not equal to all values.

The (n + 1) values of the y = f (x) function correspond to the arguments x = x0, x1, x2 are f (x0), f (x1), f (x2) ……… f (xn)… Xn, where interval differences Are not identical.

Newton Interpolation Formula

Write a Program to find value of x using Newton Interpolation Formula

y= f(x) = 0.7071, 0.7660, 0.8192, 0.8660

Python Code:
def u_cal(u,n): 
temp = u 
for i in range(1,n): 
temp = temp*(u-i) 
return temp
def fact(n): 
f = 1
 for i in range(2,n+1): 
f*=i 
return f
n = 4
x = [45,50,55,60]y = [[0 for i in range(n)] for j in range(n)]y[0][0]=0.7071
y[1][0]=0.7660
y[2][0]=0.8192
y[3][0]=0.8660
for i in range(1,n): 
for j in range(n-i): 
y[j][i]=y[j+1][i-1]-y[j][i-1]for i in range (n): 
print(x[i],end="\t") 
for j in range(n-i): 
print(y[i][j],end="\t") 
print("")
value = 52
sum = y[0][0]u =(value-x[0]/x[1]-x[0])
for i in range(1,n): 
sum = sum+(u_cal(u,i)*y[0][i]/fact(i))
print("\n value at",value,"is",round(sum,6))

45 0.7071 0.05890000000000006 -0.005700000000000038 -0.0007000000000000339 50 0.766 0.053200000000000025 -0.006400000000000072 55 0.8192 0.04679999999999995 60 0.866 
value at 52 is 0.962846

Example 2:
Write a program to find value of x using Newton Interpolation Formula

Python Code
def u_cal(u,n): 
temp = u 
for i in range(1,n): 
temp = temp*(u-i) 
return temp
def fact(n): 
f = 1
 for i in range(2,n+1): 
f*=i 
return f
n = 5
x = [1891,1901,1911,1921,1931]y = [[0 for i in range(n)] for j in range(n)]y[0][0]=46
y[1][0]=66
y[2][0]=81
y[3][0]=93
y[4][0]=101
for i in range(1,n): 
for j in range(n-i): 
y[j][i]=y[j+1][i-1]-y[j][i-1]for i in range (n): 
print(x[i],end="\t") 
for j in range(n-i): 
print(y[i][j],end="\t") 
print("")
value=1925
sum=y[0][0]u =(value-x[0]/x[1]-x[0])
for i in range(1,n): 
sum = sum+(u_cal(u,i)*y[0][i]/fact(i))
print("\n value at",value,"is",round(sum,6))
 
1891 46 20 -5 2 -3 1901 66 15 -3 -1 1911 81 12 -4 1921 93 8 1931 101 value at 1925 is -113859.489961
 
 
Newton Interpolation Method in Python Reviewed by guru on 13:19 Rating: 5
 
Источник