Newton Method in N dimensions

Simple implementation of Newton's method, in n dimensions, taking input of >=n equations.

Description

For an input of n equations, it converges to the solution.
For an input of >n equations, there is no exact solution. In this case, the function minimizes sum( (individual equation errors).^2)

• Required Products: Symbolic Math Toolbox
• MATLAB release: MATLAB 7.5 (R2007b)

[Kyle Drerup]

@ Andrew Knyazev,

If there are >n equations, and only n variables, this method can solve for the "least-squares solution".

[Kyle Drerup]

@Xu,

Convergence isn't guaranteed. If your initial estimate isn't in the "Region of Convergence", then it will not converge.

It depends on your initial estimate.

[Xu]

Work for relatively large n? I tried n=9, but Matlab is down.

Here are my codes:

delta=[-1 1 -1 1 -1];
F=[delta(1)*(cos(x5)+cos(2*x5+x1)+cos(3*x5+x2)+cos(4*x5+x3)+cos(5*x5+x4)) - delta(2)*(cos(x6)+cos(2*x6+x1)+cos(3*x6+x2)+cos(4*x6+x3)+cos(5*x6+x4));
delta(2)*(cos(x6)+cos(2*x6+x1)+cos(3*x6+x2)+cos(4*x6+x3)+cos(5*x6+x4)) - delta(3)*(cos(x7)+cos(2*x7+x1)+cos(3*x7+x2)+cos(4*x7+x3)+cos(5*x7+x4));
delta(3)*(cos(x7)+cos(2*x7+x1)+cos(3*x7+x2)+cos(4*x7+x3)+cos(5*x7+x4)) - delta(4)*(cos(x8)+cos(2*x8+x1)+cos(3*x8+x2)+cos(4*x8+x3)+cos(5*x8+x4));
delta(4)*(cos(x8)+cos(2*x8+x1)+cos(3*x8+x2)+cos(4*x8+x3)+cos(5*x8+x4)) - delta(5)*(cos(x9)+cos(2*x9+x1)+cos(3*x9+x2)+cos(4*x9+x3)+cos(5*x9+x4));
-sin(x5)-2*sin(2*x5+x1)-3*sin(3*x5+x2)-4*sin(4*x5+x3)-5*sin(5*x5+x4);
-sin(x6)-2*sin(2*x6+x1)-3*sin(3*x6+x2)-4*sin(4*x6+x3)-5*sin(5*x6+x4);
-sin(x7)-2*sin(2*x7+x1)-3*sin(3*x7+x2)-4*sin(4*x7+x3)-5*sin(5*x7+x4);
-sin(x8)-2*sin(2*x8+x1)-3*sin(3*x8+x2)-4*sin(4*x8+x3)-5*sin(5*x8+x4);
-sin(x9)-2*sin(2*x9+x1)-3*sin(3*x9+x2)-4*sin(4*x9+x3)-5*sin(5*x9+x4);
];
tolerance = .01;
initial_est = ones(1,9);
solution = newton_n_dim(tolerance,initial_est,[x1,x2,x3,x4,x5,x6,x7,x8,x9],F);

All functions are sin/cos.... Cannot get a solution.

[Andrew Knyazev]

Simple, general and nice! The best I have on the block so far.

Missing: limit number of steps, check for stagnation. default for the tolerance.

Cannot you just always use F_prime_X\F_X ?

[Kyle Drerup]

There is an error with your input.
Read the example carefully.

[ravi]

Error in ==> newton_n_dim at 37
H = jacobian(sym_equations,sym_variables);

i got this error(above) when i execute the code

[Kyle Drerup]

@ abdallah:

(d(b^2 -10)/db evaluated @ b = 0 ) is 0.

The example given in the m-file has two solutions. a = 15, b = sqrt(10) and a = 15, b = -sqrt(10).

For the method to converge, your starting point must be sufficiently near a solution, and should have a derivative with respect to all variables somewhere along the path of convergence.

Your starting point of [0,0] gives 15,0 on the first iteration. This stays on this point for all successive iterations, because d(F1)/da = 0 and d(F2)/db = 0 at [a,b] = [15,0].

[abdallah]

Hello,
first of all thanks for this little program. what if the initial guess was [0, 0] instead of [0, 10] in your example? your program will not converge, any idea?

[Ivan]

Hi bro

I found a 'bug', which is actually not a bug in this .m file. It should be a bug in symbolic toolbox. Whenever my equations contain any log terms(or power terms), error occurs. It seems the sym toolbox translate 'log', which is a built-in function of matlab, into 'ln' which is unrecognizable to matlab. Do you have any idea how to fix it? I am using matlab 2008b with sym toolbox 5.1. Many thanks.