Re: Solving a set of quadratic equations

In article <1138238832.750596.51810@xxxxxxxxxxxxxxxxxxxxxxxxxxxx>,
<mindspawn@xxxxxxxxx> wrote:
>Greetings,
>
>Can some one suggest a method for solving a set of equations of the
>form
>
>f_1(x_1) - f_2(x_2) = 0
>f_1(x_2) - f_2(x_3) = 0

Perhaps you mean f_2(x_2) - f_3(x_3) = 0? Otherwise I
don't see what the pattern is.

>.......................
>.......................
>.......................
>f_{n-1}(x_{n-1}) - f_n(x_n) = 0
>x_1 + x_2 + ... + x_n = N
>
>where f_i(x_i) are second degree polynomials.


Assuming line #j is f_j(x_j) - f_{j+1}(x_{j+1}),
this says all f_i(x_i) are equal. Let's say the common
value is y. If the f_i have degree 2, and y is in an appropriate
interval (greater than the greatest of the lower bounds,
and less than the least of the upper bounds, of those f_i that
have them), there are two possible values for x_i, say a_i and
a_i + h_i with h_i > 0. We can write x_i = a_i + t_i h_i where
t_i is 0 or 1. Then the last equation says

sum_i t_i h_i = N - sum_i a_i

Finding t_i's that make this work is a knapsack problem, but
if you round the h_i and N - sum_i a_i to the nearest multiple
of some fixed epsilon > 0 you get an approximation that can
easily be solved using dynamic programming. I'd start with
a fairly large epsilon and try searching for a value y for
which such an approximate solution to the knapsack problem
exists, then fixing the t_i's from that approximate solution
and using Newton's method to find y that gives you an accurate
solution with those t_i's.

Robert Israel israel@xxxxxxxxxxx
Department of Mathematics http://www.math.ubc.ca/~israel
University of British Columbia Vancouver, BC, Canada
.

Quantcast