Szénási Eszter
SZTE TTIK Matematika BSc,
Numerikus matematika projekt
2015. november 30.

A Newton-Raphson iteráció kezdeti értéktől való érzékenysége

Medencék (attraktorok) színezése

Alapfeladat: függvény zérushelyének közelítése

Az f(x)=0 nemlineáris egyenlet (valamely) ξ ∈ ℝ zérushelyének meghatározása, ahol f(x) differenciálható függvény ξ egy (kicsiny) környezetében, ott f'(x) ≠0 és abban a környezetben adott egy (Subscript[x, 0])∈ ℝ, melyet kezdeti közelítésnek nevezünk.

Geometriai megközelítés (érintő módszer): Newton-Raphson iteráció

Az érintő egyenlete ((Subscript[x, 0]),f((Subscript[x, 0]))) pontban  y=f(x) függvény esetén

y=f((Subscript[x, 0]))+f'((Subscript[x, 0]))(x-(Subscript[x, 0]))

Ennek az x-tengellyel való ((Subscript[x, 1]),0) metszéspontjának (Subscript[x, 1]) koordinátáját az alábbi egyenletből határozzuk meg

0=f((Subscript[x, 0]))+f'((Subscript[x, 0]))((Subscript[x, 1])-(Subscript[x, 0]))

(Subscript[x, 1])=(Subscript[x, 0])-((f((Subscript[x, 0])))/(f'((Subscript[x, 0]))))

Az eljárást ismételve most az (Subscript[x, 1]) pontból, majd az újonnan keletkezett pontokból, az {(Subscript[x, m])} ⊂ ℝ iterációs sorozathoz jutunk, amelynek általános képlete:

(Subscript[x, m]):=(Subscript[x, m-1])-((f((Subscript[x, m-1])))/(f'((Subscript[x, m-1])))), m=1,2,...

Alkalmazása - gyökvonás

A Newton-Raphson iteráció alkalmazása pozitív számokból való gyökvonás gyors elvégzésére.

Legyen f(x) =(x^r)-a, melynek zérushelye: ξ = (a^(1/r)) (a>0,r>0)

Elegendő az a>1 esetet tekinteni, mert ha 0<a<1, akkor

(a^(1/r))=(1/((1/a)^(1/r))) és (1/a)>1

Tehát ebben az esetben az iteráció:

(Subscript[x, m]):=(Subscript[x, m-1])-((f((Subscript[x, m-1])))/(f'((Subscript[x, m-1]))))=(Subscript[x, m-1])-(((Subscript[(x^r), m-1])-a)/(r (Subscript[(x^(r-1)), m-1])))=(1/r)((r-1)(Subscript[x, m-1])+(a/(Subscript[(x^(r-1)), m-1]))), m=1,2,...

Manipulate[
DynamicModule[{f,T,x,adat,u},
f[x_]:=x^r-a;
T[x_]:=x-f[x]/f'[x];
adat=NestWhileList[T,(a^(1/r))+2.,Function[x,Abs[f[x]]>10^(-6)]];
Column[{Row[{"(Subscript[x, 0])=",(a^(1/r))+2.,"   ","(OverBar[x])=",Last[adat]}],
Show[Plot[f[x],{x,(a^(1/r))-2.,(a^(1/r))+2.1},PlotRange->All],Graphics[adat/.u_Real->Line[{{u,0},{u,f[u]},{T[u],0}}]],PlotRange->All]
}]
],
{r,{2,3,4,5}},{a,{2,3,4,5}}]

Kezdeti értéktől való függés érzékenysége

Problémás értékek: f'(x) “kicsi”.

Az ábrán: cos(x) függvény zérushelyeinek közelítése NR-iterációval, dinamikusan

Már itt is látható, mennyire függ a rendszer viselkedése a kezdőérték választásától

Manipulate[
DynamicModule[{f,T,x,adat,u},
f[x_]:=Cos[x];
T[x_]:=x-f[x]/f'[x];
adat=NestWhileList[T,x0,Function[x,Abs[f[x]]>10^(-6)]];
Column[{Row[{"(Subscript[x, 0])=",x0,"   ","(OverBar[x])=",Last[adat]}],
Show[Plot[f[x],{x,Min[adat]-1,Max[adat]+1}],Graphics[adat/.u_Real->Line[{{u,0},{u,f[u]},{T[u],0}}]]]
}]
],
{x0,-1.,Pi+1.}]

Megjegyzés: konvergencia

ξ egyszeres zérushelye f(x)-nek ⇔f(ξ)=0 és f'(ξ)≠0.

A közelítés hibája: (Subscript[e, m])=(Subscript[x, m])-ξ, ahol ξ az f(x) gyöke

A Newton-Raphson iteráció hibaképlete : (Subscript[e, m])=((f''((Subscript[α, m-1])))/(2f'((Subscript[x, m-1]))))((Subscript[e, m-1])^2), ahol αm-1 ∈ (ξ, (Subscript[x, m-1]))

A Newton-Raphson iteráció négyzetes konvergenciája: (lim_(m->∞))((Subscript[e, m])/((Subscript[e, m-1])^2))=((f''(ξ))/(2f'(ξ)))

Aszimptotikus hibakonstans: ((f''(ξ))/(2f'(ξ)))

Általánosítás a komplex síkra

Példa: komplex egységgyökök közelítése

Legyen f(z) =(z^r)-1, (r=2,3,4,5,....)

Az iteráció azonos a valós esettel:

(Subscript[z, m]):=(Subscript[z, m-1])-((f((Subscript[z, m-1])))/(f'((Subscript[z, m-1]))))=(Subscript[z, m-1])-(((Subscript[(z^r), m-1])-1)/(r (Subscript[(z^(r-1)), m-1]))), m=1,2,...

Legyen r=3:

f[z_]:=z^3-1;
Show[DensityPlot[Abs[f[x+I y]],{x,-1.1,1.1},{y,-1.1,1.1},PlotLegends->Automatic],
Graphics[{Thread[{{Yellow,Red, Green},
PointSize[0.05],Map[Point[Through[{Re,Im}[#]]]&,z/.NSolve[f[z]==0,z]]}]}]
]

Manipuláció - dinamikus megjelenítés

Manipulate[
DynamicModule[{f,T,z,adat,u,sol},
f[z_]:=z^3-1;
T[z_]:=z-f[z]/f'[z];
sol=z/.NSolve[f[z]==0,z];
adat=NestWhileList[T,x0+I y0,Function[z,Abs[f[z]]>10^(-6)]];
Column[{Row[{"(Subscript[z, 0])=",x0+I y0,"   ","(OverBar[z])=",Last[adat]}],
Row[{Graphics[{
Texture[],Polygon[{{-1,-1},{-1,1},{1,1},{1,-1}},VertexTextureCoordinates->{{0,1},{0,0},{1,0},{1,1}}]
,PointSize[0.05],Point[{x0,y0}]},PlotRange->{{-1,1},{-1,1}},Frame->True,ImageSize->{300,300}],
Show[Graphics[{Thread[{{Yellow,Red, Green},
PointSize[0.05],Map[Point[Through[{Re,Im}[#]]]&,sol]}],PointSize[0.05],Point[{x0,y0}],Line[Map[Through[{Re,Im}[#]]&,adat]],PointSize[0.02],Point[Map[Through[{Re,Im}[#]]&,adat]]},
AspectRatio->1,PlotRange->{{-5,5},{-5,5}},Frame->True],
ImageSize->{300,300}
]
}]
}]
],
{{x0,0.4,"Re (Subscript[z, 0])"},-1,1},{{y0,0.4,"Im (Subscript[z, 0])"},-1,1}]

Magasabb hatványokra

Manipulate[
DynamicModule[{f,T,z,adat,u,sol,critlines},
f[z_]:=z^p-1;
T[z_]:=z-f[z]/f'[z];
sol=z/.NSolve[f[z]==0,z,Complexes];
critlines=Map[Line[{{0,0},5(({{Cos[Pi/p], Sin[Pi/p]}, {-Sin[Pi/p], Cos[Pi/p]}})).Through[{Re,Im}[#]]}]&,sol];
adat=NestWhileList[T,x0+I y0,Function[z,Abs[f[z]]>10^(-6)]];
Column[{Row[{"(Subscript[z, 0])=",x0+I y0,"   ","(OverBar[z])=",Last[adat]}],
Row[{Graphics[{critlines,
PointSize[0.05],Point[{x0,y0}]},PlotRange->{{-1,1},{-1,1}},Frame->True,ImageSize->{200,200}],
Show[
Graphics[{
critlines,
PointSize[0.05],Point[{x0,y0}],Red,Opacity[0.5],PointSize[0.05],Map[Point[Through[{Re,Im}[#]]]&,sol],Black,PointSize[0.05],Opacity[1],Point[{x0,y0}],Line[Map[Through[{Re,Im}[#]]&,adat]],PointSize[0.02],Point[Map[Through[{Re,Im}[#]]&,adat]]},
AspectRatio->1,PlotRange->{{-5,5},{-5,5}},Frame->True],
ImageSize->{200,200}]
}]
}]
],
{{p,3},{3,4,5,6,7},ControlType->RadioButtonBar},{{x0,0.6,"Re (Subscript[z, 0])"},-1,1},{{y0,0.4,"Im (Subscript[z, 0])"},-1,1}]

Newton-fraktálok

Fraktálok

Végtelenül komplex geometriai - úgynevezett önhasonló alakzatok, amelyek két gyakori, jellemző tulajdonsággal rendelkeznek:

Határoló vonalaik vagy -felületeik végtelenül „gyűröttek" vagy „érdesek", illetve „szakadásosak", vagyis nem-differenciálhatóak.

Ebből kifolyólag az olyan geometriai jellemzőik, mint a kerület, terület, térfogat, ívhossz, felszín, stb. elfajult (végtelen vagy nulla) értékeket adnak, és általában is, a térszemlélettel ellentétesen, meglepő és paradox módon viselkednek.

Newton-fraktál

Egy korlátos halmaz a komplex számsíkon, melyet egy konkrét polinom gyökeit számoló Newton-iteráció határoz meg.

A Newton-fraktálra tekinthetünk úgy, mint egy hozzárendelésre a komplex számsíkon, amely a (Subscript[z, 0]) kezdeti értékhez rendeli hozzá az iteráció határértékét (színezés).

mivel véges sok határérték van (n. gyököt számolunk), ezért a határérték argumentuma szerint célszerű színezni

newt=Compile[{{n,_Integer},{z,_Complex}},Arg[FixedPoint[#-(#^n-1)/(n #^(n-1))&,z,100]]];

Show[GraphicsGrid[Partition[Table[ListDensityPlot[Table[newt[n,b+a I],{a,-1.1,1.1,0.015},{b,-1.1,1.1,0.015}],Mesh->False,
ColorFunction->"BrightBands",Frame->False,DisplayFunction->Identity,ImageSize->{300,300}],{n,3,6}],3]]]

image=Image[ListDensityPlot[Table[newt[3,b+a I],{a,-1.1,1.1,0.008},{b,-1.1,1.1,0.015}],Mesh->False,Frame->False,ColorFunction->"BrightBands",DisplayFunction->Identity,ImageSize->{300,300}]]

Források

http://mathworld.wolfram.com/NewtonsMethod.html

http : // mathforum.org/advanced/robertd/newtons.html

https://reference.wolfram.com/language/tutorial/UnconstrainedOptimizationNewtonsMethodMinimum.html

http://www.model.u-szeged.hu/kurzus-19-1-felsobb_mathematica.html

Móricz Ferenc: Bevezetés a numerikus matematikába (Polygon jegyzettár)

Richard L. Burden, J. Douglas Faires: Numerical Analysis

Berkey, Blanchard: Calculus

https://en.wikipedia.org/wiki/Newton_fractal

http://www.mitchr.me/SS/newton/

http://eldar.mathstat.uoguelph.ca/dashlock/ftax/Newton.html

Köszönet Dr. Karsai Jánosnak a programozásban nyújtott segítségéért

Köszönöm a figyelmet!

Newton-fraktál az (x^8)+15 (x^4)-16 polinomra