Numerical methods. Note 11


	[ Home ]	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 { y = x + λΔx if |f(y)|<(1-^λ/₂)|f(x)| x=y; exit else λ = λ/2 }

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_r = p₀ - α(p_h - p₀), α=1
Expansion: p_e = p₀ + β(p_r - p₀), β=2
Contraction: p_c = p₀ + γ(p_h - p₀), γ=1/2
Reduction: p_i = ¹/₂(p_i+p_l).

Algorithm:

do until converged try Reflection If f(p_r)<f(p_l) accept Reflection; do Expansion; done If f(p_r)<f(p_h) accept Reflection; done try Contraction if f(p_c)<f(p_h) accept Contraction; done do Reduction done

Problems

Finish up Lanczos+QR
Implement the Modified Newton's method and downhill simplex method