Ngô Quốc Anh

Tháng Năm 28, 2009

Finite difference method: A brief introduction

Chuyên mục: Giải tích 9 (MA5265), Linh Tinh, Nghiên Cứu Khoa Học — Ngô Quốc Anh @ 20:08

In mathematics, finite-difference methods are numerical methods for approximating the solutions to differential equations using finite difference equations to approximate derivatives.

Intuitive derivation

Finite-difference methods approximate the solutions to differential equations by replacing derivative expressions with approximately equivalent difference quotients. That is, because the first derivative of a function f is, by definition,

f'(a)=\lim_{h\to 0}{f(a+h)-f(a)\over h},

then a reasonable approximation for that derivative would be to take

f'(a)\approx {f(a+h)-f(a)\over h}

for some small value of h. In fact, this is the forward difference equation for the first derivative. Using this and similar formulae to replace derivative expressions in differential equations, one can approximate their solutions without the need for calculus.

Derivation from Taylor’s polynomial

Assuming the function whose derivatives are to be approximated is properly-behaved, by Taylor’s theorem,

f(x_0 + h) = f(x_0) + \frac{f'(x_0)}{1!}h + \frac{f^{(2)}(x_0)}{2!}h^2 + \cdots + \frac{f^{(n)}(x_0)}{n!}h^n + R_n(x),
where n! denotes the factorial of n, and R_n(x) is a remainder term, denoting the difference between the Taylor polynomial of degree n and the original function. Again using the first derivative of the function f as an example, by Taylor’s theorem,

f(x_0 + h) = f(x_0) + f'(x_0)h + R_1(x),

which, with some minor algebraic manipulation, is equivalent to

f'(a) = {f(a+h)-f(a)\over h} + R_1(x)
so that for R_1(x) sufficiently small,

f'(a)\approx {f(a+h)-f(a)\over h}.

Accuracy and order

The error in a method’s solution is defined as the difference between its approximation and the exact analytical solution. The two sources of error in finite difference methods are round-off error, the loss of precision due to computer rounding of decimal quantities, and truncation error or discretization error, the difference between the exact solution of the finite difference equation and the exact quantity assuming perfect arithmetic (that is, assuming no round-off).

To use a finite difference method to attempt to solve (or, more generally, approximate the solution to) a problem, one must first discretize the problem’s domain. This is usually done by dividing the domain into a uniform grid (see image to the right). Note that this means that finite-difference methods produce sets of discrete numerical approximations to the derivative, often in a “time-stepping” manner.

File:Finite Differences.png

An expression of general interest is the local truncation error of a method. Typically expressed using Big-O notation, local truncation error refers to the error from a single application of a method. That is, it is the quantity f'(x_i)-f'_i if f'(x_i) refers to the exact value and f'_i to the numerical approximation. The remainder term of a Taylor polynomial is convenient for analyzing the local truncation error. Using the Lagrange form of the remainder from the Taylor polynomial for f(x_0 + h), which is

R_n(x_0 + h) = \frac{f^{(n+1)}(\xi)}{(n+1)!} (h)^{n+1},
where x_0 <\xi< x_0 + h, the dominant term of the local truncation error can be discovered. For example, again using the forward-difference formula for the first derivative, knowing that f(x_i) = f(x_0 + ih),

f(x_0 + i h) = f(x_0) + f'(x_0)i h + \frac{f''(\xi)}{2!} (i h)^{2},
and with some algebraic manipulation, this leads to

\frac{f(x_0 + i h) - f(x_0)}{i h} = f'(x_0) + \frac{f''(\xi)}{2!} i h,
and further noting that the quantity on the left is the approximation from the finite difference method and that the quantity on the right is the exact quantity of interest plus a remainder, clearly that remainder is the local truncation error. A final expression of this example and its order is:

\frac{f(x_0 + i h) - f(x_0)}{i h} = f'(x_0) + O(h).
This means that, in this case, the local truncation error is proportional to the step size.

Explicit method

Using a forward difference at time t_n and a second-order central difference for the space derivative at position x_j (“FTCS”) we get the recurrence equation:

\frac{u_j^{n+1} - u_j^{n}}{k} =\frac{u_{j+1}^n - 2u_j^n + u_{j-1}^n}{h^2}.
This is an explicit method for solving the one-dimensional heat equation. We can obtain u_j^{n+1} from the other values this way:

u_{j}^{n+1} = (1-2r)u_{j}^{n} + ru_{j-1}^{n} + ru_{j+1}^{n}
where r = \frac{k}{h^2}. So, knowing the values at time n you can obtain the corresponding ones at time n+1 using this recurrence relation. u_0^n and u_J^n must be replaced by the boundary conditions, in this example they are both 0.

File:Explicit method-stencil.svg

This explicit method is known to be numerically stable and convergent whenever r\le \frac{1}{2}. The numerical errors are proportional to the time step and the square of the space step:

\Delta u = O(k)+O(h^2).

Implicit method

If we use the backward difference at time t_{i + 1} and a second-order central difference for the space derivative at position x_j (“BTCS”) we get the recurrence equation:

\frac{u_{j}^{i+1} - u_{j}^{i}}{k} =\frac{u_{j+1}^{i+1} - 2u_{j}^{i+1} + u_{j-1}^{i+1}}{h^2}.
This is an implicit method for solving the one-dimensional heat equation.

File:Implicit method-stencil.svg

We can obtain u_j^{i+1} from solving a system of linear equations:

(1+2r)u_j^{i+1} - ru_{j-1}^{i+1} - ru_{j+1}^{i+1}= u_{j}^{i}.

The scheme is always numerically stable and convergent but usually more numerically intensive than the explicit method as it requires solving a system of numerical equations on each time step. The errors are linear over the time step and quadratic over the space step.

Crank-Nicolson method

Finally if we use the central difference at time t_{n + \frac{1}{2}} and a second-order central difference for the space derivative at position x_j (“CTCS”) we get the recurrence equation:

\frac{u_j^{n+1} - u_j^{n}}{k} = \frac{1}{2} \left(\frac{u_{j+1}^{n+1} - 2u_j^{n+1} + u_{j-1}^{n+1}}{h^2}+\frac{u_{j+1}^{n} - ...
This formula is known as the Crank-Nicolson method. We can obtain u_j^{n+1} from solving a system of linear equations:

(2+2r)u_j^{n+1} - ru_{j-1}^{n+1} - ru_{j+1}^{n+1}= (2-2r)u_j^n + ru_{j-1}^n + ru_{j+1}^n .

The scheme is always numerically stable and convergent but usually more numerically intensive as it requires solving a system of numerical equations on each time step.

File:Crank-Nicolson-stencil.svg

The errors are quadratic over the time step and formally are of the fourth degree regarding the space step:

\Delta u = O(k^2)+O(h^4).
However, near the boundaries, the error is often O(h^2) instead of O(h^4). Usually the Crank-Nicolson scheme is the most accurate scheme for small time steps. The explicit scheme is the least accurate and can be unstable, but is also the easiest to implement and the least numerically intensive. The implicit scheme works the best for large time steps.

Source

Tháng Năm 19, 2009

Casorati–Weierstrass theorem, the behavior of meromorphic functions near essential singularities

Chuyên mục: Giải tích 7 (MA4247), Linh Tinh, Nghiên Cứu Khoa Học — Ngô Quốc Anh @ 14:42

In complex analysis, a branch of mathematics, the Casorati–Weierstrass theorem describes the remarkable behavior of meromorphic functions near essential singularities. It is named for Karl Theodor Wilhelm Weierstrass and Felice Casorati.

Formal statement of the theorem

Start with some open subset U in the complex plane containing the number z_0, and a function f that is holomorphic on U\backslash \left\{ {{z_0}} \right\}, but has an essential singularity at z_0. The Casorati–Weierstrass theorem then states that

if V is any neighborhood of z_0 contained in U, then f(V \backslash  \{z_0\}) is dense in \mathbb C.

This can also be stated as follows:

for any \varepsilon > 0 and any complex number w, there exists a complex number z in U with |z-z_0| < \varepsilon and |f(z)-w| < \varepsilon.

Or in still more descriptive terms:

f comes arbitrarily close to any complex value in every neighbourhood of z_0.

This form of the theorem also applies if f is only meromorphic. The theorem is considerably strengthened by Picard’s great theorem, which states, in the notation above, that f assumes every complex value, with one possible exception, infinitely often on V.

Examples

The function f(z) = e^\frac{1}{z} has an essential singularity at z_0 = 0, but the function g(z) = \frac{1}{z^3} does not (it has a pole at 0). Consider the function

f(z)=e^{1/z}.

This function has the following Laurent series about the essential singular point at z_0:

f(z)=\displaystyle\sum_{n=0}^{\infty}\frac{1}{n!z^{n}}.

Because f'(z) =\frac{-e^{\frac{1}{z}}}{z^{2}} exists for all points z\ne 0 we know that f(z) is analytic in the neighborhood of z = 0. Hence it is an isolated singularity, as well as being and essential singularity. Using a change of variable to polar coordinates z = re^{i\theta} our function, f(z) = e^\frac{1}{z} becomes:

f(z)=e^{\frac{1}{r}e^{-i\theta}}=e^{\frac{1}{r}\cos(\theta)}e^{-\frac{1}{r}i \sin(\theta)}.

Taking the absolute value of both sides:

\left| f(z) \right| = \left| e^{\frac{1}{r}cos \theta} \right| \left| e^{-\frac{1}{r}i \sin(\theta)} \right | =e^{\frac{1}{r}...

Thus, for values of \theta such that \cos \theta > 0, we have f(z)\rightarrow\infty as r \rightarrow 0, and for \cos \theta < 0, f(z) \rightarrow 0 as r \rightarrow 0.

Consider what happens, for example when z takes values on a circle of diameter \frac{1}{R} tangent to the imaginary axis. This circle is given by r = \frac{1}{R} \cos \theta. Then,

f(z) = e^{R} \left[ \cos \left( R\tan \theta \right) - i \sin \left( R\tan \theta \right) \right]

and

\left| f(z) \right| = e^R.

Thus,\left| f(z) \right| may take any positive value other than zero by the appropriate choice of R. As z \rightarrow 0 on the circle, \theta \rightarrow \frac{\pi}{2} with R fixed. So this part of the equation:

\left[ \cos \left( R \tan \theta \right) - i \sin \left( R \tan \theta \right) \right]

takes on all values on the unit circle infinitely often. Hence f(z) takes on all the value of every number in the complex plane except for zero infinitely often.

Proof of the theorem

A short proof of the theorem is as follows: Take as given that function f is meromorphic on some punctured neighborhood V\backslash \left\{ {{z_0}} \right\}, and that z_0 is an essential singularity. Assume by way of contradiction that some value b exists that the function can never get close to; that is: assume that there is some complex value b and some \varepsilon > 0 such that |f(z)-b| \geq \varepsilon for all z in V at which f is defined.

Then the new function:

g(z) = \frac{1}{f(z) - b}

must be holomorphic on V\backslash \left\{ {{z_0}} \right\}, with zeroes at the poles of f, and bounded by \frac{1}{\varepsilon}. It can therefore be analytically continued (or continuously extended, or holomorphically extended) to all of V by Riemann’s analytic continuation theorem. So the original function can be expressed in terms of g:

f(z) = \frac{1}{g(z)} + b

for all arguments z in V\backslash \left\{ {{z_0}} \right\}. Consider the two possible cases for \lim_{z \rarr z_0} g(z). If the limit is 0, then f has a pole at z_0 . If the limit is not 0, then z_0 is a removable singularity of f. Both possibilities contradict the assumption that the the point z_0 is an essential singularity of the function f. Hence the assumption is false and the theorem holds.

The QE – Purdue University, Department of Mathematics

Chuyên mục: Đề Thi — Ngô Quốc Anh @ 14:06

The QE – Texas A&M University, Department of Mathematics

Chuyên mục: Đề Thi — Ngô Quốc Anh @ 13:49

Algebra

Syllabus
January,2008
May, 2007
January, 2007
May, 2006
January, 2006
May, 2005
January, 2005
May, 2004
January, 2004
May, 2003
January, 2003
May, 2002
January, 2002
May, 2001
May, 2000
January, 2000
May, 1999
January, 1999
May, 1998
January, 1998
May, 1997
January, 1997
May, 1996
Spring, 1995

Applied
Analysis

Syllabus
January,2009
May,2008
January,2008
May, 2007
January, 2007
May, 2006
May, 2005
January, 2005
May, 2004
January, 2004
May, 2003
January, 2003
May, 2002
January, 2002
May, 2001
January, 2001
May, 2000
January, 2000
May, 1999
January, 1999
May, 1998
January, 1998
May, 1997
January, 1997
May, 1996
January, 1996

Combinatorics (C)/
Graph (G) and Number (N) Theory

Syllabus
May, 2008(C),
January, 2008(C),
May, 2007(G), (N)
January, 2007(C), (G), (N)
May, 2006(C), (G)
January, 2006(C), (G)
(N)
May, 2005(C), (G), (N)
January, 2005(C), (G)
(N)
May, 2004(C), (G), (N)
January, 2004(C), (N)

Complex
Analysis

Syllabus
May, 2008
January, 2008
May, 2007
January, 2007
May, 2006
January, 2006
May, 2005
January, 2005
May, 2004
January, 2004
May, 2003
January, 2003
May, 2002
January, 2002
May, 2001
January, 2000
May, 1999
January, 1999
May, 1998
January, 1998
May, 1997
May, 1996
January, 1996
May, 1995

Differential
Geometry

Syllabus
May, 2008
January, 2007
May, 2005
May, 2004
May, 2003
May, 2002
January, 2002
May, 2000
Spring, 1999
May, 1998
May, 1997
May, 1996
May, 1994

Numerical
Analysis

Syllabus
January, 2009
May, 2008
January, 2008
May, 2007
January, 2007
May, 2006
May, 2005
May, 2003
May, 2002
January, 2002
January, 2000
May, 1999
January, 1998
May, 1997
January, 1997
May, 1996
Spring, 1996
Fall, 1995

Real
Analysis

Syllabus
May, 2008
January, 2008
May, 2007
January, 2007
May, 2006
January, 2006
May, 2005
January, 2005
May, 2004
January, 2004
May, 2003
January, 2003
May, 2002
January, 2002
May, 2001
January, 2001
May, 2000
January, 2000
May, 1999
January, 1999
May, 1998
January, 1998
May, 1997
January, 1997
May, 1996
May, 1995

Topology

Syllabus
January, 2009
May, 2008
January, 2008
May, 2007
January, 2007
May, 2005
January, 2005
May, 2004
January, 2004
May, 2003
January, 2003
May, 2002
January, 2002
May, 2001
January, 2001
May, 2000
January, 2000
May, 1999
January, 1999
May, 1998
January, 1998
May, 1997
May, 1996
January, 1996
May, 1995

Source: http://www.math.tamu.edu/teaching/graduate/quals.htm

The QE – Indiana University, Department of Mathematics

Chuyên mục: Đề Thi — Ngô Quốc Anh @ 13:39

Tháng Năm 17, 2009

Rouché’s theorem and several applications

Chuyên mục: Giải tích 7 (MA4247), Linh Tinh, Nghiên Cứu Khoa Học — Ngô Quốc Anh @ 16:51

In mathematics, especially complex analysis, Rouché’s theorem tells us that if the complex-valued functions f and g are holomorphic inside and on some closed contour C, with |g(z)|<|f(z)| on C, then f and f + g have the same number of zeros inside C, where each zero is counted as many times as its multiplicity. This theorem assumes that the contour C is simple, that is, without self-intersections. Moreover, f and f + g should have no zeros on C.

The theorem is usually used to simplify the problem of locating zeros, as follows. Given an analytic function, we write it as the sum of two parts, one of which is simpler and grows faster than (thus dominates) the other part. We can then locate the zeros by looking at only the dominating part.

For example, the polynomial z^5+3z^3+7 has exactly 5 zeros in the disk |z|<2 since |3z^3+7|<32 = | z^5 | for every | z | = 2, and z^5, the dominating part, has five zeros in the disk.

Geometric explanation

It is possible to provide an informal explanation on why the Rouche’s theorem holds. First we need to rephrase the theorem a little bit. Let h(z) = f(z) + g(z). Notice that f, g holomorphic implies h holomorphic too. Then, with the conditions imposed above, Rouche’s theorem says that

If |f(z)| > |h(z)-f(z)| then f(z) and h(z) have the same number of zeros on the interior of C.

Notice that the condition |f(z)| > |h(z)-f(z)| means that for any z, the distance of f(z) to the origin is larger than the length of h(z)- f(z), which in the following picture means that for each point on the blue curve, the segment joining to the origin is larger than the green segment associated to it. Informally we can say that the red curve h(z) is always closer to the blue curve f(z) than to the origin.

http://upload.wikimedia.org/wikipedia/commons/1/13/Rouche-thm.png

But the previous paragraph shows that since f(z) winds exactly once around 0, so must h(z), and by the argument principle, the index of both curves around zero is the same, which means that f(z) and h(z) have the same number of zeros.

One popular, informal way to summarize this argument is as follows: If a person were to walk a dog on a leash around and around a tree, and the length of the leash is less than the radius of the tree, then the person and the dog go around the tree an equal number of times. (Indeed, one may see that the converse of Rouche’s theorem is false, insofar as the leash need only be less than the circumference of the tree.)

Applications

Consider the polynomial z^2 + 2az + b^2 (where a > b > 0). By the quadratic formula we find that it has two zeros at a \pm \sqrt{a^2 - b^2}. Since

|z^2 + b^2| \le 2b^2 < 2a|z|

for every | z | = b. Rouché’s theorem says that the polynomial has exactly one zero inside the disk | z | < b. Since a + \sqrt{a^2 - b^2} is clearly outside the disk, we conclude that the polynomial has a zero at a - \sqrt{a^2 - b^2}. This sort of arguments can be useful in locating residues when one applies Cauchy’s Residue theorem.

Rouché’s theorem can also be used to give a short proof of the Fundamental Theorem of Algebra. Let p(z) = a_0 + a_1z + a_2z^2 + ... + a_nz^n, and choose a R so large that

|a_0 + a_1z + ... + a_{n-1}z^{n-1}| \le \sum_{j=1}^n |a_j| R^{n-1} < |a_n|R^n = |a_n z^n|

for every | z | = R.  Since a_nz^n has n zeros inside the disk | z | < R, it follows from Rouché’s theorem that p also has the same number of zeros inside the disk.

One advantage of this proof over the others is that it shows not only that a polynomial must have a zero but the number of its zeros is equal to its degree (counting, as usual, multiplicity).

Another use of Rouché’s theorem is to prove the open mapping theorem for analytic functions.

Proof of Rouché’s theorem

The hypothesis, that |g(z)| < |f(z)| on C, implies

\left|\frac{f(z)+g(z)}{f(z)}-1\right| < 1

for all z \in C. Hence the function F(z) = \frac{f(z)+g(z)}{f(z)} takes the curve C to a curve F(C) in the interior of the disc of radius 1 and center 1. The winding number of F(C) about the origin is thus zero. On the other hand, by the argument principle, this winding number is given by

0 = {1\over 2\pi i}\oint_C {F'(z) \over F(z)} dz=N_F(C)-P_F(C)

where N_F(C) is the number of zeroes of F inside C, P_F(C) is the number of poles inside C. Hence N_F = P_F. But F is the ratio of two holomorphic functions f+g and f inside C, and so the zeros are those of f+g and the poles are the zeros of f. That is,

0=N_F(C) - P_F(C) = N_{f+g}(C) - N_f(C),

as required.

[Source]

Tháng Năm 8, 2009

A Relation Between Pointwise Convergence Of Functions And Convergence Of Functionals

Chuyên mục: Các Bài Tập Nhỏ, Giải Tích 6 (MA5205), Nghiên Cứu Khoa Học — Ngô Quốc Anh @ 16:40

Let (\Omega, \Sigma, \mu) be a measure space and let \{f_n\}_{n=1}^\infty be a sequence of complex valued measurable functions which are uniformly bounded in L^p= L^p(\Omega, \Sigma, \mu) for some 0 < p<\infty. Suppose that f_n \to f pointwise almost everywhere (a. e.). What can be said about \| f\|_p?

The simplest tool for estimating \| f\|_p is Fatou’s lemma, which yields

\displaystyle\| f\|_p \leq \liminf_{n \to \infty} \|f_n\|_p.

The purpose of this note is to point out that much more can be said, namely

\displaystyle\lim_{n \to \infty} \left( \|f_n\|_p^p - \| f_n - f\|_p^p \right) = \|f\|_p^p.

More generally, if j : \mathbb C \to \mathbb C is a continuous function such that j(0) = 0, then, when f_n \to f a.e. and

\displaystyle\int |j(f_n(x))| d\mu(x) \leq C < \infty

it follows that

\displaystyle\lim\limits_{n \to \infty} \int \left[ j(f_n) - j(f_n - f)\right] = \int j(f)

under suitable conditions on j and/or \{f_n\}.

Statement. The L^p case (0<p<\infty): Suppose f_n \to f a.e. and \|f_n\|_p \leq C<\infty for all n and for some 0<p<\infty. Then the following  limit exists and the equality holds

\displaystyle\lim_{n \to \infty} \left( \|f_n\|_p^p - \| f_n - f\|_p^p \right) = \|f\|_p^p.

Proof.

(i) By Fatou’s lemma, f \in L^p.

(ii) In case 0<p\leq 1, and if we assume that f \in L^p, then we do not need the hypothesis that \|f_n\|_p is uniformly bounded. [This follows from the inequality

\displaystyle|f_n|^p - |f_n - f|^p \leq |f|^p

and the dominated convergence theorem.] However, when 1<p<\infty, the hypothesis that \|f_n\|_p is uniformly bounded is really necessary (even if we assume that f \in L^p) as a simple counterexample shows.

(iii) When 1<p<\infty, the hypotheses imply that f_n \rightharpoonup f weakly in L^p. [By the Banach-Alaoglu theorem, for some subsequence,f_n, converges weakly to some g; but g = f since f_n \to f a.e.] However, weak convergence in L^p is insufficient to conclude that

\displaystyle\lim_{n \to \infty} \left( \|f_n\|_p^p - \| f_n - f\|_p^p \right) = \|f\|_p^p

holds, except in the case p=2. When p\ne 2 it is easy to construct counterexamples, that is

\displaystyle\lim_{n \to \infty} \left( \|f_n\|_p^p - \| f_n - f\|_p^p \right) \ne \|f\|_p^p

under the assumption only of weak convergence. When p=2 the proof of

\displaystyle\lim_{n \to \infty} \left( \|f_n\|_2^2 - \| f_n - f\|_2^2 \right) = \|f\|_2^2

is trivial under the assumption of weak convergence. Indeed,

\|f_n\|_2^2 - \| f_n - f\|_2^2 = \displaystyle\int \big[ f_n^2 - (f_n-f)^2 \big]= \int \big[ 2f_nf -f^2\big] .

Since f_n \rightharpoonup f in L^2, then \int f_n f \to \int f^2 (note that the dual space of L^2 is itself). Thus

\displaystyle\lim_{n \to \infty} \left( \|f_n\|_2^2 - \| f_n - f\|_2^2 \right) = \|f\|_2^2.

Tháng Năm 6, 2009

MA5213: Advanced Partial Differential Equations

Chuyên mục: Linh Tinh — Ngô Quốc Anh @ 14:10

The text books used to prepare this course are

  1. Walter Strass, Partial Differential Equation: and Introduction, John Wiley & Sons, 1992, ISBN 0-471-54868-5.
  2. Fritz John, Partial Differential Equations, 4th ed, 1982, Springer, ISBN 0-387-9060606-6.

Assessment: 70% CA 30% Final Exam.

The topics scheduled will include:

  • Wave Equations. (Hyperbolic equation with space-dimensions 1,2,3) Characteristic Curves method, energy methods, Green’s function, Kirchkoff formula.
  • Heat equation. (Parabolic equation) Maximal principle, Heat Kernel, Energy method.
  • Green’s functions
  • Nonlinear equations such as shock wave theories, Burgers equation, shock layers, and stability of viscous shock layers for compressible Navier-Stokes equation, Broadwell model,

Lecture Notes:

Final exam: ma5213_final

Blog at WordPress.com.