Neville-algoritmus

1. Sablon:Label

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),\dots ,(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\text{minden }i\in \{0,1,\dots ,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},\dots ,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},\dots ,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),(x_1,y_1)=(2,4),(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.

• Sablon:En: Sablon:T+