ผลต่างระหว่างรุ่นของ "01204472 ภาคต้น 2555"

จาก Theory Wiki
ไปยังการนำทาง ไปยังการค้นหา
 
(ไม่แสดง 32 รุ่นระหว่างกลางโดยผู้ใช้ 2 คน)
แถว 18: แถว 18:
 
* '''12 มิ.ย.''' แนะนำเนื้อหาและแนวคิดพื้นฐานผ่านทางปัญหาการวาดกราฟ (graph drawing) ด้วยสปริงโมเดล
 
* '''12 มิ.ย.''' แนะนำเนื้อหาและแนวคิดพื้นฐานผ่านทางปัญหาการวาดกราฟ (graph drawing) ด้วยสปริงโมเดล
 
** [[01204472/ตัวอย่าง matplotlib|ตัวอย่างการพล็อตกราฟด้วย matplotlib]]
 
** [[01204472/ตัวอย่าง matplotlib|ตัวอย่างการพล็อตกราฟด้วย matplotlib]]
 +
 
* '''14 มิ.ย.''' ทดลองเกี่ยวกับขีดจำกัดของการคำนวณด้วยจำนวนจริงบนคอมพิวเตอร์ [[01204472/การทดลองการคำนวณจำนวนจริง|รายละเอียดการทดลอง]]
 
* '''14 มิ.ย.''' ทดลองเกี่ยวกับขีดจำกัดของการคำนวณด้วยจำนวนจริงบนคอมพิวเตอร์ [[01204472/การทดลองการคำนวณจำนวนจริง|รายละเอียดการทดลอง]]
 
** [http://en.wikipedia.org/wiki/IEEE_754-2008 มาตรฐานการเก็บจำนวนจริง IEEE 754]
 
** [http://en.wikipedia.org/wiki/IEEE_754-2008 มาตรฐานการเก็บจำนวนจริง IEEE 754]
 +
 
* '''19 มิ.ย.''' Vectors (ใช้ Lecture 1 จากเว็บวิชา [http://www.ee.ucla.edu/~vandenbe/ee103.html EE103])
 
* '''19 มิ.ย.''' Vectors (ใช้ Lecture 1 จากเว็บวิชา [http://www.ee.ucla.edu/~vandenbe/ee103.html EE103])
 
** [http://en.wikipedia.org/wiki/Vector_space_model Vector space model] (จาก วิกิพีเดีย)
 
** [http://en.wikipedia.org/wiki/Vector_space_model Vector space model] (จาก วิกิพีเดีย)
 +
 
* '''21 มิ.ย.''' ทดลองเกี่ยวกับเวกเตอร์ [[01204472/การทดลองเกี่ยวกับเวกเตอร์|รายละเอียดการทดลอง]]
 
* '''21 มิ.ย.''' ทดลองเกี่ยวกับเวกเตอร์ [[01204472/การทดลองเกี่ยวกับเวกเตอร์|รายละเอียดการทดลอง]]
 
** [[01204472/perceptron algorithm|The Perceptron Algorithm]]
 
** [[01204472/perceptron algorithm|The Perceptron Algorithm]]
 +
 
* '''26 มิ.ย.''' Matrices (ใช้ Lecture 2 จากเว็บวิชา [http://www.ee.ucla.edu/~vandenbe/ee103.html EE103])
 
* '''26 มิ.ย.''' Matrices (ใช้ Lecture 2 จากเว็บวิชา [http://www.ee.ucla.edu/~vandenbe/ee103.html EE103])
−
* '''28 มิ.ย.'''  
+
 
−
** ทดลองเกี่ยวกับเมตริกซ์
+
* '''28 มิ.ย.''' [[01204472/การทดลองเกี่ยวกับเมตริกซ์|ทดลองเกี่ยวกับเมตริกซ์]]
−
** เกริ่น Linear equations (ใช้ Lecture 3 จากเว็บวิชา [http://www.ee.ucla.edu/~vandenbe/ee103.html EE103])
+
 
 +
* '''3 ก.ค.''' Linear equations, เกริ่น Theory of linear equations (ใช้ Lecture 3 และ 4 จากเว็บวิชา [http://www.ee.ucla.edu/~vandenbe/ee103.html EE103])
 +
 
 +
* '''5 ก.ค.''':
 +
** Theory of linear equations (ต่อ)
 +
** [[01204472/การทดลองเกี่ยวกับเมตริกซ์|ทดลองเกี่ยวกับเมตริกซ์]] (ต่อ)
 +
 
 +
* '''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 ส.ค.''': [[01204472/การทดลองเกี่ยวกับการหารากของสมการ|การทดลองเกี่ยวกับการหารากของสมการ]]
 +
* '''4 ก.ย.''': [https://en.wikipedia.org/wiki/Singular_value_decomposition Singular Value Decomposition]
 +
* '''6 ก.ย.''': [[01204472/การทดลองเกี่ยวกับ SVD|การทดลองเกี่ยวกับ SVD]]
 +
* '''11 ก.ย.''': SVD ต่อ
 +
* '''13 ก.ย.''': SVD ต่อ
 +
* '''18 ก.ย.''': Linear optimization (บทที่ 18 ที่เว็บ [http://www.ee.ucla.edu/~vandenbe/ee103.html EE103])
 +
* '''20 ก.ย.''': Problem condition and numerical stability (บทที่ 15 ที่เว็บ [http://www.ee.ucla.edu/~vandenbe/ee103.html EE103])
  
 
=== เนื้อหาเชิงทฤษฎีโดยรวม ===
 
=== เนื้อหาเชิงทฤษฎีโดยรวม ===
แถว 35: แถว 63:
 
* Matrix algorithms (Choleskey factorization, LU factorization, Least square problems, QR fatorization) (เนื้อหาจาก [http://www.ee.ucla.edu/~vandenbe/ee103.html UCLA EE103])
 
* Matrix algorithms (Choleskey factorization, LU factorization, Least square problems, QR fatorization) (เนื้อหาจาก [http://www.ee.ucla.edu/~vandenbe/ee103.html UCLA EE103])
 
* Nonlinear equations and optimization (เนื้อหาจาก [http://www.ee.ucla.edu/~vandenbe/ee103.html UCLA EE103])
 
* Nonlinear equations and optimization (เนื้อหาจาก [http://www.ee.ucla.edu/~vandenbe/ee103.html UCLA EE103])
 +
 +
== การบ้าน ==
 +
 +
ถ้าการบ้านข้อใดมีเขียน (Vx.y) แสดงว่านำมาจากปัญหาท้ายบทข้อที่ y จากบทที่ x จาก reader ของ[http://www.ee.ucla.edu/~vandenbe/ee103.html วิชา EE103] ซึ่งสามารถดาวน์โหลดต้นฉบับภาษาอังกฤษได้จากลิงก์
 +
 +
=== การบ้าน 1 (กำหนดส่ง 31 ก.ค. 2555) ===
 +
 +
'''1.''' (V1.4) ให้ <math>n</math>-vector <math>x</math> โดยที่ <math>n=2m-1</math>  และ <math>m\geq 1</math>  เราจะเรียก <math>x_m</math> ว่าเป็น ''middle element ของ <math>x</math>''  เรากำหนดให้
 +
 +
<math>f(x) = x_m - \frac{1}{n}\sum_{i=1}^n x_i</math>
 +
 +
แทนความแตกต่างระหว่าง middle element กับค่าเฉลี่ยของ element ใน <math>x</math>  จงเขียนฟังก์ชัน <math>f</math> ในรูป <math>f(x)=a^T x</math> เมื่อ <math>a</math> เป็น <math>n</math>-vector
 +
 +
'''2.''' (V1.15) จงใช้ Cauchy-Schwarz inequality เพื่อพิสูจน์ว่า
 +
 +
<math>-\frac{1}{\sqrt{n}}\|x\| \leq \frac{1}{n}\sum_{i=1}^n x_i \leq \frac{1}{\sqrt{n}}\|x\|</math>
 +
 +
สำหรับทุก ๆ <math>n</math>-vector <math>x</math>  นั่นคือค่าเฉลี่ยของทุก ๆ element ของเวกเตอร์ มีค่าอยู่ระหว่าง <math>\pm 1/\sqrt{n}</math>เท่าของ norm ของมัน
 +
 +
ให้อธิบายด้วยว่าเมื่อใดที่ upperbound ดังกล่าวมีค่าเท่ากับค่าเฉลี่ย  และเมื่อใดที่ lowerbound มีค่าเท่ากับค่าเฉลี่ย
 +
 +
'''3.''' (V2.6) ''Projection ของเวกเตอร์ <math>x</math> บนเวกเตอร์ <math>y</math>''  ให้ <math>y</math> เป็น <math>n</math>-vector เราจะนิยามฟังก์ชัน <math>f:{\mathbf R}^n \rightarrow {\mathbf R}^n</math> ดังนี้
 +
 +
<math>f(x) = \frac{x^T y}{\|y\|^2} y</math>
 +
 +
เราทราบว่าฟังก์ชันดังกล่าวคือ projection ของ <math>x</math> บนเวกเตอร์ <math>y</math>  ฟังก์ชัน <math>f</math> เป็น linear function หรือไม่?
 +
 +
(ถ้าตอบว่าใช่ ให้ระบุ <math>n\times n</math> เมตริกซ์ <math>A</math> ที่ <math>f(x) = Ax</math> ถ้าตอบว่าไม่ใช่ ให้แสดงตัวอย่างที่แสดงว่า <math>f</math> ไม่มีคุณสมบัติ linearity <math>f(\alpha u + \beta v)=\alpha f(u) + \beta f(v)</math>)
 +
 +
'''4.''' (V3.9) เมตริกซ์จัสตุรัส <math>A</math> จะถูกเรียกว่า diagonal matrix ถ้า element ทั้งหมดที่อยู่นอกเส้นแทยงมุมมีค่าเป็น 0, นั่นคือ <math>a_{ij}=0</math> สำหรับทุก ๆ <math>i\neq j</math>
 +
 +
(a) จงหา range และ nullspace ของเมตริกซ์ด้านล่าง
 +
 +
<math>\left[\begin{array}{cccc}
 +
1&0&0&0\\
 +
0&-2&0&0\\
 +
0&0&0&0\\
 +
0&0&0&3
 +
\end{array}\right]</math>
 +
 +
(b) เมื่อใดที่ diagonal matrix จะ invertible?
 +
 +
'''5.''' (V3.12) ให้ <math>A</math> เป็น nonsingular matrix ที่ order <math>n</math> พิจารณาเมตริกซ์ <math>M</math> ขนาด <math>2n\times 2n</math> ที่นิยามเป็น
 +
 +
<math>\left[\begin{array}{cc}
 +
A&A+A^{-T}\\
 +
A&A
 +
\end{array}\right]</math>
 +
 +
(a) แสดงว่า <math>M</math> เป็น nonsingular โดยแสดงว่าถ้า <math>Mx=0</math> แล้ว <math>x=0</math>
 +
 +
(b) จงหา inverse ของ <math>M</math> &nbsp;&nbsp; ในการทำข้อนี้ ให้เขียน <math>M^{-1}</math> ในรูปของ block matrix:
 +
 +
<math>\left[\begin{array}{cc}
 +
W&X\\
 +
Y&Z
 +
\end{array}\right]</math>
 +
 +
โดยที่แต่ละ block มีมิติ <math>n\times n</math> จากนั้นหาค่าของเมตริกซ์ <math>W,X,Y,Z</math> จากเงื่อนไขว่า <math>MM^{-1}=I</math>
 +
 +
=== การบ้าน 2 (กำหนดส่ง 16 ส.ค. 2555) ===
 +
 +
'''1.''' (V6.1) คำนวณหา Cholesky factorization ของเมตริกซ์  สามารถใช้คอมพิวเตอร์ในการคำนวณได้
 +
 +
<math>
 +
A=\left[
 +
\begin{array}{cccc}
 +
4&6&2&-6\\
 +
6&34&2&-9\\
 +
2&3&2&-1\\
 +
-6&-9&-1&38
 +
\end{array}
 +
\right]
 +
</math>
 +
 +
'''2.''' (V6.2) พิจารณาเมตริกซ์ <math>A</math> ต่อไปนี้ทีละข้อ จากนั้นให้หาเงื่อนไขของค่า <math>a</math> ที่ทำให้เมตริกซ์ดังกล่าวเป็น positive definite.  ในการหาเงื่อนไขดังกล่าว ให้ factor <math>A</math> จากนั้นให้หาเงื่อนไขของ <math>a</math> ที่ทำให้การแยก factor สามารถกระทำได้
 +
 +
(a)
 +
<math>
 +
A=\left[
 +
\begin{array}{cc}
 +
1&a\\
 +
a&1
 +
\end{array}
 +
\right]
 +
</math>
 +
 +
(b)
 +
<math>
 +
A=\left[
 +
\begin{array}{ccc}
 +
1&a&0\\
 +
a&1&a\\
 +
0&a&1
 +
\end{array}
 +
\right]
 +
</math>
 +
 +
(c)
 +
<math>
 +
A=\left[
 +
\begin{array}{cc}
 +
I&aI\\
 +
aI&I
 +
\end{array}
 +
\right]
 +
</math>, เมื่อ <math>I</math> เป็น identity matrix ขนาด <math>n\times n</math>
 +
 +
'''3.''' (V7.5) คำนวณหา LU factorization โดยใช้ฟังก์ชัน scipy.linalg.lu  สังเกตผลลัพธ์ที่ได้
 +
 +
<math>
 +
A=\left[
 +
\begin{array}{cccc}
 +
-3&2&0&3\\
 +
6&-6&0&-12\\
 +
-3&6&-1&16\\
 +
12&-14&-2&-25
 +
\end{array}
 +
\right]
 +
</math>
 +
 +
'''4.''' (V7.7) สมมติว่าคุณต้องแก้ linear equations ทั้งหมด <math>K</math> ชุด ดังนี้
 +
 +
<math>AD_1Bx_1 = b_1</math>
 +
 +
<math>AD_2Bx_2 = b_2</math>, จนถึง
 +
 +
<math>AD_KBx_K = b_K</math>
 +
 +
โดยคุณได้รับเมตริกซ์ <math>A</math> และ <math>B</math> ขนาด <math>n\times n</math> ที่เป็น nonsingular  เมตริกซ์ <math>D_k</math> เป็น diagonal matrix ที่สมาชิกบนเส้นทะแยงมุมมีค่าไม่เป็นศูนย์  นอกจากนี้ คุณก็จะได้รับพจน์ด้านขวา <math>b_k\in{\mathbf R}^n</math>
 +
 +
ตัวแปรที่คุณต้องหาคำตอบคือ <math>n</math>-vectors <math>x_k</math>, สำหรับ <math>k=1,\ldots, K</math>
 +
 +
อธิบายวิธีการที่ใช้หาค่าของ <math>x_k</math> สำหรับทุก ๆ <math>k=1,\ldots, K</math>  ให้เปรียบเทียบเวลาที่ใช้ กับการคำนวณหาคำตอบโดยตรงด้วยวิธีการธรรมดา
 +
 +
: ''สำหรับข้อต่อไปนี้ จะทยอยใส่คำแปลให้ตามเหมาะสม''
 +
 +
 +
'''5.''' ทำข้อ V7.12
 +
 +
'''6.''' ทำข้อ V8.1
 +
 +
'''7.''' ทำข้อ V8.3
  
 
== ซอฟต์แวร์ ==
 
== ซอฟต์แวร์ ==

รุ่นแก้ไขปัจจุบันเมื่อ 07:44, 20 กันยายน 2555

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

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

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

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

การวัดผล

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

หัวข้อ

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

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

  • 19 มิ.ย. Vectors (ใช้ Lecture 1 จากเว็บวิชา EE103)
  • 26 มิ.ย. Matrices (ใช้ Lecture 2 จากเว็บวิชา EE103)
  • 3 ก.ค. Linear equations, เกริ่น Theory of linear equations (ใช้ Lecture 3 และ 4 จากเว็บวิชา EE103)
  • 19 ก.ค.:
    • Guest speaker
    • Theory of linear equations.

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

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

  • 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) ให้ -vector โดยที่ และ เราจะเรียก ว่าเป็น middle element ของ เรากำหนดให้

แทนความแตกต่างระหว่าง middle element กับค่าเฉลี่ยของ element ใน จงเขียนฟังก์ชัน ในรูป เมื่อ เป็น -vector

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

สำหรับทุก ๆ -vector นั่นคือค่าเฉลี่ยของทุก ๆ element ของเวกเตอร์ มีค่าอยู่ระหว่าง เท่าของ norm ของมัน

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

3. (V2.6) Projection ของเวกเตอร์ บนเวกเตอร์ ให้ เป็น -vector เราจะนิยามฟังก์ชัน ดังนี้

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

(ถ้าตอบว่าใช่ ให้ระบุ เมตริกซ์ ที่ ถ้าตอบว่าไม่ใช่ ให้แสดงตัวอย่างที่แสดงว่า ไม่มีคุณสมบัติ linearity )

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

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

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

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

(a) แสดงว่า เป็น nonsingular โดยแสดงว่าถ้า แล้ว

(b) จงหา inverse ของ    ในการทำข้อนี้ ให้เขียน ในรูปของ block matrix:

โดยที่แต่ละ block มีมิติ จากนั้นหาค่าของเมตริกซ์ จากเงื่อนไขว่า

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

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

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

(a)

(b)

(c) , เมื่อ เป็น identity matrix ขนาด

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

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

, จนถึง

โดยคุณได้รับเมตริกซ์ และ ขนาด ที่เป็น nonsingular เมตริกซ์ เป็น diagonal matrix ที่สมาชิกบนเส้นทะแยงมุมมีค่าไม่เป็นศูนย์ นอกจากนี้ คุณก็จะได้รับพจน์ด้านขวา

ตัวแปรที่คุณต้องหาคำตอบคือ -vectors , สำหรับ

อธิบายวิธีการที่ใช้หาค่าของ สำหรับทุก ๆ ให้เปรียบเทียบเวลาที่ใช้ กับการคำนวณหาคำตอบโดยตรงด้วยวิธีการธรรมดา

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


5. ทำข้อ V7.12

6. ทำข้อ V8.1

7. ทำข้อ V8.3

ซอฟต์แวร์

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

  • ทฤษฎีเมตริกซ์
    • Machine learning / AI: ใช้เพื่อโมเดลเอกสารและแสดงความสัมพันธ์ระหว่างเอกสาร (Vector space model), เทคนิคที่เกี่ยวข้องกับ eigenvalue เช่น SVD และ PCA, Collaborative filtering
  • การหาค่าที่ดีที่สุด

ลิงก์ภายนอก

ดึงข้อมูลจาก "http://158.108.32.49/wiki/index.php?title=01204472_ภาคต้น_2555&oldid=36594"