1
00:00:03,260 --> 00:00:08,750
Hello. Welcome to this big room. I think we're here just today. And then back to the usual room on Tuesday.

2
00:00:09,950 --> 00:00:15,230
Today, I'm going to talk about more mathematics than usual, but it's very applied mathematics.

3
00:00:16,070 --> 00:00:26,870
Fourier Laurent and Chevy chef are three parallel settings, which are the basis of algorithms used in all areas of computational science.

4
00:00:27,350 --> 00:00:32,000
In particular, odes and pdes ultimately rely on these ideas.

5
00:00:32,210 --> 00:00:38,690
And I want to highlight for you the very close relationship between these three in particular.

6
00:00:38,690 --> 00:00:42,169
These are the basis of spectral methods, but all sorts of expansions.

7
00:00:42,170 --> 00:00:48,890
And whenever you try to connect something discrete to something continuous, the chances are you're going to use one of these three settings.

8
00:00:49,400 --> 00:00:55,820
The picture is the unit circle and that's where Z lives.

9
00:00:56,240 --> 00:01:00,470
So you can imagine a variable Z on the unit circle in the complex plane,

10
00:01:00,950 --> 00:01:09,770
and then the diameter of that circle would be the unit interval from -1 to 1, and that's where X lives.

11
00:01:10,970 --> 00:01:14,360
And then theta is the angle to a point Z.

12
00:01:14,930 --> 00:01:24,800
So if that would be a point Z on the unit circle, then that's the corresponding angle theta and this would be the corresponding value of x.

13
00:01:26,360 --> 00:01:30,860
So that picture describes how three variables relate one to another.

14
00:01:31,400 --> 00:01:39,260
You could say, Why do we need all three? Well, the answer is so much mathematics depends on these that all three are truly important.

15
00:01:39,590 --> 00:01:46,249
Theta is Fourier analysis, Z is complex analysis, and X is real analysis.

16
00:01:46,250 --> 00:01:54,950
These are huge, huge territories. Of course, once you see the picture, you immediately see various algebraic relations between the two.

17
00:01:55,130 --> 00:02:01,160
So for example, X is written as one half times Z plus Z inverse.

18
00:02:03,110 --> 00:02:11,780
And we could also say that x is the cosine of I keep writing theta because in my head I usually use theta.

19
00:02:12,020 --> 00:02:22,850
But I think in this lecture I intend to use T instead. So if I ever write theta, it's a mistake I meant to say T of course it's really theta.

20
00:02:23,090 --> 00:02:27,079
But when you're writing codes and so on, theta is an annoying variable.

21
00:02:27,080 --> 00:02:33,139
So we tend to switch to T. So I'm going to spend the first few minutes actually detailing all three of

22
00:02:33,140 --> 00:02:38,300
these contexts in a completely parallel fashion to emphasise the parallels.

23
00:02:38,570 --> 00:02:46,550
So let's begin with Fourier and of course we've all heard of Fourier analysis about 200 years old now.

24
00:02:47,780 --> 00:02:56,450
So the setting here is that we have a periodic function, so not an arbitrary function, a periodic function,

25
00:02:56,870 --> 00:03:08,930
and conventionally on an interval of length to pi, I'll call the function capital F of T and t will be the interval from 0 to 2 pi.

26
00:03:10,070 --> 00:03:14,930
Of course, you could also take minus pi to pi or various other fundamental domains.

27
00:03:16,310 --> 00:03:21,950
Now, whenever we do numerical things, the chances are we're going to sample the function at a set of points.

28
00:03:22,250 --> 00:03:26,690
And of course, for periodic functions, equally spaced points are the obvious choice.

29
00:03:26,960 --> 00:03:30,770
So let's talk about two and plus one.

30
00:03:32,450 --> 00:03:34,970
Equally spaced, equally spaced points.

31
00:03:39,590 --> 00:03:58,190
And I will label them to t sub k and that will be equal to two pi k over two n plus one where K ranges between zero and two n.

32
00:04:02,410 --> 00:04:09,490
So if you draw the picture for that. Notice that because the function is periodic, we only include one end point.

33
00:04:10,450 --> 00:04:14,980
So here we are on our interval going from 0 to 2 pi.

34
00:04:16,900 --> 00:04:22,360
And if we had four points, for example, well, sorry, they're going to be five points.

35
00:04:22,420 --> 00:04:33,880
So if we have five points, for example, they would be here and here and here and here and here, not including there, because that's the same as this.

36
00:04:38,320 --> 00:04:45,760
So of course, for you now with this corresponds to discrete for analysis, which is what an engineer would typically be doing in signal processing.

37
00:04:47,140 --> 00:04:52,840
Now, the basic functions that we expand things in, we loosely speak of signs and cosines,

38
00:04:52,840 --> 00:04:57,790
but it's usually more convenient mathematically to take their complex version.

39
00:04:58,090 --> 00:05:11,230
The complex exponential. So e to the i k t is the complex exponential with wave number k.

40
00:05:11,680 --> 00:05:14,440
And of course, from there you can get the cosine and the sine.

41
00:05:14,440 --> 00:05:20,709
So the cosine would be the real part of this and the sine would be the imaginary part or a better way to say

42
00:05:20,710 --> 00:05:29,410
it is the cosine is this plus E to the minus k over to the sine is this minus C to the minus Oct to II.

43
00:05:31,210 --> 00:05:38,260
Now something that we do explicitly or implicitly all the time is trigonometric interpolation.

44
00:05:40,720 --> 00:05:44,980
And there again, loosely speaking, we're talking about signs and cosines,

45
00:05:45,370 --> 00:05:50,010
but it's often more convenient to write down the formulas in terms of e to the effect.

46
00:05:51,640 --> 00:05:54,850
So a trigonometric interpolate, let's say.

47
00:05:58,260 --> 00:06:07,020
Would be a function I'll call Capital PM and it's a trigonometric polynomial,

48
00:06:07,020 --> 00:06:18,270
which means it's a finite sum from minus m to m of some coefficient c k times e to the i.

49
00:06:18,330 --> 00:06:27,850
K t. So that's some from minus end to end.

50
00:06:27,880 --> 00:06:31,770
Equivalently, you could talk about signs and cosines of Katie.

51
00:06:33,760 --> 00:06:37,570
Now, when people do numerical integration, which we call quadrature,

52
00:06:40,240 --> 00:06:48,100
the obvious idea is to interpolate by trigonometric and then integrate the interpolate, and that's called the trapezoidal root.

53
00:06:49,450 --> 00:06:54,250
It's not obvious that that's the trapezoidal rule, but it is.

54
00:06:54,520 --> 00:07:00,400
So of course we think of the trapezoidal rule as trapezoidal, and then you integrate the trapezoids.

55
00:07:00,610 --> 00:07:06,880
That turns out to be equivalent to interpolating by trigonometric and integrating the trigonometric interpolate.

56
00:07:07,060 --> 00:07:14,470
I won't go through that argument. It's a straightforward one. So the trapezoidal rule effectively integrates the trigonometric and turbulent.

57
00:07:15,220 --> 00:07:25,630
Let's at least make that statement. This is equivalent to integration of P seven.

58
00:07:28,180 --> 00:07:30,480
More precisely, integration of P seven.

59
00:07:30,490 --> 00:07:42,820
Well, there are two N plus one points, so I should say the two and plus one point trapezoidal rule is equivalent to integration of that interpolate.

60
00:07:44,560 --> 00:07:53,050
Now if you want to find roots, let's say root finding, if you want to find the zeros of a trigonometric interpolate.

61
00:07:58,150 --> 00:08:06,700
Well, I'm not going to go into that just now. But effectively what you do is you can compute the eigenvalues of a matrix.

62
00:08:08,200 --> 00:08:15,730
So that turns out to be an effective way to find roots of P sub in its so-called companion matrix.

63
00:08:20,650 --> 00:08:26,500
So root finding and eigenvalue problems are very closely related in numerical practice.

64
00:08:28,720 --> 00:08:33,730
What happens as you take the limit of K going to infinity?

65
00:08:33,730 --> 00:08:46,750
I really should say n going to infinity. The limit as NW Goes to Infinity is a 48 series.

66
00:08:47,140 --> 00:08:52,660
So you have a trigonometric interpolate means a finite degree trigonometric polynomial.

67
00:08:52,870 --> 00:08:56,080
As that degree goes to infinity, you have 48 series.

68
00:08:56,350 --> 00:09:07,569
So in that limit you get this famous idea, assuming F is, let's say Lipschitz Continuous or something,

69
00:09:07,570 --> 00:09:17,290
you can write it as an infinite series where now K goes from minus infinity to infinity of the same thing.

70
00:09:17,330 --> 00:09:27,110
A k. E to the t. What are the 48 coefficients in that series?

71
00:09:32,560 --> 00:09:37,510
So a sub k is equal to one over two pi.

72
00:09:40,840 --> 00:09:48,180
Times the integral from 0 to 2 pi of f little f of t no foreign capital f 50.

73
00:09:49,360 --> 00:09:57,519
Getting my notations confused. Times e to the minus i k.

74
00:09:57,520 --> 00:10:07,760
T. D d t. So 48 theories involves 48 coefficients and then infinite series.

75
00:10:08,030 --> 00:10:10,640
And you all know this from different angles, I'm sure.

76
00:10:12,230 --> 00:10:19,340
Finally, let me mention the basic principle that people use if they're analysing the convergence of the theories.

77
00:10:19,580 --> 00:10:23,720
Assuming that your function is analytic so it has convergent Taylor theories.

78
00:10:24,290 --> 00:10:30,080
The fundamental hypothesis is if you have an analytic function on the interval.

79
00:10:33,940 --> 00:10:38,710
Then it can be analytically continued into the complex plane into some strip.

80
00:10:43,070 --> 00:10:45,650
And I will say a little more about that in a moment.

81
00:10:46,850 --> 00:10:59,660
And that implies that the 48 coefficients decrease geometrically, so they are O of C to the minus absolute value of K for something bigger than one.

82
00:11:02,150 --> 00:11:07,220
So any time you have an analytic function, it's for you. Coefficients decrease at a geometric rate.

83
00:11:07,520 --> 00:11:11,960
So that means its trigonometric and turbulence converge at a geometric rate.

84
00:11:13,400 --> 00:11:17,720
So there on one screen you have a summary of all of 44 theories.

85
00:11:19,280 --> 00:11:21,380
And let me give you a reference.

86
00:11:22,130 --> 00:11:31,100
Of course, there are a thousand work from this, but from a numerical point of view, my favourite references as usual something by myself.

87
00:11:32,900 --> 00:11:45,260
So let me recommend a paper by right and javaid and our to Monto Nellie.

88
00:11:48,430 --> 00:11:54,250
And myself. And that's it's called extension of fun to periodic functions.

89
00:11:54,460 --> 00:12:02,030
It's in the Siam Journal of Numerical Analysis, and it's coming out this year.

90
00:12:02,050 --> 00:12:03,790
You can find it on my web page.

91
00:12:07,840 --> 00:12:14,920
And in particular, we discuss all this stuff in a way that fits very cleanly with the other cases of Laurent and Cherif.

92
00:12:16,900 --> 00:12:25,270
So now let's switch to the Laurent setting for analysis is famous to engineers and real mathematicians.

93
00:12:26,350 --> 00:12:32,650
The Laurent setting is famous to complex mathematicians. This is what you do when you're working in the complex plane.

94
00:12:35,020 --> 00:12:42,520
And incidentally, my opinion is that mathematically, in some sense, the Laurent case is the fundamental ones.

95
00:12:42,700 --> 00:12:50,440
Of course, they're all more or less equivalent. But this conceptually, I think, is the basis from which it's easiest to derive the others.

96
00:12:51,940 --> 00:13:02,139
So now we're going to suppose that we have a function which I will call a fancy F,

97
00:13:02,140 --> 00:13:07,810
so I'm going to call it like that F of Z and Z is in the unit circle.

98
00:13:13,850 --> 00:13:18,920
Now, if you have a function defined on the unit circle, then sort of by definition it's periodic in some sense.

99
00:13:19,100 --> 00:13:22,640
So I don't have to say it's periodic that goes with the territory.

100
00:13:23,990 --> 00:13:30,860
And then in analogy to the equally spaced points, we now have two and plus one roots of unity.

101
00:13:33,250 --> 00:13:38,380
So these are the two and plus first roots of the number one.

102
00:13:38,920 --> 00:13:51,640
And we could write those as z sub k equals e to the i times t some k for k between zero and two m.

103
00:13:54,990 --> 00:14:03,690
Now corresponding to the complex exponential, you have simply Z to the K, which we could call a mano z to the K.

104
00:14:05,490 --> 00:14:09,360
So you begin to see why somehow this is a more fundamental territory.

105
00:14:09,600 --> 00:14:18,450
Z to the K is marginally simpler than E to the T corresponding to a trigonometric and turbulent.

106
00:14:18,690 --> 00:14:22,170
You have what people would call a laurent polynomial interpolate.

107
00:14:31,800 --> 00:14:36,030
And well, you should be able to write down the formula just by this close analogy.

108
00:14:36,270 --> 00:14:48,059
So a laurent polynomial and turbulent I would write as fancy p of z is the sum from minus m

109
00:14:48,060 --> 00:14:57,480
to end of c sub k z to the k so given and plus one roots of two m plus one roots of unity.

110
00:14:57,720 --> 00:15:05,400
There is a unique and turbulent of that form. It's a polynomial, except it has some negative powers as well as some positive powers.

111
00:15:05,670 --> 00:15:16,500
So that's what the word Lawrence polynomial means. Negative as well as positive powers if you want to do quadrature root numerical integration.

112
00:15:19,860 --> 00:15:26,190
Then again, the obvious formula is the appropriately scaled trapezoidal rule,

113
00:15:27,600 --> 00:15:33,150
where basically you add up the samples at Roots of Unity and multiply by the obvious factor.

114
00:15:33,690 --> 00:15:38,070
And that again is equivalent to integrating the interpolate.

115
00:15:47,730 --> 00:15:50,790
And then what comes next in our list is root finding.

116
00:15:52,080 --> 00:15:55,710
So that's the same again, I'm not spelling out the matrix involved,

117
00:15:56,010 --> 00:16:03,120
but if you want to do route finding and for functions that are that sort of live on the unit circle,

118
00:16:04,380 --> 00:16:08,400
then the way to do it is to set up a eigenvalue problem.

119
00:16:08,400 --> 00:16:12,660
You find the eigenvalues of a companion matrix.

120
00:16:15,990 --> 00:16:26,430
A companion matrix is a matrix that's mostly zero except on two diagonals and one row and it contains the coefficient c some k.

121
00:16:31,180 --> 00:16:39,670
What about the limit? Well, as Kate then goes to infinity, you have a long, long series.

122
00:16:41,890 --> 00:16:50,710
So you all know. Taylor Theories. Lauren Theories is the same except with negative as well as positive powers of Z.

123
00:16:51,670 --> 00:17:08,340
So a Lauren series. Means that you have the sum from minus infinity to infinity of a sub k z to the k.

124
00:17:10,620 --> 00:17:16,269
What are the law on coefficients? Well,

125
00:17:16,270 --> 00:17:25,479
it's the same formula as above for 48 coefficients transplanted from the TI variable to the Z variable and you get

126
00:17:25,480 --> 00:17:39,700
a sub k equals one over two pi times the integral over the circle of fancy f of z time z to the minus k minus one.

127
00:17:41,380 --> 00:17:51,360
And that's an integral over the unit circle. So if you know your complex variables, that's a Kochi integral.

128
00:17:51,660 --> 00:17:55,800
So Kochi integrals are the same as for a integrals.

129
00:17:56,580 --> 00:18:01,290
Once you know this stuff, you begin to lose the distinction between the different territories.

130
00:18:02,940 --> 00:18:07,800
Now, what happens if you have an analytic function?

131
00:18:10,080 --> 00:18:14,310
Well, now the appropriate region of an electricity is an annulus.

132
00:18:14,520 --> 00:18:18,640
So let's see on the interval from 0 to 2 pi.

133
00:18:18,960 --> 00:18:23,760
If you have an analytic function, then it's also analytic in some strip in the complex plan.

134
00:18:24,660 --> 00:18:33,000
Well, on the unit circle, if you have an analytic function on the unit circle, then it's also analytic in some annulus.

135
00:18:35,510 --> 00:18:44,720
Surrounding the unit circle, and that would be equivalent to this strip under the E to the i z map, e to the t map.

136
00:18:45,260 --> 00:18:49,580
So if F is analytic in an unknown annulus.

137
00:18:56,630 --> 00:19:09,950
Then that implies that the coefficients a sub k decrease geometric same as above o of C to the minus k for C greater than one.

138
00:19:12,440 --> 00:19:15,950
These two settings are not merely analogous, they're identical.

139
00:19:15,950 --> 00:19:24,350
They really are the same. Everything is the same. We've just changed variables between Z and now the reference on that.

140
00:19:31,710 --> 00:19:36,630
This is harder to find numerical references on a lot of people do numerical Fourier analysis.

141
00:19:36,900 --> 00:19:40,860
Not so many people do numerical lorente analysis, although of course there are some.

142
00:19:41,520 --> 00:19:48,180
And the paper I would suggest you look at is by my student, Anthony Austin and Peter Craven.

143
00:19:48,210 --> 00:19:52,030
Yeah. And myself.

144
00:19:52,540 --> 00:19:59,950
And that's in Siam Journal of Numerical Analysis in 2014.

145
00:20:08,200 --> 00:20:13,900
And that's called numerical algorithms based on analytic function values at roots of Unity.

146
00:20:16,210 --> 00:20:24,310
So as I say, these two are identical. The championship chef setting is not quite identical because it has a further symmetry assumption.

147
00:20:25,420 --> 00:20:30,340
And the picture on that is in these settings I can have an arbitrary function on the circle.

148
00:20:31,120 --> 00:20:37,900
But when I predict to the to the interval, I'm going to require that my function take the same value there as there.

149
00:20:38,320 --> 00:20:43,870
See, here's another value, the inverse. They both project to the same value of X.

150
00:20:44,140 --> 00:20:47,830
And in chubby chef analysis, I want a well-defined function here.

151
00:20:48,070 --> 00:20:51,490
So that entails a symmetry assumption for Z or T.

152
00:20:53,830 --> 00:21:05,450
So here we go. Fauria and TV chef were very famous mathematicians.

153
00:21:05,460 --> 00:21:09,560
I actually don't know anything about. Laurent is not as big a name, I guess.

154
00:21:11,780 --> 00:21:15,500
Okay, so now we suppose we have a function. Little F, a little X.

155
00:21:21,580 --> 00:21:24,760
And X is in the unit interval.

156
00:21:27,750 --> 00:21:31,559
And of course, we don't assume it's periodic. Now,

157
00:21:31,560 --> 00:21:37,590
the analogy to equally spaced points or roots of unity is what you get when you

158
00:21:37,590 --> 00:21:41,400
project those equally spaced points or routes of unity down to the interval.

159
00:21:41,670 --> 00:21:49,860
And those are cheryshev points, and now they're only in plus one of them, not two and plus one of them because pairs project to the same thing.

160
00:21:49,920 --> 00:21:52,860
So we've end plus one chubby chef points.

161
00:21:57,220 --> 00:22:11,290
And those are defined by x sub k equals the cosine of k pi over n zero less than or equal to k less than or equal to n.

162
00:22:13,880 --> 00:22:18,320
Analogous to the binomial or the complex exponential.

163
00:22:18,500 --> 00:22:20,930
We have the Chevy chef polynomial.

164
00:22:25,770 --> 00:22:39,690
And the chubby chef polynomial is written with a capital t t sub k of x and that is one half times z to the k plus z to the minus k.

165
00:22:41,550 --> 00:22:50,460
Another way to say it is, it's the cosine of k times, the arc cosine, the inverse cosine of x.

166
00:22:52,950 --> 00:23:02,280
So it oscillates like a cosine a tabish polynomial on the unit interval oscillates like a cosine,

167
00:23:03,750 --> 00:23:11,940
but it's and then it gets huge outside the interval for a polynomial in turbulent.

168
00:23:20,180 --> 00:23:33,710
Can be written as little pe of nn seven of x is equal to the sum, and now we have a sum from zero to n of c sub k.

169
00:23:34,610 --> 00:23:48,280
T k of x. If you do Quadrature Well, of course you know the natural method is to integrate the interpolate.

170
00:23:48,290 --> 00:23:51,499
I've got some data at VHF points. I integrate that interpolate.

171
00:23:51,500 --> 00:23:58,190
That's my approximate integral. All we need is a name for that algorithm and it's called Crenshaw.

172
00:23:58,190 --> 00:24:10,910
Curtis. So Crenshaw. Curtis Quadrature is the name we give to integrating the Chevy chef interpolate.

173
00:24:23,540 --> 00:24:31,839
Root finding. Well, it turns out now that instead of a big diagonal matrix eigenvalue problem,

174
00:24:31,840 --> 00:24:38,200
you essentially have a tri diagonal matrix eigenvalue problem and the matrix is called a colleague matrix.

175
00:24:38,590 --> 00:24:44,980
So you do this by computing the eigenvalues of a colleague matrix.

176
00:24:48,160 --> 00:24:52,570
These names were given at the height of the Cold War when people thought it was funny to talk about

177
00:24:53,200 --> 00:25:01,960
companion matrices and comrade matrices and colleague matrices in the limit as then goes to infinity.

178
00:25:04,030 --> 00:25:06,100
You, of course, have a Chubby Chef series.

179
00:25:07,570 --> 00:25:23,510
So a Chubby Chef series represents a function F of X as an infinite series from zero to infinity of a sum k.

180
00:25:24,090 --> 00:25:29,930
K of x. I haven't mentioned.

181
00:25:29,930 --> 00:25:35,240
Why do I have C K's and AK? So the interpreter and I'm using C K's, the series I'm using.

182
00:25:35,720 --> 00:25:41,870
Well, these are different numbers. As N goes to infinity, those six will approach these.

183
00:25:42,230 --> 00:25:46,220
But for any finite end, you have coefficients here which will be different from that.

184
00:25:49,490 --> 00:26:01,719
What are those cheryshev coefficients? Well, it's the same as the 48 or Lawrence thing with the change of variables, and when you do your sums,

185
00:26:01,720 --> 00:26:09,430
it turns out it's a sub k equals two over pi times the integral from -1 to 1

186
00:26:11,290 --> 00:26:19,540
of f of x t k of x divided by the square root of one minus x squared the x.

187
00:26:24,990 --> 00:26:26,460
Finally, what about analytics?

188
00:26:26,790 --> 00:26:35,939
Well, for periodic functions, if you're analytic on an interval that implies you're analytic in some strip for functions on the unit circle,

189
00:26:35,940 --> 00:26:38,429
if you're analytic on the circle, that implies you're analytic.

190
00:26:38,430 --> 00:26:46,200
In some analysts in the Chevy chef case, where, again, we're analytic on an interval but no longer periodic,

191
00:26:46,500 --> 00:26:53,610
it turns out that the right domain is an ellipse with four at minus one and one.

192
00:26:53,880 --> 00:27:02,880
And that ellipse is what you get when you take a circle and transplant it by this map.

193
00:27:06,340 --> 00:27:11,110
So if I take a circle here in the Z plan and apply this tarkowski map to it,

194
00:27:11,110 --> 00:27:17,229
I get in the lips in the X plane and any function analytic on the unit interval will

195
00:27:17,230 --> 00:27:23,560
be analytic in some ellipse corresponding to some sufficiently narrow annulus.

196
00:27:25,660 --> 00:27:30,220
So that's the analytic city setting. If F is analytic in an ellipse.

197
00:27:36,170 --> 00:27:43,250
With focus at minus one and one. Then that implies that the coefficients decrease geometrically.

198
00:27:53,080 --> 00:27:56,440
Now. It's a little tedious for me to write out all this stuff for 20 minutes.

199
00:27:56,450 --> 00:28:03,640
But let me tell you, the amount of practical mathematics codified in those three screens is just extraordinary.

200
00:28:03,700 --> 00:28:11,770
Here you have the basis of a large part of what people really do on computers, especially when they want high accurate solutions.

201
00:28:12,670 --> 00:28:18,310
The reference on this is my book Approximation Theory and Approximation Practice.

202
00:28:19,510 --> 00:28:24,190
At top, I called it approximation theory and approximation practice and I'll pass that around.

203
00:28:24,640 --> 00:28:28,660
So it's the book with the horse on the cover. This is from Port Meadow, the picture of the horse.

204
00:28:34,200 --> 00:28:37,650
Okay. Let me show a little bit of that stuff on the computer.

205
00:28:43,670 --> 00:28:51,830
So we're now working with the code called M 52, which is going to show a little of Fourier series and championship series in seven for convenience.

206
00:28:52,100 --> 00:28:56,390
So suppose I say Capital F equals ten fun.

207
00:28:57,320 --> 00:29:02,540
And then the function I will choose will be cosine of e to the sign of t,

208
00:29:03,590 --> 00:29:12,840
and that's a periodic function for well I put it on minus pi pi in the handout, but it might as well be two pi I think.

209
00:29:12,840 --> 00:29:20,990
I hope that works. And now in check from the way you do, you signal that you're dealing with something periodic as you type trig.

210
00:29:22,730 --> 00:29:27,680
So there we're constructing a for a series of four and turbulent to that function.

211
00:29:28,040 --> 00:29:37,520
And let's plot it I'll say subplot 1 to 1 plot F and I'll plot it in that mode.

212
00:29:44,060 --> 00:29:54,980
Okay. So there you have a periodic, not especially exciting function.

213
00:29:55,160 --> 00:30:02,750
Now suppose I say subplot one, two, two and I plot the Fourier coefficients of F.

214
00:30:03,260 --> 00:30:06,980
So there you are. And you see.

215
00:30:09,570 --> 00:30:14,399
Zero is the zero wave number, the constant term and you have minus KS and plus K.

216
00:30:14,400 --> 00:30:17,760
So you always have the symmetry when you write 48 coefficients.

217
00:30:18,060 --> 00:30:26,129
So there you see the 48 coefficients of that function on an absolute on a large scale and we're plotting their absolute value in seven.

218
00:30:26,130 --> 00:30:31,200
It always goes down to machine precision and then stops. Of course, mathematically it would keep going forever.

219
00:30:31,710 --> 00:30:35,610
It's an analytic function which implies it's analytic in some strip,

220
00:30:35,820 --> 00:30:44,160
which implies that the 48 coefficients decreased geometrically and sure enough, you see a geometric decrease of the Fourier coefficients.

221
00:30:46,950 --> 00:30:56,640
We have these gallery things built in, so if I say help Cheb gallerie trig, you'll see a collection.

222
00:30:57,000 --> 00:31:01,110
Things are going slowly of all sorts of built in functions you can play with,

223
00:31:01,890 --> 00:31:05,460
and we're now going to play with two of them, the AMP signal and the FM signal.

224
00:31:07,260 --> 00:31:14,280
So suppose I say F equals Chaddock Gallery Trig of F.M. signal.

225
00:31:16,200 --> 00:31:20,579
That is a preloaded Chevy fun. I'll now say subplot.

226
00:31:20,580 --> 00:31:24,000
One, two, two, one. And I'll plotted.

227
00:31:27,510 --> 00:31:31,730
And that is what we see. So it's an FM signal.

228
00:31:31,740 --> 00:31:37,380
You can sort of see that the amplitude is constant, but the frequency is being modulated.

229
00:31:39,060 --> 00:31:48,120
Let's look at it's Fourier transform. So I'll say subplot to two, three plot coefficients of S.

230
00:31:49,290 --> 00:31:52,769
So there you have a lot of coefficients.

231
00:31:52,770 --> 00:31:56,760
It's a smooth signal. So they're decaying nicely down to machine precision.

232
00:31:57,660 --> 00:32:10,890
Now let's compare that with an AM signal. So I'll now say F equals cab, dot, gallerie trig and signal and I'll say subplot.

233
00:32:11,970 --> 00:32:20,980
Two, two, two. So there you have an AM signal where the carrier frequency is constant,

234
00:32:20,980 --> 00:32:26,020
but the amplitude is being modulated and the you should all think in your head.

235
00:32:26,030 --> 00:32:31,840
Now what will its four year transform look like? So subplot 2 to 4.

236
00:32:35,140 --> 00:32:44,410
What you see are peaks at the carrier frequency so that the energy is all near plus or -50 because that's the carrier frequency.

237
00:32:44,410 --> 00:32:48,820
So to an engineer, there's a lot of interesting stuff there.

238
00:32:49,450 --> 00:32:53,290
Of course, I'm of a generation when these analogue signals were very important.

239
00:32:53,290 --> 00:32:57,550
Nowadays everything is so digitised. Who knows how your radio works nowadays?

240
00:32:58,930 --> 00:33:06,010
Finally, let's do a Chevy chaff analogue. So I'll now say F little s equals headphone of the same thing.

241
00:33:06,340 --> 00:33:14,950
So that was cosine of E to the sign of x. And of course by default it's the unit interval minus one one.

242
00:33:15,910 --> 00:33:20,050
If I say subplot one, two, one.

243
00:33:25,310 --> 00:33:30,410
And plot a little less. You see that?

244
00:33:32,120 --> 00:33:35,870
I've made a mistake. I meant to put it on a.

245
00:33:36,650 --> 00:33:45,900
Sorry. I meant to put it on 0 to 2 pi. Yeah.

246
00:33:45,990 --> 00:33:52,940
So there we have the same function, but now it's represented by a Chevy truck series instead of a 48 series.

247
00:33:53,840 --> 00:33:57,650
And if I now look at its coefficients, so that would be 1 to 2.

248
00:33:59,570 --> 00:34:02,930
These will now be Chevy chef rather than 48 coefficients.

249
00:34:03,140 --> 00:34:07,520
So no longer do we have a zero wave number and then plus and minus we have a zero wave

250
00:34:07,520 --> 00:34:12,889
number and then just higher and higher degree Chevy chef polynomials again analytically.

251
00:34:12,890 --> 00:34:21,620
So geometric convergent, that function is analytic in a ellipse and therefore you have geometric convergence of the Chevy Chef series.

252
00:34:24,560 --> 00:34:29,150
So there's a lot of beautiful mathematics here, which I've been very focussed on in recent years.

253
00:34:29,540 --> 00:34:32,030
Now let me tell you some more of it.

254
00:34:40,170 --> 00:34:48,790
So we're now going to focus on TV chef for the rest of today's lecture and tell you a word about Chevy Chef series and interpret.

255
00:34:57,100 --> 00:35:08,290
Well, the most basic word to say. Is that mathematically cheryshev is essentially the same as for gay.

256
00:35:08,320 --> 00:35:11,380
There's gifts that extra symmetry condition. Otherwise it's the same.

257
00:35:11,920 --> 00:35:15,760
But sociologically it's very different in the 48 territory.

258
00:35:18,470 --> 00:35:24,350
Everyone on earth, given a periodic function and sampling it would of course use equally spaced points.

259
00:35:24,560 --> 00:35:31,700
This is exactly what everyone would obviously do. Nobody would dream of any other method of representing a periodic function.

260
00:35:32,060 --> 00:35:41,750
But in the championship territory with non periodic functions, what people dream of is numerically exponentially bad.

261
00:35:41,990 --> 00:35:45,590
So of course most people don't use championship polynomials.

262
00:35:45,590 --> 00:35:50,630
They would just use mono x to the one, x to the two. Those are exponentially ill conditioned.

263
00:35:50,960 --> 00:35:56,990
So numerical methods that work with polynomials in the Multnomah or basis are catastrophically bad.

264
00:35:57,500 --> 00:36:01,490
If you use TV Chef, everything is just like Fourier analysis and it all works.

265
00:36:02,540 --> 00:36:11,270
So if you're ever working with polynomials on an interval you must use be here unless the degree of your polynomial is like three or four.

266
00:36:12,860 --> 00:36:18,290
Okay, so I've told you what the Chevy chef polynomials are and the general formula,

267
00:36:18,290 --> 00:36:26,060
for example, is t k of x equals the cosine of k times the cosine inverse of x.

268
00:36:26,780 --> 00:36:43,490
So for example, t zero is one and t one is x and T2 is two x squared minus one and t three is four x cubed minus three x and so on.

269
00:36:44,360 --> 00:36:51,440
And as I mentioned, they actually oscillate in the unit interval and grow a great deal outside the unit.

270
00:36:53,480 --> 00:37:05,270
So those are Tabish polynomials. And now as time permits, I want to tell you some theorems about representing functions by Chevy Chef series.

271
00:37:08,920 --> 00:37:22,920
So they were in one. If F is Lipschitz Continuous, and I'm sure many of you know what that means, and maybe some of you don't.

272
00:37:23,670 --> 00:37:29,970
You can look it up. It's a little stronger than continuity. It means that basically the slopes are all bounded by a constant.

273
00:37:31,740 --> 00:37:38,610
Then the TV Chef series, which I've already defined for you, convergence.

274
00:37:39,540 --> 00:37:44,520
And moreover, it converges absolutely and uniformly.

275
00:37:44,820 --> 00:37:51,110
These are technical terms. Absolutely means it works.

276
00:37:51,120 --> 00:38:01,500
Even if you put absolute values on each term, uniformly means that it works even if that the Epsilon two deltas are uniform across the interval.

277
00:38:02,280 --> 00:38:08,429
The consequences of these are that you can work with to have theories however you want, you can reorder them.

278
00:38:08,430 --> 00:38:13,319
That doesn't mess up the convergence. You can differentiate them. You can do all sorts of things.

279
00:38:13,320 --> 00:38:20,420
Turn by turn. Of course, this is an analogue of a theorem in four year analysis,

280
00:38:20,660 --> 00:38:27,290
which says that if Capital F is Lipschitz Continuous, then the Fourier series converges absolutely and uniformly.

281
00:38:33,890 --> 00:38:41,030
Ferrum, too, has to do with the geometric rate of convergence.

282
00:38:43,520 --> 00:38:55,130
Theorem two is that if F is analytic and bounded by some number in absolute value, call it M.

283
00:38:58,770 --> 00:39:03,750
In the Berenstein Rollups. And I'll say in a moment exactly what I mean by that.

284
00:39:07,350 --> 00:39:10,830
Then the Chevy Chase coefficient decreased and here's the rate.

285
00:39:10,860 --> 00:39:16,200
They're bounded by two and row to the minus k.

286
00:39:18,120 --> 00:39:24,570
So I mentioned earlier that analytic functions have geometrically decreasing cheryshev coefficients.

287
00:39:24,750 --> 00:39:29,700
Well, here's a theorem to tell you how fast that goes. And now let me tell you what row is.

288
00:39:36,480 --> 00:39:40,350
There's a unit circle of radius one out here.

289
00:39:40,350 --> 00:39:44,310
I've drawn a circle of radius row bigger than one.

290
00:39:45,930 --> 00:39:52,020
So if you take a circle of radius, row bigger than one and map it by this Tarkovsky map, it turns into an ellipse.

291
00:39:52,830 --> 00:40:05,650
And that's called the Berenstein Rowan. Berenstein worked on this stuff in 1912.

292
00:40:13,350 --> 00:40:22,110
Now from that found on the size of the Chevy chef coefficient, which of course is analogous to a bound on 48 coefficients,

293
00:40:23,250 --> 00:40:26,880
you can reach conclusions about the accuracy of approximations.

294
00:40:29,560 --> 00:40:40,970
So Theorem three. Says if f sub n is the truncated series.

295
00:40:42,020 --> 00:40:45,230
So we take the Chevy Shuffle series, but we truncated a term n.

296
00:40:49,560 --> 00:40:54,240
Then the error between F and it's truncated series.

297
00:40:55,890 --> 00:40:59,640
And when I said the error, I mean the maximum error on the unit interval.

298
00:40:59,820 --> 00:41:13,110
We could call that the infinity normal error. The maximum error on the unit interval is bounded by two and row to the minus n over row minus one.

299
00:41:15,610 --> 00:41:20,320
You get that just by adding up all the terms you've truncated away.

300
00:41:20,740 --> 00:41:28,520
So if you take an infinite TV Chef series with coefficients decreasing at that rate and you chop it at some point, how big is the tail?

301
00:41:28,540 --> 00:41:31,930
Well, you add up all of these bounds and this is what you get.

302
00:41:35,120 --> 00:41:41,900
So Chubby Chef series four analytic functions converge at a geometric rate if you truncate them.

303
00:41:45,990 --> 00:41:56,120
Theorem for. Concerns and turbulence as opposed to truncation.

304
00:41:56,120 --> 00:42:00,860
So suppose ppm is what we've already talked about the Chevy chef in turbulent.

305
00:42:05,260 --> 00:42:16,440
As opposed to the truncated series. Well, it turns out you get the same bound except twice as with that factor too out front.

306
00:42:16,440 --> 00:42:28,320
So f minus pm, the worst error on the unit interval is no greater than four m relative to minus n over rho minus one.

307
00:42:31,790 --> 00:42:38,570
So that tells you how big the error can be when you do interpolation and cheryshev points.

308
00:42:38,870 --> 00:42:44,030
If you have an analytic function, you're guaranteed that the entire plinth converge geometrically.

309
00:42:49,330 --> 00:42:52,960
So the final thing I want to mention is the subject of the other handout.

310
00:42:53,830 --> 00:42:57,069
So take a look here. This paper by seltzer.

311
00:42:57,070 --> 00:43:00,910
In 1972, Lagrangian interpolation at the Archbishop Points.

312
00:43:02,500 --> 00:43:14,470
Seltzer pointed out that there's a beautiful, stable way to compute these polynomial, and it's called the Barry centric formula.

313
00:43:14,710 --> 00:43:21,490
And here he set that forth. Somebody should have done this 50 years ago, but nobody did it with seltzer in 1972.

314
00:43:21,790 --> 00:43:31,510
He showed that you really can compute these things even if n is in the millions and this is called the barrier centric interpolation formula.

315
00:43:32,380 --> 00:43:42,940
Let me write it down. So Theorem five says.

316
00:43:46,860 --> 00:43:57,120
That piece of em that's the interpolate and cheryshev points is equal to a quotient of one thing by another thing.

317
00:43:58,350 --> 00:44:09,060
Each of those is a sum from zero to n. There's a prime there, which I'll explain in a second.

318
00:44:09,990 --> 00:44:18,810
You have in the numerator minus one to the J times f at the j championship point

319
00:44:19,110 --> 00:44:26,970
divided by x minus x j and in the denominator you have minus one to the j.

320
00:44:27,930 --> 00:44:39,040
Divided by x. Minus x. J. This is called the virus centric interpolation formula.

321
00:44:45,620 --> 00:44:51,890
So it's a mathematical formula which is kind of a curious one,

322
00:44:52,280 --> 00:44:59,210
because what you seem to see here is a function with a lot of polls in the numerator and a function with a lot of polls in the denominator.

323
00:44:59,600 --> 00:45:02,990
And yet the end result is a polynomial. Well, that is true.

324
00:45:03,470 --> 00:45:06,470
It's a mathematical fact that it's equal to a polynomial.

325
00:45:06,710 --> 00:45:11,420
Moreover, it is provably numerically stable.

326
00:45:12,050 --> 00:45:17,820
So this formula really does work. And this is what Chevy Fun did for many, many years.

327
00:45:17,840 --> 00:45:21,230
This is the formula that led to the creation of Chevy Fun, actually.

328
00:45:23,030 --> 00:45:35,240
I have to explain what the Prime means. So when I say the sum of something from K equals zero to m prime,

329
00:45:36,230 --> 00:45:44,690
I mean that we take one half times D, not plus one half times DRM and then all the others.

330
00:45:47,530 --> 00:45:52,860
Like that. So the prime means you multiply the terms by one half.

331
00:45:53,430 --> 00:46:05,000
Prime. Prime. So this amazing formula enables you to interpolate by polynomials in TV, Chef points.

332
00:46:05,390 --> 00:46:09,010
To any degree, it's as stable as Fourier analysis.

333
00:46:09,020 --> 00:46:17,540
It's just the same, really. So anything you can do with a discrete 48 transform, you can also do with Chevy Chef points for non periodic functions.

334
00:46:18,260 --> 00:46:21,649
If you look at this a little more, the more you look at it, the more puzzling it seems.

335
00:46:21,650 --> 00:46:25,460
Because what happens when x is equal to x j?

336
00:46:25,910 --> 00:46:33,770
Well, in that case, you bypass the formula and you say part of x j is equal to the data value f of x j.

337
00:46:34,040 --> 00:46:36,160
But what if x is very close to x j.

338
00:46:36,590 --> 00:46:42,950
We're going to have something huge here with tremendous cancellation errors and something huge here with tremendous cancellation errors.

339
00:46:43,280 --> 00:46:48,740
But it turns out the cancellation errors cancel and it really is provably numerically stable.

340
00:46:49,100 --> 00:46:56,990
So this is both fast. If there were then operations not in squared and numerically stable.

341
00:46:57,200 --> 00:47:03,820
So this really is the right way to interpolate. And I just want to finish by showing you that.

342
00:47:03,860 --> 00:47:09,320
Oh, so the back page of the handout is a paper by myself and Jean-Paul Baru.

343
00:47:10,040 --> 00:47:17,000
Baru is a professor at the University of Fribourg in Switzerland, and he is a great authority on the various centric methods.

344
00:47:18,680 --> 00:47:22,460
So if you want to read about it, maybe our survey paper is a good place to do that.

345
00:47:23,390 --> 00:47:28,610
So let me finish with this final demonstration showing Ben Stein ellipses.

346
00:47:32,430 --> 00:47:38,850
So this one's called. I'm 53. Ben Stein So what I'll do is I'll set F equal to a famous function.

347
00:47:38,850 --> 00:47:47,760
I run a function it's called. So it's one divided by one plus 25 x squared.

348
00:47:52,390 --> 00:48:01,510
And now I'll say a subplot. One, three, one plot f y lim minus one, two.

349
00:48:04,930 --> 00:48:13,270
So there you have the wrong assumption. It's analytic, but it's troublesome for certain methods of approximation.

350
00:48:14,920 --> 00:48:24,370
Let's look at its TV chef coefficient. So I'll say subplot 132 plot coefficients of f line width.

351
00:48:26,840 --> 00:48:36,340
Point six. Really? Oh. So there you see what looks like a solid triangle.

352
00:48:38,440 --> 00:48:43,160
Actually, all the odd coefficients have zero and the even coefficients are non-zero.

353
00:48:43,180 --> 00:48:49,960
So we're getting this kind of effect. But you see the totally clean geometric rate of convergence of the cheryshev coefficients.

354
00:48:51,890 --> 00:48:57,140
Finally, the last command will show the Bernstein Ellipse.

355
00:48:58,280 --> 00:49:02,990
So suppose I now say subplot. One, three, three.

356
00:49:04,100 --> 00:49:07,190
Plot, region. Plot.

357
00:49:07,190 --> 00:49:15,820
Region of death plots. The Bernstein Ellipse associated with this function axis equal grid arm.

358
00:49:17,520 --> 00:49:25,579
So well, there you see the unit interval and then that ellipse is the region of an electricity of this function

359
00:49:25,580 --> 00:49:32,690
because the wrong function has poles at plus or minus I over five and that ellipse is bounded by that.

360
00:49:32,930 --> 00:49:36,110
Let's now finally confirm the rate of convergence.

361
00:49:36,620 --> 00:49:39,889
It turns out. Oh, well, let's let's plot those polls. I say hold on.

362
00:49:39,890 --> 00:49:43,459
And I'll say plot -0.2.

363
00:49:43,460 --> 00:49:47,950
I'd point to I as red dots. Oops.

364
00:49:48,490 --> 00:49:59,729
What did I do? So you can see the poles of that function are right there on the very fine lips they bound the region of analytically.

365
00:49:59,730 --> 00:50:03,600
So that's the largest ellipse inside which this function is analytic.

366
00:50:03,900 --> 00:50:07,980
Finally, let's compute the Bernstein value of row.

367
00:50:08,010 --> 00:50:12,150
It turns out it's one plus the square root of 26 divided by five.

368
00:50:13,560 --> 00:50:17,880
And let's see how our prediction matches the data.

369
00:50:18,690 --> 00:50:31,950
So I'll go back to the middle plot. And now I'll say plot k against Ro to the minus K as a dashed red line.

370
00:50:32,970 --> 00:50:38,760
So what this is going to do is I've figured out the value of row corresponding to that ellipse of analytically.

371
00:50:39,030 --> 00:50:45,240
And you remember the prediction is the coefficients decrease geometrically and the constant involved is a row.

372
00:50:46,650 --> 00:50:50,910
So there you can see the prediction is beautifully matched by the.