Феномен Рунге15.08.2024 21:46

Введение

Карл Давид Тольме Рунге (30 августа 1856 — 3 января 1927) — выдающийся немецкий математик, физик и спектроскопист. Обучался в Берлинском университете, где получил степень PhD, являлся профессором математики в Ганноверском университете, а также главой кафедры прикладной математики в Гёттингене. [1]

в 1901 году Карл открыл «Феномен Рунге» — в численном анализе эффект нежелательных колебаний, возникающий при интерполяции полиномами высоких степеней — о котором пойдёт речь в данной статье. [2]

Но прежде, чем мы окунёмся глубже в изучение данного феномена, давайте поговорим об интерполяционном многочлене Лагранжа, на примере которого мы и разберём Феномен Рунге.

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

Полином Лагранжа — это математическая функция, позволяющая записать полином n-степени, который будет соединять все заданные точки из набора значений, полученных опытным путём или методом случайной выборки. Многочлен в форме Лагранжа в явном виде содержит значения функций в узлах интерполяции, поэтому он удобен, когда значения функций меняются, а узлы интерполяции неизменны. Число арифметических операции, необходимых для построения многочлена Лагранжа, пропорционально и является наименьшим для всех форм записи. [3]

Полином Лагранжа в общем виде выглядит следующим образом:

$L(x) = \sum_{i=0}^n y_i * l_i (x)$

где l_i (x) — это базисные полиномы Лагранжа, определяющиеся как

$l_i(x) = \Pi \frac{x-x_j}{x_i-x_j}$

где 0≤j≤n, j≠i

Так, например, интерполяционный многочлен в форме Лагранжа, проходящий через три заданных точкибудет записываться вот так: [3]

$L(x) = f(x_0) * \frac{x-x_1}{x_0-x_1}\frac{x-x_2}{x_0-x_2} *f(x_1) * \frac{x-x_0}{x_1-x_0}\frac{x-x_2}{x_1-x_2} *f(x_2) * \frac{x-x_0}{x_2-x_0}\frac{x-x_1}{x_2-x_1}$

Погрешность интерполяционного многочлена Лагранжа описывается следующим образом:

$f(x)-P_n(x)=\frac{f^{n+1}(\xi)}{(n+1)!}\Pi_{i=1}^{n+1}(x-x_i)$

Пример полинома Лагранжа

Для лучшего понимания составления полинома Лагранжа, давайте рассмотрим простенький пример. Мы выберем три точки (-1, 1); (0,0); (1,1).

Начнём с составления базисных полиномов Лагранжа:

$l_0(x)=\frac{(x-0)(x-1)}{(-1-0)(-1-1)} = \frac{x(x-1)}{2}$ $l_1(x)=\frac{(x+1)(x-1)}{(0+1)(0-1)} = -x(x-1)$ $l_2(x)=\frac{(x+1)(x)}{(1+1)(1-0)} = \frac{x(x+1)}{2}$

Таким образом, полином Лагранжа выглядит вот так:

$L(x) = 1*\frac{x(x-1)}{2} + 0*(-x(x-1)) + 1*\frac{x(x+1)}{2} = x^2 - \frac{1}{2}$

Демонстрация феномена Рунге через полином Лагранжа

Мы хотим аппроксимировать функцию $f(x)=\frac{1}{1+25x^2}$ на

интервале [-1, 1] использую полином Лагранжа.

Используя функцию интерполяции Лагранжа SciPy, мы вычислим полином Лагранжа степени 6, 8, 10, 12 .

Здесь мы рассматриваем узлы $x_i = \frac{i}{n}$ для i = 0, 1, ... , n.

Мы построим графики различных полиномов и функции f(x) на интервале [-1, 1].

import numpy as np
from scipy.interpolate import lagrange
import matplotlib.pyplot as plt

def f(x):
  return 1/(1+25*x**2)
  
n=100
x_fine=np.linspace(-1, 1, 1000)
y_fine=f(x_fine)
plt.plot(x_fine, y_fine, color='black', label='f(x)') 

for degree in range(6,13,2):
  x_nodes=np.array([-1+(2*i/degree)for i in range(degree+1)]) 
  p_n=lagrange(x_nodes, f(x_nodes))
  y_nodes=p_n(x_fine)
  plt.plot(x_fine, y_nodes, label=f'Полином Лагранжа Степени {degree}')
  
plt.xlabel('x') 
plt.ylabel('f(x)')
plt.legend() 
plt.show()

результат прогонки кода

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

Феномен Рунге показывает, что переход к более высоким степеням не всегда повышает точность. Почему такое происходит? Давайте обратимся к погрешности Лагранжа.

$\frac{f^{n+1}(\xi)}{(n+1)!}\Pi_{i=1}^{n+1}(x-x_i)$

Для случая функции Рунге, интерполированной в равноудаленных точках, каждый из двух множителей в погрешности аппроксимации растет до бесконечности с ростом n. Хотя это часто используется для объяснения феномена Рунге, тот факт, что верхняя граница погрешности стремится к бесконечности, не обязательно подразумевает, конечно, что сама погрешность также расходится с n. [4]

Решение проблемы

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

Для натурального числа n узлы Чебышёва на отрезке [−1, 1] задаются формулой: [5]

$x_k = \cos(\frac{2i-1}{2n}) * \pi, i= 1, ..., n$

import numpy as np
from scipy.interpolate import lagrange
import matplotlib.pyplot as plt

def f(x):
  return 1/(1+25*x**2)
 
def chebyshev_nodes(n): 
  nodes=np.zeros(n+1) 
  for i in range (n+1):
    nodes[i]=np.array(np.cos((2*i+1)*np.pi/(2*(n+1)))) 
  return nodes
  
n=100
x_fine=np.linspace(-1, 1, 1000)
y_fine=f(x_fine)
plt.plot(x_fine, y_fine, color='black', label='f(x)') 
for degree in range(6,13,2):
  x_nodes=np.array(chebyshev_nodes(degree)) 
  p_n=lagrange(x_nodes, f(x_nodes))
  y_nodes=p_n(x_fine)
  plt.plot(x_fine, y_nodes, label=f'Лаг Пол Ст {degree}')
  
plt.xlabel('x') 
plt.ylabel('f(x)')
plt.legend(loc='upper left') 
plt.show()

результат прогонки кода

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

Заключение

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

Список Литературы

https://dic.academic.ru/dic.nsf/ruwiki/491639
https://ru.wikipedia.org/wiki/Феномен_Рунге
http://simenergy.ru/mathematical-analysis/basic-data/lagrange-polynomial
http://www.tlu.ee/~tonu/Arvmeet/Runge’s%20phenomenon.pdf
https://en.wikipedia.org/wiki/Chebyshev_nodes