Numerical Analysis Course

Numerical Analysis CourseBaghdad University,Faculty of Sciences,Department of Computer SciencesSecond Class Syllabus AcademicDr. Ali H. KashmarYear 2018/20191

Syllabus for Numerical AnalysisCourse (First Semester), 2018-2019Second class; Computer Science Dept.;Collage of Sciences; University of Baghdad Weekly hours: 4 hours:10:30 am -12:30 pm 2h Theoretical:(A)(Room No.3 on Wednesday)(B):Room No.7 on Thursday: 2h practical/MatLab No.1(Numerical AnalysisLab):(A,G1,G2 and B, G1)8:30 am-1:30 pm.(Sunday/(B, G2)Tuesday: 10:30-12:30) pm Dr. Ali H. Kashmar Room No. SC 212 2

Chapter 1: Root Finding(Solving Transcending Equations): Bisection Method.Newton-Raphson Method.Secant Method.Fixed Point Method.False Position Method.3

ReferencesCurtis F. Gerald and Patrick O. Wheatly,2016,“Applied Numerical Analysis”, 4th Edition, William S. Dorn and Daniel D.Mc Craben,2014, “Numerical Methods with Matlab”,John Wiley and Sons. Curtio F. Gerald, 2012, “Applied methodsfor Mathematics”, Science and Engineering,Prentice Hall of India Private limited NewDelhi. Kendall Atkenson, 2010, “ElementaryNumerical Analysis”, John Wiley and Sons. 4

Lecture 1Introduction to Numerical Methods What are NUMERICAL METHODS?Why do we need them?5

Numerical MethodsNumerical Methods:Algorithms that are used to obtain numericalsolutions of a mathematical problem.Why do we need them?1. No analytical solution exists,2. An analytical solution is difficult to obtainor not practical.6

What do we need?Basic Needs in the Numerical Methods: Practical:Can be computed in a reasonable amount of time. Accurate: Good approximate to the true value,Information about the approximation error(Bounds, error order, ).7

Outlines of the Course Solution of nonlinearEquationsSolution of largesystems of lDifferentiationNumerical Integration Least Squares curvefittingSolution of ordinarydifferential equationsSolution of Partialdifferential equations8

Solution of Nonlinear Equations Some simple equations can be solved analytically:x2 4x 3 0Analy ticsolution roots 4 4 2 4(1)(3)2(1)x 1 and x 3 Many other equations have no analytical solution:x 9 2 x 2 5 0 No analy tic solution x x e 9

Integration Some functions can be integratedanalytically:331 29 1 1 xdx 2 x 1 2 2 4But many functions have no analytical solutions :a e x2dx ?010

Solution of Systems of Linear Equationsx1 x2 3x1 2 x2 5We can solve it as :x1 3 x2 ,3 x2 2 x2 5 x2 2, x1 3 2 1What to do if we have1000 equations in 1000 unknowns.11

Solution of Partial Differential EquationsPartial Differential Equations are moredifficult to solve than ordinary differentialequations: u2 u2 2 0 x tu (0, t ) u (1, t ) 0, u ( x,0) sin( x)2212

Solution of Ordinary DifferentialEquationsA solution to the differential equation : x (t ) 3x (t ) 3 x(t ) 0x (0) 1; x(0) 0is a function x(t) that satisfies the equations.* Analytical solutions are available forspecial cases only.13

Theorem 1 14

Theorem 2 15

Example 1 16

Number of Roots 17

Budan’s Theorem 18

ExampleNo. ofRoot2 01- 1one0-- 1zero-1 -- 2one-2- - 3one19

Summary Numerical Methods:Algorithms that areused to obtainnumerical solution of amathematical problem.We need them whenNo analytical solutionexists or it is difficultto obtain it.Topics Covered in the Course Solution of Nonlinear EquationsSolution of Linear EquationsCurve Fitting Least SquaresInterpolationNumerical IntegrationNumerical DifferentiationSolution of Ordinary DifferentialEquationsSolution of Partial DifferentialEquations20

Methods for SolvingNonlinear EquationsoooooBisection MethodNewton-Raphson MethodSecant MethodFixed Point MethodFalse Position Method21

Lecture 2Bisection Method(Halving the interval) What is Bisection Method ? Bisection StepsExamplesAlgorithm Some Properties of Bisection MethodHomework22

1. Bisection Method(Halving the interval) 23

Roots of Some Selected Functions(a) No Roots(b) One Root

Two RootsThree Roots

Bisection StepsThe bisection method is simple, robust, andstraight-forward: Take an interval [a, b] such that f(a) and f(b)have opposite signs, Find the midpoint of [a, b], and then Decide whether the root lies on [a, (a b)/2] or[(a b)/2, b]. Repeat until the interval issufficiently small. 26

Bisection Method c (a b)/2f(a) 0f(c) 0acbf(b) 0

Bisection Method Guaranteed to converge to a root if oneexists within the bracket.a cf(a) 0cabf(c) 0f(b) 028

Bisection Method Slowly converges to a rootb cf(b) 0acb29

The Bisection Method The Bisection Method is a successive approximationmethod that narrows down an interval that contains aroot of the function f(x)The Bisection Method is given an initial interval [a.b]that contains a root (We can use the property sign off(a) sign of f(b) to find such an initial interval)The Bisection Method will cut the interval into 2halves and check which half interval contains a rootof the functionThe Bisection Method will keep cut the interval inhalves until the resulting interval is extremely smallThe root is then approximately equal to any value inthe final (very small) interval.

Algorithm 31

Example 1 32

Example 1(continued) 33

no1121.5-43-1.875 -0.94335 41.6251.751.6875-0.943350.17187-0.4942 51.68751.751.71875-0.49420.17187-0.12478 51.34371.726560.0000534

Example 2 35

No1010.5-20.7183-1.17564 20.510.75-1.175640.7183-0.141225 0.412250.09902-0.1690 50.81251.8750.84375-0.16900.09902-0.03820 Since f(0.84375) 0.05 The approximate root 0.84375 36

Example 3 37

Some Properties of Bisection Method 38

Some Properties ofBisection Method AdvantagesAlways convergent The root bracket gets halved with eachiteration - guaranteed. 39http://numericalmethod

Drawbacks Slow convergenceIf one of the initial guesses is closeto the root, the convergence isslower40

Drawbacks (continued)If a function f(x) is such that it just touchesthe x-axis it will be unable to find the lowerand upper guesses. This mean that:(can not apply on multiple-root) f(x)f x xx412

Drawbacks (continued)Function changes sign but root does notexist. This mean that:(can not apply on complex-root)f(x)1f x xx42

Homework 43

Lecture 3Newton-Raphson Method What is Newton-Raphson Method? Newton-Raphson Method StepsExamplesAlgorithm Some Properties of Newton-RaphsonHomework44

What is Newton-RaphsonMethod? 45

(continued) 46

Geometric 47

Newton-Raphson Methodf(x) x f x f(xi)i,if(xi )xi 1 xi f (xi )f(xi-1) xi 2xi 1xiXFigure 1 Geometrical illustration of the Newton-Raphson method.48

Derivationf(x)f(xi)tan( BABACf ( xi )f ' ( xi ) xi xi 1C Axi 1xiXf ( xi )xi 1 xi f ( xi )Figure 2 Derivation of the Newton-Raphson method.49

Algorithm for Newton-RaphsonMethod 50

Example 1 51

.73771.7320.005752

Example 2 53

TableNo.132.15310.846922.15311.95400.199131.954054

Example 3 55

Example 3 56

TableNo.166.583330.5833326.583336.55790.0254357

Home work 58

Properties of N-R methodAdvantages 59

Prove 60

Prove (continued) 61

Disadvantages (Drawbacks) 62

Drawbacks1.Divergence at inflection pointsSelection of the initial guess or an iteration value of the root that isclose to the inflection point of the function f x may start divergingaway from the root in their Newton-Raphson method.For example, to find the root of the equation f x x 1 0.512 0 .3The Newton-Raphson method reduces to xi 1 xi x3i 3 1 0.512.23 xi 1 Table 1 shows the iterated values of the root of the equation.The root starts to diverge at Iteration 6 because the previous estimate ofx . 10.92589 is close to the inflection point ofEventually after 12 more iterations the root converges to the exact valuex 0.2.of63

Drawbacks – Inflection PointsTable 1 Divergence near inflection 441.600050.925896 30.1197 19.746180.200064Figure 8 Divergence at inflection point forf x x 1 0.512 03

Drawbacks – Division by Zero2. Division by zeroFor the equationf x x3 0.03x 2 2.4 10 6 0the Newton-Raphson methodreduces toxi3 0.03xi2 2.4 10 6xi 1 xi 3xi2 0.06 xiFor x0 0 or x0 0.02 , thedenominator will equal zero.65Figure 9 Pitfall of division by zeroor near a zero number

Drawbacks – Oscillations near localmaximum and minimum3. Oscillations near local maximum and minimumResults obtained from the Newton-Raphson method mayoscillate about the local maximum or minimum withoutconverging on a root but converging on the local maximum orminimum.Eventually, it may lead to division by a number close to zeroand may diverge.2For example for f x x 2 0 the equation has no realroots.66

Drawbacks – Oscillations near localmaximum and minimumTable 3 Oscillations near local maximaand mimima in Newton-Raphson 76786765f xi a e 10 Oscillations around local2minima for f x x 2 .3.142

Drawbacks – Root Jumping4. Root JumpingIn some cases where the function f x is oscillating and has a numberof roots, one may choose an initial guess close to a root. However, theguesses may jump and converge to some other root. f(x)For example1f x sin x 00.5ChooseIt will converge to68x0x0 2.4 7.539822instead of1.5-20-0.06307x 0x 2 6.283185320.5499464.46187.53982210-0.5-1-1.5Figure 11 Root jumping from intendedlocation of root forf x sin. x 0

Lecture 4Secant Method What is Secant Method?Secant Method Steps Algorithm Examples Some Properties of Secant MethodHomework69

Secant Method – Derivationf(x)(1)The secant method can be derived from Newton’s Method x f x f(xi)i,xi 1 xi -if(xi )f (xi )(1)Approximate the derivativef ( xi ) f(xi-1) xi 2xi 1xiXFigure 1 Geometrical illustration ofthe Newton-Raphson method.70f ( xi ) f ( xi 1 )xi xi 1(2)Substituting Equation (2)into Equation (1) gives theSecant methodxi 1f ( xi )( xi xi 1 ) xi f ( xi ) f ( xi 1 )

Secant Method – Derivation(2)The secant method can also be derived from geometry:f(x)The Geometric Similar Triangles ABE and DCEAB DC AE DEBf(xi)can be written asf ( xi )f ( xi 1 ) xi xi 1 xi 1 xi 1Cf(xi-1)xi 1E Dxi-1AxiXFigure 2 Geometrical representation ofthe Secant method.71On rearranging, the secantmethod is given asxi 1f ( xi )( xi xi 1 ) xi f ( xi ) f ( xi 1 )

What is Secant Method? 72

Algorithm 73

Example 1 74

000551.735131.731991.7320-0.0292-0.0005 75

Example 2 76

Table -541.76151.76320.0017-0.0027-3.5784e-5 .77

Properties of Secant Method 78

AdvantagesConverges fast, if it converges Requires two guesses that do not needto bracket the root

Disadvantages 80

Drawbacks221f ( x)f ( x)00f ( x)1 22105 100f(x)prev. guessnew guessDivision by zero815x x gu ess1 x gu ess21010f x Sin x 0

Drawbacks (continued)221f ( x)f ( x)0f ( x)0secant( x)f ( x)1 22105 10510x x 0 x 1' x x 1f(x)x'1, (first guess)x0, (previous guess)Secant linex1, (new guess)Root Jumping82010f x Sinx 0

Homework 83

Lecture 5False position MethodWhat is False position Method? False position Method Steps Algorithm Examples Some Properties of False position Method Homework84

What is False position Method? 85

Geometrical representation ofthe False Position methodThe false Position method can be derived from geometry:f(x)The Geometric Similar Triangles ABE and DCEAB DC AE DEBf(xi)can be written asf ( xi )f ( xi 1 ) xi xi 1 xi 1 xi 1Cf(xi-1)xi 1E Dxi-1AxiXFigure 3 Geometrical representation ofthe false position method.86On rearranging, the false positionmethod is given asxi 1f ( xi )( xi xi 1 ) xi f ( xi ) f ( xi 1 )

What is False position Method? 87

Algorithm 88

Example 1 89

TableNo.11221.57142 -4.03-1.364491.57142 21.70540 -1.36443-0.2478431.70540 21.72788 -0.24783-0.0393641.72788 21.73140 -0.039363-0.0061551.73140 21.73193-0.0010-0.0061590

Example 2 -0.016431.727321.7317-0.0016410.0012091

Properties of False position Method Advantages: 1. Simple2. Brackets the RootDisadvantages: 1. Can be VERY slow2. Like Bisection, need an initial interval around theroot.92

Homework 93

Lecture 6Fixed Point MethodWhat is Fixed Point Method? Fixed Point Method Steps Algorithm Examples Some Properties of Fixed Point Method Homework94

What is Fixed Point Method? 95

Example 1 96

Example 1 97

Example 1 98

Algorithm 99

Condition for Convergence 100

Example 4 101

Example 2 4191.070318252.4297181161.3795102

Example 3 5

Example 5 104

Table Convergence at x 3.000105

Example 6 -0.9990-1.00030.001311-1.0003-0.99990.0004106

Homework 107

No analytical solution exists or it is difficult to obtain it. Solution of Nonlinear Equations Solution of Linear Equations Curve Fitting Least Squares Interpolation Numerical Integration Numerical Differentiation Solution of Ordinary Differential Equations Solution of Partial Differential Equations