MyOOPS開放式課程
請加入會員以使用更多個人化功能
來自全球頂尖大學的開放式課程,現在由世界各國的數千名義工志工為您翻譯成中文。請免費享用!
課程來源:MIT
     

 

18.335J 數值方法導論,2004 秋季

18.335J Introduction to Numerical Methods, Fall 2004

譯者:廖超

編輯:陳盈、洪曉慧

Eigenvalues of the 100´100 Pascal Matrix.

100 x 100帕斯卡矩陣的本征值。(圖片由Plamen Koev提供)

課程重點

本課程附有課堂講稿和附解答的作業。

課程描述

課程的重點為用數值線性代數和數值方法求常微分方程之解。主要內容包括線性方程組,最小平方問題,本征值問題和奇異值問題。


技術需求

需要MATLAB® software 來執行課程網站上的.m檔。

 

 

教學大綱

相關描述

本課程由兩部分組成。在開始的三分之二課程,我們將主要介紹數值線性代數。我們將學習線性方程組的解,最小平方問題,本征值問題和奇異值問題的解法。密集性矩陣,稀疏性矩陣和結構性矩陣等問題的相關技巧都包含在內。學生應該學會欣賞很多藝術化的技巧並了解如何去運用它們。我們也將學習適用於各種數值問題的一些基本定理。它們包括(1)矩陣分解,(2)微擾論和狀態數,(3)包括浮點運算在內的捨入對演算法的影響,(4)分析演算法的速度,(5)選擇對問題的數學結構最好的演算法,以及(6)熟悉數值軟體。除了討論有定解的問題,開放性問題也將被補充進來。

在課程的第二階段,我們將重點討論常微分方程的數值解法。這些方法通常在大學本科階段數值分析課程,如數學分析導論(18.330)中提到。然而,瞭解這些課程並不是學習18.335(即本課程譯者注)必須的前提條件。本課內容屬於研究生水準,已包含了相關所需知識,同時也會提供課堂講稿。

必備先修課程

微分方程(18.03)和線性代數 (18.06)或相關知識。本課程要求學生熟悉線性代數並包含了大量以MATLAB軟體做的程式編寫。

教材

必備

Trefethen, Lloyd N., and David Bau. 《數值線性代數》 Numerical Linear Algebra. Philadelphia, PA: 工業與應用數學協會Society for Industrial and Applied Mathematics, May 1, 1997. ISBN: 0898713617.

選讀參考書

Demmel, James W. 《應用數值線性代數》 Applied Numerical Linear Algebra. Philadelphia, PA: 工業與應用數學協會Society for Industrial and Applied Mathematics, September 1, 1997. ISBN: 0898713897.

提供常微分方程的課堂講稿。

成績評定

成績評定表

項目

百分比

作業

80%

一次隨堂期中考試

20%

 

 

課堂講稿、教學時程

課程單元

課堂講稿

重要日期

1

導論,示例, 矩陣向量和矩陣集

Introduction, Examples, Matrix-Vector and Matrix-Matrix products

(PDF)

 

2

導論,示例, 矩陣向量和矩陣集

Orthogonal Matrices, Norms of Matrices

(PDF)

 

3

奇異值分解

The Singular Value Decomposition

(PDF)

 

4

QR分解

QR Factorization

(PDF)

 

5

Givens旋轉和 Householder反射

Givens Rotations and Householder Reflections

(PDF)

交第一次作業

6

最小平方問題

Least Squares Problems

(PDF)

 

7

浮點運算

Floating Point Arithmetic

(PDF)

交第二次作業

8

矩陣的條件與穩定性

Conditioning and Stability

(PDF)

 

9

Givens旋轉和倒疊代的穩定性

Stability of Givens Rotations and Backward Substitution

(PDF)

交第三次作業

10

最小平方問題的穩定性

Stability of Least Squares Problems

(PDF)

 

11

高斯消去法

Gaussian Elimination

(PDF)

 

12

Cholesky 分解

Cholesky Factorization

(PDF)

交第四次作業

13

本征值問題

Eigenvalue Problems

(PDF)

 

14

海森堡簡化

Hessenberg Reduction

 

交第五次作業

15

QR 演算法

QR Algorithm

(PDF)

 

16

期中考試

Midterm

 

交第六次作業

17

QR演算法穩定性; Jacobi演算法

Stability of the QR Algorithm; Jacobi

(PDF)

 

18

二分法,分開擊破法

Bisection, Divide and Conquer

(PDF)

 

19

Lanczos演算法,廣義最小餘數法

Lanczos, GMRES

(PDF)

 

20

迭代演算法, Arnoldi演算法

Iterative Algorithms, Arnoldi

(PDF)

交第七次作業

21

Lanczos演算法

Lanczos Algorithm

(PDF)

 

22

共軛梯度法

Conjugate Gradients

(PDF)

交第八次作業

23

常微分方程的解

Solutions to Ordinary Differential Equations

(PDF)

 

24

Runge Kutta

Runge Kutta Methods

(PDF)

交第九次作業

25

Stiff ODEs解法- I

Solutions to Stiff ODEs - I

(PDF)

 

26

Stiff ODEs解法 – II

Solutions to Stiff ODEs - II

(PDF)

交第十次作業

 

作業

作業在表中列出的課堂內繳交。有一些問題是選自課本:Trefethen, Lloyd N., and David Bau.《數值線性代數》Numerical Linear Algebra. Philadelphia, PA: 工業和應用數學協會, May 1, 1997. ISBN: 0898713617.

作業答案由Nikos Savva提供並得到授權使用。

 

作業

解答

5

作業 1 (PDF)

(PDF)

7

作業 2 (PDF)

(PDF)

9

作業 3(PDF)

(PDF)

12

作業 4(PDF)

(PDF)

14

作業 5(PDF)

(PDF)

16

作業 6(PDF)

(PDF)

20

作業 7(PDF)

(PDF)

22

作業 8(PDF)

(PDF)

24

作業 9(PDF)

(PDF)

支援檔案
Supporting Files
mmatinverse.pdf (PDF)
hw6.m (M)
InverseMM.m (M)

26

作業 10(PDF)

(PDF)

 

測驗

期中考試占整個成績的20%。沒有期末考試。

期中考試練習題(PDF)

期中考試試題(PDF)

 

使用工具或軟體

執行本部分中的.m檔需要MATLAB® software

下面的MATLAB檔是用來課堂演示的。

 

Householder QR (M)

Givens QR (M)

Clown (M)

Secular方程Secular Equation (M)

Golub-Kahan 雙對角化Golub-Kahan Bidiagonalization (M)

Jacobi 方法Jacobi Method (M)

Arnoldi (M)

Arnoldi Driver (M)

共軛梯度預處理Conjugate Gradient Preconditioners (M)

 

 

18.335J Introduction to Numerical Methods

Fall 2004

Eigenvalues of the 100´100 Pascal Matrix.Eigenvalues of the 100 x 100 Pascal Matrix. (Image by Plamen Koev.)

Course Highlights

This course features lecture notes and assignments with solutions.

Course Description

The focus of this course is on numerical linear algebra and numerical methods for solving ordinary differential equations. Topics include linear systems of equations, least square problems, eigenvalue problems, and singular value problems.

Technical Requirements

Special software is required to use some of the files in this course: .m.





Syllabus

Amazon logo When you click the Amazon logo to the left of any citation and purchase the book (or other media) from Amazon.com, MIT OpenCourseWare will receive up to 10% of this purchase and any other purchases you make during that visit. This will not increase the cost of your purchase. Links provided are to the US Amazon site, but you can also support OCW through Amazon sites in other regions. Learn more.
Description

This course will consist of two parts. During the first two thirds of the course, we will concentrate on Numerical Linear Algebra. We will study the solutions of linear systems of equations, least square problems, eigenvalue problems, and singular value problems. Techniques for dense, sparse and structured problems will be covered. Students should still come to appreciate many state-of-the-art techniques and recognize when to consider applying them. We will also learn basic principles applicable to a variety of numerical problems and learn how to apply them. These principles include (1) matrix factorizations, (2) perturbation theory and condition numbers, (3) effect of roundoff on algorithms, including properties of floating point arithmetic, (4) analyzing the speed of an algorithm, (5) choosing the best algorithm for the mathematical structure of your problem, and (6) engineering numerical software. In addition to discussing established solution techniques, open problems will also be presented.

During the second part of the course, we will concentrate on numerical methods for solving ordinary differential equations. These methods are usually introduced in undergraduate numerical analysis courses such as Introduction to Numerical Analysis (18.330). Such courses, however, are not prerequisites for 18.335. This graduate-level exposition will be self contained and lecture notes will be provided.

Prerequisites

Differential Equations (18.03) and Linear Algebra (18.06) or equivalent. The course assumes familiarity with linear algebra and will involve a reasonable amount of programming in MATLAB®.

Textbooks

Required

Amazon logo Trefethen, Lloyd N., and David Bau. Numerical Linear Algebra. Philadelphia, PA: Society for Industrial and Applied Mathematics, May 1, 1997. ISBN: 0898713617.

Optional

Amazon logo Demmel, James W. Applied Numerical Linear Algebra. Philadelphia, PA: Society for Industrial and Applied Mathematics, September 1, 1997. ISBN: 0898713897.

Lecture notes for Numerical Ordinary Differential Equations will be provided.

Grading

Table for Grading ACTIVITIES PERCENTAGES
 
Homework Assignments 80%
One In-class Midterm 20%




Calendar

Table for Calender Section LEC # TOPICS KEY DATES
 
1 Introduction, Examples, Matrix-Vector and Matrix-Matrix Products  
2 Orthogonal Matrices, Norms of Matrices  
3 The Singular Value Decomposition  
4 QR Factorization  
5 Givens Rotations and Householder Reflections Homework 1 due
6 Least Squares Problems  
7 Floating Point Arithmetic Homework 2 due
8 Conditioning and Stability  
9 Stability of Givens Rotations and Backward Substitution Homework 3 due
10 Stability of Least Squares Problems  
11 Gaussian Elimination  
12 Cholesky Factorization Homework 4 due
13 Eigenvalue Problems  
14 Hessenberg Reduction Homework 5 due
15 QR Algorithm  
16 Midterm Homework 6 due
17 Stability of the QR Algorithm; Jacobi  
18 Bisection, Divide and Conquer  
19 SVD Algorithms  
20 Iterative Algorithms, Arnoldi Homework 7 due
21 Lanczos, GMRES  
22 Conjugate Gradients Homework 8 due
23 Solutions to Ordinary Differential Equations  
24 Runge Kutta Methods Homework 9 due
25 Solutions to Stiff ODEs - I  
26 Solutions to Stiff ODEs - II Homework 10 due




Lecture Notes

Table for Lecture Notes LEC # TOPICS LECTURE NOTES
 
1 Introduction, Examples, Matrix-Vector and Matrix-Matrix products (PDF)
2 Orthogonal Matrices, Norms of Matrices (PDF)
3 The Singular Value Decomposition (PDF)
4 QR Factorization (PDF)
5 Givens Rotations and Householder Reflections (PDF)
6 Least Squares Problems (PDF)
7 Floating Point Arithmetic (PDF)
8 Conditioning and Stability (PDF)
9 Stability of Givens Rotations and Backward Substitution (PDF)
10 Stability of Least Squares Problems (PDF)
11 Gaussian Elimination (PDF)
12 Cholesky Factorization (PDF)
13 Eigenvalue Problems (PDF)
14 Hessenberg Reduction  
15 QR Algorithm (PDF)
16 Midterm  
17 Stability of the QR Algorithm; Jacobi (PDF)
18 Bisection, Divide and Conquer (PDF)
19 Lanczos, GMRES (PDF)
20 Iterative Algorithms, Arnoldi (PDF)
21 Lanczos Algorithm (PDF)
22 Conjugate Gradients (PDF)
23 Solutions to Ordinary Differential Equations (PDF)
24 Runge Kutta Methods (PDF)
25 Solutions to Stiff ODEs - I (PDF)
26 Solutions to Stiff ODEs - II (PDF)




Assignments

Amazon logo When you click the Amazon logo to the left of any citation and purchase the book (or other media) from Amazon.com, MIT OpenCourseWare will receive up to 10% of this purchase and any other purchases you make during that visit. This will not increase the cost of your purchase. Links provided are to the US Amazon site, but you can also support OCW through Amazon sites in other regions. Learn more.

Special software is required to use some of the files in this section: .m.

The assignments are due in the sessions listed in the table. Some of the problems are assigned from the required text: Amazon logo Trefethen, Lloyd N., and David Bau. Numerical Linear Algebra. Philadelphia, PA: Society for Industrial and Applied Mathematics, May 1, 1997. ISBN: 0898713617.

Homework solutions are courtesy of Nikos Savva. Used with permission.

Table for Assignment Section lec # ASSIGNMENTS SOLUTIONS
 
5 Homework 1 (PDF) (PDF)
7 Homework 2 (PDF) (PDF)
9 Homework 3 (PDF) (PDF)
12 Homework 4 (PDF) (PDF)
14 Homework 5 (PDF) (PDF)
16 Homework 6 (PDF) (PDF)
20 Homework 7 (PDF) (PDF)
22 Homework 8 (PDF) (PDF)
24 Homework 9 (PDF) (PDF)

Supporting Files

mmatinverse.pdf (PDF)
hw6.m (M)
InverseMM.m (M)
26 Homework 10 (PDF) (PDF)





Exams

The midterm counts as 20% of the course grade. There is no final exam.

Practice Midterm (PDF)

Midterm Exam (PDF)





Tools

Special software is required to use some of the files in this section: .m.

The MATLAB® files below were used as demonstration software in class.

Householder QR (M)

Givens QR (M)

Clown (M)

Secular Equation (M)

Golub-Kahan Bidiagonalization (M)

Jacobi Method (M)

Arnoldi (M)

Arnoldi Driver (M)

Conjugate Gradient Preconditioners (M)



留下您對本課程的評論
標題:
您目前為非會員,留言名稱將顯示「匿名非會員」
只能進行20字留言

留言內容:

驗證碼請輸入3 + 6 =

標籤

現有標籤:
新增標籤:


有關本課程的討論

目前暫無評論,快來留言吧!

Creative Commons授權條款 本站一切著作係採用 Creative Commons 授權條款授權。
協助推廣單位: