Newton-Raphson iteráció

Cél: valós gyökök közelítése.

Legyen f kétszer differenciálható. ∃x∈[a,b]: f[x]=0? Hogyan keressük meg a gyököket? Pl. folytonossági megfontolások és intervallumfelezés. Az alábbi módszer a deriváltra épít.
Alapötlet: legyen (Subscript[x, 0])egy jó közelítése a gyöknek és használjuk a deriváltat egy jobb közelítés megadására:

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

f[x_]:=Cos[x]-(x^3);
Solve[f[x]==0,x]

Plot[f[x],{x,-5,5},PlotRange->{-10,10}]

Black-Box típusú feladatmegoldás

FindRoot[f[x],{x,1}]

Options[FindRoot]

White-Box típusú feladatmegoldás

Most mi is megoldjuk iterációval! ⟶ Nest, NestList, NestWhile
A Mathematicában elegánsan képezhetjük az iteráltakat.

Nest[F,x,3]

NestList[F,x,3]

A Newton-Raphson iteráció magfüggvénye

NewtonRaphsonStep[x_]:=N[x-f[x]/f'[x]];

Nest[NewtonRaphsonStep,1,3]

NestList[NewtonRaphsonStep,1,3]

Ezt egy kicsit nehezebb megérteni, mindenki próbálkozzon azért!

NestWhile[NewtonRaphsonStep,1,Unequal,2]

Konvergencia gyorsaság?

f[x_]:=x^2-5

NewtonRaphsonStepb[x_] := N[x - f[x]/f'[x], 40];

NestList[NewtonRaphsonStepb,3,7]//TableForm

N[Sqrt[5],40]

Adjuk meg 3 tizedesjegy pontossággal, felhasználva a NewtonRaphsonStep függvényt, az alábbi egyenletek összes zéróhelyét, melyek benne vanak a 0 3 sugarú környezetében.

eq1=(x^2)==5;
eq2=(x^3)==2;
eq3=4 x ((Cos[x])^2)+π/2==2x +Sin[2x];

A harmadik egyenlet esete (3 valós gyök [-3,3]-ban)

f[x_]:=4 x ((Cos[x])^2)+π/2-2x -Sin[2x];

Plot[f[x],{x,-3,3}]

{Nest[NewtonRaphsonStep,-2,4],Nest[NewtonRaphsonStep,1,4],Nest[NewtonRaphsonStep,2,4]}

Az első egyenlet
(f függvényt újra definiáljuk mert ez globális a NewtonRaphsonStep-re!)

f[x_]:=(x^2)-5

NewtonRaphsonStep[x]//Simplify

Négyzetgyökvonás

Nest[NewtonRaphsonStep,2,4]

N[(Sqrt[5])]

Most osztályozzuk a valós egyenes pontjait: 
A osztály) Konvergencia van és lim=Sqrt[5], 
B osztály) Konvergencia van és lim=-Sqrt[5], 
C osztály) Nincs konvergencia vagy az interációssorozat nem értelmezhető

x0

TableForm[Table[Nest[NewtonRaphsonStep,x0,10],{x0,-5,5,1/4}]]

Projektmunka: NR Vizualizáció

Egy lépés vizualizációja

Clear[f,g]

f[x_]:=(x^2)-5;

g[x_]:=(x^3)-2;

NewtonRaphsonVis[f_,x0_]:=
Module[{x},
Plot[f[x],{x,x0-1,x0+1},PlotStyle->{Thickness[.01],RGBColor[0,1,0]},AspectRatio->1,Epilog->{RGBColor[1,0,0],Line[{{x0,f[x0]},{-f[x0]/(D[f[x],x]/.x->x0)+x0,0}}],Line[{{x0,0},{x0,f[x0]}}],RGBColor[0,0,1],PointSize[.03],Point[{-f[x0]/(D[f[x],x]/.x->x0)+x0,0}]}]
]

NewtonRaphsonVis[f,3]

Nest[NewtonRaphsonStep,3,1]

NewtonRaphsonVis[g,2]

Memo: f globális NR-re nézve!

f[x_]=g[x];

Nest[NewtonRaphsonStep,2,1]

Oldjuk meg az alábbi egyenletrendszert:

f[x,y]=0, 
g[x,y]=0

Vektoriteráció:

F[{x_,y_}]:={x+1,2y}

NestList[F,{0,1},5]//TableForm

f1[x_,y_]=(x^2)+(y^2)-5;
f2[x_,y_]=x-y-1;

Solve[{f1[x,y]==0,f2[x,y]==0},{x,y}]

Meg tudjuk-e közelíteni hasonlóan a megoldásokat?

ContourPlot[{f1[x,y]==0,f2[x,y]==0},{x,-3,3},{y,-3,3},ImageSize->{200,200},GridLines->Automatic,ContourStyle->{{Blue,Thickness[.01]},{Red,Thickness[.01]}}]

Általánosítás 2 dimenzióra a Jacobi mátrix segítségével:

J[x_,y_]=(({{D[f1[x,y],x], D[f1[x,y],y]}, {D[f2[x,y],x], D[f2[x,y],y]}}))

J[1/2,1/2]

NewtonRaphsonStep2D[{x_,y_}]:=N[{x,y}-Inverse[J[x,y]].{f1[x,y],f2[x,y]}];

TableForm[NestList[NewtonRaphsonStep2D,{1/2,1/2},5]]

TableForm[NestList[NewtonRaphsonStep2D,{-3,-1/2},5]]

NoOfIterations=6;GridSize=.1;

F[z_]:=z^3-2;

NS[z_]:=z-F[z]/F'[z]

NestList[NS,1+I,10]//N//Chop//TableForm

z/.NSolve[z^3==2,z]

NestList[NS,I,10]//N//Chop//TableForm

NestList[NS,-I,10]//N//Chop//TableForm

Három különböző pontból indulva három különböző pontba tartanak a komplex iterációs sorozatok. Ezek éppen 2 (komplex) köbgyökei.

Konvergencia van 'majdnem' mindenhol, de hogy hová tartunk, nem nyilvánvaló: Ansatz, csak a 3 köbgyökhöz, ábrázoljuk egy medencét.
Az ábrázolás kényelemes a MatrixPlot utasítással. Egy példa először: sakktábla

Table[If[EvenQ[i+j],1,0],{j,-2,2},{i,-2,2}]//TableForm

MatrixPlot[Table[If[EvenQ[i+j],1,0],{j,-2,2},{i,-2,2}],Mesh->None,ColorRules->{1->Black,0->White}]

z/.Solve[z^3==2,z]//ExpToTrig

Arg[%]//N

Argumetumok szerint színezünk. Fekete pontok: a valós köbgyök a limesz.

Timing[MatrixPlot[Table[If[Abs[Arg[Nest[NS,i+j I,6]]/.{Indeterminate->10}]<0.2,1,0],{j,-2.,2.,GridSize},{i,-2.,2.,GridSize}],Mesh->None,Mesh->False,ImageSize->{250,250},ColorRules->{1->Black,0->White}]]

3 köbgyök medencéje 3 különböző színnel.

Timing[MatrixPlot[Table[θ=Arg[Nest[NS,i+j I,NoOfIterations]/.{Indeterminate->10}];If[θ>1.8,1,If[θ<-1.8,2,0]],{j,-2.,2.,GridSize},{i,-2.,2.,GridSize}],Mesh->None,Mesh->False,ImageSize->{250,250},ColorRules->{2->Red,0->Green,1->Blue}]]

Megjegyzés:  Konvergencia bizonyítást itt nem közlünk, érdekesebb nemkonvergens "attraktorok"

Színezés konvergencia gyorsasága szerint is

Ez eddig empirikus matematika. De a konvergencia bizonyítása lehetséges fixpont-tételek felhasználásával (vonzó/taszító fixpontok, deriváltak )