Numerical Techniques (Math 2) PDF - S.Y.B.Sc. (Computer Science) - 2020

 A Text Book for S.Y.B.Sc. (Computer Science) Semester - III MATHEMATICS PAPER - II : MTC-232 (Credit 2) Choice Based Credit System (CBCS) (2020 Pattern) NUMERICAL TECHNIQUES Dr. Kalyanrao Takale...

 A Text Book for S.Y.B.Sc. (Computer Science) Semester - III MATHEMATICS PAPER - II : MTC-232 (Credit 2) Choice Based Credit System (CBCS) (2020 Pattern) NUMERICAL TECHNIQUES Dr. Kalyanrao Takale Dr. Shrikisan Gaikwad M.Sc., B.Ed., Ph.D. M.Sc., B.Ed., M.Phil., Ph.D. RNC Arts, JDB Commerce and NSC Science College New Arts, Commerce and Science College Nashik Road, Nashik Ahmednagar Dr. Mrs. Nivedita Mahajan Dr. Amjad Shaikh M.Sc., M.Phil., Ph.D. M.Sc., Ph.D. Modern College of Arts, Science and Commerce AKI's, Poona College of Arts, Science and Commerce Shivajinagar, Pune Pune Prof. Mrs. Shamal Deshmukh Dr. Veena P. Kshirsagar M.Sc., M.Phil. M.Sc., M.Phil., Ph.D. Modern College of Arts, Science and Commerce MIT World Peace University Ganeshkhind, Pune Kothrud, Pune Prof. S. R. Patil M.Sc. Ex. HOD., S.M. Joshi College Hadapsar, Pune Price ` 115.00 N5409 NUMERICAL TECHNIQUES ISBN 978-93-89944-96-9 First Edition : July 2020 [Cover Design by : Himanee Mahajan : Lines_n_Lores] © : Authors The text of this publication, or any part thereof, should not be reproduced or transmitted in any form or stored in any computer storage system or device for distribution including photocopy, recording, taping or information retrieval system or reproduced on any disc, tape, perforated media or other information storage device etc., without the written permission of Authors with whom the rights are reserved. Breach of this condition is liable for legal action. Every effort has been made to avoid errors or omissions in this publication. In spite of this, errors may have crept in. Any mistake, error or discrepancy so noted and shall be brought to our notice shall be taken care of in the next edition. It is notified that neither the publisher nor the authors or seller shall be responsible for any damage or loss of action to any one, of any kind, in any manner, therefrom. Published By : Polyplate Printed By : NIRALI PRAKASHAN YOGIRAJ PRINTERS AND BINDERS Abhyudaya Pragati, 1312, Shivaji Nagar Survey No. 10/1A, Ghule Industrial Estate Off J.M. Road, PUNE – 411005 Nanded Gaon Road Tel - (020) 25512336/37/39, Fax - (020) 25511379 Nanded, Pune - 411041 Email : [email protected] Mobile No. 9404233041/9850046517 DISTRIBUTION CENTRES PUNE Nirali Prakashan : 119, Budhwar Peth, Jogeshwari Mandir Lane, Pune 411002, Maharashtra (For orders within Pune) Tel : (020) 2445 2044, Mobile : 9657703145 Email : [email protected] Nirali Prakashan : S. No. 28/27, Dhayari, Near Asian College Pune 411041 (For orders outside Pune) Tel : (020) 24690204, Mobile : 9657703143 Email : [email protected] MUMBAI Nirali Prakashan : 385, S.V.P. Road, Rasdhara Co-op. Hsg. Society Ltd., Girgaum, Mumbai 400004, Maharashtra; Mobile : 9320129587 Tel : (022) 2385 6339 / 2386 9976, Fax : (022) 2386 9976 Email : [email protected] DISTRIBUTION BRANCHES JALGAON Nirali Prakashan : 34, V. V. Golani Market, Navi Peth, Jalgaon 425001, Maharashtra, Tel : (0257) 222 0395, Mob : 94234 91860; Email : [email protected] KOLHAPUR Nirali Prakashan : New Mahadvar Road, Kedar Plaza, 1st Floor Opp. IDBI Bank, Kolhapur 416 012 Maharashtra. Mob : 9850046155; Email : [email protected] NAGPUR Nirali Prakashan : Above Maratha Mandir, Shop No. 3, First Floor, Rani Jhanshi Square, Sitabuldi, Nagpur 440012, Maharashtra Tel : (0712) 254 7129; Email : [email protected] DELHI Nirali Prakashan : 4593/15, Basement, Agarwal Lane, Ansari Road, Daryaganj Near Times of India Building, New Delhi 110002 Mob : 08505972553 Email : [email protected] BENGALURU Nirali Prakashan : Maitri Ground Floor, Jaya Apartments, No. 99, 6th Cross, 6th Main, Malleswaram, Bengaluru 560003, Karnataka; Mob : 9449043034 Email: [email protected] Other Branches : Gujarat, Hyderabad, Chennai, Kolkata Note : Every possible effort has been made to avoid errors or omissions in this book. In spite this, errors may have crept in. Any type of error or mistake so noted, and shall be brought to our notice, shall be taken care of in the next edition. It is notified that neither the publisher, nor the author or book seller shall be responsible for any damage or loss of action to any one of any kind, in any manner, therefrom. The reader must cross check all the facts and contents with original Government notification or publications. [email protected] | www.pragationline.com Also find us on www.facebook.com/niralibooks A Text Book for S.Y.B.Sc.(Computer Science) Mathematics (2020 Pattern) Choice Based Credit System (CBCS) PAPER-II: MTC-232 (Credit- 2) NUMERICAL TECHNIQUES Authors Dr. Kalyanrao Takale Dr. Shrikisan Gaikwad M.Sc., B.Ed., Ph.D. M.Sc., B.Ed., M.Phil., Ph.D. RNC Arts, JDB Commerce New Arts, Commerce and and NSC Science College, Science College, Ahmednagar. Nashik-Road, Nashik. Dr. Mrs. Nivedita Mahajan Dr. Amjad Shaikh M.Sc., M.Phil., Ph.D. M.Sc., Ph.D. Modern College of Arts, Science AKI’s, Poona College of Arts, and Commerce, Shivajinagar, Pune Science and Commerce, Pune. Prof. Mrs. Shamal Deshmukh Dr. Veena Kshirsagar M.Sc., M.Phil. M.Sc., M.Phil., Ph.D. Modern College of Arts, Science MIT World Peace University, and Commerce, Ganeshkhind, Pune. Kothrud, Pune. Prof. S. R. Patil M.Sc. Ex. HOD.,S. M. Joshi College, Hadapsar, Pune  Preface This book is based on a course PAPER-II: MTC-232: Numerical Techniques. The purpose of this text book is to provide a rigorous treatment of the foundations of Numerical Techniques and its Applications. We write this book as per the revised syllabus of S.Y. B.Sc.(Computer Science) Math- ematics, revised by Savitribai Phule Pune University, Pune, implemented from June 2020. This book is to be accessible to students, we have provided numerous examples and figures for illustrative purposes. Numerical analysis is the most useful subject in applied mathematics and engineering. In Chapter 1, we develop the theory of errors and their computations, furthermore, we develop the it- erative formulae for obtaining the solution of algebraic and transcendental equations such as method of False position and Newton-Raphson iteration method and solved some examples related to these iteration methods. The Chapter 2, is devoted for interpolation first we study finite difference operators and their rela- tions. Then we study differences of a polynomial and we prove Newtons Interpolation Formulae for forward and backward differences and solve some examples. Furthermore, we prove the Lagrange’s Interpolation Formula and Newton’s divided difference formula and as an application of these for- mulae we have solve some examples. Third Chapter deals with the concept of numerical integration and first we prove the general quadra- ture formula for numerical integration. Then we prove the formulae from general quadrature formula to obtain numerical integration such as Trapezoidal rule, Simpsonss 1/3rd rule and Simpsonss 3/8th rule and solve some examples. Fourth Chapter is devoted for numerical solution of first order Ordinary Differential Equations. Also, we discuss some numerical methods such as Eulers method, Modified Eulers methods and Runge - Kutta Methods to obtain the numerical solutions of first order ordinary differential equations and solve some initial value problems. We are very much thankful to Mr. Dinesh Furia and Mr. Jignesh Furia, Nirali Prakashan, Pune, for valuable cooperation and guidance. Also, we are specially thankful to Mrs. Nanda Takale for her valuable cooperation and Miss. Himanee Hemant Mahajan for designing cover page of text book. All authors devote this book to their parents. We welcome any opinions and suggestions which will improve the future editions and help readers in future. In case of queries/suggestions, send an email to: [email protected] -Authors  i Syllabus: PAPER-II: MTC-232: Numerical Techniques 1. Unit1: Algebraic and Transcendental Equation 1.1 Introduction to Errors 1.2 False Position Method 1.3 Newton- Raphson method 2. Unit 2: Calculus of Finite Differences and Interpolation 2.1 Differences 2.2 Forward Differences 2.3 Backward Differences 2.4 Central Differences 2.5 Other Differences (δ, µ operators) 2.6 Properties of Operators 2.7 Relation between Operators 2.8 Newton’s Gregory Formula for Forward Interpolation 2.9 Newton’s Gregory Formula for Backward Interpolation 2.10 Lagrange’s Interpolation Formula 2.11 Divided Difference 2.12 Newton’s Divided Difference Formula 3. Unit 3: Numerical Integration 3.1 General Quadrature Formula 3.2 Trapezoidal rule. 1 3.3 Simpsons’s rd rule. 3 3 3.4 Simpsons’s th rule. 8 4. Unit 4: Numerical Solution of Ordinary Differential Equations 4.1 Eulers method. 4.2 Modified Eulers methods. 4.3 Runge - Kutta Methods. Contents 1 Algebraic and Transcendental Equation 1 1.1 Introduction to Errors................................... 1 1.1.1 Errors and their Computations.......................... 2 1.2 False Position Method................................... 8 1.3 Newton-Raphson Method................................. 17 2 Calculus of Finite Differences and Interpolation 28 2.1 Finite Differences...................................... 28 2.1.1 Forward Differences................................. 29 2.1.2 Other Difference Operator............................. 34 2.1.3 Properties of Operators............................... 35 2.1.4 Relation between Different Operators....................... 36 2.2 Newton’s Formulae for Interpolation........................... 46 2.2.1 Newton’s Forward Difference Interpolation Formula............... 46 2.2.2 Newton’s Backward Difference Interpolation Formula.............. 51 2.2.3 Lagrange’s Interpolation Formula......................... 60 2.3 Divided Difference..................................... 63 2.4 Newton’s Divided Difference Formula........................... 65 3 Numerical Integration 71 3.1 The General Quadrature Formula............................. 71 3.2 Trapezoidal Rule...................................... 72 1 rd 3.3 Simpson’s Rule..................................... 73 3 3 th 3.4 Simpson’s Rule..................................... 74 8 4 Numerical Solution of Ordinary Differential Equations 83 4.1 Euler’s Method....................................... 83 4.1.1 Modified Euler’s Method.............................. 85 4.2 Runge - Kutta Methods.................................. 96 Chapter 1 Algebraic and Transcendental Equation 1.1 Introduction to Errors Many problems in science and engineering, occurs frequently to find the root of the equation f (x) = 0. If f (x) is quadratic, cubic or biquadratic then direct formulae are available to find the roots of the equation. If f (x) is a polynomial od higher degree or an expression involving transcendental functions such as tan x, log x etc. algebraic methods are not available to find the roots, in such cases we use the numerical methods to obtain the approximate roots. A numerical method is a mathematical procedure that generates a sequence of approximate solutions for many problems. A certain way of implementation of an iteration method, including the termination criteria, is called an algorithm of the iteration method. In some cases a numerical method to solve equations may be a longer process. Therefore, for finding the solution of the equation by iteration method an initial guess is important. The iteration method involve repetition of the same process many times, because of that the numerical method is called iterative method. In this chapter, we study the following iteration methods for finding solution of equations (i) Method of false position (Regula-falsi Method), (ii) Newton-Raphson method. We discuss the numerical methods of finding real roots of algebraic or transcendental equations by above methods. If the method leads to value close to the exact solution, then we say that the method is convergent, otherwise, the method is said to be divergent. If f (x) = a0 xn + a1 xn−1 + a2 xn−2 + · · · + an−1 xan (1.1) in x of degree n then following results will be useful for locating the roots. (i) every polynomial equation of nth degree has n roots. (ii) If n is odd, the polynomial equation has at least one real root whose sign is opposite to that of the last term. CHAPTER 1. ALGEBRAIC AND TRANSCENDENTAL EQUATION 2 (iii) If n is even and the constant term is negative then the polynomial equation has at least one positive root and at least one negative root. Theorem 1.1. Descartes rule for sign: (a) A polynomial equation f (x) = 0 can not have more number of positive real roots than the number of changes of sign in coefficients of f (x). (b) A polynomial equation f (x) = 0 can not have more number of negative roots than the number of changes of sign in coefficients of f (−x). Theorem 1.2. If a function f (x) continuous on aleqx ≤ b and if f (a) and f (b) are of opposite signs then for the equation f (x) = 0 there is at least one real root lies between a and b. 1.1.1 Errors and their Computations There are two types of numbers (i) exact numbers and (ii) approximate numbers. √ For example: (i) The exact numbers are 1, 2, 3, · · · , 12 , 32 , · · · 3, π etc. (ii) Approximate numbers are those that represents the numbers to a certain degree of accuracy. e.g. The approximate value of π is 3.1416 if we write a better approximation, it is 3.141592654, 3.14159265358979, 3.141592653589793238462643, · · · , so, we can not write the exact value of π. Definition 1.1. The digits that are used to express a number are called Significant digits or Significant figures. Example 1.1. (i) The numbers 3.141592654, 0.141592654 and 5.023456789 contains ten significant figures each. (ii) The number 0.00025 has only two significant digits viz. 2 and 5 because zeros serve only to fix the position of the decimal point. Definition 1.2. If in numerical computations, numbers which have large number of digits and it will be necessary to cut them to useful number of figures then this process is called rounding-off. We can round the numbers according to the following rules. To round-off a number to n significant digits, describe all digits to the right of the nth digit and if this discarded number is (i) less than half a unit in the nth place, leave the nth digit unaltered. (ii) greater than half a unit in the nth place, increase the nth digit by unity. CHAPTER 1. ALGEBRAIC AND TRANSCENDENTAL EQUATION 3 (iii) exactly half a unit in the nth place, increase the nth digit by unity of its odd, otherwise leave it unchanged. The number thus round-off is said to be correct to n significant figures. Example 1.2. The numbers given below are round-off to five significant figures Number Round-off to significant figures 3.141592654 3.1416 0.141592654 0.14159 30.0567 30.057 1.65835 1.6584 Definition 1.3. Error If X is a quantity we want to compute and X 0 is an approximation to that quantity, then the error is the difference between the true value of a quantity and its approximate value. Error = E = X − X 0 Definition 1.4. Absolute Error Absolute error is the numerical difference between the true value of a quantity and its approximate value. Thus if X 0 is the approximate value of quantity X then |X − X 0 | is called the absolute error and denoted by Ea.Therefore Ea = |X − X 0 | = δX (1.2) The unit of exact or unit of approximate values expresses the absolute error. Definition 1.5. Relative Error The relative error Er defined by |X − X 0 | Ea Er = =. (1.3) |X| True Value Where X 0 is the approximate value of quantity X. The relative error is independent of units. Definition 1.6. Percentage Error The percentage error in X 0 which is the approximate value of X is given by |X − X 0 | Ep = 100 × Er = 100 ×. (1.4) |X| The percentage error is also independent of units. Remark 1.1. Let ∆X be a number such that |X1 − X| ≤ ∆X. Then ∆X is an upper limit on the magnitude of the absolute error and is said to measure absolute accuracy. Similarly, the quantity ∆X ∆X ≈ |X| |X1 | measures the the relative accuracy. CHAPTER 1. ALGEBRAIC AND TRANSCENDENTAL EQUATION 4 Example 1.3. If X = 0.25 and X1 = 0.251 is correct to two decimal places then find the absolute error and absolute accuracy ∆X. Solution: Here X = 0.25 and X1 = 0.251 Therefore, the absolute error is EA = |X1 − X| = |0.251 − 0.25| = 0.001 If the number X is rounded to N decimal places then 1 ∆X = × 10−N 2 Suppose X = 0.25 and correct to two decimal places then absolute accuracy ∆X is 1 0.5 ∆X = × 10−2 = = 0.005 2 100 Example 1.4. If X = 0.51 and is correct to two decimal places then find the absolute error (absolute accuracy) ∆X and percentage accuracy. Solution: Suppose X = 0.51 and correct to two decimal places. If the number X is rounded to N decimal places then 1 ∆X = × 10−N 2 Therefore, the absolute accuracy is 1 0.5 ∆X = × 10−2 = = 0.005 2 100 4X 0.005 and the percentage accuracy is × 100 = × 100 = 0.98 % |X| |0.51| Example 1.5. If X = 0.1416 and is correct to four decimal places then find the absolute accuracy ∆X and percentage accuracy. Solution: Suppose X = 0.1416 and correct to four decimal places. If the number X is rounded to N decimal places then 1 ∆X = × 10−N 2 Therefore, the absolute accuracy is 1 ∆X = × 10−4 = 0.00005 2 ∆X 0.00005 and the percentage accuracy is × 100 = × 100 = 0.035 % |X| |0.1416| Example 1.6. If X = 3.1416 and X1 = 3.14159 is correct to five decimal places then find the absolute error ER and absolute accuracy ∆X. CHAPTER 1. ALGEBRAIC AND TRANSCENDENTAL EQUATION 5 Solution: Here X = 3.1416 and X1 = 3.14159 Therefore, the absolute error is EA = |X − X1 | = |3.14159 − 3.1416| = 0.00001 If the number X is rounded to N decimal places then 1 ∆X = × 10−N 2 Suppose X = 3.1416 and correct to five decimal places then absolute accuracy ∆X is 1 0.5 ∆X = × 10−5 = = 0.000005 2 10000 Example 1.7. Find the absolute, percentage and relative errors if x is rounded-off to three decimal digits. Given x = 0.005998. Solution: If x is rounded-off to three decimal places we get x = 0.006. Therefore Error = True value − Approximate value. Error = 0.005998 − 0.006 = −0.000002 Absolute Error = Ea = Error = 0.000002 Ea Ea 0.000002 Relative Error = Er = = = = 0.0033344 True Value 0.005998 0.005998 Percentage Error = Ep = 100 × Er = 0.33344. Example 1.8. Solution: Here X = 3.1416 and X1 = 3.14159 The error is E = X − X1 = 3.1416 − 3.14159 = 0.00001 Example 1.9. Find relative error and percentage error of the number 8.6 if both of digits are correct. Solution: Here X = 8.6 is correct to two decimal places. Therefore, the absolute error is 1 EA = × 10−2 = 0.05 2 The relative error is EA 0.005 ER = = = 0.0058 |X| |8.6| The percentage error is EP = ER × 100 = 0.0058 × 100 = 0.58 %. √ √ √ Example 1.10. Evaluate the sum S = 3 + 5 + 7 to four significant digits and find its absolute error and relative error. CHAPTER 1. ALGEBRAIC AND TRANSCENDENTAL EQUATION 6 √ √ √ Solution: Here S = 3 + 5 + 7 √ √ √ Therefore, 3 = 1.732, 5 = 2.236, 7 = 2.646 Hence, S = 6.614 then the absolute error is EA = 0.0005 + 0.0005 + 0.0005 = 0.0015 The total absolute error shows that the sum is correct to three significant figures only. Hence we take S = 6.61 The relative error is EA 0.0015 ER = = = 0.0002 |X| |6.61| The percentage error is EP = ER × 100 = 0.0002 × 100 = 0.02 %. Example 1.11. Two numbers are given as 2.5 and 48.289 both of which being correct to the significant figures given then find their product. Solution: Here number 2.5 is the one with the greatest absolute error is 0.05. Therefore, we round-off the second number 48.289 to three significant digits i.e. 48.3 The required product is given by P = 48.3 × 2.5 = 1.2 × 102 In the product, we retained only two significant digits, since one of the given numbers viz. 2.5 contained only two significant digits. r l Example 1.12. Compute the percentage error in the time period T = 2π for l = 2m if the error g in the measurement of l is 0.01. r l Solution: Given T = 2π g On taking log both the sides, we get 1 1 log(T ) = log2π + log(l) − log(g) 2 2 1 1 δl ∴ δT = T 2 l δT δl 0.01 ∴ × 100 = × 100 = × 100 = 0.5%. T 2l 2×1 Exercise:1.1 1. Explain the term round-off error and round-off the following numbers to two decimal places. 48.21416, 2.3742, 52.275, 2.375, 81.255. CHAPTER 1. ALGEBRAIC AND TRANSCENDENTAL EQUATION 7 2. Round-off the following numbers to four significant figures. 38.46235, 0.70029, 0.0022218, 19.235101, 2.36425. √ √ 3. Calculate the value of 102 − 101 correct to four significant figures. 4. If P = 3c6 − 6c2 , find the percentage error in P at c = 1 if the error in c is 0.05. 5. Find the absolute error in the sum of the following numbers. 105.6, 27.28, 5.63, 0.1467, 0.000523, 208.5, 0.0235, 0.432 and 0.0467 where each number is correct to the digits given. 4.536 6. Find the relative error in the quotient the numbers being correct to the digits given. 1.32 √ √ 7. Find the relative error in taking the difference of numbers 5.5 = 2.345 and 6.1 = 2.470. Numbers should be correct to four significant figures. 8. Let X = 3.1416 be the actual value of the number and X1 = 3.14159 be the approximated value of the number π, find error, absolute error, relative error and percentage error. Solutions 1. 48.21, 2.37, 52.28, 2.38, 81.26. 2. 38.46, 0.7003, 0.002222, 19.24, 2.364. 3. 0.04963 4. 10% 5. 347.7 ± 0.15 6. 0.004 7. 0.008 8. The Absolute error is Ea = |X − X 0 | = |3.14159 − 3.1416| = 0.00001. The relative error is |X − X 0 | |3.14159 − 3.1416| Er = = = 0.0000031831. |X| |3.1416| The percentage error is |X − X 0 | Ep = × 100 = 100Er = 0.00031831 %. |X| CHAPTER 1. ALGEBRAIC AND TRANSCENDENTAL EQUATION 8 In the next section, we discuss the numerical iterative methods to obtain the roots of the algebraic and transcendental equations. 1.2 False Position Method The method of False Position is also called linear interpolation method or regula-falsi method or method of chord. By this method we will obtain the approximate value of the root of the equation f (x) = 0. Therefore, we need to obtain the interval in which lies. Suppose the root of the equa- tion f (x) = 0 lies in the interval (xi−1 , xi ), therefore, f (xi−1 )f (xi ) < 0. Let P (xi−1 , f (xi−1 )) and Q(xi , f (xi )) be points on the curve f (x) = 0. Now, draw a straight line joining the points P and Q as shown in figure. y P x3 x2 x1 x x0 y = f (x) Q Figure 1.1 The line P Q is taken as an approximation of the curve in the interval [xi−1 , xi ]. Therefore, equation of the line P Q is given by y − f (xi ) x − xi = (1.5) f (xi ) − f (xi−1 ) xi − xi−1 The point of intersection of this line P Q with the x−axis is taken as the next approximation to the root. Let us set y = 0, and solving for x, we obtain 0 − f (xi ) x − xi = f (xi ) − f (xi−1 ) x − xi−1 i  xi − xi−1 x − xi = (−f (xi )) f (xi ) − f (xi−1 )   xi − xi−1 x = xi − f (xi ) f (xi ) − f (xi−1 ) The next approximation to the root is   xi − xi−1 xi+1 = xi − f (xi ), for i = 1, 2, · · · (1.6) f (xi ) − f (xi−1 ) CHAPTER 1. ALGEBRAIC AND TRANSCENDENTAL EQUATION 9 After simplification, we can write the approximation to the root formula as follows xi−1 f (xi ) − xi f (xi−1 ) xi+1 = , for i = 1, 2, · · · (1.7) f (xi ) − f (xi−1 ) Procedure for the False Position Method to Find the Root of the Equation f (x) = 0 Step 1: Choose two initial guess values (approximations) x0 and x1 (where x> x0 ) such that f (x0 ).f (x1 ) < 0. Step 2: Find the next approximation x2 using the formula x0 f (x1 ) − x1 f (x0 ) x2 = , for i = 1, 2, · · · (1.8) f (x1 ) − f (x0 ) and also evaluate f (x2 ). Step 3: If f (x2 )f (x1 ) < 0, then go to the next step. If not, rename x0 as x1 and then go to the next step. Step 4: Evaluate successive approximations using the formula xi−1 f (xi ) − xi f (xi−1 ) xi+1 = , where i = 2, 3, 4, · · · (1.9) f (xi ) − f (xi−1 ) But before applying the formula for xi+1 , ensure whether f (xi−1 ).f (xi ) < 0; if not, rename xi−2 as xi−1 and proceed. Step 5: Stop the evaluation when |xi − xi−1 | < ε, where ε is the prescribed accuracy. Example 1.13. Find a real root correct to three decimal places of the equation f (x) = x3 −x2 −2 = 0 using the method of False-Position. Solution: The given equation is f (x) = x3 − x2 − 2 = 0 (1.10) Now, f (x) = x3 − x2 − 2, ⇒ f (0) = −2 < 0 f (1) = −2 < 0 f (2) = 2 > 0. ∴ f (1)f (2) < 0. Therefore, real root lies between 1 and 2. We have x0 = 1 and x1 = 2 ∴ f (x0 ) = f (1) = −2 f (x1 ) = f (2) = 2 CHAPTER 1. ALGEBRAIC AND TRANSCENDENTAL EQUATION 10 Therefore, putting k = 1 in equation (1.7), the first approximation to the root is x0 f (x1 ) − x1 f (x0 ) x2 = f (x1 ) − f (x0 ) 1(2) − 2(−2) = = 1.5 2−1 ∴ f (x2 ) = f (1.5) = 1.53 − 1.52 − 2 = −0.875 < 0. Hence, f (x1 )f (x2 ) = f (1.5)f (2) < 0. Therefore, real root lies between 1.5 and 2. Then the next approximation to the root is x0 f (x2 ) − x2 f (x0 ) x3 = f (x2 ) − f (x0 ) 1.5(2) − 2(−0.875) = 2 − 1.5 = 1.6522. ∴ f (x3 ) = f (1.6522) = 1.65223 − 1.65222 − 2 = −0.2197 < 0. Therefore, real root lies between 1.6522 and 2. Then the next approximation to the root is x0 f (x3 ) − x3 f (x0 ) x4 = f (x3 ) − f (x0 ) 1.6522(2) − 2(−0.2197) = 2 − 1.6522 = 1.6866. ∴ f (x4 ) = f (1.6866) = 1.68663 − 1.68662 − 2 = −0.0469 < 0 Therefore, real root lies between 1.6866 and 2. Then the next approximation to the root is x0 f (x4 ) − x4 f (x0 ) x5 = f (x4 ) − f (x0 ) 1.6866(2) − 2(−0.0469) = 2 − 1.6866 = 1.6938. ∴ f (x5 ) = f (1.6938) = 1.69383 − 1.69382 − 2 = −0.0096 < 0 Therefore, real root lies between 1.6938 and 2. Then the next approximation to the root is x0 f (x5 ) − x5 f (x0 ) x6 = f (x5 ) − f (x0 ) 1.6938(2) − 2(−0.0096) = 2 − 1.6938 = 1.6953 CHAPTER 1. ALGEBRAIC AND TRANSCENDENTAL EQUATION 11 f (x5 ) = f (1.6953) = 1.69533 − 1.69532 − 2 = −0.0016 < 0 Therefore, real root lies between 1.6953 and 2. Then the next approximation to the root is x0 f (x5 ) − x5 f (x0 ) x6 = f (x5 ) − f (x0 ) 1.6953(2) − 2(−0.0016) = = 1.6955. 2 − 1.6953 Thus the root has computed correct to three decimal places. Hence, the required root of the equation correct to three decimal places is x ≈ 1.695. Example 1.14. Find a real root correct to three decimal places of the equation f (x) = x3 −3x+1 = 0 using the method of False-Position. Solution: The given equation is f (x) = x3 − 3x + 1 = 0 (1.11) Now, f (x) = x3 − 3x + 1 f (0) = 1 > 0 and f (1) = −1 < 0 ∴ f (0)f (1) < 0. Therefore, real root lies between 0 and 1. We have x0 = 0 and x1 = 1 ∴ f (x0 ) = f (0) = 1 f (x1 ) = f (1) = 13 − 3(1) + 1 = −1 Therefore, putting k = 1 in equation (1.7), the first approximation to the root is x0 f (x1 ) − x1 f (x0 ) x2 = f (x1 ) − f (x0 ) 0(−1) − 1(1) = = 0.5 −1 − 1 f (x2 ) = f (0.5) = 0.53 − 3(0.5) + 1 = −0.375 ∴ f (x0 )f (x2 ) = f (0)f (0.5) < 0 Therefore, real root lies between 0 and 0.5. Then the next approximation to the root is x0 f (x2 ) − x2 f (x0 ) x3 = f (x2 ) − f (x0 ) 0(−0.375) − 0.5(1) = = 0.3636. −0.375 − 1 CHAPTER 1. ALGEBRAIC AND TRANSCENDENTAL EQUATION 12 f (x3 ) = f (0.3636) = 0.36363 − 3(0.3636) + 1 = −0.0428 ∴ f (x0 )f (x3 ) = f (0)f (0.3636) < 0 Therefore, real root lies between 0 and 0.3636. Then the next approximation to the root is x0 f (x3 ) − x3 f (x0 ) x4 = f (x3 ) − f (x0 ) 0(−0.0428) − 0.3636(1) = −0.0428 − 1 = 0.3487 ∴ f (x4 ) = f (0.3487) = 0.34873 − 3(0.3487) + 1 = −0.0037 Hence, f (x0 )f (x4 ) = f (0)f (0.3487) < 0. Therefore, real root lies between 0 and 0.3487. Then the next approximation to the root is x0 f (x4 ) − x4 f (x0 ) x5 = f (x4 ) − f (x0 ) 0(−0.0037) − 0.3487(1) = −0.0037 − 1 = 0.3474. ∴ f (x5 ) = f (0.3474) = 0.34743 − 3(0.3474) + 1 = −0.0003 Hence, f (x0 )f (x5 ) = f (0)f (0.3474) < 0. Therefore, real root lies between 0 and 0.3474. Then the next approximation to the root is x0 f (x5 ) − x5 f (x0 ) x6 = f (x5 ) − f (x0 ) 0(−0.0003) − 0.3474(1) = −0.0003 − 1 = 0.3473 ∴ |x6 − x5 | = |0.3473 − 0.3474| = 0.0001 < 0.0005 Thus the root has computed correct to three decimal places. Hence, the required root of the equation correct to three decimal places is x ≈ 0.347 Example 1.15. Find a real root of the equation f (x) = x3 − 2x − 5 = 0 by the method of false position up to three places of decimal. Solution: The given equation is f (x) = x3 − 2x − 5 = 0 (1.12) ⇒ f (2) = 23 − 2(2) − 5 = −1 < 0 and f (3) = 33 − 2(3) − 5 = 16 > 0. CHAPTER 1. ALGEBRAIC AND TRANSCENDENTAL EQUATION 13 ∴ f (2)f (3) < 0. Hence, real root lies between 2 and 3. We have x0 = 2 and x1 = 3 ∴ f (x0 ) = f (2) = −1 and f (x1 ) = f (3) = 16. Therefore, putting k = 1 in equation (1.7), the first approximation to the root is x0 f (x1 ) − x1 f (x0 ) x2 = f (x1 ) − f (x0 ) 2(16) − (3)(−1) = 16 − (−1) = 2.0588 ∴ f (x2 ) = f (2.0588) = (2.0588)3 − 2(2.0588) − 5 = −0.3911 < 0. Therefore, real root lies between 2.0588 and 3. Then the next approximation to the root is x0 f (x1 ) − x1 f (x0 ) x3 = f (x1 ) − f (x0 ) 2.0588(16) − (3)(−0.3911) = 16 − (−0.3911) = 2.0813, ∴ f (x3 ) = f (2.0813) = (2.0813)3 − 2(2.0813) − 5 = −0.1468 < 0. Therefore, real root lies between 2.0813 and 3. Then, the next approximation to the root is x0 f (x3 ) − x3 f (x0 ) x4 = f (x3 ) − f (x0 ) 2.0813(16) − (3)(−0.1468) = 16 − (−0.1468) = 2.0897 ∴ f (x4 ) = f (2.0897) = (2.0897)3 − 2(2.0897) − 2.0897 = −0.054 < 0. Therefore, real root lies between 2.0897 and 3. Then the next approximation to the root is x0 f (x4 ) − x4 f (x0 ) x5 = f (x4 ) − f (x0 ) 2.0897(16) − (2.0897)(−0.054) = 16 − (−0.054) = 2.0928. ∴ f (x5 ) = f (2.0928) = (2.0928)3 − 2(2.0928) − 2.0928 = −0.0195 < 0 Therefore, real root lies between 2.0928 and 3. CHAPTER 1. ALGEBRAIC AND TRANSCENDENTAL EQUATION 14 Then the next approximation to the root is x0 f (x5 ) − x5 f (x0 ) x6 = f (x5 ) − f (x0 ) 2.0928(16) − (2.0928)(−0.0195) = 16 − (−0.0195) = 2.0939. ∴ f (x6 ) = f (2.0939) = (2.0939)3 − 2(2.0939) − 5 = −0.0074 < 0. Therefore, real root lies between 2.0939 and 3. Then the next approximation to the root is x0 f (x6 ) − x6 f (x0 ) x7 = f (x6 ) − f (x0 ) 2.0939(16) − (3)(−0.0074) = 16 − (−0.0074) = 2.0943. ∴ f (x6 ) = f (2.0943) = (2.0943)3 − 2(2.0943) − 5 = −0.0028 < 0. Therefore, real root lies between 2.0943 and 3. Then the next approximation to the root is x0 f (x6 ) − x6 f (x0 ) x7 = f (x6 ) − f (x0 ) 2.0943(16) − (3)(−0.0028) = 16 − (−0.0028) = 2.0945. ∴ |x7 − x6 | = |2.0945 − 2.0943| = 0.0003 < 0.0005. Thus the root has computed correct to three decimal places. Hence, the required root of the equation correct to three decimal places is x ≈ 2.0945. Example 1.16. Find a real root of the equation f (x) = x tan x + 1 = 0 in (2, 3) correct to three decimal places using the method of False-Position. Solution: The given equation is f (x) = x tan x + 1 = 0 (1.13) Now, f (x) = x tan x + 1 f (0) = 1 > 0 and f (1) = 2.5514 > 0 f (2) = −3.3700 < 0 and f (3) = 0.5723 > 0 ∴ f (2)f (3) < 0. Therefore, real root lies between 2 and 3. CHAPTER 1. ALGEBRAIC AND TRANSCENDENTAL EQUATION 15 We have x0 = 2 and x1 = 3 ∴ f (x0 ) = f (2) = −3.3700 f (x1 ) = f (3) = 0.5723. Therefore, putting k = 1 in equation (1.7), the first approximation to the root is x0 f (x1 ) − x1 f (x0 ) x2 = f (x1 ) − f (x0 ) 2(0.5723) − 3(−3.3700) = 0.5723 + 3.3700 = 2.8548. ⇒ f (x2 ) = f (2.8548) = 2.8548 tan(2.8548) + 1 = 0.1581 > 0 ∴ f (x0 )f (x2 ) = f (2)f (2.8548) < 0 Therefore, real root lies between 2 and 2.8548. Then, the next approximation to the root is x0 f (x2 ) − x2 f (x0 ) x3 = f (x2 ) − f (x0 ) 2(0.1581) − 2.8548(−3.3700) = 0.1581 + 3.3700 = 2.8165 ⇒ f (x3 ) = f (2.8165) = 2.8165 tan(2.8165) + 1 = 0.0507 > 0 ∴ f (x0 )f (x3 ) = f (2)f (2.8165) < 0 Therefore, real root lies between 2 and 2.8165. Then the next approximation to the root is x0 f (x3 ) − x3 f (x0 ) x4 = f (x3 ) − f (x0 ) 2(0.0507) − 2.8165(−3.3700) = 0.0507 + 3.3700 = 2.8044 ⇒ f (x4 ) = f (2.8044) = 2.8044 tan(2.8044) + 1 = 0.0168 > 0 ∴ f (x0 )f (x4 ) = f (2)f (2.8044) < 0 Therefore, real root lies between 2 and 2.8044. Then the next approximation to the root is x0 f (x4 ) − x4 f (x0 ) x5 = f (x4 ) − f (x0 ) 2(0.0168) − 2.8044(−3.3700) = = 2.8004. 0.0168 + 3.3700 CHAPTER 1. ALGEBRAIC AND TRANSCENDENTAL EQUATION 16 ⇒ f (x5 ) = f (2.8004) = 2.8004 tan(2.8004) + 1 = 0.0056 > 0. ∴ f (x0 )f (x5 ) = f (2)f (2.8004) < 0. Therefore, real root lies between 2 and 2.8004. Then the next approximation to the root is x0 f (x5 ) − x5 f (x0 ) x6 = f (x5 ) − f (x0 ) 2(0.0056) − 2.8004(−3.3700) = 0.0056 + 3.3700 = 2.7990 ⇒ f (x6 ) = f (2.7990) = 2.7990 tan(2.7990) + 1 = 0.0018 > 0 ∴ f (x0 )f (x6 ) = f (2)f (2.7990) < 0 Therefore, real root lies between 2 and 2.7990. Then the next approximation to the root is x0 f (x6 ) − x6 f (x0 ) x7 = f (x6 ) − f (x0 ) 2(0.0018) − 2.7990(−3.3700) = 0.0018 + 3.3700 = 2.7986 ⇒ f (x7 ) = f (2.7986) = 2.7986 tan(2.7986) + 1 = 0.0006 > 0 ∴ f (x0 )f (x7 ) = f (2)f (2.7986) < 0. Therefore, real root lies between 2 and 2.7986. Then the next approximation to the root is x0 f (x7 ) − x7 f (x0 ) x8 = f (x7 ) − f (x0 ) 2(0.0006) − 2.7986(−3.3700) = 0.0006 + 3.3700 = 2.7984. ∴ |x8 − x7 | = |2.7986 + 2.7984| = 0.0003 < 0.0005. Thus the root has computed correct to three decimal places. Hence, the required root of the equation correct to three decimal places is x ≈ 2.7984 In the next section, we discuss the Newton-Raphson Method to obtain the roots of the equation f (x) = 0. This method is used to improve the results obtained by one of the previous methods. CHAPTER 1. ALGEBRAIC AND TRANSCENDENTAL EQUATION 17 1.3 Newton-Raphson Method In this section, we discuss the Newton-Raphson Method to obtain the roots of the equation f (x) = 0. This method is used to improve the results obtained by one of the previous methods. Let x0 be an approximate root of f (x) = 0 and x1 = x0 + h be the correct root of the equation f (x1 ) = 0. Now, we expand f (x0 + h) by Taylors series, we obtain h2 00 f (x0 + h) = f (x0 ) + hf 0 (x0 ) + f (x0 ) + · · · = 0 (1.14) 2! We neglect second and higher order derivatives from equation (1.14), we have f (x0 ) + hf 0 (x0 ) = 0 f (x0 ) ∴h=− 0 f (x0 ) Therefore, the better approximation than x0 is given by x1 , where f (x0 ) x1 = x0 − (1.15) f 0 (x0 ) Now, continue the procedure then the successive approximations are given by f (xn ) xn+1 = xn − , n = 0, 1, 2, · · · (1.16) f 0 (xn ) This is called Newton-Raphson formula. Theorem 1.3. Prove that the Newton-Raphson process has second-order or quadratic convergence. Proof: Suppose xn+1 = φ(xn ), then we obtain f (x) φ(x) = x − f 0 (x) f (x)f 00 (x) φ0 (x) = [f 0 (x)]2 To examine the convergence, we assume that f (x), f 0 (x) and f 00 (x) are continuous and bounded on the interval containing the root x = ξ of the equation f (x) = 0. If ξ is a simple root then f 0 (x) 6= 0. Since f 0 (x) is continuous |f 0 (x)| ≥  for some  > 0 in a suitable neighborhood of ξ. In this neighborhood, we select the interval such that |f (x)f 0 (x)| < 2. This is possible because of f (ξ) = 0 and f (x) is continuously twice differentiable. Therefore, in this interval, we have f (x)f 00 (x) φ0 (x) = < 1. [f 0 (x)]2 Therefore, Newton-Raphson formula given in equation (1.16) converges, provided that the initial approximation x0 is chosen sufficiently close to ξ. Now, ξ is a multiple root, the Newton-Raphson CHAPTER 1. ALGEBRAIC AND TRANSCENDENTAL EQUATION 18 method still converges but slowly. The convergence can be made faster by modifying equation (1.16). Now, to obtain the rate of the convergence Newton-Raphson method, we consider f (ξ) = 0. So, Taylor’s series expansion gives 1 f (xn ) + (ξ − xn )f 0 (xn ) + (ξ − xn )2 f 00 (x0 ) + · · · = 0 (1.17) 2 From this, we obtain 00 f (xn ) 1 2 f (xn ) − = (ξ − x n ) + (ξ − x n ) (1.18) f 0 (xn ) 2 f 0 (xn ) Therefore, from equations (1.16) and (1.18), we have 1 f 00 (xn ) xn+1 − ξ = (ξ − xn )2 0 (1.19) 2 f (xn ) Now, by putting n = xn − ξ, equation (1.19) gives 1 f 00 (xn ) n+1 = 2n 0 (1.20) 2 f (xn ) This proves that the Newton-Raphson process has a second order or quadratic convergence. Remark 1.2. Geometrically, the method consists in replacing the part of the curve between the point [x0 , f (x0 )] and the x− axis by means of the tangent to the curve at that point. It can be used for solving both algebraic and transcendental equations. y y = f (x) P (x0 , y0 ) x x1 x0 Figure 1.2 Procedure for Newton Raphson Method to Find the Root of the Equation f (x) = 0 Step 1: Take a trial solution (initial approximation) as x0 find f (x0 ) and f 0 (x0 ). Step 2: Find next (first) approximation x1 by using the formula f (x0 ) x1 = x0 −. (1.21) f 0 (x0 ) CHAPTER 1. ALGEBRAIC AND TRANSCENDENTAL EQUATION 19 Step 3: Follow the above procedure to find the successive approximations xn+1 using the formula f (xn ) xn+1 = xn − , where n = 1, 2, 3, · · · (1.22) f 0 (xn ) Step 4: Stop the process when |xn+1 − xn | < ε, where ε is the prescribed accuracy. Example 1.17. Find a real root correct to three decimal places of the equation x3 − 8x − 4 = 0 near x = 3.5 using Newton-Raphson method. Solution: The given equation is f (x) = x3 − 8x − 4 == 0 (1.23) Now, f (x) = x3 − 8x − 4, f 0 (x) = 3x2 − 8 Take x0 = 3.5, then we obtain f (x0 ) = f (3.5) = (3.5)3 − 8(3.5) − 4 = 10.875 f 0 (x0 ) = f 0 (3.5) = 3(3.5)2 − 8 = 28.75 The Newton-Raphson iteration formula (1.16), the first approximation to the root is f (x0 ) x1 = x0 − f 0 (x0 ) 10.875 = 3.5 − = 3.1217. 28.75 ⇒ f (x1 ) = f (3.1217) = (3.1217)3 − 8(3.1217) − 4 = 1.4474 f 0 (x1 ) = f 0 (3.1217) = 3(3.1217)2 − 8 = 21.2350. Therefore, the second approximation to the root is f (x1 ) x2 = x1 − f 0 (x1 ) 1.4474 = 3.1217 − = 3.0535 21.2350 ⇒ f (x2 ) = f (3.0535) = (3.0535)3 − 8(3.0535) − 4 = 0.0424 f 0 (x2 ) = f 0 (3.0535) = 3(3.0535)2 − 8 = 19.9716 The third approximation to the root is f (x2 ) x3 = x2 − f 0 (x2 ) 0.0424 = 3.0535 − = 3.0514. 19.9716 f (x3 ) = f (3.0514) = (3.0514)3 − 8(3.0514) − 4 = −0.0002 f 0 (x3 ) = f 0 (3.0514) = 3(3.0514)2 − 8 = 19.9331 CHAPTER 1. ALGEBRAIC AND TRANSCENDENTAL EQUATION 20 The fourth approximation to the root is f (x2 ) x 3 = x2 − f 0 (x2 ) −0.0002 = 3.0514 − 19.9331 = 3.0514 Hence, the required root of the equation is x ≈ 3.0514. Example 1.18. Find a real root correct to three decimal places of the equation xsin 2 − 4 = 0 near x = 4.5 using Newton-Raphson method. Solution: The given equation is f (x) = xsin 2 − 4 = 0 (1.24) Now, f (x) = xsin 2 − 4, f 0 (x) = (sin 2)xsin 2−1 Take x0 = 4.5, then we obtain f (x0 ) = f (4.5) = (4.5)sin 2 − 4 = −0.07387 f 0 (x0 ) = f 0 (4.5) = (sin 2)(4.5)sin 2−1 = 0.7933. The Newton-Raphson iteration formula (1.16), the first approximation to the root is f (x0 ) x1 = x 0 − f 0 (x0 ) −0.07387 = 4.5 − = 4.5931 0.7933 ⇒ f (x1 ) = f (4.5931) = (4.5931)sin 2 − 4 = −0.000068 f 0 (x1 ) = f 0 (4.5931) = (sin 2)(4.5931)sin 2−1 = 0.7918. Therefore, the second approximation to the root is f (x1 ) x2 = x1 − f 0 (x1 ) −0.000068 = 4.5931 − = 4.5932 0.7918 ⇒ f (x2 ) = f (4.5932) = (4.5932)sin 2 − 4 = −0.00000027 f 0 (x2 ) = f 0 (4.5932) = (sin 2)(4.5932)sin 2−1 = 0.7919. The third approximation to the root is f (x2 ) x3 = x2 − f 0 (x2 ) −0.00000027 = 4.5932 − = 4.5932 0.7919 ⇒ f (x3 ) = f (4.5932) = (4.5932)sin 2 − 4 = −0.00000027 f 0 (x3 ) = f 0 (4.5932) = (sin 2)(4.5932)sin 2−1 = 0.7919. CHAPTER 1. ALGEBRAIC AND TRANSCENDENTAL EQUATION 21 The fourth approximation to the root is f (x2 ) x 3 = x2 − f 0 (x2 ) −0.00000027 = 4.5932 − 0.7919 = 4.5932. Hence, the required root of the equation is x ≈ 4.5932. Note: We observe that, this example demonstrate that the Newton-Raphson method converges more rapidly than the methods studied in previous sections. Example 1.19. Find a real root correct to three decimal places of the equation x sin x + cos x = 0 near x = π using Newton-Raphson method. Solution: The given equation is f (x) = x sin x + cos x = 0 (1.25) Now, f (x) = x sin x + cos x, f 0 (x) = x cos x Take x0 = π, then we obtain f (x0 ) = f (π) = π sin π + cos π = −1 f 0 (x0 ) = f 0 (π) = π cos π = −π = −3.1416 The Newton-Raphson iteration formula (1.16), the first approximation to the root is f (x0 ) x1 = x0 − f 0 (x0 ) −1 =π− −3.1416 = 2.8233 f (x1 ) = f (2.8233) = 2.8233 sin 2.8233 + cos 2.8233 == −0.06623 f 0 (x1 ) = f 0 (2.8233) = 2.8233 cos 2.8233 = −2.6815 Therefore, the second approximation to the root is f (x1 ) x2 = x1 − f 0 (x1 ) −0.06623 = 2.8233 − −2.6815 = 2.7986 f (x2 ) = f (2.7986) = 2.7986 sin 2.7986 + cos 2.7986 == −0.00056 f 0 (x2 ) = f 0 (2.7986) = 2.7986 cos 2.7986 = −2.6356 CHAPTER 1. ALGEBRAIC AND TRANSCENDENTAL EQUATION 22 Therefore, the third approximation to the root is f (x2 ) x3 = x2 − f 0 (x2 ) −0.00056 = 2.7986 − −2.6356 = 2.7984 f (x3 ) = f (2.7984) = 2.7984 sin 2.7984 + cos 2.7984 == −0.0 f 0 (x3 ) = f 0 (2.7984) = 2.7984 cos 2.7984 = −2.6350 Therefore, the fourth approximation to the root is f (x3 ) x4 = x3 − f 0 (x3 ) −0.0 = 2.7984 − −2.6350 = 2.7984 Hence, the required root of the equation is x ≈ 2.7984. Example 1.20. Find a real root correct to four decimal places of the equation xex = cos x using Newton-Raphson method. Solution: The given equation is f (x) = xex − cos x = 0 (1.26) Now, f (x) = xex − cos x, f 0 (x) = (x + 1)ex + sin x f (0) = 0 − cos 0 = −1 < 0 f (1) = 1 − cos 1 = 2.1779 > 0 ∴ f (0)f (1) < 0. Therefore, root lies between 0 and 1. 0+1 Take x0 = 2 = 0.5, then we obtain f (x0 ) = f (0.5) = 0.5e0.5 − cos 0.5 = −0.0532 f 0 (x0 ) = f 0 (0.5) = (0.5 + 1)e0.5 + sin 0.5 = 2.9525 The Newton-Raphson iteration formula (1.16), the first approximation to the root is f (x0 ) x1 = x0 − f 0 (x0 ) −0.0532 = 0.5 − 2.9525 = 0.5180 CHAPTER 1. ALGEBRAIC AND TRANSCENDENTAL EQUATION 23 f (x1 ) = f (0.5180) = 0.5180e0.5180 − cos 0.5180 = 0.0008 f 0 (x1 ) = f 0 (0.5180) = (0.5180 + 1)e0.5180 + sin 0.5180 = 2.9525 Therefore, the second approximation to the root is f (x1 ) x2 = x1 − f 0 (x1 ) 0.0008 = 0.5180 − 2.9525 = 0.5178 f (x2 ) = f (0.5178) = 0.5178e0.5178 − cos 0.5178 = 0.0 f 0 (x2 ) = f 0 (0.5178) = (0.5178 + 1)e0.5178 + sin 0.5178 = 3.0421 Therefore, the third approximation to the root is f (x2 ) x3 = x2 − f 0 (x2 ) 0.0 = 0.5178 − 3.0421 = 0.5178 Example 1.21. Apply Newton’s formula to prove that the recurrence formula for finding the nth roots of a is (n − 1)xni + a xi+1 = nxn−1 i 1. Hence, evaluate (240) 5. 1 Solution: Let x = an ⇒ xn = a or xn − a = 0 Let f (x) = xn − a = 0. ⇒ f 0 (x) = nxn−1. Now, by Newtons’s-Raphson method, we have f (xi ) xni − a xi+1 = xi − ⇒ x i+1 = x i − f 0 (xi ) nxn−1 i (n − 1)xni + a ∴ xi+1 =. nxin−1 1 Now to find the value of (240) 5. 1 1 We know that (243) 5 = (35 ) 5 = 3 Take a = 240 and n = 5 we get 4x5i + a xi+1 = (1.27) 5x4i CHAPTER 1. ALGEBRAIC AND TRANSCENDENTAL EQUATION 24 Let i = 0, xi = x0 = 2.9 (say), then from above equation (1.27), we get 4x50 + 240 4(2.9)5 + 240 x1 = = 5x40 5(2.9)4 4(205.111) + 240 1060.444 = = = 2.99 5(70.7281) 353.6403 Next, let i = 1, xi = x1 = 2.99 (say), then from above equation (1.27), we get 4x51 + 240 4(2.99)5 + 240 x2 = = 5x41 5(2.99)4 4(238.977) + 240 = = 2.9925 399.627 1 Hence, the required value of (240) 4 correct to three places of decimal is 2.993. 1 Example 1.22. Derive the Newton-Raphson method for finding the value of where N > 0. Find N 1 the value of using initial approximation as 0.05. Does the iterations converges? 19 1 1 Solution: Suppose x = or = N. N x 1 0 −1 Take f (x) = − N , f (x) = 2 The Newton-Raphson iteration formula (1.16), the approximation x x to the root is f (xk ) xk+1 = xk − f 0 (xk ) 1 −N xk = xk − −1 x2k 1 − N xk = xk − −1 xk ∴ xk+1 = xk − (N x2k − xk ) xk+1 = xk − N x2k + xk xk+1 = 2xk − N x2k (1.28) Here, N = 19 and x0 = 0.05. Therefore, from equation (1.28) we obtain the sequence of approximations. x1 = 2x0 − N x20 = 2(0.05) − 19(0.05)2 = 0.0525 x2 = 2x1 − N x21 = 2(0.0525) − 19(0.0525)2 = 0.0526 CHAPTER 1. ALGEBRAIC AND TRANSCENDENTAL EQUATION 25 x3 = 2x2 − N x22 = 2(0.0526) − 19(0.0526)2 = 0.0526. Therefore, |x3 − x2 | = |0.0526 − 0.0526| = 0 < 0.0001, hence iterations converges. 1 The required approximate value of is 0.0526. 19 √ Example 1.23. Find the value of 12 using Newton-Raphson method correct to four decimal places. √ Solution: Suppose x = 12, therefore, x2 = 12 ⇒ x2 − 12 = 0. Take f (x) = x2 − 12, f 0 (x) = 2x. f (0) = −12 < 0 f (1) = −11 < 0... f (3) = 9 − 12 = −3 < 0 f (4) = 16 − 12 = 4 > 0 ∴ f (11)f (12) < 0. Therefore, root lies between 3 and 4. 3+4 Take x0 = = 3.5, then we obtain 2 f (x0 ) = f (3.5) = (3.5)2 − 12 = 0.25 f 0 (x0 ) = f 0 (3.5) = 2(3.5) = 7 The Newton-Raphson iteration formula (1.16), the first approximation to the root is f (x0 ) x1 = x0 − f 0 (x0 ) 0.25 = 3.5 − 7 = 3.4625 f (x1 ) = f (3.4625) = (3.4625)2 − 12 = −0.01109 f 0 (x1 ) = f 0 (3.4625) = 2(3.4625) = 6.925 Therefore, the second approximation to the root is f (x1 ) x2 = x1 − f 0 (x1 ) −0.01109 = 3.4625 − 6.925 = 3.4641 CHAPTER 1. ALGEBRAIC AND TRANSCENDENTAL EQUATION 26 f (x2 ) = f (3.4641) = (3.4641)2 − 12 = −0.00001 f 0 (x2 ) = f 0 (3.4641) = 2(3.4641) = 6.9282 f (x2 ) x3 = x2 − f 0 (x2 ) −0.00001 = 3.4641 − 6.9282 = 3.4641. Therefore, the required root of the given equation correct to four decimal places is x ' 3.4641. Exercise:1.2 1. Find the real root correct to three decimal places by the method of False-Position of each of the following equations. a. x3 − x2 − 2 = 0 b. x − 3e−x = 0 c. x3 + x2 + x + 7 = 0 d. x3 − 9x + 1 = 0 e. x2 − lnx − 12 = 0. f. 4e−x sin x − 1 = 0 in [0, 0.5]. 2. Find a real root which lies between 2 and 3 of the equation x logx10 −1.2 = 0 using the method of False-Position to a tolerance of 0.5 %. 3. Find a real the smallest positive root of the equation x4 − x − 10 = 0 correct to three decimal places using the method of False-Position to a tolerance of 0.005. 4. Find a real root of the equation xex − 3 = 0 correct to three decimal places using the method of False-Position to a tolerance of 0.005. 5. Find a real root of each of the following equations correct to three decimal places using Newton- Raphson method. a. x2 + 2x − 2 = 0 b. logx − cosx = 0 c. x3 − 5x + 3 = 0 near x0 = 0.5 CHAPTER 1. ALGEBRAIC AND TRANSCENDENTAL EQUATION 27 d. 3x = 1 + cos x e. tan x = x f. x − ex = 0 π hπ i g. sin x − = 0 in ,π. 2 2 h. x + log x = 2. 6. Using Newton-Raphson method find the value of each of the following. √ a. 27 1 b. (13) 3 1 c. (3) 5. 7. Using Newton-Raphson method derive the formula for finding the k th root of a positive number 1 N and hence compute the value of (25) 4. √ S N 8. Show that the square roots of N = AB is given by N ≈ + , where S = A + B. 4 S √ √ 9. Using N-R method, obtain formula for N and find 20 correct to two decimal places. Solutions Q.1. (a.) 0.7320 (b.)1.6955, (c.) 1.04991, (d.) -2.1046., (e.) 2.9428 (f.) 3.5425, (g.) 6.371 Q.2. 2.7406, Q.3. 1.8555, Q.4. 1.04991 Q.5. (a.) 1.3030, (b.) 0.6565, (c.) 0.6071, (d.) 2.798 (e.) 4.4934, (f.) 1.896, (g.) 0.370 (h.) 1.756. Q.6. (a.) 5.1961, (b.) 2.3523, (c.) 1.2457 Q.7. 2.2360. Q.9. 4.47.  Chapter 2 Calculus of Finite Differences and Interpolation The calculus of finite differences deals with the changes that take place in the value of the dependent variable due to finite changes in the independent variable from this we study the relations that exist between the values, which can be assumed by function, whenever the independent variable changes by finite jumps whether equal or unequal. The study of finite difference calculus has become very important due to its wide variety of application in routine life. It has been originated by Sir Issac Newton. It has been of great use for Mathematicians as well as Computer Scientists for solution of the Scientific, business and engineering problems. There it helps in reducing complex mathematical expressions like trigonometric functions in terms of simple arithmetic operations. Interpolation is important concept in numerical analysis which refers to introducing something additional or extra- neous between other things or parts. In numerical analysis, interpolation is a method of constructing new data points within a discrete set of known data points, using finite differences. The time series data which is recorded after a regular or irregular interval of time consists of values of a phenomenon at a certain point in time, or when the values of some hypothetical function corresponding to a few values of the independent variable are not sufficient to provide information regarding the values of the same phenomenon in between the specified intervals. 2.1 Finite Differences If f is a function from x into y for a ≤ x ≤ b such that y = f (x), this meansthat one or more values of y = f (x) exist corresponding to every value of x in the given range. However if the function f is not known, the value of y can be obtained, when a set of values of x is given. The method to find out such values is based on principle of finite differences provided the function is continuous. Definition 2.1. Many functions may not be available explicitly but only the values of the function at a set of points, called nodes, tabular points or pivotal points. Then finding the value of the function at any non-tabular point, is called interpolation. CHAPTER 2. CALCULUS OF FINITE DIFFERENCES AND INTERPOLATION 29 We consider the function y = f (x) defined on the interval [x0 , xn ], divide the interval [x0 , xn ] such that x0 ≤ x1 ≤ x2 ≤ · · · ≤ xn and the values of x being equally spaced that is xi = x0 + ih, i = 0, 1, 2, · · · , n and h is called interval of differencing. Assume that f (x) is single valued and continuous and that is known explicitly then the values of f (x) corresponding to certain given values of x, say x0 , x1 , x2 , · · · , xn can easily be calculated and tabulated. The set of tabular values (x0 , y0 ), (x1 , y1 ), · · · , (xn , yn ) satisfying the relation y = f (x) and explicit definition of f (x) is not known, it is possible to find a simple function g(x) such that f (x) and g(x) agree at the set of points, this process of finding g(x) is called interpolation. 2.1.1 Forward Differences Let y = f (x) be a single valued function and continuous on the interval [x0 , xn ]. The differences f (x + h) − f (x), f (x + 2h) − f (x + h), · · · , f (x + nh) − f (x + (n − 1)h) are called first forward differences and h is called interval of differencing. These are denoted by ∆f (x) = f (x + h) − f (x) ∆f (x + h) = f (x + 2h) − f (x + h)... The differences of first order forward differences are called second order forward differences. The second order forward differences calculated as follows ∆2 f (x) = ∆[∆f (x)] = ∆[f (x + h) − f (x)] =∆f (x + h) − ∆f (x) =f (x + 2h) − f (x + h) − f (x + h) + f (x) =f (x + 2h) − 2f (x + h) + f (x). The differences of second order forward differences are called third order forward differences. Also, we can denote the forward differences as follows. Let y0 , y1 , y2 , · · · , yn be a set of values of any function y = f (x). The differences y1 − y0 , y2 − y1 , · · · , yn −yn−1 are called first forward differences and are denoted by ∆y0 , ∆y1 , · · · ∆yn , respectively. The operator ∆ is known as the forward difference operator. ∆y0 = y1 − y0 ∆y1 = y2 − y1... ∆yn−1 = yn − yn−1. The differences of first order forward differences are called second order forward differences. The second and order forward differences calculated as follows CHAPTER 2. CALCULUS OF FINITE DIFFERENCES AND INTERPOLATION 30 ∆2 y0 = ∆[∆y0 ] = ∆[y1 − y0 ] = ∆y1 − ∆y0 = y2 − y1 − y1 + y0 = y2 − 2y1 + y0... ∆2 yn−1 = ∆yn − ∆yn−1 ∆3 y0 = ∆2 y1 − ∆2 y0 ∆3 y1 = ∆2 y2 − ∆2 y1... ∆3 yn−1 = ∆2 yn − ∆2 yn−1 In general, nth forward difference are given by ∆n yr =∆n−1 yr−1 − ∆n−1 yr ∆n f (x) =∆n−1 f (x + h) − ∆n−1 f (x) The following is the forward difference table Forward Difference Table x y = f(x) ∆y ∆2 y ∆3 y x0 y0 ∆y0 = y1 − y0 x1 = x0 + h y1 ∆2 y0 = y2 − 2y1 + y0 ∆y1 = y2 − y1 ∆3 y0 = y3 − 3y2 + 3y1 − y0 2 x2 = x0 + 2h y2 ∆ y1 = y3 − 2y2 + y1 ∆y2 = y3 − y2 ∆3 y1 = y4 − 3y3 + 3y2 − y1 2 x3 = x0 + 3h y3 ∆ y2 = y4 − 2y3 + y2 ∆y3 = y4 − y3 ∆3 y2 = y5 − 3y4 + 3y3 − y2 2 x4 = x0 + 4h y4 ∆ y3 = y5 − 2y4 + y3 ∆y4 = y5 − y4 x5 = x0 + 5h y5 The above difference table is called a diagonal difference table. The value x is called the argument and y the function or the entry. The entry y0 is called the leading term and ∆y0 , ∆2 y0 , · · · are called leading differences. Lemma 2.1. Prove that yn = (1 + ∆)n y0 , where ∆ is a forward difference operator. Proof: Let y0 , y1 , y2 , · · · , yn be a set of values of any function y = f (x). The differences y1 − y0 , y2 − y1 , · · · , yn − yn−1 are called first forward differences and are denoted by CHAPTER 2. CALCULUS OF FINITE DIFFERENCES AND INTERPOLATION 31 ∆y0 , ∆y1 , · · · , ∆yn−1 respectively. Therefore, ∆y0 = y1 − y0 y1 = ∆y0 + y0 = (1 + ∆)y0 ∆2 y0 = ∆y1 − ∆y0 ∆y1 = ∆y0 + ∆2 y0 We have, ∆y1 = y2 − y1 ⇒ y2 = y1 + ∆y1 = (1 + ∆)y0 + ∆y0 + ∆2 y0 = (1 + 2∆ + ∆2 )y0 = (1 + ∆)2 y0 Similarly, we obtain, y3 = (1 + ∆)2 y0... yn = (1 + ∆)n y0. Hence, result is proved. Theorem 2.1. If ∆ is linear operator then it satisfies the following axioms (i) ∆[f (x) + g(x)] = ∆[f (x)] + ∆[g(x)] (ii) ∆[Cf (x)] = C∆[f (x)], for any C > 0 and (iii) ∆m ∆n [f (x)] = ∆m+n [f (x)], for all m, n > 0. Example 2.1. Construct the forward difference table for the following set of values x 0 1 2 3 4 5 f(x) 12 15 20 27 39 52 Solution: Forward difference table for given data is: x y = f(x) ∆y ∆2 y ∆3 y ∆4 y ∆5 y 0 12 3 1 15 2 5 0 2 20 2 3 7 3 -10 3 27 5 -7 12 -4 4 39 1 13 5 52 Example 2.2. Construct the forward difference table for the following set of values of f (x) = x2 + x + 1 for x = −2, −1, 0, 1, 2. CHAPTER 2. CALCULUS OF FINITE DIFFERENCES AND INTERPOLATION 32 Solution: The following is the forward difference table for given set of values x y = f(x) ∆y ∆2 y ∆3 y ∆4 y (argument) (entry) −2 = x0 3 = y0 −2 = ∆y0 −1 = x1 1 = y1 2 = ∆ 2 y0 0 = ∆y1 0 = ∆3 y0 0 = x2 1 = y2 2 = ∆ 2 y1 0 = ∆4 y0 3 2 = ∆y2 0 = ∆ y1 1 = x3 3 = y3 2 = ∆ 2 y2 4 = ∆y3 2 = x4 7 = y4 Example 2.3. Find (i) ∆eax and ∆2 eax (ii) the function whose first difference is ex. Solution: (i) Here f (x) = eax , therefore f (x + h) = ea(x+h). We have ∆f (x) = f (x + h) − f (x) ∴ ∆eax = ea(x+h) − eax = eax.eah − eax = (eah − 1)eax ∆2 eax = ∆[∆eax ] = ∆[(eah − 1)eax ] = (eah − 1)∆eax = (eah − 1)[(eah − 1)eax ] = (eah − 1)2 eax. ii) We know that ∆ex = ex−h − ex = ex (eh − 1) , where h is the interval of differencing. Therefore,  x  x 1 x e e = h ∆e = ∆ h e −1 e −1 x e Hence, required function is given by h. e −1 Backward Differences Let y = f (x) be a single valued function and continuous on the interval [x0 , xn ]. The differences f (x) − f (x − h), f (x + h) − f (x), · · · , f (x + nh) − f (x + (n − 1)h), (n = 0, 1, 2 · · · , n) are called first backward differences and h is called interval of differencing. These are denoted by ∇f (x) = f (x) − f (x − h) CHAPTER 2. CALCULUS OF FINITE DIFFERENCES AND INTERPOLATION 33 ∇f (x + h) = f (x + h) − f (x)... ∇f (x + nh) = f (x + nh) − f (x + (n − 1)h). The differences of first order backward differences are called second order backward differences. The second order backward differences calculated as follows ∇2 f (x + h) = ∇[∇f (x + h)] =∇[f (x + h) − f (x)] =∇f (x + h) − ∇f (x) =f (x + h) − f (x) − f (x) + f (x − h) =f (x + h) − 2f (x) + f (x − h). The differences of second order backward differences are called third order backward differences. Also, we can denote the forward differences as follows. Let y0 , y1 , y2 · · · , yn be a set of values of any function y = f (x). The differences y1 −y0 , y2 −y1 , · · · yn −yn−1 are called first backward differences and are denoted by ∇y1 , ∇y2 , · · · ∇yn , respectively. The operator ∇ is known as the backward difference operator. ∇y1 = y1 − y0 ∇y2 = y2 − y1... ∇yn = yn − yn−1. Also it can be written as, ∇f (x + h) = f (x + h) − f (x). Similarly, second forward difference is given by, ∇2 f (x + h) = ∇f (x + h) − ∇f (x). The differences of first order backward differences are called second order backward differences. The second order backward differences calculated as follows ∇2 y2 = ∇[∇y2 ] = ∇[y2 − y1 ] = ∇y2 − ∇y1 = y2 − y1 − y1 + y0 = y2 − 2y1 + y0. In general, ∇n yr+1 = ∇n−1 yr+1 − ∇n−1 yr ∇n f (x + h) = ∇n−1 f (x + h) − ∇n−1 f (x). CHAPTER 2. CALCULUS OF FINITE DIFFERENCES AND INTERPOLATION 34 Backward Difference Table x y = f(x) ∇y ∇2 y ∇3 y ∇4 y x0 y0 ∇y1 x1 y1 ∇2 y2 ∇y2 ∇3 y3 x2 y2 ∇2 y3 ∇4 y4 3 ∇y3 ∇ y4 2 x3 y3 ∇ y4 ∇y4 x4 y4 Central Differences The central difference operator is denoted by the symbol δ and central differences is given by,     h h δf (x) = f x + −f x− 2 2 It is also w