Numerical methods. Note 10

[~Home~]

Solution of Nonlinear Equations and Minimization.

Numerical Methods. Note~ « 10 »

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\dot{}Δ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: \tt

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

\xtt

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 thus moving it downhill until it reaches the minimum.

Definitions:

Simplex: a figure represented by n+1 points p_i, i=1,..,n+1 (each point p_i is an n-dimensional vector).
highest point, p_h, f(p_h) = max_(i) f(p_i); lowest point, p_l, f(p_l) = min_(i) f(p_i); centroid, p₀, p₀ = ¹/_n ∑_{(i ≠ h)} p_i

Operations on the simplex:

Reflection: p_h → p_r = p₀ - (p_h - p₀),
Expansion: p_l → p_e = p₀ + 2(p_r - p₀),
Contraction: p_h → p_c = p₀ + ½(p_h - p₀),
Reduction: p_i = ¹/₂(p_i+p_l).

Algorithm:

\tt

do until converged
	try Reflection
	If f(p_r)\lt{}f(p_l) accept Reflection; Expansion; cycle
	If f(p_r)\lt{}f(p_h) accept Reflection; cycle
	try Contraction; if f(p_c)\lt{}f(p_h) accept Contraction; cycle
	Reduction
cycle

\xtt

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)².