《数值分析》课程PPT教学课件（Numerical Analysis）Chapter 2 the numerical solution of the nonlinear equations

Chapter 2 the numerical solution of thenonlinear equationsSection I Import of practical problemSection II DichotomySection III Fixed point iteration methodSection IV Newton methodSection V Secant Method

Section II Dichotomy Chapter 2 the numerical solution of the nonlinear equations Section III Fixed point iteration method Section IV Newton method Section V Secant Method Section I Import of practical problem

S 1 Import of practical problemThe nonlinear phenomenon widely exists in the material worldand the social life,Many practical problems are transformed into nonlinear equationsortheproblemtosolveequations.We look at an example.In celestial mechanics, Kepler equationx-t-sinx=0,0<8<1Where t represents time, x represents the radian, a planetarymotion track x is a function of t.There is a sole x corresponding to each t in Kepler equationIn this chapter, we discuss the single-variable nonlinear equationf(x)= 0the problem of finding roots, here x E R, f(x) eC[a,b]

§1 Import of practical problem The nonlinear phenomenon widely exists in the material world and the social life, Many practical problems are transformed into nonlinear equations, or the problem to solve equations. We look at an example. In celestial mechanics, Kepler equation x t x − − =     sin 0,0 1 Where t represents time, x represents the radian, a planetary motion track x is a function of t. There is a sole x corresponding to each t in Kepler equation. In this chapter, we discuss the single-variable nonlinear equation. f x( ) 0 = the problem of finding roots, here x f x C a b   R, ( ) [ , ]

Seeking the root of this equation f (x) = 0Principle:Iff eC[a, bl, and f(a) : f(b)< O, then there must beone root off on (a, b)1、 The Graphic method: Give sketche of y=f(x) , determine theapproximate location of the root.2、 Test method: take some of the data appropriately to test,search out the inter-cell of sign changes, namely the inter-cell tomeet f(ak):f(bk)<0

Seeking the root of this equation f (x) = 0 Principle:If f C[a, b]，and f (a) · f (b) < 0，then there must be one root of f on (a, b) . 1、The Graphic method: Give sketche of y＝f (x) , determine the approximate location of the root. 2、Test method: take some of the data appropriately to test, search out the inter-cell of sign changes, namely the inter-cell to meet f (ak )·f (bk ) < 0

s2 Dichotomy41中弟ab[f(x)<&2Xk+1-x|<8orCan not guaranteethe accuracyof x82x

a b x1 x2 a b 1 1 x x ε k+ − k  2 f (x)  ε or x*  2 x* x §2 Dichotomy Can not guarantee the accuracy of x

ErronAnalysis:a+bb-aStep 1 generatehas the error k,-x*|≤Xi22b-athe k-th step xk has the error x -x*|≤24the number k of dichotomy required can be estimated according to thgivenaccuracy:[n(b - a)- In a]b-ak<82kIn 2① Simple;② The require of f (x) is not high ( just continuous) Can not demand complex roots and even re-root②Slow convergenceNote: when finding roots by dichotomy, it is best to give thesketche of f (x) in order to determine the approximate locationof the root

Error Analysis： Step 1 generate 2 1 a b x + = has the error 2 1 b a |x x*| − −  the k-th step xk has the error k k b a |x x*| 2 − −  the number k of dichotomy required can be estimated according to the given accuracy  ：  ( )  ln 2 ln ln 2 b a ε ε k b a k − −    − ① Simple; ② The require of f (x) is not high ( just continuous). ① Can not demand complex roots and even re-root ② Slow convergence Note: when finding roots by dichotomy, it is best to give the sketche of f (x) in order to determine the approximate location of the root

3 Fixed point iteration methodI Fixed point iteration methodEquivalentf (x) = 0x=g (x)transformationthe fixed point g(x)the rooot of f (x) =0Starting from an initial value xo,calculate xi = g(xo), x2 =Thinkingg(x),.., k+ = g(xx),...if (, J- is convergence, existx* to make lim x, = x*, and g is continuous, fromthe lim Xk+1 = lim g(xk) can get x* = g(x* ), that x* isαa fixed point of g , which is the root of f =0

f (x) = 0 x = g (x) Equivalent transformation the rooot of f (x) ＝ 0 the fixed point g(x) Thinking Starting from an initial value x0 ,calculate x1 = g(x0 ), x2 = g(x1 ), ., xk+1 = g(xk ), . if is convergence，exist x* to make , and g is continuous，from the can get x* = g(x* )，that x* is a fixed point of g ，which is the root of f ＝0。    k k=0 x lim x x * k k = → ( ) k k k k x g x → + → lim 1 = lim §3 Fixed point iteration method Ⅰ、Fixed point iteration method

yyJ=xy=xPoPiy=g(x)-1Po-1--y=g(x)11:Pi--1-1-V-1-1--1111-1X1X1北*XiXoXiXoJyJ=XJ=xy=g(x)y=g(x)PoXPoX71P1-I7Pi1--1--1-1----------1.LXXI七*北弟XiXoXoXi

x y y = x x y y = x x y y = x x y y = x x* x* x* x* y=g(x) y=g(x) y=g(x) y=g(x) x0 p0 x1 p1 ✓ x0 p0 x1 p1 ✓ x0 p0 x1 p1  x0 p0 x1 p1 

Example 1.Solving equations 2x3 -x-1= 0 byiterative methodSlove: (1) Take the original equations into the equivalentequationx=2x3 -1If we take the initial value xo = O,According to the iterative method(3),we can getX = 2x -1=-1X2 =2xi -1=-3x = 2x -1 = -55Obviously iterative method is divergence

Example 1. 2 1 0 3 x − x − = Slove: 2 1 3 x = x − (1) Take the original equations into the equivalent equation 0, x0 = 2 1 3 x1 = x0 − = −1 2 1 3 x2 = x1 − = −3 2 1 3 x3 = x2 − = −55  Obviously iterative method is divergence Solving equations by iterative method If we take the initial value According to the iterative method(3),we can get

(2) If the original equation into an equivalent equationx+1x=32Taking the initial valueX = 0Xo +11xi=~0.79373122X +11.79373X2=～ 0.9644322

3 2 +1 = x x (2) If the original equation into an equivalent equation x0 = 0 Taking the initial value  0.7937 3 1 2 2 +1 = x x 3 2 1.7937 =  0.9644 3 0 1 2 +1 = x x 3 2 1 =

And so on, tox2 = 0.9644x3 = 0.9940x4 = 0.9990x5 =0.9998x6 = 1.0000x7 = 1.0000Have convergence, therefore, the solution of the equation isx = 1.0000There are different results with different Iterativeschemes in the sameequation,relate to Iterative function structureWhat forms of iteration to converge?

x = 1.0000 There are different results with different Iterative schemes in the same equation， What forms of iteration to converge? relate to Iterative function structure x2 = 0.9644 x3 = 0.9940 x4 = 0.9990 x5 = 0.9998 x6 = 1.0000 x7 = 1.0000 And so on, to Have convergence, therefore, the solution of the equation is