GidaSistema ez-linealakaurreratua

Kostua eta eraginkortasuna n dimentsioan

Iterazio bakoitzeko kostuaren kontabilitatea sistemetan: nn ebaluazio FF bakoitzeko, n2n^2 jacobiar bakoitzeko, sistema linealen kostua, eraginkortasun-indizeak eta optimalitate-aieru multidimentsionala.

Zenbat kostatzen den iterazio bakoitza

nn dimentsioan, FF funtzio bektorialaren ebaluazio bakoitza nn ebaluazio eskalar dira, eta F′F' jacobiar bakoitza n2n^2. Gainera, zuzenean ebatzitako sistema lineal bakoitzak n33+n2−n3\frac{n^3}{3}+n^2-\frac{n}{3} biderketa/zatiketa kostatzen du, eta koefiziente-matrize bereko qq sistema ebazteak (behin bakarrik faktorizatuz) n33+qn2−n3\frac{n^3}{3}+qn^2-\frac{n}{3}: horregatik dira hain erakargarriak jacobiarra izozten duten metodoak.

AdibideaNewton-en metodoaren eraginkortasuna

Kalkulatu sistemetarako Newton-en eraginkortasun-indizeak nn dimentsioan.

  1. Iterazio bakoitzeko FF-ren ebaluazio bat dago (nn eskalarrak) eta jacobiarraren bat (n2n^2): guztira d=n2+nd=n^2+n ebaluazio funtzional.

  2. Iterazio bakoitzeko sistema lineal bakarra ebazten da; beraz, op=n33+n2−n3op=\frac{n^3}{3}+n^2-\frac{n}{3} biderketa/zatiketa.

  3. p=2p=2 ordenarekin, indizeak honela geratzen dira:

    IN=21/(n2+n),ICN=21/(n33+2n2+2n3)I_N=2^{1/(n^2+n)},\qquad IC_N=2^{1/\left(\frac{n^3}{3}+2n^2+\frac{2n}{3}\right)}

Bi indizeak 1erantz doaz nn handitzean: dimentsio altuetan, eraginkortasun guztiak konprimitzen dira eta sistema linealen kostuak agintzen du.

Optimalitate multidimentsionala

Kung-Traub aieru eskalarra (p≤2d−1p\le 2^{d-1}) ez da baliozkoa aldagai anitzetan. Aieru multidimentsionalak ordena honela mugatzen du:

p≤2k1+k2−1,k1≤k2p\le 2^{k_1+k_2-1},\qquad k_1\le k_2
k1k_1 = jacobiarraren ebaluazioak eta k2k_2 = FF-ren ebaluazioak iterazio bakoitzeko (d=k1+k2d=k_1+k_2).