第一章緒論-數(shù)值

數(shù)值分析NumericalAnalysis西安電子科技大學理學院數(shù)學科學系Dept.ofMathematicsSchoolofScienceXidianUniv.什么是數(shù)值分析?NumericalAnalysisisconcernedwiththedesignandanalysisofalgorithmsforsolvingmathematicalproblemsthatariseinmanyfields,especiallyscienceandengineering.----MichaelT.HeathNumericalanalysisisthestudyofalgorithmsfortheproblemsofcontinuousmathematics.----LloydN.TrefethenChapter1Introduction“數(shù)值分析”就是研究在計算機上解決數(shù)學問題的理論和數(shù)值方法?數(shù)值算法的構造:計算公式和算法步驟?算法的理論分析：誤差分析、收斂性、穩(wěn)定性等什么是數(shù)值分析?Chapter1Introduction提問：數(shù)值分析是做什么用的？數(shù)值分析輸入復雜問題或運算計算機近似解Chapter1Introduction數(shù)值分析的學科別名?計算方法?科學與工程計算Chapter1Introduction科學計算的重要性?科學計算是工程實踐的重要工具?科學計算是繼理論與實驗后另一科學研究手段Chapter1IntroductionChapter1Introduction科學計算的國家戰(zhàn)略與發(fā)展(1)?1983年一個由美國著名數(shù)學家拉克斯(P.Lax)為首的不同學科的專家委員會向美國政府提出的報告之中，強調“科學計算是關系到國家安全、經(jīng)濟發(fā)展和科技進步的關鍵性環(huán)節(jié)，是事關國家命脈的大事?！?1984年美國政府大幅度地增加對科學計算經(jīng)費的支持,新建成五個國家級超級計算中心（分別在普林斯頓大學、圣地亞哥、伊里諾大學、康奈爾大學、匹茲堡大學），配備當時最高性能的計算機，建立NSF-net新網(wǎng)絡。?80年代中期我國將“大規(guī)?？茖W與工程計算”列入國家資助重大項目。?1987年起美國NSF把“科學與工程計算”，“生物工程”“全局性科學”作為三大優(yōu)先資助的領域。?1990年美國國家研究委員會發(fā)表《振興美國數(shù)學：90年代的計劃》的報告，建議對由計算引發(fā)的數(shù)學給予特殊的鼓勵和資助。?1991年以美國總統(tǒng)倡議的形式提出了“高性能計算與通信HPCC計劃”，這是為了保持和提高美國在計算和網(wǎng)絡的所有先進領域中的領導地位而制定的。其發(fā)展的關鍵技術是可擴展的大規(guī)模并行計算。?1995年美國為了確保核庫存的性能安全性、可靠性和更新需要而實施的“加速戰(zhàn)略計算創(chuàng)新ASCI計劃”?？茖W計算的國家戰(zhàn)略與發(fā)展(2)Chapter1Introduction戰(zhàn)略計算?這是因為美國克林頓總統(tǒng)在1995年8月11日宣布：“美國決定謀求真正的“零當量”全面禁止試驗核武器條約”。?這并不意味著核競賽的結束，恰恰相反是核武器計劃新時代的開始，要求通過逼真的建模和模擬計算來取代傳統(tǒng)的反復試驗的工程處理方法，這主要依賴于先進的數(shù)值計算和模擬能力。?1995年8月22日（即美國總統(tǒng)宣布決定后的11天），能源部DOE就采購世界上最快的一臺計算機（速度超過萬億次運算）交付圣地亞哥實驗室（96年12月安裝）。?1998年7月30-31日，美國DOE/FNS共同聯(lián)合組織召開了關于“先進科學計算”的全國會議，會議強調科學模擬的重要性，希望應用科學模擬來攻克復雜的科學與工程難題。Chapter1IntroductionSomepastdevelopmentsinscientificcomputing----LloydN.Trefethen?1970--1998quasi-NewtoniterationsmultigridAdaptivityMatlabstiffODEsolversinteriorpointmethodssoftwarelibrariesspectralmethodssparseanditerativelinearalgebra

?Before1940Newton'smethodGaussianeliminationGaussquadrature(求積法Least-squaresfittingAdamsandRunge-KuttaformulasRichardsonextrapolation

?1940--1970floatingpointarithmeticFortranfinitedifferencesfiniteelementssimplexalgorithm單純形算法MonteCarloFFTorthogonallinearalgebraChapter1IntroductionThefuturedevelopmentinscientificcomputing----LloydN.Trefethen?1998—2048linearalgebrainO(N2+)flopsmultipolemethodsbreakthroughsinpreconditioners,spectralmethods,timesteppingforPDE*speechandgraphicseverywhere*fullyintelligent,adaptivenumerics*lossofdeterminism*seamlessinteroperability*massivelyparallelcomputingmadepossiblebyideasrelatedtothehumanbrain*newprogrammingmethodsmadepossiblebyideasrelatedtonaturalselectionChapter1Introduction數(shù)值分析課的主要內容Chapter1Introduction?插值和函數(shù)逼近?數(shù)值微分和數(shù)值積分?常微分方程數(shù)值解法非線性方程的迭代法?數(shù)值代數(shù):求解線性和非線性方程組的直接法和間接法?代數(shù)特征值問題的數(shù)值解法數(shù)值分析的學科特點實用性理論性實踐性1面向計算機，根據(jù)計算機的特點提供可行的有效算法；?只提供加減乘除和邏輯運算?串行機和并行機2有可靠的理論分析:算法的收斂性、穩(wěn)定性和誤差分析；3有好的計算復雜性:時間和空間復雜性；4有充分的數(shù)值實驗證明算法的有效性。Chapter1Introduction構造數(shù)值算法的基本思想近似替代離散化遞推化Chapter1Introduction學習“計算方法”需注意如下幾點1.要掌握算法的原理和思想2.要掌握算法的處理技巧,步驟和計算公式3.重視誤差分析,理解收斂性,穩(wěn)定性分析的理論4.做一定的理論分析證明與計算練習5.上機實踐Chapter1Introduction§2誤差的基本理論

/*Introductionoferror*/§2Introductionoferror

§2Introductionoferror

1.誤差的來源與分類

/*Source&Classification*/從實際問題中抽象(簡化)出數(shù)學模型,模型與實際問題之間存在誤差——模型誤差/*ModelingError*/§2Introductionoferror

通過測量得到模型中參數(shù)的值，觀測產(chǎn)生誤差

——觀測誤差/*MeasurementError*/§2Introductionoferror

采用數(shù)值方法求模型的近似解，近似解與精確解之間有誤差——方法誤差(截斷誤差/*TruncationError*/)§2Introductionoferror

機器字長有限,數(shù)據(jù)在計算機中表示產(chǎn)生誤差——舍入誤差

/*RoundoffError*/§2Introductionoferror

§2Introductionoferror

大家一起猜？11/e解法之一：將作Taylor展開后再積分S4R4

/*Remainder*/取則稱為截斷誤差/*TruncationError*/|

舍入誤差

/*RoundoffError*/|=0.747……由截去部分/*excludedterms*/引起由留下部分/*includedterms*/引起§2Introductionoferror

2.傳播與積累/*Spread&Accumulation*/例：蝴蝶效應——紐約的一只蝴蝶翅膀一拍，風和日麗的北京就刮起臺風來了？！NYBJ以上是一個病態(tài)問題

/*ill-posedproblem*/關于本身是病態(tài)的問題，我們還是留給數(shù)學家去頭痛吧！§2Introductionoferror

例6：計算公式一：注意此公式精確成立記為則初始誤差????!!!Whathappened?!§2Introductionoferror

考察第n步的誤差我們有責任改變。造成這種情況的是不穩(wěn)定的算法/*unstablealgorithm*/迅速積累，誤差呈遞增走勢?？梢姵跏嫉男_動公式二：注意此公式與公式一在理論上等價。方法：先估計一個IN

,再反推要求的In(n<<N)。可取§2Introductionoferror

取Wejustgotlucky?§2Introductionoferror

考察反推一步的誤差：以此類推，對n<N有：誤差逐步遞減,這樣的算法稱為穩(wěn)定的算法/*stablealgorithm*/

在我們今后的討論中，誤差將不可回避，算法的穩(wěn)定性會是一個非常重要的話題。§2Introductionoferror

§3

誤差與有效數(shù)字/*ErrorandSignificantDigits*/§3

ErrorandSignificantDigits

例7.用一把有毫米的刻度的米尺,來測量桌子的長度,讀出的長度x*=1235mm§3

ErrorandSignificantDigits

注：e理論上講是唯一確定的，可能取正，也可能取負。e>0不唯一，當然e越小越具有參考價值。Icantellthatthispart’sdiameteris20cm1cm.Icantellthatdistancebetweentwoplanetsis1millionlightyear±1lightyear.Ofcoursemineismoreaccurate!Theaccuracyrelatestonotonlytheabsoluteerror,butalsotothesizeoftheexactvalue.例5中：§3

ErrorandSignificantDigits

§3

ErrorandSignificantDigits

§3

ErrorandSignificantDigits

有效數(shù)字/*significantdigits*/§3

ErrorandSignificantDigits

例8例9Def1.例10問：有幾位有效數(shù)字？請證明你的結論。證明：有位有效數(shù)字，精確到小數(shù)點后第位。43注：0.2300有4位有效數(shù)字，而00023只有2位有效。12300如果寫成0.123105，則表示只有3位有效數(shù)字。

數(shù)字末尾的0不可隨意省去！用科學計數(shù)法，記（其中）。若（即的截取按四舍五入規(guī)則），則稱有n位有效數(shù)字，精確到。Def2.§3

ErrorandSignificantDigits

Def1,2例11例12§3

ErrorandSignificantDigits

有效數(shù)字與相對誤差的關系

有效數(shù)字

相對誤差限§3

ErrorandSignificantDigits

相對誤差限有效數(shù)字§3

ErrorandSignificantDigits

例13例14§3

ErrorandSignificantDigits

§4

函數(shù)的誤差估計/*ErrorEstimationforFunctions*/問題：對于y=f(x)，若用x*

取代x，將對y

產(chǎn)生什么影響？分析：e(y)=f(x*)f(x)e(x)=x*xMeanValueTheorem=f()(x*x)x*與x非常接近時，可認為f()

f(x*)，則有：|e(y)||f(x*)|·|e(x)|即：x*產(chǎn)生的誤差經(jīng)過f作用后被放大/縮小了|f(x*)|倍。故稱|f(x*)|為放大因子

/*amplificationfactor*/

或絕對條件數(shù)

/*absoluteconditionnumber*/.§4

ErrorEstimationforFunctions相對誤差條件數(shù)

/*relativeconditionnumber*/

f的條件數(shù)在某一點是小\大，則稱f在該點是好條件的

/*well-conditioned*/\壞條件的

/*ill-conditioned*/。MeanValueTheorem§4

ErrorEstimationforFunctions例15:計算y=lnx。若x

20，則取x的幾位有效數(shù)字可保證y的相對誤差<0.1%?解：設截取

n

位有效數(shù)字后得x*

x，則估計x和y的相對誤差上限滿足近似關系不知道怎么辦??？x可能是20.#，也可能是19.#，取最壞情況，即a1=1。n4例：計算，取4

位有效，即,則相對誤差§4

ErrorEstimationforFunctions§4

ErrorEstimationforFunctions例16§4

ErrorEstimationforFunctions特例----算術運算的誤差和絕對誤差限分析:§4

ErrorEstimationforFunctions§4

ErrorEstimationforFunctions§4

ErrorEstimationforFunctions特例----算術運算