Newton’s method for nonlinear systems generalizes the single-variable iteration g ( x ) = x − ϕ ( x ) f ( x ) g(x) = x - \phi(x)f(x) g ( x ) = x − ϕ ( x ) f ( x ) ϕ ( x ) = 1 / f ′ ( x ) \phi(x) = 1/f'(x) ϕ ( x ) = 1/ f ′ ( x ) n n n ϕ ( x ) \phi(x) ϕ ( x ) A ( x ⃗ ) A(\vec{x}) A ( x )
G ( x ⃗ ) = x ⃗ − A ( x ⃗ ) − 1 F ( x ⃗ ) G(\vec{x}) = \vec{x} - A(\vec{x})^{-1}F(\vec{x}) G ( x ) = x − A ( x ) − 1 F ( x ) Quadratic convergence of this fixed-point iteration to p ⃗ \vec{p} p ∂ g i ( p ⃗ ) ∂ x k = 0 \dfrac{\partial g_i(\vec{p})}{\partial x_k} = 0 ∂ x k ∂ g i ( p ) = 0 i , k i, k i , k A ( x ⃗ ) A(\vec{x}) A ( x ) Jacobian matrix J ( x ⃗ ) J(\vec{x}) J ( x ) F F F
Iteration
G ( x ⃗ ) = x ⃗ − J ( x ⃗ ) − 1 F ( x ⃗ ) G(\vec{x}) = \vec{x} - J(\vec{x})^{-1}F(\vec{x}) G ( x ) = x − J ( x ) − 1 F ( x ) x ⃗ ( k ) = x ⃗ ( k − 1 ) − J ( x ⃗ ( k − 1 ) ) − 1 F ( x ⃗ ( k − 1 ) ) , k ≥ 1 \vec{x}^{(k)} = \vec{x}^{(k-1)} - J(\vec{x}^{(k-1)})^{-1}F(\vec{x}^{(k-1)}), \quad k \geq 1 x ( k ) = x ( k − 1 ) − J ( x ( k − 1 ) ) − 1 F ( x ( k − 1 ) ) , k ≥ 1 Inverting J ( x ⃗ ( k − 1 ) ) J(\vec{x}^{(k-1)}) J ( x ( k − 1 ) )
J ( x ⃗ ( k − 1 ) ) y ⃗ ( k − 1 ) = − F ( x ⃗ ( k − 1 ) ) J(\vec{x}^{(k-1)})\vec{y}^{(k-1)} = -F(\vec{x}^{(k-1)}) J ( x ( k − 1 ) ) y ( k − 1 ) = − F ( x ( k − 1 ) ) for y ⃗ ( k − 1 ) \vec{y}^{(k-1)} y ( k − 1 ) Gaussian elimination , then set x ⃗ ( k ) = x ⃗ ( k − 1 ) + y ⃗ ( k − 1 ) \vec{x}^{(k)} = \vec{x}^{(k-1)} + \vec{y}^{(k-1)} x ( k ) = x ( k − 1 ) + y ( k − 1 )
Convergence is quadratic, provided a sufficiently accurate starting value x ⃗ ( 0 ) \vec{x}^{(0)} x ( 0 ) J ( p ⃗ ) − 1 J(\vec{p})^{-1} J ( p ) − 1
Example
Apply Newton’s method to the nonlinear system with its Jacobian , starting from x ⃗ ( 0 ) = ( 0.1 , 0.1 , − 0.1 ) T \vec{x}^{(0)} = (0.1, 0.1, -0.1)^T x ( 0 ) = ( 0.1 , 0.1 , − 0.1 ) T
F ( x ⃗ ( 0 ) ) ≈ ( − 1.199950 , − 2.269833 , 8.462025 ) T F(\vec{x}^{(0)}) \approx (-1.199950, -2.269833, 8.462025)^T F ( x ( 0 ) ) ≈ ( − 1.199950 , − 2.269833 , 8.462025 ) T J ( x ⃗ ( 0 ) ) ≈ ( 3 0.001000 − 0.001000 0.200000 − 32.400000 0.995004 − 0.099005 − 0.099005 20.000000 ) J(\vec{x}^{(0)}) \approx
\begin{pmatrix}
3 & 0.001000 & -0.001000 \\
0.200000 & -32.400000 & 0.995004 \\
-0.099005 & -0.099005 & 20.000000
\end{pmatrix} J ( x ( 0 ) ) ≈ 3 0.200000 − 0.099005 0.001000 − 32.400000 − 0.099005 − 0.001000 0.995004 20.000000 Solving J ( x ⃗ ( 0 ) ) y ⃗ ( 0 ) = − F ( x ⃗ ( 0 ) ) J(\vec{x}^{(0)})\vec{y}^{(0)} = -F(\vec{x}^{(0)}) J ( x ( 0 ) ) y ( 0 ) = − F ( x ( 0 ) )
y ⃗ ( 0 ) ≈ ( 0.399870 , − 0.080533 , − 0.421520 ) T \vec{y}^{(0)} \approx (0.399870, -0.080533, -0.421520)^T y ( 0 ) ≈ ( 0.399870 , − 0.080533 , − 0.421520 ) T x ⃗ ( 1 ) = x ⃗ ( 0 ) + y ⃗ ( 0 ) ≈ ( 0.499870 , 0.019467 , − 0.521520 ) T \vec{x}^{(1)} = \vec{x}^{(0)} + \vec{y}^{(0)} \approx (0.499870, 0.019467, -0.521520)^T x ( 1 ) = x ( 0 ) + y ( 0 ) ≈ ( 0.499870 , 0.019467 , − 0.521520 ) T Repeating converges to x ⃗ ( 5 ) ≈ ( 0.500000 , 0.000000 , − 0.523599 ) T \vec{x}^{(5)} \approx (0.500000, 0.000000, -0.523599)^T x ( 5 ) ≈ ( 0.500000 , 0.000000 , − 0.523599 ) T p ⃗ = ( 0.5 , 0 , − π / 6 ) \vec{p} = (0.5, 0, -\pi/6) p = ( 0.5 , 0 , − π /6 )