Mathematics

12:10 AM

Hello everyone, I'm new to the chat room and in full disclosure I'm working on homework for a graduate-level applied math course. I'm also pretty new to doing proofs.

What is the general strategy for proving that an algorithm is backward stable?

Here is the specific problem that I'm working on: https://imgur.com/0ja9taE

Ted Shifrin

Full disclosure: We have more unapplied than applied math geeks in here, so you may not get help unless the right people are around.

Joseph Dasenbrock

Thanks @ted

Ted Shifrin

In particular, I know some applied stuff but absolutely nothing about what you're thinking about.

Joseph Dasenbrock

Proofs in general are difficult for me, in my undergrad I really tried to avoid memorizing patterns vs building real understanding. Still feel like I'm unprepared for proofs, different type of thinking.

Ted Shifrin

I believe your professor stated the problem very sloppily, which won't help. Have you taken a beginning real analysis course? This is of that same flavor.

I believe his statement should be something like: given any $x$ and $\varepsilon>0$, there is an $\tilde x$ so that blah blah blah.

In other words, the $\tilde x$ is going to depend on $\varepsilon$.

The $C$ is supposed to be universal.

Joseph Dasenbrock

12:19 AM

I haven't done any work in real analysis, unfortunately. How do you mean "universal" about $C$?

Ted Shifrin

The flavor of this question makes me think some real analysis experience might be a good prerequisite. I mean the point is that the constant $C$ is supposed to work for all $x$ and all $\varepsilon$ and appropriate $\tilde x$.

Ryan Unger

Universal property

In various branches of mathematics, a useful construction is often viewed as the “most efficient solution” to a certain problem. The definition of a universal property uses the language of category theory to make this notion precise and to study it abstractly. This article gives a general treatment of universal properties. To understand the concept, it is useful to study several examples first, of which there are many: all free objects, direct product and direct sum, free group, free lattice, Grothendieck group, Dedekind–MacNeille completion, product topology, Stone–Čech compactification, tensor...

Ted Shifrin

Oh, and I didn't state what he did, the $\tilde x$ has to give you result of the algorithm when you plug it into $f$.

No, no, no, @Ryan, not helpful.

Ryan Unger

lol

it will be when some number theorist categorifies analysis

Ted Shifrin

So the thing you need to analyze, @Joseph, is this: How well does taking the floor of the square of the floor of $x$ approximate $x^2$?

Joseph Dasenbrock

12:23 AM

That sounds interesting re real analysis, maybe I'll try to get some self-study in on real analysis. I see what you're saying about universality, yes, that makes sense.

Ted Shifrin

So, if you choose $\tilde x$ with $\tilde x^2 = \text{alg}(x)$, can you estimate $|x-\tilde x|/|x|$?

I guess I don't understand this. You don't get much freedom in choosing $\tilde x$. It's essentially unique (up to sign), given $x$.

Joseph Dasenbrock

I hadn't thought of it in terms of a floor. I think that would assume a truncation rounding strategy. I'm gathering that IEEE typically has a different rounding strategy - en.wikipedia.org/wiki/IEEE_754#Rounding_rules

assuming truncation might be fair enough for this problem since it doesn't explicitly state.

Ted Shifrin

But if you make $\varepsilon$ smaller, you have to be able to move $\tilde x$ closer to $x$. So I totally do not understand this.

Oh, what does fl mean?

floating?

Joseph Dasenbrock

floating point representation of the true value

yes,

Ted Shifrin

Aha. My bad.

Joseph Dasenbrock

12:29 AM

np

Ted Shifrin

Oh, I see, so fl depends on $\varepsilon$. Now it makes more sense.

I'm out of my league :)

Joseph Dasenbrock

the top problem here seems to be a similar problem: bicmr.pku.edu.cn/~dongbin/Teaching_files/UA575A.13f/…

Ted Shifrin

So the point is that $x$ and $\text{fl}(x)$ differ by (at most) machine $\varepsilon$. You want to see what happens when you do the squaring stuff.

Joseph Dasenbrock

I believe $fl(x) = x(1+\delta)$, where $|\delta| < \macheps$.

yes, I hit enter before reading your last post

Ted Shifrin

Is the error between fl($x$) and $x$ scaling with $|x|$ or is it absolute?

Oh, I guess what you wrote makes sense.

Joseph Dasenbrock

12:34 AM

I believe it would be absolute because it is basically just roundoff

Ted Shifrin

No, I'm not worrying absolute value. I was worrying about whether the error should scale with $x$.

Anyhow, I think you know what to try to do now.

Joseph Dasenbrock

wouldn't the error be invariant to $x$ since it is based on roundoff?

yes, I think I'll get it

thanks for the help

Ted Shifrin

Well, you put the $|x|$ multiplying $\delta$. I guess if you do a huge number, the roundoff error will be more significant, obviously, than if you do a small number. The computer can keep track of only so many significant digits. So I'm saying I think what you wrote makes sense to me.

Joseph Dasenbrock

ah, I see what you're saying

@TedShifrin, what is a good intro text for real analysis?

Ted Shifrin

Hmm, here's a non-traditional suggestion, but a much more intuitive treatment, working only (for most of the book) on $\Bbb R$. Look at Arthur Mattuck's Introduction to analysis.

Joseph Dasenbrock

12:46 AM

Great! The amazon description looks like it was written for me - amazon.com/Introduction-Analysis-Arthur-Mattuck/dp/1484814118

Ted Shifrin

I know the book reasonably well, and know the author extremely well.

anakhro

There is also Yet Another Intro to Analysis

Victor Bryant.

It's pretty intro, though.

Ted Shifrin

Mattuck's book is in the spirit of approximating within $\varepsilon$, which I think is exactly what @Joseph needs.

Mattuck wrote the book because so many students (not headed to PhD's in pure math) at MIT were failing the Rudin real analysis course.

anakhro

Yeah I just like to suggest Bryant's book since I had not heard about it until I was in my masters.

Joseph Dasenbrock

I just picked up the Mattuck book for a good price (used), thanks @TedShifrin

anakhro

12:49 AM

I was convinced that there does not exist a good book on analysis.

Ted Shifrin

Wow, that was fast, @Joseph.

My book is an excellent book for multivariable analysis, @anakhro :)

anakhro

Heh

Joseph Dasenbrock

If it is less than ten bucks and from a good recommendation.. don't need too long to make that decision.

:)

Ted Shifrin

Oh, that is super cheap. I hope the book is usable.

anakhro

I have been writing more lately. I wrote a little diddle on the non-squeezing theorem in symplectic topology aimed at students who only had a first course in linear algebra (which included vector spaces).

I approached it in the linear case so there was no need for Gromov or manifolds in the slightest.

Just a little 11pg pdf.

Ted Shifrin

12:51 AM

Don't do as a grad student things that are better saved until you have tenure :P

Joseph Dasenbrock

yep, yep, I'm sure it is quite a bargain at that price

anakhro

Why is it better to write when you are tenure?

I find writing about things is one of the best ways I know to grok things.

Ted Shifrin

Because now you need to be concentrating on your career, research publications.

anakhro

I am more concerned with pedagogy than research, unfortunately.

Ted Shifrin

I mean ... obviously I have always cared more about teaching and explaining than the average bear.

Well, I cannot fault you for that, but in today's world it may cause you career problems.

anakhro

12:53 AM

Yeah, I am not sure how long I will stick with academia.

Already have too negative of an opinion on academia to cut it.

Also I probably am not cut out for it.

Ted Shifrin

Well, I'm not gonna try to twist your arm. I would not have made it in today's world.

anakhro

Because you were average back then, having Chern as your advisor and all. ;)

Ted Shifrin

No, obviously, I had more than my share of advantages.

anakhro

How did you first get in contact with Chern? Was it by chance?

How did you get into geometry?

Ted Shifrin

But academia has changed to being more research money oriented, far more slave labor being hired rather than hiring tenure-track faculty.

Well, he was one of my qualifying exam examiners (in algebra, ironically). But, actually, we had met when I was 7, and he actually remembered when I told him.

So that was quite a laugh.

anakhro

12:57 AM

At 7? Did you have family who were mathematically inclined?

Ted Shifrin

(I grew up in Berkeley. My dad was a music prof. We rented an apartment in Paris for 3 months when I was 7, as it turns out, from a famous mathematician who was going to spend the year in Berkeley at our house. Chern and his family were moving out of the Paris apartment as we moved in.)

anakhro

Wow, coincidental.

Ted Shifrin

Yeah, pretty funny. So a lot of Berkeley's math department, it turns out, had been in my childhood house.

I truly doubt this is why Chern agreed to be my adviser, however :)

anakhro

Heh. Yeah I wouldn't think so.

Were you always interested in math throughout school?

Semiclassical

@TedShifrin the distinction between "full time" and "tenure-track" is huge

Ted Shifrin

12:59 AM

And he was actually very supportive of my caring about teaching. Of course, he got to let me cover his classes whenever he was traveling.

@Semiclassic: I am fully aware.

Semiclassical

yeah, bit of an obvious statement

or, at least, obvious for anyone in academia.

Ted Shifrin

Well, lots of people in here wouldn't have a clue about it, Semiclassic.

Semiclassical

true

anakhro

Sort of a fear in the back of my mind I won't make it through my Ph.D.

I feel like I have too much to catch up on.

Ted Shifrin

Well, you can't learn/know everything.

anakhro

1:02 AM

I am told "imposter syndrome" is rampant, though. It's hard to convince yourself you are insane, though.

Ted Shifrin

I'm just reading a review of Bryant's book. Looks like it doesn't even get to things like pointwise and uniform convergence. That's a liability.

anakhro

@TedShifrin yes it is extremely introductory.

It's like intermediate between calc and analysis.

It is mostly motivational.

Ted Shifrin

I'll stand by my recommendation.

For applied math, it's really important to understand things like uniform convergence.

anakhro

I usually suggest it to those who are having troubles grasping the point behind analysis, or those who want to "get ahead" but don't want to spoil the class they will be taking in the next year.

It's really good as a supplementary book.

Ted Shifrin

Yeah, my fondest recommendation is Spivak's Calculus, but it's totally serious.

anakhro

1:06 AM

Spivak at least has excellent exercises.

Ted Shifrin

So did you ever put the finishing touch on our discussion of the normal bundle of $K$?

Superb exercises.

Of course, I say that having written hundreds of them :P

anakhro

The ToC of Bryant's book in case it wasn't online

You can tell from this that he doesn't actually cover much in detail.

I haven't had a chance to write out the details, but I think it will iron out. Just need to make time to do it.

Ted Shifrin

OK, I'll shaddup.

anakhro

@TedShifrin it's not because of you talking to me, but I am working on some other more pressing things. Paper work, an assignment, and the finishing edits on my thesis before I submit it for my degree.

Ted Shifrin

Not to mention wasting so much time in here.

Finishing edits in September?

When do you graduate?

anakhro

1:16 AM

I only defended at the end of August. I technically have my degree in the bag already, it's just a matter of doing the edits that the examiners suggested.

Which were not that many...I just have put it off because I started my Ph.D.

Ted Shifrin

Oh wow. Almost congratulations.

Ohhhhh ... you mean MA thesis. I thought you meant the ultimate.

anakhro

No, not Ph.D.

Ted Shifrin

Got it. I'm no longer confuzled.

anakhro

Yeah. But new city, new university. They also even have geometry courses at this university. ;)

My alma mater didn't have any geometers.

Ted Shifrin

Aha. I see. That makes more sense.

anakhro

1:19 AM

Though I am a bit disappointed because the geometry course I have to take for the comprehensive is just G&P's differential topology book. :/

Ted Shifrin

Hmm, what about Riemannian geometry, etc.? Post comprehensive.

Well, good thing we were just discussing G&P.

anakhro

They have a Riemannian geometry course, yeah. And they have tonnes of symplectic geometers. So I am in good company.

Ted Shifrin

Cool.

anakhro

And yeah, it was good reminder of Whitney's proof.

But I am going to have to step it up. Little gaps in my intuition and knowledge where I just fail to see little things like you point out. I feel like they should be more obvious but I am just lost sometimes.

Ted Shifrin

So have you talked to any of the symplectic folks about giving you a problem?

anakhro

1:21 AM

Not yet, I was going to get on that because there are applications due for research proposals for external funding.

Ted Shifrin

Well, in fairness, I taught G&P about 6 times or more in my career.

And graduate manifolds/diff geo another 4 or 5 times.

Mike Miller

Any good questions today? Yesterday?

anakhro

Since I have mostly just focused on 3D contact geometry, I am unsure about what I would actually want to do. But I will definitely ask around.

Ted Shifrin

No, @MikeM, only tomorrow.

anakhro

Hi Mike.

Mike Miller

1:23 AM

OK. See you then.

anakhro

Mike really likes to expedite his internet usage.

I hope he's doing well.

@TedShifrin are Ph.D. problems usually given to you, or are they usually more open ended?

Because my M.Sc. problem was given to me, so I thought maybe the next step up was more independent, but maybe that's not the case. I certainly would have no idea where to start.

Quote Dave

Hey, could someone help me with this problem: math.stackexchange.com/questions/3339422/…

Bob

where does this problem come from?

anakhro

@QuoteDave is there a reason why you require the method to revolve around integration?

Some rhetoric, in an interval around a root, the only defining feature of the integral here is that the integral becomes small. However, the integral being small can happen in other scenarios where a root is not necessary.

So it would have to be more elaborate of a method than naively using integrals to refine to subintervals.

In spirit of Bob's answer, Newton's method uses differentiation (the opposite of integration) to find roots.

Semiclassical

1:39 AM

about the only method I know about where integration is used for root-finding is in the context of complex contour integration and the argument principle

Bob

I am starting to think that by looking at some integrals you can get a good idea where the root(s) are and find them. However, it does not seem like the easy way to do it.

could somebody look at my question: math.stackexchange.com/questions/3357982/…

Semiclassical

@Bob WA gives 7/12 for E(x), so I'd redo that computation

Bob

what is WA?

Semiclassical

note that the antiderivative of xy is xy^2/2, not x^2 y^2/2

wolfram alpha

once you fix that, the integral should work out fine

Bob

@Semiclassical Please post that as an answer so I can give you some points and close the question.

Semiclassical