|
|
To estimate the error term for the nth Lagrange interpolating polynomial, an error function is defined in our course book,
=f(x)-L_n(x))
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
=K(x)(x-x_0)(x-x_1)...(x-x_n))
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. Continue reading About Removable Singularity
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]
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 <img src=”http://latex.codecogs.com/gif.latex?B_u” alt=”" /> 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:
|
PR(A) |
PR(B) |
PR(C) |
PR(D) |
| Setup |
0.25 |
0.25 |
0.25 |
0.25 |
| First Iteration |
0.75 |
0 |
0 |
0 |
| Second Interation |
0 |
0 |
0 |
0 |
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):
|
PR(A) |
PR(B) |
PR(C) |
PR(D) |
| Setup |
0.25 |
0.25 |
0.25 |
0.25 |
| First Iteration |
0.4583 |
0.0833 |
0.2083 |
0 |
| Second Iteration |
0.25 |
0 |
0.0417 |
0 |
| Third Iteration |
0.0417 |
0 |
0 |
0 |
| Fourth Iteration |
0 |
0 |
0 |
0 |
Huh? The PageRank algorithm turns out to be a failure? Continue reading Google Pagerank Algorithm
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: Continue reading Another Proof of the Levi’s Theorem
If you toss a coin, it will come up a head or a tail. When it is head, the gambler will earn a dollar. When it is tail, he loses one. Suppose the gambler succeeds when he has m dollar in hand, and bankrupts when he has no dollar left. Now a gambler’s initial property is x dollars, where x is an integer and smaller than m. Show the probability that he will become a bankrupt.
Continue reading Gambler’s bankruptcy
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]
There are two ways of describing a set. One method is to list all of its members, for example, {1,2,3}. Another way to do this is to use the set-builder notation, such as {x|x>3}. The set-builder notation brings convenience to the description of sets, however, it also brings ‘catastrophe’ due to its vagueness. Here are two examples in the book Elements of Set Theory.
1
Consider the set {x|x is the smallest integer that cannot be defined in a line.}
The above sentence defined an integer, however, the integer, according to the definition above, cannot be defined in a line!
2
Consider the set {x|x does not belongs to x}
Let A = {x|x does not belongs to x}. There are two cases. A belongs to A, and A doesn’t belong to A. If A doesn’t belong to A, then A satisfies the condition, thus A belongs to A; Otherwise, if A belongs to A, then A fails to satisfy the condition, thus A doesn’t belong to A.
[Chinese Version of This Post]
The zero-point theorem, also called the existence theorem of roots, is a special case of the medium theorem of continuous functions. It is stated as below,
If function f(x) is continuous on interval [a,b], and f(a) and f(b) are of opposite sign, then there exists at least one point  in (a,b), s.t. f()=0.
Now we use the theorem to solve a practical problem:
On a floor that is not flat, can you find an adequate position such that the four legs of a quadrate desk touch the ground at the same time?
For this problem, we first assume:
(1) The four legs are of the same length
(2) Take the part of the desk where its leg touches the ground as a geometric point, and the endpoints of the four legs form a strict square.
(3) The ground is relatively plain, i.e. , there are at least three legs of the desk on the ground at the same time within the range considered.
(4) The height of the ground is continuous. No sharp gap exists.
According to the assumptions above, we take the center of the square as origin. When the desk rotates around the origin, the angle between diagonal vector CA and x-axis is denoted as  .
Let the sum of the distance between leg A,C and the ground be g(). Likewise, the sum of the distance between leg B,D and the ground be f(). According to (3), for arbitrary , one of f() and g() is zero. And because of (4), both of f() and g() are continuous. So the quadrate desk problem can be stated in words of math like this,
For continuous functions f(x) and g(x), g(0)=0, f(0)>=0. And for arbitrary x, we have f(x)g(x) = 0. Prove that there exists a point , such that f() = g() = 0.
Proof: Continue reading Application of the Zero-point Theorem -> Quadrate Desk Problem
Suppose you are in a game show. Now there are three boxes for you to choose, two of which are empty and one with a present inside. You don’t know in which box the present is, but the host knows. In the game, the host let you choose a box at first, and then opens one of the other two boxes to show that it is empty. At last the host gives you a chance to switch,which means that you can choose to change the box you had chosen to the other unopened one. Will you make a change? (The answer is hidden below, printed in white color.)
You should absolutely change the box. Label the three boxes A,B and C, and suppose you have chosen A at first. It’s apparent that there is 1/3 probability that the present is in A. So the probability that the present is in B or C is 2/3. One of B or C may be empty, or both. So, after you have chosen A, the host will probably open B or C to show it is empty. Notice that the action of the host will not influence the probability that the present is in box A. Now we assume the host has opened B. So the probability that the present is in A is still 1/3, whereas the probability that the present is in B shrinks to zero. Thus the probability that the present is in C rises to 2/3. So you should change to C, which doubles the probability that you get the present.
One of 100,000 people in the world is a AIDS patient. Till now, the diagnosis of AIDS is quite accurate,but is not foolproof. The accuracy of diagnosis is 99%. Suppose you have just finished a HIV test, and the result is … positive! Will you feel desperate? Or to what degree do you feel afraid?
You should certainly feel safe, because there is high possibility that you are not infected with AIDS. What? HIV positive means that I’m most probably not infected? Yes. To illustrate this, suppose there are 1 million people who also did the test. Among these people, 10 are AIDS patient and the other 999,990 are not. Nine to ten people who are AIDS patient will be diagnosed positive. Among the other 999,990 people, 1% will be falsely diagnosed positive. In numbers, it is about 10,000 people. So, most of the cases are misdiagnosis. When you are diagnosed positive, the real possibility that you are infected is only 1/1000. (Of course, if you did something dangerous before testing, that’s another matter.)
A couple has two children. One of them is a girl. What’s the possibility that the other is a boy?
The answer is 2/3. There are altogether four cases: (boy boy),(boy girl),(girl boy),(girl girl). One of them is a girl, so the case (boy boy) has been excluded, leaving three possible cases, two of which include a boy. So the probability is 2/3. The reason that the answer is NOT 1/2 is that whether the girl was the first born or the second born is not known.
[Chinese Version of This Post]
1 A function is derivable, but its derivative function is not continuous.
According to the derivative limit theorem, the discontinuity points of these kinds of derivative functions can only be of the second kind,i.e, essential discontinuity. Moreover, the derivative function cannot reach infinity at the discontinuity point, otherwise the original function is not derivable at this point. So the conclusion is that it must be an oscillation discontinuity point.
The original function:
Graph:
The derivative function:
Graph:
Note: There are functions whose derivative have infinite discontinuity points. For example, those functions like the concatenation of half circles:
At the concatenation points, the derivative is discontinuous. That is because at these points the original function is not derivable.
2 A function is derivable at a point, but is not derivable at any neighborhood of that point.
y = xD(x)
where D(x) is the Dirichlet function.
The function is derivable at point zero, and the derivative is also zero. However, it is not derivable at any other point.
3 A function has a positive derivative at a point, but there is no monotonous increasing interval at any neighborhood of that point.
The original function:
The function has derivative 1/2 at point zero, but there exists monotonous decreasing interval at any neighborhood of zero(because of oscillation). It can be easily understood when writing down its derivative function. The graph of the function is like a rotation of the graph of y=xsin(1/x), as is drawn below:
[Chinese Version of This Post]
When learning the continuity of functions, we come across an interesting function, y = sin(1/x), which is not continuous at point zero. The frequency of oscillation increases to infinity as x approaches zero. Here are several graphs of the function under different intervals:
However much I magnify the graph, it is always obscure near the point zero. But when I take some discrete points in the function, for example the sequence x = 1/n, and plot the points (1/n,sin(n)), a beautiful, well-patterned graph come into my eyes,
It can be seen that there are many discrete curves. So what are the points that form each individual curve?
This is closely related to the changes of the values of sin(n). Since y = sin(x) is a periodic function with period 2*pi, then for arbitrary natural number n, the corresponding value of sin(n) is determined by the remainder of n/(2*pi). Thus if we sort the remainders in ascending order, and trace the corresponding sequence of natural number n, the sequence must follow some certain patterns. Continue reading Oscillation of sin(1/x) near x=0
I’ve ever heard of two ways about the introduction of the Golden Ratio. One is quite straightforward: Divide a line segment into two parts, such that the length of the first part over the whole is equal to the length of the second part over that of the first part. The proportion is called the Golden Ratio. It equals to (√5-1)/2, approximately 0.618.
Another way to get the Golden Ratio is to construct the so-called Golden Rectangle. For more details, you can refer to Wolfram Mathworld.
It is not until today did I know that there was relationship between the Golden Ratio and Fibonacci Sequence. People with a knowledge of programming may be familiar with the Fibonacci Sequence, since it is a good practice to list the first n terms of the sequence when learning recurrence.
1,1,2,3,5,8,13,21,34,55,89,144…
The characteristics of Fibonacci Sequence is that every term in the sequence is the sum of the previous two terms(except that the first two terms are initially given). That is, F(n) = F(n-1) + F(n-2). If you divide the Nth term by the (N+1)th term, the ratio you get is very close to the Golden Ratio. For example, 13/21 = 0.61904761904762… . Moreover, the difference decreases as N increases. This leads us to the idea that the limit of the ratio as N approaches infinity is exactly the Fibonacci Ratio. Is it really the case? Continue reading Fibonacci Sequence and Golden Ratio
I have ever seen a math joke like this,
When there are common parts in the numerator and denominator, we always have a natural impulse to cancel them out. Philosophically speaking, this is perhaps because human beings have a natural tendency to make things clear and simple. However, such mistake might sometimes result in a correct answer. Here is such an example,
Besides, you can write arbitrary number of ’6’s in the above equation without destroying its correctness, as long as the number of ‘6’s in the numerator is equal to that in the denominator. But why? Continue reading Cancel like this…
|
|
New Comments