The SOR-Newton method (in R²)

Directly to the input form

• The SOR-Newton method is meant for the solution of large nonlinear systems of equations F(x)=0.
• It is a combination of the ideas of Newton's method and the SOR method for linear systems, in the form first relax then linearize.
• Given an approximation x_k for the zero x^* in a cycle of n substeps new coordinates are computed as
  x_k+1,i = x_k,i -ω*F_i(x_k+1,1,..,x_k+1,i-1,x_k,i,..,x_k,n)/((d/d x_i) F_i(x_k+1,1,..,x_k+1,i-1,x_k,i,..,x_k,n)), i=1,...,n
  that means we take a onedimensional Newton's step with stepsize variation for the i-th equation, considered as a function of the i-th variable only.
• The relaxation parameter ω has the same role as in the linear case.
• If F(x)=Ax-b, then this is identical to the SOR method for linear equations.
• Proofs of local convergence are possible under the same assumptions on the Jacobian of F at x^* as used in the linear case. Global convergence can be shown if F is the gradient of an uniformly convex function on Rⁿ (this means that the Jabobian is symmetric and its eigenvalues have a globally valid upper and lower bound > 0). In addition ω needs to be ''sufficiently small'' or otherwise one needs to use a test for sufficient decrease of the principal function of F. Even if this principal function is available its computation (for each k,i) is as costly as a complete cycle in this iteration.
• The advantage of this method is the fact that it is completely ''matrix free'', the required diagonal of the Jacobian might well be approximated by finite differences.
• The convergence conditions however are very restrictive.

Input

• For the nonlinear system F(x) = (F₁(x₁,x₂) , F₂(x₁,x₂)) = 0 there is a predefined case and you have the possibility to specify the two components of F as formulas following FORTRAN rules.
• The initial point (x_0,1,x_0,2).
• The relaxation parameter ω. Important: 0 < ω < 2 ! This does not necessarily yield convergence!
• The required precision in the two components of F (as absolute bounds).
• The maximum number of iterations allowed. Important: 50 <= iter <= 1000.
• fac, a safety parameter for detecting divergence: we finish if
  ||F(x_k)|| >= fac*||F(x₀)||
• Since we show a 3D plot showing the two components of x and ||F|| you must specify your view point via two rotation angles for the x- and the z-axis.

Output

• The 3D-Plot showing the sequence x₁, x₂, ||F||
• A table of numbers with this sequence.

Questions?!

• When can you observe monotonic convergence in the euclidean sense?
• Which influence has the relaxation parameter ?
• In which cases you observe convergence, in which divergence?

To the input form