Numerical methods. Note 11

[ Home ]

Nonlinear Equations and Function Minimization.

Numerical Methods. Note « 11 »

Systems of nonlinear equations. Modified Newton"s method. Consider a system of n nonlinear equations f_i(x₁,...,x_n)=0, i=1,...,n. Suppose that the point x is close to the root. Let us try to find the step Δx which brings us to the solution f_i(x+Δx)=0. The first order Taylor expansion gives a system of linear equations

f_i(x)+∑_j ^∂f_i/_{∂x_j}Δx_j = 0, or, A⋅Δx = -F , where A_ij ≡ ^∂f_i/_{∂x_j}, f ≡ F_i

The solution Δx to this equation gives the approximate direction and the step-size towards the root. However in the modified Newton's method instead of the full step a more conservative approach is usually taken, for example:

λ = 1;  do until λ<0.01 {
	z = x + λΔx;
	if |f(z)| < (1-^λ/₂) |f(x)| exit;
	else λ = λ/2;}
	x = z;

Minimization of functions. Downhill simplex method. The method is used to find a minimum of a function of n variables f(p) (p is an n-dimensional vector) by transforming the simplex according to the function values at the vertices, moving it downhill until it reaches the minimum.

Definitions:

Simplex: a figure represented by n+1 points p_k, k=1,..,n+1 (each point p_k is an n-dimensional vector).
highest point, p_hi, f(p_hi) = max_(k) f(p_k);
lowest point, p_lo, f(p_lo) = min_(k) f(p_k);
centroid, p_ce, p_ce = ¹/_n ∑_{(k ≠ hi)} p_k

Operations on the simplex:

Reflection: p_hi → p_re = p_ce - (p_hi - p_ce),
Expansion: p_hi → p_ex = p_ce + 2(p_ce - p_hi),
Contraction: p_hi → p_co = p_ce + ½(p_hi - p_ce),
Reduction: p_k≠lo = ¹/₂(p_k+p_lo).

Algorithm:

do until converged
	try Reflection
	if f(p_re)<f(p_lo) Expansion; cycle
	if f(p_re)<f(p_hi) accept Reflection; cycle
	try Contraction; if f(p_co)<f(p_hi) accept Contraction; cycle
	Reduction
	cycle

Problems

Implement the Modified Newton's method and the downhill simplex method
Solve the system of two equations (1-x)=0, 10(x-y²)=0.
Find the minimum of a paraboloid f(x,y)=10(x-1)²+20(y-2)².
Evaluate the difficulty and usfulness level of each set of problems by giving them (two) marks from 1 to 5 (with 3 being at the normal level). The marks should be visible on your web-page.