WikiDer > Newton-Raphson-Methode

Das Newton-Raphson-Methode, auch bekannt als die Newtons Methode oder kurz Newton-Raphson, ist ein numerischIterationsmethode um die Nullen a . bestimmen differenzierbarFunktion, so wie ein Polynom oder ein transzendente Funktion. Die Methode ist benannt nach Isaac Newton, der die Methode entwickelt hat, und Joseph Raphson, der eine formale Beschreibung davon gab. Es Algorithmuskonvergiert unter günstigen Bedingungen recht schnell, d.h. quadratisch: der Fehler nach dem ${displaystyle(n1)}$-ste Wiederholung ist verhältnismäßig mit dem Quadrat des Fehlers nach dem ${displaystyle n}$-die Iteration. Das Verfahren konstruiert in jedem nachfolgenden Schritt eine nachfolgende Approximation unter Verwendung des ersten Derivat und der Funktionswert in der aktuellen Näherung der Null. Die Methode ist nicht immer stabil.

In der Praxis werden stabilere und schnellere numerische Verfahren verwendet, um die Nullstellen von Funktionen zu bestimmen, wie z Edmond Halley, die eine Erweiterung der Methode von . ist Newton. Die meisten Methoden verwenden zweite (und höhere) Ableitungen und ein Polynom einer zweiten (oder höheren) Grad um die Nullstellen einer Funktion zu finden.

Definition

Das Newton-Raphson-Methode nähert sich einer Null von a differenzierbare Funktion${displaystyle f}$, bezogen auf den Startwert ${displaystyle x_{0}}$, iterativ durch die rekursiv Beziehung:

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

Rechtfertigung

Die Funktion ${Anzeigestil f(x)}$ hat eine Null für ${Anzeigestil x=alpha}$, So ${Anzeigestil f(alpha)=0}$. Name ${displaystyle h_{n}=alpha -x_{n}}$ die Differenz zwischen dem Nullpunkt ${displaystyle alpha }$ und der Ansatz ${displaystyle x_{n}}$, so dass

${Anzeigestil f(x_{n} h_{n})=f(alpha)=0}$

Das Taylors Theorem gibt ein Ansatz von ${displaystyle f}$ in dem Umfeld von ${displaystyle x_{n}}$:

${displaystyle 0=f(alpha)=f(x_{n} h_{n})=f(x_{n}) hf'(x_{n}) ldots}$

Unter Vernachlässigung der Terme zweiter Ordnung erhält man eine Näherung von ${displaystyle h_{n}}$:

${displaystyle h_{n}ungefähr -{frac {f(x_{n})}{f'(x_{n})}}}$ (Die Ableitung ${displaystyle f'(x_{n})}$ wird als ungleich Null angenommen).

Eine bessere Näherung für den Nullpunkt ist dann:

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

Zusammen mit dem Startwert ${displaystyle x_{0}}$ gibt dies ein rekursives Verfahren zur Annäherung an den Nullpunkt ${displaystyle alpha }$.

Beachten Sie, dass ${displaystyle x_{n 1}}$ der Schnittpunkt mit der x-Achse ist die Tangente an den Graphen von ${displaystyle f}$ im punkt ${displaystyle x_{n}}$, gegeben durch die Formel

${Anzeigestil y=(x-x_{n})f'(x_{n}) f(x_{n})}$

Geometrische Interpretation

1. Wähle einen Punkt ${displaystyle x_{0}}$ auf der x-Achse nahe dem Nullpunkt α;
2. Konstruiere eine Senkrechte zur x-Achse, durch ${displaystyle x_{0}}$;
3. Konstruiere die Tangente durch ${displaystyle f(x_{0})}$ auf der Kurve ${Anzeigestil f(x)}$;
4. Der neue Ansatz ${displaystyle x_{1}}$ ist durch den Schnittpunkt der Tangente mit der x-Achse gegeben.

Geschichte

Isaac Newton schrieb das Werk in der Zeit von 1664-1671 Methodus fluxionum et serierum infinitarum (lateinisch für: "Die Methode der Ableitungen und unendlichen Folgen"). Darin erklärt er einen neuen Algorithmus zur Lösung polynomialer Gleichungen am Beispiel ${Anzeigestil y^{3}-2y-5=0}$. Dafür kann man leicht erraten, dass der Punkt ${Anzeigestil y=2}$ ist eine erste Näherung. Newton ging davon aus, dass ${Anzeigestil y=2p}$ jetzt sofort ${displaystyle p}$ angenommen, "klein" zu sein, und setze es in die Gleichung ein:

${displaystyle y^{3}=(2p)^{3}=8 12p 6p^{2}p^{3}}$

${Anzeigestil 2y=2(2p)=4 2p}$

so dass

${Anzeigestil 0=y^{3}-2y-5=-1 10p 6p^{2} p^{3}}$

weil ${displaystyle p}$ wird als "klein" angenommen, die Terme mit ${displaystyle p^{2}}$ und ${displaystyle p^{3}}$ ignoriert, danach

${Anzeigestil 10p-1ca. 0}$, So ${displaystyle pca. 0{,}1}$

bleibt als bessere Näherung.

Dieser Vorgang kann nun wiederholt werden durch ${Anzeigestil p=0{,}1q}$ und fülle die Gleichung für ${displaystyle p}$.

${displaystyle p^{3}=(0{,}1 q)^{3}=0{,}001 0{,}03q 0{,}3q^{2} q^{3}}$

${displaystyle p^{2}=(0{,}1 q)^{2}=0{,}01 0{,}2q q^{2}}$

so dass

${displaystyle 0=-1 10p 6p^{2} p^{3}=0{,}061 11{,}23q 6{,}3q^{2} q^{3}}$

Auch hier werden die Terme höherer Ordnung weggelassen, wonach:

${displaystyle qapprox -0{,}061/11{,}23=-0{,}0054ldots }$

Joseph Raphson beschrieb diesen Rechenprozess 1690 formell in der Arbeit Analyse Aequationum universalis, und illustrierte den Formalismus mit der allgemeinen kubischen Gleichung, wobei er die folgende Iterationsregel fand. ^[1]

Die abstrakte Form dieser Methode

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

mit der Ableitung ist von Thomas Simpson.

Beispiel

Nullstellen von ${Anzeigestil f(x)=cos(x)}$, mit Startwert ${displaystyle x_{0}=1}$. Die Rekursionsformel lautet:

${displaystyle x_{n 1}=x_{n}-{frac {cos(x_{n})}{-sin(x_{n})}}=x_{n} Kinderbett(x_{n})}$

und die gewünschte Null ist

${displaystyle x={frac {pi}{2}}=1{,}570796327}$

Iteration führt zu:

${displaystyle x_{0}=1}$

${displaystyle x_{1}=1{,}0000000000 Kinderbett(1{,}00000000)=1{,}642092616}$; Fehler: 7,1×10⁻²

${displaystyle x_{2}=1{,}642092616 Kinderbett(1{,}642092616)=1{,}570675277}$; Fehler: 1,2×10⁻⁴

${displaystyle x_{3}=1{,}570675277 Kinderbett(1{,}570675277)=1{,}570796327}$; Fehler: 5.9×10⁻¹³

Bereits nach drei Iterationen erhält man eine bereits sehr genaue Näherung. Beachten Sie, dass sich der Exponent des Fehlers mit jedem Iterationsschritt mindestens verdoppelt; dies ist ein Merkmal der quadratischen Konvergenz.

Die Methode ist auch nützlich für:

• Systeme von ${displaystyle n}$ nichtlineare algebraische Gleichungen in ${displaystyle n}$ Unbekannte. In diesem Fall müssen die skalaren Variablen durch Matrizen ersetzt werden. Anstelle der Ableitung kommt die jakobisch.
• Finden von Extremen einer Skalarfunktion in a ${displaystyle n}$-dimensionaler Raum; ${displaystyle 1/f'(x_{n})}$ wird dann durch das Inverse ersetzt hessisch. Abhängig von der Verfügbarkeit analytischer Ausdrücke der ersten und zweiten Ableitungen von ${displaystyle f}$ Es gibt viele Varianten dieses Verfahrens, bei denen die Ableitungen entweder exakt berechnet oder aus aufeinanderfolgenden Iterationsschritten angenähert werden.

Siehe auch

• Halbierungsmethode
• regula falsch
• Sekantenmethode

Verweise