I frequent math.stackexchange these days (if you haven’t heard of it, you should go check it out), and every once in a while I get stunned by a solution or a thoughtful question. As I took my Numerical Analysis Class my last semester as an undergrad (last semester, woo hoo!), I remember coming up against Gaussian Quadrature estimates for integration. It’s a very cool thing, but the system of equations to solve seems very challenging – in fact, it feels like one must use a numerical approximation method to solve them. While I don’t have any big qualms with numerical solutions, I much prefer exact solutions. Here is the best method I’ve seen in solving these (this is for 3 points, but we see how it could be used for 1,2, and 4 points as well), and all credit must be given to the user Aryabhatta at Math SE, from this post.

The task is easy to state: solve the following system:

$latex \begin{aligned}

a + b + c &= m_0 \\

ax + by + cz &= m_1 \\

ax^2 + by^2 + cz^2 &= m_2 \\

ax^3 + by^3 + cz^3 &= m_3 \\

ax^4 + by^4 + cz^4 &= m_4 \\

ax^5 + by^5 + cz^5 &= m_5

\end{aligned}$

We are to solve for x, y, z, a, b, and c; the m are given. This is unfortunately nonlinear. And when I first came across such a nonlinear system, I barely recognized the fact that it would be so annoying to solve. It would seem that for too many years, the solutions the most of the questions that I’ve had to come across were too pretty to demand such ‘vulgar’ attempts to solve them. Anyhow, one could use iterative methods to arrive at a solution. Or one could use the Golub-Welsch Algorithm (which I also discovered at Math SE). One could use resultants, which I did in my class. Or one could be witty.

Let’s introduce three new variables. Let x, y, and z be the roots of $latex t^3 + pt^2 + qt + r$. Then we have

$latex \begin{aligned}

x^3 + px^2 + qx + r = 0\\

y^3 + py^2 + qy + r = 0\\

z^3 + pz^2 + qz + r = 0

\end{aligned}$

Multiply equation (1) by $latex a$, equation (2) by $latex b$, and equation (3) by $latex c$ and add. Then we get

$latex m_3 + pm_2 + qm_1 + rm_0 = 0 $

Multiply equation (1) by $latex ax$, equation (2) by $latex by$, and equation (3) by $latex cz$ and add. Then we get

$latex m_4 + pm_3 + qm_2 + rm_1 = 0 $

Finally (you might have guessed it) multiply equation (1) by $latex ax^2$, equation (2) by $latex by^2$, and equation (3) by $latex cz^2$ and add. Then we get

$latex m_5 + pm_4 + qm_3 + rm_2 = 0 $

Now (4),(5), (6) is just a set of 3 linear equations in terms of the variables p, q, r. Solving them yields our cubic. We can then solve the cubic (perhaps using Cardano’s formula, etc.) for x, y, and z. And once we know x, y, and z we have only a linear system to solve to find the weights a, b, and c. That’s way cool!

You’re right that the nonlinearity is misleading. The problem can be restated as

$latex displaystyle frac{a}{1 – xt} + frac{b}{1 – yt} + frac{c}{1 – zt} equiv m_0 + m_1 t + … + m_5 t^5 bmod t^5$

and then it becomes the most natural thing in the world to clear denominators.

That’s true, and it immediately makes a lot of sense.

We seem to run across each other a lot now. I suspect that we’ll run across each other a lot in the future, too. Do you have any grad school plans yet?

Not much beyond “go to grad school.” I’m still gathering information.

A great mathematician. Without the inventions the world would be different.