GidaEkuazio ez-linealakertaina

Newton-Raphson metodoa

Erreferentziazko metodo iteratiboa: f linealizatu uneko iteratuan eta tangentearen errora jauzi egin. Dedukzio osoa hiru bidetatik eta ordena koadratikoaren frogapena bere errore-ekuazioarekin.

Formula

xk+1=xk−f(xk)f′(xk),k=0,1,2,…x_{k+1}=x_k-\frac{f(x_k)}{f'(x_k)},\qquad k=0,1,2,\dots
Newton-Raphson metodoa.

Geometrikoki, iterazio bakoitzak kurba (xk,f(xk))(x_k,f(x_k)) puntuko zuzen ukitzaileaz ordezkatzen du eta hurrengo hurbilketa gisa ukitzaile horrek ardatza mozten duen puntua hartzen du. Puntu finkoko metodo bat da, ϕ(x)=x−f(x)f′(x)\phi(x)=x-\frac{f(x)}{f'(x)} duena: puntu bakarrekoa, memoriarik gabea eta deribatuduna.

Dedukzioa eta ordena

FrogapenaDedukzioa: Newton-Raphson eta bere ordena koadratikoaIkusi orri propio gisa →

1. bidea: zuzen ukitzailea

  1. Uneko xkx_k iteratuan, y=f(x)y=f(x) kurbaren zuzen ukitzailea hau da:

    y=f(xk)+f′(xk)(x−xk)y=f(x_k)+f'(x_k)(x-x_k)

  2. Ukitzailea ff-ren hurbilketa lineal onena da xkx_k-tik hurbil; beraz, hurrengo iteratu gisa ukitzailea anulatzen den puntua hartzen dugu (y=0y=0):

    0=f(xk)+f′(xk)(xk+1−xk)  ⇒  xk+1=xk−f(xk)f′(xk)0=f(x_k)+f'(x_k)(x_{k+1}-x_k)\;\Rightarrow\; x_{k+1}=x_k-\frac{f(x_k)}{f'(x_k)}

2. bidea: Kalkuluaren Oinarrizko Teorema

  1. ff Kalkuluaren Oinarrizko Teoremaren bidez idazten dugu xkx_k-tik abiatuta eta integrala laukizuzen batez hurbiltzen dugu (f′(xk)f'(x_k) integrakizun konstantea, Euler-en dedukzioko ideia bera):

    f(x)=f(xk)+∫xkxf′(t) dt  ≈  f(xk)+f′(xk)(x−xk)f(x)=f(x_k)+\int_{x_k}^{x}f'(t)\,dt\;\approx\; f(x_k)+f'(x_k)(x-x_k)

  2. x=αx=\alpha-n ebaluatzen dugu, non f(α)=0f(\alpha)=0 den, eta α\alpha askatzen dugu:

    0≈f(xk)+f′(xk)(α−xk)  ⇒  α≈xk−f(xk)f′(xk)0\approx f(x_k)+f'(x_k)(\alpha-x_k)\;\Rightarrow\;\alpha\approx x_k-\frac{f(x_k)}{f'(x_k)}

  3. α\alpha-ren hurbilketa hori da hurrengo iteratua. Integrala kuadratura aberatsagoekin hurbiltzeak (trapezioa, erdiko puntua, Simpson) ordena handiagoko metodoak sortzen ditu bide beretik.

2. ordenaren frogapena (errore-ekuazioa)

  1. Izan bedi α\alpha erro sinplea (f(α)=0f(\alpha)=0, f′(α)≠0f'(\alpha)\ne 0), ek=xk−αe_k=x_k-\alpha errorea eta c2=12f′′(α)f′(α)c_2=\frac{1}{2}\frac{f''(\alpha)}{f'(\alpha)}. f(xk)f(x_k) Taylor bidez garatzen dugu α\alpha-ren inguruan; f(α)f(\alpha) gai konstantea desagertu egiten da:

    f(xk)=f′(α) ek+12f′′(α) ek2+O(ek3)=f′(α)[ek+c2ek2]+O(ek3)f(x_k)=f'(\alpha)\,e_k+\frac{1}{2}f''(\alpha)\,e_k^2+\mathcal{O}(e_k^3)=f'(\alpha)\bigl[e_k+c_2e_k^2\bigr]+\mathcal{O}(e_k^3)

  2. Deribatua ere garatzen dugu:

    f′(xk)=f′(α)+f′′(α) ek+O(ek2)=f′(α)[1+2c2ek]+O(ek2)f'(x_k)=f'(\alpha)+f''(\alpha)\,e_k+\mathcal{O}(e_k^2)=f'(\alpha)\bigl[1+2c_2e_k\bigr]+\mathcal{O}(e_k^2)

  3. Bi garapenak zatitzen ditugu. f′(α)f'(\alpha) faktorea ezabatzen da eta, 11+2c2ek=1−2c2ek+O(ek2)\frac{1}{1+2c_2e_k}=1-2c_2e_k+\mathcal{O}(e_k^2) erabiliz:

    f(xk)f′(xk)=(ek+c2ek2)(1−2c2ek)+O(ek3)=ek−c2ek2+O(ek3)\frac{f(x_k)}{f'(x_k)}=\bigl(e_k+c_2e_k^2\bigr)\bigl(1-2c_2e_k\bigr)+\mathcal{O}(e_k^3)=e_k-c_2e_k^2+\mathcal{O}(e_k^3)

  4. Newton-en formulan α\alpha kentzen dugu eta ordezkatzen dugu: eke_k-ren gai linealak ezabatzen dira eta errore-ekuazio koadratikoa geratzen da. Newton-en metodoak p=2p=2 ordena du.

    ek+1=xk+1−α=ek−f(xk)f′(xk)=c2ek2+O(ek3)e_{k+1}=x_{k+1}-\alpha=e_k-\frac{f(x_k)}{f'(x_k)}=c_2e_k^2+\mathcal{O}(e_k^3)

Newton-etik harago

Newton ia gainerako guztiaren abiapuntua da: deribatua diferentziez ordezkatuz sekantea eta Steffensen lortzen dira; konposatuz eta pisu-funtzioak gehituz ordena altuko metodoak eraikitzen dira (Traub, Ostrowski, Jarratt); eta bere bertsio bektorialak ekuazio ez-linealen sistemak ebazten ditu. EDOetarako metodo inplizituetan agertzen diren ekuazio inplizituetarako tresna estandarra ere bada.