Ngô Quốc Anh

May 28, 2009

Finite difference method: A brief introduction

Filed under: 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,

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

then a reasonable approximation for that derivative would be to take

\displaystyle 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,

\displaystyle 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,

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

which, with some minor algebraic manipulation, is equivalent to

\displaystyle f'(a) = {f(a+h)-f(a)\over h} + R_1(x)

so that for R_1(x) sufficiently small,

\displaystyle 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

\displaystyle 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),

\displaystyle 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

\displaystyle \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

\displaystyle \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

\displaystyle \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

\displaystyle 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

\displaystyle \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

\displaystyle\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

\displaystyle (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

\displaystyle \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}-2u_{j}^{n}+u_{j-1}^{n}}{h^{2}}\right).

This formula is known as the Crank-Nicolson method. We can obtain u_j^{n+1} from solving a system of linear equations

\displaystyle (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

\displaystyle \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

Advertisements

May 19, 2009

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

Filed under: Giải tích 7 (MA4247) — Tags: , — 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

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

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

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

(more…)

The QE – Purdue University, Department of Mathematics

Filed under: Đề Thi — Ngô Quốc Anh @ 14:06

The student must pass four written examinations chosen as described below. The exams are based on material that is covered in the courses listed and on material from undergraduate prerequisites. Credit for passing a similar examination at another university cannot be transferred.

The Qualifying Examinations are written examinations offered twice a year during week long Qualifier Exam Sessions the week before classes start in August and January. Each examination is written and graded by a faculty member or a committee of faculty members chosen by the Graduate Committee.

The following four subject areas are called the Core 4 Areas:.

  • Complex Analysis (MA 530)
  • Real Analysis (MA 544)
  • Abstract Algebra (MA 553)
  • Linear Algebra (MA 554)

The qualifier exam subject areas are the Core 4 Areas plus the following Area Exams:

  • Numerical Analysis (MA 514)
  • Probability (MA 519)
  • Partial Differential Equations (MA 523)
  • Differential Geometry (MA 562)
  • Topology (MA 571)
  • Mathematical Logic (MA 585)

The student must pass at least two exams from the Core 4 Areas, including at least one of 544 or 553. They must also pass two more exams from the Area Exams and the unused two exams from the Core 4.

The Qualifier Deadline for students who enter the program with a master’s degree is the January Qualifier Exam Session of their second year. The Qualifier Deadline for students without a master’s degree is the January Qualifier Exam Session of their third year. Students who have not passed the four exams on or before the session of their Qualifier Deadline will have their privileges to continue in the mathematics PhD program terminated.

Each qualifier exam can be attempted a maximum of three times and students may attempt as many qualifier exams as they wish at any Qualifier Session on or before their Qualifier Deadline.

Once an exam is passed, it cannot be retaken to improve the grade from B to A.

(more…)

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

Filed under: Đề Thi — Ngô Quốc Anh @ 13:49

This is a combination of Qualifying Exams and Basic Coursework. We offer 5 distinct qualifying exams, twice a year (January and August), consisting of 4hour long written exams in the following subjects:

  • Algebra
  • Complex Analysis
  • Geometry/Topology
  • Numerical/Applied Analysis
  • Real Analysis

These exams are designed to assess that student’s competence in basic mathematical skill and knowledge in each of these areas at the level of the core courses displayed below. In order to fulfill the requirement, a student must pass at least 2 qualifying exams and take at least 2 full-year core sequences (with at least a B grade)out of the following table of basic level courses:

Group I Group II Group III Group IV
AlgebraMath 653/Math 654 Real AnalysisMath 607/Math 608 Diff. GeometryMath 622/Math623 Applied AnalysisMath 641/Math 642
Discrete Math/Number TheoryMath 613/Math 630/Math 627 Complex AnalysisMath 617/Math 618 TopologyMath 636/Math 637 Numerical AnalysisMath 609/Math 610

Furthermore, the choices must be made so that the combination of qualifying exams and core sequences cover at least three out of the four groups displayed in the columns of the table above. A typical student is expect to have fulfilled the qualifying requirements by the end of the second year of enrollment.

Timetable for the Qualifying Exams

To be considered in good academic standing in the Ph.D. program, a student must have passed two qualifying exams by the end of their second year in the Ph.D. program. For the purpose of the qualifying exam timetable, students will be considered to have begun their Ph.D. program with the Fall semester occurring in the calendar year in which they first enroll in the program.

Except for students being admitted to the Ph.D. program upon completion of a M.S. degree in mathematics at Texas A&M University, the following guidelines apply:

  • Students are expected to have passed at least one qualifying exam by the end of their first year in the Ph.D. program.
  • Students are expected to have passed at least two qualifying exams by the end of their second year in the Ph.D. program.

Since students being admitted to the Ph.D. program upon completion of a M.S. degree in Mathematics at Texas A&M University must have already passed at least one Ph.D. qualifying exam prior to admission to the Ph.D. program, the following amended guideline will apply:

  • Students are expected to have passed their second qualifying exam by the end of their first year in the Ph.D. program.

An archive with previous Qualifying Exams can be found here. Students have the option of passing additional qualifying exams in place of taking the additional two full qualifying exam course sequences.

(more…)

The QE – Indiana University, Department of Mathematics

Filed under: Đề Thi — Ngô Quốc Anh @ 13:39

The Math Department “qualifying exam” is comprised of a 3-tier system designed to help determine as quickly and efficiently as possible whether students have mastered basic graduate level mathematics, exhibit the necessary abilities and self-discipline, and have prepared themselves to pursue the independent research necessary for the Ph.D. within a 2 to 3 year period.

Tier-1: Comprehensive 400-level written exams

Ph.D. students will take a 2-part written exam on 400-level Analysis and Algebra. These exams will be given the week before classes begin in the fall and in the spring. New students may take either or both of the Tier-1 exams in August when they first arrive. A student is allowed to try each exam each time it is offered, but s/he must pass both exams prior to the end of the second year of study. Students pursuing a Master’s Degree are not required to take the Tier-1 exams.

Tier 1 Exams

Tier-2: Committee Review

Each spring, the Graduate Policy Committee will review the record of every Ph.D. student who has either:

  1. Completed 2 years in the program without previous review, or
  2. Passed the Tier-1 exams on entrance to the program and elects the review at the end of their first year.

The committee will decide which students may continue toward Ph.D. candidacy. The committee’s considerations will include:

  1. Performance on the Tier-1 exams
  2. Performance in 500 level coursework
  3. Student’s academic advisor’s report (see below)
  4. Written personal statement by student
  5. Student’s performance of assistantship duties
  6. Student’s performance on A.I. English exams (if applicable)

As indicated above, students can accelerate their progress in the program by passing the Tier-1 exams on entrance into the program and electing the Tier-2 review at the end of their first year. The review committee will treat this as favorable for their case. Students who do not get a recommendation to continue will be encouraged to complete the M.A. degree. If they have financial support at the time of review, they will be entitled to one additional semester of support.

(more…)

May 17, 2009

Rouché’s theorem and several applications

Filed under: 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.

https://i2.wp.com/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.

(more…)

May 8, 2009

A Relation Between Pointwise Convergence Of Functions And Convergence Of Functionals

Filed under: 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.

May 6, 2009

MA5213: Advanced Partial Differential Equations

Filed under: 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

Create a free website or blog at WordPress.com.