Intro Numerical Analysis
Intro Numerical Analysis MATH 441
Popular in Course
Popular in Mathematics (M)
This 4 page Class Notes was uploaded by Alphonso Thompson on Thursday October 29, 2015. The Class Notes belongs to MATH 441 at Western Carolina University taught by Erin McNelis in Fall. Since its upload, it has received 12 views. For similar materials see /class/230961/math-441-western-carolina-university in Mathematics (M) at Western Carolina University.
Reviews for Intro Numerical Analysis
Report this Material
What is Karma?
Karma is the currency of StudySoup.
Date Created: 10/29/15
MATH 441541 Numerical Analysis Fourth Meeting Root Finding Algorithms cont Thursday September 13th 2007 Root Finding ie Solving Nonlinear Equations in One Variable 0 Section 23 Newton7s Method Secant Method and Method of False Position 1 The Problem 7 Given Suppose you have a continuous and possibly continuously differentiable function f and some reasonable guesses as to a root of the function 7 The Big Question How do you go about nding the root p given this information and the formula for f 2 The Secant Method a Given the continuous function x and two reasonable guesses to the root7 p0 and p1 A Visual Explanation Deriving the Formula for the New Guess at the Root approximation to the solution to zcosm 3 8x 7 3 f What Problems Could Occur g Strengths and Weaknesses of the Secant Method Newton s Method correct to three decimal places OJ a Given continuously differentiable f and one reasonable guesses to the root7 p0 b A Visual Explanation c Deriving the Formula for the New Guess at the Root d Newton s Method Algorithm e The Relation to the Secant Method f An Example Use Newton s Method with initial guess p0 2 to nd an approximation to the solution to zcosm 3 8x 7 3 correct to three decimal places g What Problems Could Occur h Strengths and Weaknesses of Newton s Method The Method of False Position a Given continuous function x and two reasonable guesses to the root7 p0 and p1 that bracket the root b A Visual Explanation c The Formula for the New Guess at the Root d An Example Use the Method of False Position with initial guesses p0 2 and p1 4 to nd an approximation to the solution to zcosm 3 8x 7 3 correct to three decimal places e What Problems Could Occur f Strengths and Weaknesses of Method of False Position q A 0 Section 22 FixedPoint Methods 1 The Problem 7 Given Suppose you have a continuous function f and some reasonable guesses as to a xed point of the function 7 The Big Question How do you go about nding the xed point p given this information and the formula for f 2 What is a xed point7 and how is nding the xed point of a function related to root nding 3 Fixed Point lteration a Given the continuous function x and a reasonable guess to the xed point7 p0 b A Visual Explanation c Deriving the Formula for the New Guess at the Fixed Point d The Fixed Point Algorithm 4 Existence and Uniqueness Theorems a Existence If g 6 CW7 b and a S g S b for all z 6 11 then 9 has at least one xed point7 197 in 11 b Uniqueness i Contraction Mapping Theorem If there also exists a value 0 lt k lt 1 such that 1905 79yl S W 7 241 for all z and y in 11 ie g is a contraction mapping on 0119 then the xed point p is unique ii Text Theorem lf7 in addition to the existence criteria7 g m exists on 11 and a positive constant 1 lt 1 exists with lgm k for all z E 071 then the xed pint in 071 is unique c Fixed Point Theorem Let g 6 CW7 b be such that a S g S b for all z 6 11 Suppose7 in addtion7 tht 9 exists on 11 and that a constant 0 lt k lt 1 exists with lgm k for all z E 071 Then7 for any number p0 in 11 the sequence de ned by pn 9pn71 n 1 converges to the unique xed point p in 11 Also7 the bounds for the error involved in using pn to approximate p are given by lpn 7pl S k maxpo 7 I75 7190 and k 1 7 k lpn7pl lp17pol 7121 d An Example Verify that the function x e m has a unique xed point on 07 1 Use the Fixed Point lteration Method with initial guess p0 09 to nd an approximation to the true xed point correct to three decimal places e What Problems Could Occur f How are the xed point method and Newton s Method related g Strengths and Weaknesses of the Fixed Point Method A 0 Section 24 Error Analysis for Iterative Methods 1 De nition pn0 converges to p with order of convergence 04 If 1973310 converges to p and positive constants Oz and exist such that hm lpn1 7p A Hoe My 7 p04 then pn 0 has order of convergence 4 In particular a If 04 1 the sequence is linearly convergent b If 04 gt 1 the sequence is superlinearly convergent c If 04 2 the sequence is quadratically convergent 2 Theorem Let g E Cab be such that a S g S b for all z E a 1 Suppose in addition that g is continuous on a b and a positive constant k lt 1 exists with g m k for all z 6 ab lf g p 7 0 then for any number 190 in ab the sequence pn1 9pn for n 2 0 converges only linearly to the unique xed point p in a b 3 Theorem Let p be a xed point of Suppose that g p 0 and g is continuous and strictly bounded by M on an open interval I containing p Then there exists a 6 gt 0 such that for pg 6 Lp 7 619 6 the sequence de ned by pn1 9pn when n 2 O converges at least quadratically to p Moreover for suf ciently large values of n M 2 pn1 7p lt 7 Man 19 4 Theorem from 23 Let f E Czab lfp E a b is such that fp 0 and f p 7 0 then there exists a 6 gt 0 such that Newton s method generates a sequence pn0 converging to p for any initial approximation pg 6 p 7 619 6 5 Theorem 1 E Clab has a simple zero at p in a b if and only if fp 0 but f p 7 O 6 Corollary If f E Clab and has a root p on ab there exists an interval about p where Newton s method converges quadratically to p for any initial approximation po 6 a 1 provided that p is not a simple zero 0 A Couple Other Other Root Finding Methods 1 Brief Comment on Horner s Method and Connections with Newton s Method 2 Muller 75 Method a Given the continuous function x and three reasonable guesses to the root m0 m1 and 2 In A Visual Explanation c The Formula for the New Guess for the Root Given three guesses m0 m1 and 2 generate the new approximation mg as where 327 902 21 b sgnbb2 7 4010 b 900 22f961 f902 901 22f900 HM x0 7 m2m1 7 20 m1 901 7 zz mol f901 900 22f951 952 900 7 zzz1 7 zgz0 7 351 d Strengths and Weaknesses 0 Speci c Rates of Convergence for Methods1 McGraw Hill 2002 Page 234 Bisection Secant Newton False Position Fixed Point Muller s Oz 2 a 1 a HT E 162 for simple roots a 1 a x 1839 04 1 for multiple roots 1For Muller s Method rate in particular see Michael T Heath Scienti c Computing An Introductory Survey 2 Ed