Neville-algoritmus

Magyar

Kiejtés

• IPA: [ ˈnɛvilːɛɒlɡoritmuʃ]

Főnév

Neville-algoritmus

1. (matematika)

Neville-algoritmus

A **Neville-algoritmus** egy numerikus interpolációs módszer, amely segítségével adott adatpontok alapján egy közelítő polinomot határozunk meg. A módszer rekurzívan számítja ki az interpoláló polinomot, amely áthalad az adatpontokon, és hatékony megoldást nyújt interpolációs problémákra.

Probléma

Adottak az \( n+1 \) pontok: $$(x_{0},y_{0}),(x_{1},y_{1}),\ldots ,(x_{n},y_{n}),$$ ahol $y_{i}=f(x_{i})$. A cél egy interpoláló polinom $P(x)$ meghatározása, amelyre: $$P(x_{i})=y_{i}\quad {\text{minden }}i\in \{0,1,\ldots ,n\}.$$

Neville-algoritmus alapja

Az interpoláló polinomot rekurzívan számítjuk:

1. Indulás: Az egyes adatpontokra a polinom:

  $$P_{i}(x)=y_{i}.$$

1. Rekurzió: Ha $P_{i,j}(x)$ az $x_{i},x_{i+1},\ldots ,x_{j}$ pontokon áthaladó polinom, akkor:

  $$P_{i,j}(x)={\frac {(x-x_{j})P_{i,j-1}(x)-(x-x_{i})P_{i+1,j}(x)}{x_{i}-x_{j}}}.$$
  Ahol $P_{i,j-1}(x)$ és $P_{i+1,j}(x)$ kisebb fokszámú interpoláló polinomok.

1. Végső polinom: Az interpolált érték a $P_{0,n}(x)$ polinom $x$-re való értéke lesz.

Pszeudokód

NEVILLE(x, xi, yi):
  Input: 
    x   - az interpolálandó érték,
    xi  - az \( x_i \) adatpontok listája,
    yi  - az \( y_i \) adatpontok listája.
  Output: 
    y   - az interpolált érték.

  n = hossz(xi)
  P = n x n-es mátrix, kezdetben üres

  for i = 0 to n-1:
    P[i][i] = yi[i]  # Diagonális inicializálás

  for j = 1 to n-1:
    for i = 0 to n-j-1:
      P[i][i+j] = ((x - xi[i+j]) * P[i][i+j-1] - (x - xi[i]) * P[i+1][i+j]) / (xi[i] - xi[i+j])

  return P[0][n-1]

Neville-algoritmus működése

1. Adatpontok inicializálása

Minden adatpontot egy-egy egyszerű polinom reprezentál: $$P_{i,i}(x)=y_{i}.$$

2. Rekurzív számítás

Fokozatosan építjük fel a polinomokat, amelyek egyre több adatpontra illeszkednek. Az $(i,j)$-edik elem az $x_{i},x_{i+1},\ldots ,x_{j}$ pontokon áthaladó polinom értéke.

3. Végső érték

A mátrix $P[0][n-1]$ eleme lesz a keresett $P(x)$ polinom értéke.

Python implementáció

def neville(x, xi, yi):
    """
    Neville-algoritmus az interpolációhoz.
    :param x: Az interpoláció helye.
    :param xi: Az adatpontok x koordinátái.
    :param yi: Az adatpontok y koordinátái.
    :return: Az interpolált érték.
    """
    n = len(xi)
    P = [[0] * n for _ in range(n)]

    # Inicializálás
    for i in range(n):
        P[i][i] = yi[i]

    # Rekurzív számítás
    for j in range(1, n):
        for i in range(n - j):
            P[i][i + j] = ((x - xi[i + j]) * P[i][i + j - 1] - (x - xi[i]) * P[i + 1][i + j]) / (xi[i] - xi[i + j])

    return P[0][n - 1]

# Példa használat
xi = [1, 2, 3]
yi = [1, 4, 9]  # y = x^2
x = 1.5

result = neville(x, xi, yi)
print(f"Interpolált érték a {x} helyen: {result}")

Példa

Bemenet

Adott adatpontok: $$(x_{0},y_{0})=(1,1),\quad (x_{1},y_{1})=(2,4),\quad (x_{2},y_{2})=(3,9).$$

Interpolálandó hely: $$x=1.5.$$

Kimenet

A Neville-algoritmus a $P(x)$ polinom értékét $x=1.5$-nél: $$P(1.5)=2.25.$$

Előnyök

1. **Pontosság**: Garantáltan áthalad az összes adatponton.
2. **Rugalmas**: Könnyen alkalmazható egyenlőtlenül elosztott adatpontokra.
3. **Numerikus stabilitás**: Az interpoláló polinom fokozatos építése csökkenti a numerikus hibák valószínűségét.

Hátrányok

1. **Időigény**: Az algoritmus $O(n^{2})$ bonyolultságú, ami nagy adatpontok esetén lassabb.
2. **Nem adaptív**: Ha új adatpontokat adunk hozzá, az algoritmust újra kell futtatni.
3. **Rossz extrapoláció**: Csak interpolációra alkalmas, extrapoláció esetén pontatlanság léphet fel.

Alkalmazások

• **Numerikus analízis**: Függvények értékeinek közelítése ismert adatpontok alapján.
• **Fizikai szimulációk**: Ismeretlen függvények numerikus megközelítése.
• **Adatmodellezés**: Kísérleti adatokhoz illeszkedő polinom meghatározása.

A **Neville-algoritmus** hatékony interpolációs módszer, amelyet akkor érdemes használni, ha az adatpontok száma kicsi és pontos interpolációra van szükség.

Fordítások

Tartalom

angol: Neville's algorithm (en)

További információk

• Neville-algoritmus - Értelmező szótár (MEK)
• Neville-algoritmus - Etimológiai szótár (UMIL)
• Neville-algoritmus - Szótár.net (hu-hu)
• Neville-algoritmus - DeepL (hu-de)
• Neville-algoritmus - Яндекс (hu-ru)
• Neville-algoritmus - Google (hu-en)
• Neville-algoritmus - Helyesírási szótár (MTA)
• Neville-algoritmus - Wikidata
• Neville-algoritmus - Wikipédia (magyar)