วีดีโอ

This follows from Taylor's theorem with remainder. In many situations in numerical analysis, we just write f(x+h) = f(x) + h f'(x) + O(h^2), and the "big-O" term captures everything at higher order. But Taylor's theorem with remainder allows us to make a more precise statement, and characterize that additional term exactly. We can say that f(x+h) = f(x) + h f'(x) + h^2 f''(c)/2, where c is some number between a and h. In general, we don't know exactly what c is, but we know that it exists. This is helpful, because if we have a bound on f'', such as |f''(c)| ≤ M as above, then that allows us to precisely bound this term, even without knowing exactly what c is. By contrast, the "big-O" notation does not give us a way to make an exact bound like this. You can find a number of references online for Taylor's theorem with remainder. The Wikipedia page for Taylor's theorem has it, although the presentation is somewhat technical. See the section about "Mean-value forms of the remainder".

@@chrisrycroft2010 Thanks a lot for the detailed explanation, I will read up on Taylor’s theorem with remainder. Can’t wait to go through the rest of the series, thanks again!

Thanks for the feedback and that is a good observation. I've always found this algorithm difficult to explain, given the similar definitions of the Q_k, R_k, and the underscored versions. You make a good point about A_k becoming close to diagonal. One counterpoint is that A_0 does exactly match A. But I think you're right, that some other notation might be more appropriate to indicate how it behaves in the limit.

The main course website is people.math.wisc.edu/~chr/am205/ and you can find all of the code examples on GitHub at github.com/chr1shr/am205_examples .

You're right: this is not an ideal computer demo, and I always found it awkward when I lectured on this. It solves the mathematical problem, but it glosses over the implementation details. This largely arose due to the structure of the lecture-based course: nonlinear least squares belongs mathematically in Unit 1, but I didn't want to get too much into these types of algorithms until Unit 4. If I end up creating online-only material in the future, where the timing of each topic is more flexible, then I will look at revising this.

Thanks for your quick reply and confirmation. I just hacked together the algorithm in javascript as an exercise, so knowing all the nitty-gritty implementation details under the hood became important. I wonder why scipy.root even has a "lm" option and what it does with it. @@chrisrycroft2010

Glad you like the videos. The term eps*f(x)/h comes from considerations of computer hardware and how rounding errors occur. This is one of the first videos in the sequence and it's designed to provide a quick introduction, so I gloss over these details here. But they are covered extensively in the later video 0.4 (th-cam.com/video/VzKl3-D1CVc/w-d-xo.htmlsi=cmaXFMYZnO877_fJ). Modern computer hardware typically represents real numbers using floating point arithmetic, which is essentially like scientific notation and allows numbers with very different scales to be represented. Whenever you do an arithmetic operation like a+b, then the hardware guarantees that you will get the correct answer up to a relative error of machine precision (called epsilon). Typically epsilon is on the order of 10^{-16}. Here, when you calculate the derivative, you have to do f(x+h)-f(x) in the numerator. Since f(x) and f(x+h) roughly have the same scale, the rounding error you will get will be of size epsilon*|f(x)|. Dividing through by h from the denominator gives epsilon*|f(x)|/h. This division will also create an additional rounding error, although it turns out this will be small and not affect the approximate bound. The reason that the f(x+h)-f(x) operation gives the largest contribution to the rounding error is that you are trying to measure a small difference between two terms that are large. That is a case where rounding error becomes noticeable.

@@chrisrycroft2010 Thank you so much for the prompt reply and detailed explanation. It really helps, and I found the explanation in video 0.4 (@ around 18:00). Thanks again!

It is indeed a backward iteration, and the algorithm is correctly written in the video. You need to start at the bottom of each column at j=m and work your way up to j=k+1. By considering in that order, you will zero out all of the entries in the column below the diagonal.

@@chrisrycroft2010 But it is possible to have G(j-1,j,theta) to eliminate a_{jk} ? not G(j,k,theta)

@@holyshit922 Yes, the notation G(j-1,j,theta) is correct. This matrix is only acting on rows j-1 and j. The theta value is chosen so that G eliminates a_{jk} and sets it to zero. Essentially, it rotates all of the contribution of a_{jk} into a_{j-1,k}. See earlier in the video. The G matrix will do nothing to the columns q where q<k, since by the time you reach that point in the algorithm, all of those entries are zero. The G matrix will modify entries in columns q where q>k, but that doesn't matter since those columns haven't been considered yet.

Hi Eitan, I'm glad you like the videos. I am definitely planning to make more videos, an in particular I would like to make videos on more advanced topics like the AM225 material. But I have a large number of Ph.D. students graduating in summer 2024, and I am very busy ensuring they complete their thesis work on time, so it will likely be mid-2024 before I have sufficient time to do this.

The material for videos 5.7 and 5.8 was given as a stand-alone lecture that was separate from the main course content. Because of this, I did not record videos for that material along with the others. I am intending to record videos on this material, but I want to do a good job so it will take some time. I may complete them around Jan/Feb 2024, outside of my usual teaching responsibilities. In the meantime, you may find the associated notes useful: people.math.wisc.edu/~chr/am205/notes/iter_lecture.pdf

We need the following two properties: 1. A matrix M is positive definite if and only if x^T M x > 0 for all non-zero vectors x. 2. If a matrix M is invertible, then the only vector z that satisfies Mz=0 is the zero vector. Now suppose S^T S is positive definite, and that there exists a vector z such that (A^T A + S^T S) z = 0. Then 0 = z^T (A^T A + S^T S ) z = (Az)^T Az + z^T S^T S z = || Az ||^2 + z^T (S^T S) z. We know that ||Az||^2≥0, and hence the only way that this can be zero is if z^T (S^T S) z = 0. Therefore property 1 implies that z is the zero vector. Hence property 2 shows that (A^T A + S^T S) is invertible.

Yes, I am aware of Zu Chongzhi's amazing achievement. The history of the calculation of pi is a fascinating subject that links many mathematicians together across millennia. While the video above could only cover a small fraction of the history, I have previously given a lecture on pi, where I feature Zu Chongzhi. See the slides here: people.math.wisc.edu/~chr/events/pi_day_talk.pdf At some point I may convert these lecture slides into a separate video.

I just finished my undergraduate, saw this course online. Let me go through it I hope I can understand it

Glad you find the videos useful. Yes-I think that that the core ideas behind PageRank are similar to the spectral graph analysis example I describe in the video. The example that I give is also called eigenvector centrality, and Wikipedia mentions that PageRank is a variant of eigenvector centrality. (see en.wikipedia.org/wiki/Eigenvector_centrality )

I think the only thing that you need to change is that when you compute the scalar products, such as alpha_m = q_m^T v, then they use the Hermitian transpose instead of the regular transpose. Therefore alpha_m = q_m^* v. That also affects the computation of the Euclidean norm. Instead of ||b||_2 = sqrt(b^T b), it becomes ||b||_2 = sqrt(b^* b). The Wikipedia page on the Lanczos algorithm presents the algorithm for the complex case: en.wikipedia.org/wiki/Lanczos_algorithm

Thanks for your comment. The Broyden method and BFGS are connected, but they solve two different problems. For the Broyden method, you are trying to solve a nonlinear system of equations F(x)=0, where x is an n-dimensional vector, and F is an n-dimensional function (i.e. F: R^n -> R^n). BFGS on the other hand solves the optimization problem of minimizing a function g(x), where x is an n-dimensional vector and g is a scalar function (i.e. g: R^n -> R). To minimize (or maximize) a function we can search for points where grad(g)=0. Thus if we define F(x)=grad(g(x)), then this optimization problem can be viewed as a root-finding problem, for finding F(x)=grad(g(x))=0. The key point is that F in the Broyden method is roughly equivalent to grad(g) in BFGS. Thus, it isn't the case that BFGS uses more information by using the gradient, because BFGS is trying set the gradient to zero, whereas Broyden is trying to set F to zero. Overall, the two methods have similar information available, and converge similarly for their respective tasks. Some of the other videos in Unit 4 of the course talk a bit further about these connections between root-finding and optimization.