数值分析课件

數值分析數值分析

能夠做什麼？

§1

Introduction應用問題舉例今有上禾三秉，中禾二秉，下禾一秉，實三十九鬥；上禾二秉，中禾三秉，下禾一秉，實三十四鬥；上禾一秉，中禾二秉，下禾三秉，實二十六鬥。問上、中、下禾實一秉各幾何？答曰：上禾一秉九鬥四分鬥之一。中禾一秉四鬥四分鬥之一。下禾一秉二鬥四分鬥之三。-------《九章算術》1、一個兩千年前的例子線性方程組的求解！2、天體力學中的Kepler方程x是行星運動的軌道，它是時間t的函數.非線性方程求根！全球定位系統：在地球的任何一個位置，至少可以同時收到4顆以上衛星發射的信號

3、全球定位系統（GlobalPositioningSystem,GPS)

表示地球上一個接收點R的當前位置，衛星Si的位置為，則得到下列非線性方程組記為其中，非線性方程組的求解！4、已經測得在某處海洋不同深度處的水溫如下：深度（M）46674195014221634水溫（oC）7.044.283.402.542.13根據這些數據，希望合理地估計出其他深度（如500米，600米，1000米…）處的水溫.插值法！5、人口預測

下麵給出的是中國1900年到2000年的人口數，我們的目標是預測未來的人口數（數據量較大時）19505519619606620719708299219809870519901143332000126743數據擬合！6、鋁制波紋瓦的長度問題建築上用的一種鋁制波紋瓦是用一種機器將一塊平整的鋁板壓制而成的.假若要求波紋瓦長4英尺,每個波紋的高度(從中心線)為1英寸,且每個波紋以近似2π英寸為一個週期.求制做一塊波紋瓦所需鋁板的長度L.

這個問題就是要求由函數f(x)=sinx給定的曲線從x=0到x=48英寸間的弧長L.

由微積分學我們知道,所求的弧長可表示為:上述積分稱為第二類橢圓積分,它不能用普通方法來計算.數值積分！電腦輔助設計：波音777應用三維立體建模，數位化設計與有限元計算的第一架噴氣客機。天氣預報：計算能力的發展將把海洋、大氣和生態系統的綜合知識融合成一個氣象變化模型。醫學與生物工程：CT、核磁共振與Radon變換；至病基因與藥物設計；人造生物材料的彷真回應；傳染病動力學模型。現代科學計算在工程計算中的應用電子系統自動化設計：大規模積體電路的設計與邏輯檢測。材料設計：性能設計的大規模計算與模擬：設計用於生產新的高熱值、高壓材料中的化學蒸發沉澱反應器。車輛與道路工程設計與模擬：車輛與道路相互作用綜合系統設計。存儲與物流系統：工農業發展使得產品的存儲、交流和時效性極大提高；廢物和垃圾問題成為城市生活的重大問題。規劃計算和系統分析成為常用計算方法。燃燒與爆炸工程：燃燒對環境的影響；計算流體力學與爆炸工程。網路設計與計算：搜索引擎的設計航空航太工程：神州飛船系列資訊與通信工程：GPS衛星導航數值計算方法的意義、內容與方法軟體的核心就是演算法。20世紀最偉大的科學技術發明---電腦

電腦是對人腦的模擬，它強化了人的思維智能；電腦的發展和應用，已不僅僅是一種科學技術現象，而且成了一種政治、軍事、經濟和社會現象；沒有軟體的支持，超級電腦只是一堆廢鐵而已；演算法猶如樂譜，軟體猶如CD盤片，而硬體如同CD唱機。理論研究科學實驗科學計算計算數學諾貝爾獎得主,計算物理學家Wilson提出現代科學研究的三大支柱

科學方法論的巨大變革：如果說伽利略和牛頓在科學發展史上奠定了實驗和理論這兩大科學方法的支柱，那麼由馮.諾依曼研製的現代電子電腦把計算推上了人類科學活動的前沿，使計算成為第三種方法。21世紀資訊社會的兩個主要特徵：“電腦無處不在”“數學無處不在”21世紀資訊社會對科技人才的要求：--會用數學解決實際問題--會用電腦進行科學計算建立數學模型選取計算方法編寫上機程式計算得出結果科學計算解題過程數值計算方法是計算數學的一個主要組成部分，“什麼是數值計算方法？”它主要研究使用電腦求解各種科學與工程計算問題的數值方法（近似方法）;對求得的解的精度進行評估以及在電腦上實現求解等。

數值計算方法已經成為電腦處理實際問題的一個重要手段，從宏觀天體運動學到微觀分子細胞學，從工程系統到社會經濟系統，無一能離開數值計算方法。因此，數值計算與電腦模擬被稱為“第三種科學研究方法”。

科學計算可視化是目前研究的熱門問題，下麵的藝術圖形是基於科學計算的數據表示的例子分形圖混沌圖1、數值逼近

插值與擬合、FFT、數值積分與微分2、數值代數

代數基礎、線性代數方程組的解法、非線性代數方程（組）的解法、特徵值與特徵向量3、微分方程數值解

ODE、PDE和有限元法4、最優化方法*無約束優化與約束優化方法融進了機器學習計算、仿生計算、網路計算、以數據為核心的計算和各種普適計算、非線性科學計算等內容。傳統的數值計算的主要研究內容

現代計算方法：數值計算方法的主要特點借助電腦提供切實可行的數學演算法.想的精確度;收斂且穩定;誤差可以分析或估計.所提出的演算法必須具有：可靠的理論分析;理時間複雜性好__指節省時間；空間複雜性好__指節省存儲量。計算複雜性好

通過數值實驗證明演算法行之有效.採用“近似替代”方法→逼近採用“構造性”方法採用“離散化”方法

把求連續變數的問題轉化為求離散變數的問題採用“遞推化”方法

複雜的計算歸結為簡單過程的多次重複，易於用迴圈結構來實現（迭代法）。採用各種搜索方法構造數值演算法的主要手段

希望：求近似解，但方法簡單可行，行之有效（計算量小，誤差小,需存儲單元少等）,

以電腦為工具，易在電腦上實現。電腦運算:

只能進行加，減，乘，除等算術運算和一些邏輯運算。數值計算方法：

把求解數學問題轉化為按一定次序只進行加，減，乘，除等基本運算.設計數值演算法的出發點？如何學好數值計算方法？威爾金森（JamesHardy.Wilkinson，1919-1986）Wilkinson是數值分析和數值計算的開拓者和奠基人。1940年，開始研究彈道的數學模型與數值計算。1946年成為Turing的助手，協助設計PilotACE電腦。1969年他當選為英國皇家學會院士；1970年工業和應用數學會(s1am)授予他馮·諾伊曼獎；1987年他獲得美國數學會的chauvenet獎。著名的美國阿爾貢國家實驗室曾聘威爾金森為榮譽高級研究員並兩次向他授獎。

Wilkinson在數值分析研究領域作出了傑出貢獻，是數值計算的早期開拓者，其工作加速了數字電腦(在科學計算中)的使用。他研究的主要問題是線性代數方程組和矩陣特徵值問題的數值解法，特別是他的向後誤差分析法(backwarderroranalysis)的創造性工作奠定了數值分析和數值計算早期的理論基礎。

1975年J.H.Wilkinson成為第五位圖靈獎獲得者。教材現代科學與工程計算孟大志劉偉（高等教育出版社）參考書目

數值分析孫志忠袁慰平等（東南大學出版社,第二版）

應用數值方法使用MATLAB和C語言

RobertJ.Schilling&SandraL.Harris（機械工業出版社）

數值分析（第4版）李慶楊王能超易大義華中科技大學出版社數值分析與科學計算JefferyJ.Leader著，張威，劉志軍，李豔紅等譯，（清華大學出版社)

數值分析精品課程網站：/na/html/index_common.htm

§2

算法一、演算法的概念

描述演算法可以有不同的方式。例如，可以用日常語言和數學語言加以敘述，也可以借助形式語言（演算法語言）給出精確的說明，也可以用框圖直觀地顯示演算法的全貌。

定義：由基本運算及運算順序的規定所構成的完整的解題步驟，稱為演算法。例：求解二元一次聯立方程組用行列式解法：首先判別

（1）如果，則令電腦計算

輸出計算的結果x1，x2。（2）如果D=0，則或是無解，或有無窮多組解。是否為零，存在兩種可能：令通過求解過程，可以總結出演算法步驟如下：S2計算S3如果則輸出原方程無解或有無窮多組解的資訊;否則S1輸入S4輸出計算的結果輸入

D=a11a22-a12a21D=0開始輸出

x1,x2

結束

No輸出無解資訊Yes二、演算法優劣的判別

計算量的大小

存貯量

邏輯結構例：用行列式解法求解線性方程組:n階方程組，要計算n+1個n階行列式的值，總共需要做n!(n-1)(n+1)

次乘法運算。

n=20需要運算多少次？n=100?一、誤差的來源與分類從實際問題中抽象出數學模型

——模型誤差例:品質為m的物體，在重力作用下,自由下落，其下落距離s

與時間t的關係是：

其中g

為重力加速度。§3誤差通過測量得到模型中參數的值

——觀測誤差求近似解——方法誤差(截斷誤差）例如，當函數用Taylor多項式

近似代替時，數值方法的截斷誤差是

與0之間。在機器字長有限——

舍入誤差

用電腦、計算器和筆算，都只能用有限位

=3.1415926…

小數來代替無窮小數或用位數較少的小數來代替位數較多的有限小數，如：四捨五入後……在數值計算方法中，主要研究截斷誤差和舍入誤差（包括初始數據的誤差）對計算結果的影響！二、誤差的概念1、絕對誤差與絕對誤差限例:若用以釐米為最小刻度的尺去量桌子的長，大約為1.45米，求1.45米的絕對誤差。1.45米的絕對誤差=？不知道！是近似值的絕對誤差,簡稱為誤差。

定義：設是準確值，為

的一個近似值，稱但實際問題往往可以估計出不超過某個正數，即則稱為絕對誤差限，有了絕對誤差限,就可以知道的範圍為即落在內。在應用上，常常採用下列寫法來刻劃的精度。2、相對誤差與相對誤差限定義：設是準確值，是近似值，是近似值的誤差，通常取為近似值的相對誤差，記作，稱一般情況下是不知道的，怎麼辦？事實上，當較小時是的二次方項級,故可忽略不計.相應地，若正數滿足

則稱為的相對誤差限。3、有效數字定義：如果則說近似表示準確到小數後第位，並從這第位起直到最左邊的非零數字之間的一切數字都稱為有效數字，並把有效數字的位數稱為有效位數。如果一個近似數的所有數字均為有效數字，則稱之為有效數。由上述定義故若取作的近似值，就有五位有效數字。若取作的近似值，就有六位有效數字。取作的近似值，就有三位有效數字。注：若一近似數是由原真值經四捨五入得到，則必為有效數.定義:若近似值的誤差限是某一位的半個單位,也即，若有位有效數字。則稱其中，是1到9中的一個數字；是0到9中一個數字；為整數，且該位到的左邊第一位非零數字共有位,就說有位有效數字。由上述定義故的近似值分別有三位、五位和六位有效數字。4、相對誤差限與有效數字的關係Th1.1：

則

至少具有位有效數字。對於用式表示的近似數，若具有位有效數字，則其相對誤差限為反之，若的相對誤差限為Th1.2：

設反之,若的相對誤差的絕對值大於，其中為整數,為正整數,。有位有效數字。則至多若至多有位有效數字,即是有效數字,而不是有效數字,則的相對誤差的絕對值必大於;證明：不是有效數字

反之,若

則

不是有效數字，

即至多有位有效數字.

§4

數值運算的誤差估計一、四則運算的誤差估計兩個近似數與,其誤差限分別為及,它們進行加減乘除運算得到的誤差限分別為二、函數誤差估計當引數有誤差時，計算函數值也會產生誤差，其誤差限可利用函數的Taylor展開式進行估計。

設是一元函數，的近似值為,以近似，其誤差限記作，可用Taylor展開

介於之間.取絕對值得假定與的比值不太大,,可忽略的高階項,於是可得計算函數的誤差限為

當為多元函數時計算,如果的近似值為,則的近似為於是函數值的誤差由Taylor展開,得：於是誤差限為而的相對誤差限為(1.3.1)(1.3.2)例:已測得某場地長的值為,寬的值為,已知,.試求面積的絕對誤差限與相對誤差限.解:因

其中由式(1.3.1)得而於是絕對誤差限為相對誤差限為§5

演算法的數值穩定性

數值計算在設計演算法時首先關心的是由它產生的計算結果的穩定性，而演算法的穩定性與舍入誤差是否增長密切相關。一個演算法如果輸入數據有微小擾動（即誤差），而在計算過程中舍入誤差不增長，則稱此演算法是數值穩定的，否則稱其為數值不穩定。

例：求定積分的值.解：直接積分可產生遞推公式若取初值可得遞推公式按公式就可以逐步算出注意此公式精確成立，且Whathappened?!不穩定的演算法！這就是誤差傳播所引起的危害!

NYBJ蝴蝶效應——紐約的一只蝴蝶翅膀一拍，風和日麗的北京就刮起颱風來了？！這是一個病態問題由題設中的遞推公式（1）可看出，

的誤差擴大了5倍後傳給

，因而初值

的誤差對以後各步這就造成的計算結果嚴重失真。計算結果的影響，隨著

的增大愈來愈嚴重。要怎麼做才能解決這個問題呢?可求得I9

0.017，按改寫後的公式可逐次求得不妨設I9

I10，於是由將公式變為

I8

0.019I7

0.021 I6

0.024I8

0.028 I4

0.034I3

0.043 I2

0.058I1

0.088 I0

0.182穩定的演算法！

在我們今後的討論中，誤差將不可回避，演算法的穩定性會是一個非常重要的話題。注：遞推公式(1)的舍入誤差以5的冪次增長進行傳播，因此是數值不穩定的，而遞推公式(2)的舍入誤差在一定範圍內以0.2的冪次進行傳播，隨著n的增大，誤差逐步減少，因此該演算法是數值穩定的。

因此，可以看出數值不穩定的演算法是不能使用的，實際計算中對任何輸入數據都是數值穩定的演算法，稱為無條件穩定。而對某些數據數值穩定，對其他數據數值不穩定的演算法，稱為條件穩定。1.要避免兩個相近的數相減在數值計算中，兩個相近的數作減法時有效數字會損失。例:

求的值。當x=1000，y的準確值為0.01580

§6數值計算中應該注意的一些原則類似地

(2)若將原式改寫為則y=0.01581(1)直接相減有3位有效數字！只有1位有效數字2.儘量避免絕對值太小的數作分母例：如分母變為0.0011，也即分母只有0.0001的變化時結果相差這麼大!3.避免大數吃小數精確解為

演算法1：利用求根公式例：用單精確度計算的根。在電腦內，109存為0.11010，1存為0.1101。做加法時，兩加數的指數先向大指數對齊，再將浮點部分相加。即1的指數部分須變為1010，則：1=0.00000000011010，取單精確度時就成為：109+1=0.100000001010+0.000000001010=0.100000001010演算法2：先解出再利用注：求和時從小到大相加，可使和的誤差減小。例：按從小到大、以及從大到小的順序分別計算1+2+3+…+40+1094.簡化計算步驟，避免誤差積累。一般來說，電腦處理下列運算的速度為例：多項式求值：給定的x求下列n次多項式的值。

解：1.用一般演算法，即直接求和法；

2.逐項求和法；3.秦九韶方法(即Hornor演算法）；先計算x2,x3,…,xn,再作線性組合，需做2n-1次乘法和n次加法。解法一：直接求和法解法二：逐項求和法按順序依次計算每一項的值再求和，需做n(n+1)/2次乘法和n次加法。解法三：秦九韶演算法（即Horner演算法）只需做n次乘法和n次加法。且可以遞推實現。電腦上使用的演算法常採用遞推化的形式，遞推化的基本思想是把一個複雜的計算過程歸結為簡單過程的多次重複。這種重複在程式上表現為迴圈。遞推化的優點是簡化結構和節省計算量。演算法的遞推性例：用秦九韶方法求多項式p(x)在x=-2處的值解：

Ka5-KvK00.008330.00833v0=a510.041670.04v1=v0x+a420.166670.15867v2=v1x+a330.50.46827v3=v2x+a2410.90635v4=v3x+a1510.81873v5=v4x+a0約翰·馮·諾依曼（JohnvonNeumann,1903-1957）美藉匈牙利人，1930年接受了普林斯頓大學客座教授的職位，西渡美國。1931年成為該校終身教授。1933年成為新成立的普林斯頓高等研究院的終身研究員。1951年至1953年任美國數學會主席。馮·諾依曼是20世紀少有的數學科學通才，在許多領域都有重要的貢獻，被西方人譽為“數學奇才、電腦之父”。馮·諾依曼對人類的最大貢獻是對電腦科學、電腦技術和數值分析的開拓性工作。並行計算

一、電子電腦的並行計算分類

傳統電腦一般採用VonNeumann結構，每一時刻只有一個進程的演算法，即串行演算法。

並行電腦每一時刻具有2個以上的進程的演算法稱為並行演算法。並行機必須包含2臺以上處理機，按指令流是單個還是多個並行演算法可分為兩類：

SIMD演算法適用於單指令流多數據流系統；

MIMD演算法適用於多指令流多數據流系統。

按照進程之間是否同步可將並行演算法分為:

同步演算法:是指在k個進程的演算法中有些進程的若干算法必須在另一些進程的某些演算法之後執行；非同步演算法:指k個進程間有資訊聯繫但不須同步，它只能在一個具有k臺處理機的MIMD系統中實現。二、並行計算的演算法設計

並行演算法設計的重要原則是“分而治之”。其基本思想是把問題依次劃分為可以獨立完成的較小問題，將規模逐次減半的二分技術是並行演算法設計的一種基本技術。二分演算法的設計原理是反復地將所給計算問題加工成規模減半的同類計算問題而計算。可利用串行演算法來改造或設計並行演算法，不少數值演算法包含了可直接利用的並行性。還可以根據並行演算法的特點設計具有新思想的新演算法，它的出發點仍然是“分而治之”的原理，符合此原理的區域、算子、系統的分裂方法和技術是設計和實現並行處理的重要手段。此外，非同步數值演算法基本上是混亂迭代法，是並行算法最富有特色的組成部分之一。第二章插值§1引言一、引例已經測得在某處海洋不同深度處的水溫如下：深度（M）46674195014221634水溫（oC）7.044.283.402.542.13根據這些數據，希望合理地估計出其他深度（如500米，600米，1000米…）處的水溫.這就是本章要討論的“插值問題”問題驅動：汽車的刹車距離

司機駕駛汽車時需要根據車速估計汽車的刹車距離以確保行車安全。圖2.1.1某車型乾燥路況刹車距離示意圖

美國的某司機培訓課程的有如下駕駛規則：正常的駕駛條件下對車與車之間的距離的要求是每小時10英里的速率可以允許一輛車的跟隨距離。實現這一規則的簡便方法就是“2秒法則”：這種方法不管車速為多少，後車司機從前車經過某一標誌開始默數“一千零一，一千零二”，這樣用英文讀完就是兩秒。如果你在默數完這句話前就到了同一標誌處，那麼你的車和前面的車靠得太近了。

假設車長為15英尺，根據這條法則可以得到如圖2.1.1所示的圖形，它表明該法則允許的距離間隔和速率成比例，即。其中為比例常數。

圖2.1.2“2秒法則”的幾何解釋

下麵給出一組經測試得到的關於刹車距離與速度的較為理想的實驗數據，如表2.1.1所示。要想瞭解刹車的距離與車速的關係，試建立適當的數學模型，預測車輛的總停止距離d（英尺）關於速度v（英里/小時）的函數，檢驗2秒法則與駕駛規則是否一致，並嘗試尋找更好的駕駛規則。v20253035404550d425673.591.5116142.5173v556065707580d209.5248292.5343401464表2.1.1刹車距離實驗數據

插值法是一種古老的數學方法。早在1000多年前，我國曆法上已經記載了應用一次插值和二次插值的實例。

偉大的數學家：拉格朗日（Lagrange）、牛頓Newton）、埃爾米特（Hermite）等人分別給出了不同的解決方法。二、插值問題的定義

當精確函數y=f(x)非常複雜或未知時，在區間這個問題稱為“插值問題”

(2.1.1)近似函數g(x)

f(x)，滿足條件

,由此構造一個簡單易算的

上一系列節點

處測得函數值

這裏的g(x)

稱為f(x)的插值函數。節點x0…xm稱為插值節點,條件（2.1.1)稱為插值條件，區間稱為插值區間。如果利用g(x)來求f(x)

在y點的近似值，則稱y為插值點。插值函數的類型有很多種最常用的插值函數是

…?代數多項式用代數多項式作插值函數的插值稱為代數插值，即選取次數不超過n的多項式Pn(x)，使得

Pn(xj)=yj(j=0,1…n)(2.1.2)本章主要討論的內容插值問題插值法插值函數§2代數插值代數插值一、插值問題解的存在唯一性？二、插值多項式的常用構造方法？三、插值函數的誤差如何估計？一、插值多項式的存在唯一性：設所要構造的插值多項式為：

由插值條件得到如下線性代數方程組：（2.2.1）（2.2.2）此方程組的係數行列式為

當

時，

D

0，因此，Pn(x)由a0,a1,…,an唯一確定。範得蒙行列式的轉置！定理插值條件的n

階插值多項式Pn(x)存在且唯一。插值多項式的構造：插值多項式的存在唯一性說明，滿足插值條件的多項式存在，並且插值多項式與構造方法無關。如何構造插值函數才能達到預期的效果呢？對於給定的互異節點x0…xn,滿足

，用於插值的簡單函數元素集+線性組合結構→插值多項式簡單函數元素集是指構成多項式的基函數集合，例如自然形式（2.2.1）的自然基底,、

、

(結構)(集合)若求自然形式(2.2.1)的插值多項式問題，只要求解線性方程組（2.2.2）計算出多項式係數即可。一般插值多項式的構造方法通過解方程組(2.2.2)求得插值多項式的方法並不可取.這是因為當n較大時解方程組的計算量較大，而且方程組係數矩陣的條件數一般較大（可能是病態方程組）,當階數n越高時，

病態越重。怎樣可以不通過求解方程組而獲得插值多項式呢?在n次多項式空間Pn中找一組合適的基函數

,使不同的基函數的選取導致不同的插值方法.Lagrange插值Newton插值Hermite插值二、拉格朗日(Lagrange)插值1．線性插值(n=1)

x0x1(x0,y0)(x1

,y1)f(x)P1(x)n=1已知

x0

,

x1

;

y0

,

y1

，求l0(x)l1(x)2．拋物插值(n=2)p2(x)

f(x)x0x1x2f(x)因過三點的二次曲線為拋物線，故稱為拋物插值。

3．n次拉格朗日插值公式設連續函數y=f（x）在[a,b]上對給定n+1個不同結點：

x0,x1,…,xn,分別取函數值y0,y1,…,yn其中

yi=f(xi)i=0,1,2,…,n試構造一個次數不超過n的插值多項式使之滿足條件

i=0,1,2,…,n要求：無重合節點，即若能求得n次多項式lk(x),k=0,1,…,n，則

i=0,1,2,…,n即Pn(x)滿足插值條件（2.1.2）.

滿足因此，令又由lk(xk)=1，得：

的運算式推導：根據lk(x)的定義，xk以外所有的結點都是lk(x)的根，從而得n

階拉格朗日（Lagrange）插值公式：4、插值餘項/*Remainder*/定理4.3.1

若

在[a,b]記憶體在,則在[a,b]上的n+1個互異的點，對f（x)所作的n次Lagrange插值多項式有誤差估計也稱為Lagrange插值多項式的插值餘項。當n=1時，線性插值的餘項當n=2時，拋物插值的餘項注：

通常不能確定

,而是估計,

x(a,b)，將作為誤差估計上限。

當

f(x)為任一個次數

n

的多項式時，,可知，即插值多項式對於次數

n的多項式是精確的。

插值多項式一般僅用來估計插值區間內點的函數值（即內插），用它來計算插值區間外點的函數值（即外插）時，誤差可能很大。

通常取依靠增加節點不一定能減少誤差；

事後誤差估計在實際計算中，由於函數f(x)往往未知或很難求得，也就難以求出或估計出其較精確的上界，從而難以估計一般可使用求出兩個插值多項式之差的方法來估計誤差，稱之為事後估計。圖2.1前後兩組插值節點的劃分插值餘項可表示成取n+2個節點分別用前n+1個節點和後n+1個節點和，如圖2.1所示構造n次插值多項式例：已知分別利用sinx的1次、2次Lagrange插值計算

sin50

，

並估計誤差。解：n=1分別利用x0,x1

以及x1,x2

計算

利用

利用計算得：sin50

0.76008,

sin50=0.7660444…利用x0,x1

作為插值節點的實際誤差

0.01001利用x1,x2作為插值節點的實際誤差

0.00596n=2

sin50=0.7660444…2次插值的實際誤差

0.00061三、牛頓插值（Newton’sInterpolation）Lagrange插值雖然易算，但若要增加一個節點時，全部基函數li(x)

都需要重新計算。希望每加一個節點時，只附加一項上去即可。

1、能否重新在

中尋找新的基函數？回顧：Lagrange插值的優缺點：

優點：具有嚴格的規律性,便於記憶。

缺點：計算量大、不具有承襲性。利用插值條件代入上式，得關於的線性代數方程組:設當

互異時，係數矩陣非奇異，且容易求解.Itisnotadifficultthingforamathematician.WecanusenotationHowcomplextheexpressionare!2．差商2.1差商的定義(亦稱均差)

定義1：設已知函數f(x)在一系列互不相等的上的函數值

f(xi)

,

稱為f(x)在點xi,xj處的一階差商，記作f[xi,xj]，

節點，（即在時，）又稱為f(x)在點xi,xj,xk處的二階差商

稱

為f(x)在點x0,x1,…,xk處的k階差商。由差商定義可知：

高階差商是兩個低一階差商的差商。利用差商的定義,可得的係數

:從而

因此，每增加一個結點，Newton插值多項式只增加一項，克服了Lagrange插值的缺點。

2.2差商的性質:

性質1(差商與函數值的關係):

記,則

性質2

（對稱性）：

差商的值與結點排列順序無關，即性質3(差商與導數的關係):設在上有階導數,且則存在使得性質4(特徵定理):差商可列表計算：

f(x0)f(x1)f(x2)…f(xn1)f(xn)f[x0,x1]f[x1,x2]…………f[xn1,xn]f[x0,x1,x2]…………f[xn2,xn1,xn]f[x0,…,xn]xi

yi

一階差商

二階差商

n階差商

……x0x1x2xn-1xn

xn+1f(xn+1)f[xn,xn+1]f[xn1,xn,xn+1]f[x1,…,xn+1]f[x0,…,xn+1]2.3差商的計算:

3.牛頓插值餘項由插值多項式的唯一性可知，故其餘項也相同，即定理：Newton插值多項式的餘項為

其中，從而，例:給定的數據表

2.202.402.602.803.000.788460.875470.955511.029621.098611.構造差商表2.分別寫出二次、四次Newton插值多項式解:構造差商表一階差商二階差商三階差商四階差商餘項四、等距節點插值

1．引入(微商的離散化)2．差分的定義設函數在等距節點上的值

為已知,這裏為常數,稱為步長.定義:分別稱為在處以為步長的一階向前差分,一階向後差分,以及一階中心差分.3、差分表

計算各階差分可按如下差分表進行：4、差分的性質性質1

(差分與函數值的關係):

各階差分均可表示為函數值的線性組合:其中，性質2(向前差分與向後差分的關係):性質3(多項式的差分):

若f(x)∈Pn(n次多項式類),則性質4(差分與差商的關係):在等距節點的前提下，性質5(差分與導數的關係）：在等距節點的前提下，性質6：常數的差分等於零.性質7：差分算子為線性算子，即性質8：這個性質類比於

性質9：

（類比於分部積分法則）

5、等距節點的牛頓插值公式牛頓公式:

牛頓前插公式（用於計算最小節點附近的函數值）利用差分的性質,可將Newton公式簡化為(1)稱公式(1)為Newton向前差分插值公式,其餘項為(2)

牛頓後插公式（用於計算最大節點附近的函數值）如果將Newton插值公式改為按節點的(3)次序排列的Newton插值公式,即令x=xn-th,則當x0≤x≤xn時,0≤t≤1.利用差商與向後差分的關係,式(3)可簡化為(4)稱式(4)為Newton向後差分插值公式。其餘項為注：一般當x

靠近x0時用前插，靠近xn時用後插，故兩種公式亦稱為表初公式和表末公式。例

給定f(x)在等距節點上的函數值表如下:

xi0.40.60.81.0

f(xi)1.51.82.22.8分別用Newton向前和向後差分公式求f(0.5)及f(0.9)的近似值.

解

先構造向前差分表如下:

xi

fi

△fi

△2fi△3fi

0.41.50.61.80.30.82.20.40.11.02.80.60.20.1

x0=0.4,h=0.2,x3=1.0.分別用差分表中對角線上的值和最後一行的值,得Newton向前和向後插值公式如下:(1)

(2)當x=0.5時,用公式(1),這時t=(x-x0)/h=0.5.將t=0.5代入(1),得

f(0.5)≈N3(0.5)=1.64375.當x=0.9時,用公式(2),這時t=(x3-x)/h=0.5.將t=0.5代入(2),得

f(0.9)≈N3(0.9)=2.46875.五、Hermite插值1．引入

在實際問題中，對所構造的插值多項式，不僅要求函數值重合，而且要求若干階導數也重合。即：要求插值函數P(x)滿足:（1）把此類插值問題稱為帶導數的插值多項式，相應的插值多項式稱為埃米爾特（Hermite）插值多項式或稱H(x)

存在且唯一埃米爾特（Hermite）插值記為H(x)。2.推導只討論函數值與導數值個數相等的情況.設在節點上,要求插值多項式,滿足條件(5)這裏給出的個條件,可唯一確定一個次數不超過的多項式其形式為如根據條件(5)來確定個係數,顯然非常複雜。先求插值基函數及,共有個,每一個基函數都是次多項式,且滿足條件Lagrange型Hermite插值多項式基函數方法(6)於是滿足條件(5)的插值多項式可寫成用插值基函數表示的形式,即(7)由條件(6),顯然有下麵的問題就是求滿足條件(6)的基函數及為此,可利用Lagrange插值基函數.令其中,由條件式(6),有整理,得解得由於兩端取對數再求導,得於是同理可得(8)(9)仿照Lagrange插值餘項的證明方法,若在內的階導數存在，則其插值餘項為多少？(10)其中且與有關.3.Hermite插值餘項作為帶導數插值多項式(7)的重要特例是n=1的情形.這時可取節點為及,插值多項式為,滿足條件(11)相應的插值基函數為,它們滿足條件根據(8)式及(9)式的一般運算式,可得於是滿足條件(11)的插值多項式是其餘項為,由式(10)得注：

N

個條件可以確定階多項式。其餘項為N

1

要求在1個節點x0處直到m0階導數都重合的插值多項式即為在點處的Taylor多項式Newton型Hermite插值（1）單節點的重節點差商（2）多節點的重節點差商插值條件：重節點差商可列表計算：

重節點差商的計算其中，例：設

x0

x1

x2,已知

,

求多項式

P(x)滿足

解：首先，P的階數為3,模仿Lagrange多項式的思想，設其中且

,並估計誤差。4.舉例h0(x)有根x1,x2，且

x1是重根。又:h0(x0)=1C0

h2(x)與h0(x)完全類似。h1(x)有根

x0,x2

由餘下條件

h1(x1)=1和

可解。

(x)

h1

有根

x0,x1,x2又:

C1可解。與Lagrange分析完全類似

六、分段低次插值1.多項式插值的龍格現象例：在[5,5]上考察的Ln(x)。取

-5

-4

-3

-2

-1

0

1

2

3

4

5

-0.5

0

0.5

1

1.5

2

2.5

Ln(x)

f(x)

n

越大，端點附近抖動越大，稱為Runge現象2.分段線性插值在每個區間上，用1階多項式

(直線)逼近f(x):記,易證：當時，一致失去了原函數的光滑性。yxoy=f(x)y=p(x)若令則是分段一次的連續函數且滿足條件

則即為分段線性插值的基函數,

基函數只在附近不為零,在其他地方均為零。這種性質稱為局部非零性質。相應的分段線性插值函數為：分段線性插值的誤差估計定理1

如果在上二階連續可微,則分段線性插值函數的餘項有以下估計

其中,3.分段三次Hermite插值

給定節點，在節點上的函數值及導數值分別為。其中基函數為是分段三次，總體是直至一階導數連續，插值函數為在每個子區間上作兩點三次Hermite插值，因此分段Hermite插值餘項

由三次Hermite插值的餘項可以估計分段Hermite插值的餘項：設是給定節點

上的分段三次Hermite插值函數，，與的誤差限為其中，

要求：插值曲線既要簡單，又要在曲線的連接處比較光滑。

這樣的分段插值函數在分段上要求多項式次數低，這種插值方法稱為——樣條插值。它所對應的曲線稱為樣條曲線，其節點稱為樣點，把滿足這樣條件的插值函數，稱為樣條插值函數，而在節點上不僅連續，還存在連續的低階導數，圖2.1早期機翼下輪廓的放樣如圖2.1所示，在早期的板材曲線切割時，常把富有彈性的細長木條（樣條）固定在樣點上，其他地方讓其自由彎曲，然後畫出長條的曲線稱為樣條曲線，由此啟發設計整體連續光滑的樣條插值函數。

問題

分段低次插值雖然具有簡單、收斂性、整體連續性及數值計算的穩定性等優點，但在節點處常有“尖點”出現，光滑性較差。特別是需要給出節點處的導數值，這在多數問題中是不實際的。如何在沒有節點導數數據時也能達到上述目的？為此引入樣條插值函數。七、三次樣條插值1.引入定義：設對y=f(x)在區間[a,b]上給定一組節點a=x0<x1<x2<…<xn=b和相應的函數值y0,y1,…,yn，如果s(x)具有如下性質：（1）在每個子區間[xi-1,xi](i=1,2,…,n)上s(x)是不高於三次的多項式;（2）s(x)，s’(x)，s

(x)在[a,b]上連續；則稱s(x)為三次樣條函數.如再有（3）s(xi

)=f(xi)(i=0,1,2,…,n)，則稱s(x)為y=f(x)的三次樣條插值函數。注：三次樣條與分段Hermite插值的根本區別在於S(x)自身光滑，不需要知道f的導數值（除了在2個端點可能需要）；而Hermite插值依賴於f在所有插值點的導數值。S(x)H(x)f(x)給定函數f(x)在[a,b]上的一組節點：及節點上的函數值

，函數S(x)是滿足下列條件的函數的三次樣條插值(2)S(x)在子區間

上是三次多項式，記為;；

2.三次樣條插值函數的構造(3)在插值節點處連續，即

(4)即(1)。

要保證S(x)的存在唯一性，必須附加兩個邊界條件。例如，滿足下列四種邊界條件中的任意一個：(1)固支邊界條件（D1-樣條）：3.邊界條件(2)彎矩邊界條件（D2-樣條）：

(3)自然邊界條件（自然樣條）：

(4)週期邊界條件（週期樣條）

：上述幾種邊界條件都有它們的實際意義，從力學角度看，附加邊界條件相當於在細梁兩端加上約束。工程中常用自然邊界條件求樣條插值函數，這類插值函數稱為自然樣條函數，利用插值條件和連續線性條件列出線性方程組並求解，是一種構造樣條的基本方法。構造思想:

通過構造含待定參數的分段三次Hermite插值多項式來構造三次樣條插值函數。構造Hermite插值多項式需要知道被逼近函數f(x)的導數，而導數通常是不知道的。三次樣條插值函數的構造則不需要知道f(x)的導數值，直接將其作為待定參數，利用各節點在連接處的光滑性與連續性條件，建立關係式來確定待定參數，從而構造插值多項式。4.三彎矩方程設f(x)是定義在

[a,b]區間上的一個二次連續可微函數，

為分劃：令i=0,1,2,…,n在每一個社區間[xi-1,xi]i=1,…,n

上都是三次多項式，

S

(x)在

[xi-1,xi]上的運算式為：其中，將（12）兩次積分得：（12）Ai和Bi為積分常數。

因為所以它滿足方程：

（13）解得故求

Mi，確定S(x)的運算式。微分（13）式於是

11111163)(++++++--+=¢iiiiiiiiiMhhyyMhxS由

得（14）則（13）可以寫為各項除以hi+hi+1，並記

（1）D1-樣條：於是可得有給定兩端點導數值：

分別補充為方程組（13）的第一個和最後一個方程組，得D1-樣條的三彎矩方程為：

（2）D2-樣條：給定邊界條件得三彎矩方程若取M0=Mn=0，稱為三次自然樣條。（3）週期樣條：若f(x0)=f(xn),則可將s(x0

)=f(x0)或

s(xn

)=f(xn)去掉，再加入條件①②③可得週期樣條的三彎矩方程補充（14）中的最後及第一個方程經補充後的方程組（13）為（14）其中，對端點條件①，有對端點條件③，有（14）是一個三對角方程組，可用追趕法解之。此方程組係數嚴格對角占優！從而存在唯一解。求出了Mi(i=0,1,…,n)，也就求得了S(x)在各個社區間的運算式Si(x)（i=0,1,2,…,n）5、三次樣條插值的計算步驟(1)根據已知條件順次計算方程組係數

，求出三次樣條插值的三彎矩方程組；

(2)由給定邊界條件，確定

；(3)用追趕法求解方程組(14)，求出

，再使用逆序回代求出

；(4)將求出的代入(13)式，求出

上的三次樣條插值

函數。對給定的點

，須首先確定所在的子區間然後按三次樣條插值的計算步驟計算，，進而求出

。6.演算法若取等距節點

hi=h,i=1,…,n–1（1）

i=1,2,…,nhi=xi–xi-1（2）i=1,2,…,n（3）解n–1階三對角方程組，得M1,M2,…,Mn-1

代入端點條件計算M0,Mn（4）

若取，計算7.三次樣條插值函數的收斂性定義:設是區間上的連續函數，記函數的範數.為定理

設被插值函數為滿足邊界條件①或③的3次樣條插值函數，則在插值區間

上成立餘項估計式其中,汽車刹車距離求解

使用三次樣條插值來預測車輛的停止距離，若給定自然邊界條件進行三次樣條插值，則有

，由公式可計算出代入(14)可得由追趕法可求得代入公式求得三次樣條函數如表2.1所示，插值圖像如圖2.2所示。表2.1圖2.2刹車距離問題的三次樣條插值函數

顯然這個結果與“2秒法則”並不一致，對於每小時40英里以下速率是相當吻合的，而對速率大於每小時40英里的汽車來說則大大低估了停止距離。根據樣條插值函數，計算不同速率的刹車時間為：

由此可以提出一種新的法則為：當速率介於為英里/小時之間時遵循“2秒法則”，當速率介於為英里/小時之間時遵循“3秒法則”，當速率介於為英里/小時之間時遵循“4秒法則”。歷史與注記

1756年，拉格朗日被任命為普魯士科學院通訊院士。1766年任普魯士科學院數學部主任。1786年出任法國米制委員會主任。1795年拉格朗日被選為法蘭西研究院科學院數理委員會主席。1813年4月3日，拿破崙授予他帝國大十字勳章。

拉格朗日在數學上最突出的貢獻是使數學分析與幾何與力學脫離開來，使數學的獨立性更為清楚。他在數值計算上的主要貢獻是發展了歐拉所開創的變分法，為變分法奠定了理論基礎。近百餘年來，數學領域的許多新成就都可以直接或間接地溯源於拉格朗日的工作，在數學史上被認為是對數學的發展產生全面影響的數學家之一。拉格朗日(Joseph-LouisLagrange，1736～1813)拉格朗日1736年生於義大利都靈，1813年卒於巴黎。

在近代，插值法是觀測數據處理和函數製錶所常用的工具，又是導出其他許多數值方法（如數值積分、非線性方程求根、微分方程數值解等）的依據。插值法的一般參考資料見文獻[1,2]，關於樣條的一篇有重要影響的論文參見文獻[3]。

插值一詞最早是由Wallis提出的，西元6世紀，中國劉焯已將等距二次插值用於天文計算。17世紀，牛頓和格雷果裏建立了等距節點上的插值公式。18世紀，拉格朗日給出了更一般的非等距節點上的插值公式。1946年,Schoenberg首先提出了樣條插值函數。[1]P.J.Davies.TheFiniteElementMethod:AFirstApproach.OxfordUniversityPress,NewYork,1980.[2]M.J.D.Powell.ApproximationTheoryandMethods.CambridgeUniversityPress,NewYork,1981.[3]I.J.Schoenberg.Contributionstotheproblemofapproximationofequidistantdatabyanalyticfunctions.QuarterlyofAppliedMathematics4,1946.參考文獻第三章函數逼近與計算

在科學與工程技術的很多領域，人們常碰到大量帶有誤差的實驗數據，這時採用高次插值會出現震盪，採用分段插值則會使函數非常複雜，無法準確反映被側函數的整體性態，因此，不適合用插值法。§1引言

如何在給定精度下，求出計算量最小的近似式，這就是函數逼近要解決的問題。

一、問題的提出二、函數逼近問題的一般提法：對於函數類

中給定的函數

，要求在另一類較簡單的且便於計算的函數類

中尋找一個函數

，使

與

之差在某種度量意義下最小。注：本章中所研究的函數類

通常為區間

上的連續函數，記做

;而函數類

通常是代數多項式或三角多項式。

的函數逼近稱為最佳一致逼近或均勻逼近。三、常用的度量標準：

(一)最佳一致逼近若以函數f(x)和P(x)的最大誤差作為度量誤差

f(x)－P(x)

“大小”的標準,在這種意義下(二)最佳平方逼近：採用

作為度量誤差“大小”標準的函數逼近稱為最佳平方逼近或均方逼近。§2最佳一致逼近一、最佳一致逼近的概念設函數

是區間

對於任意，如果存在多項式

，使不等式則稱多項式

在區間

上一致逼近(或均勻逼近)於函數

定義上的連續函數，給定的成立，。二、最佳一致逼近多項式的存在性定理1（維爾斯特拉斯定理）

若f(x)是區間[a,b]上的連續函數，則對於任意

>0，總存在多項式

P(x)，使對一切a≤x≤b

有上的最佳一致逼近在能否在所有次數不超過n的代數多項式中找到一個

表示由所有次數不超過n的代數多項式構成的線性空間。空間中的最佳一致逼近問題。

意義下:，使得其中，這就是三、四、上最佳一致逼近多項式的存在性

定理2（Borel定理)

在

中都存在對

的最佳一致逼近多項式,記為

的n次最佳一致逼近多項式。稱為簡稱最佳逼近多項式。,使得

成立.對任意的

五、相關概念1、偏差定義

上的偏差。則稱為與在注：

，集合，記作

，它有下界0.顯然，若的全體組成一個2、最小偏差若記集合的下確界為則稱

為

在上的最小偏差。定義

3、偏差點定義

設

若在

上有

則稱

是

的偏差點。

若

若

則稱

則稱

為“正”偏差點。

為“負”偏差點。

4、交錯點組定義

若函數

在其定義域的某一區間

個點

上存在使得

則稱點集

為函數

在區間

上的一個交錯點組，稱為交錯點。點六、上的最佳一致逼近的特徵引理3.1是區間

上的連續函數，是

的n次最佳一致逼近多項式，存在正負偏差點。

則設必同時定理3

（Chebyshev定理）是區間

上的連續函數，

設則

是

的n次最佳一致逼近多項式的充要條件是:

在區間

上存在一個至少由組。個點組成的交錯點推論1是區間

上的連續函數，是

的n次最佳一致逼近多項式，在

記憶體在且保號，在區間

個點組成的交錯點組，端點

都在交錯點組中。

上恰好存在一個由設若則且兩推論2推論3中,若存在對函數

的最佳一致逼近元，則惟一.在是區間上的連續函數，的

次最佳一致逼近多項式是

的某個

次插值多

項式。設則七、一次最佳逼近多項式1、推導過程設

，且

在內不變號，要求在上的一次最佳一致逼近多項式由推論1，在上恰好有3個點構成的交錯且區間端點屬於這個交錯點組，組，設另一個交錯點為則解得即即2、幾何意義？3、舉例求在上的最佳一次逼近多項式。解：由可算出故解得由得於是得的最佳一次逼近多項式為故誤差限為(*)在（*）式中若令，則可得一個求根的公式八、Chebyshev多項式及其應用(1)定義稱為n次Chebyshev多項式.[注]Itisveryimportant

令則而故為關於的次代數多項式。(2)性質正交性：由Tn(x)所組成的序列{Tn(x)}是在區間[-1,1]上帶權

的正交多項式序列。

且

遞推關係相鄰的三個切比雪夫多項式具有如下遞推關係式：

奇偶性：

切比雪夫多項式

，當