| For numerical methods, I can't recommend this text highly enough.
They explain clearly and concisely the theory and practice behind
all algorithms, as well as pathological behavior and special
conditions to be met.
For this case they point out that, unlike the linear case, you are
not gauranteed a solution, even for "well behaved" f().
The discussion goes something like this--
For the linear case, finding the n-vector x such that
Ax = b for a given matrix A and n-vector b is equivalent to solving
f(x) = Ax-b =0.
It's easy to visualize for the real, 2dimensional case, where A is 2X2,
and f(x) = (f1(x),f2(x))^T is a 2-tuple. Each of
f1() and f2() takes R2 into number, so (x1,x2,f1)^T and (x1,x2,f2)^T
each define a plane in R3, where x = (x1,x2)^T varies over R2.
These two planes intersect in a line (unless they are parallel),
and the solution to f(x) = 0 is precisely that x where the line
goes through the (x1,x2) plane. If A is singular, then either the
planes are parallel, or the line is parallel to the (x1,x2) plane,
or the line lies in the (x1,x2) plane. Thus, it's easy to
characterize the cases of when there is 1) a unique solution, 2)
no solution, 3) a whole family of solutions, based on the matrix A.
For the general case, (x1,x2,f1) and (x1,x2,f2) are general
surfaces in R3. There is no gaurantee that they will intersect
at all, let alone on the (x1,x2) plane, and there is no universal
way to characterize these cases without some a prior knowledge of
f().
The algorithms they introduce are quazi-Newton methods (I think),
such as Gordon-Fletcher-Powell, etc. See the text for details; I
remember enough about it.
Avery
|
| Homotopy continuation methods are slow but useable for such
equations. Note that unlike an n'th degree polynomial in one variable
which always has n roots, systems of equations do not necessarily
have any solutions.
The idea is to take simple polynomials of some form which you *do*
know the solutoins to, and continuously perturb the form into the
polynomials or functions you have, always tracking (or continuing)
the solution path. Thus, when you reach the target function, the
solution set will in principle have evolved to the solution set too.
There is a book by Alexander Morgan on the subject. You can't
really solve for zillions of unknowns, but can solve for modest
numbers of variables.
If you have only one function, then the solution set will be a
complex manifold of solutions, not a unique solution or discrete
set of solutoin points as in the one variable case.
- Jim
|
| > That is, we have a vector of variables, (x0, x1, . . .) and a function
> f, so that f(x0, x1, . . .) = (y0, y1, . . .) and we want to solve for
> when f(x0, x1, . . .) = (0, 0, . . .).
>
> Are there methods that are fairly well-behaved?
I assume that your f is non-linear. As .1 points out, the linear special case
is much easier.
Is f really of the same dimension as x? All the examples I have seen use a
scalar f, and even some I could imagine give the dimension of f as much
smaller than the dimension of x.
The special case of scalar f and scalar x is treated in most books on numerical
analysis, and often part of standard math packages. Solution behavior varies a
lot with the form of f, but is often well behaved.
The special case of scalar f and vector x is also commonly treated. In general
it shows all the nastiness possible: runaway regions, very slow convergence,
complicated oscillations and false minima. Various forms of steepest descent
are commonly used. I have not heard of the methods in .2, but they sound
interesting.
Note that you can convert your general case into the second special case above
by using the length of your vector f as my scalar f. f=(0,0,0...) iff ||f||=0.
This may or may not produce an easier problem.
The usual advice at this point is to back off and think carefully about your
specific problem. Is there anything in your functional form of f which can
help you? For example, can any dimensions be separated out, exactly or approxi-
mately? Have you derived this problem from another problem which may in fact be
easier to solve? If the f is analytic, can you use the analytic form to solve
part or all of the problem? If the f is fitted to data, could you start with
a family of f's which allow an easy solution and fit those to the data? Can
you convert this non-linear problem approximately to a linear problem?
|
| Re .3:
There isn't a specific problem here. I am thinking of the general case
where one is given a system of several equations and wishes to solve
them. The value of f in this case is the vector of the differences of
the sides of each equation.
One example where I might use such a thing is a problem that appeared
several months ago: A four-foot bar is attached at its ends to
two-foot and three-foot ropes which are attached five feet apart to a
horizontal ceiling. Find any of the angles between any two items.
This can be written as scalar or two-dimensional vector equations
stating that the linear forces sum to zero, that the torques sum to
zero. Written as several equations with several unknowns, the
expressions are not too imposing. But when trying to solve the
equations to write an equation with a single unknown, the algebra
becomes quite messy. It would be nice to simply let a numerical solver
run with it.
This system in particular would probably be well behaved numerically,
since it represents a physical system that itself tends toward
stability.
-- edp
|
| > ... Written as several equations with several unknowns, the
> expressions are not too imposing. But when trying to solve the
> equations to write an equation with a single unknown, the algebra
> becomes quite messy.
Seems to me this is the kind of thing MAPLE does quite well, and exactly.
Another approach is to treat it as a minimization problem, where the
variable to be minimized is the height of the center of mass of the bar.
I think a simple binary chopping solution varying one of the ceiling angles
from 90 toward 0 will work well, since everything is continuous and
well-behaved.
Lynn
|