File Exchange

image thumbnail

Newton Method in N dimensions

version 1.1 (1.87 KB) by

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

6 Downloads

Updated

View License

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)

Comments and Ratings (9)

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

Xu (view profile)

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.

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

ravi (view profile)

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

Ivan (view profile)

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.

Updates

1.1

In rare instances, matlab tried to solve for inverse of the jacobian symbolically. I added if statement, to guarantee jacobian is numeric for each iteration.
Additionally, I changed the stop condition, to reflect linear convergence.

MATLAB Release
MATLAB 7.5 (R2007b)

Download apps, toolboxes, and other File Exchange content using Add-On Explorer in MATLAB.

» Watch video