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

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

/*Introductionoferror*/§2Introductionoferror

§2Introductionoferror

1.誤差的來源與分類

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

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

——觀測(cè)誤差/*MeasurementError*/§2Introductionoferror

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

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

/*RoundoffError*/§2Introductionoferror

§2Introductionoferror

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

/*Remainder*/取則稱為截?cái)嗾`差/*TruncationError*/|

舍入誤差

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

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

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

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

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

,再反推要求的In(n<<N)?？扇　?Introductionoferror

取Wejustgotlucky?§2Introductionoferror

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

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

§3

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

ErrorandSignificantDigits

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

ErrorandSignificantDigits

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

ErrorandSignificantDigits

§3

ErrorandSignificantDigits

§3

ErrorandSignificantDigits

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

ErrorandSignificantDigits

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

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

ErrorandSignificantDigits

Def1,2例11例12§3

ErrorandSignificantDigits

有效數(shù)字與相對(duì)誤差的關(guān)系

有效數(shù)字

相對(duì)誤差限§3

ErrorandSignificantDigits

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

ErrorandSignificantDigits

例13例14§3

ErrorandSignificantDigits

§4

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

取代x，將對(duì)y

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

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

/*amplificationfactor*/

或絕對(duì)條件數(shù)

/*absoluteconditionnumber*/.§4

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

/*relativeconditionnumber*/

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

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

/*ill-conditioned*/。MeanValueTheorem§4

ErrorEstimationforFunctions例15:計(jì)算y=lnx。若x

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

n

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

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

位有效，即,則相對(duì)誤差§4

ErrorEstimationforFunctions§4

ErrorEstimationforFunctions例16§4

ErrorEstimationforFunctions特例----算術(shù)運(yùn)算的誤差和絕對(duì)誤差限分析:§4

ErrorEstimationforFunctions§4

ErrorEstimationforFunctions§4

ErrorEstimationforFunctions特例----算術(shù)運(yùn)算