Newton-módszer

• IPA:

Newton-módszer

1. (matematika, algoritmusok) A Newton-módszer (vagy Newton-Raphson módszer) egy numerikus eljárás, amelyet a valós számok gyökeinek közelítésére használnak. Ezt a módszert elsősorban az ${\textstyle f(x)=0}$ egyenlet megoldásának keresésére alkalmazzák. Az eljárás lényege, hogy a közelítést fokozatosan javítják, amíg el nem érik a kívánt pontosságot.

A Newton-módszer lépései

1. Kezdeti közelítés: Válasszunk ki egy ${\textstyle x_{0}}$ kezdeti közelítést, amely közel áll a keresett gyökérhez.

2. Iteratív lépés: A következő közelítést az alábbi képlettel számítjuk ki:

$${\displaystyle x_{n+1}=x_{n}-{\frac {f(x_{n})}{f'(x_{n})}}}$$

ahol ${\textstyle f'(x_{n})}$ a ${\textstyle f(x)}$ függvény deriváltja az ${\textstyle x_{n}}$ pontban.

3. Folyamatos iteráció: Ismételjük meg a 2. lépést, amíg ${\textstyle x_{n}}$ közelítése nem éri el a kívánt pontosságot (pl. ${\textstyle |f(x_{n})|<\epsilon }$, ahol ${\textstyle \epsilon }$ egy kis pozitív szám).

Előnyök - Gyors konvergencia: A Newton-módszer általában gyorsan konvergál, különösen, ha a kezdeti közelítés közel van a valós gyökhöz. - Alkalmazhatóság: A módszer bármilyen differenciálható függvényre alkalmazható, amennyiben a deriváltja nem nulla a gyök körüli pontokban.

Hátrányok - Kezdeti közelítés érzékenysége: Ha a kezdeti közelítés nem megfelelő, a módszer nem mindig konvergálhat, vagy a nem kívánt gyökérhez vezethet. - Derivált szükségessége: A módszer igényli a függvény deriváltját, amely nem mindig könnyen meghatározható. - Több gyökér esetén: Ha a keresett gyökér többszörös, a konvergencia lassabb lehet.

Példa Legyen ${\textstyle f(x)=x^{2}-2}$. Az ${\textstyle f(x)=0}$ gyökének keresésére alkalmazzuk a Newton-módszert:

1. Kezdeti közelítés: ${\textstyle x_{0}=1}$ 2. Derivált: ${\textstyle f'(x)=2x}$ 3. Iteráció:

- ${\textstyle x_{1}=1-{\frac {1^{2}-2}{2\cdot 1}}=1.5}$ - ${\textstyle x_{2}=1.5-{\frac {(1.5)^{2}-2}{2\cdot 1.5}}\approx 1.41667}$

Ismételjük meg az iterációt, amíg a kívánt pontosságot elérjük.

A Newton-módszer egy iteratív numerikus eljárás, amelyet a nemlineáris egyenletek gyökeinek meghatározására vagy függvények minimumának/maximumának keresésére használnak. Az algoritmus gyorsan konvergál a gyökökhöz, ha a kezdőérték elég közel van a tényleges megoldáshoz.

Adott egy (f(x) = 0) egyenlet, ahol (f(x)) egy folytonosan deriválható függvény. A Newton-módszer a lineáris közelítést használja az iterációs folyamat során.

Az iterációs képlet:

1. Kezdj egy (x_0) kezdeti értékkel (kezdő közelítés).
2. Számítsd ki az új (x_{n+1}) értéket a fenti képlet szerint.
3. Ismételd az iterációt, amíg az (x_{n+1}) és az (x_n) közötti különbség elég kicsi (azaz a módszer konvergált).

A Newton-módszer gyorsan konvergál, ha: 1. A kezdőérték ((x_0)) elég közel van a gyökhez. 2. A (f(x)) függvény deriváltja ((f’(x))) nem nullázódik ki a gyök környezetében. 3. A függvény kétszer deriválható a gyök környezetében.

Oldjuk meg a (f(x) = x^2 - 2 = 0) egyenletet Newton-módszerrel (() kiszámítása):

Tegyük fel, hogy (x_0 = 1).

1. Iteráció: (x_1 = 1 - = 1.5)
2. Iteráció: (x_2 = 1.5 - )
3. Iteráció: (x_3 = 1.4167 - )

Az eredmény ( ).

def newton_method(f, df, x0, tol=1e-6, max_iter=100):
    x = x0
    for _ in range(max_iter):
        fx = f(x)
        dfx = df(x)
        if abs(fx) < tol:
            return x
        if dfx == 0:
            raise ValueError("A derivált nullával egyenlő, nem lehet osztani.")
        x -= fx / dfx
    raise ValueError("A módszer nem konvergált a maximális iterációk alatt.")

# Példa függvény: f(x) = x^2 - 2
f = lambda x: x**2 - 2
df = lambda x: 2 * x

# Kezdőérték
x0 = 1.0

# Eredmény
root = newton_method(f, df, x0)
print(f"A gyök: {root}")

Kimenet:

A gyök: 1.4142135623746899

#include <iostream>
#include <cmath>
#include <stdexcept>

using namespace std;

double newton_method(double (*f)(double), double (*df)(double), double x0, double tol = 1e-6, int max_iter = 100) {
    double x = x0;
    for (int i = 0; i < max_iter; ++i) {
        double fx = f(x);
        double dfx = df(x);
        if (abs(fx) < tol) {
            return x;
        }
        if (dfx == 0) {
            throw runtime_error("A derivált nullával egyenlő, nem lehet osztani.");
        }
        x -= fx / dfx;
    }
    throw runtime_error("A módszer nem konvergált a maximális iterációk alatt.");
}

double f(double x) {
    return x * x - 2;
}

double df(double x) {
    return 2 * x;
}

int main() {
    double x0 = 1.0;  // Kezdőérték
    try {
        double root = newton_method(f, df, x0);
        cout << "A gyök: " << root << endl;
    } catch (const exception& e) {
        cerr << "Hiba: " << e.what() << endl;
    }
    return 0;
}

Kimenet:

A gyök: 1.41421

1. Gyors konvergencia:
   • Ha a kezdőérték elég közel van a gyökhez, az algoritmus kvadratikusan konvergál, ami azt jelenti, hogy az iterációs hibák négyzetesen csökkennek.
2. Egyszerű implementáció:
   • Könnyen megvalósítható, ha a deriváltak számítása nem túl bonyolult.

1. Kezdőértéktől függő:
   • Ha a kezdőérték távol van a gyöktől, az algoritmus lassan konvergálhat, vagy egyáltalán nem találja meg a gyököt.
2. Lokális optimumok:
   • Ha a derivált nullához közelít ((f’(x) )), az algoritmus meghibásodhat.
3. Nem mindig működik nemlineáris rendszereknél:
   • További információra lehet szükség komplex függvényeknél.

1. Nemlineáris egyenletek megoldása:
   • Gyökök meghatározása.
2. Optimális pontok keresése:
   • Függvény minimumának vagy maximumának meghatározása (gradiens alapú optimalizálás).
3. Fizikai modellek:
   • Dinamikus rendszerek stabilitásának vizsgálata.
4. Képfeldolgozás:
   • Illesztési algoritmusokban.

A Newton-módszer egy gyors és hatékony numerikus eljárás, amelyet széles körben használnak matematikai, mérnöki és tudományos alkalmazásokban. Bár kezdőértéktől függően instabil lehet, megfelelő kezdeti közelítéssel az egyik leghatékonyabb módszer nemlineáris egyenletek megoldására.

• angol: Newton’s method (en)
• orosz: метод Ньютона (ru) (metod Nʹjutona)

Newton +‎ módszer

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