Skip to content

Instantly share code, notes, and snippets.

@EndangeredMassa
Last active August 29, 2015 14:06
Show Gist options
  • Save EndangeredMassa/380ad9001f09175f733e to your computer and use it in GitHub Desktop.
Save EndangeredMassa/380ad9001f09175f733e to your computer and use it in GitHub Desktop.
Estimating Over-determined Systems of Equations
/*
An over-determined system of equations is one that has more equations than unknowns.
This can lead to unsolvable systems--where there is no one value for each unkown
that can satisfy all equations in the system.
When this happens, there are ways to estimate the value of each unkown
such that it is the best fit for the system. That is, it will make each equation
come the closest to being balanced.
I am trying to reproduce this operation to get the same result.
https://www.elie.net/blog/hearthstone/how-to-find-automatically-hearthstone-undervalued-cards#.VBdzGi5dWEg
The example here isn't over-determined, but that's not important right now. System:
4a + 3h + 1c + 0d + 1i = 4
5a + 2h + 1c + 0d + 1i = 6
4a + 2h + 1c + 1d + 1i = 6
3a + 1h + 0c + 1d + 1i = 3
1a + 1h + 0c + 1d + 1i = 1
Supposedul, performing an "ordinary least squares" reduction on this system produces:
a = 1
h = -2
c = 4
d = 1
i = 1
My first goal is to reproduce this result in code. My second goal is to apply the technique
to a different system of equations that is wildly over-determined.
*/
// node.js with `npm install numeric`
// http://www.numericjs.com/documentation.html
var numeric = require('numeric');
// using https://en.wikipedia.org/wiki/Overdetermined_system#Approximate_solutions
var a = [
[4,3,1,0,1],
[5,2,1,0,1],
[4,2,1,1,1],
[3,1,0,1,1],
[1,1,0,1,1]
];
var b = [4, 6, 6, 3, 1];
var at = numeric.transpose(a);
var lhs = numeric.inv(numeric.dot(at, a));
var rhs = numeric.dot(at, b);
numeric.dot(lhs, rhs);
/*
[ 1.000000000000007,
-1.0000000000000568,
3,
0.9999999999999858,
0 ]
*/
// or: [1, -1, 3, 1, 0]
// expected: [1, -2, 4, 1, 1]
/*
This is just the latest thing I tried. I'd prefer to find a JavaScript library
that can do what I need, but am having trouble. Each library either appears
to only do a simpler form of what I need OR is not clear how I actually use it.
I'm happy to consider other platforms if their solutions work, but I would probably
just port that back to JavaScript.
*/
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment