I know linear algebra decently well, but I've never taken a numerical analysis course. However, I've heard that it provides a good intuition for the subject. Assuming that I'm already familiar with most linear algebra concepts and matrix decompositions, in what way would a numerical analysis course benefit my understanding? Are there any concrete examples of something valuable from a computational perspective that one wouldn't get in a more abstract setting?
$\begingroup$
$\endgroup$
3
-
3$\begingroup$ johndcook.com/blog/2010/01/20/… $\endgroup$– AmzotiSep 6, 2013 at 5:04
-
$\begingroup$ Thanks Amzoti, that is a nice list. That said, I think the thing @user908123 might appreciate from a numerical course, at least the course I envision (but have never taught or taken) is a course whose theme is the ubiquity of linear approximation. Nonlinear functions, nonlinear DEs, ... near some point, suitably restricted all nicely captured by linear data. At least, linear approximation is a good starting point which obtains much of what we are interested. So, solving linear problems provides a template for approximate knowledge in many fields beyond simple linear algebra. $\endgroup$– James S. CookSep 6, 2013 at 5:11
-
$\begingroup$ @JamesS.Cook: If we are going to include numerical anything, why limit ourselves at all? We can throw in everything including the kitchen sink. For example, propagation of errors, partial differential equations, integration, eigenvalue problems, ... In fact, in most real world problems numerical methods rule. $\endgroup$– AmzotiSep 6, 2013 at 5:54
Add a comment
|
2 Answers
$\begingroup$
$\endgroup$
4
I think the big thing you'd learn is that computing and theory are quite different, and this might cause you to look at your theoretical knowledge in a different way. In particular, computing involves issues of performance and numerical stability that are typically ignored in theoretical studies.
A couple of specific examples are:
Computing a matrix inverse is almost never a good way to solve a system of linear equations.
Calculating the zeros of the characteristic polynomial is almost never a good way to find eigenvalues. Interestingly, the reverse is true — computing eigenvalues is a very good way to find the zeros of a polynomial.
Also, I think you can learn a lot by "playing" with numerical examples, which is only feasible if you have a good toolbox of numerical methods and a convenient way to access them.
-
$\begingroup$ Point (1) does not require numerical analysis. Computing a matrix inverse to solve a single system of equations is not a good idea, even over say a finite field. It requires $O(n^3)$ operations while solving a single system by Gaussian elimination requires only $O(n^2)$ operations. $\endgroup$ Sep 6, 2013 at 9:20
-
$\begingroup$ @Marc -- I guess that's true. But, back when I took linear algebra courses, they never talked about operation counts or algorithm complexity. Those topics were left for computing courses. But, the last linear algebra class I took was 45 years ago, so maybe things are different nowadays. $\endgroup$– bubbaSep 6, 2013 at 14:03
-
1$\begingroup$ @Marc van Leeuwen I do not understand the phrase "while solving a single system by Gaussian elimination requires only O(n2) operations" - it seems to contradict, for example cstheory.stackexchange.com/questions/3921/…. Could you explain? $\endgroup$– user64540Jan 22, 2015 at 8:15
-
$\begingroup$ @JohnDonn: I guess you are right; now that I think of it, the pivoting phase takes $O(n^3)$ operations, regardless of the right hand side (single vector or whole matrix to be inverted). Once a system is triangular, a single solution can be obtained in $O(n^2)$ by back substitution, while inverting the triangular matrix still costs $O(n^3)$; this must have been what was on my mind. Thanks for correcting me. $\endgroup$ Jan 22, 2015 at 9:04
$\begingroup$
$\endgroup$
Some examples, which may appear more often in numerical analysis than in linear algebra courses.
Condition numbers of matrices. This number roughly describes how sensitive the solution of $A \mathbf x = \mathbf b$ is with respect to pertubations in $\mathbf b$. Pertubations are always present in numerical analysis, due to numerical errors or different influences. This leads to the field of pre-conditioners: How can we multiply our system, i.e. $C A \mathbf x = C \mathbf b$, such that the condition number decreases? Both systems would be treated to be equal as pure linear systems, but as numerical linear systems they differ, since their numerical solutions are different.
Constructive proofs and approximative sequences. If unique, the largest eigenvector of a matrix can be found via the recursive sequence $\mathbf x_k = \frac{A \mathbf x_{k-1}}{||A \mathbf x_{k-1}||}$. (If the starting vector $\mathbf x_0$ is not orthogonal to the eigenspace of the largest eigenvalue.) This example shows how a good intuition in linear algebra helps to build numerical algorithms. This even goes further: If the iteration is ill-conditioned in direction of the largest eigenvector, numerical errors will even improve the convergence of the iteration. This leads to new algorithms, where this property is used. This is again a property, which would less interesting in a non-numerical setting.
Estimates. A typical theorem here is the Gershgorin circle theorem, which tells you more about the distance of eigenvalues from the diagonal entries of a matrix.
Special classes of matrices. For example Hessenberg-matrices are useful to build stable algorithms for eigenvalue approximation. Some numerical analysts are pure magicians when it comes to decompositions and useful matrix calculus identities.
- Sparse matrices. For parallel algorithms, matrices should be almost diagonal, here the questions also differ from typical questions in linear algebra. How can we decrease the bandwidth of a matrix, i.e. the maximum distance of non-zero entries from the diagonal?
I have the feeling that advanced linear algebra topics are spread around in almost any mathematical branch. You can analyse matrix groups, go to infinite dimensions, etc. In this sense, numerical analysis is also an extension, with a special focus on certain topics, like for example stability or sparsity. But it is not the only way to learn more about linear algebra!