Featured Posts

There has been a spate of Questions posted in the past week about computing eigenvalues. Invariably, the Questioners have computed some eigenvalues by applying fsolve to a characteristic polynomial obtained from a floating-point matrix via LinearAlgebra:-Determinant. They are then surprised when various tests show that these eigenvalues are not correct. In the following worksheet, I show that the eigenvalues computed by the fsolve@Determinant method (when applied to a floating-point matrix) are 100% garbage for dense matrices larger than about Digits x Digits. The reason for this is that computing the determinant introduces too much round-off error into the coefficients of the characteristic polynomial. The best way to compute the eigenvalues is to use LinearAlgebra:-Eigenvalues or LinearAlgebra:-Eigenvectors. Furthermore, very accurate results can be obtained without increasing Digits.

 

The correct and incorrect ways to compute floating-point eigenvalues

Carl Love 2016-Jan-18

restart:

Digits:= 15:

macro(LA= LinearAlgebra):

n:= 2^5:  #Try also 2^3 and 2^4.

A:= LA:-RandomMatrix(n):

A is an exact matrix of integers; Af is its floating-point counterpart.

Af:= Matrix(A, datatype= float[8]):

P:= LA:-CharacteristicPolynomial(A, x):

P is the exact characteristic polynomial with integer coefficients; Pf is the floating-point characteristic polynomial computed by the determinant method.

Pf:= LA:-Determinant(Af - LA:-DiagonalMatrix([x$n])):

RP:= [fsolve(P, complex)]:

RP is the list of floating-point eigenvalues computed from the exact polynomial; RPf is the list of eigenvalues computed from Pf.

RPf:= [fsolve(Pf, complex)]:

RootPlot:= (R::list(complexcons))->
     plot(
          [Re,Im]~(R), style= point, symbol= cross, symbolsize= 24,
          axes= box, color= red, labels= [Re,Im], args[2..]
     )
:

RootPlot(RP);

RootPlot(RPf);

We see that the eigenvalues computed from the determinant are completely garbage. The characteristic polynomial might as well have been x^n - a^n for some positive real number a > 1.

 

Ef is the eigenvalues computed from the floating-point matrix Af using the Eigenvalues command.

Ef:= convert(LA:-Eigenvalues(Af), list):

RootPlot(Ef, color= blue);

We see that this eigenvalue plot is visually indistinguishable from that produced from the exact polynomial. This is even more obvious if I plot them together:

plots:-display([RootPlot(Ef, color= blue), RootPlot(RP)]);

Indeed, we can compare the two lists of  eigenvalues and show that the maximum difference is exceedingly small.

 

The following procedure is a novel way of sorting a list of complex numbers so that it can be compared to another list of almost-equal complex numbers.

RootSort:= (R::list(complexcons))-> sort(R, key= abs*map2(`@`, signum+2, Re+Im)):


max(abs~(RootSort(RP) -~ RootSort(Ef)));

HFloat(1.3258049636636544e-12)

 

 

``

 

Download Eigenvalues.mw

Disclaimer: This blog post has been contributed by Dr. Nicola Wilkin, Head of Teaching Innovation (Science), College of Engineering and Physical Sciences and Jonathan Watkins from the University of Birmingham Maple T.A. user group*.

 

If you have arrived at this post you are likely to have a STEM background. You may have heard of or had experience with Maple T.A or similar products in the past. For the uninitiated, Maple T.A. is a powerful system for learning and assessment designed for STEM courses, backed by the power of the Maple computer algebra engine. If that sounds interesting enough to continue reading let us introduce this series of blog posts for the mapleprimes website contributed by the Maple T.A. user group from the University of Birmingham(UoB), UK.

These posts mirror conversations we have had amongst the development team and with colleagues at UoB and as such are likely of interest to the wider Maple T.A. community and potential adopters. The implementation of Maple T.A. over the last couple of years at UoB has resulted in a strong and enthusiastic knowledge base which spans the STEM subjects and includes academics, postgraduates, undergraduates both as users and developers, and the essential IT support in embedding it within our Virtual Learning Environment (VLE), CANVAS at UoB.

By effectively extending our VLE such that it is able to understand mathematics we are able to deliver much wider and more robust learning and assessment in mathematics based courses. This first post demonstrates that by comparing the learning experience between a standard multiple choice question, and the same material delivered in a Maple TA context.

To answer this lets compare how we might test if a student can solve a quadratic equation, and what we can actually test for if we are not restricted to multiple choice. So we all have a good understanding of the solution method, let's run through a typical paper-based example and see the steps to solving this sort of problem.

Here is an example of a quadratic

To find the roots of this quadratic means to find what values of x make this equation equal to zero. Clearly we can just guess the values. For example, guessing 0 would give

So 0 is not a root but -1 is.

There are a few standard methods that can be used to find the roots. The point though is the answer to this sort of question takes the form of a list of numbers. i.e. the above example has the roots -1, 5. For quadratics there are always two roots. In some cases two roots could be the same number and they are called repeated roots. So a student may want to answer this question as a pair of different numbers 3, -5, the same number repeated 2, 2 or a single number 2. In the last case they may only list a repeated roots once or maybe they could only find one root from a pair of roots. Either way there is quite a range of answer forms for this type of question.

With the basics covered let us see how we might tackle this question in a standard VLE. Most are not designed to deal with lists of variable length and so we would have to ask this as a multiple choice question. Fig. 1, shows how this might look.

VLE Question

Fig 1: Multiple choice question from a standard VLE

Unfortunately asking the question in this way gives the student a lot of implicit help with the answer and students are able to play a process of elimination game to solve this problem rather than understand or use the key concepts.

They can just put the numbers in and see which work...

Let's now see how we may ask this question in Maple T.A.. Fig. 2 shows how the question would look in Maple T.A. Clearly this is not multiple choice and the student is encouraged to answer the question using a simple list of numbers separated by commas. The students are not helped by a list of possible answers and are left to genuinely evaluate the problem. They are able to provide a single root or both if they can find them, and moreover the question is not fussy about the way students provide repeated roots. After a student has attempted the question, in the formative mode, a student is able to review their answer and the teacher's answer as well as question specific feedback, Fig. 3. We'll return to the power of the feedback that can be incorporated in a later post.

Maple T.A. Question

Fig. 2: Free response question in Maple T.A.

  

Maple T.A. Answer

Fig. 3: Grading response from Maple T.A.

The demo of this question and others presented in this blog, are available as live previews through the UoB Maple T.A. user group site.

Click here for a live demo of this question.

The question can be downloaded from here and imported as a course module to your Maple T.A. instance. It can also be found on the Maple TA cloud by searching for "Find the roots of a quadratic". Simply click on the Clone into my class button to get your own version of the question to explore and modify.

* Any views or opinions presented are solely those of the author(s) and do not necessarily represent those of the University of Birmingham unless explicitly stated otherwise.


MaplePrimes Questions Recent Unanswered Maple MapleSim Maple T.A.