Durand-Kerner-Methode – Wikipedia

In der numerischen Analyse wird die Weierstrass-Methode oder Durand-Kerner-Methode, 1891 von Karl Weierstrass entdeckt und 1960 von Durand und 1966 von Kerner unabhängig wiederentdeckt, ist ein Algorithmus zur Wurzelfindung zur Lösung von Polynomgleichungen.[1] Mit anderen Worten kann das Verfahren verwendet werden, um die Gleichung numerisch zu lösen

f((x) = 0,

wo f ist ein gegebenes Polynom, das so skaliert werden kann, dass der führende Koeffizient 1 ist.

Erläuterung[edit]

Diese Erklärung berücksichtigt Gleichungen des vierten Grades. Es ist leicht auf andere Grade zu verallgemeinern.

Lassen Sie das Polynom f definiert werden durch

f((x)=x4+einx3+bx2+cx+d{ displaystyle f (x) = x ^ {4} + ax ^ {3} + bx ^ {2} + cx + d}

für alle x.

Die bekannten Zahlen ein, b, c, d sind die Koeffizienten.

Lassen Sie die (komplexen) Zahlen P., Q., R., S. seien Sie die Wurzeln dieses Polynoms f.

Dann

f((x)=((x– –P.)((x– –Q.)((x– –R.)((x– –S.){ displaystyle f (x) = (xP) (xQ) (xR) (xS)}

für alle x. Man kann den Wert isolieren P. aus dieser Gleichung:

P.=x– –f((x)((x– –Q.)((x– –R.)((x– –S.).{ displaystyle P = x – { frac {f (x)} {(xQ) (xR) (xS)}}.}

Wenn also als Festpunktiteration verwendet

x1: =x0– –f((x0)((x0– –Q.)((x0– –R.)((x0– –S.),{ displaystyle x_ {1}: = x_ {0} – { frac {f (x_ {0})} {(x_ {0} -Q) (x_ {0} -R) (x_ {0} -S )}},}

es ist in jedem Anfangspunkt stark stabil x0Q., R., S.
liefert nach einer Iteration die Wurzel P. = x1.

Außerdem, wenn man die Nullen ersetzt Q., R. und S.
durch Annäherungen qQ., rR., sS., so dass q, r, s sind nicht gleich P., dann P.
ist immer noch ein fester Punkt der gestörten Festpunktiteration

xk+1: =xk– –f((xk)((xk– –q)((xk– –r)((xk– –s),{ displaystyle x_ {k + 1}: = x_ {k} – { frac {f (x_ {k})} {(x_ {k} -q) (x_ {k} -r) (x_ {k} -s)}},}

schon seit

P.– –f((P.)((P.– –q)((P.– –r)((P.– –s)=P.– –0=P..{ displaystyle P – { frac {f (P)} {(Pq) (Pr) (Ps)}} = P-0 = P.}

Beachten Sie, dass sich der Nenner immer noch von Null unterscheidet. Diese Festpunktiteration ist eine Kontraktionsabbildung für x um P..

Der Schlüssel zur Methode besteht nun darin, die Festpunktiteration für zu kombinieren P. mit ähnlichen Iterationen für Q., R., S. in eine gleichzeitige Iteration für alle Wurzeln.

Initialisieren p, q, r, s::

p0 : = (0,4 + 0,9ich)0,
q0 : = (0,4 + 0,9ich)1,
r0 : = (0,4 + 0,9ich)2,
s0 : = (0,4 + 0,9ich)3.

Die Wahl von 0,4 + 0,9 ist nichts Besonderesich außer dass es weder eine reelle Zahl noch eine Wurzel der Einheit ist.

Nehmen Sie die Ersetzungen für n = 1, 2, 3, …:

pn=pn– –1– –f((pn– –1)((pn– –1– –qn– –1)((pn– –1– –rn– –1)((pn– –1– –sn– –1),{ displaystyle p_ {n} = p_ {n-1} – { frac {f (p_ {n-1})} {(p_ {n-1} -q_ {n-1}) (p_ {n- 1} -r_ {n-1}) (p_ {n-1} -s_ {n-1})}},}

qn=qn– –1– –f((qn– –1)((qn– –1– –pn)((qn– –1– –rn– –1)((qn– –1– –sn– –1),{ displaystyle q_ {n} = q_ {n-1} – { frac {f (q_ {n-1})} {(q_ {n-1} -p_ {n}) (q_ {n-1} -r_ {n-1}) (q_ {n-1} -s_ {n-1})}},}

rn=rn– –1– –f((rn– –1)((rn– –1– –pn)((rn– –1– –qn)((rn– –1– –sn– –1),{ displaystyle r_ {n} = r_ {n-1} – { frac {f (r_ {n-1})} {(r_ {n-1} -p_ {n}) (r_ {n-1} -q_ {n}) (r_ {n-1} -s_ {n-1})}},}

sn=sn– –1– –f((sn– –1)((sn– –1– –pn)((sn– –1– –qn)((sn– –1– –rn).{ displaystyle s_ {n} = s_ {n-1} – { frac {f (s_ {n-1})} {(s_ {n-1} -p_ {n}) (s_ {n-1} -q_ {n}) (s_ {n-1} -r_ {n})}}.}

Wiederholen Sie bis zu den Zahlen p, q, r, s
im Wesentlichen aufhören, sich relativ zur gewünschten Präzision zu ändern. Sie haben dann die Werte P., Q., R., S. in einer bestimmten Reihenfolge und in der gewählten Präzision. Damit ist das Problem gelöst.

Beachten Sie, dass eine komplexe Zahlenarithmetik verwendet werden muss und dass die Wurzeln gleichzeitig und nicht einzeln gefunden werden.

Variationen[edit]

Dieses Iterationsverfahren berechnet wie die Gauß-Seidel-Methode für lineare Gleichungen jeweils eine Zahl basierend auf den bereits berechneten Zahlen. Eine Variante dieses Verfahrens berechnet wie die Jacobi-Methode jeweils einen Vektor von Wurzelnäherungen. Beide Varianten sind effektive Wurzelfindungsalgorithmen.

Man könnte auch die Anfangswerte für wählen p, q, r, s
durch ein anderes Verfahren, sogar zufällig, aber auf eine Weise, die

  • Sie befinden sich in einem nicht allzu großen Kreis, der auch die Wurzeln von enthält f((x), zB der Kreis um den Ursprung mit Radius
    1+max((|ein|,|b|,|c|,|d|){ displaystyle 1+ max { big (} | a |, | b |, | c |, | d | { big)}}

    , (wo 1, ein, b, c, d sind die Koeffizienten von f((x))

und das

  • sie sind nicht zu nah beieinander,

Dies kann mit zunehmendem Grad des Polynoms zunehmend zu einem Problem werden.

Wenn die Koeffizienten reell sind und das Polynom einen ungeraden Grad hat, muss es mindestens eine reelle Wurzel haben. Verwenden Sie dazu einen realen Wert von p0 als erste Vermutung und machen q0 und r0usw. komplexe konjugierte Paare. Dann behält die Iteration diese Eigenschaften bei; das ist, pn wird immer real sein, und qn und rnusw. werden immer konjugiert sein. Auf diese Weise kann die pn wird zu einer echten Wurzel konvergieren P.. Alternativ können Sie alle anfänglichen Vermutungen realisieren. sie werden es bleiben.

Beispiel[edit]

Dieses Beispiel stammt aus der Referenz 1992. Die gelöste Gleichung lautet x3 – 3x2 + 3x – 5 = 0. Die ersten 4 Iterationen werden verschoben p, q, r scheinbar chaotisch, aber dann liegen die Wurzeln auf 1 Dezimalstelle. Nach der Iterationsnummer 5 haben wir 4 korrekte Dezimalstellen, und die nachfolgende Iterationsnummer 6 bestätigt, dass die berechneten Wurzeln fest sind. Dieses allgemeine Verhalten ist charakteristisch für die Methode. Beachten Sie auch, dass in diesem Beispiel die Wurzeln verwendet werden, sobald sie in jeder Iteration berechnet werden. Mit anderen Worten, die Berechnung jeder zweiten Spalte verwendet den Wert der zuvor berechneten Spalten.

it.-no. p q r
0 +1.0000 + 0.0000i +0,4000 + 0,9000i –0,6500 + 0,7200i
1 +1,3608 + 2,0222i –0,3658 + 2,4838i -2,3858 – 0,0284i
2 +2,6597 + 2,7137i +0,5977 + 0,8225i −0.6320−1.6716i
3 +2,2704 + 0,3880i +0,1312 + 1,3128i +0,2821 – 1,5015i
4 +2,5428 – 0,0153i +0,2044 + 1,3716i +0,2056 – 1,3721i
5 +2,5874 + 0,0000i +0,2063 + 1,3747i +0,2063 – 1,3747i
6 +2,5874 + 0,0000i +0,2063 + 1,3747i +0,2063 – 1,3747i

Beachten Sie, dass die Gleichung eine reelle Wurzel und ein Paar komplexer konjugierter Wurzeln hat und dass die Summe der Wurzeln 3 ist.

Ableitung der Methode über die Newtonsche Methode[edit]

Für jeden n-Tupel komplexer Zahlen gibt es genau ein monisches Polynom des Grades n das hat sie als Nullen (Multiplizitäten behalten). Dieses Polynom ist gegeben, indem alle entsprechenden linearen Faktoren multipliziert werden, d. H.

Gz→((X.)=((X.– –z1)⋯((X.– –zn).{ displaystyle g _ { vec {z}} (X) = (X-z_ {1}) cdots (X-z_ {n}).}

Dieses Polynom hat Koeffizienten, die von den vorgeschriebenen Nullen abhängen.

Gz→((X.)=X.n+Gn– –1((z→)X.n– –1+⋯+G0((z→).{ displaystyle g _ { vec {z}} (X) = X ^ {n} + g_ {n-1} ({ vec {z}}) X ^ {n-1} + cdots + g_ {0 } ({ vec {z}}).}

Diese Koeffizienten sind bis zu einem Vorzeichen die elementaren symmetrischen Polynome

α1((z→),…,αn((z→){ displaystyle alpha _ {1} ({ vec {z}}), dots, alpha _ {n} ({ vec {z}})}

von Grad 1, …, n.

Alle Wurzeln eines bestimmten Polynoms finden

f((X.)=X.n+cn– –1X.n– –1+⋯+c0{ displaystyle f (X) = X ^ {n} + c_ {n-1} X ^ {n-1} + cdots + c_ {0}}

mit Koeffizientenvektor

((cn– –1,…,c0){ displaystyle (c_ {n-1}, dots, c_ {0})}

gleichzeitig ist jetzt das gleiche wie ein Lösungsvektor für das System zu finden

c0=G0((z→)=((– –1)nαn((z→)=((– –1)nz1⋯znc1=G1((z→)=((– –1)n– –1αn– –1((z→)⋮cn– –1=Gn– –1((z→)=– –α1((z→)=– –((z1+z2+⋯+zn).{ displaystyle { begin {matrix} c_ {0} & = & g_ {0} ({ vec {z}}) & = & (- 1) ^ {n} alpha _ {n} ({ vec { z}}) & = & (- 1) ^ {n} z_ {1} cdots z_ {n} \ c_ {1} & = & g_ {1} ({ vec {z}}) & = & ( -1) ^ {n-1} alpha _ {n-1} ({ vec {z}}) \ & vdots & \ c_ {n-1} & = & g_ {n-1} ({ vec {z}}) & = & – alpha _ {1} ({ vec {z}}) & = & – (z_ {1} + z_ {2} + cdots + z_ {n}). end {matrix}}}

Die Durand-Kerner-Methode wird als mehrdimensionale Newton-Methode erhalten, die auf dieses System angewendet wird. Es ist algebraisch bequemer, diese Identitäten von Koeffizienten als die Identität der entsprechenden Polynome zu behandeln.

Gz→((X.)=f((X.){ displaystyle g _ { vec {z}} (X) = f (X)}

. Bei der Newtonschen Methode sieht man nach einem Anfangsvektor

z→{ displaystyle { vec {z}}}

für einen Inkrementvektor

w→{ displaystyle { vec {w}}}

so dass

Gz→+w→((X.)=f((X.){ displaystyle g _ {{ vec {z}} + { vec {w}}} (X) = f (X)}

ist bis zu Termen zweiter und höherer Ordnung im Inkrement erfüllt. Hierfür löst man die Identität

f((X.)– –Gz→((X.)=∑k=1n∂Gz→((X.)∂zkwk=– –∑k=1nwk∏j≠k((X.– –zj).{ displaystyle f (X) -g _ { vec {z}} (X) = sum _ {k = 1} ^ {n} { frac { partielles g _ { vec {z}} (X)} { partielle z_ {k}}} w_ {k} = – sum _ {k = 1} ^ {n} w_ {k} prod _ {j neq k} (X-z_ {j}).}

Wenn die Zahlen

z1,…,zn{ displaystyle z_ {1}, dots, z_ {n}}

sind paarweise unterschiedlich, dann bilden die Polynome in Bezug auf die rechte Seite eine Basis der n-dimensionaler Raum

C.[X]n– –1{ displaystyle mathbb {C} [X]_ {n-1}}

von Polynomen mit maximalem Grad n – 1. Also eine Lösung

w→{ displaystyle { vec {w}}}

zur Inkrementgleichung existiert in diesem Fall. Die Koordinaten des Inkrements

w→{ displaystyle { vec {w}}}

werden einfach durch Auswerten der Inkrementgleichung erhalten

– –∑k=1nwk∏j≠k((X.– –zj)=f((X.)– –∏j=1n((X.– –zj){ displaystyle – sum _ {k = 1} ^ {n} w_ {k} prod _ {j neq k} (X-z_ {j}) = f (X) – prod _ {j = 1 } ^ {n} (X-z_ {j})}

an den Punkten

X.=zk{ displaystyle X = z_ {k}}

, was in … endet

– –wk∏j≠k((zk– –zj)=– –wkGz→‘((zk)=f((zk){ displaystyle -w_ {k} prod _ {j neq k} (z_ {k} -z_ {j}) = – w_ {k} g _ { vec {z}} ‘(z_ {k}) = f (z_ {k})}

, das ist wk=– –f((zk)∏j≠k((zk– –zj).{ displaystyle w_ {k} = – { frac {f (z_ {k})} { prod _ {j neq k} (z_ {k} -z_ {j})}}.}

Wurzeleinschluss über Gerschgorins Kreise[edit]

Im Quotientenring (Algebra) der Restklassen modulo ƒ (X.), die Multiplikation mit X. definiert einen Endomorphismus mit den Nullen von ƒ (X.) als Eigenwerte mit den entsprechenden Multiplizitäten. Bei Auswahl einer Basis wird der Multiplikationsoperator durch seine Koeffizientenmatrix dargestellt EIN, die Begleitmatrix von ƒ (X.) für diese Basis.

Da jedes Polynom modulo reduziert werden kann ƒ (X.) bis zu einem Gradpolynom n – 1 oder niedriger, der Raum der Restklassen kann mit dem Raum der Polynome des Grads identifiziert werden, der durch begrenzt ist n – 1. Eine problemspezifische Basis kann aus der Lagrange-Interpolation als Menge von entnommen werden n Polynome

bk((X.)=∏1≤j≤n,j≠k((X.– –zj),k=1,…,n,{ displaystyle b_ {k} (X) = prod _ {1 leq j leq n, ; j neq k} (X-z_ {j}), quad k = 1, dots, n, }}

wo

z1,…,zn∈C.{ displaystyle z_ {1}, dots, z_ {n} in mathbb {C}}

sind paarweise unterschiedliche komplexe Zahlen. Beachten Sie, dass die Kernelfunktionen für die Lagrange-Interpolation sind

L.k((X.)=bk((X.)bk((zk){ displaystyle L_ {k} (X) = { frac {b_ {k} (X)} {b_ {k} (z_ {k})}}

.

Für den Multiplikationsoperator, der auf die Basispolynome angewendet wird, erhält man aus der Lagrange-Interpolation

X.⋅bk((X.)modf((X.)=X.⋅bk((X.)– –f((X.){ displaystyle X cdot b_ {k} (X) mod f (X) = X cdot b_ {k} (X) -f (X)}

=∑j=1n((zj⋅bk((zj)– –f((zj))⋅bj((X.)bj((zj){ displaystyle = sum _ {j = 1} ^ {n} { Big (} z_ {j} cdot b_ {k} (z_ {j}) – f (z_ {j}) { Big)} cdot { frac {b_ {j} (X)} {b_ {j} (z_ {j})}}

=zk⋅bk((X.)+∑j=1nwj⋅bj((X.){ displaystyle = z_ {k} cdot b_ {k} (X) + sum _ {j = 1} ^ {n} w_ {j} cdot b_ {j} (X)}

,

wo

wj=– –f((zj)bj((zj){ displaystyle w_ {j} = – { frac {f (z_ {j})} {b_ {j} (z_ {j})}}

sind wieder die Weierstrass Updates.

Die Begleitmatrix von ƒ (X.) ist deshalb

EIN=dicheinG((z1,…,zn)+((1⋮1)⋅((w1,…,wn).{ displaystyle A = mathrm {diag} (z_ {1}, dots, z_ {n}) + { begin {pmatrix} 1 \ vdots \ 1 end {pmatrix}} cdot left ( w_ {1}, dots, w_ {n} right).}

Aus dem transponierten Matrixfall des Gershgorin-Kreissatzes folgt, dass alle Eigenwerte von EINdas heißt, alle Wurzeln von ƒ (X.), sind in der Vereinigung der Scheiben enthalten

D.((eink,k,rk){ displaystyle D (a_ {k, k}, r_ {k})}

mit einem Radius

rk=∑j≠k|einj,k|{ displaystyle r_ {k} = sum _ {j neq k} { big |} a_ {j, k} { big |}}

.

Hier hat man

eink,k=zk+wk{ displaystyle a_ {k, k} = z_ {k} + w_ {k}}

Die Zentren sind also die nächsten Iterationen der Weierstrass-Iteration und die Radien

rk=((n– –1)|wk|{ displaystyle r_ {k} = (n-1) left | w_ {k} right |}

Das sind Vielfache der Weierstrass-Updates. Wenn die Wurzeln von ƒ (X.) sind alle gut isoliert (relativ zur Rechengenauigkeit) und die Punkte

z1,…,zn∈C.{ displaystyle z_ {1}, dots, z_ {n} in mathbb {C}}

Wenn diese Wurzeln ausreichend nahe an diesen Wurzeln liegen, werden alle Scheiben disjunkt, sodass jede genau eine Null enthält. Die Mittelpunkte der Kreise sind bessere Annäherungen an die Nullen.

Jede konjugierte Matrix

T.EINT.– –1{ displaystyle TAT ^ {- 1}}

von EIN ist auch eine Begleitmatrix von ƒ (X.). Wählen T. als diagonale Matrix verlässt die Struktur von EIN invariant. Die Wurzel in der Nähe

zk{ displaystyle z_ {k}}

ist in einem isolierten Kreis mit Mittelpunkt enthalten

zk{ displaystyle z_ {k}}

Egal ob T.. Auswahl der optimalen Diagonalmatrix T. Für jeden Index ergeben sich bessere Schätzungen (siehe Lit. Petkovic et al. 1995).

Konvergenzergebnisse[edit]

Die Verbindung zwischen der Taylorreihenerweiterung und der Newtonschen Methode legt nahe, dass der Abstand von

zk+wk{ displaystyle z_ {k} + w_ {k}}

zur entsprechenden Wurzel ist in der Reihenfolge

Ö((|wk|2){ displaystyle O { big (} | w_ {k} | ^ {2} { big)}}

, wenn die Wurzel gut von nahegelegenen Wurzeln isoliert ist und die Annäherung ausreichend nahe an der Wurzel liegt. Nachdem die Annäherung nahe ist, konvergiert die Newtonsche Methode quadratisch;; Das heißt, der Fehler wird bei jedem Schritt quadriert (wodurch der Fehler erheblich reduziert wird, sobald er kleiner als 1 ist). Bei der Durand-Kerner-Methode ist die Konvergenz quadratisch, wenn der Vektor

z→=((z1,…,zn){ displaystyle { vec {z}} = (z_ {1}, dots, z_ {n})}

ist nahe an einer Permutation des Vektors der Wurzeln von f.

Für die Schlussfolgerung der linearen Konvergenz gibt es ein spezifischeres Ergebnis (siehe Lit. Petkovic et al. 1995). Wenn der Anfangsvektor

z→{ displaystyle { vec {z}}}

und sein Vektor von Weierstrass-Updates

w→=((w1,…,wn){ displaystyle { vec {w}} = (w_ {1}, dots, w_ {n})}

befriedigt die Ungleichung

max1≤k≤n|wk|≤15nMindest1≤j<k≤n|zk– –zj|,{ displaystyle max _ {1 leq k leq n} | w_ {k} | leq { frac {1} {5n}} min _ {1 leq j

dann gilt diese Ungleichung auch für alle Iterationen, alle Einschlussdisketten

D.((zk+wk,((n– –1)|wk|){ displaystyle D { big (} z_ {k} + w_ {k}, (n-1) | w_ {k} | { big)}}

sind disjunkt und lineare Konvergenz mit einem Kontraktionsfaktor von 1/2 gilt. Ferner können die Einschlussscheiben in diesem Fall als ausgewählt werden

D.((zk+wk,14|wk|),k=1,…,n,{ displaystyle D left (z_ {k} + w_ {k}, { tfrac {1} {4}} | w_ {k} | right), quad k = 1, dots, n,}

jedes enthält genau eine Null von f.

Fehlschlagen der allgemeinen Konvergenz[edit]

Die Weierstrass / Durand-Kerner-Methode ist im Allgemeinen nicht konvergent: Mit anderen Worten, es ist nicht wahr, dass für jedes Polynom die Menge der Anfangsvektoren, die schließlich zu Wurzeln konvergieren, offen und dicht ist. Tatsächlich gibt es offene Sätze von Polynomen mit offenen Sätzen von Anfangsvektoren, die zu anderen periodischen Zyklen als Wurzeln konvergieren (siehe Reinke et al.)

Verweise[edit]

  1. ^ Petković, Miodrag (1989). Iterative Methoden zur gleichzeitigen Einbeziehung von Polynomnullen. Berlin [u.a.]: Springer. S. 31–32. ISBN 978-3-540-51485-5.

Externe Links[edit]