The Problem of Approximation II Exercises

Here is a new topic to discuss any questions encountered when completing the exercises found in the topic above.

Hey TAs and everyone! I’m working on number 6 in developing an algorithm to compute an approximation of f(x) = sin(x) with four different bases. I see the example algorithm above the exercises, but I am unsure how to fill in the blanks where there are functions such as compute_quadrature_points and _weights as well as compute_basis and compute_geom.

I am also struggling to recognize how to go from a vector based basis to a function based basis as done in previous exercises.

Thank you in advance!

Hey, Kennen, sorry for the delayed response. For routines such as compute_quadrature_points and compute_quadrature_weights, you can just hard code in the values of the quadrature for each rule. So I would probably create a function for each of those that takes in an integer value n and returns a list of quadrature points or quadrature weights that correspond to the n-point Gauss quadrature rule.

The function compute_geom in the algorithm relates to the change of variables that you will need to do on the integral. If you do a change of variables from x\in[0,1] to some new variable \xi\in[-1,1] you will have some linear relationship x(\xi)=a\xi+b. Just as a reminder, we are doing this so that we can use quadrature, which integrates from -1 to 1. The \xi in this change of variables will be where you plug in the quadrature points and x is the value you use to evaluate \sin(x). So the compute_geom function takes in a \xi (one number) and returns an x and \frac{dx}{d\xi} at the given \xi value (one number each).

Lastly, compute_basis is a function that, given the number of basis functions desired and an evaluation point (\xi_i, or qp(i) in the code), returns a list of all the basis functions evaluated at that point. So for example, if I was doing the power basis, and I called compute_basis(3,0) I would get a list back of \{1,\xi,\xi^2\} evaluated at \xi=0.

I could ramble on, but that’s an overview of what these functions mean and how they could be implemented. It’s probably more productive if I leave it at that and let you ask further clarifying questions as needed.

Thanks Caleb! That helped me wrap my head around the exercise some more. I’ve been creating my own MATLAB functions for the different bases. I’ve been able to complete the power, Legendre, and Bernstein bases, but I’ve run into issues in my understanding of the Lagrange basis which has more than just one \xi.

For the Lagrange basis, we have \xi_m, \xi_n, and \xi_i. I know \xi is what value we want to evaluate it at. What determines these other \xi values? Is it linked to our bounds?

Hey, Kennen, in order to generate the Lagrange basis you need to choose a set of points to be the zeros of the functions. These are the \xi_i's. The standard practice is to pick the \xi_i's to be evenly spaced in the interval, but you could choose them to be any set of points that don’t coincide in the interval. So for example, for n=2, and keeping in mind that we are defining these polynomials on [-1,1], standard practice would be to choose the set of points \xi_0=-1, \xi_1=0, \xi_2=1.

Now let’s talk about the subscripts. The notation
L_i(\xi) = \prod_{\begin{smallmatrix}0\le m\le n\\ m\neq i\end{smallmatrix}} \frac{\xi-\xi_m}{\xi_i-\xi_m}
can be a bit difficult to digest until you see some examples. Let’s continue what we started above. You’ve got n=2, you’ve chosen a \xi_0, \xi_1 and \xi_2, and you want to create L_i, for i=0,1,2. This is done as

L_0(\xi) = \prod_{\begin{smallmatrix}0\le m\le 2\\ m\neq 0\end{smallmatrix}} \frac{\xi-\xi_m}{\xi_0-\xi_m}=\frac{\xi-\xi_1}{\xi_0-\xi_1}\frac{\xi-\xi_2}{\xi_0-\xi_2}

L_1(\xi) = \prod_{\begin{smallmatrix}0\le m\le 2\\ m\neq 1\end{smallmatrix}} \frac{\xi-\xi_m}{\xi_1-\xi_m}=\frac{\xi-\xi_0}{\xi_1-\xi_0}\frac{\xi-\xi_2}{\xi_1-\xi_2}

L_2(\xi) = \prod_{\begin{smallmatrix}0\le m\le 2\\ m\neq 2\end{smallmatrix}} \frac{\xi-\xi_m}{\xi_2-\xi_m}=\frac{\xi-\xi_0}{\xi_2-\xi_0}\frac{\xi-\xi_1}{\xi_2-\xi_1}

So you basically create a product of all these linear polynomials in \xi, skipping the one when m=i which would cause a divide by zero anyway.

Hopefully that’s helpful. Let me know where I can further clarify.

Also, if you haven’t seen the \Pi notation before, it’s like the sum notation \Sigma but for products instead of sums. See Wikipedia:

Ok so if I were to make a function to calculate the polynomials for this basis I would need to know what degree (n) and have a vector of all the given \xi like [\xi_0, \xi_1, \xi_2]. Now taking it one step further of calculating a value for a this basis at a specific point I would need the above two inputs as well as a single point to evaluate at?

So in MATLAB my function would have three inputs? The degree, n, the vector of \xi_i, and the value for \xi? Is that correct?

Yes, or you can hard code the \xi_i into that function so that it will have the same input as the other bases.

I’ve got a question on number 6. For some reason I’m able to match the coefficient output using x [0,1] for the power basis and xi [-1,1] for the Bernstein basis (if I ignore the 5th (extra?) row of the answer key), but my Lagrange and Legendre don’t match. However, when I graph the Legendre and Lagrange bases I get graphs that seem to match up with theory. That makes the problem appear to be happening in my mass matrix and F calculations, but that is confusing because my Bernstein and power bases do alright through that. What’s also interesting is that the error is 10^(-2) to 10^(-11) so the fit of uh to sin(x) for all cases is very good. It’s got me thinking in circles. Do you have an idea what’s happening?


Row 1 = power, row 2 = Legendre, row 3 = Lagrange, row 4 = Bernstein

@Rebecca, if your approximation u^h converges to sin(x) and you’ve verified that you are using a correct form for the legendre and lagrange polynomials then you’re done. There are some different things that could cause the answer key to differ such as using standard form of legendre vs. the normalized version but as you’ve already noted, the answer key is already suspect because of the erroneous row. We will work to improve the answer key with more clarity about how results were obtained, and we’ll work with you to make sure we can get the same answer but for now I would mark what you’ve done as correct since your approximation is working correctly.

1 Like