CIS 51 – Numerical MethodsDepartment of Computer ：顺541–数值方法计算机系

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

1、CSE 541 - DifferentiationRoger CrawfisDecember 6, 2021OSU/CIS 5412Numerical Differentiation The mathematical definition: Can also be thought of as the tangent line.0()( )( )limhf xhf xfxhxx+hDecember 6, 2021OSU/CIS 5413Numerical Differentiation We can not calculate the limit as h goes to zero, so we

2、 need to approximate it. Apply directly for a non-zero h leads to the slope of the secant curve.xx+hDecember 6, 2021OSU/CIS 5414Numerical Differentiation This is called Forward Differences and can be derived using Taylors Series:22()( )( )( )2!()( )( )( )2!()( )( )( )2!()( )( )0hf xhf xfx hfhf xhf x

3、fx hff xhf xhfxfhf xhf xfx as hhTheoretically speakingDecember 6, 2021OSU/CIS 5415Truncation Errors Let f(x) = a+e, and f(x+h) = a+f. Then, as h approaches zero, ea 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 mo

4、st significant digit in the subtraction. Dividing by h, leads to a very wrong answer for f(x).December 6, 2021OSU/CIS 5416Error TradeoffUsing a smaller step size reduces truncation error.However, it increases the round-off error.Trade off/diminishing returns occurs: Always think and test!Log errorLo

5、g step sizeTruncation errorRound off errorTotal errorPoint of diminishingreturnsDecember 6, 2021OSU/CIS 5417Numerical Differentiation This formula favors (or biases towards) the right-hand side of the curve. Why not use the left?xx+hx-hDecember 6, 2021OSU/CIS 5418Numerical Differentiation This leads

6、 to the Backward Differences formula.2()( )( )( )2!( )()( )( )2!( )()( )0hf xhf xfx hff xf xhhfxfhf xf xhfx as hhDecember 6, 2021OSU/CIS 5419Numerical Differentiation Can we do better? Lets average the two: This is called the Central Difference formula.1()( )( )()()()( )22f xhf xf xf xhf xhf xhfxhhh

7、Forward difference Backward differenceDecember 6, 2021OSU/CIS 54110Central Differences This 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-hDecember 6, 2021OSU

8、/CIS 54111Numerical Differentiation Is this any better? Lets use Taylors Series to examine the error:232333()( )( )( )( )23!()( )( )( )( )23!()()2( )( )( )3!3!hhf xhf xfx hfxfhhf xhf xfx hfxfsubtractinghhf xhf xhfx hffDecember 6, 2021OSU/CIS 54112Central Differences The central differences formula h

9、as much better convergence. Approaches the derivative as h2 goes to zero!2()()1( )( ),26f xhf xhfxfhxh xhh2()()( )2f xhf xhfxO hhDecember 6, 2021OSU/CIS 54113Warning Still have truncation error problem. Consider the case of: Build a table withsmaller values of h. What about largevalues of h for this

10、function?( )100100100( )21,0.000333,60.01000330.0099966( )0.0100500.000666666Relative error:0.01-0.0100500.5%0.01xf xxhxhfxhat xhwith significantdigitsfxDecember 6, 2021OSU/CIS 54114Richardson Extrapolation Can we do better? Is my choice of h a good one? Lets subtract the two Taylor Series expansion

11、s again: 2345452345455533()( )( )( )( )( )( )23!4!5!()( )( )( )( )( )( )23!4!5!( )( )()()2( )222( )3!3!5!hhhhf xhf xfx hfxfxfxfxhhhhf xhf xfx hfxffxfxsubtractingfxfxhf xhf xhfx hhhfxDecember 6, 2021OSU/CIS 54115Richardson Extrapolation Assuming the higher derivatives exist, we can hold x fixed (whic

12、h also fixes the values of f(x), to obtain the following formula. Richardson Extrapolation examines the operator below as a function of h.2462461( )()()2fxf xhf xha ha ha hh1( )()()2hf xhf xhhDecember 6, 2021OSU/CIS 54116Richardson Extrapolation This function approximates f(x) to O(h2) as we saw ear

13、lier. Lets look at the operator as h goes to zero.246246246246( )( )( )( )2222hfxa ha ha hhhhhfxaaaSame leading constantsDecember 6, 2021OSU/CIS 54117Richardson Extrapolation Using these two formulas, we can come up with another estimate for the derivative that cancels out the h2 terms.46464315( )4

14、( )3( )24161( )( )( )( )232hhfxa ha horhhfxhO h new estimatedifference between old and new estimatesExtrapolates by assuming the new estimate undershot.December 6, 2021OSU/CIS 54118Richardson Extrapolation If h is small (h1), then h4 goes to zero much faster than h2. Cool! Can we cancel out the h6 t

15、erm? Yes, by using h/4 to estimate the derivative.December 6, 2021OSU/CIS 54119Richardson Extrapolation Consider the following property: where L is unknown, as are the coefficients, a2k.221221( )( )kkkkkkhfxa hLa h 0lim ( )hLhfxDecember 6, 2021OSU/CIS 54120Richardson Extrapolation Do not forget the

16、formal definition is simply the central-differences formula: New symbology (is this a word?):1( )()()2hf xhf xhh21,02,02nknkhD nhLA kFrom previous slideDecember 6, 2021OSU/CIS 54121Richardson Extrapolation D(n,0) is just the central differences operator for different values of h. Okay, so we proceed

17、 by computing D(n,0) for several values of n. Recalling our cancellation of the h2 term.441( )( )( )( )2321(1,0)(1,0)(0,0)4 1hhfxhO hDDDO hDecember 6, 2021OSU/CIS 54122Richardson Extrapolation If we let hh/2, then in general, we can write: Lets denote this operator as:41( )( ,0)( ,0)(1,0)4 12nhfxD n

18、D nD nO11,1( ,0),01,041D nD nD nD nDecember 6, 2021OSU/CIS 54123Richardson Extrapolation Now, we can formally define Richardsons extrapolation operator as: or41,( ,1)1,1 ,14141mmmD n mD n mD nmmnnew estimateold estimate1,( ,1),11,141mD n mD n mD n mD nmDecember 6, 2021OSU/CIS 54124Richardson Extrapo

19、lation Now, we can formally define Richardsons extrapolation operator as: Memorize me!1,( ,1),11,141mD n mD n mD n mD nmDecember 6, 2021OSU/CIS 54125Richardson Extrapolation Theorem These terms approach f(x) very quickly.21,2knk mhD n mLA k mOrder starts much higher!December 6, 2021OSU/CIS 54126Rich

20、ardson Extrapolation Since 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.0,01,01,12,02,12,2,0,1,2,DDDDDDD ND ND ND N NDecember 6, 2021OSU/CIS 54127Example523cos(100( )11.3,1280,016.6963861,040.5833932,0109.3

21、225283,0135.0317474,0142.0686155,0143.866937xf xxxhDDDDDD10.002444096h December 6, 2021OSU/CIS 54128Example0,016.6963861,040.5833931,148.5833932,0109.3225282,1132.2355743,0135.0317473,1143.6014874,0142.0686154,1144.4142385,0143.8669375,1144.466377DDDDDDDDDDD13extrapolateDecember 6, 2021OSU/CIS 54129

22、Example0,016.6963861,040.5833931,148.5833932,0109.3225282,1132.2355742,2137.8148973,0135.0317473,1143.6014873,2144.3592144,0142.0686154,1144.4142384,2144.4684215,0143.8669375,1144DDDDDDDDDDDDDD.4663775,2144.469853D115extrapolateDecember 6, 2021OSU/CIS 54130Example Which converges up to eight decimal

23、 places. Is it accurate?16.69638640.58339348.583393109.322528132.235574137.814897135.031747143.601487144.359214144.463092142.068615144.414238144.468421144.470154 144.470182143.866937144.466377144.469853144.469876 144.4698755,D5144.46987511023extrapolate1255extrapolate163extrapolate115extrapolate13ex

24、trapolateDecember 6, 2021OSU/CIS 54131Example We can look at the (theoretical) error term on this example. Taking the derivative:255 1122575,5,5211.3(6,5),540962kkkkhDLA khfAA k 2-144(1.3)144.469874253f Round-off errorDecember 6, 2021OSU/CIS 54132Second Derivatives What if we need the second derivat

25、ive? Any guesses? 234545234545()( )( )( )( )( )( )23!4!5!()( )( )( )( )( )( )23!4!5!hhhhf xhf xfx hfxfxfxfxhhhhf xhf xfx hfxffxfxDecember 6, 2021OSU/CIS 54133Second Derivatives Lets cancel out the odd derivatives and double up the even ones: Implies adding the terms together. 244()()2 ( )2( )2( )24!

26、hhf xhf xhf xfxfxDecember 6, 2021OSU/CIS 54134Second Derivatives Isolating the second derivative term yields: With an error term of:2()2 ( )()( )f xhf xf xhfxh 42112Eh f December 6, 2021OSU/CIS 54135Partial Derivatives Remember: Nothing special about partial derivatives:,2,2f xh yf xh yfx yxhf x yhf x yhfx yyhDecember 6, 2021OSU/CIS 54136Calculating the Gradient For lab 2, you need to calculate the gradient. Just use central differences for each partial derivative. Remember to normalize it (divide by its length).