is called the Fourier series of , where 为 are the Fourier coefficients.

Similarly, in , is an orthonormal [...]]]> Denote ，then is an orthonormal basis for . Thus all the functions in can be approximated by this basis in sense. This basis is always called the Fourier basis. For a function ,

is called the Fourier series of , where 为 are the Fourier coefficients.

Similarly, in , is an orthonormal basis for . Therefore any function in can be approximated by this basis in the sense. This set of basis is called the polynomial basis. For a function ,

is called the polynomial series or power series of , where are the polynomial coefficients of .

In the first example, the period is set to . Actually any finite period will work. Consider a function defined on , we can extend it to become a function in . Similarly, in the second example, the is chosen just for simplicity. Any function in has a polynomial series. To sum up, all functions defined on a closed interval can be approximated by the two set of basis(Fourier & polynomial) in sense.

Because of their nice properties, such as infinitely times differentiable, we always use the two basis to approximate a given function in real-world applications. Of course we cannot sum up to infinity. The approximation is done by finite summation of the terms in their Fourier or polynomial series. In this process, people have discovered two interesting phenomenon, namely the Gibbs phenomenon and the Runge phenomenon.

Gibbs phenomenon shows up when one tries to approximate a function that has a point of discontinuity of the first kind. Consider a function f that is constant 0 on and value 1 on . Its Fourier approximation is plotted below.

At the point of discontinuity, as we add in more and more terms, the series doesn’t seem to be converge to the original function uniformly. Instead, high frequency oscillation is observed. In fact, when n is sufficiently large, it has been proved that the magnitude of the oscillation is approximately 9% larger than the gap of discontinuity! This phenomenon is called the Gibbs phenomenon. Note that the number 9% is independent on which function or which point of discontinuity we choose. That’s amazing! But where does the number 9% come from?

[Chinese Version of This Post]

The following sentence is quoted from Wilfrid Hodges’s Logic. Try to figure out its meaning by yourself.

For every person and every age, and every positive number, there is a second positive [...]]]> Believe it or not, sometimes when you fail to understand a sentence, it is not your language skill but your math that is to blame.

The following sentence is quoted from Wilfrid Hodges’s Logic. Try to figure out its meaning by yourself.

For every person and every age, and every positive number, there is a second positive number such that at any age which differs from the first-mentioned age by fewer days than the latter positive number, the person’s height differs from his height at the first-mentioned age by less than the former positive number of inches.

Solution:

Denote h(x,y) as the height of people x at age y. As usual, we use “∀” to represent “for all” and “∃” to represent “there exists”.

Here it goes.

For every person and every age, and every positive number (∀x,a,n>0), there is a second positive number (∃m>0) such that (s.t.) at any age (∀b) which differs from the first-mentioned age by fewer days than the latter positive number(|b-a|<m), the person’s height (h(x,b)) differs from his height at the first-mentioned age (h(x,a)) by less than the former positive number of inches (|h(x,b)-h(x,a)|<n).

Now we combine the “translated” parts together,

∀x,a,n>0, ∃m>0, s.t. ∀b. |b-a|<m, |h(x,b)-h(x,a)|<n

This is exactly the definition of the continuity of function h(x,y) respect to y.

Therefore the meaning of this sentence is:

A person’s height is a continuous function of his age.

[Chinese Version of This Post]

The theorem we are going to prove is [...]]]> An useful trick of proving the equality of two sets is to prove subsumption in both directions, i.e.and. The two proofs are typically independent of each other. Yet today I have seen a proof where the proof of one direction uses the conclusion of the other direction.

The theorem we are going to prove is called the Knaster-Tarski theorem. It states that the set of fixed points of a order-preserving function on a complete lattice is also a complete lattice. This is a very general conclusion. Since a complete lattice cannot be empty, one application of this theorem is to demonstrate the existence of a least(or maximum) fixed point. To avoid complicated mathematical definitions, we hereby consider only one of the special cases — when the complete lattice is the power set lattice. Thus a corollary of the theorem above states as follows:

Suppose is a monotone function from set to set . Then has a least fixed point. And the fixed point is .

Proof: Denote .
We first prove that is a fixed point, i.e. . As usual, to prove set equality, we prove subsumption in both directions.
1.
Since is the intersection of all the sets in , it is sufficient to prove that .
，where the monotonicity of is used in the second step.
2.
Note: In this proof we used the conclusion of 1.
, where the monotonicity of is used in the first step.
According to 1 and 2, we have shown that is a fixed point. Now we prove that it is also the least fixed point.

Q.E.D.

[Chinese Version of This Post]

where f(x) is the function to be approximated. Since there is no error at the n+1 interpolating points, the error function has at least n+1 roots. So it is supposed

where  are the interpolation points.

At first glance, [...]]]> To estimate the error term for the nth Lagrange interpolating polynomial, an error function is defined in our course book,

where f(x) is the function to be approximated. Since there is no error at the n+1 interpolating points, the error function has at least n+1 roots. So it is supposed

where  are the interpolation points.

At first glance, it seems that the supposition needs to be verified. Can all the functions, with roots , be written in the form? Suppose f(x) = log(x), then the error function should be log(x) minus a polynomial, which seems impossible to share that form.

Actually, the supposition is out of question. Note that

It is undefined at the points  . However, subsequent proof should make use of the fact that K(x) is continuous. The reason why we can suppose K(x) to be of this form is that can be regarded as “removable singularity”. We can define

The above equation uses the L’Hospital‘s rule. Since both of the numerator and denominator has roots   , so the limits of K(x) at points exist.

Actually, in complex variable functions, there is similar notion of removable singularity. For instance, for function

the point zero (on the complex plane) is its removable singularity. That is because when we define f(0)=1, f(x) is analytical on the whole complex plane.

[Chinese Version of This Post]

When I see this definition, I doubt that the third property is redundant. If 1 and 2 are satisfied, 3 seems to be true. Remember [...]]]> Two metric spaces, X and Y, are homeomorphic when there exists a function f, such that
1. f is a bijection
2. f is continuous
3. the inverse of  f is also continuous.

When I see this definition, I doubt that the third property is redundant. If 1 and 2 are satisfied, 3 seems to be true. Remember that the continuity of f means that when two elements in X are close enough, their image in Y are also close enough. So it seems like the continuity of f and f^-1 are somewhat symmetric. If given the continuity of f, when the distance of two elements in Y are small, then their image in X should also be near each other.

However I am wrong. One of my classmates, Hu Yong, shows me a counterexample.

Define

X={1, 2 , 3 , … , n , …}
Y={1 , 1/2 , 1/3 , … , 1/n , …}
The distance functions in X and Y are both defined as d(x,y) = |x – y| (That d is a metric is not difficult to verify.)
Denote f as the mapping from X to Y, such that x (in X) is mapped into 1/x (in Y).
For arbitrary  ε > 0, let δ=1/2. When d(m,n)=|m-n|<δ (in this case, the only possible situation is m=n), we have
d(f(m),f(n))=|f(m)-f(n)|=|1/m – 1/n|=0<ε
So f is not only continuous, but uniformly continuous.

However, when considering f^-1, for arbitrary point 1/m in Y, let ε=1. Then for arbitrary δ>0, we can always find 1/n in Y, such that d(1/m,1/n)=|1/m – 1/n|<δ. Yet d(f^-1(1/m),f^-1(1/n))=|m – n|>=1, which shows that f^-1 is discontinuous.

[Chinese Version of This Post]

The process of calculating a website’s PageRank can be viewed as a process of polling. For example, if my blog linked to Wikipedia, then [...]]]> Using the PageRank Algorithm, Google assigns each website a number ranges from 0 to 10 to represent its degree of importance. Its results are basically determined by the internal links between pages.

The process of calculating a website’s PageRank can be viewed as a process of polling. For example, if my blog linked to Wikipedia, then I voted for Wikipedia. And as a result, its PageRank will rise. Intuitively speaking, the PageRank value of a website is the sum of all the votes. Yet it’s unfair to take all the votes equally weighted. Votes from important websites should be of greater weight. But how to determine the importance of a website? PageRank! So it returns to the initial problem. That seems a contradiction, since we have to use PageRank to determine the degree of importance of a website, and the degree of importance is used to calculate PageRank.

It sounds like a process of recursion, or iteration. That’s exactly how PageRank works.

Define PR(A) as the PageRank of website A. For simplicity, we won’t use google’s 0-10 measure, instead, we use 0-1 measure. This is on a par with the range of probability. In fact, PageRank is a probability which reflects the probability of a random walker on the internet arriving at a specific site. Perhaps it is because of the preference that decimals are not welcomed by most people, so that Google changed its scale.

We assume that, initially, the PageRank of all the websites are equally distributed. In other words, suppose there are altogether N websites on the internet, every single website will be assigned PageRank 1/N. To make it easy, we now consider the tiny network that only consists of 4 sites, A,B,C and D. So, according to our analysis, every site has PageRank 1/4. Suppose B,C,D link and only link to A (shown in figure below), then they each contributes 0.25 PageRank to A.

Define
PR(A) = PR(B) + PR(C) + PR(D),
where PR represents PageRank.
Then PR(A) = 0.75.

Next, we suppose B also links to C, and D are linked by all of the other three sites, as shown in figure below.

This time, A and C share B’s votes, so they both receive 0.125 PageRank. Only 1/3 of D’s votes are given to A. In this case,
PR(A) = PR(B)/2 + PR(c)/1 + PR(D)/3
Therefore, according to this definition, the PageRank site X contributes to site Y is equal to its original PageRank divided by the number of its external links. Note that we made an assumption here, that is, multiple links from X to Y are counted only once. The assumption is definitely reasonable, since otherwise the PageRank of my blog will not be so low if a website like http://worlds-highest-website.com/ are  full of links to my blog .
The general equation for calculating the PageRank of a site u is (copied from Wikipedia),

where is the set of all the sites linked to u, and v is the total external links.

One thing noteworthy is that the PageRanks of all the sites are calculated simultaneously, which means that a directed graph (similar to the one drawn above) is predetermined before the calculation. Using the equation above, the PageRank of every site can be achieved. The iteration process is as follows,
Setup: All the sites share equal PageRank.
First Iteration: Every site gets a new PageRank.
Second Iteration: Substitute in the PageRank in the First Iteration to the equation and get another set of PageRank.
…

The thing we really care about is whether the PageRank values will converge if the iteration process continues.

We now turn back to the two examples mentioned at the beginning. For the first case, it is not difficult to figure out that the PageRanks of all the sites go to 0 after the second iteration:

The second case lasts longer, but finally it also results in all-zeros. That is because no website links to D, so after the first iteration PR(D) = 0. And as a consequence, PR(C) goes to 0, and then PR(A):

Huh? The PageRank algorithm turns out to be a failure?

To discuss the situation that finally leads to all-zeros, we now abandon the websites, and simply study directed graphs, which is an abstraction of the PageRank problem.

First things first, for the disconnected graphs (see figure below), we only need to study each component, since it does not influence convergence.

Suppose the vertex set of a directed Graph G is V={V₁,V₂,…,V_n}, the edge set is E={E_ij}. Every vertex is assigned a weight P(V_i) representing its PR value. The weight of Directed edge AB is defined as the PageRank A contributes to B. Thus, for a single vertex, if its outdegree is greater than 0, then its total outdegree is 1.

A direct result is that, if one of the vertexes in the directed graph has outdegree zero, then after finite iterations all of the PRs will turn to zero. Intuitively speaking, the vertex is like a black hole, absorbing the whole PR of the system. Since it does not contribute any PR value to others, the total PR will decrease during each iteration, and finally down to zero.

So how does Google prevent this kind of graph? After all, it is quite possible that a website does not link to any other site. Here is a possible solution (Huh, who knows how Google did it). If a website has no external links, it is assumed that it links to all the other sites. Using this approach, we are able to avoid the problem.

When the outdegree of every vertex is greater than 0, the PR value circulates inside the graph, which indicates that the total PR is conservative. Some might ask, “What if there is a vertex with indegree 0?”. In this case, its PR becomes 0 after the first iteration, and its original PR is contributed to the rest vertexes of the graph. Eventually, all the vertexes with indegree 0 will be 0. However, the whole PR of the system is also conservative.

Does the conservation of PR guarantee the convergence?

Look at the following example,

The iteration process is as follow,

The iteration will continue infinitely and will never converge.

In fact, we can also use matrix to represent the problem. That is because, essentially, a directed graph can be transformed to a equivalent matrix, and vice versa. Denote A_ij as the PageRank percent vertex i contributes to j, the above graph is equivalent to the following matrix,

Given the initial vector,
.

The first iteration, in the matrix representation, is to multiply the matrix by the initial vector. The second iteration, similarly, is to multiply the matrix by the resulting matrix of the first iteration. And this goes on and on … . Actually, the above matrix is called ‘’state transition matrix” in stochastic process theory. The iteration process is called Markov chain. Denote the state transition matrix as P. If there is a positive integer N, such that P^N>0 (a matrix is positive is defined as every element in the matrix is positive), the Markov chain is called regular chain. It has a unique limit state independent of the initial state. In our problem, it means that the PageRanks will converge. (For more, please reference to books on stochastic process.)

In this post, we only take a glimpse at the principle of PageRank algorithm. To form the final algorithm, far more things are to be considered, such as domain data, quality of the content, customer data, and the set-up time of the website. I think the most interesting point is that Google can calculate the PR values of almost all the websites in the internet in a limited time, given the extremely huge amount of data and the real-time changes of the sites. Really unbelievable, isn’t it?

Reference:
http://en.wikipedia.org/wiki/PageRank
http://en.wikipedia.org/wiki/Markov_chain
Mathematical Modeling(3rd edition), Qiyuan Jiang, Jinxing Xie, JunBian Ye, Higher Education Press

[Chinese Version of This Post]

Suppose  and  are non-negative measurable functions on measurable set D. And for almost all , is a monotone increasing sequence [...]]]> The Levi’s Theorem, also known as Levi’s monotone convergence theorem, shows that for a non-negative measurable function, the order of the limit operator and integral operator can be rearranged. It is stated as follows:

Suppose  and  are non-negative measurable functions on measurable set D. And for almost all , is a monotone increasing sequence that converges to , then

In Real Variable Funtions, a book written by Xingwei, Zhou, the proof of the theorem is beautiful. Let me show you how it is done. Since the Lebesgue integral of a non-negative measurable function is defined by the limit of the integral of a monotone increasing sequence of non-negative simple functions. Every  can be approximated by a monotone increasing sequence of non-negative simple functions, which are denoted as . The next step is to construct a new function series  like this:

To write it down,

Therefore, the sequence  have the following properties:
(1) is monotone increasing
(2)

In the second property, we first let  , then let , so the limit of  becomes . Besides, according to the first property, the integral of  can be defined by the limit of the integrals of .

The idea behind the proof, whose key point lies in the construction of  , is inspiring. In fact, ways to construct  is not unique. It works as long as the sequence you constructed satisfies the two properties. I found another way to build the sequence:

Proof：, suppose the integral of  is defined by monotone increasing sequence of non-negative simple functions . Denote


…

Then  is sequence of non-negative simple functions. Besides, it satisfies,
(1) is monotone increasing
(2) 
According to (2), we have
(3) 

In (2),(3), let( note that  at the same time), we get
(4)
(5) 
In (4),(5), let, we have


Then

Reference：Real Variable Functions, Xingwei, Zhou, Science Press.

[Chinese Version of This Post]

Show that for arbitrary triangle in a plane, there exists a line that divides the triangle into two parts that have the same area. In geometry, our task usually is to find such a line. However, here we will [...]]]> In this article, the zero-point theorem has been implemented to solve a practical problem. Here is another example.

Show that for arbitrary triangle in a plane, there exists a line that divides the triangle into two parts that have the same area.
In geometry, our task usually is to find such a line. However, here we will prove its existence. (In most cases, the proof of existence is very important. For example, consider the statement that among all the closed curves in a plain which have the same circumference, circle has the biggest area. To prove this statement, first of all, we have to show that there exists a closed curve which has the biggest area. Then we are to prove that the curve is a circle. For this problem, the proof of existence is much more difficult than showing that the required curve it is a circle. By the way, the whole axiom set theory is based on 10 fundamental axioms, most of which are axioms of existence. For instance, the simplest empty set axiom: There exists a set with no elements. Only after asserting this axiom can we define the empty set. So we can say that existence is the prerequisite of every properties. )
OK, now let’s prove this theory.
Proof: Suppose ABC is a given triangle and l is a given direction. Denote S(x) as the shaded area drawn below.
First we show that S(x) is a continuous function.
In fact, for x1,x2 belongs to [a,b], since  |S(x1)-S(x2)|<=|OT|*|x1-x2|,  S(x) is not only continuous, but also uniformly continuous.
Denote the area of triangle ABC as M.
Define function f(x) = S(x) – M/2, so f(x) is continuous. f(a)= -M/2 , f(b)=M/2. According to the zero-point theorem, there exists a point c in [a,b], such that f(c) = 0, which means that S(c) = M/2.

[Chinese Version of This Post]