Substitution to turn a nonlinear least squares problem into a linear oneby bers Tags: linear, nonlinear, squares, substitution, turn 

#1
Dec1112, 03:56 PM

P: 4

Hi,
I want to solve an overdetermined nonlinear equation with the method of least squares. Assume it's f(x) = 1 + ax + a^2 + b, and I want to estimate a and b. This is nonlinear, as I said, so the derivatives of the squared residuals involve a^3 terms and are difficult to solve. Now I thought about substituting c = a^2 + b, which would turn this into a linear system that LOOKS pretty easy to solve. But when calculating the derivatives of the residuals, do I need to take into account that dc/da != 0 (which would make the terms quite complicated again), or can I simply proceed as if c had been the original variable? If I am allowed to go this way (I guess I am), what are the conditions  when am I allowed to substitute to turn a nonlinear leastsquares system into a linear one? Can you point me at any fundamental rule for this? I searched Google quite a bit, but have not found any adequate. Thanks bers 



#2
Dec1112, 07:44 PM

Math
Emeritus
Sci Advisor
Thanks
PF Gold
P: 38,882

You can approximate a nonlinear problem, about a fixed set of values, by replacing any nonlinear formula with its linear approximation. You are allowed to do this any time, at any point but how accurate the approximation is depends on how close to linear the function is at that point. If you are allowed to choose the point, then take the derivative and choose the point where the derivative (or its magnitude) is smallest. If, as often happens, you are given the point, check the derivative to see if "linearizing" will give reasonably accurate results.




#3
Dec1112, 08:04 PM

HW Helper
P: 930

Least squares using nonlinear functions can be rather straighforward. It's really just a series of linearized least squares problems (based on an initial guess of the solution) that (hopefully) iteratively converge to a solution. Difficulties can arrise if the starting point is far from the solution and/or the matrices are illconditioned.




#4
Dec1212, 02:17 AM

P: 4

Substitution to turn a nonlinear least squares problem into a linear one
Hi,
thanks for your answers. I do think, however, I did not point out two important things clearly enough: 1. I am aware of many iterative algorithms for this problem. However, I'm interested in a noniterative solution. (Would you call this an adhoc solution?) Anyway, I want to have a fixedruntime algorithm for the problem I mentioned, and we all know that linear problems can be solved this way. 2. I am also not interested in an approximation. I am interested whether the substitution will allow me to find the exact solution in a linear way. So let me summarize what I got to so far. Let's talke about [itex]f(x) = 1 + ax + a^2 + b[/itex]. Using some data [itex]x_i[/itex] and [itex]y_i[/itex], I can define the residual [itex]R = \sum_{i=1}^n f(x_i)  y_i^2[/itex] Inserting [itex]f[/itex] with [itex]c[/itex] substituted by [itex]a^2 + b[/itex], I find [itex]R = \sum_{i=1}^n 1 + ax_i + c  y_i^2[/itex] Now, I need to calculate the derivatives with respect to a and c. Not knowing whether total or partial derivatives are the way to go, let's try both. [itex]\partial R / \partial a = \sum_{i=1}^n 2 (1 + ax_i + c  y_i) \cdot x_i = 0[/itex] [itex]\partial R / \partial c = \sum_{i=1}^n 2 (1 + ax_i + c  y_i) \cdot 1 = 0[/itex] These are pretty easy to solve noniteratively, because they are linear in a and c, although my original problem is not. That is my main concern. Will the solution I achieve from this system of equations be exact? In the manual examples I calculated, they were, but I cannot be sure this is always the case. If we go for total derivatives, we need to account for c depending on a, with [itex]\partial c / \partial a = 2a[/itex] and [itex]\partial a / \partial c[/itex] involving roots. [itex]dR / da = \sum_{i=1}^n 2 (1 + ax_i + c  y_i) \cdot (x_i + \partial c / \partial a) = 0[/itex] [itex]dR / dc = \sum_{i=1}^n 2 (1 + ax_i + c  y_i) \cdot (1 + \partial a / \partial c)= 0[/itex] These are now not linear any more, and much more complex to solve. Testing some values fulfilling [itex]f(x_i) = y_i[/itex] and the correct values for a and b will of course make the first term [itex]1 + \dots  y_i[/itex] equal 0, so the derivatives are 0 in both cases. So, still I am not sure which way is the right one... 



#5
Dec1212, 11:39 AM

HW Helper
P: 930

Seems to me your first approach is perfectly valid. But, the problem is even simpler if you let c = 1 + a^{2} + b. Your equation is then f(x) = ax + c which is very easy to solve for a, c from a least squares standpoint. Then, you can determine b = c  1  a^{2}.




#6
Dec1212, 11:46 AM

P: 4

Yes, I confirmed that this works using distorted data (y_i = f(x_i) + some error) with a nonzero residuum. I obtained the same estimates as with Matlab and a nonlinear iterative procedure (and got wrong results with the total differential method, by the way).
So that would mean I can obtain a linear formulation for a lot of nonlinear problems, such as f(x) = bx + ax + a^2. For example, I could do c = a^2 and then d = b + sqrt(c) to obtain f(x) = dx + c. What I am wondering is:  Why can't I find any mentioning of these substitutions on Google or elsewhere?  Under which conditions can I do this substitution? So, what "kinds of" nonlinearities can be (perfectly) "linearized", and which ones can't? 



#7
Dec1212, 08:24 PM

HW Helper
P: 930

I believe the problem you stated is really a linear problem. Let's say the problem was proposed in reverse. I give you data and ask you to fit it to the equation f(x) = ax + c. After you give me the result I tell you I want to redefine c = 1 + a^{2} + b. The fact that a valid algebraic manipulation is performed on the parameters doesn't turn a linear problem into a nonlinear one.
It seems to me (though I have no idea how to prove it mathematically) that if you can obtain a solveable algebraic expression for the unknown parameters you'll be ok. 


Register to reply 
Related Discussions  
Linear Algebra problem (Least Squares?)  Calculus & Beyond Homework  2  
Linear Least squares  Calculus & Beyond Homework  0  
Uncertainty of linear and non linear leastsquares fit  Set Theory, Logic, Probability, Statistics  6  
Numerical Methods  Linear Least Squares, NonLinear Least Squares, Optimization  Mathematics Learning Materials  0  
Linear Regression, Linear Least Squares, Least Squares, Nonlinear Least Squares  Linear & Abstract Algebra  4 