Re: Exact or Least-Squares Solution 5 Equations
- From: monir <monirg@xxxxxxxxxxxx>
- Date: Mon, 29 Oct 2007 12:33:35 -0700
On Oct 26, 10:40 pm, monir <mon...@xxxxxxxxxxxx> wrote:
On Oct 26, 8:48 am, spellu...@xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx
(Peter Spellucci) wrote:
In article <1193323844.403041.220...@xxxxxxxxxxxxxxxxxxxxxxxxxxxx>, monir <mon...@xxxxxxxxxxxx> writes:
>On Oct 25, 5:40 am, spellu...@xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx >(Peter Spellucci) wrote:
>> In article <1193280435.133367.29...@xxxxxxxxxxxxxxxxxxxxxxxxxxxx>, monir <mon...@xxxxxxxxxxxx> writes:
>> >Hello;
>> >I've tried a number of techniques to solve 5 equations in 5 unknowns
>> >with no avail!! I hope someone might have either come across a
>> >similar problem or has the appropriate analytical tools and would be
>> >kind enough to share his/her expertise.
>> >Here's a brief discription of the problem.
>> >5 UNKNOWNS: B, C, D, F, G
>> >SQRT { (x2-F)^2 + (y2-G)^2 } = { a + B.t2 + C.t22 + D.t23 } Exp(m.t2)
>> >SQRT { (x3-F)^2 + (y3-G)^2 } = { a + B.t3 + C.t32 + D.t33 } Exp(m.t3)
>> >SQRT { (x4-F)^2 + (y4-G)^2 } = { a + B.t4 + C.t42 + D.t43 } Exp(m.t4)
>> >SQRT { (x5-F)^2 + (y5-G)^2 } = { a + B.t5 + C.t52 + D.t53 } Exp(m.t5)
>> >SQRT { (x6-F)^2 + (y6-G)^2 } = { a + B.t6 + C.t62 + D.t63 } Exp(m.t6)
>> >All other quantities in the above equations are known.
>> >Q1: What are the exact expressions for B, C, D, F, G ??
>> >Q2: In the event that such exact expressions are defficult/impossible
>> >to derive (I certaily hope not!), then what are the least-squares
>> >regression formulas ??
>> >Your expert help would be greatly appreciated.
>> >Monir
>> this system looks a little bit strange:
>> on the right hand side we have a linear part in the three unknowns.
>> if you can pick here a submatrix of the 5 by 3 matrix formed by
>> [ t2 t22 t23 ]
>> ...............
>> [ t6 t62 t63 ]
>> which has rank 3 you could solve the corresponding 3 equations for B,C,D
>> in terms of the sqrt... involving the unknowns F and G, insert in the other
>> two equations, with only F,G remaining as unknowns and then solving these
>> using e.g. Newtons method.
>> if this is impossible, then the system might have no solution at all and you need
>> to use nonlinear least squares minimizer to get a "quasisolution"
>> for this I would work in two stages:
>> first squaring both sides, then building the difference LHS-RHS, squaring again
>> and summing up you get a sum which is quartic in the 5 unknowns, miminimize
>> this by an appropriate code (e.g. ELSUNC) , then going back to the
>> orignal equation, building RHS-LHS squaring and summing up, doing the
>> same with the solution from the first step as an initial guess.
>> this because the least squares solution of the original system will not be
>> identical to that of the squared system (the optimal sum of squares will not be
>> zero in most cases) .
>> a quartic in 5 unknowns can also be quite hard to minimize, but the problem
>> involving the square roots might be even harder.
>> hth
>> peter
>Peter;
>Thank you for your prompt and helpful suggestions.
>How about the following approach:
>1. start with an initial "good" guess of F and G
>2. the 5 equations then become:
> t2.B + t22.C + t23.D = h2 .........(1)
> t3.B + t32.C + t33.D = h3 .........(2)
> t4.B + t42.C + t43.D = h4 .........(3)
>-----------
> t5.B + t52.C + t53.D = h5 .........(4)
> t6.B + t62.C + t63.D = h6 .........(5)
>3a. solve the top 3 simultaneous linear equations for B, C, D
> {it would be more practical here to apply the general solution
>formula, x(i) = ..., i=1,3
> x(i) ,i=1,3 refers to B, C, D. plse see item 5 below) }
>3b. substitute the values of B, C, D into equations (4) and (5) and
>solve for G:
> (x6 - x5) = sqrt {k62 - (y6 - G)^2} - sqrt {k52 - (y5 -
>G)^2} ....................(6)
> (possibly by a goal seek scenario if I can't derive G = ...);
>and
> F = x5 - sqrt {k52 - (y5 - G)^2} .................(7)
>3c. use the new values of F and G and repeat steps 2, 3a, 3b above
>until (hopefully!) a
> reasonable convergence is achieved.
>4a. an alternative to step 3. above would be to obtain the least
>squares solution of the 3
> variables B, C, D based on the coefficients of the 5 simultaneous
>linear equations.
> {similarly, I would prefer here to use the applicable general
>regression formula
> x(i) = ...., i=1,3 (plse see item 5 below}
>4b. establish a convergence criterion for the solution, and repeat 4a
>above by modifying the
> initial values of F and G. Repeat until a target value is
>achieved.
>5. Since I'm dealing with max 5 equations, I would appreciate if
>someone can (with no
> much effort) provide:
> - the analytical solution formula x(i) = ......., i=1, N for N
>simultaneous linear
> equations; and / or
> - the regression expression x(i) =......., i=1, 3 based on the
>coeffs of N simultaneous
> linear equations
> (unfortunately, my equation solver can handle max 3 unknowns in
>only 4 linear equations.
> Will keep searching!)
>Thank you again for your help.
>Monir
what you imagine to do is in short this:
you have a system of n equations in n unknowns x
T_i(x) = 0 i=1,..,n
now , because of the special strucuture of the system, and bbeing hindered by
extremely poor software, you want to do the following:
split x into [y,z];
y=[F,G]; z=[B,C,D];
split also T into R,S (of the corresponding dimensions) and now iterate:
given [y^0,z^0]
solve
R(y^1,z^0)=0 for y^1 ;
solve
S(y^1,z^1)=0 for z^1 ;
repeat until convergence is achieved.
o.k. this is long known as kind of block-Newton-Gauss-Seidel.
whether this converges and how fast depends strongly on the properties
of the
Jacobian of _ T (!) _ (the complete one, not the two small ones)
There are sufficient convergence criteria, but these
are quite restrictive.
also, you want to do the solving (which in this specific case involves solution
of two linear systems of equatuons only) using explicit formulae for the inverse,
obviously in order to circumvent the weakness of your software.
for the 2 by two system the formula is
(in MATLAB notation: ; begins a new row ; [...] denotes a matrix or vector)
inverse([ a b ; c d]) = (1/(a*d-b*c)) [ d -b ; -c a ]
and this might be used.
for a three by three system also there exists such a formula, the formula for
the inverse via the adjoint:
inverse(A) = (1/det(A)) *adjoint(A) ;
the adjoint(A) has in position (j,i) the element det(A'(i,j))(-1)^{i+j)
where A'(i,j) is obtained from A by deleting row i and column j.
in your case this means 9 determinants of 2 by 2 matrices
and the denominator in the first formula is the determinant of the 2 by 2
matrix
but I would strongly discourage the use of these formulae because the numerical
evaluation can be subject to severe roundoff error.
since also your approach as a whole is questionable in respect to applicability
as well as efficiency, why not simply using a hand crafted damped
Newtons method say, with a intial guess
obtained by say setting F,G to zero and solving three equations for B,C,D
and then the other two for G,H?
(... I assume you work on a small dedicated processor such that the use of
well known standard software from netlib is excluded?)
hth
peter
Thanks for your reply. Greatly appreciated.
Your description of the approach and your understanding of the problem/
situation is very close to being perfect.
I need to ponder this a while and to experiment with a couple of
things first.
(Please ignore the first item in 5. of my previous reply. I've
located my analytical formula for solving a small number of
simultaneous linear equations. I'm still searching, however, for the
regression formula when (no. of eqns) > (no of unknowns).
Thanks again.
Monir- Hide quoted text -
- Show quoted text -
i) I'm afraid the following 5-step approach DID NOT work:
(5 simultaneous equations in 5 unknowns B, C, D, F, G. All other
quantities are known)
....step 1. start with an initial "good" guess of F and G
....step 2. the 5 equations then yield:
a11.B + a12.C + a13.D = h1 .........(1)
a21.B + a22.C + a23.D = h2 .........(2)
a31.B + a32.C + a33.D = h3 .........(3)
-----------
a41.B + a42.C + a43.D = h4 .........(4)
a51.B + a52.C + a53.D = h5 .........(5)
....step 3. solve the top 3 simultaneous linear equations for B, C, D
....step 4. substitute the values of B, C, D into equations (4) and (5)
and solve for G:
(x6 - x5) = sqrt {k62 - (y6 - G)^2} - sqrt {k52 - (y5 - G)^2}
and
F = x5 - sqrt {k52 - (y5 - G)^2}
....step 5. use the new values of F and G and repeat steps 2, 3, 4
above until (hopefully!) a
reasonable convergence is achieved.
ii) The above approach failed at step 4. The resulting quadratic
equation for G (or F)
has imaginary roots. The initial "good" guess for F and G (step
1) to produce
B, C, D (step 3) was apparently not good enough for this system of
equations.
Other attempts have also failed.
iii) So I'm back to squared one!
How to solve (exact or least-squares) the following 5 equations in
B, C, D, F, G:
a11.B + a12.C + a13.D - sqrt{ (F-a14)^2 +(G-a15)^2 } = 0
a21.B + a22.C + a23.D - sqrt{ (F-a24)^2 +(G-a25)^2 } = 0
a31.B + a32.C + a33.D - sqrt{ (F-a34)^2 +(G-a35)^2 } = 0
a41.B + a42.C + a43.D - sqrt{ (F-a44)^2 +(G-a45)^2 } = 0
a51.B + a52.C + a53.D - sqrt{ (F-a54)^2 +(G-a55)^2 } = 0
iv) The system should have at least one real solution.
Value of F should be a fraction of 1. and -ve.
Value of G should be a fraction of 1. and +ve.
The elements of the 5 by 3 submatrix a11 .... a53 are all +ve
The 5 coeffs a14 to a54 are all -ve
The 5 coeffs a15 to a55 are all +ve
That's all I'm sure of about the system.
v) Here's a thought! Someone recently was kind enough to provide the
expression for the root of a relatively complex one-dimensional
equation. The expression was 4-line long, an exact solution with no
error term O(), and was obtained by a "computer algebra system". It
might be a wishful thinking on my part, but could it be possible that
one plugs in the 5 equations (item iii. above) into one of those
"computer algebra systems" and gets the general expressions for B, C,
D, F, G in terms of the system coefficients a11 to a55, even with
error terms ?????????? I doubt it, but I've been wrong in the past!
(I've no access to analytical packages such as Mathematica, Scilab,
MATLAB, Octave, R, MathCad, Maple, etc.)
Your expert help would be greatly appreciated.
Monir
.
- Follow-Ups:
- Re: Exact or Least-Squares Solution 5 Equations
- From: Peter Spellucci
- Re: Exact or Least-Squares Solution 5 Equations
- References:
- Exact or Least-Squares Solution 5 Equations
- From: monir
- Re: Exact or Least-Squares Solution 5 Equations
- From: Peter Spellucci
- Re: Exact or Least-Squares Solution 5 Equations
- From: monir
- Re: Exact or Least-Squares Solution 5 Equations
- From: Peter Spellucci
- Re: Exact or Least-Squares Solution 5 Equations
- From: monir
- Exact or Least-Squares Solution 5 Equations
- Prev by Date: Production and Operations Analysis, 5th edition, Steven Nahamias
- Next by Date: Re: Software that generates a 2D triangular mesh from an image
- Previous by thread: Re: Exact or Least-Squares Solution 5 Equations
- Next by thread: Re: Exact or Least-Squares Solution 5 Equations
- Index(es):
Relevant Pages
|
|
