01204472 ภาคต้น 2555

การคำนวณเชิงตัวเลข เป็นหนึ่งในการประยุกต์ใช้งานหลักของคอมพิวเตอร์ การคำนวณเชิงตัวเลขมีขอบเขตในการประยุกต์ใช้ที่กว้างขวาง (ดูรายการด้านล่าง) ในวิชานี้ เราจะศึกษาทฤษฎีและอัลกอริทึมเกี่ยวกับเวกเตอร์และเมตริกซ์ ซึ่งนอกจากจะเป็นพื้นฐานในการทำความเข้าใจเทคนิคต่าง ๆ เกี่ยวกับการคำนวณเชิงตัวเลขแล้ว เนื้อหาในส่วนนี้ยังเกี่ยวข้องโดยตรงกับการประยุกต์ใช้งานในด้านต่าง ๆ รวมทั้งอัลกอริทึมสำหรับการหาค่าที่ดีที่สุดซึ่งเราจะได้ศึกษาทฤษฎีและอัลกอริทึมในวิชานี้

นอกจากนี้เรายังจะสัมผัสเนื้อหามาตรฐานของรายวิชาการคำนวณเชิงตัวเลข เช่น การหาค่าประมาณการ การหาอนุพันธ์ การอินทิเกรตเชิงตัวเลข การเข้าสมการอนุพันธ์ และการปรับหาเส้นโค้งที่เหมาะสม

ในหัวข้อต่าง ๆ เราจะศึกษาทั้งทฤษฎีและการนำไปประยุกต์ใช้

ติดต่อสื่อสาร: Group 01204472/55 Numerical Computation บน facebook

การวัดผล

• การบ้าน 20%
• สอบกลางภาค 20% สอบปลายภาค 20%
• โครงงานเล็ก 2 โครงงาน โครงงานละ 20%

หัวข้อ

เนื้อหาแต่ละสัปดาห์จะโพสที่นี่ อย่างไรก็ตาม ถ้าต้องการดูภาพรวมของเนื้อหาในรายวิชากรุณาดูได้ที่หัวข้อเนื้อหาเชิงทฤษฎีโดยรวม

หัวข้อละเอียด

• 12 มิ.ย. แนะนำเนื้อหาและแนวคิดพื้นฐานผ่านทางปัญหาการวาดกราฟ (graph drawing) ด้วยสปริงโมเดล
  • ตัวอย่างการพล็อตกราฟด้วย matplotlib

• 14 มิ.ย. ทดลองเกี่ยวกับขีดจำกัดของการคำนวณด้วยจำนวนจริงบนคอมพิวเตอร์ รายละเอียดการทดลอง
  • มาตรฐานการเก็บจำนวนจริง IEEE 754

• 19 มิ.ย. Vectors (ใช้ Lecture 1 จากเว็บวิชา EE103)
  • Vector space model (จาก วิกิพีเดีย)

• 21 มิ.ย. ทดลองเกี่ยวกับเวกเตอร์ รายละเอียดการทดลอง
  • The Perceptron Algorithm

• 26 มิ.ย. Matrices (ใช้ Lecture 2 จากเว็บวิชา EE103)

• 28 มิ.ย. ทดลองเกี่ยวกับเมตริกซ์

• 3 ก.ค. Linear equations, เกริ่น Theory of linear equations (ใช้ Lecture 3 และ 4 จากเว็บวิชา EE103)

• 5 ก.ค.:
  • Theory of linear equations (ต่อ)
  • ทดลองเกี่ยวกับเมตริกซ์ (ต่อ)

• 19 ก.ค.:
  • Guest speaker
  • Theory of linear equations.

• 24 ก.ค.: Cholesky factorization
• 26 ก.ค.: LU factorization
• 31 ก.ค.: Linear least-square
• 2 ส.ค.: QR factorization
• 14 ส.ค.: Least-norm problems
• 16 ส.ค.: Nonlinear equations
• 21 ส.ค.: Unconstrained optimization
• 23 ส.ค.: การทดลองเกี่ยวกับการหารากของสมการ
• 4 ก.ย.: Singular Value Decomposition
• 6 ก.ย.: การทดลองเกี่ยวกับ SVD
• 11 ก.ย.: SVD ต่อ
• 13 ก.ย.: SVD ต่อ
• 18 ก.ย.: Linear optimization (บทที่ 18 ที่เว็บ EE103)
• 20 ก.ย.: Problem condition and numerical stability (บทที่ 15 ที่เว็บ EE103)

เนื้อหาเชิงทฤษฎีโดยรวม

ถึงแม้วิชานี้จะเน้นการปฏิบัติ แต่เนื้อหาทางทฤษฎีหลายอย่างก็ยังจำเป็นมาก

• Introductory concepts (approximation errors, Taylor's theorem, computer arithemetic)
• Matrix theory (vectors, matrics, linear equations) (เนื้อหาจาก UCLA EE103)
• Matrix algorithms (Choleskey factorization, LU factorization, Least square problems, QR fatorization) (เนื้อหาจาก UCLA EE103)
• Nonlinear equations and optimization (เนื้อหาจาก UCLA EE103)

การบ้าน

ถ้าการบ้านข้อใดมีเขียน (Vx.y) แสดงว่านำมาจากปัญหาท้ายบทข้อที่ y จากบทที่ x จาก reader ของวิชา EE103 ซึ่งสามารถดาวน์โหลดต้นฉบับภาษาอังกฤษได้จากลิงก์

การบ้าน 1 (กำหนดส่ง 31 ก.ค. 2555)

1. (V1.4) ให้ $n$-vector $x$ โดยที่ $n=2m-1$ และ $m\geq 1$ เราจะเรียก $x_{m}$ ว่าเป็น middle element ของ $x$ เรากำหนดให้

$f(x)=x_{m}-{\frac {1}{n}}\sum _{i=1}^{n}x_{i}$

แทนความแตกต่างระหว่าง middle element กับค่าเฉลี่ยของ element ใน $x$ จงเขียนฟังก์ชัน $f$ ในรูป $f(x)=a^{T}x$ เมื่อ $a$ เป็น $n$-vector

2. (V1.15) จงใช้ Cauchy-Schwarz inequality เพื่อพิสูจน์ว่า

$-{\frac {1}{\sqrt {n}}}\|x\|\leq {\frac {1}{n}}\sum _{i=1}^{n}x_{i}\leq {\frac {1}{\sqrt {n}}}\|x\|$

สำหรับทุก ๆ $n$-vector $x$ นั่นคือค่าเฉลี่ยของทุก ๆ element ของเวกเตอร์ มีค่าอยู่ระหว่าง $\pm 1/{\sqrt {n}}$เท่าของ norm ของมัน

ให้อธิบายด้วยว่าเมื่อใดที่ upperbound ดังกล่าวมีค่าเท่ากับค่าเฉลี่ย และเมื่อใดที่ lowerbound มีค่าเท่ากับค่าเฉลี่ย

3. (V2.6) Projection ของเวกเตอร์ $x$ บนเวกเตอร์ $y$ ให้ $y$ เป็น $n$-vector เราจะนิยามฟังก์ชัน $f:{\mathbf {R} }^{n}\rightarrow {\mathbf {R} }^{n}$ ดังนี้

$f(x)={\frac {x^{T}y}{\|y\|^{2}}}y$

เราทราบว่าฟังก์ชันดังกล่าวคือ projection ของ $x$ บนเวกเตอร์ $y$ ฟังก์ชัน $f$ เป็น linear function หรือไม่?

(ถ้าตอบว่าใช่ ให้ระบุ $n\times n$ เมตริกซ์ $A$ ที่ $f(x)=Ax$ ถ้าตอบว่าไม่ใช่ ให้แสดงตัวอย่างที่แสดงว่า $f$ ไม่มีคุณสมบัติ linearity $f(\alpha u+\beta v)=\alpha f(u)+\beta f(v)$)

4. (V3.9) เมตริกซ์จัสตุรัส $A$ จะถูกเรียกว่า diagonal matrix ถ้า element ทั้งหมดที่อยู่นอกเส้นแทยงมุมมีค่าเป็น 0, นั่นคือ $a_{ij}=0$ สำหรับทุก ๆ $i\neq j$

(a) จงหา range และ nullspace ของเมตริกซ์ด้านล่าง

$\left[{\begin{array}{cccc}1&0&0&0\\0&-2&0&0\\0&0&0&0\\0&0&0&3\end{array}}\right]$

(b) เมื่อใดที่ diagonal matrix จะ invertible?

5. (V3.12) ให้ $A$ เป็น nonsingular matrix ที่ order $n$ พิจารณาเมตริกซ์ $M$ ขนาด $2n\times 2n$ ที่นิยามเป็น

$\left[{\begin{array}{cc}A&A+A^{-T}\\A&A\end{array}}\right]$

(a) แสดงว่า $M$ เป็น nonsingular โดยแสดงว่าถ้า $Mx=0$ แล้ว $x=0$

(b) จงหา inverse ของ $M$    ในการทำข้อนี้ ให้เขียน $M^{-1}$ ในรูปของ block matrix:

$\left[{\begin{array}{cc}W&X\\Y&Z\end{array}}\right]$

โดยที่แต่ละ block มีมิติ $n\times n$ จากนั้นหาค่าของเมตริกซ์ $W,X,Y,Z$ จากเงื่อนไขว่า $MM^{-1}=I$

การบ้าน 2 (กำหนดส่ง 16 ส.ค. 2555)

1. (V6.1) คำนวณหา Cholesky factorization ของเมตริกซ์ สามารถใช้คอมพิวเตอร์ในการคำนวณได้

$A=\left[{\begin{array}{cccc}4&6&2&-6\\6&34&2&-9\\2&3&2&-1\\-6&-9&-1&38\end{array}}\right]$

2. (V6.2) พิจารณาเมตริกซ์ $A$ ต่อไปนี้ทีละข้อ จากนั้นให้หาเงื่อนไขของค่า $a$ ที่ทำให้เมตริกซ์ดังกล่าวเป็น positive definite. ในการหาเงื่อนไขดังกล่าว ให้ factor $A$ จากนั้นให้หาเงื่อนไขของ $a$ ที่ทำให้การแยก factor สามารถกระทำได้

(a) $A=\left[{\begin{array}{cc}1&a\\a&1\end{array}}\right]$

(b) $A=\left[{\begin{array}{ccc}1&a&0\\a&1&a\\0&a&1\end{array}}\right]$

(c) $A=\left[{\begin{array}{cc}I&aI\\aI&I\end{array}}\right]$, เมื่อ $I$ เป็น identity matrix ขนาด $n\times n$

3. (V7.5) คำนวณหา LU factorization โดยใช้ฟังก์ชัน scipy.linalg.lu สังเกตผลลัพธ์ที่ได้

$A=\left[{\begin{array}{cccc}-3&2&0&3\\6&-6&0&-12\\-3&6&-1&16\\12&-14&-2&-25\end{array}}\right]$

4. (V7.7) สมมติว่าคุณต้องแก้ linear equations ทั้งหมด $K$ ชุด ดังนี้

$AD_{1}Bx_{1}=b_{1}$

$AD_{2}Bx_{2}=b_{2}$, จนถึง

$AD_{K}Bx_{K}=b_{K}$

โดยคุณได้รับเมตริกซ์ $A$ และ $B$ ขนาด $n\times n$ ที่เป็น nonsingular เมตริกซ์ $D_{k}$ เป็น diagonal matrix ที่สมาชิกบนเส้นทะแยงมุมมีค่าไม่เป็นศูนย์ นอกจากนี้ คุณก็จะได้รับพจน์ด้านขวา $b_{k}\in {\mathbf {R} }^{n}$

ตัวแปรที่คุณต้องหาคำตอบคือ $n$-vectors $x_{k}$, สำหรับ $k=1,\ldots ,K$

อธิบายวิธีการที่ใช้หาค่าของ $x_{k}$ สำหรับทุก ๆ $k=1,\ldots ,K$ ให้เปรียบเทียบเวลาที่ใช้ กับการคำนวณหาคำตอบโดยตรงด้วยวิธีการธรรมดา

สำหรับข้อต่อไปนี้ จะทยอยใส่คำแปลให้ตามเหมาะสม

5. ทำข้อ V7.12

6. ทำข้อ V8.1

7. ทำข้อ V8.3

ซอฟต์แวร์

• Python, Matplotlib, NumPy, PyLab

รายการการประยุกต์ใช้

• ทฤษฎีเมตริกซ์
  • Machine learning / AI: ใช้เพื่อโมเดลเอกสารและแสดงความสัมพันธ์ระหว่างเอกสาร (Vector space model), เทคนิคที่เกี่ยวข้องกับ eigenvalue เช่น SVD และ PCA, Collaborative filtering
• การหาค่าที่ดีที่สุด
  • Machine learning / AI: ใช้ในการเทรนเครื่องจักรการเรียนรู้ เช่น neural networks หรือ Support vector machine
  • Computer graphics: การประยุกต์ใช้การหาค่าที่ดีที่สุดในปัญหาต่าง ๆ ดูตัวอย่างจากรายวิชาต่อไปนี้: Generating Natural Human Motion Physically Based Character Animation หรือเรื่องของ optimization based synthesis
  • หุ่นยนต์
  • เครือข่ายคอมพิวเตอร์

ลิงก์ภายนอก

• UCLA EE103 - Applied Numerical Computing