Solutions Of Equations In One Variable [0.125in]3.375in0.02in Newton's .
![Solutions Of Equations In One Variable [0.125in]3.375in0.02in Newton's .](/img2/200/ch02-3a.webp)
Solutions of Equations in One VariableNewton’s MethodNumerical Analysis (9th Edition)R L Burden & J D FairesBeamer Presentation Slidesprepared byJohn CarrollDublin City Universityc 2011 Brooks/Cole, Cengage Learning
DerivationExampleConvergenceFinal RemarksOutline1Newton’s Method: DerivationNumerical Analysis (Chapter 2)Newton’s MethodR L Burden & J D Faires2 / 33
DerivationExampleConvergenceFinal RemarksOutline1Newton’s Method: Derivation2Example using Newton’s Method & Fixed-Point IterationNumerical Analysis (Chapter 2)Newton’s MethodR L Burden & J D Faires2 / 33
DerivationExampleConvergenceFinal RemarksOutline1Newton’s Method: Derivation2Example using Newton’s Method & Fixed-Point Iteration3Convergence using Newton’s MethodNumerical Analysis (Chapter 2)Newton’s MethodR L Burden & J D Faires2 / 33
DerivationExampleConvergenceFinal RemarksOutline1Newton’s Method: Derivation2Example using Newton’s Method & Fixed-Point Iteration3Convergence using Newton’s Method4Final Remarks on Practical ApplicationNumerical Analysis (Chapter 2)Newton’s MethodR L Burden & J D Faires2 / 33
DerivationExampleConvergenceFinal RemarksOutline1Newton’s Method: Derivation2Example using Newton’s Method & Fixed-Point Iteration3Convergence using Newton’s Method4Final Remarks on Practical ApplicationNumerical Analysis (Chapter 2)Newton’s MethodR L Burden & J D Faires3 / 33
DerivationExampleConvergenceFinal RemarksNewton’s MethodContextNewton’s (or the Newton-Raphson) method is one of the most powerfuland well-known numerical methods for solving a root-finding problem.Numerical Analysis (Chapter 2)Newton’s MethodR L Burden & J D Faires4 / 33
DerivationExampleConvergenceFinal RemarksNewton’s MethodContextNewton’s (or the Newton-Raphson) method is one of the most powerfuland well-known numerical methods for solving a root-finding problem.Various ways of introducing Newton’s methodGraphically, as is often done in calculus.Numerical Analysis (Chapter 2)Newton’s MethodR L Burden & J D Faires4 / 33
DerivationExampleConvergenceFinal RemarksNewton’s MethodContextNewton’s (or the Newton-Raphson) method is one of the most powerfuland well-known numerical methods for solving a root-finding problem.Various ways of introducing Newton’s methodGraphically, as is often done in calculus.As a technique to obtain faster convergence than offered by othertypes of functional iteration.Numerical Analysis (Chapter 2)Newton’s MethodR L Burden & J D Faires4 / 33
DerivationExampleConvergenceFinal RemarksNewton’s MethodContextNewton’s (or the Newton-Raphson) method is one of the most powerfuland well-known numerical methods for solving a root-finding problem.Various ways of introducing Newton’s methodGraphically, as is often done in calculus.As a technique to obtain faster convergence than offered by othertypes of functional iteration.Using Taylor polynomials. We will see there that this particularderivation produces not only the method, but also a bound for theerror of the approximation.Numerical Analysis (Chapter 2)Newton’s MethodR L Burden & J D Faires4 / 33
DerivationExampleConvergenceFinal RemarksNewton’s MethodDerivationNumerical Analysis (Chapter 2)Newton’s MethodR L Burden & J D Faires5 / 33
DerivationExampleConvergenceFinal RemarksNewton’s MethodDerivationSuppose that f C 2 [a, b]. Let p0 [a, b] be an approximation to psuch that f 0 (p0 ) 6 0 and p p0 is “small.”Numerical Analysis (Chapter 2)Newton’s MethodR L Burden & J D Faires5 / 33
DerivationExampleConvergenceFinal RemarksNewton’s MethodDerivationSuppose that f C 2 [a, b]. Let p0 [a, b] be an approximation to psuch that f 0 (p0 ) 6 0 and p p0 is “small.”Consider the first Taylor polynomial for f (x) expanded about p0and evaluated at x p.f (p) f (p0 ) (p p0 )f 0 (p0 ) (p p0 )2 00f (ξ(p)),2where ξ(p) lies between p and p0 .Numerical Analysis (Chapter 2)Newton’s MethodR L Burden & J D Faires5 / 33
DerivationExampleConvergenceFinal RemarksNewton’s MethodDerivationSuppose that f C 2 [a, b]. Let p0 [a, b] be an approximation to psuch that f 0 (p0 ) 6 0 and p p0 is “small.”Consider the first Taylor polynomial for f (x) expanded about p0and evaluated at x p.f (p) f (p0 ) (p p0 )f 0 (p0 ) (p p0 )2 00f (ξ(p)),2where ξ(p) lies between p and p0 .Since f (p) 0, this equation gives0 f (p0 ) (p p0 )f 0 (p0 ) Numerical Analysis (Chapter 2)Newton’s Method(p p0 )2 00f (ξ(p)).2R L Burden & J D Faires5 / 33
DerivationExampleConvergenceFinal RemarksNewton’s Method0 f (p0 ) (p p0 )f 0 (p0 ) (p p0 )2 00f (ξ(p)).2Derivation (Cont’d)Numerical Analysis (Chapter 2)Newton’s MethodR L Burden & J D Faires6 / 33
DerivationExampleConvergenceFinal RemarksNewton’s Method0 f (p0 ) (p p0 )f 0 (p0 ) (p p0 )2 00f (ξ(p)).2Derivation (Cont’d)Newton’s method is derived by assuming that since p p0 issmall, the term involving (p p0 )2 is much smaller, so0 f (p0 ) (p p0 )f 0 (p0 ).Numerical Analysis (Chapter 2)Newton’s MethodR L Burden & J D Faires6 / 33
DerivationExampleConvergenceFinal RemarksNewton’s Method0 f (p0 ) (p p0 )f 0 (p0 ) (p p0 )2 00f (ξ(p)).2Derivation (Cont’d)Newton’s method is derived by assuming that since p p0 issmall, the term involving (p p0 )2 is much smaller, so0 f (p0 ) (p p0 )f 0 (p0 ).Solving for p givesp p0 Numerical Analysis (Chapter 2)f (p0 ) p1 .f 0 (p0 )Newton’s MethodR L Burden & J D Faires6 / 33
DerivationExampleConvergenceFinal RemarksNewton’s Methodp p0 f (p0 ) p1 .f 0 (p0 )Newton’s MethodNumerical Analysis (Chapter 2)Newton’s MethodR L Burden & J D Faires7 / 33
DerivationExampleConvergenceFinal RemarksNewton’s Methodp p0 f (p0 ) p1 .f 0 (p0 )Newton’s MethodThis sets the stage for Newton’s method, which starts with an initialapproximation p0 and generates the sequence {pn } n 0 , bypn pn 1 Numerical Analysis (Chapter 2)f (pn 1 )f 0 (pn 1 )Newton’s Methodfor n 1R L Burden & J D Faires7 / 33
DerivationExampleConvergenceFinal RemarksNewton’s Method: Using Successive TangentsySlope f 9(p1)y 5 f (x)(p1, f ( p1))p0Slope f 9( p0)pp2p1x(p0, f ( p0))Numerical Analysis (Chapter 2)Newton’s MethodR L Burden & J D Faires8 / 33
DerivationExampleConvergenceFinal RemarksNewton’s AlgorithmTo find a solution to f (x) 0 given an initial approximation p0 :Numerical Analysis (Chapter 2)Newton’s MethodR L Burden & J D Faires9 / 33
DerivationExampleConvergenceFinal RemarksNewton’s AlgorithmTo find a solution to f (x) 0 given an initial approximation p0 :1. Set i 0;2. While i N, do Step 3:Numerical Analysis (Chapter 2)Newton’s MethodR L Burden & J D Faires9 / 33
DerivationExampleConvergenceFinal RemarksNewton’s AlgorithmTo find a solution to f (x) 0 given an initial approximation p0 :1. Set i 0;2. While i N, do Step 3:3.1 If f 0 (p0 ) 0 then Step 5.Numerical Analysis (Chapter 2)Newton’s MethodR L Burden & J D Faires9 / 33
DerivationExampleConvergenceFinal RemarksNewton’s AlgorithmTo find a solution to f (x) 0 given an initial approximation p0 :1. Set i 0;2. While i N, do Step 3:3.1 If f 0 (p0 ) 0 then Step 5.3.2 Set p p0 f (p0 )/f 0 (p0 );Numerical Analysis (Chapter 2)Newton’s MethodR L Burden & J D Faires9 / 33
DerivationExampleConvergenceFinal RemarksNewton’s AlgorithmTo find a solution to f (x) 0 given an initial approximation p0 :1. Set i 0;2. While i N, do Step 3:3.1 If f 0 (p0 ) 0 then Step 5.3.2 Set p p0 f (p0 )/f 0 (p0 );3.3 If p p0 TOL then Step 6;Numerical Analysis (Chapter 2)Newton’s MethodR L Burden & J D Faires9 / 33
DerivationExampleConvergenceFinal RemarksNewton’s AlgorithmTo find a solution to f (x) 0 given an initial approximation p0 :1. Set i 0;2. While i N, do Step 3:3.13.23.33.4If f 0 (p0 ) 0 then Step 5.Set p p0 f (p0 )/f 0 (p0 );If p p0 TOL then Step 6;Set i i 1;Numerical Analysis (Chapter 2)Newton’s MethodR L Burden & J D Faires9 / 33
DerivationExampleConvergenceFinal RemarksNewton’s AlgorithmTo find a solution to f (x) 0 given an initial approximation p0 :1. Set i 0;2. While i N, do Step 3:3.13.23.33.43.5If f 0 (p0 ) 0 then Step 5.Set p p0 f (p0 )/f 0 (p0 );If p p0 TOL then Step 6;Set i i 1;Set p0 p;Numerical Analysis (Chapter 2)Newton’s MethodR L Burden & J D Faires9 / 33
DerivationExampleConvergenceFinal RemarksNewton’s AlgorithmTo find a solution to f (x) 0 given an initial approximation p0 :1. Set i 0;2. While i N, do Step 3:3.13.23.33.43.5If f 0 (p0 ) 0 then Step 5.Set p p0 f (p0 )/f 0 (p0 );If p p0 TOL then Step 6;Set i i 1;Set p0 p;4. Output a ‘failure to converge within the specified number ofiterations’ message & Stop;Numerical Analysis (Chapter 2)Newton’s MethodR L Burden & J D Faires9 / 33
DerivationExampleConvergenceFinal RemarksNewton’s AlgorithmTo find a solution to f (x) 0 given an initial approximation p0 :1. Set i 0;2. While i N, do Step 3:3.13.23.33.43.5If f 0 (p0 ) 0 then Step 5.Set p p0 f (p0 )/f 0 (p0 );If p p0 TOL then Step 6;Set i i 1;Set p0 p;4. Output a ‘failure to converge within the specified number ofiterations’ message & Stop;5. Output an appropriate failure message (zero derivative) & Stop;Numerical Analysis (Chapter 2)Newton’s MethodR L Burden & J D Faires9 / 33
DerivationExampleConvergenceFinal RemarksNewton’s AlgorithmTo find a solution to f (x) 0 given an initial approximation p0 :1. Set i 0;2. While i N, do Step 3:3.13.23.33.43.5If f 0 (p0 ) 0 then Step 5.Set p p0 f (p0 )/f 0 (p0 );If p p0 TOL then Step 6;Set i i 1;Set p0 p;4. Output a ‘failure to converge within the specified number ofiterations’ message & Stop;5. Output an appropriate failure message (zero derivative) & Stop;6. Output pNumerical Analysis (Chapter 2)Newton’s MethodR L Burden & J D Faires9 / 33
DerivationExampleConvergenceFinal RemarksNewton’s MethodStopping Criteria for the AlgorithmVarious stopping procedures can be applied in Step 3.3.Numerical Analysis (Chapter 2)Newton’s MethodR L Burden & J D Faires10 / 33
DerivationExampleConvergenceFinal RemarksNewton’s MethodStopping Criteria for the AlgorithmVarious stopping procedures can be applied in Step 3.3.We can select a tolerance 0 and generate p1 , . . . , pN until oneof the following conditions is met:Numerical Analysis (Chapter 2)Newton’s MethodR L Burden & J D Faires10 / 33
DerivationExampleConvergenceFinal RemarksNewton’s MethodStopping Criteria for the AlgorithmVarious stopping procedures can be applied in Step 3.3.We can select a tolerance 0 and generate p1 , . . . , pN until oneof the following conditions is met: pN pN 1 pN pN 1 pN ,(1)pN 6 0,or f (pN ) Numerical Analysis (Chapter 2)Newton’s Method(2)(3)R L Burden & J D Faires10 / 33
DerivationExampleConvergenceFinal RemarksNewton’s MethodStopping Criteria for the AlgorithmVarious stopping procedures can be applied in Step 3.3.We can select a tolerance 0 and generate p1 , . . . , pN until oneof the following conditions is met: pN pN 1 pN pN 1 pN ,(1)pN 6 0,or f (pN ) (2)(3)Note that none of these inequalities give precise information aboutthe actual error pN p .Numerical Analysis (Chapter 2)Newton’s MethodR L Burden & J D Faires10 / 33
DerivationExampleConvergenceFinal RemarksNewton’s Method as a Functional Iteration TechniqueFunctional IterationNumerical Analysis (Chapter 2)Newton’s MethodR L Burden & J D Faires11 / 33
DerivationExampleConvergenceFinal RemarksNewton’s Method as a Functional Iteration TechniqueFunctional IterationNewton’s Methodpn pn 1 Numerical Analysis (Chapter 2)f (pn 1 )f 0 (pn 1 )Newton’s Methodfor n 1R L Burden & J D Faires11 / 33
DerivationExampleConvergenceFinal RemarksNewton’s Method as a Functional Iteration TechniqueFunctional IterationNewton’s Methodpn pn 1 f (pn 1 )f 0 (pn 1 )for n 1can be written in the formpn g (pn 1 )Numerical Analysis (Chapter 2)Newton’s MethodR L Burden & J D Faires11 / 33
DerivationExampleConvergenceFinal RemarksNewton’s Method as a Functional Iteration TechniqueFunctional IterationNewton’s Methodpn pn 1 f (pn 1 )f 0 (pn 1 )for n 1can be written in the formpn g (pn 1 )withg (pn 1 ) pn 1 Numerical Analysis (Chapter 2)f (pn 1 )f 0 (pn 1 )Newton’s Methodfor n 1R L Burden & J D Faires11 / 33
DerivationExampleConvergenceFinal RemarksOutline1Newton’s Method: Derivation2Example using Newton’s Method & Fixed-Point Iteration3Convergence using Newton’s Method4Final Remarks on Practical ApplicationNumerical Analysis (Chapter 2)Newton’s MethodR L Burden & J D Faires12 / 33
DerivationExampleConvergenceFinal RemarksNewton’s MethodExample: Fixed-Point Iteration & Newton’s MethodConsider the functionf (x) cos x x 0Approximate a root of f using (a) a fixed-point method, and (b)Newton’s MethodNumerical Analysis (Chapter 2)Newton’s MethodR L Burden & J D Faires13 / 33
DerivationExampleConvergenceFinal RemarksNewton’s Method & Fixed-Point Iterationyy5x1y 5 cos x1Numerical Analysis (Chapter 2)Newton’s MethodqxR L Burden & J D Faires14 / 33
DerivationExampleConvergenceFinal RemarksNewton’s Method & Fixed-Point Iteration(a) Fixed-Point Iteration for f (x) cos x xNumerical Analysis (Chapter 2)Newton’s MethodR L Burden & J D Faires15 / 33
DerivationExampleConvergenceFinal RemarksNewton’s Method & Fixed-Point Iteration(a) Fixed-Point Iteration for f (x) cos x xA solution to this root-finding problem is also a solution to thefixed-point problemx cos xand the graph implies that a single fixed-point p lies in [0, π/2].Numerical Analysis (Chapter 2)Newton’s MethodR L Burden & J D Faires15 / 33
DerivationExampleConvergenceFinal RemarksNewton’s Method & Fixed-Point Iteration(a) Fixed-Point Iteration for f (x) cos x xA solution to this root-finding problem is also a solution to thefixed-point problemx cos xand the graph implies that a single fixed-point p lies in [0, π/2].The following table shows the results of fixed-point iteration withp0 π/4.Numerical Analysis (Chapter 2)Newton’s MethodR L Burden & J D Faires15 / 33
DerivationExampleConvergenceFinal RemarksNewton’s Method & Fixed-Point Iteration(a) Fixed-Point Iteration for f (x) cos x xA solution to this root-finding problem is also a solution to thefixed-point problemx cos xand the graph implies that a single fixed-point p lies in [0, π/2].The following table shows the results of fixed-point iteration withp0 π/4.The best conclusion from these results is that p 0.74.Numerical Analysis (Chapter 2)Newton’s MethodR L Burden & J D Faires15 / 33
DerivationExampleConvergenceFinal RemarksNewton’s Method & Fixed-Point IterationFixed-Point Iteration: x cos(x), x0 n1234567pn 0.743464Numerical Analysis (Chapter 4640.736128π4 pn pn 1 .007336Newton’s Methoden /en 16R L Burden & J D Faires16 / 33
DerivationExampleConvergenceFinal RemarksNewton’s Method(b) Newton’s Method for f (x) cos x xNumerical Analysis (Chapter 2)Newton’s MethodR L Burden & J D Faires17 / 33
DerivationExampleConvergenceFinal RemarksNewton’s Method(b) Newton’s Method for f (x) cos x xTo apply Newton’s method to this problem we needf 0 (x) sin x 1Numerical Analysis (Chapter 2)Newton’s MethodR L Burden & J D Faires17 / 33
DerivationExampleConvergenceFinal RemarksNewton’s Method(b) Newton’s Method for f (x) cos x xTo apply Newton’s method to this problem we needf 0 (x) sin x 1Starting again with p0 π/4, we generate the sequence defined,for n 1, bypn pn 1 Numerical Analysis (Chapter 2)f (pn 1 )cos pn 1 pn 1. pn 1 0f (pn 1 sin pn 1 1)Newton’s MethodR L Burden & J D Faires17 / 33
DerivationExampleConvergenceFinal RemarksNewton’s Method(b) Newton’s Method for f (x) cos x xTo apply Newton’s method to this problem we needf 0 (x) sin x 1Starting again with p0 π/4, we generate the sequence defined,for n 1, bypn pn 1 f (pn 1 )cos pn 1 pn 1. pn 1 0f (pn 1 sin pn 1 1)This gives the approximations shown in the following table.Numerical Analysis (Chapter 2)Newton’s MethodR L Burden & J D Faires17 / 33
DerivationExampleConvergenceFinal RemarksNewton’s MethodNewton’s Method for f (x) cos(x) x, x0 n1234pn 10.785398160.739536130.739085180.73908513Numerical Analysis (Chapter 2)f (pn 1 )-0.078291-0.000755-0.000000-0.000000f 0 (pn 1 )-1.707107-1.673945-1.673612-1.673612Newton’s 3 pn pn 1 0.045862030.000450960.000000040.00000000R L Burden & J D Faires18 / 33
DerivationExampleConvergenceFinal RemarksNewton’s MethodNewton’s Method for f (x) cos(x) x, x0 n1234pn 10.785398160.739536130.739085180.73908513f (pn 1 )-0.078291-0.000755-0.000000-0.000000f 0 (pn 1 130.739085180.739085130.73908513 pn pn 1 0.045862030.000450960.000000040.00000000An excellent approximation is obtained with n 3.Numerical Analysis (Chapter 2)Newton’s MethodR L Burden & J D Faires18 / 33
DerivationExampleConvergenceFinal RemarksNewton’s MethodNewton’s Method for f (x) cos(x) x, x0 n1234pn 10.785398160.739536130.739085180.73908513f (pn 1 )-0.078291-0.000755-0.000000-0.000000f 0 (pn 1 130.739085180.739085130.73908513 pn pn 1 0.045862030.000450960.000000040.00000000An excellent approximation is obtained with n 3.Because of the agreement of p3 and p4 we could reasonablyexpect this result to be accurate to the places listed.Numerical Analysis (Chapter 2)Newton’s MethodR L Burden & J D Faires18 / 33
DerivationExampleConvergenceFinal RemarksOutline1Newton’s Method: Derivation2Example using Newton’s Method & Fixed-Point Iteration3Convergence using Newton’s Method4Final Remarks on Practical ApplicationNumerical Analysis (Chapter 2)Newton’s MethodR L Burden & J D Faires19 / 33
DerivationExampleConvergenceFinal RemarksConvergence using Newton’s MethodTheoretical importance of the choice of p0Numerical Analysis (Chapter 2)Newton’s MethodR L Burden & J D Faires20 / 33
DerivationExampleConvergenceFinal RemarksConvergence using Newton’s MethodTheoretical importance of the choice of p0The Taylor series derivation of Newton’s method points out theimportance of an accurate initial approximation.Numerical Analysis (Chapter 2)Newton’s MethodR L Burden & J D Faires20 / 33
DerivationExampleConvergenceFinal RemarksConvergence using Newton’s MethodTheoretical importance of the choice of p0The Taylor series derivation of Newton’s method points out theimportance of an accurate initial approximation.The crucial assumption is that the term involving (p p0 )2 is, bycomparison with p p0 , so small that it can be deleted.Numerical Analysis (Chapter 2)Newton’s MethodR L Burden & J D Faires20 / 33
DerivationExampleConvergenceFinal RemarksConvergence using Newton’s MethodTheoretical importance of the choice of p0The Taylor series derivation of Newton’s method points out theimportance of an accurate initial approximation.The crucial assumption is that the term involving (p p0 )2 is, bycomparison with p p0 , so small that it can be deleted.This will clearly be false unless p0 is a good approximation to p.Numerical Analysis (Chapter 2)Newton’s MethodR L Burden & J D Faires20 / 33
DerivationExampleConvergenceFinal RemarksConvergence using Newton’s MethodTheoretical importance of the choice of p0The Taylor series derivation of Newton’s method points out theimportance of an accurate initial approximation.The crucial assumption is that the term involving (p p0 )2 is, bycomparison with p p0 , so small that it can be deleted.This will clearly be false unless p0 is a good approximation to p.If p0 is not sufficiently close to the actual root, there is little reasonto suspect that Newton’s method will converge to the root.Numerical Analysis (Chapter 2)Newton’s MethodR L Burden & J D Faires20 / 33
DerivationExampleConvergenceFinal RemarksConvergence using Newton’s MethodTheoretical importance of the choice of p0The Taylor series derivation of Newton’s method points out theimportance of an accurate initial approximation.The crucial assumption is that the term involving (p p0 )2 is, bycomparison with p p0 , so small that it can be deleted.This will clearly be false unless p0 is a good approximation to p.If p0 is not sufficiently close to the actual root, there is little reasonto suspect that Newton’s method will converge to the root.However, in some instances, even poor initial approximations willproduce convergence.Numerical Analysis (Chapter 2)Newton’s MethodR L Burden & J D Faires20 / 33
DerivationExampleConvergenceFinal RemarksConvergence using Newton’s MethodConvergence Theorem for Newton’s MethodNumerical Analysis (Chapter 2)Newton’s MethodR L Burden & J D Faires21 / 33
DerivationExampleConvergenceFinal RemarksConvergence using Newton’s MethodConvergence Theorem for Newton’s MethodLet f C 2 [a, b]. If p (a, b) is such that f (p) 0 and f 0 (p) 6 0.Numerical Analysis (Chapter 2)Newton’s MethodR L Burden & J D Faires21 / 33
DerivationExampleConvergenceFinal RemarksConvergence using Newton’s MethodConvergence Theorem for Newton’s MethodLet f C 2 [a, b]. If p (a, b) is such that f (p) 0 and f 0 (p) 6 0.Then there exists a δ 0 such that Newton’s method generates asequence {pn } n 1 , defined bypn pn 1 f (pn 1 )0f (pn 1)converging to p for any initial approximationp0 [p δ, p δ]Numerical Analysis (Chapter 2)Newton’s MethodR L Burden & J D Faires21 / 33
DerivationExampleConvergenceFinal RemarksConvergence using Newton’s MethodConvergence Theorem (1/4)Numerical Analysis (Chapter 2)Newton’s MethodR L Burden & J D Faires22 / 33
DerivationExampleConvergenceFinal RemarksConvergence using Newton’s MethodConvergence Theorem (1/4)The proof is based on analyzing Newton’s method as thefunctional iteration scheme pn g(pn 1 ), for n 1, withg(x) x Numerical Analysis (Chapter 2)Newton’s Methodf (x).f 0 (x)R L Burden & J D Faires22 / 33
DerivationExampleConvergenceFinal RemarksConvergence using Newton’s MethodConvergence Theorem (1/4)The proof is based on analyzing Newton’s method as thefunctional iteration scheme pn g(pn 1 ), for n 1, withg(x) x f (x).f 0 (x)Let k be in (0, 1). We first find an interval [p δ, p δ] that g mapsinto itself and for which g 0 (x) k , for all x (p δ, p δ).Numerical Analysis (Chapter 2)Newton’s MethodR L Burden & J D Faires22 / 33
DerivationExampleConvergenceFinal RemarksConvergence using Newton’s MethodConvergence Theorem (1/4)The proof is based on analyzing Newton’s method as thefunctional iteration scheme pn g(pn 1 ), for n 1, withg(x) x f (x).f 0 (x)Let k be in (0, 1). We first find an interval [p δ, p δ] that g mapsinto itself and for which g 0 (x) k , for all x (p δ, p δ).Since f 0 is continuous and f 0 (p) 6 0, part (a) of Exercise 29 inSection 1.1 Ex 29 implies that there exists a δ1 0, such thatf 0 (x) 6 0 for x [p δ1 , p δ1 ] [a, b].Numerical Analysis (Chapter 2)Newton’s MethodR L Burden & J D Faires22 / 33
DerivationExampleConvergenceFinal RemarksConvergence using Newton’s MethodConvergence Theorem (2/4)Numerical Analysis (Chapter 2)Newton’s MethodR L Burden & J D Faires23 / 33
DerivationExampleConvergenceFinal RemarksConvergence using Newton’s MethodConvergence Theorem (2/4)Thus g is defined and continuous on [p δ1 , p δ1 ]. Alsog 0 (x) 1 f 0 (x)f 0 (x) f (x)f 00 (x)f (x)f 00 (x) ,[f 0 (x)]2[f 0 (x)]2for x [p δ1 , p δ1 ], and, since f C 2 [a, b], we haveg C 1 [p δ1 , p δ1 ].Numerical Analysis (Chapter 2)Newton’s MethodR L Burden & J D Faires23 / 33
DerivationExampleConvergenceFinal RemarksConvergence using Newton’s MethodConvergence Theorem (2/4)Thus g is defined and continuous on [p δ1 , p δ1 ]. Alsog 0 (x) 1 f 0 (x)f 0 (x) f (x)f 00 (x)f (x)f 00 (x) ,[f 0 (x)]2[f 0 (x)]2for x [p δ1 , p δ1 ], and, since f C 2 [a, b], we haveg C 1 [p δ1 , p δ1 ].By assumption, f (p) 0, sog 0 (p) Numerical Analysis (Chapter 2)f (p)f 00 (p) 0.[f 0 (p)]2Newton’s MethodR L Burden & J D Faires23 / 33
DerivationExampleConvergenceFinal RemarksConvergence using Newton’s Methodg 0 (p) f (p)f 00 (p) 0.[f 0 (p)]2Convergence Theorem (3/4)Numerical Analysis (Chapter 2)Newton’s MethodR L Burden & J D Faires24 / 33
DerivationExampleConvergenceFinal RemarksConvergence using Newton’s Methodg 0 (p) f (p)f 00 (p) 0.[f 0 (p)]2Convergence Theorem (3/4)Since g 0 is continuous and 0 k 1, part (b) of Exercise 29 inSection 1.1 Ex 29 implies that there exists a δ, with 0 δ δ1 ,and g 0 (x) k , for all x [p δ, p δ].Numerical Analysis (Chapter 2)Newton’s MethodR L Burden & J D Faires24 / 33
DerivationExampleConvergenceFinal RemarksConvergence using Newton’s Methodg 0 (p) f (p)f 00 (p) 0.[f 0 (p)]2Convergence Theorem (3/4)Since g 0 is continuous and 0 k 1, part (b) of Exercise 29 inSection 1.1 Ex 29 implies that there exists a δ, with 0 δ δ1 ,and g 0 (x) k , for all x [p δ, p δ].It remains to show that g maps [p δ, p δ] into [p δ, p δ].Numerical Analysis (Chapter 2)Newton’s MethodR L Burden & J D Faires24 / 33
DerivationExampleConvergenceFinal RemarksConvergence using Newton’s Methodg 0 (p) f (p)f 00 (p) 0.[f 0 (p)]2Convergence Theorem (3/4)Since g 0 is continuous and 0 k 1, part (b) of Exercise 29 inSection 1.1 Ex 29 implies that there exists a δ, with 0 δ δ1 ,and g 0 (x) k , for all x [p δ, p δ].It remains to show that g maps [p δ, p δ] into [p δ, p δ].If x [p δ, p δ], the Mean Value Theorem MVT implies that forsome number ξ between x and p, g(x) g(p) g 0 (ξ) x p . So g(x) p g(x) g(p) g 0 (ξ) x p k x p x p .Numerical Analysis (Chapter 2)Newton’s MethodR L Burden & J D Faires24 / 33
DerivationExampleConvergenceFinal RemarksConvergence using Newton’s MethodConvergence Theorem (4/4)Numerical Analysis (Chapter 2)Newton’s MethodR L Burden & J D Faires25 / 33
DerivationExampleConvergenceFinal RemarksConvergence using Newton’s MethodConvergence Theorem (4/4)Since x [p δ, p δ], it follows that x p δ and that g(x) p δ. Hence, g maps [p δ, p δ] into [p δ, p δ].Numerical Analysis (Chapter 2)Newton’s MethodR L Burden & J D Faires25 / 33
DerivationExampleConvergenceFinal RemarksConvergence using Newton’s MethodConvergence Theorem (4/4)Since x [p δ, p δ], it follows that x p δ and that g(x) p δ. Hence, g maps [p δ, p δ] into [p δ, p δ].All the hypotheses of the Fixed-Point Theoremsatisfied, so the sequence {pn } n 1 , defined bypn g(pn 1 ) pn 1 f (pn 1 ),f 0 (pn 1 )Theorem 2.4are nowfor n 1,converges to p for any p0 [p δ, p δ].Numerical Analysis (Chapter 2)Newton’s MethodR L Burden & J D Faires25 / 33
DerivationExampleConvergenceFinal RemarksOutline1Newton’s Method: Derivation2Example using Newton’s Method & Fixed-Point Iteration3Convergence using Newton’s Method4Final Remarks on Practical ApplicationNumerical Analysis (Chapter 2)Newton’s MethodR L Burden & J D Faires26 / 33
DerivationExampleConvergenceFinal RemarksNewton’s Method in PracticeChoice of Initial ApproximationNumerical Analysis (Chapter 2)Newton’s MethodR L Burden & J D Faires27 / 33
DerivationExampleConvergenceFinal RemarksNewton’s Method in PracticeChoice of Initial ApproximationThe convergence theorem states that, under reasonableassumptions, Newton’s method converges provided a sufficientlyaccurate initial approximation is chosen.Numerical Analysis (Chapter 2)Newton’s MethodR L Burden & J D Faires27 / 33
DerivationExampleConvergenceFinal RemarksNewton’s Method in PracticeChoice of Initial ApproximationThe convergence theorem states that, under reasonableassumptions, Newton’s method converges provided a sufficientlyaccurate initial approximation is chosen.It also implies that the constant k that bounds the derivative of g,and, consequently, indicates the speed of convergence of themethod, decreases to 0 as the procedure continues.Numerical Analysis (Chapter 2)Newton’s MethodR L Burden & J D Faires27 / 33
DerivationExampleConvergenceFinal RemarksNewton’s Method in PracticeChoice of Initial ApproximationThe convergence theorem states that, under reasonableassumptions, Newton’s method converges provided a sufficientlyaccurate initial approximation is chosen.It also implies that the constant k that bounds the derivative of g,and, consequently, indicates the speed of convergence of themethod, decreases to 0 as the procedure continues.This result is important for the theory of Newton’s method, but it isseldom applied in practice because it does not tell us how todetermine δ.Numerical Analysis (Chapter 2)Newton’s MethodR L Burden & J D Faires27 / 33
DerivationExampleConvergenceFinal RemarksNewton’s Method in PracticeIn a practical application . . .Numerical Analysis (Chapter 2)Newton’s MethodR L Burden & J D Faires28 / 33
DerivationExampleConvergenceFinal RemarksNewton’s Method in PracticeIn a practical application . . .an initial approximation is selectedNumerical Analysis (Chapter 2)Newton’s MethodR L Burden & J D Faires28 / 33
DerivationExampleConvergenceFinal RemarksNewton’s Method in PracticeIn a practical application . . .an initial approximation is selectedand successive approximations are generated by Newton’smethod.Numerical Analysis (Chapter 2)Newton’s MethodR L Burden & J D Faires28 / 33
DerivationExampleConvergenceFinal RemarksNewton’s Method in PracticeIn a
Derivation Example Convergence Final Remarks Outline 1 Newton's Method: Derivation 2 Example using Newton's Method & Fixed-Point Iteration 3 Convergence using Newton's Method 4 Final Remarks on Practical Application Numerical Analysis (Chapter 2) Newton's Method R L Burden & J D Faires 2 / 33
EQUATIONS AND INEQUALITIES Golden Rule of Equations: "What you do to one side, you do to the other side too" Linear Equations Quadratic Equations Simultaneous Linear Equations Word Problems Literal Equations Linear Inequalities 1 LINEAR EQUATIONS E.g. Solve the following equations: (a) (b) 2s 3 11 4 2 8 2 11 3 s
1.2 First Order Equations 5 1.3 Direction Fields for First Order Equations 14 Chapter 2 First Order Equations 2.1 Linear First Order Equations 27 2.2 Separable Equations 39 2.3 Existence and Uniqueness of Solutions of Nonlinear Equations 48 2.5 Exact Equations 55 2.6 Integrating Factors 63 Chapter 3 Numerical Methods 3.1 Euler’s Method 74
point can be determined by solving a system of equations. A system of equations is a set of two or more equations. To ÒsolveÓ a system of equations means to find values for the variables in the equations, which make all the equations true at the same time. One way to solve a system of equations is by graphing.
Chapter 1 Introduction 1 1.1 ApplicationsLeading to Differential Equations 1.2 First Order Equations 5 1.3 Direction Fields for First Order Equations 16 Chapter 2 First Order Equations 30 2.1 Linear First Order Equations 30 2.2 Separable Equations 45 2.3 Existence and Uniqueness of Solutionsof Nonlinear Equations 55
CONCEPT IN SOLVING TRIG EQUATIONS. To solve a trig equation, transform it into one or many basic trig equations. Solving trig equations finally results in solving 4 types of basic trig equations, or similar. SOLVING BASIC TRIG EQUATIONS. There are 4 types of common basic trig equations: sin x a cos x a (a is a given number) tan x a cot x a
solving equations from previous grades and is a gateway into the entire unit on equations and inequalities. Conceptual Understanding: Mystery Letters 4-5 days I will review equations by Conceptual Understanding:Solving simple equations, multi-step equations, and equations
9.1 Properties of Radicals 9.2 Solving Quadratic Equations by Graphing 9.3 Solving Quadratic Equations Using Square Roots 9.4 Solving Quadratic Equations by Completing the Square 9.5 Solving Quadratic Equations Using the Quadratic Formula 9.6 Solving Nonlinear Systems of Equations 9 Solving Quadratic Equations
3.1 Theory of Linear Equations 97 HIGHER-ORDER 3 DIFFERENTIAL EQUATIONS 3.1 Theory of Linear Equations 3.1.1 Initial-Value and Boundary-Value Problems 3.1.2 Homogeneous Equations 3.1.3 Nonhomogeneous Equations 3.2 Reduction of Order 3.3 Homogeneous Linear Equations with Constant Coeffi cients 3.4 Undetermined Coeffi cients 3.5 V
