Ngô Quốc Anh

December 30, 2008

Nonexpansive Maps and a fixed point theorem due to Browder, Gohde and Kirk

Filed under: Các Bài Tập Nhỏ, Nghiên Cứu Khoa Học — Ngô Quốc Anh @ 23:41

Let (X,d) be a metric space with C \subset X. Recall that a mapping F: C \to X is non-expansive if F satisfies

d(F(x),F(y) \leqslant d(x,y)

for all x,y \in X.

Theorem. Let C be a nonempty, closed, convex subset of a normed linear space E with F: C \to C nonexpansive and F(C) a subset of a compact set of C. Then F has a fixed point.

Proof. Let x_0 \in C. For n\geqslant 2 define

\displaystyle F_n = \left( 1-\frac{1}{n}\right)F +\frac{1}{n} x_0

Since C is convex and x_0 \in C, we see that F_n: C \to C and it is clear that F_n: C \to C is a contradiction. Therefore each F_n has a unique fixed point x_n \in C. That is

\displaystyle x_n = F_n(x_n)=\left( 1-\frac{1}{n}\right)F(x_n) +\frac{1}{n} x_0.

In addition, since F(C) lies in a compact subset of C, there exist a subsequence S of integers and a u \in C with F(x_n) \to u as n \to \infty in S.

Thus x_n \to u as n \to \infty in S. By continuityF(x_n) \to F(u), as n \to \infty in S which claims that u=F(u).

The main theorem of this topic is a result proved independently by Browder, Gohde and Kirk in 1965. We state it as follows.

Theorem. Let C be a nonempty, closed, bounded, convex set in a (real) Hilbert space H. Then each nonexpansive map F : C \to C has at least one fixed point.

Remark. Notice that uniqueness need not hold as the example, F(x) = x, x\in C = [0, 1], shows.

Remark. In fact the above Theorem, it is enough to assume that H is a uniformly convex Banach space.

In the proof of the above Theorem, we will need the following two technical results.

Claim 1. Let H be a Hilbert space with u, v \in H, and let r, R be constants with 0 \leqslant r \leqslant R. If there exists an x \in H with

\displaystyle \|u-x \| \leq R, \| v -x\| \leq R, \quad \|\frac{u+v}{2} - x\| \geq r

then

\displaystyle \|u-v\| \leqslant 2\sqrt{R^2-r^2}.

Proof. This comes from the so-called parallelogram law, that is,

\displaystyle\|u-v\|^2 = 2\|u-x\|^2 + 2\|v -x\|^2 - \| (u-x)+(v-x)\|^2.

Claim 2. Let H be a Hilbert space, C\subset H a bounded set and F : C\to C a nonexpansive map. Suppose x \in C, y \in C and a = \frac{x + y}{2}\in C. Let \delta (C) denote the diameter of C and let \varepsilon \leqslant \delta (C) with \|x-F(x)\| \leqslant \varepsilon and \|y - F(y)\|\leqslant \varepsilon. Then

\displaystyle\|a-F(a)\| \leq 2\sqrt{\varepsilon} \sqrt{2\delta(C)}.

Proof of main theorem. Assume that 0\in C. (A modified argument from the one given below holds for any x_0 \in C, therefore for simplicity we let x_0 = 0.) Also assume that F(0) \ne 0 (otherwise we are finished). For each n \geqslant 2, notice that

\displaystyle F_n = \left( 1-\frac{1}{n}\right)F : C \to C

is a contradiction. Now the first theorem guarantees that there exists a unique x_n \in C with

\displaystyle x_n= F_n(x_n)=\left( 1- \frac{1}{n}\right) F(x_n).

Thus,

\displaystyle \|x_n - F(x_n) \| = \frac{1}{n} \|F(x_n)\| \leq \frac{1}{n} \delta(C).

For each n \geqslant 2, let

\displaystyle {Q_n} = \left\{ {x \in C:x - F(x) \leqslant \frac{1}{n}\delta (C)} \right\}.

Now

\displaystyle Q_2 \supseteq Q_3 \supseteq ... \supseteq Q_n \dots

is a decreasing sequence of nonempty closed sets. Let

\displaystyle {d_n} = \inf \left\{ {\left\| x \right\|:x \in {Q_n}} \right\}

and since the Q_ns are decreasing we have

\displaystyle d_2 \leq d_3 \leq... \leq d_n \leq...

with d_i \leqslant \delta (C) for each i \geqslant 2. Consequently, {d_n} \uparrow d with d \leqslant \delta (C).

Next let

\displaystyle A_n =Q_{8n^2} \cap \overline{B(0, d+1/n)},

where

\displaystyle B\left( {0,d + \frac{1}{n}} \right) = \left\{ {x \in H:\left\| x \right\| < d + \frac{1}{n}} \right\}.

Now A_n is a decreasing sequence of closed, nonemplty sets. We now show that

\displaystyle\lim_{n\to\infty} \delta(A_n)=0.

To see this, let . Then

\displaystyle \|u-0\| \leq d+\frac{1}{n}, \quad \|v-0\| \leq d+\frac{1}{n}.

Also since we have

\displaystyle \|u -F(u) \| \leq \frac{1}{8n^2} \delta(C), \quad \| v-F(v)\| \leq \frac{1}{8n^2} \delta(C).

Thus

\displaystyle\left\| {\frac{{u + v}}{2} - F\left( {\frac{{u + v}}{2}} \right)} \right\| \leqslant 2\sqrt {2\delta (C)} \sqrt {\frac{1}{{8{n^2}}}\delta (C)} = \frac{1}{n}\delta (C).

This implies

\displaystyle \frac{u+v}{2} \in Q_n

and

\displaystyle \left\| \frac{u+v}{2} - 0\right\| \geq d_n.

It is easy to check that r : H \to \overline{B}_r is non-expansive. As a result

r \circ F: \overline{B}_r \to \overline{B}_r

is a non-expansive map. This guarantees that there exists x \in \overline{B}_r with r(F(x))=x. If F(x) \in \overline{B}_r, then

x=r(F(x))=F(x)

and F has a fixed point. If F(x) does not belong to \overline{B}_r then

\displaystyle x=r(F(x)) = r \frac{F(x)}{\| F(x) \|} = \lambda F(x)

with

\displaystyle\lambda = \frac{r}{\|F(x)\|} <1.

Source: Ravi P. Agarwal, Maria Meehan, Donal O’Regan, Fixed point theory and applications, Cambridge University Press, 2001.

December 29, 2008

A fixed point theorem

Filed under: Các Bài Tập Nhỏ, Nghiên Cứu Khoa Học — Ngô Quốc Anh @ 17:06

Let (X,d) be a complete metric space and let F: X\to X be such that F^N : X \to X is a contraction for some positive integer N. Show that F has a unique fixed point u \in X and that for each x \in X, \mathop {\lim }\limits_{n \to \infty } {F^n}\left( x \right) = u.

Proof.
Since F^N : X \to X is a contraction, then F^N has a fixed point, say u_0, i.e., F^N u_0=u_0. Note that

\displaystyle d\left( {F{u_0},{u_0}} \right) = d\left( {{{\left( {{F^N}} \right)}^n}F{u_0},{{\left( {{F^N}} \right)}^n}{u_0}} \right) \leq {k^n}d\left( {F{u_0},{u_0}} \right).

Since k<1 then d\left( {F{u_0},{u_0}} \right)=0. In other word, u_0 is a fixed point of F.

To prove the uniqueness, assume $u’_0$ is also a fixed point of F. Then both $u_0$ and $u’_0$ are fixed points of F^N which implies that u_0 \equiv u'_0 due to the uniqueness of fixed point of a contractive mapping.

December 22, 2008

The LaTeX Font Catalogue

Filed under: Linh Tinh — Ngô Quốc Anh @ 23:50

Link sau có rất nhiều font để sử dụng trong TeX http://www.tug.dk/FontCatalogue/allfonts.html. Để sử dụng chúng, các bạn làm như sau:

  • Chọn một font nào đó trong danh sách bằng cách clicj vào tên font hoặc ví dụ minh họa ngay bên dưới, ví dụ tôi chọn font sau Auriocus Kalligraphicus

Auriocus Kalligraphicus sample

  • Trong trang tiếp theo, các bạn chọn link [LaTeX source of PDF sample] để download file TeX ví dụ về xem.
  • Mở file ví dụ và typeset và quan sát kết quả.

auriocuskalligraphicus

Chúc thành công.

December 16, 2008

Inkscape, a real SVG holder…

Filed under: Linh Tinh — Ngô Quốc Anh @ 1:46

Nếu thường xuyên sử dụng thư viện mã nguồn mở wikipedia để học tập và tra cứu, nếu để ý chắc hẳn các bạn rất hay gặp định dạng file SVG trong các hình ví dụ. Vậy định dạng SVG là gì và mục đích của định dạng SVG là để làm gì?

Tôi xin trích một số thông tin được lấy ở http://vi.wikipedia.org/wiki/SVG về chuẩn SVG (chi tiết hơn các bạn có thể đọc ở phiên bản tiếng Anh tại địa chỉ sau http://en.wikipedia.org/wiki/SVG).

SVG (viết tắt của Scalable Vector Graphics) là một ngôn ngữ đánh dấu (markup language) XML và dùng để miêu tả các hình ảnh đồ họa véc tơ hai chiều, tĩnh và hoạt hình, thường dành cho ứng dụng trên các trang mạng. SVG thuộc tiêu chuẩn mở và được quản lí bởi tổ chức World Wide Web Consortium, một tổ chức quản lý nhiều chuẩn khác như HTML, XHTML… Các tập tin có đuôi “.svg” được mặc định hiểu là tập tin SVG. SVG có thể phóng to thu nhỏ mọi kích cỡ mà không giảm chất lượng hình ảnh. Vì thế, nó được dùng nhiều trong các bản đồ, sơ đồ.Đối thủ chính của SVGMacromedia Flash, nhưng Macromedia Flash không phải là một chuẩn mở.

Ưu điểm:

  • Vì là định dạng đồ họa vectơ, lợi điểm của SVG là khả năng hiển thị tốt ở mọi kích cỡ và độ phân giải. Với một kích thước tương tự, một tập tin SVG có thể chứa nhiều thông tin hơn là một tập tin định dạng nhị phân khác (GIF, PNG, …).
  • SVG là một chuẩn mở, nó cho phép việc tùy biến theo mục đích sử dụng một cách dễ dàng. Các hình ảnh SVG có thể được dễ dàng sửa chữa và phát triển sau này, khác với đồ họa mảng thường là sản phẩm cuối cùng của các xử lý ảnh, không chứa mã nguồn các lớp ảnh.
  • Các tập tin SVG ở dạng văn bản, việc chỉnh sửa có thể thực hiện bằng các trình soạn thảo đơn giản nhất.

Nhược điểm:

  • SVG là ngôn ngữ không được thiết kế để sửa chữa trực tiếp trên mã nguồn. Để tạo ra các hình ảnh SVG nói chung, cần dùng các công cụ hỗ trợ.
  • Dù SVG có thể là một lựa chọn cho hình ảnh của các trang mạng trong tương lai không xa, nó vẫn còn khá mới mẻ và cần sự hỗ trợ từ các trình duyệt mạng. Hiện nay Mozilla Firefox đã hỗ trợ tương đối đầy đủ cho SVG, tuy nhiên Internet Explorer và một số trình duyệt khác cần có plug-in đặt riêng lẻ.

Ví dụ minh họa và so sánh giữa chuẩn SVG và các chuẩn đồ họa thông dụng hiện nay:

bitmap_vs_svg
Các bạn có thể thấy chất lượng ảnh SVG tốt hơn rất nhiều so với các định dạng còn lại.

smiley

Các bạn có tìn được hình mặt cười trên là từ file SVG mà ra hay không?

Phần mềm hỗ trợ: Sau một thời gian tìm hiểu tôi phát hiện được Inkscape một phần mềm miễn phí hỗ trợ SVG hoàn hảo. Trang chủ ở đây http://www.inkscape.org.

Màn hình sau khi khởi động của Inkscape khá lằng nhằng.

inkscape1

Inkscape hỗ trợ người dùng vẽ tự do như các chương trình vẽ chuyên nghiệp khác. Sau khi hoàn thành, người sử dụng chỉ việc lưu lại, mặc định là file SVG.

Làm thế nào để sử dụng file SVG cho các mục đích khác: Với Inkscape, các bạn cứ yên tâm.

  • Để lưu công việc bạn đang làm và xuất kết quả thành file ảnh, các bạn sử dụng menu File\Export Bitmap. Sau khi export, các bạn sẽ nhận được file PNG, từ file PNG các bạn có thể dễ dàng chuyển sang các định dạng khác như GIF, JPG, BMP,..
  • Để sử dụng được trong TeX, các bạn phải chuyển file SVG sang định dạng PS/EPS. Các bạn chỉ cần vào File\Save as là được. Nếu bạn đang sử dụng gói PSTricks trong TeX, có thể export trực tiếp sang tương tự như trên.

Và đây là kết quả minh hoạ

inkscape2

Chúc thành công!

December 2, 2008

Differential and Integral Equations through Practical Problems and Exercises (Texts in the Mathematical Sciences)

Filed under: Sách Hay — Ngô Quốc Anh @ 22:27

http://217.205.197.220/borders-media/BookCoverThumbnail/9780792318903/differential-and-integral-equations-through-practical-problems-and-exercises-(texts-in-the-mathematical-sciences).jpg?w=200&h=1000

This volume presents a valuable and comprehensive collection of problems and exercises, together with guidelines and worked solutions, of a wide range of the most important commonly occurring differential and integral equations.

The book is divided into two parts. Part I, which comprises eight chapters, contains the problems and exercises, and Part II, having eight corresponding chapters, presents the worked solutions. The various chapters deal, respectively, with: (1) the classical type of differential equations of first and higher order; (2) problems relating to existence and uniqueness theorems; (3) linear differential equations; (4) the method of the Laplace transform; (5) integral and integro-differential equations; (6) numerical and approximation methods; and (7) first-order partial differential equations. The final chapter (8) presents a miscellaneous selection of problems and exercises dealing with the deepest areas of differential, integral and partial differential equations.

Many of the problems discussed are original, and all have been tried and tested in a teaching environment.
This volume provides an invaluable guide to the solving of differential and integral equations and can be recommended to all researchers, students and teachers, whose work involves this fundamental aspect of mathematics.

  • Hardcover: 412 pages
  • Publisher: Springer; 1 edition (August 31, 1992)
  • Language: English
  • ISBN-10: 0792318900
  • ISBN-13: 978-0792318903
  • Product Dimensions: 9.2 x 6.1 x 1 inches

Tôi có bản copy của sách này…

Blog at WordPress.com.