CIS-541-–-Numerical-s---Department-of-Computer-：顺541–数值方法-计算机系-资料课件

《CIS-541-–-Numerical-s---Department-of-Computer-：顺541–数值方法-计算机系-资料课件》由会员分享，可在线阅读，更多相关《CIS-541-–-Numerical-s---Department-of-Computer-：顺541–数值方法-计算机系-资料课件（38页珍藏版）》请在装配图网上搜索。

1、CSE 541-DifferentiationRoger Crawfis04 May 2024OSU/CIS 5412Numerical DifferentiationThe mathematical definition:Can also be thought of as the tangent line.xx+h04 May 2024OSU/CIS 5413Numerical DifferentiationWe can not calculate the limit as h goes to zero,so we need to approximate it.Apply directly

2、for a non-zero h leads to the slope of the secant curve.xx+h04 May 2024OSU/CIS 5414Numerical DifferentiationThis is called Forward Differences and can be derived using Taylors Series:Theoretically speaking04 May 2024OSU/CIS 5415Truncation ErrorsLet f(x)=a+e,and f(x+h)=a+f.Then,as h approaches zero,e

3、a and fa.With limited precision on our computer,our representation of f(x)a f(x+h).We can easily get a random round-off bit as the most significant digit in the subtraction.Dividing by h,leads to a very wrong answer for f(x).04 May 2024OSU/CIS 5416Error TradeoffUsing a smaller step size reduces trun

4、cation error.However,it increases the round-off error.Trade off/diminishing returns occurs:Always think and test!Log errorLog step sizeTruncation errorRound off errorTotal errorPoint of diminishingreturns04 May 2024OSU/CIS 5417Numerical DifferentiationThis formula favors(or biases towards)the right-

5、hand side of the curve.Why not use the left?xx+hx-h04 May 2024OSU/CIS 5418Numerical DifferentiationThis leads to the Backward Differences formula.04 May 2024OSU/CIS 5419Numerical DifferentiationCan we do better?Lets average the two:This is called the Central Difference formula.Forward difference Bac

6、kward difference04 May 2024OSU/CIS 54110Central DifferencesThis formula does not seem very good.It does not follow the calculus formula.It takes the slope of the secant with width 2h.The actual point we are interested in is not even evaluated.xx+hx-h04 May 2024OSU/CIS 54111Numerical DifferentiationI

7、s this any better?Lets use Taylors Series to examine the error:04 May 2024OSU/CIS 54112Central DifferencesThe central differences formula has much better convergence.Approaches the derivative as h2 goes to zero!04 May 2024OSU/CIS 54113WarningStill have truncation error problem.Consider the case of:B

8、uild a table withsmaller values of h.What about largevalues of h for thisfunction?04 May 2024OSU/CIS 54114Richardson ExtrapolationCan we do better?Is my choice of h a good one?Lets subtract the two Taylor Series expansions again:04 May 2024OSU/CIS 54115Richardson ExtrapolationAssuming the higher der

9、ivatives exist,we can hold x fixed(which also fixes the values of f(x),to obtain the following formula.Richardson Extrapolation examines the operator below as a function of h.04 May 2024OSU/CIS 54116Richardson ExtrapolationThis function approximates f(x)to O(h2)as we saw earlier.Lets look at the ope

10、rator as h goes to zero.Same leading constants04 May 2024OSU/CIS 54117Richardson ExtrapolationUsing these two formulas,we can come up with another estimate for the derivative that cancels out the h2 terms.new estimatedifference between old and new estimatesExtrapolates by assuming the new estimate u

11、ndershot.04 May 2024OSU/CIS 54118Richardson ExtrapolationIf h is small(h1),then h4 goes to zero much faster than h2.Cool!Can we cancel out the h6 term?Yes,by using h/4 to estimate the derivative.04 May 2024OSU/CIS 54119Richardson ExtrapolationConsider the following property:where L is unknown,as are

12、 the coefficients,a2k.04 May 2024OSU/CIS 54120Richardson ExtrapolationDo not forget the formal definition is simply the central-differences formula:New symbology(is this a word?):From previous slide04 May 2024OSU/CIS 54121Richardson ExtrapolationD(n,0)is just the central differences operator for dif

13、ferent values of h.Okay,so we proceed by computing D(n,0)for several values of n.Recalling our cancellation of the h2 term.04 May 2024OSU/CIS 54122Richardson ExtrapolationIf we let hh/2,then in general,we can write:Lets denote this operator as:04 May 2024OSU/CIS 54123Richardson ExtrapolationNow,we c

14、an formally define Richardsons extrapolation operator as:ornew estimateold estimate04 May 2024OSU/CIS 54124Richardson ExtrapolationNow,we can formally define Richardsons extrapolation operator as:Memorize me!04 May 2024OSU/CIS 54125Richardson Extrapolation TheoremThese terms approach f(x)very quickl

15、y.Order starts much higher!04 May 2024OSU/CIS 54126Richardson ExtrapolationSince m n,this leads to a two-dimensional triangular array of values as follows:We must pick an initial value of h and a max iteration value N.04 May 2024OSU/CIS 54127Example04 May 2024OSU/CIS 54128Example04 May 2024OSU/CIS 5

16、4129Example04 May 2024OSU/CIS 54130ExampleWhich converges up to eight decimal places.Is it accurate?04 May 2024OSU/CIS 54131ExampleWe can look at the(theoretical)error term on this example.Taking the derivative:2-144Round-off error04 May 2024OSU/CIS 54132Second DerivativesWhat if we need the second

17、derivative?Any guesses?04 May 2024OSU/CIS 54133Second DerivativesLets cancel out the odd derivatives and double up the even ones:Implies adding the terms together.04 May 2024OSU/CIS 54134Second DerivativesIsolating the second derivative term yields:With an error term of:04 May 2024OSU/CIS 54135Parti

18、al DerivativesRemember:Nothing special about partial derivatives:04 May 2024OSU/CIS 54136Calculating the GradientFor lab 2,you need to calculate the gradient.Just use central differences for each partial derivative.Remember to normalize it(divide by its length).谢谢你的阅读v知识就是财富v丰富你的人生 Thank you拯畏怖汾关炉烹霉躲渠早膘岸缅兰辆坐蔬光膊列板哮瞥疹傻俘源拯割宜跟三叉神经痛-治疗三叉神经痛-治疗