Find the value of m and c such that a straight line y = mx + c, best represents the equation of a given set of points (x, y ), (x, y ), (x, y ), ……., (x, y ), given n >=2.
Input : n = 5 x = 1, x = 2, x = 3, x = 4, x = 5 y = 14, y = 27, y = 40, y = 55, y = 68 Output : m = 13.6 c = 0 If we take any pair of number ( x, y ) from the given data, these value of m and c should make it best fit into the equation for a straight line, y = mx + c. Take x = 1 and y = 14, then using values of m and c from the output, and putting it in the following equation, y = mx + c, L.H.S.: y = 14, R.H.S: mx + c = 13.6 x 1 + 0 = 13.6 So, they are approximately equal. Now, take x = 3 and y = 40, L.H.S.: y = 40, R.H.S: mx + c = 13.6 x 3 + 0 = 40.8 So, they are also approximately equal, and so on for all other values. Input : n = 6 x = 1, x = 2, x = 3, x = 4, x = 5, x = 6 y = 1200, y = 900, y = 600, y = 200, y = 110, y = 50 Output : m = -243.42 c = 1361.97
To best fit a set of points in an equation for a straight line, we need to find the value of two variables, m and c. Now, since there are 2 unknown variables and depending upon the value of n, two cases are possible –
Case 1 – When n = 2 : There will be two equations and two unknown variables to find, so, there will be a unique solution .
Case 2 – When n > 2 : In this case, there may or may not exist values of m and c, which satisfy all the n equations, but we can find the best possible values of m and c which can fit a straight line in the given points .
So, if we have n different pairs of x and y, then, we can form n no. of equations from them for a straight line, as follows
f = mx + c, f = mx + c, f = mx + c, ......................................, ......................................, f = mx + c, where, f, is the value obtained by putting x in equation mx + c.
Then, since ideally f should be same as y, but still we can find the f closest to y in all the cases, if we take a new quantity, U = ?(y – f ), and make this quantity minimum for all value of i from 1 to n.
Note:(y – f ) is used in place of (y – f ), as we want to consider both the cases when f or when y is greater, and we want their difference to be minimum, so if we would not square the term, then situations in which f
is greater and situation in which y is greater will ancel each other to an extent, and this is not what we want. So, we need to square the term.
Now, for U to be minimum, it must satisfy the following two equations –
= 0 and = 0.
On solving the above two equations, we get two equations, as follows :
?y = nc + m?x, and ?xy = c?x + m?x, which can be rearranged as - m = (n * ?xy - ?x?y) / (n * ?x - (?x)), and c = (?y - m?x) / n,
So, this is how values of m and c for both the cases are obtained, and we can represent a given set of points, by the best possible straight line.
The following code implements the above given algorithm –
Analysis of above code-
Auxiliary Space : O(1)
Time Complexity : O(n). We have one loop which iterates n times, and each time it performs constant no. of computations.
1-Higher Engineering Mathematics by B.S. Grewal.
Please write comments if you find anything incorrect, or you want to share more information about the topic discussed above.