Explorations in math and programming
David Lowry-Duda

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: $$ \begin{align*} 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{align*}$$ 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 $ t^3 + pt^2 + qt + r$. Then we have $$\begin{align*} x^3 + px^2 + qx + r = 0\\ y^3 + py^2 + qy + r = 0\\ z^3 + pz^2 + qz + r = 0 \end{align*}$$ Multiply equation (1) by $ a$, equation (2) by $ b$, and equation (3) by $ c$ and add. Then we get $$ m_3 + pm_2 + qm_1 + rm_0 = 0 $$ Multiply equation (1) by $ ax$, equation (2) by $ by$, and equation (3) by $ cz$ and add. Then we get $$ m_4 + pm_3 + qm_2 + rm_1 = 0 $$ Finally (you might have guessed it) multiply equation (1) by $ ax^2$, equation (2) by $ by^2$, and equation (3) by $ cz^2$ and add. Then we get $$ 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!

Leave a comment

Info on how to comment

To make a comment, please send an email using the button below. Your email address won't be shared (unless you include it in the body of your comment). If you don't want your real name to be used next to your comment, please specify the name you would like to use. If you want your name to link to a particular url, include that as well.

bold, italics, and plain text are allowed in comments. A reasonable subset of markdown is supported, including lists, links, and fenced code blocks. In addition, math can be formatted using $(inline math)$ or $$(your display equation)$$.

Please use plaintext email when commenting. See Plaintext Email and Comments on this site for more. Note also that comments are expected to be open, considerate, and respectful.

Comment via email

Comments (4)
  1. 2011-06-07 Qiaochu Yuan

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

    $$ \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.

  2. 2011-06-07 davidlowryduda

    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?

  3. 2011-06-08 Qiaochu Yuan

    Not much beyond "go to grad school." I'm still gathering information.

  4. 2011-12-25 Aryabhatta

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