# Ngô Quốc Anh

## January 11, 2009

### A complex trigonometric equation

Filed under: Các Bài Tập Nhỏ, Giải tích 7 (MA4247) — Ngô Quốc Anh @ 20:29

In NUS, department of mathematics, QE in semester 1 AY 08-09 has the following complex trigonometric equation

To solve the above equation, firstly we can see that $2 \sinh (iz) = 2(-i \sin (i^2z) = 2i \sin z$. Then the given equation can be transformed to $4 + \cos z = 2i \sin z$. Using the following formulas

$\displaystyle\cos z = \frac{{{e^{iz}} + {e^{ - iz}}}} {2}, \quad \sin z = \frac{{{e^{iz}} - {e^{ - iz}}}} {2i}$

we get the following equivalent equation

$\displaystyle 4 + \frac{{{e^{iz}} + {e^{ - iz}}}} {2} = 2i\frac{{{e^{iz}} - {e^{ - iz}}}} {{2i}}$,

i.e., $8 + 3{e^{ - iz}} = {e^{iz}}$. Denoting $t=e^{iz}$ one can easily compute that $t=4 \pm \sqrt {19}$. Thus, the solutions are

$\displaystyle z = \frac{{\ln \left| {4 + \sqrt {19} } \right| + i2n\pi }}{i}$

and

$\displaystyle z = \frac{{\ln \left| {4 - \sqrt {19} } \right| + i\left( {\pi + 2n\pi } \right)}} {i}$

where $n \in \mathbb{Z}$. If you wish to express the solutions in Cartesian form, then

$\displaystyle z = 2n\pi - i\ln \left| {4 + \sqrt {19} } \right|$

and

$\displaystyle z = (2n+1)\pi - i\ln \left| {4 - \sqrt {19} } \right|$

where $n \in \mathbb{Z}$ is the answer.

### Composite Simpson rule

Filed under: Các Bài Tập Nhỏ, Giải tích 9 (MA5265), Nghiên Cứu Khoa Học — Ngô Quốc Anh @ 16:28

In topic composite trapezium rule I have shown you what is the so-called trapezium rule and the so-called composite trapezium rule. Recall that the idea of trapezium rule is the following approximation

$\displaystyle \int_{a}^{b} f(x) dx \approx (b-a)\frac{f(a) + f(b)}{2}$.

The right hand side of the above approximation is nothing but the integration of one-order Lagrange interpolation polynomial of $f$ at the nodes $x_0=a$ and $x_1=b$. If we add one more node, we then obtain a new approximation. This leads to the so-called Simpson rule.

In numerical analysis, Simpson’s rule is a method for numerical integration, the numerical approximation of definite integrals. Specifically, it is the following approximation

$\displaystyle\int_{a}^{b} f(x) \, dx \approx \frac{b-a}{6}\left[f(a) + 4f\left(\frac{a+b}{2}\right)+f(b)\right]$.

One derivation replaces the integrand $f(x)$ by the quadratic polynomial $P_2(x)$ which takes the same values as $f(x)$ at the end points $a$ and $b$ and the midpoint $m=\frac{a+b}{2}$. One can use Lagrange polynomial interpolation to find an expression for this polynomial,

$\displaystyle P_2(x) = f(a) \frac{(x-m)(x-b)}{(a-m)(a-b)} + f(m) \frac{(x-a)(x-b)}{(m-a)(m-b)} + f(b) \frac{(x-a)(x-m)}{(b-a)(b-m)}$.

An easy calculation shows that

$\displaystyle\int_{a}^{b} P(x) \, dx =\frac{b-a}{6}\left[f(a) + 4f\left(\frac{a+b}{2}\right)+f(b)\right]$.

Next we will show you the error of Simpson rule. Firstly, we assume that  $f(x)$ is of fourth continuously differentiable. Similarly to the trapezium rule, by considering the following function

$\displaystyle g\left( y \right) = f\left( y \right) - {P_2}\left( y \right) - \frac{4} {{{{\left( {b - a} \right)}^2}}}\left( {f'\left( x \right) - {{P'}_2}\left( x \right)} \right)\left( {y - a} \right)\left( {y - m} \right)\left( {y - b} \right)$.

We firstly see that $g(a)=g(m)=g(b)=g'(m)$, then with the aid of Hermite interpolation, there exists a $\xi \in [a,b]$ such that

$\displaystyle f\left( y \right) - {P_2}\left( y \right) = \frac{{{f^{\left( 4 \right)}}\left( {\xi \left( y \right)} \right)}} {{4!}}\left( {y - a} \right){\left( {y - m} \right)^2}\left( {y - b} \right)$.

Since

$\displaystyle\int_a^b {\frac{{{f^{\left( 4 \right)}}\left( {\xi \left( x \right)} \right)}} {{4!}}\left( {x - a} \right){{\left( {x - m} \right)}^2}\left( {x - b} \right)dx} = \frac{{{f^{\left( 4 \right)}}\left( \xi \right)}} {{4!}}\int_a^b {\left( {x - a} \right){{\left( {x - m} \right)}^2}\left( {x - b} \right)dx}$

and

$\displaystyle\int_a^b {\left( {x - a} \right){{\left( {x - m} \right)}^2}\left( {x - b} \right)dx} = - \frac{{{{\left( {b - a} \right)}^5}}} {{120}}$

then we deduce that

$\displaystyle\int_a^b {f\left( x \right)dx} = \int_a^b {{P_2}\left( x \right)dx} - \frac{{{{\left( {b - a} \right)}^5}}} {{120}}\frac{{{f^{\left( 4 \right)}}\left( \xi \right)}} {{4!}} = \int_a^b {{P_2}\left( x \right)dx} - \frac{{{h^5}}} {{90}}{f^{\left( 4 \right)}}\left( \xi \right)$

where $h = \frac{b-a}{2}$. Regarding to composite Simpson rule, if the interval of integration $[a,b]$ is in some sense “small”, then Simpson’s rule will provide an adequate approximation to the exact integral. By small, what we really mean is that the function being integrated is relatively smooth over the interval $[a,b]$. For such a function, a smooth quadratic interpolant like the one used in Simpson’s rule will give good results.

However, it is often the case that the function we are trying to integrate is not smooth over the interval. Typically, this means that either the function is highly oscillatory, or it lacks derivatives at certain points. In these cases, Simpson’s rule may give very poor results. One common way of handling this problem is by breaking up the interval $[a,b]$ into a number of small subintervals. Simpson’s rule is then applied to each subinterval, with the results being summed to produce an approximation for the integral over the entire interval. This sort of approach is termed the composite Simpson’s rule.

Suppose that the interval $[a,b]$ is split up in $n$ subintervals, with $n$ an even number. Then, the composite Simpson’s rule is given by

$\displaystyle\int_a^b f(x) dx\approx \frac{h}{3}\bigg[f(x_0)+2\sum_{j=1}^{n/2-1}f(x_{2j})+ 4\sum_{j=1}^{n/2}f(x_{2j-1})+f(x_n) \bigg]$,

where $x_i = a + ih$ for $i = 0,1,...,n-1,n$ with $h = \frac{b-a}{n}$; in particular, $x_0 =a$ and $x_n=b$. The above formula can also be written as

$\displaystyle\int_a^b f(x)dx\approx \frac{h}{3}\bigg[f(x_0)+4f(x_1)+2f(x_2)+4f(x_3)+2f(x_4)+\cdots+4f(x_{n-1})+f(x_n)\bigg]$.

The error committed by the composite Simpson’s rule is bounded (in absolute value) by

$\displaystyle\frac{h^4}{180}(b-a) \max_{\xi\in[a,b]} |f^{(4)}(\xi)|$,

where $h$ is the “step length”.

### Composite trapezium rule

Filed under: Các Bài Tập Nhỏ, Giải tích 9 (MA5265), Nghiên Cứu Khoa Học — Ngô Quốc Anh @ 15:15

In mathematics, the trapezium rule (the British term) or trapezoidal rule (the American term) is a way to approximately calculate the definite integral

$\displaystyle \int_{a}^{b} f(x)dx$.

The trapezium rule works by approximating the region under the graph of the function $f(x)$ by a trapezium and calculating its area. It follows that

$\displaystyle\int_{a}^{b} f(x) dx \approx (b-a)\frac{f(a) + f(b)}{2}$.

To calculate this integral more accurately, one first splits the interval of integration $[a,b]$ into $n$ smaller subintervals, and then applies the trapezium rule on each of them. One obtains the composite trapezium rule

$\displaystyle\int_a^b f(x)dx \approx \frac{b-a}{n} \left[ {f(a) + f(b) \over 2} + \sum_{k=1}^{n-1} f \left( a+k \frac{b-a}{n} \right) \right]$.

This can alternatively be written as

$\displaystyle\int_a^b f(x)dx \approx \frac{b-a}{2n} \left(f(x_0) + 2f(x_1) + 2f(x_2)+\cdots+2f(x_{n-1}) + f(x_n) \right)$

where

$x_k=a+k \frac{b-a}{n}$, for $k=0, 1, \dots, n$.

(one can also use a non-uniform grid). The trapezium rule is one of a family of formulas for numerical integration called Newton–Cotes formulas. Simpson’s rule is another, often more accurate, member of the same family. Simpson’s rule and other like methods can be expected to improve on the trapezium rule for functions which are twice continuously differentiable; however for rougher functions the trapezium rule is likely to prove preferable. Moreover, the trapezium rule tends to become extremely accurate when periodic functions are integrated over their periods, a fact best understood in connection with the Euler–Maclaurin summation formula. For non-periodic functions, however, methods with unequally spaced points such as Gaussian quadrature and Clenshaw–Curtis quadrature are generally far more accurate; Clenshaw-Curtis quadrature can be viewed as a change of variables to express arbitrary integrals in terms of periodic integrals, at which point the trapezium rule can be applied accurately.

An advantage of the trapezium rule is that the sign of the error of the approximation is easily known. An integral approximated with this rule on a concave-up function will be an overestimate because the trapezoids include all of the area under the curve and extend over it. Using this method on a concave-down function yields an underestimate because area is unaccounted for under the curve, but none is counted above. If the interval of the integral being approximated includes an inflection point, then the error is harder to identify.

Our aim is to prove that if $latex f\in C^2([a,b])$ then the above approximation is second-order accurate. To this end, we need to recall some properties of Lagrange interpolation.

Roughly speaking, if we denote by $P_1$ the Lagrange interpolation polynomial of $f$ at the nodes $x_0=a$ and $x_1=b$. Then $P_1$ is of order $1$. Explicitly, we have

$\displaystyle {P_1}\left( x \right) = f\left( a \right)\frac{{x - b}} {{a - b}} + f\left( b \right)\frac{{x - a}} {{b - a}}$.

Next for each $x\in [a,b]$ fixed, we consider the following function

$\displaystyle g\left( y \right) = f\left( y \right) - {P_1}\left( y \right) - \left( {y - a} \right)\left( {y - b} \right)\frac{{f\left( x \right) - {P_1}\left( x \right)}} {{\left( {x - a} \right)\left( {x - b} \right)}}$

over $[a,b]$. Clearly, $g(a)=g(x)=g(b)=0$ and $g$ is of class $C^2([a,b])$. Then by Rolle theorem, there exists a $\xi(x) \in (a,b)$ such that $g''(\xi(x))=0$. Since

$\displaystyle g''\left( y \right) = f''\left( y \right) - 2\frac{{f\left( x \right) - {P_1}\left( x \right)}}{{\left( {x - a} \right)\left( {x - b} \right)}}$

then for each $x \in [a,b]$ fixed, we have

$\displaystyle f\left( x \right) - {P_1}\left( x \right) = \frac{{f''\left( {\xi \left( x \right)} \right)}}{2}\left( {x - a} \right)\left( {x - b} \right)$

which implies that

$\displaystyle\int_a^b {f\left( x \right)dx}= \int_a^b {{P_1}\left( x \right)dx}+ \int_a^b {\frac{{f''\left( {\xi \left( x \right)} \right)}} {2}\left( {x - a} \right)\left( {x - b} \right)dx}$.

By mean value theorem, there exists some $\xi_1 \in [a,b]$ such that

$\displaystyle\int_a^b {\frac{{f''\left( {\xi \left( x \right)} \right)}} {2}\left( {x - a} \right)\left( {x - b} \right)dx}= \frac{{f''\left( {{\xi _1}} \right)}} {2}\int_a^b {\left( {x - a} \right)\left( {x - b} \right)dx}$

which is nothing but

$\displaystyle\frac{{ - 1}} {{12}}{\left( {b - a} \right)^3}f''\left( {{\xi _1}} \right)$.

Okey, we have shown that

$\displaystyle\int_a^b {f\left( x \right)dx}= \int_a^b {\left( {f\left( a \right)\frac{{x - b}} {{a - b}} + f\left( b \right)\frac{{x - a}} {{b - a}}} \right)dx}+ \frac{{ - {{\left( {b - a} \right)}^3}}} {{12}}f''\left( {{\xi _1}} \right)$

i.e.,

$\displaystyle\int_a^b {f\left( x \right)dx}= \frac{{b - a}} {2}\left( {f\left( a \right) + f\left( b \right)} \right) + \frac{{ - {{\left( {b - a} \right)}^3}}} {{12}}f''\left( {{\xi _1}} \right)$.

Now regarding to composite trapezoidal rule with a uniform partition of the interval $[a,b]$, we have

$\displaystyle\int_a^b {f\left( x \right)dx}= \int_{{x_0}}^{{x_1}} {f\left( x \right)dx}+ \int_{{x_1}}^{{x_2}} {f\left( x \right)dx}+ ... + \int_{{x_{n - 1}}}^{{x_n}} {f\left( x \right)dx}$.

which helps us to formulate

$\displaystyle\int_a^b {f\left( x \right)dx}= \sum\limits_{k = 1}^n {\frac{{{x_k} - {x_{k - 1}}}} {2}\left( {f\left( {{x_{k - 1}}} \right) + f\left( {{x_k}} \right)} \right)}+ \sum\limits_{k = 1}^n {\frac{{ - {{\left( {{x_k} - {x_{k - 1}}} \right)}^3}}} {{12}}f''\left( {{\xi _k}} \right)}$

where $\xi_k \in [x_{k-1}, x_k]$ for $k=\overline{1,n}$. Thus,

$\displaystyle\int_a^b {f\left( x \right)dx}= \sum\limits_{k = 1}^n {\frac{{b - a}} {{2n}}\left( {f\left( {{x_{k - 1}}} \right) + f\left( {{x_k}} \right)} \right)}+ \sum\limits_{k = 1}^n {\frac{{ - 1}} {{12}}\frac{{{{\left( {b - a} \right)}^3}}} {{{n^3}}}f''\left( {{\xi _k}} \right)}$.

Clearly,

$\displaystyle\sum\limits_{k = 1}^n {\frac{{ - 1}} {{12}}\frac{{{{\left( {b - a} \right)}^3}}} {{{n^3}}}f''\left( {{\xi _k}} \right)}= \frac{{ - 1}} {{12}}\left( {b - a} \right){h^2}f''\left( \xi\right)$

for some $\xi \in [a,b]$ which yields

$\displaystyle\int_a^b {f\left( x \right)dx}= \sum\limits_{k = 1}^n {\frac{{b - a}} {{2n}}\left( {f\left( {{x_{k - 1}}} \right) + f\left( {{x_k}} \right)} \right)}- \frac{{b - a}} {{12}}{h^2}f''\left( \xi\right)$

which completes our proof.

### The QE – University of Michigan, Department of Mathematics

Filed under: Đề Thi — Ngô Quốc Anh @ 3:20

Each student must pass, or demonstrate a knowledge of, six of the eight core courses. These consist of two-course sequences in

• algebra (593, 594)
• analysis (596, 597)
• applied analysis (556, 572)
• geometry/topology (591, 592)

Each student must pass the Qualifying Review. This consists of written examinations, based on the same syllabuses as the core courses, a course requirement, and a survey by the Doctoral Committee of the student’s record as a graduate student in the Department. The purpose of the Review is to ensure that students have a good knowledge of core graduate mathematics and to evaluate the chances that a student will be able to complete a Ph.D. degree.

The Qualifying Review is conducted three times a year, and should be taken as soon as the student feels ready. It can be taken as many times as necessary with the only stipulation that a student must pass the exams in one area by the beginning of the fourth term in the program, and must complete the entire Review by the beginning of the sixth.

Students are required to take six courses beyond those needed for the Qualifying Review, distributed among at least three of five areas of mathematics.

To ensure greater intellectual breadth, the Graduate School requires that every student must successfully complete four hours of cognate courses before achieving Candidacy. For students in most departments, these must be taken outside the student’s home department, but mathematics students are allowed to take courses within the Mathematics Department under certain restrictions and with Advisor or Doctoral Committee approval. Cognate courses can be taken at any time.

The course requirements listed above should be regarded as the absolute minimum. The Department expects that most students will take more courses distributed so that they achieve a broad background in their specialty and related areas. Students should also participate actively in the Departmental Seminars offered in their area of interest and attend Colloquia since it is there that they can learn about the latest developments and open problems.

### An approximation via Richardson extrapolation

Suppose that  is an approximation to  for every  and that

$M = N(h) + {K_1}{h^2} + {K_2}{h^4} + {K_3}{h^6} + ...$

for some constants , , ,..

Now for given values ,  and  we will produce an  approximation to . Indeed, from

$M = N(h) + {K_1}{h^2} + {K_2}{h^4} + {K_3}{h^6} + ...$

we firstly get

$\begin{gathered} M = N\left( {\frac{h} {2}} \right) + \frac{1} {{{2^2}}}{K_1}{h^2} + \frac{1} {{{2^4}}}{K_2}{h^4} + \frac{1} {{{2^6}}}{K_3}{h^6} + ... \hfill \\ M = N\left( {\frac{h} {4}} \right) + \frac{1} {{{4^2}}}{K_1}{h^2} + \frac{1} {{{4^4}}}{K_2}{h^4} + \frac{1} {{{4^6}}}{K_3}{h^6} + .. \hfill \\ \end{gathered}$

which gives

${2^2}M - M = {2^2}N\left( {\frac{h} {4}} \right) - N\left( {\frac{h} {2}} \right) + \left( {{2^2}\frac{1} {{{4^4}}} - \frac{1} {{{2^2}}}} \right){K_2}{h^4} + \left( {{2^2}\frac{1} {{{4^6}}} - \frac{1} {{{2^6}}}} \right){K_3}{h^6} + ...$

i.e.,

$M = \frac{{{2^2}N\left( {\frac{h} {4}} \right) - N\left( {\frac{h} {2}} \right)}} {{{2^2} - 1}} + \frac{{{2^2}\frac{1} {{{4^4}}} - \frac{1} {{{2^2}}}}} {{{2^2} - 1}}{K_2}{h^4} + \frac{{{2^2}\frac{1} {{{4^6}}} - \frac{1} {{{2^6}}}}} {{{2^2} - 1}}{K_3}{h^6} +...$

Similarly, we obtain

$M = \frac{{{2^2}N\left( {\frac{h} {2}} \right) - N\left( h \right)}} {{{2^2} - 1}} + \frac{{{2^2}\frac{1} {{{2^4}}} - 1}} {{{2^2} - 1}}{K_2}{h^4} + \frac{{{2^2}\frac{1} {{{2^6}}} - 1}} {{{2^2} - 1}}{K_3}{h^6} + ...$

Now we easily get

$\left( {\frac{{{2^2}\frac{1} {{{2^4}}} - 1}} {{{2^2} - 1}} - \frac{{{2^2}\frac{1} {{{4^4}}} - \frac{1} {{{2^2}}}}} {{{2^2} - 1}}} \right)M = \frac{{{2^2}\frac{1} {{{2^4}}} - 1}} {{{2^2} - 1}}\frac{{{2^2}N\left( {\frac{h} {4}} \right) - N\left( {\frac{h} {2}} \right)}} {{{2^2} - 1}} - \frac{{{2^2}\frac{1} {{{4^4}}} - \frac{1} {{{2^2}}}}} {{{2^2} - 1}}\frac{{{2^2}N\left( {\frac{h} {2}} \right) - N\left( h \right)}} {{{2^2} - 1}} + \left( {\frac{{{2^2}\frac{1} {{{2^4}}} - 1}} {{{2^2} - 1}}\frac{{{2^2}\frac{1} {{{4^6}}} - \frac{1} {{{2^6}}}}} {{{2^2} - 1}} - \frac{{{2^2}\frac{1} {{{4^4}}} - \frac{1} {{{2^2}}}}} {{{2^2} - 1}}\frac{{{2^2}\frac{1} {{{2^6}}} - 1}} {{{2^2} - 1}}} \right){K_3}{h^6} + ...$

which implies that

$M = \frac{{ - \frac{1} {{{2^2}}}\frac{{{2^2}N\left( {\frac{h} {4}} \right) - N\left( {\frac{h} {2}} \right)}} {3} + \frac{{1 + {2^2}}} {{{2^6}}}\frac{{{2^2}N\left( {\frac{h} {2}} \right) - N\left( h \right)}} {3}}} {{\frac{{1 + {2^2}}} {{{2^6}}} - \frac{1} {{{2^2}}}}} + \frac{{\frac{{1 + {2^2}}} {{{2^6}}}\frac{{1 + {2^2}}} {{{2^{10}}}} - \frac{{1 + {2^2}}} {{{2^6}}}\frac{{1 + {2^2}}} {{{2^4}}}}} {{\frac{{1 + {2^2}}} {{{2^6}}} - \frac{1} {{{2^2}}}}}{K_3}{h^6} + ...$

For example, for given , $N\left( {\frac{h} {2}} \right) = 1.896119$, $N\left( {\frac{h} {4}} \right) = 1.974232$ one can compute that



In general, Let  be an approximation of  that depends on a positive step size  with an error formula of the form

$A - A(h) = a_0h^{k_0} + a_1h^{k_1} + a_2h^{k_2} + \cdots$

where the  are unknown constants and the  are known constants such that . The exact value sought can be given by

$A = A(h) + a_0h^{k_0} + a_1h^{k_1} + a_2h^{k_2} + \cdots$

which can be simplified with Big O notation to be

$A = A(h)+ a_0h^{k_0} + O(h^{k_1}).$

Using the step sizes  and  the two formulas for  are:

$\begin{gathered} A = A(h) + {a_0}{h^{{k_0}}} + O({h^{{k_1}}})\,, \hfill \\ A = A\left( {\frac{h} {2}} \right) + {a_0}{\left( {\frac{h} {2}} \right)^{{k_0}}} + O({h^{{k_1}}}). \hfill \\ \end{gathered}$

Multiplying the second equation by  and subtracting the first equation gives

$({t^{{k_0}}} - 1)A = {t^{{k_0}}}A\left( {\frac{h} {t}} \right) - A(h) + O({h^{{k_1}}}).$

Which can be solved for  to give

$A = \frac{{{t^{{k_0}}}A\left( {\frac{h} {t}} \right) - A(h)}} {{{t^{{k_0}}} - 1}} + O({h^{{k_1}}}).$

By this process, we have achieved a better approximation of  by subtracting the largest term in the error which was . This process can be repeated to remove more error terms to get even better approximations. A general recurrence relation can be defined for the approximations by

${A_{i + 1}}(h) = \frac{{{2^{{k_i}}}{A_i}\left( {\frac{h} {2}} \right) - {A_i}(h)}} {{{2^{{k_i}}} - 1}}$

such that $A = A_{i+1}(h) + O(h^{k_{i+1}})$ with .