Neville-algoritmus

• IPA:

Neville-algoritmus

1. (matematika)

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.

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

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

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

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

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

  $${\displaystyle 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 ${\displaystyle P_{i,j-1}(x)}$ és ${\displaystyle P_{i+1,j}(x)}$ kisebb fokszámú interpoláló polinomok.

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

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 = yi  # Diagonális inicializálás

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

  return P

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

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

A mátrix ${\displaystyle P}$ eleme lesz a keresett ${\displaystyle P(x)}$ polinom értéke.

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 =  * n for _ in range(n)]

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

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

    return P

# Példa használat
xi = 
yi =   # y = x^2
x = 1.5

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

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

Interpolálandó hely: $${\displaystyle x=1.5.}$$

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

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.

1. **Időigény**: Az algoritmus ${\displaystyle 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.

• **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.

• 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)