GuideNonlinear systemsadvanced

High order in systems: Traub, Golden Ratio, NA, Jarratt and RN

Composition with Newton and frozen Jacobian: how to gain one order by composition without evaluating new Jacobians, and the Traub, Golden Ratio, NA, vector Jarratt and RN (order 5-6) families.

Composition with frozen Jacobian

Composing a method of order pp, z(k)=Φ(x(k),y(k))z^{(k)}=\Phi(x^{(k)},y^{(k)}), with a full Newton step gives order 2p2p, but requires evaluating (and factorizing) a new Jacobian at z(k)z^{(k)}. The cheap alternative is to reuse the already factorized Jacobian:

z(k)=Φ(x(k),y(k)),x(k+1)=z(k)−[F′(x(k))]−1F(z(k))z^{(k)}=\Phi(x^{(k)},y^{(k)}),\qquad x^{(k+1)}=z^{(k)}-\bigl[F'(x^{(k)})\bigr]^{-1}F(z^{(k)})

The simplest example is the vector Traub method: Newton (order 2) followed by one frozen-Jacobian step, of order 2+1=32+1=3:

z(k)=x(k)−[F′(x(k))]−1F(x(k))x(k+1)=z(k)−[F′(x(k))]−1F(z(k))\begin{aligned} z^{(k)}&=x^{(k)}-\bigl[F'(x^{(k)})\bigr]^{-1}F(x^{(k)})\\ x^{(k+1)}&=z^{(k)}-\bigl[F'(x^{(k)})\bigr]^{-1}F(z^{(k)}) \end{aligned}
Traub's method for systems, order 3.

Golden Ratio and the NA method

Generalizing the idea with weighted steps ηj(x(k))=x(k)−aj[F′(x(k))]−1F(x(k))\eta_j(x^{(k)})=x^{(k)}-a_j[F'(x^{(k)})]^{-1}F(x^{(k)}) yields the family x(k+1)=x(k)−[F′(x(k))]−1(∑jbjF(ηj(x(k))))x^{(k+1)}=x^{(k)}-[F'(x^{(k)})]^{-1}\bigl(\sum_j b_jF(\eta_j(x^{(k)}))\bigr). The two-step member is the Golden Ratio method, of order 3, so named because its parameters involve 5\sqrt5: a=−1±52a=\frac{-1\pm\sqrt5}{2}, b=3±52b=\frac{3\pm\sqrt5}{2}.

y(k)=x(k)−a[F′(x(k))]−1F(x(k))x(k+1)=x(k)−b[F′(x(k))]−1F(y(k))\begin{aligned} y^{(k)}&=x^{(k)}-a\bigl[F'(x^{(k)})\bigr]^{-1}F(x^{(k)})\\ x^{(k+1)}&=x^{(k)}-b\bigl[F'(x^{(k)})\bigr]^{-1}F(y^{(k)}) \end{aligned}
Golden Ratio method, order 3.

Composing Golden Ratio with a frozen-Jacobian step yields the NA method, of order 4 with a single Jacobian evaluation per iteration. Its efficiency indices beat Newton's and Golden Ratio's for every n>1n>1: INA=41/(n2+3n)>IGR=31/(n2+2n)>IN=21/(n2+n)I_{NA}=4^{1/(n^2+3n)}>I_{GR}=3^{1/(n^2+2n)}>I_N=2^{1/(n^2+n)}.

y(k)=x(k)−a[F′(x(k))]−1F(x(k))z(k)=x(k)−b[F′(x(k))]−1F(y(k))x(k+1)=z(k)−[F′(x(k))]−1F(z(k))\begin{aligned} y^{(k)}&=x^{(k)}-a\bigl[F'(x^{(k)})\bigr]^{-1}F(x^{(k)})\\ z^{(k)}&=x^{(k)}-b\bigl[F'(x^{(k)})\bigr]^{-1}F(y^{(k)})\\ x^{(k+1)}&=z^{(k)}-\bigl[F'(x^{(k)})\bigr]^{-1}F(z^{(k)}) \end{aligned}
NA method, order 4 with a single Jacobian.

Vector Jarratt and the RN method

Jarratt's method also extends to systems, keeping its order 4:

y(k)=x(k)−23[F′(x(k))]−1F(x(k))x(k+1)=x(k)−12[3F′(y(k))−F′(x(k))]−1(3F′(y(k))+F′(x(k)))[F′(x(k))]−1F(x(k))\begin{aligned} y^{(k)}&=x^{(k)}-\tfrac{2}{3}\bigl[F'(x^{(k)})\bigr]^{-1}F(x^{(k)})\\ x^{(k+1)}&=x^{(k)}-\tfrac{1}{2}\bigl[3F'(y^{(k)})-F'(x^{(k)})\bigr]^{-1}\bigl(3F'(y^{(k)})+F'(x^{(k)})\bigr)\bigl[F'(x^{(k)})\bigr]^{-1}F(x^{(k)}) \end{aligned}
Jarratt's method for systems, order 4.

In exchange, it evaluates two Jacobians and solves linear systems with two different coefficient matrices: IJ=41/(2n2+n)I_J=4^{1/(2n^2+n)}. Composing it with a Newton variant yields the RN method, with a third step x(k+1)=z(k)−[aF′(x(k))+bF′(y(k))]−1F(z(k))x^{(k+1)}=z^{(k)}-\bigl[aF'(x^{(k)})+bF'(y^{(k)})\bigr]^{-1}F(z^{(k)}).