|
|
|
|
|
|
From: Glyn Holton
Affiliation: Contingency Analysis
Address: glyn@contingencyanalysis.com
Date: 10 Sep 1998
Time: 17:53:18
You can perform the Newton-Raphson method in any finite number of dimensions. Note, however, that often there will be infinitely many roots. Newton-Raphson will only find one at a time. Also, Newton-Raphson finds a root of a single equation. You are trying to solve two simultaneously. First, I'll explain how Newton-Raphson works in multiple dimensions. I'll give a worked example and then propose how you might apply the technique to solve your system of two equations.
In n dimensions, the gradient of the function plays the same role as the derivative does in 1 dimension. Recall that the gradient points in the direction in which a function most rapidly increases. Accordingly, if you travel in the opposite direction, you will (hopefully) be moving toward a root of the function. I don’t know of any references, so I provide a solution in 2 dimensions below:
1. let z = f(x,y) be your function.
2. Let (x0,y0) be an initial guess.
3. Evaluate z0 - f(x0,y0).
4. Let Df(x0,y0) be the gradient of f at (x0,y0). (i.e. it is the 2-dimensional vector whose components are the partial derivative of f with respect to x and the partial derivative of f with respect to y, both partial derivatives evaluated at the point (x0,y0).)
5. Let u0 be a unit vector in the direction of the gradient at (x0,y0). (simply take the gradient, calculate its Euclidean length (Pythagorean theorem) and divide each component of the gradient by that length. The result will be the unit vector u0)
6. To find your next point (x1,y1), you want to (similar to the one-dimension case) fit a tangent line to f at the point (x0, y0, z0) pointing in the direction of (i.e. coplanar with) u0. Your next point (x1,y1) will be the point on the x,y-plane where that tangent line intercepts.
7. That point will occur at (x1,y1) = (x0,y0) + Cu0 for some constant value C.
8. You can solve for C because z0 must equal -C times [the dot product of u0 and Df(x0,y0)]. (the dot product of two 2-dimensional vectors is the product of each of their first components plus the product of each of their second components, so it is a number)
9. Continue to repeat the process using (x1,y1) as your next guess to find (x2,y2) and so on.
As an example, consider the function z = f(x,y) = (x+1)y^2 and let’s use the initial guess (x0,y0) = (1,1). I walk through the exact same steps below:
1. We already know the function. It is z = f(x,y) = (x+1)y^2.
2. We already have the initial guess (x0,y0). It is (1,1).
3. Evaluate z0 - f(x0,y0) = f(1,1) =2.
4. The gradient of f at any point (x,y) is (y^2, 2(x+1)y). Evaluated at (x0,y0) = (1,1), we obtain Df(x0,y0) = (1,4).
5. The length of the gradient is (1^2 + 4^2)^.5 = 4.1231. Accordingly, u0 = (1/4.1231, 4/4.1231) = (.2425, .9701). This is a unit vector with the same direction as the gradient.
6. To find your next point (x1,y1), you want to (similar to the one-dimension case) fit a tangent line to f at the point (x0, y0, z0) pointing in the direction of (i.e. coplanar with) u0. Your next point (x1,y1) will be the point on the x,y-plane where that tangent line intercepts.
7. That point will occur at (x1,y1) = (x0,y0) + Cu0 for some constant value C.
8. You can solve for C because z0 must equal -C times [the dot product of u0 and Df(x0,y0)]. The dot product of the gradient and u0 is simply (1)( .2425) + (4)( .9701) = 4.1229. Hence C = -z0/4.1229 = -2/4.1229 = -.4851. We conclude that the next point (x1,x2) = (x0,y0) + Cu0 = (1,1) + (-.4851)(.2425, .9701) = (.8823, .5294)
9. Continue to repeat the process using (x1,y1) as your next guess to find (x2,y2) and so on.
Of course, your problem is to solve two equations simultaneously. Let's say that the two equations are 0 = f(x,y) and 0 = g(x,y). If you apply Newton-Raphson to the function h(x,y) = [f(x,y)^2 + g(x,y)^2)] then any solution to the equation 0 = h(x,y) will simultaneously solve your two equations.
Good Luck.
|
|
